Informatikai algoritmusok 3

Eloszó......Page 14
Bevezetés a 3. kötethez......Page 15
V. ADATBÁZISKEZELÉS......Page 19
Bevezetés......Page 20
29.  Adattömörítés (Ulrich Tamm)......Page 21
29.1.1. Diszkrét, emlékezet nélküli forrás......Page 23
29.1.2. Prefix kódok......Page 24
29.1.3. Kraft-egyenlotlenség és a zajmentes kódolás tétele......Page 26
29.1.4. A Shannon-Fano-Elias-kód és a Shannon-Fano algoritmus......Page 30
Elemzés......Page 31
29.2.1. Aritmetikai kódolás......Page 34
Pontossági probléma......Page 37
Elemzés......Page 41
29.3.1. LZ77......Page 48
29.3.2. LZ78......Page 49
Elemzés......Page 50
29.4. Burrows-Wheeler-transzformáció......Page 51
Elemzés......Page 55
29.5.1. Adatábrázolás......Page 56
29.5.2. A diszkrét koszinusz transzformáció......Page 58
29.5.3. Kvantálás......Page 59
29.5.4. Kódolás......Page 60
30.1. Félig strukturált adatok és az XML......Page 67
30.2. Sémák és szimulációk......Page 70
30.3. Lekérdezések és indexek......Page 76
30.4. Stabil partíciók és a PT-algoritmus......Page 83
30.5. A(k)-indexek......Page 92
30.6. D(k)- és M(k)-indexek......Page 95
30.7. Elágazó lekérdezések......Page 103
30.8. Az indexek frissítése......Page 107
31.  Gyakori elemhalmazok keresése (Bodon Ferenc)......Page 117
31.1. Gyakori elemhalmazok keresése......Page 118
31.1.1. Asszociációs szabályok......Page 120
31.2. Gyakori elemhalmazokat kinyero algoritmusok......Page 122
31.2.1. Az Apriori algoritmus......Page 123
Futási ido és memóriaigény......Page 127
31.2.2. Az Eclat algoritmus......Page 132
31.2.3. Az FP-growth algoritmus......Page 135
31.2.4. Toivonen mintavételezo algoritmusa......Page 140
32.  Klaszterezés (Fogaras Dániel és Lukács András)......Page 146
32.1.1. A hasonlóság és távolság tulajdonságai......Page 147
32.1.2. Mátrixábrázolások......Page 148
32.2. A klaszterezo algoritmusok jóságának kérdései......Page 149
32.3.2. Bináris és kategorikus adatok......Page 151
32.4. Dimenzió-csökkentés......Page 152
32.4.1. Szinguláris felbontás......Page 153
32.4.2. Ujjlenyomat alapú dimenzió-csökkentés......Page 158
32.5.1. k-közép......Page 161
32.5.2. k-medoid......Page 164
32.6.1. Felhalmozó és lebontó módszerek......Page 166
32.6.2. Klasztertávolságok mértékei......Page 167
32.6.3. A Rock algoritmus......Page 169
32.7. Suruség alapú eljárások......Page 171
32.7.1. A Dbscan algoritmus......Page 172
32.7.2. Az Optics algoritmus......Page 174
33.1. Lekérdezések......Page 179
Datalog – szabály alapú lekérdezés......Page 181
Táblázatos lekérdezések......Page 182
Relációs algebra*......Page 183
Egyenloség atomok......Page 187
Diszjunkció – egyesítés......Page 188
Tagadás......Page 189
Rekurzió......Page 191
Fixpont szemantika......Page 192
33.1.3. Bonyolultsági kérdések lekérdezések közti tartalmazásról......Page 196
Lekérdezés optimalizálás tábla minimalizálással......Page 197
33.2. Nézetek......Page 201
33.2.1. Nézet, mint lekérdezés eredménye......Page 202
Materializált nézet......Page 203
Lekérdezés optimalizálás......Page 205
Fizikai adatfüggetlenség......Page 206
Adategyesítés......Page 207
33.3.2. Átírás bonyolultsági kérdései......Page 210
33.3.3. Gyakorlati algoritmusok......Page 214
Lekérdezés optimalizálás materializált nézetek használatával......Page 215
System-R stílusú optimalizálás......Page 216
Vödör algoritmus......Page 218
Inverz szabályok......Page 222
MiniCon......Page 228
34.1. Partícionálás......Page 237
34.1.1. Rögzített partíciók......Page 239
34.1.2. Dinamikus partíciók......Page 246
34.2. Lapcserélési algoritmusok......Page 254
34.2.1. Statikus lapcserélés......Page 256
34.2.2. Dinamikus lapcsere......Page 265
34.3.1. Lapcsere......Page 267
34.3.2. Listás ütemezés......Page 269
34.3.3. Párhuzamos feldolgozás átfedéses memóriával......Page 278
34.3.4. Az anomália elkerülése......Page 279
Rendezo gyors algoritmus (QFD)......Page 280
Gazdaságos hatványtípusú optimális algoritmus (EP)......Page 285
34.4.4. Becslések (ULE)......Page 286
34.4.5. Algoritmusok páronkénti összehasonlítása......Page 287
34.4.6. Közelíto algoritmusok hibája......Page 290
35.1. Bevezetés......Page 295
35.2. Funkcionális függoségek......Page 296
35.2.1. Armstrong-axiómák......Page 297
35.2.2. Lezárások......Page 298
35.2.3. Minimális fedés......Page 302
35.2.4. Kulcsok......Page 303
35.3. Relációs sémák szétvágása......Page 305
35.3.1. Veszteségmentes összekapcsolás......Page 307
35.3.2. Veszteségmentes összekapcsolás ellenorzése......Page 308
35.3.3. Funkcionális függoségeket megorzo szétbontások......Page 312
3NF......Page 315
Veszteségmentes összekapcsolású felbontás BCNF-be......Page 316
Függoségmegorzo szétvágás 3NF-re......Page 319
35.3.5. Többértéku függoségek......Page 322
Függoségi bázis......Page 323
Negyedik normálforma (4NF)......Page 325
35.4.1. Összekapcsolási függoségek......Page 329
35.4.2. Elágazó függoségek......Page 330
36.1. A SPARQL kiértékelése MapReduce módszerrel......Page 335
36.1.2. GenerateBestPlan algoritmus......Page 336
36.2. Alkalmazás közösségi hálók elemzésére......Page 341
36.2.1. Közösségi hálózatok reprezentálása RDF segítségével......Page 342
36.2.2. Közösségi hálók lekérdezése és transzformálása......Page 345
36.2.3. Csoportok kiválasztása hatékonyan......Page 349
36.2.4. Közösségi hálózatok lekérdezése MapReduce módszerrel......Page 353
Lekérdezésterv generálás......Page 354
Bemeneti fájl kiválasztása......Page 64
36.2.5. GenerateBestPlan algoritmus......Page 359
36.3.1. Közösségi hálózatok reprezentálása RDF segítségével......Page 364
36.3.2. Közösségi hálók lekérdezése és transzformálása......Page 367
36.3.3. Csoportok kiválasztása hatékonyan......Page 371
36.3.4. Közösségi hálózatok lekérdezése MapReduce módszerrel......Page 375
Lekérdezésterv generálás......Page 376
37.1.1. RDF reprezentáció......Page 382
Szemantika......Page 383
37.2.1. And és Filter muveletek......Page 387
37.2.2. And, Filter és Union muveletek......Page 388
37.2.3. Az Opt muvelet......Page 389
37.2.4. Az unió-normálforma......Page 391
37.2.5. Jól tervezett SPARQL lekérdezések......Page 392
37.3. A SPARQL optimalizálása......Page 396
37.3.1. Algebrai optimalizálás......Page 397
37.3.2. Szemantikus optimalizálás......Page 402
38.1.1. Két szekvencia távolsága lineáris résbüntetés mellett......Page 406
38.1.2. Dinamikus programozás tetszoleges résbüntetés mellett......Page 409
38.1.4. Konkáv résbüntetés......Page 411
38.1.5. Két szekvencia hasonlósága, Smith-Waterman algoritmus......Page 415
38.1.6. Többszörös szekvenciaillesztés......Page 416
38.1.7. Memóriaredukció Hirschberg algoritmusával......Page 418
38.1.8. Memóriaredukció saroklevágással......Page 420
38.2.1. A takarékossági elv kis problémája......Page 423
38.2.2. Felsenstein algoritmusa......Page 424
38.3. Algoritmusok sztochasztikus nyelvtanokon......Page 426
38.3.1. Rejtett Markov-modellek: elore, hátra és Viterbi algoritmusa......Page 427
38.3.2. Sztochasztikus környezetfüggetlen nyelvtanok: belülrol, kívülrol és a CYK algoritmus......Page 429
38.4.1. Címkézett, gyökeres fák illesztése......Page 433
38.4.2. Két rejtett Markov-modell együttes kibocsátási valószínusége......Page 434
38.5. Törzsfakészítés távolságon alapuló algoritmusokkal......Page 436
38.5.1. Osztályozó algoritmusok......Page 438
38.5.2. Szomszédok egyesítése......Page 441
38.6.1. Genomok átrendezodése......Page 447
38.6.2. Sörétes-puska nukleinsavleolvasás......Page 450
39.1. Több választási lehetoséget kínáló rendszerek......Page 457
39.1.1. Példák több választási lehetoséget kínáló rendszerre......Page 459
39.2.1. Lehetséges megoldások eloállítása heurisztikák és ismételt heurisztikák segítségével......Page 462
A lehetséges megoldások összegyujtése különbözo heurisztikák alkalmazásával......Page 463
39.2.2. Bünteto módszer egzakt algoritmusokkal......Page 466
39.2.3. Példák -típusú problémákra......Page 468
Büntetés melletti megoldások keresése az összes 0 paraméterre......Page 469
A büntetéses megoldások monotonitási tulajdonságai......Page 472
Több alternatív megoldás létrehozása ugyanarra az  bünteto paraméterre......Page 475
Egy lineáris programozási feladat, amelyik két alternatív útvonalat ad meg s-bol t-be......Page 477
39.2.6. Bünteto módszer heurisztikák alkalmazásával......Page 482
39.3.1. Tetszoleges futási ideju algoritmusok......Page 484
39.3.3. Egymást követo rögzítések......Page 486
39.3.5. Különbözo további témák......Page 487
40.1. Analitikus geometriai alapok......Page 490
40.1.1. A Descartes-koordinátarendszer......Page 491
40.2.1. Testek......Page 492
40.2.2. Felületek......Page 493
40.2.3. Görbék......Page 494
40.2.4. Normálvektorok......Page 495
40.2.5. Görbemodellezés......Page 496
Bézier-görbe......Page 497
B-spline......Page 498
40.2.6. Felületmodellezés......Page 502
40.2.8. Konstruktív tömörtest geometria......Page 504
40.3. Geometriai feldolgozó és tesszellációs algoritmusok......Page 506
40.3.1. Sokszög és poliéder......Page 507
40.3.3. Egyszeru sokszögek háromszögekre bontása......Page 508
40.3.4. Paraméteres felületek tesszellációja......Page 511
40.3.5. Töröttvonal és felület simítás, felosztott görbék és felületek......Page 513
40.3.6. Implicit felületek tesszellációja......Page 516
40.4. Tartalmazási algoritmusok......Page 518
Háromszög......Page 519
40.4.2. Poliéder-poliéder ütközésvizsgálat......Page 524
Szakaszok vágása féltérre......Page 525
Szakaszok vágása AABB-re......Page 526
40.5. Mozgatás, torzítás, geometriai transzformációk......Page 531
40.5.1. Projektív geometria és homogén koordináták......Page 532
Projektív sík......Page 533
Projektív tér......Page 534
40.5.2. Homogén lineáris transzformációk......Page 536
40.6. Megjelenítés sugárkövetéssel......Page 540
Háromszög metszése......Page 542
AABB metszése......Page 543
40.6.2. A metszéspontszámítás gyorsítási lehetoségei......Page 544
A szabályos felosztási algoritmus ido és tárbonyolultsága......Page 545
A virtuális világ valószínuségi modellje......Page 550
A metszési kísérletek számának várható értéke......Page 551
A cellalépések várható száma......Page 553
A kd-fa......Page 554
40.7. Az inkrementális képszintézis algoritmusai......Page 563
40.7.1. A kamera transzformáció......Page 566
40.7.3. A perspektív transzformáció......Page 567
40.7.4. Vágás homogén koordinátákban......Page 570
40.7.6. Raszterizációs algoritmusok......Page 572
Poligonkitöltés......Page 573
Z-buffer algoritmus......Page 579
Festo algoritmus......Page 581
BSP-fa......Page 585
41.1.1. A vektoros adatmodell......Page 591
41.1.2. A raszteres modell......Page 592
41.2. Térbeli indexelés......Page 593
41.2.1. Grid index......Page 595
41.2.2. Négy-fa......Page 597
41.2.3. Nyolc-fa......Page 601
41.3.1. Az RGB színmodell......Page 602
41.3.2. Hisztogram kiegyenlítés......Page 604
41.3.3. Fourier-transzformáció......Page 606
Dirac-......Page 607
41.3.5. Konvolúció......Page 609
A konvolúció tulajdonságai......Page 610
41.3.6. Szurési algoritmusok......Page 611
Éldetektorok......Page 613
41.4. Mintavételezés......Page 619
41.4.1. Mintavételi tétel......Page 620
41.4.2. A mintavételi tétel néhány következménye......Page 622
Domborzati modellek......Page 623
42.1.1. Hibaszámítási alapismeretek......Page 628
42.1.2. Direkt és inverz hibák......Page 630
42.1.3. Kerekítési hibák és hatásuk a lebegopontos aritmetikában......Page 631
42.1.4. A lebegopontos aritmetikai szabvány......Page 637
A foelemkiválasztásos Gauss-módszer......Page 640
A Gauss-módszer muveletigénye......Page 644
Az LU-felbontás......Page 646
Az LU- és a Cholesky-módszer sávmátrixokon......Page 647
42.2.2. Lineáris egyenletrendszerek iteratív megoldási módszerei......Page 652
42.2.3. Lineáris egyenletrendszerek hibaelemzése......Page 655
Érzékenységvizsgálat......Page 656
Skálázás és prekondicionálás......Page 660
A direkt hiba becslése a reziduális segítségével......Page 662
Az inverz hiba Oettli-Práger-féle becslése......Page 663
42.3. Sajátértékszámítás......Page 666
Ortogonalizálási eljárások......Page 670
A QR-módszer......Page 673
42.4.1. Szabványos lineáris algebrai szubrutinok......Page 678
BLAS 3 rutinok......Page 679
42.4.2. Matematikai szoftverek......Page 682
A közelíto megoldás iteratív javítása......Page 683
Irodalomjegyzék......Page 689
Tárgymutató......Page 705