Zápočtový program - Programování II.
Nápady ze stránek Mgr. Martina Mareše, Ph.D.
Nápady ze stránek Martina Mareše. Pro zimní semestr by měla být obtížnost alespoň 4, pro letní alespoň 5. Určitě je ale potřeba dané téma se mnou zkonzultovat,
protože některé jsou příliš ohrané, některé zase nejsou pro Pascal ideální.
Project Euler
Project Euler: různé matematicko-logické problémy. Pro zápočtový program by bylo vhodné vybrat si cca 10 problémů různé obtížnosti
(v letním semestru o něco vyšší) a vytvořit program, který je řeší. Důraz by měl být kladen na:
- Nízkou časovou a paměťovou složitost řešení.
- Vhodnou strukturu celého programu - tak, aby bylo snadné případné přidání dalších problémů, aby byla struktura přehledná a logická.
- Pokud by řešení některých problémů v něčem překrývaly (např. obě budou zkoumat prvočíselnost), daný kód by tam měl být pouze jednou - např. v nějaké pomocné unitě.
- Je-li program na stránkách zadán pro konkrétní hodnoty (např. What is the sum of the digits of the number 21000?), vaše řešení by mělo být obecné
a danou hodnotu by mělo očekávat na vstupu. Nicméně je dost možné, že budete muset určit omezení pro tuto hodnotu (např. že nesmí přesáhnout 10000). To je v pořádku,
ale tato omezení předem dobře promyslete (Jsou nutná? Víte jistě, že pro ně bude program fungovat a nebude např. padat?), přehledně dejte vědět uživatli a zdůvodněte
v dokumentaci.
Srovnávací zápočťáky
Během letního, ale i zimního semestru se učíte mnohé algoritmy a datové struktury, které řeší podobné věci. Často o nich umíte dokázat odhad časové složitosti v nejhorším
(někdy i průměrném případě). Jak to ale dopadne při reálném použití?
Zde je pár nápadů, co byste mohli v rámci svého zápočťáku srovnat. Vždy byste implementovali oba přístupy a pak vygenerovali větší množství +-náhodných dat a změřili,
jak který algoritmus dopadne. Žádný z přístupů zde není příliš složitý, ale o některých se v matematickém prográmku neučí - k těm bych Vám dodala materiály,
nebo nějak poradila.
Nápady do zimního semestru:
- Srovnání rychlosti běhu různých metod na řešení lineárních rovnic (jedna z nich může být Gaussova eliminace).
- Srovnání rychlosti běhu různých algoritmů na třídění čísel.
Klidně můžete přijít s něčím vlastním. ;)
Nápady do letního semestru:
- Srovnání rychlosti běhu Rabin-Karpova algoritmu a algoritmu Aho-Corasickové na nějakých obyčejných datech.
- Srovnání (na různých náhodných grafech) Dijkstrova algoritmu implementovaného pomocí:
- binární haldy
- Fibonacciho haldy
- jiné datové struktury
- Srovnání výkonnosti AVL/červeno-černých stromů a splay stromů na:
- náhodných datech
- "biased" datech - něco trochu vhodnějšího pro splay stromy, než co jsou náhodná data
- Srovnání výkonnosti trie a hashovací tabulky jako implementace asociativního pole (pole indexované řetězci).
Další nápady
- Program na kontrolu a odhalování opsaných zdrojáků. Co přesně by to mělo umět bychom se dohodli, určitě by to mělo zvládat shodnost až na odřádkování,
až na komentáře, až na přejmenování proměnných, až na odsazení atd. (většina těch věcí je jednodušší, než by na první pohled vypadalo).
Toto jsou jen nápady pro inspiraci. Samozřejmě budu ráda, když si vymyslíte vlastní neotřelé téma.
Poměrně oblíbené zápočťáky se týkají implementace nějaké logické hry. To je samozřejmě možné. V takovém zápočťáku je ale dobré se zaměřit především na algoritmickou část,
tzn. typicky umělou inteligenci pro hraní této hry. Zároveň je dobré nad hrou přemýšlet co nejobecněji
(hraje-li se např. na poli o daných malých rozměrech, přemýšlet, zda by Vaše řešení fungovalo i na poli větším apod.).
