Előszó | 9 |
Számítási modellek | |
Algoritmusok és bonyolultságuk | 14 |
Közvetlen elérésű gépek | 17 |
KEG programok számítási bonyolultsága | 23 |
Tárolt programú modell | 27 |
A KEG egyszerűsítései | 31 |
Elemi számítási modell: a Turing-gép | 37 |
A Turing-gép és a KEG modell közötti kapcsolat | 42 |
Egy magas szintű nyelv: az ALGOL-zsargon | 46 |
Hatékony algoritmusko tervezése | |
Adatstruktúrák: listák, sorok és vermek | 56 |
Halmazábrázolások | 61 |
Gráfok | 62 |
Fák | 65 |
Rekurzió | 68 |
Oszd meg és uralkodj | 73 |
Kiegyensúlyozás | 78 |
Dinamikus programozás | 80 |
Utószó | 82 |
Rendezés és rendezési statisztikák | |
A rendezési feladat | 90 |
Radix rendezés | 91 |
Rendezés összehasonlításokkal | 100 |
Kupacos rendezés (heapsort) - egy O(n log n) összehasonlító rendezés | 101 |
A gyorsrendezés - egy O(n log n) várható idejű rendezés | 106 |
Rendezési statisztikák | 111 |
Rendezési statisztikák várható ideje | 114 |
Adatstruktúrák halmazokkal kapcsolatos feladatokra | |
Alapműveletek halmazokkal | 124 |
A tördelés | 127 |
Bináris keresés | 129 |
Bináris keresőfák | 131 |
Optimális bináris keresőfák | 135 |
Algoritmus diszjunkt halmazok egyesítésére | 139 |
Fastruktúrák az UNIÓ - HOLVAN feladatban | 144 |
Az UNIÓ - HOLVAN algoritmus alkalmazásai és kiterjesztései | 154 |
Kiegyensúlyozott fák | 160 |
Szótárak és elsőbbségi sorok | 163 |
Összefésülhető kupacok | 167 |
Összefűzhető sorok | 170 |
Particionálás | 172 |
Összefoglalás | 179 |
Gráfalgoritmusok | |
Minimális költségű feszítőfa | 188 |
Mélységi keresés | 192 |
Kétszeresen összefüggő komponensek | 196 |
Irányított gráfok mélységi keresése | 204 |
Erősen összefüggő komponensek | 205 |
Útkereső feladatok | 212 |
Egy tranzitív lezárási algoritmus | 215 |
Legrövidebb utat kijelölő algoritmus | 217 |
Útproblémák és mátrixszorzás | 218 |
Adott forrásból induló utak problémája | 223 |
Irányított (körmentes) gráfok dominátorai: a tárgyalt fogalmak összekapcsolás | 225 |
Mátrixszorzás és rokon műveletei | |
Alapfogalmak | 242 |
Strassen mátrixszorzó algoritmusa | 246 |
Mátrixok invertálása | 248 |
Mátrixok AFP felbontása | 251 |
Az AFP felbontása | 258 |
Boole-mátrixok szorzása | 260 |
A gyors Fourier-transzformáció és alkalmazásai | |
A véges Fourier-transzformáció és inverze | 270 |
A gyors Fourier-transzformáció algoritmusa | 275 |
A GYFT végrehajtása bitműveletekkel | 283 |
Polinomok szorzása | 288 |
A Schönhage-Strassen-féle algoritmus egész számok szorzására | 289 |
Az egész számok és a polinomok aritmetikája | |
Az egész számok és a polinomok hasonlóságáról | 298 |
Egész számok szorzása és osztása | 299 |
Polinomok szorzása és osztása | 306 |
Modulo aritmetika | 309 |
Modulo polinomaritmetika és polinomok helyettesítési értékének meghatározása | 313 |
A kínai maradéktétel | 314 |
A kínai maradéktétel és polinomok interpolációja | 319 |
A legnagobb közös osztók és az euklideszi algoritmus | 321 |
Aszimptotikusan gyors algoritmus polinomok LNKO-jának kiszámítására | 324 |
Egész számok LNKO-ja | 330 |
Még egyszer a kínai maradéktételről | 332 |
A ritka polinomok | 333 |
Mintaillesztő algoritmusok | |
Véges automaták és reguláris kifejezések | 340 |
Reguláris kifejezésminták felismerése | 348 |
Alláncok felismerése | 351 |
Kétirányú determinisztikus veremtáras automata | 357 |
Pozíciófák és azonosító láncok | 368 |
NP-teljes feladatok | |
Nemdeterminisztikus Turing-gépek | 386 |
A P és az NP osztály | 394 |
Nyelvek és problémák | 396 |
NP-teljesség és a kielégíthetőség problémája | 399 |
További NP-teljes feladatok | 406 |
Polinominális tárkorlátos feladatok | 416 |
Néhány bizonyíthatóan kezelhetetlen probléma | |
Bonyolultsági hierarchiák | 428 |
Determinisztikus Turing-gépek tárhierarchiája | 429 |
Exponenciális időt és tárat követelő feladat | 432 |
Egy nem elemi probléma | 440 |
Aritmetikai műveletek számára adható alsó becslések | |
Testek | 450 |
Még egyszer az egyenes vonalú kódról | 451 |
Problémák megfogalmazása mátrixokkal | 454 |
Alsó korlát szorzásokra a sorok alapján | 454 |
Szorzásokra vonatkozó alsó korlát az oszlopok alapján | 456 |
Alsó korlát a szorzásokra a sorok és oszlopok alapján | 461 |
Előkészítés | 463 |
Irodalomjegyzék | 473 |
Név- és tárgymutató | 483 |