Algoritmusok

Szerző

Lektor

Budapest

'Rónyai Lajos: Algoritmusok ' összes példány

Kiadó:	Typotex Kft.
Kiadás helye:	Budapest
Kiadás éve:	1998
Kötés típusa:	Ragasztott papírkötés
Oldalszám:	349 oldal
Sorozatcím:
Kötetszám:
Nyelv:	Magyar
Méret:	24 cm x 17 cm
ISBN:	963-9132-16-0
Megjegyzés:	Fekete-fehér ábrákkal illusztrálva.

É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

Fülszöveg

Algoritmusokkal és adatszerkezetekkel kapcsolatos ismeretekre, készségekre mindenkinek szüksége van, aki komolyan foglalkozik programozással és programok tervezésével. Ennek megfelelően kialakult egy eléggé letisztult törzsanyag, amit világszerte oktatnak a számítástechnikai, informatikai képzést nyújtó egyetemi szakokon. A könyv elsődleges célja ennek az anyagnak a feldolgozása.
A legfontosabb témák a következők: rendezés, keresés, információtömörítés, gráflogaritmusok, a kiszámíthatóság alapfogalmai, nevezetes bonyolultsági osztályok (P, NP) és algoritmustervezési módszerek. A bemutatott algoritmusok tárgyalását példák és feladatok teszik teljessé.
A könyv szerzői évek óta tanítanak algoritmus témájú tárgyakat a Budapesti Műszaki Egyetemen és az Eötvös Loránd Tudományegyetemen.

Tartalom

Bevezetés	9
Algoritmikus problémák megoldása	12
A feladattól a modellig	14
Közlekedési lámpák ütemezése	14
Arthur király civilizációs törekvései	16
Algoritmusok	18
Szuperforrás keresése	18
Hosszú egészek párhuzamos összeadása	21
Rendezés	25
Keresés rendezett halmazban	27
Összehasonlítás alapú rendező módszerek	29
Buborék-rendezés	30
Beszúrásos rendezés	31
Egy alsó becslés	33
Összefésüléses rendezés	35
A kupac adatszerkezet és kupacos rendezés	37
Gyorsrendezés	42
A k-adik elem kiválasztása	44
Kulcsmanipulációs rendezések	46
Ládarendezés (binsort)	47
Radix rendezés	48
A Batcher-féle páros-páratlan összefésülés	50
Külső tárak tartalmának rendezése	51
Összefésüléses rendezés külső tárakon	52
Keresőfák	57
Bináris fák	58
Bináris keresőfák, naiv algoritmusok	60
2-3-fák	64
B-fák	69
AVL-fák	71
További megjegyzések kiegyensúlyozott fákról	77
Egy önszervező megoldás: az S-fák	80
Szófák	83
Hash-elés és szekvenciális keresés	86
A hash-elés alapjai	87
Vödrös hash-elés	88
Nyitott címzés	90
Hash-függvények	95
Hash-elés kontra keresőfák	98
Szekvenciális keresés	99
Információtömörítés	102
A Huffman-kód	102
A Lempel-Ziv-Welch-módszer	106
Gráflogaritmusok	110
Bevezetés	110
Alapfogalmak, jelölések	111
Gráfok ábrázolásai	113
A legrövidebb utak problémája (egy forrásból)	115
Dijkstra módszere	116
A Bellman-Ford-módszer	120
Floyd módszere az összes csúcspár közötti távolság meghatározására	122
Floyd módszere	123
Tranzitív lezárás	125
Egy alkalmazás: centrum keresése irányított gráfban	126
Mélységi bejárás	127
Irányított gráfok mélységi bejárása	128
Irányított körmentes gráfok (DAG-ok)	135
Erősen összefüggő (erős) komponensek	141
Irányítatlan gráfok mélységi bejárása	144
A szélességi bejárás	146
Minimális költségű feszítőfák	151
Prim módszere	156
Kruskal módszere	160
Az Unió-Holvan adatszerkezet	162
Megjegyzések	166
Maximális párosítás páros gráfokban	167
A magyar módszer	168
Maximális folyamatok hálózatokban	171
Kapcsolat a minimális vágással: a Ford-Fulkerson-tétel	174
A Ford-Fulkerson-algoritmus	178
Edmonds-Karp és Dinic algoritmusai	179
Alkalmazások	183
Turing-gépek	190
A Turing-gép fogalma	191
Idő- és tárigény	197
Néhány szimuláció	198
A kiszámíthatóság alapfogalmai	202
Az univerzális Turing-gép	205
Alapvető kiszámíthatatlansági tételek	208
A diagonális nyelv - egy nem rekurzíve felsorolható nyelv	208
Az univerzális nyelv - egy rekurzíve felsorolható, de nem rekurzív nyelv	209
Összefüggések a kiszámíthatósági fogalmak között	210
Rekurzivitás és rekurzíve felsorolhatóság	211
Függvények és halmazok (nyelvek)	213
További eldöndthetetlen problémák	215
A Megállási probléma (Halting problem)	216
Hilbert 10. problémája	217
A Dominóprobléma	222
Post megfeleltetési problémája	226
Egy nyitott kérdés: a kongruens számok felismerése	227
Kolmogorov-bonyolultság	229
A közvetlen elérésű gép (RAM)	239
Az NP nyelvosztály	246
Idő- és tárkorlátok	247
Tár-idő-tétel, nevezetes nyelvosztályok	250
Nemdeterminisztikus Turing-gépek; az NP nyelvosztály	255
Néhány NP-beli nyelv	262
3 színnel színezhető gráfok	262
Hamilton-körrel rendelkező gráfok	262
Síkba rajzolható gráfok	263
A prímszámok nyelve	265
A felismerés és a keresés kapcsolata (prímtényezős felbontás)	266
Karp-redukció. NP-teljesség	268
A SAT nyelv és a Cook-Levin-tétel	272
További NP-teljes feladatok	275
Konjuktív normálformájú formulák kielégíthetősége és a 3-SAT	276
3 színnel színezhető gráfok	278
Maximális méretű független pontrendszer gráfokban	280
A 3 dimenziós házasítás és az X3C feladat	282
Hamilton-kört tartalmazó gráfok és az Utazó ügynök probléma	285
A Hátizsák feladat és néhány más rokon probléma	289
Lineáris programozás	292
Minimális késésszámú ütemezés	296
Néhány általános algoritmus-tervezési módszer	297
Elágazás és korlátozás	299
Dinamikus programozás	302
Közelítő algoritmusok	305
Véletlent használó módszerek	310
Az RP nyelvosztály	314
Prímtesztelés	316
Nagy prímszám keresése	320
Prekondícionálás	321
Nyilvános kulcsú titkosírások	328
Kriptográfia - a titkosírások tudománya	328
Nyilvános kulcsú kriptográfia	331
A Rivest-Shamir-Adleman- (RSA-) kód	332
Tárgymutató	336

Témakörök

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