Jak to vyřešit?
 |
Radek Pelánek Portál, 2011 ISBN: 978-80-7367-872-2 160 stran stránky nakladatelství |
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ů.
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í.
Errata
ErrataObsah 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
Sebereferenční test
Šifry
Polyomina
Sudoku
- sudoku.cc
- sudoku-zadani.txt - 1326 zadání
- sudoku-reseni.txt - řešení předchozích úloh
Sokoban
Hanojské věže
Triomina
Hra Nim
Zajíc a psi
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)