A számítógép-programozás művészete 1-3. (ALAPVETŐ ALGORITMUSOK, SZEMINUMERIKUS ALGORITMUSOK, KERESÉS ÉS RENDEZÉS)

ELŐSZÓ Előszó a magyar kiadáshoz D. E. Knuth könyvének magyar nyelvű kiadása sokáig váratott magára. Eddig csak nehezen volt elérhető (oroszul és angolul), itthoni kiadásával azonban mindenki által megszerezhetővé és remélhetőleg sokkal nagyobb hatásúvá is válik. Az előkészítés során egyik fontos szempontunk az volt, hogy - a sokéves késést tovább nem növelve - a lehető leggyorsabban fordítsuk le a három kötetet. Ezért kiváló szakembereket kértünk fel a fordításra és lektorálásra. Ahol tudtuk, lábjegyzetekkel könnyítettük meg az olvasó tájékozódását, a magyar nyelvű irodalmat általában az egyes fejezetek végén jeleztük. Jelöléseink többnyire a szokásos magyar jelölésrendszert követik. Három helyen tértünk el jelentősen a megszokottól: a) tizedespontot használunk, b) Knuthot követve lg x-szel a kettes alapú logaritmust jelöljük és c) ugyancsak Knuthot követve, ,,a mod c"-vel jelöljük a c-re vett legkisebb nemnegatív maradékot. így a=b (modulo c) és a = b mod c nem ugyanaz. Külön köszönjük tehát az OMFB-nek és a Videoton NSZK-beli leányvállalatának a Waldham Electronic-nek, hogy igen jelentős anyagi segítséget nyújtottak e kiadáshoz. Reméljük, hogy a könyv olvasása sok érdekes információt nyújt majd, és hogy az Olvasó örömét és hasznát találja e könyvben. A KIADÓ Vissza TARTALOM 1. kötet Előszó a magyar kiadáshoz 5 Előszó 9 Előszó a második kiadáshoz 17 Megjegyzések a feladatokhoz 21 1. fejezet - Alapfogalmak 25 1.1. Algoritmusok (Székely László) 25 1.2. Matematikai előismeretek (Székely László) 34 1.2.1. Teljes indukció 35 1.2.2. Számok, hatványok és logaritmusok 44 1.2.3. összegek és szorzatok 50 1.2.4. Egészrész-függvények és elemi számelmélet 61 1.2.5. Permutációk és faktoriálisok 67 1.2.6. Binomiális együtthatók 73 1.2.7. Harmonikus számok 95 1.2.8. Fibonacci-számok 99 1.2.9. Generátorfüggvények 107 1.2.10. Elemzünk egy algoritmust 115 1.2.11. Aszimptotikus előállítás 124 1.2.11.1. Az O-jelölés 124 1.2.11.2. Az Euler-féle összegzési formula 128 1.2.11.3. Néhány aszimptotika 133 1.3. MIX (Túrán Tamás) 141 1.3.1. A MIX leírása 141 1.3.2. A MIX Assembly nyelve 161 1.3.3. Alkalmazások permutációkra 181 1.4. Néhány alapvető programozási technika (Túrán Tamás) 203 1.4.1. Szubrutinok 1.4.2. Korutinok 210 1.4.3. Értelmező rutinok 1.4.3.1, Egy MIX szimulátor 219 1,4.3.2. Nyomkövető rutinok 229 1.4.4. Bevitel és kivitel 232 1.4.5. Történeti megjegyzések és bibliográfia 246 2. fejezet - Információs struktúrák 249 2.1. Bevezetés (Szabó Q. Zoltán) 249 2.2. Lineáris listák (Szabó Q. Zoltán) 255 2.2.1. Vermek, sorok és kétvégű sorok 255 2.2.2. Szekvenciális helyfoglalás 261 2.2.3. Láncolt helyfoglalás 272 2.2.4. Ciklikus listák 292 2.2.5. Kétszeresen láncolt listák 299 2.2.6. Tömbök és ortogonális listák 320 2.3. Fák (Gyárfás András, Szabó Q. Zoltán) 330 2.3.1. Bináris fák bejárása 339 2.3.2. Fák reprezentációja bináris fával 355 2.3.3. Fák további reprezentációi 368 2.3.4. Fák alapvető matematikai tulajdonságai 380 2.3.4.1. Szabad fák 381 2.3.4.2. Irányított fák 389 2.3.4.3. A König-lemma 398 2.3.4.4. Fák leszámlálása 402 2.3.4.5. Úthossz 416 2.3.4.6. Történet és bibliográfia 423 2.3.5. Listák és hulladékgyűjtés 424 2.4. Többszörösen láncolt struktúrák (Túrán Tamás) 441 2.5. Dinamikus tárkiosztás (Székely László) 453 2.6. Történeti megjegyzések és bibliográfia (Túrán Tamás) 474 Megoldások 482 A) Függelék - Index a jelölésekhez 625 B) Függelék - Numerikus táblázatok 630 Tárgy- és névmutató 635 2. kötet Előszó a magyar kiadáshoz 8 Előszó 9 Előszó a második kiadáshoz 11 Megjegyzések a feladatokhoz 13 3. fejezet - Véletlenszámok 17 3.1. Bevezetés (Nemetz T.) 17 3.2. Egyenletes eloszlású véletlenszámok generálása (Gerlits J.) 24 3.2.1. A lineáris kongruencia módszere 24 3.2.1.1. A modulus megválasztása 26 3.2.1.2. Az együttható megválasztása 30 3.2.1.3. A potencia 37 3.2.2. Egyéb módszerek 39 3.3. Statisztikai próbák (Nemetz T.) 51 3.3.1. Véletlen adatok általános vizsgálati módszerei 52 3.3.2. Tapasztalati vizsgálatok 71 3.3.3. Elméleti próbák 87 3.3.4. A spektrálpróba 100 3.4. Másfajta véletlen mennyiségek (Gerlits J.) 125 3.4.1. Numerikus eloszlások 125 3.4.2. Véletlen mintavétel és keverés 147 3.5. Mit jelent az, hogy véletlen sorozat? (Gerlits J.) 153 3.6. összefoglalás (Gerlits J.) 180 4. fejezet - Aritmetika 188 4.1. Helyi értékes számrendszerek (Fiala T.) 188 4.2. Lebegőpontos aritmetika (Fiala T.) 208 4.2.1. Egyszeres pontosságú számítások 208 4.2.2. A lebegőpontos aritmetika pontossága 223 4.2.3. Dupla pontosságú számítások 240 4.2.4. Lebegőpontos számok eloszlása 247 4.3. Többszörös pontosságú aritmetika (Fiala T.) 259 4.3.1. Klasszikus algoritmusok 259 4.3.2. Moduláris aritmetika 277 4.3.3. Milyen gyorsan tudunk szorozni? 286 4.4. Különböző alapú számrendszerek közötti átváltás (Fiala T.) 310 4.5. Racionális aritmetika (Freud R.) 321 4.5.1. Törtek 321 4.5.2. A legnagyobb közös osztó 324 4.5.3. Az euklideszi algoritmus elemzése 347 4.5.4. Prímfelbontás 371 4.6. Polinomaritmetika (Hanák G.) 406 4.6.1. Polinomok osztása 408 *4.6.2. Polinomok felbontása 427 4.6.3. Hatványok kiértékelése 447 4.6.4. Polinomok kiértékelése 472 4.7. Műveletek hatványsorokkal (Hanák G.) 511 Megoldások 522 A Függelék - Numerikus mennyiségek táblázatai 659 1. Gyakran használt értékek (decimálisak) 659 2. Gyakran használt értékek (oktálisak) 660 3. Harmonikus számok, Bemoulli-számok, Fibonacci-számok 661 B Függelék - A jelölések magyarázata 663 Név- és tárgymutató 668 3. kötet Előszó a magyar kiadáshoz g Előszó 9 Megjegyzések a feladatokhoz 11 5. fejezet - Rendezés 15 5.1. Permutációk kombinatorikus tulajdonságai 25 1.1.1- Inverziók 25 5.1.2. A multihalmaz permutációi 35 5.1 A Futamok 47 5.1.4. Tablók és involúciók 60 5.2. Belső rendezés 84 5.2.1. Beszúró rendezés 91 5.2.2. Cserélő rendezés 118 5.2.3. Kiválasztó rendezés 154 5.2.4. Rendezés összefésüléssel 175 5.2.5. Szétosztó rendezés 187 5.3. Optimális rendezés 199 5.3.1. Rendezés minimális számú összehasonlítással 199 5.3.2. összefésülés minimális számú összehasonlítással 216 5.3.3. Kiválasztás minimális számú összehasonlítással 226 5.3.4. Rendezőhálózatok 238 5.4. Külső rendezés 264 5.4.1. Többrétű összefésülés és helyettesítő kiválasztás 267 5.4.2. Többfázisú összefésülés 283 5.4.3. Kaszkád összefésülés 305 5.4.4. A szalag visszafelé olvasása 317 5.4.5. Oszcilláló rendezés 330 5.4.6. A szalag-összefésüléssel kapcsolatos gyakorlati megfontolások 336 5.4.7. Külső számjegyes rendezés 363 5.4.8. Kétszalagos rendezés 368 5.4.9. Lemezek és dobok 377 5.5. összefoglalás, történeti és irodalmi megjegyzések 396 6. fejezet - Keresés 407 6.1. Szekvenciális keresések 412 6.2. Keresés kulcsok összehasonlításával 425 6.2.1. Keresés rendezett táblázatban 425 6.2.2. Bináris fakeresések 442 6.2.3. Kiegyensúlyozott fák 471 6.2.4. Többfelé ágazó fák 493 6.3. Digitális keresés 503 6.4. Hash-elés 528 6.5. Visszakeresés másodlagos kulcsok szerint 572 Megoldások 693 A. Függelék - Numerikus mennyiségek táblázatai 733 1. Mennyiségek 40 decimális jegyre 733 2. Mennyiségek nyolcas számrendszerben 734 3. A harmonikus számok, a Bernoulli-számok és a Fibonacci-számok kis n értékekre 735 B. Függelék - Jelölések 737 Tárgy- és névmutató 742