Errata v Průvodci labyrintem algoritmů (1. vydání)

Jak praví staré programátorské úsloví, v každém programu je alespoň jedna chyba. U knížky o programování to bohužel přes veškerou péči autorů platí také. Navíc na rozdíl od programů tištěné knížky nejdou tak snadno opravit.

Zde naleznete seznam všech známých chyb (kromě triviálních překlepů) spolu s datem, kdy byly opraveny v elektronické verzi knihy. Děkujeme všem čtenářům, kteří na ně upozornili.

V dotisku z ledna 2018 (viz zadní tiráž) jsou opraveny všechny chyby starší než 2018-02-01.

V dotisku z května 2019 jsou opraveny všechny chyby starší než 2019-05-15.

V dotisku z ledna 2021 jsou opraveny všechny chyby starší než 2021-01-18.

Chyby v druhém vydání najdete na samostatné stránce.

Seznam chyb

• strana 28, algoritmus DvojiceSeSoučtem: ve 3. kroku má být x_i + x_j namísto x_j + x_j. [2017-11-28]
• strana 27, poslední odstavec: zapamatovaná pozice je j, nikoliv t. [2021-06-08]
• strana 29, cvičení 4: první prvek má být +∞, nikoliv -∞. [2021-06-08]
• strana 29, cvičení 9: chybí upozornění, že vstup není v paměti povoleno měnit. [2019-05-06]
• strana 30, důkaz Lemmatu G: v 5. řádku důkazu má být d(x'-y') namísto d(x-y). [2017-11-28]
• strana 32, cvičení 5: gcd(a,b) má být gcd(a,n). [2018-06-05]
• strana 35, cvičení 4: nerovnost má znít F_n+2 ≥ φⁿ. [2017-11-28]
• strana 51, cvičení 2: nerovnost má znít c₁g(n) ≤ f(n) ≤ c₂g(n). [2017-11-28]
• strana 56, přiblížení druhé: opakující se výraz 2^{k log n} má být psán jen jednou. [2018-06-05]
• strana 61, 2. odstavec: S prvky nebudeme provádět nic jiného, než … [2019-05-06]
• strana 61: v úvodu kapitoly o třidění slibujeme, že ukážeme třídící algoritmus, který je současně rychlý, na místě a stabilní. Všechny tři podmínky dohromady splnit neumíme, libovolné dvě ano. [2018-04-13]
• strana 65: vstup a výstup algoritmu MergeSort mají být indexované od 1 do n. [2021-01-18]
• strana 69: v obrázku rozhodovacího stromu jsou některá porovnání špatně. [2020-02-21]
• strana 119, cvičení 7: i náraz do druhého robota se ignoruje. [2019-05-06]
• strana 125: Lemma A má být formulováno jako ekvivalence. [2020-02-21]
• strana 127, cvičení 1: slibujeme, že graf je souvislý. [2019-05-06]
• strana 127, cvičení 3: místo na společné kružnici mají x, y ležet na společném uzavřeném cyklu (uzavřeném cyklu bez opakování hran). [2018-06-05]
• strana 148, znění věty o Dijkstrovu algoritmu s haldou: má být T_d místo T_m. [2017-11-28]
• strana 150, v krocích 7 a 8 algoritmu Relaxace má být l(v,w) místo l(u,v). [2021-06-08]
• strana 181, v definici dokonalé vyváženosti má být R(v) místo P(v). [2021-06-08]
• strana 201: krok 6 algoritmu LlrbInsert má končit „do v uložíme původní r(v)“ [2017-11-28]
• strana 206: v kroku 2 algoritmu LlrbDelete byla opačná nerovnost, správně má být k(v) > x. [2019-11-29]
• strana 213, 3. odstavec důkazu: má být „V posledním bloku se vůbec nerealokuje.“. [2017-11-28]
• strana 230, cvičení 4: Insert je ve vážené verzi Splay stromů potřeba implementovat pomocí rozdělování a spojování stromů – původní verze se nezamortizuje. [2019-05-06]
• strana 243: v kroku 8 algoritmu Násob má být 10^2k místo 10ⁿ (to je rozdíl, je-li n liché). [2021-01-18]
• strana 279, důkaz věty o systému L': dvojice (r,s) neodpovídají (ax mod p, bx mod p), nýbrž ((ax+b) mod p, (ay+b) mod p). [2017-11-29]
• strana 280, cvičení 8: definice systému M' je příliš slabá. Použijte místo ní bity w až w+l-1 hodnoty ax+b pro a,b∈[2^w+l]. [2017-11-28]
• strana 280, cvičení 9: předpoklad slabé c-univerzality systému H nestačí. Dokažte, že ze silně c-univerzálního systému se dá vytvořit slabě 2c-univerzální nebo silně 4c-univerzální. [2017-11-28]
• strana 291: V algoritmu Edit chybí přičtení jedničky v krocích 5 a 6. [2021-01-18]
• strana 296: V algoritmu OptStrom má být v krocích 6 a 7 šipka doleva místo rovnítka. [2021-01-18]
• strana 308, cvičení 5: požadujeme nejdelší vlastní prefix. [2019-05-06]
• strana 312, 1. odstavec: místo slova β hledáme ve slově β. O něco níže: místo hledání všech slov hledáme ve všech slovech. [2019-05-06]
• strana 314: v pseudokódu Rabinova-Karpova algoritmu má být volba P a N provedena dřív, než počítáme heše. [2018-02-04]
• strana 329, důkaz důsledku: síť má m+n hran, nikoliv m+2n. [2021-10-26]
• strany 323, 331, 336: zápis sítě má být (V,E,z,s,c), nikoliv (V,E,c,z,s). [2018-03-02]
• strana 335, cvičení 9, 4. řádek od konce: místo r(w)=0 chceme položit p(w)=0. [2017-11-28]
• strana 337, invariant A: čtvrtá podmínka je příliš slabá, v následujících úvahách potřebujeme f^Δ(v) ≥ 0 pro všechny vrcholy v≠z. Z důkazu nicméně přímo plyne i tato silnější podmínka. [2017-11-28]
• strana 341, důkaz lemmatu N, poslední odstavec: není pravda, že potenciál klesá jen při nenasycených převedeních. Může klesat i jindy, ale důkazu to nijak neubližuje. [2018-03-02]
• strana 357: ve formuli pro dosazení do funkce jsou pomíchané indexy i a j, má být všude i. [2019-05-06]
• strana 370: v komentáři k obrázku 16.2 nemáme odstraňovat dva body, ale tři. [2019-05-06]
• strana 396: na ilustraci goniometrického tvaru komplexního čísla byl prohozený sin a cos. [2018-02-04]
• strana 400, začátek důkazu věty: doplňování nulami je potřeba provést tak, abychom doplnili aspoň n nul a počet koeficientů byl mocninou dvojky. [2018-02-04]
• strana 401: v definici Lemmatu R je vhodné připomenout, že stále indexujeme modulo n, takže y_n=y₀. [2020-02-21]
• strana 404: 2. řádek má znít „každou dostatečně hladkou periodickou funkci …“ [2017-11-28]
• strana 413, 1. odstavec důkazu: v „zavěšeny stromy binomiální stromy“ je první „stromy“ navíc. [2017-11-28]
• strana 414, důsledek po lemmatu D: maximální počet stromů může být o 1 větší. Podobně v cvičení 3 na téže straně. [2017-11-28]
• strana 414, tamtéž: minulá oprava také nebyla správně, je ještě potřeba vyměnit horní celou část za dolní. Má tedy být ⌊log₂ n⌋ + 1. [2019-11-29]