Pravidla pro vypracování a odevzdání zápočtových programů jsou podobná jako v zimním semestru. Nejprve je potřeba sepsat specifikaci zápočtového programu v minimálním rozsahu zhruba půlka stránky A4.

Samotný zápočtový program musí odpovídat pokroku v programátorských dovednostech, který studenti za dosavadní dobu studia učinili. Jinými slovy, zápočtový program pro letní semestr musí být náročnější než zápočtový program v zimním semestru.

Pochopitelně, zápočtový program musí být opatřen smysluplnou dokumentací, podle které i laik dokáže program ovládat a podle které programátor pochopí, jak program funguje.

Změna nastává ve způsobu odevzdávání, které bude probíhat formou prezentace pro ostatní studenty, kteří se při odevzdávání sejdou. Prezentaci bude předcházet elektronické odevzdání zápočtového programu.

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

Nová 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.

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 energii. 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 chemii). 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 geometrii, č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).

Stará témata pro zápočtové programy

Stará témata pro zápočtové programy vyhlášená v zimním semestru lze nalézt v Poznámkách ke cvičení z 2.12.2005  (pdf formát). Tato témata platí i pro letní semestr s tím, že náročnost programu je nutno odpovídajícím způsobem zvýšit.