Obsah Předmluva Čím se tato kniha liší od jiných příruček? Proč C++? Jak číst tuto knihu? Čím se budeme zabývat? Kapitola 1: Dříve než začneme Kapitola 2: Rekurze Kapitola 3: Analýza složitosti algoritmů Kapitola 4: Třídicí algoritmy Kapitola 5: Datové typy a struktury Kapitola 6: Odstraňování rekurze a optimalizace algoritmů Kapitola 7: Vyhledávací algoritmy Kapitola 8: Prohledávání textů Kapitola 9: Pokročilé programovací techniky Kapitola 10: Prvky algoritmiky grafů Kapitola 11: Numerické algoritmy Kapitola 12: Mohou počítače myslet? Kapitola 13: Kódování a komprese dat Kapitola 14: Různé úlohy Přílohy
Ukázkové programy Typografické konvence a symboly Stručné poděkování Poznámky ke čtvrtému původnímu vydání Zpětná vazba od čtenářů Zdrojové kódy ke knize Errata
11 11 12 12 13 13 13 13 13 13 13 13 14 14 14 14 14 14 14 14
15 15 16 16 17 17 17
KAPITOLA 1
Dříve než začneme Kdysi dávno aneb střípky z historie algoritmických strojů – 1801 – – 1833 – – 1890 – – třicátá léta –
K2114.indd 3
19 20 21 21 22 22
27.1.2015 10:44:24
Obsah
– čtyřicátá léta – – poválečné období – – současnost –
Nedávná historie aneb počátky metodologie programování Proces koncepce programů Úrovně abstrakce popisu a výběr jazyka Správnost algoritmů
22 22 23
23 24 24 26
KAPITOLA 2
Rekurze Definice rekurze Ukázka principu rekurze Jak pracují rekurzivní programy? Rizika rekurze Fibonacciho posloupnost Stack overflow!
Další nástrahy
29 29 30 32 34 34 35
37
Cesta na věčnost Správná definice nestačí
37 37
Typy rekurzivních programů Rekurzivní myšlení
39 40
Příklad 1: Spirála Příklad 2: „Sudé“ čtverce
40 42
Praktické poznámky k rekurzivním technikám Úlohy Řešení a poznámky k úlohám
43 44 47
KAPITOLA 3
Analýza složitosti algoritmů Definice a příklady
52
Funkce faktoriál znovu Nulování části pole Chytáme se do pasti Různé typy výpočetní složitosti
55 59 61 62
Nový úkol: zjednodušení výpočtů Analýza rekurzivních programů
64 64
Terminologie a definice Vysvětlení metody na příkladu Logaritmický rozklad Změna definičního oboru rekurzivní rovnice Ackermannova funkce aneb něco pro labužníky
Výpočetní náročnost není modla Techniky optimalizace programů Úlohy Řešení a poznámky k úlohám
K2114.indd 4
51
64 66 67 68 69
70 71 72 72
27.1.2015 10:44:24
Obsah
KAPITOLA 4
Třídicí algoritmy Třídění přímým vkládáním, algoritmus třídy O(N2) Bublinkové třídění, algoritmus třídy O(N2) Quicksort, algoritmus třídy O(N log N) HeapSort – třídění haldou Slučování setříděných množin Třídění slučováním Vnější třídění Praktické poznámky
75 76 77 79 82 85 86 87 91
KAPITOLA 5
Datové typy a struktury Základní a složené typy Znakové řetězce a texty v jazyce C++ Abstraktní datové struktury Jednosměrné seznamy Implementace seznamů pomocí polí Zásobník Fronty FIFO Haldy a prioritní fronty Stromy a jejich reprezentace Množiny
Úlohy Řešení úloh
93 93 95 96 97 122 127 131 134 140 153
156 156
KAPITOLA 6
Odstraňování rekurze a optimalizace algoritmů
159
Jak funguje kompilátor? Trocha formalizmu neuškodí Několik příkladů odstraňování rekurze v algoritmech Odstraňování rekurze s využitím zásobníku
160 162 163 166
Eliminace lokálních proměnných
Metoda opačných funkcí Klasické postupy odstraňování rekurze Schéma typu while Schéma typu if-else Schéma s dvojitým rekurzivním voláním
Shrnutí
167
169 171 172 173 175
177
KAPITOLA 7
K2114.indd 5
Vyhledávací algoritmy
179
Lineární vyhledávání Binární vyhledávání
179 180
27.1.2015 10:44:24
Obsah
Hešování Hledání funkce H Nejznámější funkce H Řešení kolizí Návrat ke kořenům Návrat k polím Lineární pokusy Dvojité hešování Využití hešování Shrnutí metod hešování
181 182 183 185 186 187 187 189 190 190
KAPITOLA 8
Prohledávání textů Algoritmus vyhledávání hrubou silou Nové vyhledávací algoritmy Algoritmus K-M-P Boyer-Mooreův algoritmus Karp-Rabinův algoritmus
193 193 195 196 200 202
KAPITOLA 9
Pokročilé programovací techniky
205
Programování typu „rozděl a panuj“
206
Vyhledávání minima a maxima v číselném poli Násobení matic s rozměry N×N Násobení celých čísel Jiné známé algoritmy typu „rozděl a panuj“
„Hladové“ algoritmy Problém batohu aneb těžký život pěšího turisty
Dynamické programování Fibonacciho posloupnost Rovnice s více proměnnými Nejdelší společný podřetězec
Jiné programovací techniky Bibliografické poznámky
207 209 212 213
213 214
216 218 218 220
222 225
KAPITOLA 10
Prvky algoritmiky grafů Základní definice a pojmy Cykly v grafech Způsoby reprezentace grafů Reprezentace pomocí pole Slovníky uzlů Seznamy kontra množiny
Základní operace s grafy Součet grafů Kompozice grafů Mocnina grafu
K2114.indd 6
227 228 231 233 233 235 235
236 236 236 237
27.1.2015 10:44:24
Obsah
Roy-Warshallův algoritmus Floyd-Warshallův algoritmus Dijkstrův algoritmus Bellman-Fordův algoritmus Minimální rozpínavý strom Kruskalův algoritmus Primův algoritmus
Prohledávání grafů Strategie „do hloubky“ (sestupné prohledávání) Strategie „do šířky“ Jiné strategie prohledávání
Problém vhodného výběru Shrnutí Úlohy
238 240 243 245 245 246 247
247 248 249 251
252 256 256
KAPITOLA 11
Numerické algoritmy Vyhledávání nulových bodů funkcí Iterativní výpočet hodnot funkce Interpolace funkcí Lagrangeovou metodou Derivování funkcí Integrování funkcí Simpsonovou metodou Řešení soustav lineárních rovnic Gaussovou metodou Závěrečné poznámky
259 259 261 262 263 265 267 269
KAPITOLA 12
Mohou počítače myslet? Přehled oblastí zájmu umělé inteligence Expertní systémy Neuronové sítě
Reprezentace problémů Cvičení 1
Hry pro dvě osoby a stromy her Algoritmus mini-max
271 272 272 274
276 277
277 278
KAPITOLA 13
Kódování a komprese dat Kódování dat a aritmetika velkých čísel Symetrické šifrování Asymetrické šifrování Primitivní metody Luštění šifer
Techniky komprese dat Komprese pomocí matematického modelování Komprese metodou RLE
K2114.indd 7
285 287 287 289 294 296
296 298 299
27.1.2015 10:44:24
Obsah
Komprese dat Huffmanovou metodou Kódování LZW Princip slovníkového kódování na příkladech Popis formátu GIF
299 305 305 308
KAPITOLA 14
Různé úlohy Texty úloh Řešení úloh
311 311 313
PŘÍLOHA A
Seznámení s jazykem C++ Prvky jazyka C++ na příkladech První program Direktiva #include
Podprogramy Procedury Funkce
Aritmetické operace Logické operace Ukazatele a dynamické proměnné
Odkazy Složené typy Pole Záznamy Příkaz switch
Iterace Rekurzivní struktury Parametry programu main() Operace se soubory v jazyce C++ Objektové programování v jazyce C++ Terminologie Objekty na příkladech Statické složky tříd Konečné metody tříd Dědičnost vlastností
Podmíněný kód v jazyce C++
317 317 317 318
318 319 319
320 321 322
323 323 323 324 324
325 326 326 326 327 328 328 331 332 332
335
PŘÍLOHA B
Úvod do číselných soustav Několik definic Dvojková soustava Aritmetické operace s dvojkovými čísly Logické operace s dvojkovými čísly
Osmičková soustava
K2114.indd 8
337 337 337 339 339
341
27.1.2015 10:44:24
Obsah
Šestnáctková soustava Proměnné v paměti počítače Kódování znaků
341 342 343
PŘÍLOHA C
Kompilování ukázkových programů
347
Obsah archivu ZIP ke stažení Bezplatně dostupné kompilátory C++ Kompilace a spouštění
347 347 348
GCC Visual C++ Express Edition Dev C++
Literatura Rejstřík
K2114.indd 9
348 349 353
355 357
27.1.2015 10:44:24
