Curs algoritmi incepatori

8/10/2019 Curs algoritmi incepatori

1/40


2/40

Dedicat memoriei luiMihai Ptracu

Mihai Ptracu, considerat cel mai bun cercettor n nformatic

teoreticdin ultimii 10 ani

Nscut pe 17 iulie 1982 la Craiova, Mihai Ptracu i-a finalizatstudiile universitare laMassachusetts Institute of Technology din StateleUnite, unde a i lucrat ulterior.

Teza lui de doctorat, susinutaici, a fost premiatdrept cea mai bunteza tiinificde la MIT, care este cea mai bine cotatuniversitate lainformaticdin lume.

Mihai a ctigat multe medalii la olimpiadele de specialitate, ajungndpe locul 20 n topul medaliailor la nivel internaional. A obinut de 9 oripremiul I la nivel naional i 7 medalii la fazele internaionale: 4 de auri 3 de argint.

A fost membru al Comitetului Stiinific al Olimpiadei Internaionale deInformatic, presedintele Comitetului tiinific al Balcaniadei deInformatic(2011) i al Olimpiadei Europene de Informatic(2009).

In 2012, Mihai Patrascu a primit premiulPresburger,de la AsociaiaEuropeande InformaticTeoretic, pentru revoluionarea domeniuluide structuri de date.

n vrstde numai 29 de ani, a murit pe data de 5 iunie 2012.

2Lect. Dr. Trimbitas Maria-Gabriela


3/40


4/40

1. CORMEN, THOMAS H. - LEISERSON, CHARLES - RIVEST, RONALD R.:

Introducere n algoritmi. Cluj-Napoca: Editura Computer Libris Agora, 2000.2. SIMONAS SALTENIS:Algorithms and Data Structures, 2002.3. STANDISH, T.A.: Data Structures, Algorithms & Software Principles in C, Addison-

Wesley, 19954. FRENTIU M., POP H.F., SERBAN G.: Programming Fundamentals, Ed.Presa

Universitara Clujeana, Cluj-Napoca, 2006, 234 pagini

5. SEDGEWICK, R.: Algorithmen, Addison-Wesley,19986. WIRTH, N.: Algorithmen und Datenstrukturen, Pascal Version, 5 Auflage, B.G.

Teubner Stuttgart,19987. NICULESCU V., CZIBULA G.: Structuri fundamentale de date. O perspective

orientate obiect. Editura Casa Cartii de Stiinta, Cluj-Napoca,20118. HOROWITZ, E.: Fundamentals of Data Structures in C++. Computer Science Press,

1995.9. MOUNT, DAVID M.: Data Structures. University of Maryland, 1993.10. AMBSBURY, WAYNE: Data Structures. From Arrays to Priority Queues, 1993.11. BRUNO R. PREISS,Data Structures and Algorithms with Object-Oriented Design

Patterns in C++, 1997.

Bibliografie



5/40

1. Introducere

Structuri de date

Algoritmi



6/40

Algoritm

n acest timbru sovietic apare

Muhammad ibn Musa al-Khwarizmi(nscut aproximativ n 780; mortntre 835 i850), matematician

persan iastronom din Khorasanprovincie a Uzbekistanului de azi.Cuvntul algoritmprovine dinnumele lui.



7/40

Definiie(generala) Un algoritm este odescriereprecisifinita unui proces constnd dinpaielementari.

Definiie(Computer Science) Un algoritm este odescriere precisifinita unui proces care este(a) datntr-un limbaj formal i(b) constdin pasielementari iexecutabil i pe

main.



8/40

Reprezentareaalgoritmilor

Descriere verbal Grafic: Structograme, diagrame de flux, etc. Pseudocod

Limbaj de programare . Teza lui Church Toate formele de

reprezentare ale algoritmilor sunt echivalente.

Alonzo Church a fost un matematician american ilogician care a avut contribuiimajore n logica matematicifundamentele teoretice ale informaticii.

WikipediaBorn: June 14, 1903, Washington, D.C., United StatesDied: August 11, 1995, Hudson, Ohio, United StatesBooks: Introduction to Mathematical Logic

http://en.wikipedia.org/wiki/Alonzo_Churchhttps://www.google.com/search?rlz=1T4ADRA_enRO460RO460&q=alonzo+church+born&stick=H4sIAAAAAAAAAGOovnz8BQMDgwoHnxCHfq6-QYpZrqmWWHaylX5Ban5BTiqQKirOz7NKyi_KO-3632nx_YXJU4X5hGb0CFxiYcycCQDpfsapQQAAAA&sa=X&ei=Yz35UuDnNe_e7AbUzYDYAQ&ved=0CJ8BEOgTKAEwFAhttps://www.google.com/search?rlz=1T4ADRA_enRO460RO460&q=washington+district+of+columbia&stick=H4sIAAAAAAAAAGOovnz8BQMDgx4HnxCHfq6-QYpZrqkSmFWUYZatJZadbKVfkJpfkJMKpIqK8_OskvKL8kQur973UvKc0q27Ew7NlMpxY6m-eQAAT2c60ksAAAA&sa=X&ei=Yz35UuDnNe_e7AbUzYDYAQ&ved=0CKABEJsTKAIwFAhttps://www.google.com/search?rlz=1T4ADRA_enRO460RO460&q=alonzo+church+died&stick=H4sIAAAAAAAAAGOovnz8BQMDgy4HnxCHfq6-QYpZrqmWfHaylX5Ban5BTqp-SmpyamJxakp8QWpRcX6eVUpmasqTM5F3bHST0uZc8ehtXBr271ZQlAEA_iSdCUoAAAA&sa=X&ei=Yz35UuDnNe_e7AbUzYDYAQ&ved=0CKQBEOgTKAEwFQhttps://www.google.com/search?rlz=1T4ADRA_enRO460RO460&q=hudson+ohio&stick=H4sIAAAAAAAAAGOovnz8BQMDgzkHnxCHfq6-QYpZrqkSmFVlZFSpJZ-dbKVfkJpfkJOqn5KanJpYnJoSX5BaVJyfZ5WSmZpiGHWBx0Pv3EFTrabYPBYHNr990vYAVYc_hVQAAAA&sa=X&ei=Yz35UuDnNe_e7AbUzYDYAQ&ved=0CKUBEJsTKAIwFQhttps://www.google.com/search?rlz=1T4ADRA_enRO460RO460&q=alonzo+church+books&stick=H4sIAAAAAAAAAGOovnz8BQMDgwYHnxCHfq6-QYpZrqmWVHaylX5Sfn62fmJpSUZ-kRWIXayQn5dTqbk9oYhvvXmHxTbNi1Lpr9Zanr_MAwA_KlpiRQAAAA&sa=X&ei=Yz35UuDnNe_e7AbUzYDYAQ&ved=0CKkBEOgTKAEwFghttps://www.google.com/search?rlz=1T4ADRA_enRO460RO460&q=introduction+to+mathematical+logic+church&stick=H4sIAAAAAAAAAGOovnz8BQMDgxkHnxCHfq6-QYpZrqkSj366vqFRUkFykkFytpZUdrKVflJ-frZ-YmlJRn6RFYhdrJCfl1MpYCWcZvPShH065yFlyWM3hft-qUgCAIr7zmNTAAAA&sa=X&ei=Yz35UuDnNe_e7AbUzYDYAQ&ved=0CKoBEJsTKAIwFghttps://www.google.com/search?rlz=1T4ADRA_enRO460RO460&q=introduction+to+mathematical+logic+church&stick=H4sIAAAAAAAAAGOovnz8BQMDgxkHnxCHfq6-QYpZrqkSj366vqFRUkFykkFytpZUdrKVflJ-frZ-YmlJRn6RFYhdrJCfl1MpYCWcZvPShH065yFlyWM3hft-qUgCAIr7zmNTAAAA&sa=X&ei=Yz35UuDnNe_e7AbUzYDYAQ&ved=0CKoBEJsTKAIwFghttps://www.google.com/search?rlz=1T4ADRA_enRO460RO460&q=alonzo+church+books&stick=H4sIAAAAAAAAAGOovnz8BQMDgwYHnxCHfq6-QYpZrqmWVHaylX5Sfn62fmJpSUZ-kRWIXayQn5dTqbk9oYhvvXmHxTbNi1Lpr9Zanr_MAwA_KlpiRQAAAA&sa=X&ei=Yz35UuDnNe_e7AbUzYDYAQ&ved=0CKkBEOgTKAEwFghttps://www.google.com/search?rlz=1T4ADRA_enRO460RO460&q=hudson+ohio&stick=H4sIAAAAAAAAAGOovnz8BQMDgzkHnxCHfq6-QYpZrqkSmFVlZFSpJZ-dbKVfkJpfkJOqn5KanJpYnJoSX5BaVJyfZ5WSmZpiGHWBx0Pv3EFTrabYPBYHNr990vYAVYc_hVQAAAA&sa=X&ei=Yz35UuDnNe_e7AbUzYDYAQ&ved=0CKUBEJsTKAIwFQhttps://www.google.com/search?rlz=1T4ADRA_enRO460RO460&q=alonzo+church+died&stick=H4sIAAAAAAAAAGOovnz8BQMDgy4HnxCHfq6-QYpZrqmWfHaylX5Ban5BTqp-SmpyamJxakp8QWpRcX6eVUpmasqTM5F3bHST0uZc8ehtXBr271ZQlAEA_iSdCUoAAAA&sa=X&ei=Yz35UuDnNe_e7AbUzYDYAQ&ved=0CKQBEOgTKAEwFQhttps://www.google.com/search?rlz=1T4ADRA_enRO460RO460&q=washington+district+of+columbia&stick=H4sIAAAAAAAAAGOovnz8BQMDgx4HnxCHfq6-QYpZrqkSmFWUYZatJZadbKVfkJpfkJMKpIqK8_OskvKL8kQur973UvKc0q27Ew7NlMpxY6m-eQAAT2c60ksAAAA&sa=X&ei=Yz35UuDnNe_e7AbUzYDYAQ&ved=0CKABEJsTKAIwFAhttps://www.google.com/search?rlz=1T4ADRA_enRO460RO460&q=alonzo+church+born&stick=H4sIAAAAAAAAAGOovnz8BQMDgwoHnxCHfq6-QYpZrqmWWHaylX5Ban5BTiqQKirOz7NKyi_KO-3632nx_YXJU4X5hGb0CFxiYcycCQDpfsapQQAAAA&sa=X&ei=Yz35UuDnNe_e7AbUzYDYAQ&ved=0CJ8BEOgTKAEwFAhttp://en.wikipedia.org/wiki/Alonzo_Church


9/40


10/40

Algoritmii lucreazasupra datelor de intrare, genereazdateintermediare, iar n final produc un rezultat (dat)O structurde date este modul n care data este reprezentatninteriorul masinii, n memorie sau pe disc (vezi icursul BD)

Structurile de date determince pot sfacalgoritmii icu cecost. Mai precis: ct costun anumit pas al unui algoritm

Complexitatea algoritmilor este strns legatde structurile de

date pe care ei le utilizeaz; att de strns ncat unii subsumeazambele concepte sub termenul de algoritm.



11/40

I(nformaia) = D(ata) + S(emantica)P(rogram) = D(ate) + A(lgoritm)

Date (atomicitatea):elementare;structurate.

11Lect. Dr. Cioban Vasile


12/40

Tipuri de SD:(dpdv al memoriei i locului n memorie)

statice: articol (nregistrare), tablou, mulime, etc;

semistatice: stiv, coad, tabel de dispersie;

dinamice: list dinamic, arbore, graf;

Clasificarea SD (dpdv al abstractizrii/implementrii)

SDLogiceDescrierea legturilor ntre elementele tipului (ex: matrice,stiv, coad, arbore, etc.)

SDFizice:Se refer la reprezentarea fizic n memorie a elementelor

domeniului n memorie.



13/40

Stil n proiectarea SD

Un program poate rezolva corect o problem, dar poate fi un programslab din multe puncte de vedere:oare un timp de execuie relativ mare;outilizeaz spaiu de memorie excedentar;odificil de depanat, de citit, de modificat;ogreu reutilizabil sau nereutilizabil n alte proiecte (programe).

SD trebuie concepute astfel nct s nlture neajunsurile de mai sus;3 reguli generale:

R1: Rafinarea pas cu pas (Stepwise refinement);R2: Abstractizare:

ogrupare unor componente n mod logic;os poat fi reutilizate de alte SD, sau alte programe;odetaliile de implementare s fie amnate pn la codificare;osepararea descrierii logice de implementare.

R3: Independen de limbaj.



14/40

Exemplu rafinare:paii n abstractizarea(prin rafinare) unei stive de elemente de tipul TE

step 1: stiva de elemente de tipul TE

step 2: stiv cu alocarea dinamic a elementelor de tipul TE

step 3: stiv cu alocarea dinamic o obiectelor care reprezint elemente de tipul TE

Versiunea 1

Nume = String[15];Persoan =

RecordNumeFam,Prenume:Nume;CodTelefon: 0..1000;

NrTelefon: String[9];Ziua: 1..31;Luna: 1..12;Anul: 1900..2100;

End;

Versiunea 2Nume = String[15];TipTelefon =

RecordCodTelefon: 0..1000;

NrTelefon: String[9];End;

DataCalend =Record

Ziua:1..31;Luna:1..12;

Anul:1900..2100;End;

Persoana =Record

NumeFam,Prenume: Nume;Telefon: TipTelefon;DataNasterii: DataCalend;

End;

Exemplu abstractizare



15/40

2. Complexiti

15


16/40

Observaiipreliminare:

1. Afirmaiile despre complexitatea algoritmilor i a problemelortrebuie sfie de regulindependentede un anumit model demaini anumite proprieti ale implementrii, ca i dedetaliile technologice

2. La studiul funciilor de complexitate nu intereseazatt demult evoluia exacta valorilor unei funcii f:N->R+citendina acesteia, comportamentul ei de cretere(comportament asimptotic) atunci cnd crete argumentul



17/40

Lect. Dr. Trimbitas Maria-Gabriela 17

Reprezentridiferite pentru acelaialgoritm (iprogramele suntreprezentri)

n plus: algoritmi diferiipentru aceeaiproblem

Scop: Comparareaalgoritmilor ntre ei (analiza complexitii)

Criterii: Timpul de execuieispaiulde memorie

Complexitatea se exprimn funciede mulimeaidimensiunea

datelor


18/40


Determinarea timpului de execuie

Posibilitide msurarea eficieneiunui algoritm:1. Implementarea unui algoritm pe un calculator real imsurareatimpuluiDezavantaj:prea multe mrimicare influeneaztimpul, abstraciefcndde algoritmul nsui

2. Numrareapailorde calcul care se efectueazpentru un set de date de

intrare. ntrebare: ce este un pas de calcul? Model formal de calcul de exemplu mainTuring sau RAM programarea algoritmului ntr-un limbaj de programare artificial i

numrareaievaluarea (ponderea) operaiilorDezavantaj: Efort mare, portabilitate incert

3. Numrareaoperaiilorla nivel nalt (de exemplu numrulcomparaiilorlacutareantr-o listsau numrulde perechi de elemente care se interschimbla sortare)

Dezavantaj: Evaluare prea grosolan


19/40


Vom folosi ca metodsimplde msuraretimpul de execuie

Fie datoproblemde dimensiune n

De exemplu sortarea a n valori

Existmai mulialgoritmi pentru rezolvarea problemei

Care algoritm este mai rapid depinde de dimensiunea naproblemei

Pentru valori foarte mari ale lui n, cel mai rapid algoritm va fintotdeauna acela al cruitimp de execuiecretecel maipuinnfunciede n.


20/40

Prof. Dr. Hans Joachim Pflug

20


21/40

Prof. Dr. Hans Joachim Pflug

21


22/40


De regulnu suntem interesaide numrulexact de operaiici de clasede complexitate: cum se modificefortul de calcul, atunci cnd semretevolumul datelor de intrare cu un anumit factor?

Care este comportamentul calitativ al funcieide timp?

Pe noi ne intereseaza cum depinde o resursa consumata de un algoritmde n (dimensiunea problemei)pentru o valoare mare a lui n. Pentru aputea exprima aceasta, matematic corect, se folosesc simbolurile luiLandau.


23/40

Simbolurile lui Landau - ,, , o si

Definiie: g(n) este marginea asimptoticsuperioara lui f(n), dacexisto constantc > 0 iun n0N, astfel nct pentru toi n n0 are loc f(n) cg(n)

Mulimea tuturor funciilor f(n), pentru care o funcie g(n) dateste margine asimptoticsuperioarse noteazcu(g(n)).

Analog se defineste marginea asimptoticinferioar, marginea asimptoticstrns, marginesuperioartare, respectiv margine inferioartare.

Definiie: Fief i g funcii N R+.

Marginea superioar:(g(n)) = {f(n) | c > 0 n0n n0 f(n) cg(n)}Marginea inferioar:(g(n)) = {f(n) | c > 0 n0n n0 cg(n) f(n)}Marginea strns(aceeai cretere):(g(n)) =(g(n) (g(n)))

Margine superioartare:o(g(n)) = {f(n) | c > 0 n0n n0 f(n) cg(n)}Margine inferioartare:(g(n)) = {f(n) | c > 0 n0n n0 cg(n) f(n)}Atenie: Se folosete adesea n locul scrierii corecte f(n) O(g(n)) pentru margineaasimptoticsuperioar, notaia neglijentf(n) =(g(n)).



24/40

Proprietilenotaiilorasimptotice

Tranzitivitate:

Reflexivitate:

Simetrie:

Antisimetrie:



25/40

Notaia(g(n)) Notaia(g(n))

Exemplu:

Fief(n) = n2+1000n demonstrm cf(n2) cu g(n)=n2deci se cautc>0 in0N astfel nct pentru toi nn0f(n)cn2

f(n) = n2+1000nn2+1000n2=1001n2 => c=1001, n0=1

Exemplu:

Fie aceeai funcie

f(n) = n2+1000n demonstrm cf(n2) cug(n)=n2deci se cautc>0 in0N astfel nct pentru toi nn0f(n)cn2

f(n) = n2+1000n 1n2 => c=1, n0=1



26/40

Notaia(g(n))

Din definiiile notaiilor asimptotice rezultcf(n) = n2+1000nf(n2)

TEMA: Sse demonstreze cf(n) = n2+1000nfo(n2log n)



27/40


28/40


La sume se impune termenul cu cretereacea mai rapid.

Demonstraie:


29/40


S-ar putea scrie if(n) = 2n+ 7n + 10 O(2n+ 7n + 10)intereseaznsnumai comparaiacu funciisimple ca de

exemplu O(n), O(n),...Clasa Denumire Exemplu

1 constant Instructiuni elementarelog n logaritmic Cautare binaran linear Minimum unui sir

n2

quadratic Procedee simple de sortaren3 cubic Inversarea matricelornk polinomial Programare Linearan log n superlinear Procedee eficiente de sortare2cn exponential brute-force search,

Backtrackingn! Factorial Permutari,Problema comis-voiajorului, Met.Kramer

Avem: O(1) O(n) ... O(n!)


30/40


Regulde baz:

Cea mai micclasde complexitate (n notatiaO) rezultdin TA(n)prin:oExtragerea termenului dominant(cel mai mare) iprinoRenunareala coeficieni

De exemplu:

T(n)=60n2+ 4n TO(n2);T(n)=lg(n) + 1 TO(lg(n))=O(log(n)),

de ce?


31/40


32/40


(g) Dacf(n) (g) if(n) O(g), atunci f(n) (g) .

Existo limitsuperioarc1i o limitinferioarc2, astfel nct dinpunct de vedere asimptotic pentru toin>n0) este adevrat:c1g(n)f(n)c2g(n)

Exemplu:

f(n) = 2n+ 7n +10=> f(n) (n) pentru n0= 9

Demonstraie:

3n 2n+7n+10 2 npentru n0= 9


33/40

33

MergeSort

Exemplu: Algoritm de tip Divide et impera

Procedure MergeSort (V,p,q)if p q then

m=(p+q) div 2MergeSort (V,p,m)MergeSort (V,m+1,q)Merge (V,p,m,q)

endifEndProcedure


34/40

34

La algoritmul de sortare prin interclasare avem divizarea n 2 subsecvene delungime n/2; deci a=2, iar dimensiunea unei probleme este 1/2

dac p = q avem timp constant (1) (n=1, deci =1);

D(n) = (1), pentru c se determin indicele de mijloc al secvenei (p,q); C(n) = (n), (pentru c interclasarea a 2 secvene de lungime p, respectivq d (p+q-1))

Avem deci:

1n(n),(1)

2

n2T

1n(1),

T(n)sau

1n(n),

2

n2T

1n(1),

T(n)

n final avem recurena

1nn,2

n2T

1n0,

T(n)

Rezolvatla seminar prin metoda iteraiei


35/40

35

Teorema master


36/40


1nn,

2

n2T

1n0,

T(n)

Revenim la recurena obinutla MERGESORT

i aplicnd Teorema master avem a=b=2 => f(n)=(n), deci ne aflm n cazul 2

=> T(n) = (n log n)

Problemtratabil = problema care poate fi rezolvatprintr-un algoritm cutimp de execuie polinomial


37/40


Cazul cel mai nefavorabil, mediu icel mai favorabil

La timpul de execuiedeosebim:

cazul cel mai defavorabil (worstcase),

cazul mediu (averagecase) i

cazul cel mai favorabil (best case).

Cazul mediu este important atunci cnd, cazul cel mai favorabil icazul celmai defavorabil sunt excepiifoarte rare


38/40

Notaia O- are originea n lucrareaDie Elemente derZahlentheorie din anul 1892 a luiPaul Gustav Heinrich Bachmann (1837 - 1920) .

Puin timp mai trziu, a utilizat-o i specialistul in Teorianumerelor Edmund Landau (1877 -1938) i pe lngO aconsiderat i o. Din aceastcauznotaia asimptoticestedenumiti Simbolurile lui Landau

Tot lui Landau i se datoreazi notaia Z pentru numerele

ntregi.

http://commons.wikimedia.org/wiki/File:Edmund_Landau.jpg


39/40


40/40

L t D T i bit M i G b i l 40
http://www.google.com/url?sa=i&rct=j&q=&esrc=s&source=images&cd=&cad=rja&docid=pAglV1ceZ7-w_M&tbnid=Js5McEwqVpdxAM:&ved=0CAUQjRw&url=http://alba24.ro/a-sosit-vremea-martisorului-afla-povestea-micului-simbol-al-primaverii-legat-cu-fir-alb-si-rosu-169610.html&ei=Z7EPU_XhNeSg0QX-toHQCg&bvm=bv.61965928,d.ZGU&psig=AFQjCNF6Pj9FC7qu2pQAIJSlLOa4SSZj0A&ust=1393623719318664

Curs algoritmi incepatori

Documents

Transcript of Curs algoritmi incepatori