Na této stránce budou zveřejňovány informace k zápočtovým programům.
Temíny pro odevzdávání zápočtových programů:
Dva týdny před odevzádním programu: schválení specifikace
Několik témat na 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é. Témata budou postupně doplňována a upřesňována. Doporučuji také nahlédnout do seznamu témat
na bakalářské a diplomové práce
zde.
Mrakodrap až do nebe. Navrhněte software pro určení maximální výšky mrakodrapu, který lze postavit s použitím
současných stavebních a (hlavně) výtahových technologií. Vhodným přístupem k řešení by mohla být například simulace
provozu mrakodrapu (pohyb lidí v rámci budovy), přičemž nedostatečná průchodnost budovy by indikovala dosažení limitní
výšky. Toto téma má nejrůznější modifikace - lze se zabývat návrhem výtahové soustavy, dá se experimentovat s tvarem
budovy (směrem k vrcholu se budova zužuje), lze uvažovat o různém způsobu využívání jednotlivých částí mrakodrapu atd...
Pro inspiraci: Frank Lloyd Wright v roce 1956 navrhl mrakodrap vysoký 1600m (Mile High Illinois).
Vševysvětlující teorie. Celulární automat je formální systém, který v jedné ze svých variant vypadá jako čtvercová
síť nekonečné velikosti, kde každá buňka této sítě se nachází buď ve stavu rozsvíceno nebo ve stavu zhasnuto (formálněji tedy
buď ve stavu 1 nebo ve stavu 0). Každé buňce sítě je přiřazena přachodová funkce (všem buňkám stejná), která prvku kartézského součinu
možných stavů buněk z jistého nevelkého okolí dané buňky přiřazuje stav. Celý automat funguje tak, že se v každém kroku změní synchronně
stavy všech buněk podle přechodové funkce (tj. všechny buňky se mění najednou). Někteří lidé si myslí, že by se dal sestrojit
celulární automat, který simuluje veškeré fyzikální zákony, či, že by pomocí celulárního automatu bylo možné simulovat celý vesmír
(pak by ovšem bylo možné říct, že vesmír je celulární automat). Tak daleko my nepůjdeme. Spokojíme se návrhem celulárního automatu, který
simuluje počítač nebo alespoň některé počítačové součástky (paměť, řídící jednotka, hodně zde záleží na interpretaci pojmů).
Téma je vhodné pro "experimentátory".
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).