Sepsal jsem zde různé návrhy původně na Ročníkové projekty, bakalářské a diplomové práce. Většina témat vyžaduje návrh netriviálních algoritmů, čímž jsou zajímavá, a nejdená se o čistě technickou implementaci. Zájemci s bohatou fantazií, chutí definovat a řešit nové úlohy mají dobré předpoklady k úspěšnému rozvoji navrhovaných témat. U náročnějších témat je při dobrém zpracování šance na publikování výsledků. Témata jsou zde popsána velmi stručně, čehož jsem si vědom a na požádání rád poskytnu bližší popis.

Virtual Jaeger Kit. Cílem bude naprogramovat fyzikálně realistický simulátor (obřího humanoidního) robota, kde robot bude sestaven z určitých pohyblivých částí, které budou charakterizovány veličinami popisujícími jejich hmotnost, točivý moment, sílu pohonu atd.. Nadstavbou simulátoru by pak mohl být algoritmus řídící základní pohyb robota (krok, úder s udržením rovnováhy, atd.).

Evacuation. Varianta kooperativního hledání cest (cooperative path-finding nebo multi-agent path-finding), kdy úkolem není dopravit agenty do cílových pozic, nýbrž maximální počet agentů (evakuovaných osob) co nejrychleji dostat z ohrožené oblasti. Lze řešit různé varianty problému: on-line varianta pro předem neznámé počáteční rozmístění agentů v nezmámém prostoru, nebo off-line varianta, kdy evakuovaný prostor je předem známý a stejně tak rozmístění evakuovaných agentů je známé (velmi aktuální téma pro divadla, kina, školy, autobusy, letadla, ...). U on-line varianty potřebujeme rychlý algoritmus, přičemž rychlosti je možno obětovat kvalitu řešení, zatímco u off-line varianty na době běhu algoritmu nezáleží a kritériem je pouze kvalita řešení.

Robot Consumation. Uvážíme-li možnost konzumace robota v úloze, jako je kooperativní hledání cest (cooperative path-finding nebo multi-agent path-finding), vznikne zajímavá situace. Nechť konzumace robota znamená jeho zmizení, jakmile dorazí do cíle; tím se úloha podstatně mění. Prostudovat charakteristiky a řešící algoritmy pro tuto variantu hledání cest by jistě bylo přínosné. Lze uvážit i možnost produkce robota (opak konzumace) - pak se přirozeně nabízí hledat pohyb, který maximalizuje počet robotů dopravených z místa jejich produkce do místa jejich konzumace (praktická motivace: robot = automobil, hledáme kooperativní jízdu maximalizující průjeznost křižovatkou, dopravním uzlem, atd.).

Remotely Controlled Robots. Plánování pohybu robotů na dálkové ovládání, kdy robot je kabelem spojen s řídícím terminálem, představuje zajímavý kombinatorický problém, pokud se chceme vyhnout zamotání kabelů. Navrhněte algoritmy pro hledání cest pro více robotů, případně algoritmy kooperativního plánování složitějších činností více robotů s ohledem na kabelové spojení robotů s řídícím centrem, jejichž křížení a zamotání je nežádoucí (pozn.: kabelové spojení je používáno u podmořských robotů).

Drone Air Superiority. Návrh kooperace letky létajících dronů, která má za úkol zabránit v průniku nepřátelských dronů do chráněného vzdušného prostoru. Téma představuje konkrétní aplikaci a variantu kooperativního hledání cest s protivníkem (Adversarial Cooperative Path Finding - ACPF). Je třeba uvážit manévrovací schopnosti létajících dronů a úroveň jejich umělé inteligence. Téma lze řešit nejprve simulačně či se zaměřit na určité podproblémy (kooperativní pronásledování unikajícího dronu).

Drone Alert! Stále dostupnější létající drony se stále větší nosností a řídícími schopnostmi budou pravděpodobně v blízké budoucnosti znamenat vážné bezpečnostní riziko. Útočník může například využít létajícího dronu k dopravě výbušniny do prostoru, který je pozemní cestou nedostupný, přičemž sám útočník zůstane skrytý. Proti podobným aplikacím létajících dronů zatím neexistuje účinná obrana. V rámci tohoto tématu je úkolem navrhnout systém protivzdušné obrany proti létajícím dronům resp. jeho vybranou komponentu se zaměřením na řídící mechanismy takového systému (software a umělou inteligenci). Zabývat se lze rovněž návrhem stíhacího dronu (jeho řídícího softwaru), jehož úkolem by bylo vyhledávání a ničení nepřátelských dronů.

Adversarial Cooperative Path-Finding (ACPF). V úloze kooperativního hledání cest s protivníkem je třeba dopravit agenty (roboty) do daných cílových pozic navzdory snaze protivníkových agentů (robotů), kteří tento záměr maří. Soupeřící skupiny agentů mohou si mohou vzájemně blokovat cílové pozice nebo si zabraňovat v pohybu. Úlohu lze zkoumat z teoretického hlediska a stejně tak z hlediska řešících algoritmů, které ovládají danou skupinu agentů.

Railroad Planning. Plánování jízdy vlaků do jejich cílových stanic v komplexní železniční síti s mnoha výhybkami může být motivací k zajímavým teoretickým problémům. Mimo jiné se v železniční síti projevuje směrová vlastnost výhybek, tj. výhybka funguje jen při průjezdu jedním směrem, což vede na určitou formu kooperativního hledání cest (cooperative path-finding - CPF, viz. další témata), ovšem nad orientovaným grafem. Orientace grafu, nad nímž se pohyb odehrává, představuje netriviální komplikaci a zároveň příležitost pro výzkum, neboť mnohé existující postupy pro řešení kooperativního hledání cest spoléhají na možnost reverzních pohybů (tj. pohybů v obou směrech).

Dangerous Roads. Nepromyšlené budování pozemních komunikací vytváří pro řidiče motorových vozidel nebezpečná místa. V tuzemnských podmínkách je problém umocněn poruchami chování některých řidičů (typicky agresivní) a někdy až cíleným vytvářením nebezpečných silničních úseků. Navrhněte systém na automatickou detekci nebezpečných silničních úseků či dopravních uzlů, přičemž jako parametry můžeme uvažovat podíl řidičů s poruchou chování (agresivní, sváteční). Jedná se o téma z oblasti simulace s příměsí psychologie chování.

Automated Music Transcription. Cílem by zde bylo vytvořit software s dobrým hudebním sluchem, který dokáže podle poslechu skladby vytvořit její notový zápis. V rámci tématu lze řešit řadu podúloh, jako je například dekompozice akordu podle poslechu atd. Jedná se převážně o výzkumné téma, neboť úloha transkripce není v době navržení tohoto tématu uspokojivě vyřešena.

Sentiment Analysis. Problémem je automaticky klasifikovat názory v krátkých textových vyjádřeních. Klasickou aplikací je analýza diskusních příspěvků k článkům na internetu s tématy, které navozují výraznou společenskou polarizaci (např. volba prezidenta, imigrace, evropská unie, ekologismus, atd...). V základní variantě by se jednalo o dichotomickou klasifikaci vyjádření ve smyslu souhlasu či neshlasu s danou otázkou (např. zda přispivatel podporuje jistého kandidáta). Výsledný softwarový nástroj by mohl najít využití v přípravě volební kampaně či v předpovědi volebního výsledku. Téma lze rozvíjet pro specificky české společenské prostředí, čímž se může odlišit od již dosažených výsledků v anglicky mluvícím prostředí.

Continuous CPF. Kooperativní hledání cest pro mnoho robotů (cooperative paht-finding - CPF) je klasická úloha řešená v umělé inteligenci. Mnoho výsledků existuje pro diskrétní variantu, kde se roboti pohybují v diskrétních krocích po grafu, který modeluje původní prostředí. Zajímavým přístupem by mohlo být řešit úlohu ve spojitém prostoru, kde by se roboti pohybovali spojitě po hladkých křivkách. Tento přístup by byl obzvlášť výhodný pro reálné roboty (kolové, pásové, létající) se specifickými manévrovacími schopnostmi.

Computer Science Department Ranking. Chceme-li posoudit vědeckou kvalitu informatického pracoviště, děláme to zpravidla tak, že si prohlédneme publikace a citovanost všech jeho členů. Tyto informace lze poměrně rutinním způsobem najít v databázích, jako jsou DBLP či Google Scholar. Zmíněná rutinnost hledání údajů vede k myšlence celý proces automatizovat. Představme si software, který po zadání webové stránky zkoumaného pracoviště se seznamem jeho členů odpoví přehledným zhodnocením jeho vědecké výkonnosti. Existence podobného softwaru by umožňovala provádět zajímavá (kontroverzní) srovnání.

Automated Encoding. Řadu kombinatorických úloh lze modelovat a řešit jako úlohu výrokové splnitelnosti (SAT). Zajímavou otázkou je, zda lze tvorbu kódování automatizovat. V jistých případech lze hledání kódování formulovat jako úlohu patříci do třídy Σ₁^P a řešit pomocí řešiče pro QBF (quantified Boolean formula). Otevřenou otázkou je rovněž hledání obecných kódovacích obratů v automaticky vygenerovaném kódování.

Smart Grid. Inteligentní propojovací sítě (smart grid) umožňují propojení míst výroby a spotřeby elektrické energie podle aktuálních potřeb v reálném čase. Problematiku lze zkoumat z hlediska teorie grafů a kombinatorické optimalizace - otázkou může být například, jak rozmístit zdroje výroby elektřiny s co nejmenšími náklady na budování sítí, jak navrhnout topologii sítě s co nejmenšími náklady atd...

Extraktor nápisů. Cílem je navrhnout a implementovat software, který ze vstupní digitální fotografie extrahuje nápisy ve formě znakových řetězců. Možná aplikace je pak v internetovém vyhledávači, který na textový dotaz odpoví pomocí obrázků, které obsahují odpovídající nápis.

Optimalizace CPF. Rychlé algoritmy pro řešení úlohy kooperativního hledání cest (cooperative path-finding - CPF) generují ve většině případů nekvalitní plán. V rámci tohoto tématu bychom se zabývali technikami pro zlepšování sub-optimálních plánů pro CPF. Jak snadno identifikovat nekvalitní podplán a jak za něj najít kvalitnější náhradu? Jedna z možností je úlohu zlepšování podplánu modelovat jako výrokovou splnitelnost (SAT) a hledat tak optimální náhrady.

CPF jako SAT. Cílem by bylo navrhnout nová kódování či vylepšení existujících kódování úlohy kooperativního hledání cest (cooperative path-finding - CPF) jako výrokové splnitelnosti (SAT). Články pojednávající o existujících kódováních lze nalézt v sekci s publikacemi.

iBIBOX. Reimplementace algoritmu BIBOX s vylepšeními pro případy, kdy je graf řídce obsazen agenty. Jedná se téma spadající pod cooperative path-finding (CPF). BIBOX je úplný suboptimální algoritmus řešící úlohu CPF na 2-souvislých grafech v polynomiálním čase. Ovšem předpokládá velkou zaplněnost grafu agenty a v případech, kdy tomu tak není, podává horší výkon (generovaný plán je příliš dlouhý).

Super zoom. Předpokládejme, že máme video záznam vzdáleného statického objektu. Chtěli bychom daný objekt z video záznamu co nejlépe zrekonstruovat, tj. pořídit fotografii v co nejlepší kvalitě. Snímáním objektu po delší časový úsek umožňuje shromáždit více světelné informace, což lze teoreticky dále využít k získání obrazu ve vyšším rozlišení než je rozlišení snímače kamery. Motivace pro tento problém je možnost identifikace diváků na sportovních akcích z televizních záznamů.

Identifikátor umění. Jednalo by se o aplikaci pro chytrý telefon, která by pomocí kamery zabudované v telefonu identifikovala umělecká díla při procházce galerií. Je-li povoleno fotografovat, mohla by aplikace rovněž automaticky přiřazovat popis pořízeným fotografiím (tedy: autor, název, rok vzniku, technika).

Vyhledávání multimediálního obsahu. Navrhněte techniky pro vyhledávání multimediálního obsahu v prostředí internetu. Multimediálním obsahem mohou být fotografie, obrazy, hudba či video. Vyhledávat lze na základě podobností či na základě abstraktních charakteristik. Například vyhledávání uměleckého díla by mohlo proběhnout na základě stručného popisu či náčrtku v editoru - návrh vhodné abstraktní charakterizace je součástí tohoto tématu.

Podmínky kardinality jako SAT. Cílem je navrhnout efektivní reprezentace podmínek kardinality nad bitovými vektory jako výrokové formule. Příkladem podmínky kardinality je požadavek, že daný počet proměnných z jisté množiny proměnných musí nabývat určité hodnoty. Téma lze spojit s modelováním úlohy, jejíž model podmínky kardinality vyžaduje, ve výrokové splnitelnosti.

Aktivní kamufláž (částečně hardwarové téma). Cílem je navrhnout a implementovat techniku "aktivní kamufláže" za pomoci jistého druhu projekce. V podstatě jde o emulaci techniky, která je známá ze sci-fi produkce (kamufláž využívá fiktivní rasa agresivních mimozemšťanů nazývaných Yautja, též známých jako Predátoři). Na základě 3D modelu povrchu kamuflovaného objektu a pozice pozorovatele chceme v reálném čase na povrch kamuflovaného objektu promítat obraz pozadí tak, aby objekt vzhledem k pozorovateli s pozadím splýval. Pro zjednodušení lze předpokládat, že kamuflovaný objekt je statický, pohybuje se pouze pozorovatel. K pokusu lze použít bežný projektor a snímač polohy. V pokročilejší variantě se pohybuje i kamuflovaný objekt. V nejpokročilejší variantě pak navíc kamuflovaný objekt mění tvar - zde patrně již dostupný HW k realizaci nestačí.

Kooperativní plánování. Zde máme na mysli zejména kooperativní plánování cest pro agenty (cooperative path-finding - CPF). Zkoumat lze zobecnění úlohy - například zobecnění cíle, kdy pouze někteří agenti budou mít předepsanou cílovou pozici. Další zobecnění se mohou týkat pohybu agentů - může být požadován pohyb ve formaci. Lze se též vydat cestou překonávání dosavadních možností - pro kolik agentů dokážete vytvářet optimální plány? V roce 2010 to bylo asi 60 agentů v grafu obsahujícím zhruba 800 vrcholů. Speciální témata k CPF budou postupně přidávána výše.

SAT v širším smyslu. Prozkoumejte možnosti aplikace některé ze SAT technik v širším smyslu - například pseudo-Boolean podmínky, MaxSAT, či QBF - pro řešení konkrétní úlohy z rozvrhování, plánování, či optimalizace. Pro vyřešení úlohy pak použijte existující pseudo-Boolean řešič, MaxSAT řešič, či QBF řešič.

Lokální řešící algoritmy. Survey propagation (propagace průzkumů), Warning propagation (propagace výstrah), Belief propagation (propagace přesvědčení). Úkolem je implementovat některou z uvedených řešících technik a prozkoumat její chování na standardní sbírce úloh z knihovny SATLib a/nebo soutěží SAT Competition a SAT Race.

Analýza sociální sítě. Navrhněte metody a algoritmy pro analýzu vztahů v sociální. Na sociální síť lze nahlížet jako na graf, na němž je možné zkoumat základní grafové vlastnosti (stupně vrcholů, velikost klik, průměr, ...). Pokuste se z grafových vlastností odvodit vztahové vlastnosti - např. kdo je oblíbený, kdo je neoblíbený. Pokročileji je možné se zabývat vývojem sociální sítě v čase.

Implementace sociální sítě. Implementujte jednuchou sociální síť formou webového rozhraní. Hlavní funkcí, kterou by sociální síť měla umožňovat, je uzavírání "přátelství" s dalšími uživateli. Lze se také zabývat otázkou, jaké další vztahové operace by síť měla umožňovat, aby se stala uživatelsky atraktivní.

Glass Facade Reflections. Jedná se o grafické téma. Cílem je vypracovat fotorealistický rendering se zaměřením na budovy s převážně skleněnou s fasádou (mrakodrapy). Jako osvětlení se předpokládá ozáření slunečními paprsky s případnými odrazy od fasád. Pokročilejší technikou by mohlo být zapracování efektů na čočce objektivu (lens flare).

Automatický výtvarník. Navrhněte systém, který bude automaticky komponovat (vizálně hezký) obraz. Seznamte se se základními pravidly výtvarné kompozice a zabudujte je do automatického systému. Pro vyřešení případných kombinatorických podúloh lze využít některého z existujících systémů pro řešení SAT či CSP. Použitelnost automatického výtvarného systému se předpokládá zejména v oblasti abstraktní malby (viz. Vasilij Kandinskij).

Automatický hudebník. Navrhněte systém, který bude automaticky skládat (poslouchatelnou) hudbu. Prozkoumejte melodická pravidla a možnosti kompozice melodie. Jako podkladový řešící systém pro kombinatorické zpracování úlohy je možno využít některý z existujících SAT či CSP řešících systémů.

ASP - Answer Set Programming. Zvolenou úlohu modelujte jako ASP instanci a použijte k jejímu řešení nějaký z existujících systémů pro ASP. Téma lze zpracovat též rešeršním způsobem, tedy porovnat možnosti modelování a řešení úloh pomocí ASP s alternativními přístupy, tj. např. s CSP (Problém splňování podmínek - Constraint Satisfaction Problem) či s ILP (Celočíselné programování - Integer Linear Programming).

Optimalizace parametrů (PbO - Programming by Optimization). Mějme jistý řešící systém (např. SAT řešič), který může se zadáním instance problému k řešení obdržet také určité parametry (např. periodu restartu). Naším cílem je najít hodnoty parametrů tak, aby s nimi řešič běžel co nejefektivněji na zvolené podmnožině instancí problému (např. na instancích kódujících plánovací problémy). Chceme tedy obecný řešit pomocí vhodné volby parametrů natrénovat na specifické instance. Téma má různé možnosti rozpracování: lze vzít existující řešič a optimalizovat jeho parametry, lze ale také cíleně navrhovat řešič s mnoha parametry včetně alternativního kódu pro následnou optimalizaci.

Mapa oblohy II. Jaký je pohled na hvězdy a planety z Europy^* či z 51 Pegasi b⁺? Vytvořte program, který takové pohledy zprostředkuje. Program by měl umět zobrazovat známé hvězdy a planety Sluneční soustavy. Dále by měl uživateli umožnit specifikovat nejen místo pozorování, ale také čas, kdy němu dochází.
^*Europa - jeden z mnoha měsíců planety Jupiter. Společně s měsíci Io, Ganymed a Callisto tvoří tzv. Galileovy měsíce, objevené Galileo Galileim v 17. století.
⁺51 Pegasi b - první objevená exoplaneta obíhající běžnou hvězdu. Objev byl uskutečněn v roce 1995.

On-line Article. Navrhněte systém pro vytváření on-line odborných článků v informatice. Odborné články v informatice často ukazují výsledky experimentů pomocí tabulek a grafů, přičemž vstupní data pro tyto tabulky a grafy bývají generována testovaným programem. V případě, že je vytvořena nová verze testovaného programu, článek automaticky zastará. Cílem systému pro on-line články je tento problém překonat automatickou aktualizací tabulek a grafů v článku vždy, když se objeví nová verze testovaného programu. Zároveň by bylo zajímavé umožnit prohlížení minulých verzí článku. Předpokládá se, že článek bude zobrazován jako webová stránka s příslušnými ovládacími prvky.

On-line řešič CSP/SAT/Plan. V rámci toho tématu bychom chtěli vytvořit on-line systém s webovým rozhraním pro řešení problémů SAT, CSP, nebo plánovacích. Cílem zde není vytváření samotného řešiče daného typu problému, nýbrž integrace již existujícího řešiče či více řešičů s webovým rozhraním a běhovým prostředím serveru. Webové rozhraní by sloužilo k interakci s uživatelem a bylo by nejspíše tvořeno webovou stránkou umožňující zadání instance problému a provedení souvisejích nastavení. Běhové prostředí by obstarávalo výběř a spuštění řešiče pro zadanou instanci a přidělení výpočetních zdrojů. Při výběru a spouštění řešiče lze využít poznatků z minulých běhů (např. lze detekovat v minulostí již řešenou instanci).

DPLL/CDCL(CSP). Kombinací řešícího systému pro booleovskou splnitelnost (SAT) - DPLL/CDCL, tedy klasického SAT řešiče řízeného konflikty s učením, a systému pro řešení omezujících podmínek (CSP) bychom mohli získat systém se zajímavými vyjadřovacími schopnostmi. Bylo by možné formulovat zobecněný CSP problém, kde nepožadujeme splnit všechny podmínky, ale nějakou jejich booleovskou kombinaci (např. chceme, aby platily podmínky c1 a c2 nebo podmínky c2 a c3). SAT řešič by se v takovém systému staral o splnění booleovské struktury podmínek a CSP řešič by kontroloval, zda podmínky vybrané SAT řešičem ke splnění lze skutečně splnit.

Ztlumovač reklamy (obrazový). Navrhněte systém, který bude sledovat obrazový signál nějakého média (tedy televize) a bude schopen identifikovat výskyt reklamního spotu a následně provést uživatelem definovanou akci (např. ztlumit zvuk).

Ztlumovač reklamy (zvukový). Úkolem je navrhnout systém, který bude sledovat zvukový signál nějakého média (např. rozhlasu nebo televize) a bude schopen identifikovat výskyt reklamního spotu a následně provést uživatelem definovanou akci (např. ztlumit zvuk).

Obrázkový google II. Cílem je navrhnout program, který bude vyhledávat bitmapové obrázky na základě podobností (prostor, kde bude vyhledávání probíhat, může být lokální disk či internet). Součástí problému je i návrh rozhraní, s jehož pomocí uživatel specifikuje hledaný obrázek.

Obtížné instance SATu. Předmětem zkoumání v rámci tématu jsou postupy na generování formulí, jež jsou obtížné pro moderní systémy pro řešení booleovské splnitelnosti (SAT řešiče). Základní otázkou například může být, jak vypadá formule (tedy instance SATu) s daným počtem výrokových proměnných, pro kterou daný řešící systém běží co nejdelší dobu než rozhodne. Přitom by ze znalosti konstrukce formule mělo být zjistitelné, zda je splnitelná či nikoli, případně jak vypadá splňující ohodnocení proměnných. V rámci tématu lze implementovat příslušný generátor, který bude parametrizován SAT řešičem. Výsledné těžko rozhodnutelné formule mohou rozšířit současné sady testovacích SAT instancí.

Aritmetika v SATu. Aritmetické operace (sčítání, násobení, atd.) a relace (rovnost, větší, atd.) lze zavést nad bitovými vektory. Pravdivost či splnitelnost výroků nad celými čísly obsahující celočíselné aritmetické operace a relace lze pak aproximovat pomocí pravdivosti a splnitelnosti odpovídajících výroků na bitovými vektory (např. můžeme zkoumat pravdivost výroku x + y = y + x nad celými čísly, tuto otázku aproximujeme zkoumáním pravdivosti výroku x_b +_b y_b = y_b +_b x_b nad bitovými vektory, kde x_b a y_b jsou řekněme 8-bitové neznaménkové vektory a +_b je 8-bitové neznaménkové sčítání). Podstatnou výhodou je, že rozhodovací otázky týkající se bitových vektorů lze kódovat jako úlohu booleovské splnitelnosti (SAT), přičemž je pak možné využít řešící systémy pro SAT. Předmětem zkoumání v tomto tématu mohou být způsoby kódování výroků s bitovými vektory vhodné pro moderní řešící systémy pro SAT. Dále je možné vytvářet systém pro automatické kódování výroků s bitovými vektory.

Konkrétní řešící programy. Představme si nějakou relativně obtížnou úlohu (například plánovací problém, CSP instanci, SAT instanci, atp...). Běžný přístup k řešení takové úlohy je napsat program, který načte zadání úlohy a pak úlohu nějakým standardním způsobem řeší (například prohledáváním). Zkusme se zamyslet nad jiným přístupem: uvažujme program, který načte zadání úlohy, ale místo, aby úlohu přímo řešil, sestaví řešící program pro dané konkrétní zadání - konkrétní řešící program. Konkrétní řešící program může být založen na standardním řešícím postupu, jaký by se použil běžně. Dovoluje však jiný programátorský styl - řídící a datové struktury konkrétního programu mohou být velmi specifické a tudíž efektivnější (například větvení programu může být jednodušší, neboť o konkrétním zadání úlohy lze odvodit, že některé případy nikdy nenastanou; místo obecných datových struktur lze používat hashovací tabulky, atd...). Konkrétní řešící program lze dále transformovat směrem k vyšší efektivitě pomocí existujících kompilačních technik a částečného vyhodnocování (například lze vyhodnocovat výrazy pro konkrétní konstanty, lze optimalizovat větvení, lze použít agresivnější vkládání (inlining), atd.). Vzhledem k tomu, že výsledný konkrétní řešící program je na závěr nutno přeložit a pak teprve spustit, přínos uvedené techniky se dá očekávat spíše u obtížných úloh, kde je čas kompilace zanedbatelný vzhledem k času řešení.

Zobecnněná posuvná skládačka (generalized sliding box puzzle). Uvažme zobecnění hry Lloydova patnáctka (viz. následující téma - přečtěte nejdříve, pak pokračujte zde). Hra se bude odehrávat na obdelníkovém hracím poli velikosti n x m, kde n a m jsou přirozená čísla. Na hracím poli budou rovnoběžně s okraji hrací plochy položeny obdélníkové kameny tak, že se vzájemně nepřekrývají a vrcholy (rohy) kamenů budou na celočíselných souřadnicích vzhledem k počátku (levému dolnímu rohu) hracího pole. Délka a šířka hracích kamenů jsou přirozená čísla. Kámen je možno posunout o celočíselnou vzdálenost v horizontální nebo vertikální ose, pokud v tomto posunutí nepřekáží jiný kámen. Úkolem je přeuspořádat kameny z dané počáteční konfigurace do dané cílové konfigurace. Snažme se minimalizovat počet tahů. Řešící systém pro tuto úlohu již existuje (SBPSolver 1.6), překonejte jej ve zvoleném kritériu (čas na řešení, kvalita řešení).

Lloydova patnátcka. Návrh algoritmů pro řešení hry Lloydova patnáctka (shoda jmen u dalšího tématu je čistě náhodná). Jedná se o hru s patnácti očíslovanými kameny na čtvercovém poli 4 x 4 míst, kde jedno místo je volné. Vždy je možné přesunout kámen na sousední volné místo. Cílem je dosáhnout zadané cílové konfigurace kamenů (například po řádcích seřazené od 1 do 15). Navrhněme řešící algoritmus tak, aby se snažil minimalizovat počet kroků nutných k řešení. Zkoumejme obecnejší varianty - větší hrací pole a více volných míst.

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