.

0 (hodnocen0 x )

BK

VYRAZENO

Praha : SNTL - Nakladatelství technické literatury, 1991

ISBN 80-03-00537-X

* konečné automaty * pojednání * programování * vyhledávání

000117914

Rekat.

1. ÚVOD 9 // 1.1 Motivace 9 // 1.2 Status quo 10 // 1.3 Obsah, forma a cfl knihy 11 // 2. ZÁKLADNÍ POJMY A DEFINICE 14 // 2.1 Vyhledávací problémy ; 14 // 2.2 Statické a dynamické datové typy 15 // 2.3 Příklady vyhledávacích problémů 17 // 2.4 Taxonomie vyhledávacích algoritmů 18 // 2.5 Výpočtový model a míry složitosti 19 // 3. JEDNOROZMĚRNÉ VYHLEDÁVÁNÍ: // SLOVNÍKY A PRIORITNÍ FRONTY 22 // 3.1 Úvod // 3.2 . Adresní vyhledávací algoritmy // 3.2.1 Charakteristický vektor. . . // 3.2.2 Využití hrubé síly // 3.2.3 Hašování // 3.2.4 Odkrytá adresace // 3.2.5 Separátní řetězení // 3.2.6 Rostoucí hašovací tabulky. . // 3.2.7 Optimální hašovací tabulky . // 3.2.8 Adaptabilní hašovací tabulky // 3.2.9 Setříděné hašovarí tabulky 31 // 3.2.10 Hašování se dvěma kolizními funkcemi 32 // 3.2.11 Nejhorší případ hašování 32 // 3.2.12 Perfektní hašování 34 // 3.2.13 Minimální perfektní hašování 35 // 3.2.14 Praktické perfektní hašování. 37 // 3.2.15 Interpolační hašování. : 39 // 5 // // 3.2.16 Externí interpolační hašování 41 // 3.2.17 Rozšířitelné hašování 43 // 3.2.18 Hašovací stromy 44 // 3.2.19 Digitální vyhledávací stromy 45 // 3.3 Asociativní vyhledávání ’ . 48 // 3.3. í Nesetříděné pole 48 // 3.3.2 Heuristiky pro sekvenční vyhledávání 49 // 3.3.3 Setříděné pole

52 // 3.3.4 Interpolační vyhledávání 53 // 3.3.5 Interpolačně-binámí vyhledávání 54 // 3.3.6 Neohraničené vyhledávání 55 // 3.3.7 Binární vyhledávací stromy 56 // 3.3.8 Vyvážené vyhledávací stromy 59 // 3.3.9 Váhově vyvážené stromy 60 // 3.3.10 Výškově vyvážené stromy 63 // 3.3.11 Srostlé stromy 67 // 3.3.12 Optimální vyhledávací stromy 68 // 3.3.13 Zkosené stromy 71 // 3.4 Vyhledávání v minimálním prostoru 75 // 3.4.1 Slovníkový problém v minimálním prostoru 75 // 3.4.2 Blokově setříděné pole 76 // 3.4.3 Mřížově setříděné pole 77 // 3.4.4 Rotované seznamy 79 // 3.4.5 Implicitní datová struktura pro slovníkový problém s polylogaritmickou časovou složitostí 82 // 4. MNOHOROZMĚRNÉ VYHLEDÁVANÍ 87 // 4.1 Úvod 87 // 4.2 Základní problémy mnohorozměrného vyhledávání 88 // 4.3 Dotazy na úplnou shodu 89 // 4.3.1 Lexikografické vyhledávání v poli 89 // 4.3.2 Lexikografické vyhledávací stromy 91 // 4.4 Dotazy na částečnou shodu 95 // 4.4.1 A:-rozměmé binární vyhledávací stromy 95 // 4.4.2 Implicitní datové struktury pro vyhledávání na částečnou // shodu 98 // 4.4.3 Optimální vyhledávání na částečnou shodu 99 // 4.4.4 Mnohorozměrné digitální vyhledávací stromy pro dotazy na // částečnou shodu 100 // 4.4.5 Rozkladové hašování 102 // 4.5 Dotazy na intervalovou shodu 103 // 6 // 4.5.1 Sekvenční

vyhledávání // 4.5.2 Projekce // 4.5.3 Sítě // 4.5.4 /?-rozměmé binární vyhledávací stromy // 4.5.5 Intervalové stromy // 4.5.6 Optimální intervalové vyhledávání // 5. SYNTÉZA EFEKTIVNÍCH ŘEŠENÍ VYHLEDÁVACÍCH PROBLÉMŮ 112 // Problém třídní příslušnosti // Definice problému 112 // Transformace vyhledávacích problémů na problémy třídní příslušnosti // Problém třídní příslušnosti ve svazech 116 // Svazy s triviálním a totálním uspořádáním 117 // Svazy s částečným uspořádáním // Svazy s přirozeným částečným uspořádáním 119 // Dynamizace řešení vyhledávacích problémů 122 // Dynamizace j22 // Periodická rekonstrukce datových struktur. I23 // Průběžná rekonstrukce datových struktur 125 // Rozložitelné vyhledávací problémy 128 // Dynamizace rozložitelných vyhledávacích problémů 128 // Metoda substruktur stejné velikosti 129 // Logaritmická metoda // Aplikace 133 // LITERATURA 136 // REJSTŘÍK