Radek Pelánek

Jak se dostat přes řeku v malé loďce a k čemu se u toho hodí počítač? Jaký je rozdíl mezi tím, jak řeší logickou úlohu matematik a informatik? Jak zjišťují logici barvu svého klobouku? Co má společného Sudoku a skládání obrazců z pentomin? Proč se pirátům hodí při dělbě pokladu matematická indukce? Jak chytrý musí být programátor, aby prohrál piškvorky proti svému algoritmu?

Lidé od pradávna rádi řeší hlavolamy, logické úlohy a hry. Tyto příklady jsou však nejenom zábavné, ale také často ilustrují pojmy a metody, které tvoří základ matematiky a informatiky. Tato kniha využívá logické úlohy jako prostředek k poutavé a zábavné ilustraci informatického stylu myšlení a ukazuje, že informatika rozhodně není jen o nejnovějším technickém vybavení a ovládání programů.

Kniha je rozdělena do tématických kapitol, z nichž každá obsahuje:

• zajímavé příklady různé obtížnosti,
• rozhovor, ve kterém jsou intuitivně osvětleny nejdůležitější myšlenky a pojmy,
• náměty na programátorské projekty včetně stručného popisu možného řešení,
• komentáře k příkladům, ve kterých naznačena řešení příkladů.

</ul>

Kniha obsahuje celkem více než 90 příkladů a 11 námětů na programátorské projekty, které mají v příloze (zde) dostupné ukázkové řešení.

Obsah knihy

• Úvod
• Jak uvažovat logicky?
• Jak kódovat informace?
• Jak najít správnou cestu?
• Jak splnit všechny podmínky?
• Jak problém zjednodušit?
• Jak vyhrát?
• Jak dostat správný nápad?

Materiály k programátorským projektům

Popis projektů je uveden v knize, bez komentářů obsažených v knize nemusí tyto materiály dávat zcela smysl. Stručný komentář k zadání je nicméně uveden i na začátku zdrojového kódu.

Poznámka: Tyto zdrojové kódy slouží pouze jako ukázka možného řešení, nikoliv jako “vzorové” řešení. Často je řešení záměrně pouze jednoduché a základní a čtenář by se měl pokusit udělat řešení lepší.

Poctivci a padouši

• poctivci.cc

Sebereferenční test

• sebereferencni-test.cc

Šifry

• sifry.cc
• Šifrátor – příklad rozsáhlejší realizace tohoto projektu

Polyomina

• polysolver.cc
• popis dílků (tetronima), příklad vstupního problému

Sudoku

• sudoku.cc
• sudoku-zadani.txt - 1326 zadání
• sudoku-reseni.txt - řešení předchozích úloh

Sokoban

• sokoban.cc
• Popis standardního vstupního formátu
• Velká sbírka zadání
• Výběr některých malých zadání

Hanojské věže

• hanoi.cc

Triomina

• triomino.cc

Hra Nim

• nim-zakladni.cc
• nim-hromadkovy.cc

Zajíc a psi

• zajic-psi.cc

Piškvorky

Programy předpokládají, že se hraje na plánu 20x20 polí. Způsob sehrání zápasu je “přes příkazovou řádku” a je realizován velmi hrubým způsobem (žádné bezpečnostní kontroly apd.), slouží pouze pro základní ilustraci toho, jak lze zápas mezi dvěmi programy realizovat.

• Algoritmy, které vždy načtou aktuální hrací plán a provedou jeden tah:
  • piskvorky-vzory.cc – jednoduché vyhledávání vzorů
  • piskvorky-ab.cc – alfa-beta algoritmus (rozšíření minimax algoritmu), základní neoptimalizovaná realizace
• Pomocné programy a soubory pro sehrání zápasu:
  • piskvorky-rozhodci.cc – rozhodne, zda již někdo vyhrál
  • sehraj-zapas.pl – skript (v jazyce Perl), který bere jako své dva argumenty jména programů, které mají proti sobě hrát
  • prázdný plán (skript sehraj-zapas.pl jej vyžaduje)

Doplnění k vybraným úlohám

Doplňují poznámky a odkazy k některým úlohám:

• Příklad 6. Tři ostrované: řešení v angličtině na Wikipedii
• Příklad 34. Žárliví muži: Pro 3 páry je úloha řešitelná (podobným stylem jako Misionáři a kanibalové), pro 4 páry úloha nemá řešení, je však řešitelná ve variantě “ostrov uprostřed řeky”.
• Příklad 35. Velká výprava: Přehrávač hry (s návodem v čínštině). Řešení (této i jiných převážecích úloh) lze nalézt například zde.
• Příklad 57. Zebra: Vodu pije Nor, Zebru vlastní Japonec. Rozbor řešení (v angličtině)
• Příklad 69, Hlasující piráti: Detailnějí rozbor této úlohy včetně popisu řešení varianty pro více jak 200 pirátů lze najít v článku A Puzzle for Pirates (Ian Stewart)