.

0 (hodnocen0 x )

(3) Půjčeno:3x 

BK

EB

1. vydání

Praha : CZ.NIC, z.s.p.o., 2017

486 stran : ilustrace ; 25 cm

ISBN 978-80-88168-19-5 (brožováno)

ISBN 978-80-88168-20-1 (online ; epub)

CZ.NIC ; 15. publikace

Obsahuje bibliografii na straně 485 a rejstřík

001460119

Obsah // Předmluva vydavatele 7 // Předmluva autorů 11 // Obsah 17 // 1 Příklady na úvod 23 // 1.1 Úsek s největším součtem 23 // 1.2 Binární vyhledávání 26 // 1.3 Euklidův algoritmus 29 // 1.4 Fibonacciho čísla a rychlé umocňování 33 // 2 Časová a prostorová složitost 39 // 2.1 3ak fungují počítače uvnitř 39 // 2.2 Rychlost konkrétního výpočtu 42 // 2.3 Složitost algoritmu 46 // 2.4 Asymptotická notace 50 // 2.5 Výpočetní model RAM 52 // 3 Třídění 61 // 3.1 Základní třídicí algoritmy 61 // 3.2 Třídění sléváním 64 // 3.3 Dolní odhad složitosti třídění 66 // 3.4 Přihrádkové třídění 70 // 3.5 Přehled třídicích algoritmů 76 // 4 Datové struktury 81 // 4.1 Rozhraní datových struktur 81 // 4.2 Haldy 84 // 4.3 Písmenkové stromy 91 // 4.4 Prefixové součty 94 // 4.5 Intervalové stromy 97 // 5 Základní grafové algoritmy 107 // 5.1 Několik grafů úvodem 107 // 5.2 Prohledávání do šířky 110 // 5.3 Reprezentace grafů 112 // 5.4 Komponenty souvislosti 115 // 5.5 Vrstvy a vzdálenosti 116 // 5.6 Prohledávání do hloubky 119 // 5.7 Mosty a artikulace 123 // Obsah // 5.8 Acyklické orientované grafy 127 // 5.9 Silná souvislost a její komponenty 130 // 5.10 Silná souvislost podruhé: Tarjanův algoritmus 134 // 5.11 Další cvičení 137 // 6 Nejkratší cesty 143 // 6.1 Ohodnocené grafy a vzdálenost 143 // 6.2 Dijkstrův algoritmus 146 // 6.3 Relaxační algoritmy 149 // 6.4 Matice vzdáleností a Floydův-Warshallův algoritmus 154 // 6.5 Další cvičení 155 // 7 Minimálni kostry 159 // 7.1 Od městečka ke kostře 159 // 7.2 Jarníkův algoritmus a řezy 160 // 7.3 Borůvkův algoritmus 165 // 7.4 Kruskalův algoritmus a Union-Find 166 // 7.5 Komprese cest 171 // 7.6 Další cvičení 174 // 8 Vyhledávací stromy 177 // 8.1 Binární vyhledávací stromy 177 // 8.2 Hloubkové vyvážení: AVL stromy 183 //

8.3 Více klíčů ve vrcholech: (a.b)-stromy 190 // 8.4 Červeno-černé stromy 198 // 8.5 Další cvičení 207 // 9 Amortizace 211 // 9.1 Nafukovací pole 211 // 9.2 Binární počítadlo 214 // 9.3 Potenciálová metoda 216 // 9.4 Líné vyvažování stromů 220 // 9.5 Splay stromy 222 // 10 Rozděl a panuj 235 // 10.1 Hanojské věže 235 // 10.2 Třídění sléváním - Mergesort 237 // 10.3 Násobení čísel - Karacubův algoritmus 240 // 10.4 Kuchařková věta o složitosti rekurzivních algoritmů 245 // 10.5 Násobení matic - Strassenův algoritmus 247 // 10.6 Hledání k-tého nejmenšího prvku - Quickselect 249 // 18 // — Obsah // 10.7 Ještě jednou třídění-Quicksort 251 // 10.8 k-tý nejmenší prvek v lineárním čase 254 // 10.9 Další cvičení 257 // 11 Randomizace 261 // 11.1 Pravděpodobnostní algoritmy 261 // 11.2 Náhodný výběr pivota 264 // 11.3 Hešování s přihrádkami 268 // 11.4 Hešování s otevřenou adresací 271 // 11.5 Univerzální hešování 273 // 12 Dynamické programování 283 // 12.1 Fibonacciho čísla podruhé 283 // 12.2 Vybrané podposloupnosti 286 // 12.3 Editační vzdálenost 290 // 12.4 Optimální vyhledávací stromy 294 // 13 Vyhledávání v textu 303 // 13.1 Řetězce a abecedy 303 // 13.2 Knuthův-Morrisův-Prattův algoritmus 304 // 13.3 Více řetězců najednou: algoritmus Aho-Corasicková 308 // 13.4 Rabinův-Karpův algoritmus 314 // 13.5 Další cvičení 315 // 14 Toky v sítích 319 // 14.1 Definice toku 319 // 14.2 Fordův-Fulkersonův algoritmus 321 // 14.3 Největší párování v bipartitních grafech 327 // 14.4 Dinicův algoritmus 329 // 14.5 Coldbergův algoritmus 335 // 14.6 Vylepšení Coldbergova algoritmu 342 // 14.7 Další cvičení 344 // 15 Paralelní algoritmy 349 // 15.1 Hradlové sítě 349 // 15.2 Sčítání a násobení binárních čísel 354 // 15.3 Třídicí sítě 360 // 16 Geometrické algoritmy 369 //

16.1 Konvexní obal 369 // 16.2 Průsečíky úseček 373 // 19 // Obsah // 16.3 Voroného diagramy 376 // 16.4 Lokalizace bodu 382 // 16.5 Rychlejší algoritmus na konvexní obal 385 // 16.6 Další cvičení 387 // 17 Fourierova transformace 391 // 17.1 Polynomy a jejich násobení 391 // 17.2 Intermezzo o komplexních číslech 395 // 17.3 Rychlá Fourierova transformace 398 // 17.4 Spektrální rozklad 401 // 17.5 Další varianty FFT 406 // 18 Pokročilé haldy 411 // 18.1 Binomiální haldy 411 // 18.2 Operace s binomiální haldou 414 // 18.3 Líná binomiální halda 419 // 18.4 Fibonacciho haldy 422 // 19 Těžké problémy 431 // 19.1 Problémy a převody 431 // 19.2 Příklady převodů 434 // 19.3 NP-úplné problémy 442 // 19.4 Důkaz Cookovy věty 447 // 19.5 Co si počít s těžkým problémem 449 // 19.6 Aproximační algoritmy 454 // Nápovědy k cvičením 463 // Rejstřík 471 // Literatura 485

(OCoLC)1000492240

cnb002905190