Informatikai algoritmusok 3

Description

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