Termíny pro odevzdávání zápočtových programů jsou následující (letní semestr 2006/2007):

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

Zde uvedená témata jsou téměř stejná, jako minulý semestr a minulý akademický rok s několika drobnými doplňky. 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.

Vědecká knihovnička. Představte si, že máte na pevném disku svého počítače tisíce vědeckých článků ve formátu .ps (PostScript) nebo .pdf. Řekněme, že články jsou více či méně logicky upořádány do nějaké adresářové struktury. Každý článek má název, autora či více autorů, abstrakt a literaturu (ještě by se našlo pář dalších věcí, ale ty už nejsou tak podstatné). Bohužel je pravidlem, že soubory s články, které se dají sehnat na internetu nebo někde jinde, jsou pojmenovány dosti nesmyslně. Takže z názvu souboru se zpravidla nedá poznat, co se v něm skrývá. Bylo by velmi zajímavé udělat program, který by automaticky evidoval vědecké články na disku. Takový program by měl umět v souboru s článkem rozpoznat název, autora, atd. a toto všechno zařadit do své databáze. Potom by bylo možné například vyhledat na disku všechny články od jistého autora. Nebo všechny články, kde se v abstraktu vyskytuje jisté klíčové slovo. Dalšími zajímavými funkcemi by mohlo být vyhledání citovaných článků nebo zobrazení grafu citací.
Poznámka: Jedná se o technicky velmi náročné téma vhodné na Ročníkový projekt (vydalo by to i na diplomovou práci implementačního typu). Původně jsem chtěl tento program napsat sám, ale bohužel na to nemám čas. Snad se najde někdo, kdo to pro mne napíše.

Vodovody. Základní úlohou tohoto typu je hledání největšího možného průtoku vody jistou vodovodní sítí. Vodovodní síť je vlastně orientovaný graf, kde hrany (trubky) mají přiřazeno reálné číslo určující maximální průtok vody hranou. Zajímavým rozšířením je možnost přidat vrcholy, kterými do vodovodní sítě přitéká další voda v závislosti na průtoku daným vrcholem (multiplikativní vrcholy - do vrcholu přiteče j jednotek vody, ale vytéká z něj c*j jednotek vody, kde c je reálné číslo).

Odstaňování nežádoucích osob (a předmětů). Ostraňování předmětů a osob z digitálních fotografií tak, aby to nebylo poznat. Představte si, že chcete pořídit digitální snímek jisté architektonicky cenné budovy, ale ve vybraném úhlu pohledu je například zaparkovaný automobil. Program, který by uměl z pořízeného snímku zmíněný automobil ostranit, by mohl danou situaci vyřešit (totéž lze vztáhnout i na osoby). Lze využít kombinace více digitálních snímků z různých pohledů k rekonstrukci. Rozšířením tématu může být odstaňování nežádoucích předmětů z filmů - tj. z posloupnosti na sebe navazujících snímků (chyby ve filmech, zejména se to týká kombinace historický film a moderní předměty).

Celulární automaty a vyčíslitelnost. Cílem je prozkoumat možnosti modelování výpočetních procesů pomocí celulárních automatů (zjednodušeně řečeno - pomocí hry LIFE). Ideálně by bylo zajímavé namodelovat pomocí celulárního automatu funkční počítač stejné výpočetní síly, jakou má programovací jazyk Pascal.

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).