Literatura k přednášce Základy algoritmizace


  1. M. Virius: Základy algoritmizace. ČVUT 1995; druhé, přepracované vydání ČVUT 2008.
    Druhé vydání tohoto skripta pokrývá přednášku v potřebném rozsahu.
    První vydání, které je stále v knihovnách a které bylo dostupné i ve formátu PDF, lze použít, ale neobsahuje některé z věcí, které jsou dnes součástí přednášky (úvodní příklad vyšetřování složitosti, algoritmus introspektivního třídění, algoritmus abecedního porovnávání a mnohé další).
    Podrobnější informace o obsahu najdete na stránce věnované mým publikacím -- odkaz je uveden v záhlaví.
  2. Donald E. Knuth: The Art of the Computer Programming. Vol. 1, 2, 3, 4. Addison-Wesley, poprvé vyšlo 1968; Od té doby vychází neustále.
    Ceský překlad: Umění programování. Díly 1 a 2. Computer Press, Brno 2008 a 2010; ISBN 978-251-2025-5 (1. díl) a 978-251-2898-5 (druhý díl)
    Ruský překlad: Искусство программирования, том 1 -- 3, том 4, выпуск 2 -- 4. Вильямс, том 1: 2006, ISBN 0-201-89683-4; том 1 -- MMIX--RISC: 2006, ISBN 0-201-85392-2; том 2: ISBN 0-201-89684-2; том 3: 2007 ISBN 0-201-89685-0;
    Starší ruský překlad: Искусство программирования для ЭВМ. Mир, Mосква 1976 (Iskusstvo programirovanija dlja EVM, Mir, Moskva 1976).
    Naprosto základní publikace v této oblasti.
    1. díl (Basic Algorithms) obsahuje úvod do problematiky algoritmů a jejich analýzy -- shrnuje potřebné matematické znalosti, definuje abstraktní počítač MIX a hovoří o základních datových strukturách.
    2. díl (Seminumerical Algorithms) se zabývá problematikou generování pseudonáhodných čísel, zobrazováním čísel v počítačích, algoritmy pro základní aritmetické operace, důsledky skutečnosti, že reálná čísla jsou zobrazena jen s konečnou přesností atd.
    3. díl (Sorting and Searching) se zabývá algoritmy pro třídění a vyhledávání, hešováním atd.
    4. díl vychází postupně, zatím vyšly tyto svazky:
    0: Introduction to Combinatorial Algorithms and Boolean Functions, (Úvod do kombinatorických algoritmů a logických funkcí, Addison-Wesley Professional, 2008, ISBN 0-321-53496-4),
    1. Bitwise tricks & techniques; Binary Decision Diagrams (Bitové třiky a techniky; Addison-Wesley Professional, březen 2009, ISBN 0-321-58050-8),
    2. Generating all Tuples and Permutations (Generování všech dvojic a permutací, Addison-Wesley, 2005 ISBN 0-201-85393-0),
    3. Generating all Combinations and Partitions (Generování všech kombinací a rozkladů, Addison-Wesley, 2005 ISBN 0-201-85394-9),
    4. Generating all Trees; History of Combinatorial Generation (Generování všech stromů; historie kombinatorického generování, Addison-Wesley, 2006, ISBN 0-321-33570-8).
    Vedle toho je k dispozici samostatně svazek 1 prvního dílu MMIX, a RISC computer for the new Millenium (MMIX, počítač pro nové tisíciletí) s nově navrženým abstraktním počítačem, pro který jsou algoritmy v knize programovány.
    Různá vydání prvních tří dílů se liší ve způsobu výkladu, za čtení ale stojí kterékoli z nich. Jde do daleko větší hloubky, než si můžeme v úvodní úpřednášce dovolit.
    Český překlad je -- alespoň po zběžném pročtení některých částí -- docela dobrý, i když v některých případech nepoužívá vžitou českou terminologii. V každém případě stojí za čtení, a to i přes značnou cenu (990,- Kč/svazek). [srpen 2007, prosinec 2010]
  3. N. Wirth: Algorithms + Data Structures = Programs. Prentice Hall 1975. Slovenský překlad Algoritmy a štruktúry údajov, Alfa 1988.
    Velice dobře napsaná (a dobře přeložená) kniha. Prochází základní datové struktury, metody třídění, rekurzivní algoritmy a dynamické datové struktury. V závěru se zabývá i kompilátory -- tedy definicí struktury jazyka, analýzou věty atd. Některé části přednášky se o ni opírají. Sehnat ji je ale dost obtížné.
  4. P. Topfer: Algoritmy a programovací techniky. Prometheus, Praha 1995.
    Dobře napsaná a poměrně obsažná kniha, ovšem pojetím spíše pro středoškoláky, neboť téměř zcela pomíjí matematickou stránku analýzy algoritmů. Prochází datové struktury, prohledávání do houbky a do šířky, práci s grafy, třídění, zpracování aritmetických výrazů atd. Vzhledem k tomu, že je stále dostupná, ji lze doporučit jako dobré doplňkové čtení.
  5. R. Sedgewick: Algoritmy v C. Části 1--4. Softpress, Praha 2003. ISBN 80-86497-56-9. 690 stran, cena 690 Kč.
    Překlad knihy Algorithms in C (upraveného vydání z r. 1998). Pokrývá analýzu algoritmů, datové struktury, třídění, vyhledávání, a rekurzi. Docela dobře napsaná, ale toporně a nepříliš kvalitně přeložená kniha. (Ta je řečeno jen velice mírně. Například termín "m-ary strom" mne opravdu uzemnil.) Obsahuje velkou řadu příkladů, všechny naprogramované v jazyce C. Je to spíše doplňkové čtení, není určena pro začátečníky.

 

   Ostatní literatura


Moje domovská stránka    Přednášky a semináře