sd_curs-01 (1)

Curs 1.Algoritmi. Introducere. Limbaj algoritmic.

Octombrie, 2013

Continut

Detalii curs

Curs1Algoritmi-IntroducereLimbaj algoritmicTipuri de dateInstructiuniTablouri

Structuri de date Curs 1 Octombrie, 2013 2 / 59

Organizare

I Pagina cursului www.info.uaic.ro/~sd

I Conf. Dr. Cristian GatuI email: [email protected] cabinet: C212 (parter); tel: 0232-201546I url: www.infoiasi.ro/~cgatuI consultatii: vineri, 10:00-12:00

I Lect. Dr. Madalina RaschipI email: [email protected] cabinet: C416; tel: 0232-202469I url: www.info.uaic.ro/~mionitaI consultatii: luni, 10:00-12:00


www.info.uaic.ro/~sd

www.infoiasi.ro/~cgatu

www.info.uaic.ro/~mionita

Obiective

I ınsusirea unei gandiri algoritmice

I dezvoltarea abilitatilor de proiectare de solutii algoritmice

I ınsusirea tehnicilor de utilizare a principalelor structuri de date

I evaluarea timpului de executie ın cazul cel mai nefavorabil


Abilitati

I Gandire algoritmica: scriere de programe

I Intelegerea limbajului algoritmic: citire de programe

I Intelegerea puterii si a limitelor calculului

I Capacitatea de reprezentare a descrierii unei probleme ıntr-un cadrucomputational


Cunoastere

I Declarativa√x = y a.ı.

y2 = x , y >= 0

I ImperativaI Start cu G arbitrarI if G 2 ≈ x STOP

else G = (G + x/G )/2I Repeat step 2

(definitie/axioma) (descriere deductiva)


Continutul cursului

I Algoritmi. Limbaj algoritmic. Tablouri si structuri

I Analiza algoritmilor

I Recursivitate. Analiza aloritmilor recursivi. Teorema master

I Liste liniare. Liste liniare ordonate. Stiva. Coada

I Coada cu prioritati. Max-heap. Colectii de multimi disjuncte

I Arbori binari

I Grafuri

I Sortare interna

I Cautare. Arbori binari de cautare

I Arbori de cautare echilibrati (arbori AVL, rosu-negru, 2-3 arbori,treaps)

I Tabele de dispersie. Rezolvarea coliziunilor


Bibliografie

I T.H. Cormen, C.E. Leiserson, R.L. Rivest: Introducere ınalgoritmi, Libris Agora, 2000

I D. Lucanu, M. Craus: Proiectarea algoritmilor, Polirom, 2008

I S. Skiena: The Algorithm Design Manual, Springer, 2008

I R. Sedgewick, K. Wayne: Algorithms, 4th ed., Addison-Wesley,2011


Cursuri online

I Algorithms: Design and Analysis, Part 1https://www.coursera.org/course/algo

I Algorithms, Part Ihttps://www.coursera.org/course/algs4partI

I Introduction to Algorithmshttp://ocw.mit.edu/courses/

electrical-engineering-and-computer-science/

6-006-introduction-to-algorithms-fall-2011/


https://www.coursera.org/course/algo

https://www.coursera.org/course/algs4partI

http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-006-introduction-to-algorithms-fall-2011/



Evaluare

I forme:I activitatea la seminar(AS)

I patru teste punctate cu note 1-10I participarea activa la seminarii (maxim 2 puncte bonus)I nota seminar: 90% teste + 10% prezenta + 20% bonus

I testele scrise (TS)I 2 teste scrise (sapt. 8, 15-16)

I criterii de promovare:I AS >= 6, TS >= 4


Evaluare

I Normele ECTS (European Credit Transfer System)

I Punctaj Final (PF) = 50%AS + 50%TSI Nota finala

I <= 4 daca sunt ındeplinite conditiile si NU sunt ındeplinite criteriile depromovare,

I = 10 daca PF este in primii 5% din cei promovati (A)I = 9 urmatorii 10% din cei promovati (B)I = 8 urmatorii 20% din cei promovati (C)I = 7 urmatorii 30% din cei promovati (D)I = 6 urmatorii 25% din cei promovati (E)I = 5 ultimii 10% din cei promovati


Continut

Detalii curs



Algoritmi

I Problema, Solutie

I Algoritm: o secventa finita de pasi aranjata ıntr-o ordine logicaspecifica, cu proprietatea ca, atunci cand este executata, produce osolutie pentru o problema data.

I Exemple: reteta culinara, algoritmul lui Euclid, ciurul lui Eratostene

I Algoritm calculator (”computer algorithm”) = un algoritm pentrucare secventa de pasi este executata de un calculator

I Limbaj Algoritmic = un limbaj folosit pentru descrierea algoritmilor


Algoritmi - etimologie

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

I metode pentru adunarea, ınmultirea si ımpartirea numerelor


Algoritmi si structuri de date

I Algoritm: metoda de rezolvare a unei probleme

I Structuri de date: metoda de a pastra informatiaAlgorithms + Data Structures = Programs. — Niklaus Wirth

I De ce studiem algoritmi?I a rezolva probleme dificileI programatori mai buni

I will, in fact, claim that the difference between a bad programmer anda good one is whether he considers his code or his data structures moreimportant. Bad programmers worry about the code. Goodprogrammers worry about data structures and their relationships. —Linus Torvalds (creator of Linux)

I a descori lucruri noimodelele computationale ınlocuiesc modelele matematice

I profit


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);}


Algoritmi - proprietati

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

I iesire (output) – 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.


Algoritmi - Eficienta

I Un algoritm trebuie sa foloseasca un volum rezonabil de resurse decalcul: memorie si timp

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


Algoritmi - Eficienta

20 25 30 35 40 45 500

20

40

60

n

tim

p(s

ecu

nd

e)

RubySchemePython

CJavaC-gcc

Figure : Executia algoritmului recursiv F (Fibonacci)

Comportamentul este diferit ın functie de tipul implementarii; totusidiferentele nu sunt atat de substantiale =⇒ Problema e algoritmul!

(complexitate exponentiala)


Proiectarea algoritmilor

Rezolvarea algoritmica a problemelor presupune urmatoarele etape:I definirea problemei

I abstractizeaza detaliile irelevante

I identificarea clasei din care face parte problema si a unui algoritm deconstructie a solutiei

I analiza corectitudinii si a eficientei algoritmului

I implementarea algoritmului

I repeta (optimizare si generalizare)


Descrierea algoritmilor

I limbaj natural - usurinta ın exprimare

I scheme logice: descrieri grafice ale prelucrarilor din algoritm; rarutilizate ın prezent

I pseudocod: limbaj artificial bazat pe un vocabular si o sintaxa; maiputin riguros ca un limbaj de programare

I limbaj de programare - precizie


Continut

Detalii curs



Limbaj algoritmic

I expresiv pentru a descrie algoritmi

I simplu, pentru a fi usor de ınteles

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

I un model computational adecvat pentru analiza complexitatiialgoritmilor, ın special complexitatea timp


Limbaj algoritmic

https://fmse.info.uaic.ro/tools/K/ → examples → alg

Executabil - se pot face experimente cu algoritmii descrisi


https://fmse.info.uaic.ro/tools/K/

Variabila

I Nume

I Adresa

I Atribute (tip de date asociat valorilor memorate)

I Instanta a variabilei


Modelul de memorie

I Memoria: structura liniara de celuleI variabile

I pointeri


Continut

Detalii curs



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


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



I CaractereI valori: ’a’, ’b’, ...I operatii: nu exista

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



I Operatori pentru numere ıntregi:I aritmetici: a+b, a-b, a*b, a/b, a%bI relationali: a==b, a!=b, a<b, a<=b, a>b, a>=b

I cost uniform: O(1)I cost logaritmic


Continut

Detalii curs



Instructiuni

I Expresii

I Conditionale: if-else if

I Iterative: while repeat for

I Intreruperea secventei: return


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 Exemplu:I Inainte de atribuire:

I Dupa atribuirea u ← −v ∗ u:


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


Instructiuni

I if

I Sintaxa:if < expresie > then

< secventa− instructiuni1 >else

< secventa− instructiuni2 >

if < expresie > then< secventa− instructiuni1 >

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


Exemplu if

I Calcululul minimului a doua numere:

if a < b thenmin← a

elsemin← b

sau

min← aif b < a then

min← b


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.


Exemplu while

I cel mai mic k astfel ıncat 7k >= n pentru un n dat

k ← 0sapte la k ← 1while sapte la k < n do

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


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


Exemplu repeat

I cel mai mic k astfel ıncat 7k >= n pentru un n dat

k ← 0sapte la k ← 1repeat

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

until sapte la k >= n;


Instructiuni

I forI Sintaxa:

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

sau

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

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


Instructiuni

I forI Semantica:

for i ← e1 > to e2 > doS

este echivalenta cu:

i ← e1temp ← e2while i <= temp do

Si ← i + 1


Instructiuni

I forI Semantica:

for i ← e1 > downto e2 > doS

este echivalenta cu:

i ← e1temp ← e2while i >= temp do

Si ← i − 1


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


Subprograme

I Proceduri:

I Sintaxa:

procedure nume(lista-parametri-formali)secventa-instructiuni

end procedure

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


Proceduri

I Exemplu:

procedure swap(x, y)aux ← xx ← yy ← aux

end procedure

SWAP(a, b)SWAP(b, c)


Subprograme

I Functii:I Sintaxa:

function nume(lista-parametri-formali)secventa-instructiuni

end function

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 >


Functii

I Exemplu:

function max3(x, y, z)temp ← x y > temptemp ← y if z > temp then

temp ← z

return tempend function

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


Continut

Detalii curs



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)


Tablouri unidimensionale


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 ]

I Costul operatiilorI a[i ] : O(1)I a[i ]← v : O(1)


Tablouri bidimensionale



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



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]



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 ]


sd_curs-01 (1)

Documents

Transcript of sd_curs-01 (1)