Introducere in algoritmi
By Thomas H Cormen, Charles E Leiserson, Ronald R Rivest, Horia Florin Pop, Simona Motogna, Paul A Blaga
Language: Romanian
Category: Ebook - Math/Science/Tech
Categories: Science
Uploader:
Uploaded At: 2022-04-22 12:41:48
nonfiction, algorithms, computer science, mathematics, data structures
Description
Există cărți riguroase despre algoritmi, dar care nu tratează un spectru larg al acestora și există cărți care acoperă majoritatea algoritmilor, dar nu sunt riguroase. "Introducere în algoritmi" combină, pentru a echilibra cele două extreme, atât rigurozitatea cât și gama de algoritmi abordați ale cărților mai sus menționate. Datorită structurării conținutului, cartea poate fi folosită ca o lectură exhaustivă asupra algoritmilor, dar și ca un ghid punctual asupra unor probleme specifice.
Cartea se adresează, în primul rând, celor care studiază la nivel elementar sau academic algoritmi și structuri de date. Deoarece tratează aspecte teoretice și practice, legate de proiectarea algoritmilor, este la fel de binevenită elevilor, studenților, profesorilor și autodidacților.
"Introducere în algoritmi" acoperă atât metodele clasice cât și metodele moderne ca, analiza amortizată și algoritmii paraleli. Prezentarea matematică, riguroasă, este atent detaliată în așa fel încât să fie accesibilă tuturor cititorilor. Capitolele încep cu elemente de bază, avansând spre subiecte mai complexe.
Felul în care sunt prezentate diversele subiecte în capitole, permit studiul independent al acestora, ușurând astfel dobândirea cunoștințelor tratate. Aceasta, împreună cu prezentarea algoritmilor în pseudocod (traduși și aceștia în limba română), asigură o lecturare ușoară de către oricare programator familiarizat cu limbaje de programare ca Fortran, C, Pascal etc. Algoritmii sunt însoțiți de exemple numeroase și pertinente, cu peste 260 de imagini, numeroase exerciții și studii de caz. Această abordare dublă, teoretică și practică, mărește eficiența subiectelor tratate.
Autorii își desfășoară activitatea în cadrul catedrei de Electronică și Informatică a unuia dintre cele mai mari centre universitare ale lumii, Massachussetts Institute of Technology.
La traducerea în limba română au colaborat studenți și cadre didactice de la Universitatea Babeș Bolyai, Cluj, Universitatea Tehnică din Cluj, Universitatea București și Academia de Studii Economice din București.
Cuprins
Prefaţa ediţiei în limba română ix
Prefaţă xi
1. Introducere
1.1. Algoritmi . . . . . . . .
1.2. Analiza algoritmilor . .
1.3. Proiectarea algoritmilor
1.4. Rezumat . . . . . . . . .
I.
Fundamente matematice
2. Creşterea funcţiilor
2.1. Notaţia asimptotică . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.2. Notaţii standard şi funcţii comune . . . . . . . . . . . . . . . . . . . . . . . . . . 20
3. Sume
3.1. Formule de însumare şi proprietăţi . . . . . . . . . . . . . . . . . . . . . . . . . .
3.2. Delimitarea sumelor . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
4. Recurenţe
4.1. Metoda substituţiei . .
4.2. Metoda iteraţiei . . . .
4.3. Metoda master . . . .
4.4. Demonstraţia teoremei master
5. Mulţimi etc.
5.1. Mulţimi .
5.2. Relaţii . .
5.3. Funcţii . .
5.4. Grafuri .
5.5. Arbori . . .
6. Numărare şi probabilitate
6.1. Numărare . . . . . . . . . . . . . . . . . . . . .
6.2. Probabilitate . . . . . . . . . . . . . . . . . . .
6.3. Variabile aleatoare discrete . . . . . . . . . . .
6.4. Distribuţia geometrică şi distribuţia binomială
6.5. Cozile distribuţiei binomiale . . . . . . . . . . .
6.6. Analiză probabilistică . . . . . . . . . . . . . .
Ordonare şi statistici de ordine
7. Heapsort
7.1. Heap-uri . . . . . . . . . .
7.2. Reconstituirea proprietăţii
7.3. Construirea unui heap . .
7.4. Algoritmul heapsort . . .
7.5. Cozi de priorităţi . . . . .
8. Sortarea rapidă
8.1. Descrierea sortării rapide . . . . . . . . . .
8.2. Performanţa algoritmului de sortare rapidă
8.3. Variantele aleatoare ale sortării rapide . . .
8.4. Analiza algoritmului de sortare rapidă . . . .
9. Sortare în timp liniar
9.1. Margini inferioare pentru sortare
9.2. Sortarea prin numărare . . . . .
9.3. Ordonare pe baza cifrelor . . . .
9.4. Ordonarea pe grupe . . . . . . . .
10.Mediane şi statistici de ordine
10.1. Minim şi maxim . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
10.2. Selecţia în timp mediu liniar . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
10.3. Selecţia în timp liniar în cazul cel mai defavorabil . . . . . . . . . . . . . . . . . . 158
Structuri de date
11.Structuri de date elementare
11.1. Stive şi cozi . . . . . . . . . . . . . . .
11.2. Liste înlănţuite . . . . . . . . . . . . .
11.3. Implementarea pointerilor şi obiectelor
11.4. Reprezentarea arborilor cu rădăcină .
167
12.Tabele de dispersie
187
12.1. Tabele cu adresare directă . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 187
12.2. Tabele de dispersie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 189
12.3. Funcţii de dispersie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 193Cuprins
v
12.4. Adresarea deschisă . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 198
13.Arbori binari de căutare
13.1. Ce este un arbore binar de căutare? . . . .
13.2. Interogarea într-un arbore binar de căutare
13.3. Inserarea şi ştergerea . . . . . . . . . . . . .
13.4. Arbori binari de căutare construiţi aleator . .
14.Arbori roşu-negru
14.1. Proprietăţile arborilor roşu-negru
14.2. Rotaţii . . . . . . . . . . . . . . .
14.3. Inserarea . . . . . . . . . . . . .
14.4. Ştergerea . . . . . . . . . . . . . .
15.Îmbogăţirea structurilor de date
243
15.1. Statistici dinamice de ordine . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 243
15.2. Cum se îmbogăţeşte o structură de date . . . . . . . . . . . . . . . . . . . . . . . 248
15.3. Arbori de intervale . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 251
IV.
Tehnici avansate de proiectare şi analiză
16.Programarea dinamică
16.1. Înmulţirea unui şir de matrice . . .
16.2. Elemente de programare dinamică
16.3. Cel mai lung subşir comun . . . . .
16.4. Triangularea optimă a poligoanelor
17.Algoritmi greedy
17.1. O problemă de selectare a activităţilor .
17.2. Elemente ale strategiei greedy . . . . . .
17.3. Coduri Huffman . . . . . . . . . . . . .
17.4. Bazele teoretice ale metodei greedy . . .
17.5. O problemă de planificare a activităţilor .
18.Analiza amortizată
18.1. Metoda de agregare
18.2. Metoda de cotare . .
18.3. Metoda de potenţial
18.4. Tabele dinamice . . .
V. Structuri de date avansate
19.B-arbori
328
19.1. Definiţia B-arborelui . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 330
19.2. Operaţii de bază în B-arbore . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 333
19.3. Ştergerea unei chei dintr-un B-arbore . . . . . . . . . . . . . . . . . . . . . . . . . 339vi
Cuprins
20.Heap-uri binomiale
344
20.1. Arbori binomiali şi heap-uri binomiale . . . . . . . . . . . . . . . . . . . . . . . . 345
20.2. Operaţii pe heap-uri binomiale . . . . . . . . . . . . . . . . . . . . . . . . . . . . 349
21.Heap-uri Fibonacci
21.1. Structura heap-urilor Fibonacci . . . .
21.2. Operaţiile heap-urilor interclasabile . .
21.3. Descreşterea unei chei şi ştergerea unui
21.4. Mărginirea gradului maxim . . . . . .
22.Structuri de date pentru mulţimi disjuncte
22.1. Operaţii pe mulţimi disjuncte . . . . . . . . . . . . . . .
22.2. Reprezentarea mulţimilor disjuncte prin liste înlănţuite .
22.3. Păduri de mulţimi disjuncte . . . . . . . . . . . . . . . .
22.4. Analiza reuniunii după rang comprimând drumul . . . . .
Algoritmi de grafuri
23.Algoritmi elementari de grafuri
23.1. Reprezentările grafurilor . . . .
23.2. Căutarea în lăţime . . . . . . .
23.3. Căutarea în adâncime . . . . .
23.4. Sortarea topologică . . . . . . .
23.5. Componente tare conexe . . . .
24.Arbori de acoperire minimi
428
24.1. Dezvoltarea unui arbore de acoperire minim . . . . . . . . . . . . . . . . . . . . . 429
24.2. Algoritmii lui Kruskal şi Prim . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 433
25.Drumuri minime de sursă unică
25.1. Drumuri minime şi relaxare . . . . . . . . . . . . .
25.2. Algoritmul Dijkstra . . . . . . . . . . . . . . . . . .
25.3. Algoritmul Bellman-Ford . . . . . . . . . . . . . .
25.4. Drumuri minime de sursă unică în grafuri orientate aciclice
25.5. Constrângeri cu diferenţe şi drumurile minime . . .
26.Drumuri minime între toate perechile de vârfuri
26.1. Drumuri minime şi înmulţirea matricelor . . . . . . .
26.2. Algoritmul Floyd-Warshall . . . . . . . . . . . . . . .
26.3. Algoritmul lui Johnson pentru grafuri rare . . . . . .
26.4. O modalitate generală pentru rezolvarea problemelor de drum în grafuri orientate 473
27.Flux maxim
27.1. Reţele de transport . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 498
27.2. Metoda lui Ford-Fulkerson . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 505
27.3. Cuplaj bipartit maxim . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 515Cuprins
vii
27.4. Algoritmi de preflux . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 519
27.5. Algoritmul mutare-în-faţă . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 527
VII.
Capitole speciale
541
28.Reţele de sortare
28.1. Reţele de comparare . . . . . .
28.2. Principiul zero-unu . . . . . . .
28.3. O reţea de sortare a secvenţelor bitone
28.4. Reţeaua de interclasare . . . .
28.5. Reţeaua de sortare . . . . . . . . . . .
29.Circuite aritmetice
29.1. Circuite combinaţionale
29.2. Circuite de sumare . . .
29.3. Circuite multiplicatoare
29.4. Circuite cu ceas . . . . . .
30.Algoritmi pentru calculatoare paralele
30.1. Saltul de pointer . . . . . . . . . . . . . .
30.2. Algoritmi CRCW şi algoritmi EREW . .
30.3. Teorema lui Brent şi eficienţa efortului . .
30.4. Calculul paralel de prefix, eficient ca efort
30.5. Întreruperi deterministe de simetrie . . . . .
31.Operaţii cu matrice
31.1. Proprietăţile matricelor . . . . . . . . . . . . . . . . . . . . .
31.2. Algoritmul lui Strassen pentru înmulţirea matricelor . . . . .
31.3. Sisteme de numere algebrice şi înmulţirea matricelor booleene
31.4. Rezolvarea sistemelor de ecuaţii liniare . . . . . . . . . . . . .
31.5. Inversarea matricelor . . . . . . . . . . . . . . . . . . . . . . .
31.6. Matrice simetrice pozitiv-definite şi aproximarea prin metoda celor mai mici pătrate . . . . . . . . . . . . . . . . . .
32.Polinoame şi TFR
32.1. Reprezentarea polinoamelor . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 667
32.2. TFD şi TFR . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 673
32.3. Implementări eficiente ale TFR . . . . . . . . . . . . . . . . . . . . . . . . . . . . 679
33.Algoritmi din teoria numerelor
33.1. Noţiuni elementare de teoria numerelor
33.2. Cel mai mare divizor comun . . . . . . .
33.3. Aritmetică modulară . . . . . . . . . . .
33.4. Rezolvarea ecuaţiilor liniare modulare .
33.5. Teorema chineză a restului . . . . . . . .
33.6. Puterile unui element . . . . . . . . . . .
viii
Cuprins
33.7. Criptosistemul RSA cu cheie publică . . . . . . . . . . . . . . . . . . . . . . . . . 711
33.8. Testul de primalitate . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 717
33.9. Factorizarea întreagă . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 724
34.Potrivirea şirurilor
34.1. Algoritmul naiv pentru potrivirea şirurilor .
34.2. Algoritmul Rabin-Karp . . . . . . . . . . .
34.3. Potrivirea şirurilor folosind automate finite
34.4. Algoritmul Knuth-Morris-Pratt . . . . . . .
34.5. Algoritmul Boyer-Moore . . . . . . . . . . .
35.Geometrie computaţională
35.1. Proprietăţile segmentului de dreaptă . . . . . . . . . . . . . . . . . .
35.2. Determinarea cazului în care oricare două segmente se intersectează
35.3. Determinarea învelitorii convexe . . . . . . . . . . . . . . . . . . . .
35.4. Determinarea celei mai apropiate perechi de puncte . . . . . . . . . . .
36.NP-completitudine
36.1. Timpul polinomial . . . . . . . . . .
36.2. Verificări în timp polinomial . . . . .
36.3. NP-completitudine şi reductibilitate
36.4. Demonstraţii ale NP-completitudinii
36.5. Probleme NP-complete . . . . . . . . .
37.Algoritmi de aproximare
37.1. Problema acoperirii cu vârfuri
37.2. Problema comis-voiajorului .
37.3. Problema acoperirii mulţimii
37.4. Problema sumei submulţimii
Bibliografie 845
Index 853