Termíny pro odevzdávání zápočtových programů jsou následující:

Náročnější témata pro zápočtové programy

Sepsal jsem zde různé návrhy na zápočtové programy. Vesměs se jedná o trochu náročnější témata vhodná i pro Ročníkový projekt. Návrhy je třeba brát hlavně jako inspiraci, protože v plné složitosti jsou některé z uvedených problémů velmi náročné. Většina témat vyžaduje návrh netriviálních algoritmů, čímž jsou zajímavá, a nejdená se o čistě technickou implementaci. Navíc témata jsou zde popsána velmi stručně, čehož jsem si vědom a na požádání rád poskytnu bližší popis.

Perspektiva versus Predátor. Chtěli bychom vytvářet neviditelné předměty metodou perspektivního klamu. Je dán předmět poměrně jednoduchého tvaru - například kvádr nebo krychle. Tento předmět je umístěn v nějakém prostředí - v interiéru či v exteriéru. Dále je zadáno pozorovací místo. Vhodným potapetováním fotografickou tapetou lze daný předmět zamaskovat tak, že při pozorování z daného pozorovacího místa bude splývat s pozadím (tj. nepozorný pozorovatel si jej nevšimne). Navrhněte program pro vytváření zneviditelňovacích tapet.

Fotolab KGB. Představme si, že chceme vyfotografovat architektonicky cennou budovu, avšak v záběru se nachází nežádoucí osoba či předmět. V takovém případě by se uplatnil program, který umí z pořízené fotografie nežádoucí osobu nebo předmět odstranit a nahradit jej odpovídajícím pozadím tak, že na výsledné fotografii nejsou patrné žádné úpravy (alespoň ne na první pohled resp. pro neodborníka).

SAT. Je dána Booleovská formule (proměnné mohou mít hodnotu pravda nebo nepravda) v konjunktivním normálním tvaru (konjunkce disjunkcí literálů, kde literál je proměnná či negace proměnné). Pro formule v tomto tvaru se používá ustálený formát souborů s příponou .cnf. Na následujícím odkazu je příklad: logistický problém. Napište řešič, který vezme soubor ve formátu .cnf jako vstup a nalezne splňující ohodnocení v něm obsažené formule nebo prokáže, že formule nemá žádné splňující ohodnocení. Téma je vhodné pro pisatele efektivních programů.

F1 Grand Prix - Optimální zastávky. Představme si, že chceme naplánovat optimální okamžik pro zastávky na výměnu pneumatik a doplnění paliva během závodu F1 GP pro vozy naší stáje. V takové situaci je velmi důležité, aby se náš vůz při návratu na trať nepřipletl za méně výkonné jezdce a vozy, což by nás mohlo stát cenné desetiny sekund. Je známa výkonnost ostatních monopostů účastnících se závodu, rovněž jsou známy určité základní technické charakteristiky monopostů jako je spotřeba paliva, zpomalení způsobené větším množstvím paliva v nádrži atd... Simulujte průběh závodu a na základě této simulace navrhněte optimální zastávkovou strategii pro váš tým.

F1 Grand Prix - Optimální stopa. Jsou dány charakteristiky monopostu F1 do jisté úrovně detailů (rozměry, hmotnost, akcelerace, přilnavost pneumatik, aerodynamický přítlak, výkon brzdového systému, atd...). Dále je zadán okruh s charakteristikami do jisté úrovně detailů (minimálně je znám tvar okruhu a šířka vozovky, detailněji může být znám i výškový profil, kvalita povrchu, atd...). Pro monopost a okruh je cílem nalézt optimální průjezd okruhem, přičemž monopost se musí při tomto průjezdu udržet na trati. Optimalizujeme vzhledem k času na jeden kolo. Intuitivně tedy hledáme stopu, ve které může jet monopost v průměru co nejrychleji.

Cesta pro robota. Hledání cesty pro robota mezi geometricky zadanými překážkami (trojúhelníky, polygony, kruhy, ...) v rovině. Je zadáno počáteční a cílové místo pro robota, rozměry robota (lze i tvar). Cílem je najít cestu z počátečního místa do cílového místa tak, aby přitom robot nenarazil do žádné překážky. Lze dělat i variantu bezpečné cesty, tj. cesty, kdy se robot překážkám vyhýbá v co největší vzdálenosti.

Zahrádka. Je zadána poloha (zeměpisná šířka a délka) a tvar pozemku, na němž se nachází zahrádka. Dále jsou zadány předměty a objekty, které se nachází na a v okolí zahrádky (stromy, budovy, kopce, ...). Úkolem programu je určit (průměrné) osvětlení jednotlivých míst na zahrádce slunečním svitem. Je třeba počítat s tím, že uvedené předměty a objekty vrhají stín. Osvětlení lze počítat v průběhu dne, měsíce, roku. Program může doporučit správný druh rostliny pro určité místo, nebo naopak správné místo pro určitý druh rostliny.

Dopravní simulace. Program na simulaci dopravního systému většího města. Je zadán dopravní systém města (silnice, železnice, metro, ...), dopravní prostředky (autobusy, vlaky, osobní auta, ...) a požadavky na přepravu (někdo chce je tam, někdo jinam, ...). Úkolem programu je odsimulovat tuto situaci, případně odhalit vytvoření dopravní zácpy. Téma lze zajímavě graficky zpracovat, případně pojmout jako hru.

Plánování. Neboli zobecněné varianty hry vlk-koza-zelí. Je dán popis zjednodušeného světa (seznam platných tvrzení - například: koza-vlevo, vlk-vpravo, ...) a pravidla, která svět mění (například: pravidlo prevez-vlka-zleva-doprava, před provedením pravidla musí platit, že vlk je vlevo, po provedení pravidla platí, že vlk je vpravo). Úkolem programu je najít posloupnost pravidel, jejichž aplikací na zadanou počáteční situaci světa (například: vlk, koza, zelí a pastevec vlevo) obdržíme požadovanou cílovou situaci (například: vlk, koza, zelí a pastevec vpravo).

Dáma a šachy. Program, který inteligentně hraje dámu či šachy. Lze udělat jako hru, tj. počítač hraje s uživatelem. Nebo lze udělat vzajemné soupeření dvou různých algoritmů, tj. počítač hraje sám se sebou.

Přepravní firma. Je dána dopravní síť (silnice, města). Přepravní firma má určitý počet vozidel určených pro přepravu zásilek. Pro zadaný seznam požadavků (z města A je třeba něco přepravit do města B) je třeba určit co nejlepší nebo aspoň dobrý rozpis jízd tak, aby byly všechny zásilky doručeny. Jako míru optimality lze vzít v úvahu rychlost doručení, spotřebu paliva, ...

Mezinárodní přístav. Je dán velký mezinárodní přístav (obrovký areál s kotvišti, jeřáby, překladišti, sklady, ...). Program by měl simulovat a automaticky řídit takový přístav - pokud možno s co nejmenší náročností na čas, zdroje a energi. Do přístavu připlouvají lodě, ty je potřeba vyložit/naložit, zboží je třeba uskladnit (je třeba vzít v úvahu prostorové rozložení přístavu, přepravu v rámci přístavu). Do přístavu také přijíždějí vlaky a kamiony se zbožím. Některé lodě jsou velké a mohou kotvit jen někde, zatímco malé lodě mohou kotvit kdekoli. Některé zboží se rychle kazí a má prioritu atd..

Symbolické počítání. Program na symbolické počítání v matematice. Symbolické integrování, derivování, zjednodušování výrazů. Lze rozšířit na symbolické počítání v komplexním oboru.

Středoškolská geometrie. Program na řešení středoškolských geometrických úloh typu narýsujte kružnici, která se dotýká čehosi někde. Vstupem programu jsou podmínky (dotyky, průsečíky, ...), které má rýsovaný útvar splňovat. Výstupem programu je seznam kroků, jejichž provedením lze pomocí pravítka a kružítka narýsovat zadaný geometrický útvar tak, že splňuje vše zadané.

Vzduch, vítr, voda, moře. Program na simulaci kapalin, který by umožňoval zkoumat chování kapaliny v interakci s předmětem do kapaliny vloženým. Lze zkoumat také proudění kapaliny v okolí vloženého předmětu. Program lze pojmout jako pomůcku pro návrhy tvarování povrchu lodí, ponorek, letadel. Jedná se náročné téma vhodné pro "numeriky" (numerická matematika).

ICU - I see you. Řešení viditelnosti. Jsou zadány geometrické útvary v prostoru (kvádr, krychle, koule, obecný polyedr, ...). Program by měl umět pokud možno efektivně určit viditelnost daných geometrických útvarů ze zadaného místa. Neviditelné hrany by program měl zobrazovat třeba čárkovaně. Jedná se o jednodušší téma.

Skládání puzzle. Je dáno rozebrané puzzle. Tedy seznam dílů - vzájemně různé polygony. Program by měl umět díly poskládat do zadané obdélníkové oblasti. Lze dělat i prostorovou verzi, jednotlivé díly jsou polyedry a skládá se do zadaného kvádru (toto má snad i nějakou aplikaci v chemi). Může být velmi kombinatoricky náročné.

Obrázkový google. Program, který vyhledává podle zadaných obrázků. Uživatel zadá obrázek a program vyhledá stejné nebo podobné obrázky na lokálním disku (obecně na internetu). Lze kombinovat s tím, že uživatel zadá jenom část obrázku (výřez). Poměrně komplikovaná varianta programu by mohla být zaměřena na vyhledávání fotografií osob podle obličejů (užitečné pro tajné služby).

Rozpoznávání písma. Program na rozpoznávání psaného textu. V základní variantě tedy, když je rozpoznáváno tištěné písmo, je program poměrně snadno zvládnutelný. Lze kombinovat s rozpoznáváním textu, který je proložen obrázky. Samostatná varianta je rozpoznávání matematických výrazů, to už je relativně komplikované. Další varianta je rozpoznávaní psaného textu - rukopisu. Asi nejtěžší varianta ja rozpoznávání rukopisu matematických výrazů.

Mapa oblohy. Program, který podle zadané polohy (zeměpisná šířka a délka) a zadaného času zobrazí viditelnou hvězdnou oblohu. V tomto tématu nejde o to, aby program obsahoval databázi všech viditelných hvězd, jde hlavně o geometri, čili stačí, aby program uměl několik málo reprezebtativních souhvězdí. Jedná se o snažší téma.

LCS - Longest Common Subsequence. Nejdelší společný podřetězec. Jsou dány dva řetězce, úkolem je najít nejdelší společný podřetězec, ne nutně souvislý. Například slova "alpha" a "aleph" mají jako svůj nejdelší společný podřetězec slovo "alph" (z prvního slova vypustíme 'a' na konci, v druhém slově vypustíme 'e' uprostřed). Problém je to jednoduchý, ale výpočetně poměrně náročný - zvlášť, když nás zajímá rozdíl mezi dvěma velkými soubory (gigabajty).

Jednodušší témata pro zápočtové programy