Cuprins
Prefaţa ediţiei în limba română ix
Prefaţă xi
1. Introducere l
Algoritmi l
Analiza algoritmilor 5
Proiectarea algoritmilor 10
Rezumat 14
1. Fundamente matematice 18
2. Creşterea funcţiilor 20
Notaţia asimptotică 20
Notaţii standard şi funcţii comune
28
3. Sume 37
Formule de însumare şi proprietăţi
37
Delimitarea sumelor 40
4. Recurenţe 46
Metoda substituţiei 47
Metoda iteraţiei 50
Metoda maşter 53
Demonstraţia teoremei maşter
55
5. Mulţimi etc. 66
Mulţimi 66
Relaţii 70
Funcţii 72
Grafuri 74
Arbori 78
6. Numărare şi probabilitate 86
Numărare 86
Probabilitate 91
Variabile aleatoare discrete
96
Distribuţia geometrică şi distribuţia binomială
100
Cozile distribuţiei binomiale
104
Analiză probabilistică 108
II. Ordonare şi statistici de ordine
116
7. Heapsort 119
Heap-uri 119
Reconstituirea proprietăţii de heap
121
Construirea unui heap 123
Algoritmul heapsort 125
Cozi de priorităţi 126
8. Sortarea rapidă 131
Descrierea sortării rapide
131
Performanţa algoritmului de sortare rapidă
133
Variantele aleatoare ale sortării rapide
137
Analiza algoritmului de sortare rapidă
139
9. Sortare în timp liniar 147
Margini inferioare pentru sortare 147
Sortarea prin numărare 149
Ordonare pe baza cifrelor 152
Ordonarea pe grupe 154
10.Mediane şi statistici de ordine 158
Minim şi maxim 158
Selecţia în timp mediu liniar
159
Selecţia în timp liniar în cazul cel mai defavorabil
161
III. Structuri de date 167
11.Structuri de date elementare 171
Stive şi cozi 171
Liste înlănţuite 174
Implementarea pointerilor şi obiectelor
178
Reprezentarea arborilor cu rădăcină
182
12.Tabele de dispersie 187
Tabele cu adresare directă 187
Tabele de dispersie 189
Funcţii de dispersie 193
12.4. Adresarea deschisă 198
13.Arbori binari de căutare 208
Ce este un arbore binar de căutare?
208
Interogarea într-un arbore binar de căutare
210
Inserarea şi ştergerea 214
Arbori binari de căutare construiţi aleator
217
14.Arbori roşu-negru 226
Proprietăţile arborilor roşu-negru
226
Rotaţii 228
Inserarea 230
Ştergerea 234
15.îmbogăţirea structurilor de date 243
Statistici dinamice de ordine 243
Cum se îmbogăţeşte o structură de date
248
Arbori de intervale 251
IV. Tehnici avansate de proiectare şi analiză
257
16.Programarea dinamică 259
înmulţirea unui şir de matrice
260
Elemente de programare dinamică 266
Cel mai lung subşir comun
270
Triangularea optimă a poligoanelor 275
17.Algoritmi greedy 283
O problemă de selectare a activităţilor
283
Elemente ale strategiei greedy 287
Coduri Huffman 290
Bazele teoretice ale metodei greedy 296
O problemă de planificare a activităţilor
301
18.Analiza amortizată 306
Metoda de agregare 306
Metoda de cotare 310
Metoda de potenţial 312
Tabele dinamice 315
V. Structuri de date avansate 325
19.B-arbori 328
Definiţia B-arborelui 330
Operaţii de bază în B-arbore
333
Ştergerea unei chei dintr-un B-arbore
339
20.Heap-uri binomiale 344
Arbori binomiali şi heap-uri binomiale
345
Operaţii pe heap-uri binomiale
349
21.Heap-uri Fibonacci 362
Structura heap-urilor Fibonacci 363
Operaţiile heap-urilor interclasabile
364
Descreşterea unei chei şi ştergerea unui nod
372
Mărginirea gradului maxim
374
22.Structuri de date pentru mulţimi disjuncte
379
Operaţii pe mulţimi disjuncte
379
Reprezentarea mulţimilor disjuncte prin liste înlănţuite
381
Păduri de mulţimi disjuncte
384
Analiza reuniunii după rang comprimând drumul
388
VI. Algoritmi de grafuri 398
23.Algoritmi elementari de grafuri 400
Reprezentările grafurilor 400
Căutarea în lăţime
403
Căutarea în adâncime 410
Sortarea topologică 417
Componente tare conexe 420
24.Arbori de acoperire minimi 428
Dezvoltarea unui arbore de acoperire minim
429
Algoritmii lui Kruskal şi Prim
433
25.Drumuri minime de sursă unică 441
Drumuri minime şi relaxare 445
Algoritmul Dijkstra 452
Algoritmul Bellman-Ford 456
Drumuri minime de sursă unică în grafuri orientate
aciclice 460
Constrângeri cu diferenţe şi drumurile minime
462
26.Drumuri minime între toate perechile de vârfuri 473
Drumuri minime şi înmulţirea matricelor
475
Algoritmul Floyd-Warshall 480
Algoritmul lui Johnson pentru grafuri rare
486
O modalitate generală pentru rezolvarea problemelor de
drum în grafuri orientate 490
27.Flux maxim 498
Reţele de transport 498
Metoda lui Ford-Fulkerson 505
Cuplaj bipartit maxim 515
Algoritmi de preflux 519
Algoritmul mutare-în-faţă 527
VII. Capitole speciale 541
28.Reţele de sortare 544
Reţele de comparare 544
Principiul zero-unu 548
O reţea de sortare a secvenţelor bitone
550
Reţeaua de interclasare 552
Reţeaua de sortare 555
29.Circuite aritmetice 561
Circuite combinaţionale 561
Circuite de sumare 566
Circuite multiplicatoare 575
Circuite cu ceas 581
30.Algoritmi pentru calculatoare paralele 590
Saltul de pointer 593
Algoritmi CRCW şi algoritmi EREW
601
Teorema lui Brent şi eficienţa efortului
608
Calculul paralel de prefix, eficient ca efort
612
întreruperi deterministe de simetrie 617
31. Operaţii cu matrice 626
Proprietăţile matricelor 626
Algoritmul lui Strassen pentru înmulţirea matricelor
633
Sisteme de numere algebrice şi înmulţirea matricelor
booleene 638
Rezolvarea sistemelor de ecuaţii liniare
642
Inversarea matricelor 653
Matrice simetrice pozitiv-definite şi aproximarea prin
metoda celor mai mici pătrate
657
32.Polinoame şi TFR 666
Reprezentarea polinoamelor 667
TFD şi TFR 673
Implementări eficiente ale TFR
679
33.Algoritmi din teoria numerelor 687
Noţiuni elementare de teoria numerelor
688
Cel mai mare divizor comun 693
Aritmetică modulară 697
Rezolvarea ecuaţiilor liniare modulare
702
Teorema chineză a restului
705
Puterile unui element 708
Criptosistemul RSA cu cheie publică
711
Testul de primalitate 717
Factorizarea întreagă 724
34.Potrivirea şirurilor 731
Algoritmul naiv pentru potrivirea şirurilor
732
Algoritmul Rabin-Karp 735
Potrivirea şirurilor folosind automate finite
739
Algoritmul Knuth-Morris-Pratt 745
Algoritmul Boyer-Moore 751
35.Geometrie computaţională 759
Proprietăţile segmentului de dreaptă
759
Determinarea cazului în care oricare două segmente se
intersectează 764
Determinarea învelitorii convexe 769
Determinarea celei mai apropiate perechi de puncte
778
36.NP-completitudine 785
Timpul polinomial 786
Verificări în timp polinomial
792
NP-completitudine şi reductibilitate
796
Demonstraţii ale NP-completitudinii
804
Probleme NP-complete 810
37.Algoritmi de aproximare 826
Problema acoperirii cu vârfuri 828
Problema comis-voiajorului 830
Problema acoperirii mulţimii
834
Problema sumei submulţimii
838
Bibliografie 845
Index 853
