P2M: Zápočtové programy

Na získání zápočtu potřebujete také naprogramovat a odevzdat zápočtový program. Co to obnáší?

• Vybrat si téma. Může být libovolné přiměřeně obtížné. Nejlepší by bylo, kdyby to byl program, který bude vám samotným nebo někomu z vašeho okolí užitečný. Pokud vás zatím múza nepolíbila, můžete se podívat na náš seznam témat (to je zatím verze z informatických cvičení, brzy doplním i nějaká jednodušší témata).
• Poslat specifikaci do 30. dubna. Pod tímto honosným názvem se skrývá stručný popis toho, co by váš program měl umět. Já ji pak potvrdím (nebo vrátím k přepracování, pokud je například téma příliš snadné nebo příliš podobné tématu někoho z vašich kolegů).
• Napsat program. V našem případě by měl být v Pythonu. Můžete používat cizí knihovny, ale mělo by být jasné, co jste napsali vy a co je dílo někoho jiného. Samozřejmě není v pořádku, abyste na cizí knihovně ponechali většinu práce – hlavní části programu musí být vaše.
• Napsat uživatelskou dokumentaci. To je stručný popis toho, jak se program používá (tedy třeba v jakém formátu se mu zadává vstup a v jakém vydá výstup). Nepište od ní evidentní věci, spíš to, co by bězný uživatel nečekal. Také by tam mělo být řečeno, co vlastně program dělá :)
• Napsat programátorskou dokumentaci. V ní je stručně popsáno, jak program funguje uvnitř. Nemusíte komentovat každý řádek programu, spíš popište celkovou koncepci. Pokud používáte nějaké netriviální algoritmy, je to dobré zmínit. Pokud používáte něco, co jste nevymysleli sami, je na místě citovat zdroje.
• Vše odevzdat. Obvykle stačí e-mailem (dokumentaci jako obyčejný text nebo PDF, nespoléhejte prosím na to, že váš cvičící rozumí formátům všech wordů světa). Pokud je souborů více, doporučuji je předem zabalit ZIPem nebo TARem (RAR prosím ne). Termín odevzdání není pevně určen, ale potřebujete získat zápočet do kontroly studijních povinností, která obvykle bývá koncem září.
• Předvést. Kdyby program měl nějaké exotické požadavky (třeba vyžadoval terabyte paměti, nebo běžel jenom na vašich programovatelných hodinkách s vodotryskem), budu ho po vás chtít předvést. Jinak si ho vyzkouším sám.
• Iterovat. Ne vždy se vše povede napoprvé. Většinou zafunguje starý známý „generálský efekt“: ať už věc funguje sebelépe, v okamžiku, kdy ji někomu předvádíte, selže nějakým těžko uvěřitelným, nicméně fatálním způsobem. Proto je možné, že budu zápočťák reklamovat a chtít po vás, abyste ho opravili. Nechte si proto prosím nějakou časovou rezervu (obvykle stačí týden).

Náměty

• Matice – knihovna maticových operací: sčítání, násobení, inverze, determinanty, řešení soustav lineárních rovnic apod.
• Stromy – implementace binárních vyhledávacích stromů s operacemi: vkládání, mazání, hledání konkrétní hodnoty, minimum, maximum, předchůdce, následník. (Může být zajímavé naučit se nějakou metodu vyvažování, třeba AVL stromy nebo Splay stromy. Ale na zápočťák stačí i nevyvažovaná verze.)
• Sudoku – program na řešení sudoku; případně je může i generovat a odhadovat obtížnost.
• Skoky po šachovnici – program dostane popis šachové figurky (jak může figurka táhnout) a vymyslí, jak touto figurkou proskákat celou šachovnici tak, abychom každé políčko navštívili právě jednou.
• Polymino – pentomino je tvořeno obrazci složenými z pěti jednotkových čtverečků, které sice nemusí být konvexní, ale musí být souvislé (tj. nemohou obsahovat díry). Napište program, který nalezne všechny obrazce skládající se z n čtverečků. Obrazce lišící se pouze otočením nebo zrcadlením se za různé nepovažují.
• Hvězdná mapa – v souboru jsou uloženy polohy hvězd na nebeské sféře (v rovníkových souřadnicích), program dostane zadané místo na Zemi, datum a čas a zobrazí oblohu tak, jak je v daný okamžik vidět.
• Čtyři čtyřky – pro všechna přirozená čisla od 0 do N zjistí, jak je zapsat za pomoci čtyř čtyřek (respektive jiného počtu jiných číslic dle zadání uživatele) a běžných aritmetických operací. Nápověda: zkuste použít dynamické programování.
• Kalkulačka – vyhodnocování aritmetických výrazů s prioritami operátorů a závorkami. Můžete rozšířit třeba o počítání s komplexními čísly, kvaterniony nebo maticemi.
• Kostkové vzorce – v mnoha hrách na hrdiny se objevují vzorce typu XdY. To znamená „Vezmi kostku o Y stěnách, X-krát s ní hoď a výsledek sečti.“ Jednoduchý vzorec stylu 2d4, 3d6+1, 2d10+1d20-5 se ještě dá pochopit a odhadnout, ale jak se chová vzorec (2d3-2)d(3d2), to už se určuje opravdu těžko. Napište program, který na vstupu přečte takovýto vzorec (s operátory +-,*,d v tomto pořadí priorit vzestupně, pro machry i dělení) a vypíše pro každý možný výsledek pravděpodobnost, s jakou nastane.
• Rozpoznání jazyka – vymyslete statistický model, který umí o daném textu rozhodnout, ve jazyce (řekněme z pěti známých) je napsaný.
• Kontrola pravopisu – dostane text a slovník, zkontroluje, zda se všechna slova v textu nachází ve slovníku, a kde nikoliv, pokusí se napovědět nejpodobnější slovo.
• Piškvorky – nějaká desková hra, která se hraje proti počítači. Kromě jednoduchých pravidel můžete zkusit rekurzivní prohledávání stavového prostoru hry.
• Logik – hra parametrizována dvěma čísly: počtem pozic N (typicky 5) a počtem barev M (typicky 8). První hráč na počátku zvolí nějakou N-prvkovou kombinaci daných barev (mohou se i opakovat), druhý se ji snaží uhodnout. V každém tahu druhý hráč navrhne nějakou kombinaci barev a první mu na ni odpoví dvěma čísly: počet správně uhodnutých pozic a počet barev, které sice v utajované kombinaci jsou, ale na jiném místě (tedy například je-li tajná kombinace 12321 a druhý hráč hádá 14212, je odpověď 1/3). Od programu se očekává, že pro typické zadání bude schopen do deseti tahů a jedné minuty problém vyřešit.
• Šachové úlohy – řešení úloh typu „bílý táhne a dá třetím tahem mat“.
• Kytarové akordy – pro akord zadaný jménem vymyslí, ze kterých tónů se skládá a nalezne všechny rozumné možnosti, jak jej na kytaru zahrát.