Obsah

Můžete si stáhnout celou knihu ka.pdf a nebo jen jednotlivé kapitoly z obsahu:

  1. Úvod (title.pdf)
  2. Jak porovnávat algoritmy? (jak_porovnavat_algoritmy.pdf)
  3. Časová složitost(cas_sloz.pdf)
  4. Rozděl a panuj (rozdel_a_panuj.pdf)
  5. Jak zrychlovat algoritmy? (jak_zrychlovat.pdf)
  6. Grafy a stromy (grafy_a_stromy.pdf)
  7. Reprezentace grafu (reprezentace_grafu.pdf)
  8. Průchod grafu (pruchod.pdf)
  9. Halda (halda.pdf)
  10. Nejkratší cesta v grafu (min_cesta.pdf)
  11. Union-Find problém (unionfind.pdf)
  12. Minimální kostra (min_kostry.pdf)
  13. Toky v sítích (toky.pdf)
  14. Dodatky (appendix.pdf)

Podrobnější obsah

  • Úvod (title.pdf)

    Pro koho je kniha psána.
    Jakým stylem je psána a proč.
    Které anglické učebnice mě inspirovaly.
    Doporučení jak studovat grafové algoritmy.
    Poděkování.

  • Jak porovnávat algoritmy? (jak_porovnavat_algoritmy.pdf)

    Co jsou to algoritmy a datové struktury.
    Jak je porovnávat (kriteria).

  • Časová složitost (cas_sloz.pdf)

    Teoretické porovnávání algoritmů a pojem časová složitost.
    Zavedení asymtotické časové složitosti a asymtotické notace.
    Časová složitost v nejhorším případě. Příklady výpočtu.
    Časová složitost v průměrném případě.
    Amortizovaná časová složitost a příklady použití.
    Příklady na procvičení.

  • Rozděl a panuj (rozdel_a_panuj.pdf)

    Metoda rozděl a panuj.
    Master theorem, kuchařka na řešení rekurencí.
    Příklady na procvičení.

  • Jak zrychlovat algoritmy? (jak_zrychlovat.pdf)

    Hrajte si s tím. Předpočítání si výsledků do paměti.
    Výpočet hodnoty na základě předchozí hodnoty.
    Přímé generování výsledku.
    Předzpracování dat.
    Odstranění rekurze.
    Odstranění opakujících se výpočtů.
    Optimalizace pro hardware a operační systém.
    Spousta dalších možností.
    Příklady na procvičení.

  • Grafy a stromy (grafy_a_stromy.pdf)

    Zavedení základních pojmů hravým způsobem.
    Stromy a jejich synové, otcové a spol.
    Příklady na procvičení.

  • Reprezentace grafu (reprezentace_grafu.pdf)

    Seznam hran, matice sousednosti, seznam sousedů.
    Výhody a nevýhody jednotlivých reprezentací.
    Příklady na procvičení.

  • Průchod grafu (pruchod.pdf)

    Efektivní průchod grafu.
    Průchod grafu do hloubky.
    Jako jeho aplikace zde máme komponenty souvislosti, komponenty 2-souvislosti.
    Průchod do hloubky v orientovaném grafu a aplikace topologické uspořádání, silně souvislé komponenty, eulerův tah.
    Průchod grafu do šířky.
    Příklady na procvičení.

  • Halda (halda.pdf)

    Zavedení binární haldy a operací na haldě.
    Poznámky o jiných haldách.
    Prioritní fronta.
    Příklady na procvičení.

  • Nejkratší cesta v grafu (min_cesta.pdf)

    Realizace grafu pomocí provázků a kuliček.
    Hledání nejkratší cesty v neohodnoceném grafu.
    Adaptace průchodu do šířky.
    Dijkstrův algoritmus.
    Floyd-Warshallův algoritmus.
    Nejkratší cesta v grafech se záporným ohodnocením hran.
    Bellmann-Fordův algoritmus, detekce záporných cyklů.
    Nejkratší cesta v acyklickém orientovaném grafu (metoda kritické cesty).
    Potenciál a jeho využití.
    Dálniční hierarchie.
    Příklady na procvičení.

  • Union-Find problém (unionfind.pdf)

    Union-Find problém, nebo také dynamické udržování komponent souvislosti.
    Uvedeme si řadu různých řešení (řešení s přepojováním stromečků, řešení s kompresí cestiček).
    Příklady na procvičení.

  • Minimální kostra (min_kostry.pdf)

    Začneme se základním meta-algoritmem a z něj odvodíme ostatní algoritmy.
    Kruskalův hladový algoritmus, Jarníkův (Primův) algoritmus.
    Probereme, kdy je minimální kostra určena jednoznačně a využijeme toho ke zjednodušení následujících algoritmů.
    Borůvkův algoritmus, kontraktivní algoritmus, červeno-modrý meta-algoritmus.
    Podobným, ale složitějším problémem jsou Steinerovy stromy.
    Příklady na procvičení.

  • Toky v sítích (toky.pdf)

    Začneme s teoretickým úvodem do toků v sítích.
    Věta o maximálním toku a minimálním řezu.
    Pak přejdeme k historicky starším algoritmům vylepšující cesty:
    Ford-Fulkerson, Edmons-Karp, Dinic, 3 indové.
    Zakončíme to Golbergovým push-relabel algoritmem.
    Na závěr první části srovnáme použitelnost všech uvedených algoritmů.

    Ve druhé části se podíváme na aplikace toků v sítích:
    maximální párování v grafu, cirkulace s požadavky, cirkulace s limity na průtok hranou, rozvrhování letadel.
    V samém konci kapitoly se zmíníme o multikomoditních tocích.
    Příklady na procvičení.

  • Dodatky (appendix.pdf)

    Dodatky obsahují poznatky o učení, můj proslov ke studentům, můj proslov k učitelům a značení použité v této knize.

Budu Vám vděčný za jakékoliv připomínky, korektury a návrhy. Budu moc rád, pokud vám sepsané texty pomohou.

Prosba

Hledám někoho, kdo by si chtěl některé kapitoly přečíst, opravit v nich chyby, případně navrhnout změny, pokud se mu něco zdá nesrozumitelné. Podle velikosti zásluh slibuji sladkou odměnu. Všem pomocníkům bude v knize poděkováno.

Plánovaná rozšíření

Stále na textu pracuji a snažím se ho vypilovat. Proto budu vděčný, za Vaše připomínky.

Texty už jsou sepsané celkem rozumně, ale ještě je nikdo jiný pořádně nekontroloval. Plánuji přidat ještě párování v grafech, pravděpodobnostní a aproximační algoritmy a rozšířit všechny kapitoly o přehled a souhrn současných poznatků a nejlepších algoritmů na dané problémy. Také bych rád ke každé kapitole přidal další zajímavé příklady.