curs algoritmi incepatori
TRANSCRIPT
-
8/10/2019 Curs algoritmi incepatori
1/40
-
8/10/2019 Curs algoritmi incepatori
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
-
8/10/2019 Curs algoritmi incepatori
3/40
-
8/10/2019 Curs algoritmi incepatori
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
4Lect. Dr. Trimbitas Maria-Gabriela
-
8/10/2019 Curs algoritmi incepatori
5/40
1. Introducere
Structuri de date
Algoritmi
5Lect. Dr. Trimbitas Maria-Gabriela
-
8/10/2019 Curs algoritmi incepatori
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.
6Lect. Dr. Trimbitas Maria-Gabriela
-
8/10/2019 Curs algoritmi incepatori
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.
7Lect. Dr. Trimbitas Maria-Gabriela
-
8/10/2019 Curs algoritmi incepatori
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
8Lect. Dr. Trimbitas Maria-Gabriela
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 -
8/10/2019 Curs algoritmi incepatori
9/40
-
8/10/2019 Curs algoritmi incepatori
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.
10Lect. Dr. Trimbitas Maria-Gabriela
-
8/10/2019 Curs algoritmi incepatori
11/40
I(nformaia) = D(ata) + S(emantica)P(rogram) = D(ate) + A(lgoritm)
Date (atomicitatea):elementare;structurate.
11Lect. Dr. Cioban Vasile
-
8/10/2019 Curs algoritmi incepatori
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.
12Lect. Dr. Cioban Vasile
-
8/10/2019 Curs algoritmi incepatori
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.
13Lect. Dr. Cioban Vasile
-
8/10/2019 Curs algoritmi incepatori
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
14Lect. Dr. Cioban Vasile
-
8/10/2019 Curs algoritmi incepatori
15/40
2. Complexiti
15
-
8/10/2019 Curs algoritmi incepatori
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
16Lect. Dr. Trimbitas Maria-Gabriela
-
8/10/2019 Curs algoritmi incepatori
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
-
8/10/2019 Curs algoritmi incepatori
18/40
Lect. Dr. Trimbitas Maria-Gabriela 18
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
-
8/10/2019 Curs algoritmi incepatori
19/40
Lect. Dr. Trimbitas Maria-Gabriela 19
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.
-
8/10/2019 Curs algoritmi incepatori
20/40
Prof. Dr. Hans Joachim Pflug
20
-
8/10/2019 Curs algoritmi incepatori
21/40
Prof. Dr. Hans Joachim Pflug
21
-
8/10/2019 Curs algoritmi incepatori
22/40
Lect. Dr. Trimbitas Maria-Gabriela 22
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.
-
8/10/2019 Curs algoritmi incepatori
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)).
23Lect. Dr. Trimbitas Maria-Gabriela
-
8/10/2019 Curs algoritmi incepatori
24/40
Proprietilenotaiilorasimptotice
Tranzitivitate:
Reflexivitate:
Simetrie:
Antisimetrie:
24Lect. Dr. Trimbitas Maria-Gabriela
-
8/10/2019 Curs algoritmi incepatori
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
25Lect. Dr. Trimbitas Maria-Gabriela
-
8/10/2019 Curs algoritmi incepatori
26/40
Notaia(g(n))
Din definiiile notaiilor asimptotice rezultcf(n) = n2+1000nf(n2)
TEMA: Sse demonstreze cf(n) = n2+1000nfo(n2log n)
26Lect. Dr. Trimbitas Maria-Gabriela
-
8/10/2019 Curs algoritmi incepatori
27/40
-
8/10/2019 Curs algoritmi incepatori
28/40
Lect. Dr. Trimbitas Maria-Gabriela 28
La sume se impune termenul cu cretereacea mai rapid.
Demonstraie:
-
8/10/2019 Curs algoritmi incepatori
29/40
Lect. Dr. Trimbitas Maria-Gabriela 29
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!)
-
8/10/2019 Curs algoritmi incepatori
30/40
Lect. Dr. Trimbitas Maria-Gabriela 30
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?
-
8/10/2019 Curs algoritmi incepatori
31/40
-
8/10/2019 Curs algoritmi incepatori
32/40
Lect. Dr. Trimbitas Maria-Gabriela 32
(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
-
8/10/2019 Curs algoritmi incepatori
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
-
8/10/2019 Curs algoritmi incepatori
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
-
8/10/2019 Curs algoritmi incepatori
35/40
35
Teorema master
-
8/10/2019 Curs algoritmi incepatori
36/40
Lect. Dr. Trimbitas Maria-Gabriela 36
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
-
8/10/2019 Curs algoritmi incepatori
37/40
Lect. Dr. Trimbitas Maria-Gabriela 37
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
-
8/10/2019 Curs algoritmi incepatori
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.
38Lect. Dr. Trimbitas Maria-Gabriela
http://commons.wikimedia.org/wiki/File:Edmund_Landau.jpg -
8/10/2019 Curs algoritmi incepatori
39/40
-
8/10/2019 Curs algoritmi incepatori
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