.

0 (hodnocen0 x )

(1.5) Půjčeno:3x 

BK

Příručka

Vyd. 1.

Brno : Computer Press, 2004

351 s. : il. ; 23 cm

ISBN 80-251-0343-9 (brož.)

angličtina, polština

Přeloženo z angličtiny a polštiny

Dotisk 2007

Obsahuje bibliografii na s. [345]-346 a rejstřík

000003109

Úvod 11 // KAPITOLA 1 // Než vyrazíme 17 // 1.1. Jak to bývávalo dříve čili výňatky z dějin algoritmických strojů 19 // 1.2. Jak to vše proběhlo aneb kdo // „vymyslel" metodologii programování 21 // 1.3. Proces tvorby koncepce programů 22 // 1.4. Úrovně zobecnění popisu a výběr jazyka 23 // 1.5. Spolehlivost algoritmů 24 // KAPITOLA 2 // Rekurze 27 // 2.1. Definice rekurze 27 // 2.2. Názorný příklad rekurze 28 // 2.3. Jak běží rekurzivní programy? 30 // 2.4. Nebezpečí rekurze 32 // 2.4.1. Fibonacciho posloupnost 32 // 2.4.2. Přetečení zásobníku! 33 // 2.5. Nástrahy pokračují 35 // 2.5.1. Odtud na věčnost 35 // 2.5.2. Definice je správná, jenže ... 36 // 2.6. Typy rekurzivních programů 37 // 2.7. Rekurzivní způsob uvažování 39 // 2.7.1. Příklad 1: Spirála 39 // 2.7.2. Příklad 2: Sudé čtverce 41 // 2.8. Praktické poznámky k technikám rekurze 42 // 2.9. Příklady 43 // 2.9.1. Úloha 2.1. 43 // 2.9.2. Úloha 2.2. 43 // 2.9.3. Úloha 2.3 45 // 2.9.4. Úloha 2.4 45 // 2.9.5. Úloha 2.5 46 // 2.10. Řešení a poznámky k úlohám 46 // 2.10.1. Úloha 2.1 46 // 2.10.2. Úloha 2.2 47 // 2.10.3. Úloha 2.3 47 // 2.10.4. Úloha 2.4 48 // 2.10.5. Úloha 2.5 49 // KAPITOLA 3 // Analýza výkonnosti algoritmů 51 // 3.1. Pro dobrý pocit uživatele programu 52 // 3.2. Příklad 1: Ještě jednou funkce faktoriál 54 // 3.3. Příklad 2: Částečné nulování matice 57 // 3.4. Příklad 3: Jsme v pasti 59 // 3.5. Příklad 4: Různé typy výpočetní náročnosti 61 // 3.6. Nový úkol: zjednodušení výpočtu 63 // 3.7. Analýza rekurzivních programů 63 // 3.7.1. Terminologie 63 // 3.7.2. Vysvětlení metody na příkladu 65 // 3.7.3 Logaritmický rozklad 66 // 3.7.4. Změna definičního oboru rekurzivní rovnice 68 // 3.7.5. Ackermannova funkce aneb něco pro odborníky 69 // 3.8. Úlohy 70 //

3.8.1. Úloha 3.1 70 // 3.8.2. Úloha 3.2 70 // 3.8.3. Úloha 3.3 71 // 3.8.4. Úloha 3.4 71 // 3.9. Výsledky a poznámky k úlohám 71 // 3.9.1. Úloha 3.2 71 // 3.9.2. Úloha 3.4 72 // KAPITOLA 4 // Třídicí algoritmy 73 // 4.1. Třídění přímým vkládáním, algoritmus třídy 0(N2) 74 // 4.2. Bublinkové třídění, algoritmus třídy 0(N2) 76 // 4.3. Quicksort, algoritmus třídy O (N log N) 78 // 4.4. Třídění pomocí haldy 81 // 4.5. Třídění spojováním 85 // 4.6. Praktické poznámky 87 // KAPITOLA 5 // Datové struktury 89 // 5.1. Jednosměrné seznamy 90 // 5.1.1. Použití jednosměrného seznamu 92 // 5.1.2. Vytváření jednosměrného seznamu 94 // 5.1.3. Jednosměrné seznamy - teorie a skutečnost 103 // 5.2. Tabulková implementace seznamu 118 // 5.2.1. Klasické tabulkové uspořádání 118 // 5.2.2. Metoda rovnoběžných polí 120 // 5.2.3. Jiné typy seznamů 122 // 5.3. Zásobník 124 // 5.3.1. Princip funkce zásobníku 124 // 5.4 Fronty FIFO 129 // 5.5. Haldy a prioritní fronty 132 // 5.6. Stromy a jejich reprezentace 139 // 5.6.1. Binární stromy a aritmetické výrazy 142 // 5.7. Univerzální slovníková struktura 147 // 5.8. Množiny 153 // 5.9. Úlohy 156 // 5.9.1. Úloha 5.1 156 // 5.9.2. Úloha 5.2 157 // 5.9.3. Úloha 5.3 157 // 5.10. Řešení úloh 157 // 5.10.1. Úloha 5.1 157 // 5.10.2. Úloha 5.3 158 // KAPITOLA 6 // Odstraňování rekurze a optimalizace algoritmů 159 // 6.1. Jak pracuje kompilátor? 160 // 6.2. Špetka formalismu neuškodí 162 // 6.3. Několik příkladů, jak odstranit rekurze algoritmů 164 // 6.4. Odstraňování rekurze pomocí zásobníku 168 // 6.4.1. Eliminace lokálních proměnných 168 // 6.5. Metoda opačných funkcí 170 // 6.6. Klasická schémata odstraňování rekurze 173 // 6.6.1. Schéma typu while 173 // 6.6.2. Schéma typu if-else 175 //

6.6.3. Schéma s dvojitým rekurzivním voláním 178 // 6.7. Shrnutí 180 // KAPITOLA 7 // Vyhledávací algoritmy 181 // 7.1. Lineární vyhledávání 181 // 7.2. Binární vyhledávání 182 // 7.3. Hešování 183 // 7.3.1. Hledá se funkce H 185 // 7.3.2. Nejznámější funkce H 185 // 7.3.3. Řešení kolizí 188 // 7.3.4. Návrat ke kořenům 188 // 7.3.5. Ještě jednou k polím! 190 // 7.3.6. Lineárni pokusy 191 // 7.3.7. Dvojité hešování 192 // 7.3.8. Uplatnení hešování 194 // 7.3.9. Shrnutí metod hešování 194 // KAPITOLA 8 // Prohledávání textů 195 // 8.1. Algoritmus vyhledávání hrubou silou 195 // 8.2. Nové vyhledávací algoritmy 198 // 8.2.1. Algoritmus KMP 198 // 8.2.2. Algoritmus Boyer-Moore 203 // 8.2.3. Algoritmus Karp-Rabin 205 // KAPITOLA 9 // Pokročilé programovací techniky 209 // 9.1. Programování typu „rozděl a panuj" 210 // 9.1.1. Vyhledávání minima a maxima numerického pole 211 // 9.1.2. Násobení matic o rozměrech NxN 214 // 9.1.3. Násobení celých čísel 217 // 9.1.4. Jiné významné algoritmy typu „rozděl a panuj" 218 // 9.2. „Žravé algoritmy" aneb je čas na malou svačinku ... 218 // 9.2.1. Batohové dilema aneb po svých se těžce pochoduje 219 // 9.3. Dynamické programování 222 // 9.4. Bibliografické poznámky 225 // KAPITOLA 10 // Prvky algoritmiky grafů 227 // 10.1. Definice a základní pojmy 228 // 10.2. Způsoby reprezentace grafů 230 // 10.3. Základní operace s grafy 231 // 10.3.1. Součet grafů 231 // 10.3.2. Kompozice grafů 232 // 10.3.3. Mocnina grafu 232 // 10.4. Roy-Warshallův algoritmus 233 // 10.5. Floydův-Warshallův algoritmus 236 // 10.6. Dijkstrův algoritmus 240 // 10.7. Minimální rozpínavý strom 242 // 10.8. Prohledávání grafů 243 // 10.8.1. Strategie „do hloubky" 243 // 10.8.2. Strategie „na šířku" 245 //

10.9. Problém vhodné volby 247 // 10.10. Shrnutí 252 // KAPITOLA 11 // Číselné algoritmy 253 // 11.1. Hledání míst v nulových funkcích 253 // 11.2. Iterativní výpočty hodnot funkcí 255 // 11.3. Interpolace funkcí Lagrangeovou metodou 256 // 11.4. Derivování funkcí 258 // 11.5. Integrace funkce Simpsonovou metodou 260 // 11.6. Řešení soustavy lineárních rovnic Gaussovou metodou 262 // 11.7. Závěr 265 KAPITOLA 12 // Mohou počítače myslet? 267 // 12.1. Přehled oblastí zájmu umělé inteligence 268 // 12.1.1. Expertní systémy 269 // 12.1.2. Neuronové sítě 271 // 12.2. Reprezentace problémů 273 // 12.2.1. Cvičení 12.1 274 // 12.3. Hry pro dva a stromy her 274 // 12.4. Algoritmus mini-max 276 KAPITOLA 13 // Kódování a komprese dat 283 // 13.1. Kódování dat a aritmetika velkých čísel 285 // 13.1.1. Asymetrické kódování 287 // 13.1.2. Primitivní metody 294 // 13.1.3. Jak prolomit šifru 295 // 13.2. Techniky komprese dat 296 // 13.2.1 Komprese prostřednictvím matematického modelování 297 // 13.2.2. Komprese metodou RLE 299 // 13.2.3. Komprese dat Huffmanovou metodou 300 // 13.2.4. Kódování LZW 306 // 13.2.5. Slovníkové kódování v příkladech 306 // 13.2.6. Popis formátu GIF 309 // KAPITOLA 14 // Různé úlohy 313 // 14.1. Texty úloh 313 // 14.1.1. Úloha 14.1 313 // 14.1.2. Úloha 14.2 314 // 14.1.3. Úloha 14.3 314 // 14.1.4. Úloha 14.4 314 // 14.1.5. Úloha 14.5 314 // 14.1.6. Úloha 14.6 314 // 14.1.7. Úloha 14.7 314 // 14.1.8. Úloha 14.8 314 // 14.1.9. Úloha 14.9 314 // 14.1.10. Úloha 14.10 315 // 14.1.11. Úloha 14.11 315 // 14.1.12. Úloha 14.12 315 // 14.2. Řešení úloh 315 // 14.2.1. Úloha 14.1 315 // 14.2.2. Úloha 14.3 316 // 14.2.3. Úloha 14.4 317 // 14.2.4. Úloha 14.10 317 // 14.2.5. Úloha 14.12 318 // PŘÍLOHA A: Jak se seznámit s jazykem C + + za pět minut 321 //

A.1. Prvky jazyka C++ v příkladech 321 // A.2. První program 321 // A.3. Aritmetické operace 322 // A.3.1. Logické operace 323 // A.3.2. Dynamické proměnné 324 // A.4. Komplexní typy 325 // A.4.1.Pole 325 // A.4.2. Záznamy 325 // A.4.3. Příkaz switch 326 // A.5. Iterace 326 // A.6. Podprogramy 327 // A.6.1. Procedury 327 // A.6.2. Funkce 328 // A.7. Rekurzivní struktury 329 // A.8. Objektové programování v jazyce C + + 330 // A.8.1. Terminologie 330 // A.8.2. Objekty v příkladech 331 // A.8.3. Statické složky tříd 335 // A.8.4. Konečné metody tříd 335 // A.8.5. Dědičné vlastnosti 335 // PŘÍLOHA B Číselné soustavy v kostce 339 // B.l Dvojková číselná soustava 339 // B.2. Osmičková soustava 343 // B.3. Šestnáctková (hexadecimální) soustava 343 // Literatura 345 // Rejstřík 347