A kosaram
0
MÉG
5000 Ft
a(z) 5000Ft-os
szállítási
értékhatárig

Számítógép-algoritmusok tervezése és analízise

Szerző
Fordító
Lektor
Budapest
Kiadó: Műszaki Könyvkiadó
Kiadás helye: Budapest
Kiadás éve:
Kötés típusa: Fűzött keménykötés
Oldalszám: 487 oldal
Sorozatcím:
Kötetszám:
Nyelv: Magyar  
Méret: 24 cm x 17 cm
ISBN: 963-10-4323-1
Megjegyzés: Fekete-fehér ábrákkal illusztrálva. Tankönyvi szám: 61 011.
Értesítőt kérek a kiadóról

A beállítást mentettük,
naponta értesítjük a beérkező friss
kiadványokról
A beállítást mentettük,
naponta értesítjük a beérkező friss
kiadványokról

Előszó

Az algoritmuselmélet a számítógép-tudomány központi területe. Ezen a területen az elmúlt években jelentős előrehaladás történt. Gyorsabb algoritmusokat fejlesztettek kis, pl. a gyors... Tovább

Előszó

Az algoritmuselmélet a számítógép-tudomány központi területe. Ezen a területen az elmúlt években jelentős előrehaladás történt. Gyorsabb algoritmusokat fejlesztettek kis, pl. a gyors Fourier-transzformációt, ugyanakkor felfedeztek olyan természetesen adódó problémákat is, amelyekre egyáltalán nincs hatékony algoritmus. Az ilyen eredmények megnövelték az érdeklődést az algoritmuselmélet iránt, és az algoritmusok tervezésének és elemzésének területe széles körben elterjedt tudományággá fejlődött. Könyvünkkel e terület alapvető eredményeinek összegyűjtése a célunk. Ez hozzásegíthet az algoritmustervezéssel kapcsolatos egységes elvek és lényeges fogalmak könnyebb tanításához. Vissza

Tartalom

Előszó9
Számítási modellek
Algoritmusok és bonyolultságuk14
Közvetlen elérésű gépek17
KEG programok számítási bonyolultsága23
Tárolt programú modell27
A KEG egyszerűsítései31
Elemi számítási modell: a Turing-gép37
A Turing-gép és a KEG modell közötti kapcsolat42
Egy magas szintű nyelv: az ALGOL-zsargon46
Hatékony algoritmusko tervezése
Adatstruktúrák: listák, sorok és vermek56
Halmazábrázolások61
Gráfok62
Fák65
Rekurzió68
Oszd meg és uralkodj73
Kiegyensúlyozás78
Dinamikus programozás80
Utószó82
Rendezés és rendezési statisztikák
A rendezési feladat90
Radix rendezés91
Rendezés összehasonlításokkal100
Kupacos rendezés (heapsort) - egy O(n log n) összehasonlító rendezés101
A gyorsrendezés - egy O(n log n) várható idejű rendezés106
Rendezési statisztikák111
Rendezési statisztikák várható ideje114
Adatstruktúrák halmazokkal kapcsolatos feladatokra
Alapműveletek halmazokkal124
A tördelés127
Bináris keresés129
Bináris keresőfák131
Optimális bináris keresőfák135
Algoritmus diszjunkt halmazok egyesítésére139
Fastruktúrák az UNIÓ - HOLVAN feladatban144
Az UNIÓ - HOLVAN algoritmus alkalmazásai és kiterjesztései154
Kiegyensúlyozott fák160
Szótárak és elsőbbségi sorok163
Összefésülhető kupacok167
Összefűzhető sorok170
Particionálás172
Összefoglalás179
Gráfalgoritmusok
Minimális költségű feszítőfa188
Mélységi keresés192
Kétszeresen összefüggő komponensek196
Irányított gráfok mélységi keresése204
Erősen összefüggő komponensek205
Útkereső feladatok212
Egy tranzitív lezárási algoritmus215
Legrövidebb utat kijelölő algoritmus217
Útproblémák és mátrixszorzás218
Adott forrásból induló utak problémája223
Irányított (körmentes) gráfok dominátorai: a tárgyalt fogalmak összekapcsolás225
Mátrixszorzás és rokon műveletei
Alapfogalmak242
Strassen mátrixszorzó algoritmusa246
Mátrixok invertálása248
Mátrixok AFP felbontása251
Az AFP felbontása258
Boole-mátrixok szorzása260
A gyors Fourier-transzformáció és alkalmazásai
A véges Fourier-transzformáció és inverze270
A gyors Fourier-transzformáció algoritmusa275
A GYFT végrehajtása bitműveletekkel283
Polinomok szorzása288
A Schönhage-Strassen-féle algoritmus egész számok szorzására289
Az egész számok és a polinomok aritmetikája
Az egész számok és a polinomok hasonlóságáról298
Egész számok szorzása és osztása299
Polinomok szorzása és osztása306
Modulo aritmetika309
Modulo polinomaritmetika és polinomok helyettesítési értékének meghatározása313
A kínai maradéktétel314
A kínai maradéktétel és polinomok interpolációja319
A legnagobb közös osztók és az euklideszi algoritmus321
Aszimptotikusan gyors algoritmus polinomok LNKO-jának kiszámítására324
Egész számok LNKO-ja330
Még egyszer a kínai maradéktételről332
A ritka polinomok333
Mintaillesztő algoritmusok
Véges automaták és reguláris kifejezések340
Reguláris kifejezésminták felismerése348
Alláncok felismerése351
Kétirányú determinisztikus veremtáras automata357
Pozíciófák és azonosító láncok368
NP-teljes feladatok
Nemdeterminisztikus Turing-gépek386
A P és az NP osztály394
Nyelvek és problémák396
NP-teljesség és a kielégíthetőség problémája399
További NP-teljes feladatok406
Polinominális tárkorlátos feladatok416
Néhány bizonyíthatóan kezelhetetlen probléma
Bonyolultsági hierarchiák428
Determinisztikus Turing-gépek tárhierarchiája429
Exponenciális időt és tárat követelő feladat432
Egy nem elemi probléma440
Aritmetikai műveletek számára adható alsó becslések
Testek450
Még egyszer az egyenes vonalú kódról451
Problémák megfogalmazása mátrixokkal454
Alsó korlát szorzásokra a sorok alapján454
Szorzásokra vonatkozó alsó korlát az oszlopok alapján456
Alsó korlát a szorzásokra a sorok és oszlopok alapján461
Előkészítés463
Irodalomjegyzék473
Név- és tárgymutató483
Megvásárolható példányok

Nincs megvásárolható példány
A könyv összes megrendelhető példánya elfogyott. Ha kívánja, előjegyezheti a könyvet, és amint a könyv egy újabb példánya elérhető lesz, értesítjük.

Előjegyzem