Řešení problémů a (jiné) hry

Řešení problému, hry, ještě před tím, než se člověk naučí všechnu tu matematiku, všechny ty programovací jazyky, gramatiky atp. Co je to za blbost? Není to blbost. Jen uvažme, mnohé problémy musíme řešit, mnohá rozhodnutí musíme v životě udělat bez toho, abychom dopodrobna znali veškerou nutnou znalost. Na druhou stranu, mnohé problémy, jejichž řešení je selským rozumem těžko k nalezení, lze překvapivě elegantně vyřešit, pokud nějakou tu matematiku či teorii známe.

Je to svého druhu slepice-vejce problém. Jak nastudovat těžkou teorii bez toho, abychom znuděním či vyčerpáním ztratili souvislosti? Zkušenost také říká, že cennější odpovědi jsou na ty otázky, které jsme sami položili, než na otázky, které za nás položil někdo jiný. A umění položit správnou otázku je mnohdy tím klíčem k nalezení řešení.

Předmět Řešení problémů a hry si mimo jiné klade za cíl zmenšit mezeru mezi teorií a praktickými problémy. Chceme se poprat s problémy, u kterých naše současné znalosti nestačí pro nalezení optimálního řešení. Měly by v nás vzbudit potřebu klást otázky a systematicky na ně hledat odpovědi.

Začneme s Vězňovým dilematem. Jednoduchá formulace základní úlohy vede na velké množství variant a překvapivě mnoho reálných problémů lze na tuto úlohu převést. Představme si trochu komplikovanější situaci. Na ostrově sídlí farmáři, každý z nich vlastní půdu o určité rozloze. Část půdy je společná. Pokud se farmářova kráva pase na společné půdě, šetří svoji. Pokud takto činí nadkritické množství farmářů, společná půda se vyčerpá a nebude k užitku nikomu. Naopak, pokud budou farmáři využívat společnou půdu rozumným způsobem společný zisk celého ostrova bude větší, mohou si dovolit mít více krav než by dovoloval součet soukromě vlastněné půdy. Jak bude takové společenství fungovat? Každý naprogramuje svého hráče a všichni budou hrát proti sobě a uvidíme, který herní algoritmus získá nejvíce.

Představme si robota v komplikované budově, jeho cílem je dostat se ven. Má senzory, které dovedou detekovat překážku. Jakým způsobem by se měl robot pohybovat, aby se nakonec z budovy-bludiště dostal? Co v případě, že má k dispozici plánek budovy? Jak naplánuje nejkratší cestu? Stejný problém řeší i nám dobře známé navigace.

Spam známe všichni, málokdo ho má rád. Jak oddělíme spam od normálního emailu? Některá slova, či slovní uskupení se ve spamu vyskytují častěji než v normálních emailech. Jak toto intuitivní cítění převést do strohé řeči deterministického (pro daný vstup vždy rozhodne stejně) algoritmu?

Jak zformulovat problém? Jaké jsou vstupy? Jaký je očekávaný výstup? Vede navržený algoritmus vždy k žádanému cíli? Jak řešení vyzkoušet a ohodnotit? Je navržený algoritmus optimální? Lze navrhnout lepší? Má problém vůbec nějaké řešení? ... Mnoho otázek, ale nemusíme se bát. Nechceme na ně najít odpověď hned, rozuměj v tomto předmětu. Naopak, chceme co nejvíce otázek otevřít a pak na ně hledat společně odpovědi během studia. Předmět Řešení problémů a hry má také být jistým vyvážením náročného začátku vysokoškolského studia, ukázat ho z té hravější stránky. Několik přednášek přednesou špičkoví informatici na téma jaké mají problémy a jak je řeší. Ani z toho pochopitelně zkoušet nebudeme ;-)