Algoritmi. Limbaj algoritmic - profs.info.uaic.rosd/curs/curs-01.pdf · Algoritmi. Introducere...

Algoritmi. Limbaj algoritmic

SD 2017/2018

Continut

Algoritmi. Introducere

Limbaj algoritmic

Tipuri de date

Tablouri si structuri

FII, UAIC Curs 1 SD 2017/2018 2 / 55

Exemplu

I o secventa de numere: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ...

I secventa Fibonacci

definitia matematica: Fn =

0, if n = 01, if n = 1

Fn−1 + Fn−2, if n > 1

I implemetare C

i n t F ( i n t n ) {i f ( n == 0) return 0 ;e l s e i f ( n == 1) return 1 ;e l s e

return F ( n−1) + F ( n−2);}

FII, UAIC Curs 1 SD 2017/2018 3 / 55

Algoritmi: etimologie

Muhammad ibn Musa al-Khwarizmi - matematician persan; a scris primacarte de algebra (cca. 830).

I metode pentru adunarea, ınmultirea si ımpartirea numerelor.

FII, UAIC Curs 1 SD 2017/2018 4 / 55

Algoritmi: definit, ie

I Nu exista o definit, ie standard pentru not, iunea de algoritm.

I Cambridge Dictionary:

“A set of mathematical instructions that must be followed in a fixedorder, and that, especially if given to a computer, will help tocalculate an answer to a mathematical problem.”

I Schneider and Gersting 1995 (Invitation for Computer Science):

“An algorithm is a well-ordered collection of unambiguous andeffectively computable operations that when executed produces aresult and halts in a finite amount of time.”

I Gersting and Schneider 2012 (Invitation for Computer Science, 6ndedition):

“An algorithm is ordered sequence of instructions that is guaranteedto solve a specific problem.”

FII, UAIC Curs 1 SD 2017/2018 5 / 55

Algoritmi: definit, ie

I Wikipedia:

“In mathematics and computer science, an algorithm is a step-by-stepprocedure for calculations. Algorithms are used for calculation, dataprocessing, and automated reasoning. An algorithm is an effectivemethod expressed as a finite list of well-defined instructions forcalculating a function. Starting from an initial state and initial input(perhaps empty), the instructions describe a computation that, whenexecuted, proceeds through a finite number of well-defined successivestates, eventually producing “output” and terminating at a finalending state. The transition from one state to the next is notnecessarily deterministic; some algorithms, known as randomizedalgorithms, incorporate random input.”

FII, UAIC Curs 1 SD 2017/2018 6 / 55

Algoritmi: model de calcul, problema rezolvata

Toate definit, iile au ceva ın comun:

I datele/informat, ia s, i procesarea acestora/acesteia ın pas, i. Acesteasunt descrise ın general de un model de calcul.Un model de calcul este format din:

I memorie - modul de reprezentare a datelor.

I instruct, iunisintaxa - descrie sintactic pas, ii de procesare;semantica - descrie pas, ii de procesare realizat, i de execut, ia uneiinstruct, iuni; ın general este data de o relat, ie de tranzit, ie pesteconfigurat, ii (sistem tranzit, ional).

I un algoritm trebuie sa produca un rezultat, adica un algoritm trebuiesa rezolve o problema.O problema este ın general reprezentata de o pereche(input, output), unde input reprezinta descrierea datelor de intrare(instant, a) iar output descrierea datelor de ies, ire (rezultatul).

FII, UAIC Curs 1 SD 2017/2018 7 / 55

Algoritmi s, i Structuri de date

I Algoritm: metoda de rezolvare a unei probleme.

I Structuri de date: metoda de a pastra/reprezenta informat, ia.

Algorithms + Data Structures = Programs. — Niklaus Wirth

I will, in fact, claim that the difference between a bad programmer and agood one is whether he considers his code or his data structures moreimportant. Bad programmers worry about the code. Good programmersworry about data structures and their relationships. — Linus Torvalds

FII, UAIC Curs 1 SD 2017/2018 8 / 55

Algoritmi: proprietati

I input (intrare) – zero sau mai multe entitati de date furnizate dinexterior.

I output (ies, ire) – algoritmul produce informatie.

I terminare – pentru orice intrare, algoritmul executa un numar finitde pasi.

I corectitudine – algoritmul se termina si produce iesirea corectapentru orice intrare; spunem ca algoritmul rezolva problema data.

FII, UAIC Curs 1 SD 2017/2018 9 / 55

Algoritmi: eficienta

I Un algoritm trebuie sa foloseasca un volum rezonabil de resurse decalcul: [spat, iu de] memorie si timp [de execut, ie].

I Avem nevoie de algoritmi eficienti pentru:I a salva timpi de asteptare, spatiu de depozitare, consum energie, etc.;

I scalabilitate: putem rezolva probleme de dimensiuni mari cu aceleasiresurse (CPU, memorie, disc, etc.);

I solutii optimizate.

FII, UAIC Curs 1 SD 2017/2018 10 / 55

Algoritmi: eficienta

20 25 30 35 40 45 500

20

40

60

n

tim

p(s

ecu

nd

e)

RubySchemePython

CJavaC-gcc

Figura : Executia algoritmului recursiv F (Fibonacci).

Observat, ie: Comportamentul este diferit ın functie de tipul implementarii; totusi diferentele nu

sunt atat de substantiale =⇒ Problema e algoritmul! (complexitate exponentiala)

FII, UAIC Curs 1 SD 2017/2018 11 / 55

Proiectarea algoritmilor

Rezolvarea algoritmica a problemelor presupune urmatoarele etape:

I definirea problemeiI abstractizeaza detaliile irelevante;

I identificarea clasei din care face parte problema s, i a unui algoritm deconstruct, ie a solut, iei;

I analiza corectitudinii s, i a eficient, ei algoritmului;

I implementarea algoritmului;

I (optimizare si generalizare).

FII, UAIC Curs 1 SD 2017/2018 12 / 55

Descrierea algoritmilor

I informal: limbaj natural.

I formal:

I notat, ie matematica (mas, ini Turing, lambda-calcul (Church), funct, iirecursive, etc.);

I limbaje de programare: de nivel inalt, de nivel jos, declarative (e.g.,programare funct, ionala, programare logica). Acesta poate fi s, i unmodel informal daca nu exista o semnatica formala pentru limbaj.

I semiformal:

I pseudo-cod: combina notat, ia formala a limbajelor de prgramare culimbajul natural;

I notat, ie grafica: scheme logice, automate (state machines), diagramede activitat, i.

FII, UAIC Curs 1 SD 2017/2018 13 / 55

Continut


Limbaj algoritmic

Tipuri de date


FII, UAIC Curs 1 SD 2017/2018 14 / 55

Limbaj algoritmic

Avem nevoie de un limbaj care este

I simplu: pentru a fi usor de ınteles;

I expresiv: pentru a descrie algoritmi;

I abstract, ın descrierea algoritmului accentul cade pe gandireaalgoritmica si nu pe detaliile de implementare;

I un model de calcul adecvat pentru analiza complexitatii algoritmilor,ın special complexitatea timp.

FII, UAIC Curs 1 SD 2017/2018 15 / 55

Variabila

I Nume

I Adresa

I Atribute (tip de date asociat valorilor memorate)

I Instanta a variabilei

FII, UAIC Curs 1 SD 2017/2018 16 / 55

Modelul de calcul

I Memoria: structura liniara de celule

I variabile

I pointeri

FII, UAIC Curs 1 SD 2017/2018 17 / 55

Continut


Limbaj algoritmic

Tipuri de date


FII, UAIC Curs 1 SD 2017/2018 18 / 55

Tip de date

I Domeniu (colectia de obiecte)

I Operatii

I Categorii de tipuri de date:I Tipuri de date elementare

I Tipuri de date structurate de nivel josI operatiile la nivel de componenta

I Tipuri de date de nivel ınaltI operatiile implementate de algoritmi utilizator

FII, UAIC Curs 1 SD 2017/2018 19 / 55

Tipuri de date elementare

I Numere ıntregiI valori: numere ıntregiI operatii: +, -, ...

I Numere realeI valori: numere rationaleI operatii: +, -, ...

I Valori booleeneI valori: true, falseI operatii: and, or, not

FII, UAIC Curs 1 SD 2017/2018 20 / 55


I CaractereI valori: ’a’, ’b’, ...I operatii: —

I PointeriI valori: adrese de variabile apartinand altui tip, valoarea NULLI operatii: —I referire indirecta: *p

FII, UAIC Curs 1 SD 2017/2018 21 / 55


I Operatori pentru numere ıntregi:

I aritmetici: a+b, a-b, a*b, a/b, a%b

I relationali: a==b, a!=b, a<b, a<=b, a>b, a>=b

operatietimp(operatie)

cost uniform cost logaritmic

a + b O(1) O(max(loga, logb))

...

FII, UAIC Curs 1 SD 2017/2018 22 / 55

Instructiuni

I Expresii

I Compuse (bloc): {instructiuni}

I Conditionale: if if-else

I Iterative: while repeat for

I Intreruperea secventei: return

FII, UAIC Curs 1 SD 2017/2018 23 / 55

Instructiuni

I Atribuirea

I Sintaxa: < variabila >←< expresie >

I Sematica:I se evalueaza < expresie > si rezultatul obtinut se memoreaza ın locatia

desemnata de < variabila >I este singura instructiune cu ajutorul careia se poate modifica continutul

memoriei

I cost uniform O(1), cost logaritmic O(log < expresie >)

FII, UAIC Curs 1 SD 2017/2018 24 / 55

Atribuirea

Exemplu:

I Inainte de atribuire:

I Dupa atribuirea u ← −v ∗ u:

FII, UAIC Curs 1 SD 2017/2018 25 / 55

Instructiuni

I Atribuirea ın cazul pointerilor

I Sintaxa:∗ < variabila pointer >←< expresie >

I Sematica:I se evalueaza < expresie > si rezultatul obtinut se memoreaza ın locatia

de la adresa stocata ın < variabila pointer >

I Exemplu: ∗p ← 10

FII, UAIC Curs 1 SD 2017/2018 26 / 55

Instructiuni

I if

I Sintaxa:if < expresie > then

< secventa− instructiuni1 >else

< secventa− instructiuni2 >

if < expresie > then< secventa− instructiuni1 >

Observatie: < expresie > este o expresie cu rezultat boolean dupaevaluare

I Semantica:I Se evalueaza < expresie >. Daca rezultatul este true, atunci se executa

< secventa− instructiuni1 > iar daca rezultatul este false, atunci seexecuta < secventa− instructiuni2 > dupa care instructiunea if setermina

FII, UAIC Curs 1 SD 2017/2018 27 / 55

Instructiunea if

I cost uniform O(1), cost logaritmic O(1)

I Exemplu: calcululul minimului a doua numere:

if a < b thenmin← a

elsemin← b

saumin← aif b < a then

min← b

FII, UAIC Curs 1 SD 2017/2018 28 / 55

Instructiuni

I while

I Sintaxa:while < expresie > do

< secventa− instructiuni >

I Semantica:I Se evalueaza < expresie >I Daca rezultatul este true atunci se executa < secventa− instructiuni >

dupa care se reia procesul ıncepand cu pasul 1. Daca rezultatul estefalse atunci executia instructiunii while se termina.

FII, UAIC Curs 1 SD 2017/2018 29 / 55

Exemplu while

I cel mai mic k astfel ıncat 7k >= n pentru un n datk ← 0sapte la k ← 1while sapte la k < n do

k ← k + 1sapte la k ← sapte la k ∗ 7

FII, UAIC Curs 1 SD 2017/2018 30 / 55

Instructiuni

I repeat

I Sintaxa:repeat

< secventa− instructiuni >until < expresie >;

I Semantica:Instructiunea:

repeatS

until e;

simuleaza executia urmatorului program:

Swhile not e do

S

FII, UAIC Curs 1 SD 2017/2018 31 / 55

Exemplu repeat

I cel mai mic k astfel ıncat 7k >= n pentru un n datk ← 0sapte la k ← 1repeat

k ← k + 1sapte la k ← sapte la k ∗ 7

until sapte la k >= n;

FII, UAIC Curs 1 SD 2017/2018 32 / 55

Instructiuni

I forI Sintaxa:

for < variabila >←< expresie1 > to < expresie2 > do< secventa− instructiuni >

saufor < variabila >←< expresie1 > downto < expresie2 > do

< secventa− instructiuni >

Observatie: < variabila > este o variabila de tip ıntreg, iar< expresie1 > si < expresie2 > sunt expresii cu rezultat ıntreg dupaevaluare

FII, UAIC Curs 1 SD 2017/2018 33 / 55

Instructiuni

I forI Semantica:

for i ← e1 to e2 doS

este echivalenta cu:i ← e1temp ← e2while i <= temp do

Si ← i + 1

FII, UAIC Curs 1 SD 2017/2018 34 / 55

Instructiuni

I forI Semantica:

for i ← e1 downto e2 doS

este echivalenta cu:i ← e1temp ← e2while i >= temp do

Si ← i − 1

FII, UAIC Curs 1 SD 2017/2018 35 / 55

Subprograme

I Limbajul este modular: un program contine un numar de module

I Un modul ın limbajul prezentat este identificat cu un subprogram

I Subprograme:I ProceduriI Functii

FII, UAIC Curs 1 SD 2017/2018 36 / 55

Subprograme

I Proceduri:

I Sintaxa:

Procedure nume (lista-parametri-formali)begin

secventa-instructiuniend

I Apel: NUME(lista-parametri-actuali)I interfata ıntre o procedura si modulul care o apeleaza se realizeaza doar

prin intermediul parametrilor si a variabilelor globale

FII, UAIC Curs 1 SD 2017/2018 37 / 55

Proceduri

I Exemplu:

Procedure SWAP (x,y)begin

aux ← xx ← yy ← aux

end

Apel:SWAP(a, b)SWAP(b, c)

FII, UAIC Curs 1 SD 2017/2018 38 / 55

Subprograme

I Functii:I Sintaxa:

Function nume (lista-parametri-formali)begin

secventa-instructiuniend

secventa-instructiuni contine macar o instructiune return < expr >

I Apel: NUME(lista-parametri-actuali)

utilizat ıntr-o expresie: valoarea ıntoarsa de functie este cea obtinutaprin evaluarea < expr >

FII, UAIC Curs 1 SD 2017/2018 39 / 55

Functii

I Exemplu:

Function max3(x,y,z)begin

temp ← xif y > temp then

temp ← yif z > temp then

temp ← zreturn temp

end

Apel:max3(a, b, c)2*max3(a, b, c) > 5

FII, UAIC Curs 1 SD 2017/2018 40 / 55

Continut


Limbaj algoritmic

Tipuri de date


FII, UAIC Curs 1 SD 2017/2018 41 / 55

Tablouri

I Ansamblu omogen de variabile numite componentele tabloului

I Toate componentele apartin aceluiasi tip

I Componentele sunt identificate cu ajutorul indicilor

I Tablourile sunt utilizate pentru a reprezenta multimi, secvente(ordinea elementelor este importanta), matrici

I Tablourile pot fi:I unidimensionale (1-dimensionale)I bidimensionale (2-dimensionale)

FII, UAIC Curs 1 SD 2017/2018 42 / 55

Tablouri unidimensionale

FII, UAIC Curs 1 SD 2017/2018 43 / 55

Tablouri unidimensionale

I Memoria este o secventa contigua de locatii

I Ordinea de memorare – ordinea indicilor

I Operatiile se realizeaza prin intermediul componentelorExemple:

for i ← 0 to n − 1 doa[i ]← 0

for i ← 0 to n − 1 doc[i ]← a[i ] + b[i ]

FII, UAIC Curs 1 SD 2017/2018 44 / 55

Tablouri

Costul operatiilor:



a[i ] O(1) O(i + logai )

a[i ]← v O(1) O(i + logv)

unde a este un tablou de dimensiune n, cu valorile a[0], ..., a[n − 1]

FII, UAIC Curs 1 SD 2017/2018 45 / 55

Tablouri bidimensionale

FII, UAIC Curs 1 SD 2017/2018 46 / 55


I Memorie contigua de mxn locatiiI Componentele sunt identificate cu ajutorul a 2 indici:

I primul indice are valori {0, 1, . . . ,m − 1}I al doilea indice are valori {0, 1, . . . , n − 1}I variabilele componente :

a[0, 0], a[0, 1], . . . , a[0, n − 1], a[1, 0], a[1, 1], . . . , a[1, n − 1], . . . , a[m −1, 0], a[m − 1, 1], . . . , a[m − 1, n − 1]

I Ordinea de memorare a componentelor este data de ordinealexicografica a indicilor

FII, UAIC Curs 1 SD 2017/2018 47 / 55


I Cu analogia de la matrici, un tablou 2-dimensional poate fi privit caun tablou 1-dimensional ın care fiecare componenta este un tablou1-dimensional.

I Notatie: a[0][0], a[0][1], . . . , a[0][n − 1], . . . , a[m − 1][0], a[m −1][1], . . . , a[m − 1][n − 1]

FII, UAIC Curs 1 SD 2017/2018 48 / 55


I Operatiile cu tablori 2-dimensionale se realizeaza prin intermediulcomponentelor

for i ← 0 to m − 1 dofor j ← 0 to n–1 do

c[i , j ]← 0for k ← 0 to p–1 do

c[i , j ]← c[i , j ] + a[i , k] ∗ b[k, j ]

FII, UAIC Curs 1 SD 2017/2018 49 / 55

Siruri de caractere

I Pot fi considerate ca fiind tablouri unidimensionale cu elemente de tipcaracter

I Constantele sir de caracter se noteaza utilizand “ ”:“Sir-de-caractere”

I Operatii: Concatenarea, notata cu +:“un sir” + “alt sir” = “un siralt sir”

FII, UAIC Curs 1 SD 2017/2018 50 / 55

Structuri

I Structura: ansamblu eterogen de variabile numite campuri.

I Structura are un nume si fiecare camp are propriul nume si propriultip.

I Exemple: o structura pentru a reprezenta puncte ın plan are douacampuri: x s, i y ; o structura pentru a reprezenta o persoana poateavea trei campuri: nume, varsta, adresa;

I Numele complet al unui camp:punct.x, punct.ypersoana.nume, persoana.varsta, persoana.adresa.stradadaca p este pointer la persoana: p− > varsta

FII, UAIC Curs 1 SD 2017/2018 51 / 55

Structuri

I Memoria alocata este o zona contigua; elementele sunt memorate ınordinea declararii ın structura

FII, UAIC Curs 1 SD 2017/2018 52 / 55

Structuri si pointeri

FII, UAIC Curs 1 SD 2017/2018 53 / 55

Structuri

Costul operatiilor:



S .x O(1) O(logSx)

S .x ← v O(1) O(logv)

FII, UAIC Curs 1 SD 2017/2018 54 / 55

Execut, ia unui algoritm

I Calcul: succesiunea de pas, i elementari determinat, i de execut, iainstruct, iunilor ce compun algoritmul.

I Configurat, ie: starea memoriei + instruct, iunea curenta;I In exemplul de mai jos calculul este dat de secvent, a de configurat, ii

(c0 7→ c1 7→ · · · 7→ c12).

x ← 0i ← 1while i < 6 do

x ← x ∗ 10 + ii ← i + 2

Pasul Instruct, iunea i x0 x ← 0 – –1 i ← 1 – 02 1 < 6 1 03 x ← x ∗ 10 + i 1 04 i ← i + 2 1 15 3 < 6 3 16 x ← x ∗ 10 + i 3 17 i ← i + 2 3 138 5 < 6 5 139 x ← x ∗ 10 + i 5 13

10 i ← i + 2 5 13511 7 < 6 7 13512 7 135

FII, UAIC Curs 1 SD 2017/2018 55 / 55



I Configurat, ie: starea memoriei + instruct, iunea curenta;

I In exemplul de mai jos calculul este dat de secvent, a de configurat, ii(c0 7→ c1 7→ · · · 7→ c12).


x ← x ∗ 10 + ii ← i + 2


10 i ← i + 2 5 13511 7 < 6 7 13512 7 135

FII, UAIC Curs 1 SD 2017/2018 55 / 55



I Configurat, ie: starea memoriei + instruct, iunea curenta;I In exemplul de mai jos calculul este dat de secvent, a de configurat, ii

(c0 7→ c1 7→ · · · 7→ c12).


x ← x ∗ 10 + ii ← i + 2


10 i ← i + 2 5 13511 7 < 6 7 13512 7 135

FII, UAIC Curs 1 SD 2017/2018 55 / 55

Algoritmi. Limbaj algoritmic - profs.info.uaic.rosd/curs/curs-01.pdf · Algoritmi. Introducere...

Documents

Transcript of Algoritmi. Limbaj algoritmic - profs.info.uaic.rosd/curs/curs-01.pdf · Algoritmi. Introducere...