Literatura k přednášce Základy algoritmizace
-
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í.
-
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]
-
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é.
-
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í.
-
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