Témata na Ročníkový projekt - NPRG045

2) Evoluce řídícího programu

Na čtverečkové ploše se pohybují organismy řízené algoritmem v podobě programu zapsaného v jakémsi jednoduchém strojovém kódu. O svých akcích se rozhodují podle obsahu sousedních políček a podle obsahu svých paměťových buněk. Algoritmus představuje genetickou informaci organismu.

Možné akce jsou: otočit doleva, otočit doprava, krok vpřed, nedělat nic. Algoritmus může testovat okolní políčka, testovat obsah proměnných, zapisovat do proměnných a provádět akce. Provedením akce končí činnost algoritmu a jeden krok organismu.

Provedení každé instrukce stojí organismus určité množství energie, pokud nemá dostatek energie, hyne. Model nemusí zahrnovat páření, populace bude průběžně doplňována kopiemi a kříženci organismů s největší energií.

Na čtverečcích roste potrava, pro každý čtvereček s individuální pravděpodobností zadávanou jako mapa úrodnosti.

Cílem práce je naprogramovat prostředí umožňující experimentovat s evolucí těchto organismů a nějak čitelně zobrazovat algoritmy nejúspěšnějších jedinců.

Program by měl dovolit před spuštěním nastavovat úrodnost jednotlivých políček mapy, ale i během evoluce globálně měnit úrodnost všech políček najednou (měnit hodnotu, kterou se násobí úrodnost každého políčka), aby bylo možné během výpočtu měnit množství dostupné potravy.

OS: Windows
Jazyk: Podle volby řešitele.

Tento projekt by mohl přerůst v bakalářskou práci.

3) Digitální evoluce organismu a ekosystému

1) Evoluce využívání paměti

Na čtverečkové ploše se pohybují organismy řízené algoritmem v podobě tabulky. O svých akcích se rozhodují podle obsahu sousedních políček a podle svého vnitřního stavu představujícího paměť, algoritmus i maximální povolený počet stavů budou součástí genetické informace.

Možné akce jsou: otočit doleva, otočit doprava, krok vpřed, nedělat nic; s každou akcí může být svázán přechod do jiného stavu (pokud má organismus více než jeden stav).

Každá akce stojí organismus určité množství energie, pokud nemá dostatek energie, hyne. Populace je průběžně doplňována kopiemi a kříženci organismů s největší energií.

Na čtverečcích roste potrava, pro každý čtvereček s individuální pravděpodobností zadávanou jako mapa úrodnosti.

Cílem práce je naprogramovat prostředí umožňující experimentovat s evolucí těchto organismů, zejména s ohledem na množství využívané paměti (počet povolených stavů). Předpokládá se, že využití paměti by mělo jedince něco stát (ať už paušálně vyšší cenu operací za to, že má větší paměť nebo jen vyšší cenu operací, které mění stav), zajímá nás, při jaké ceně se paměť vyplatí v podobě lepšího algoritmu, vedoucího k lepšímu vyhledávání potravy.

Program by měl dovolit před spuštěním nastavovat úrodnost jednotlivých políček mapy, ale i během evoluce globálně měnit úrodnost všech políček najednou (měnit hodnotu, kterou se násobí úrodnost každého políčka).

OS: Windows
Jazyk: Podle volby řešitele.

2) Evoluce parametrů páření

Na čtverečkové ploše se pohybují organismy řízené algoritmem v podobě tabulky. O svých akcích se rozhodují podle obsahu sousedních políček a podle svého vnitřního stavu představujícího paměť, algoritmus i maximální povolený počet stavů budou součástí genetické informace.

Možné akce jsou: otočit doleva, otočit doprava, krok vpřed, nedělat nic; s každou akcí může být svázán přechod do jiného stavu (pokud má organismus více než jeden stav).

Každá akce stojí organismus určité množství energie, pokud nemá dostatek energie, hyne.

Na čtverečcích roste potrava, pro každý čtvereček s individuální pravděpodobností zadávanou jako mapa úrodnosti.

Organismy se rozmnožují pářením, podmínkou páření je vzájemné splnění podmínek páření. PODMÍNKY PÁŘENÍ každého jedince zahrnují:

• dolní limit energie partnera
  (ti, kdo si neumí najít potravu, se nemohou pářit)
• množství energie předávané narozenému potomkovi
• u jedince VYVOLÁVAJÍCÍho páření: horní limit energie předané partnerovi (kolik je ochoten zaplatit)
• u jedince PŘIJÍMAJÍCÍho páření: požadavek energie požadované po partnerovi (kolik chce dostat)
• jedinec vyvolávající páření vyvolá páření akcí krok vpřed na políčko, kde stojí jedinec přijímající páření, přitom se jeho poloha nezmění, a v případě vzájemného splnění podmínek páření
  • dojde k předání energie od vyvolávajícího k přijímajícímu
  • vyvolávající může příštím tahem pokračovat
  • přijímající K tahů ČEKÁ a potom na náhodně vybraném nejbližším volném políčku vznikne nový jedinec
  • nový jedinec dostane od přijímajícího energii v množství daném parametrem přijímajícího

Při přiblížení organismů se vyhodnotí vzájemné podmínky páření a podle toho se každý organismus ve výhledu jeví jako jedinec VHODNÝ nebo NEVHODNÝ k páření. Jedinec, který ČEKÁ, je NEVHODNÝ k páření.

Cílem práce je naprogramovat prostředí umožňující experimentovat s evolucí těchto organismů, zejména s ohledem na vývoj parametrů páření.

Program by měl dovolit nastavovat úrodnost jednotlivých políček mapy i během evoluce globálně měnit úrodnost všech políček najednou (měnit hodnotu, kterou se násobí úrodnost každého políčka).

Dále by měl program dovolit sledovat statistické údaje jako je věk, počet dětí, cena za páření nebo množství energie předávané potomkům - jako průměrné hodnoty i jako histogramy rozložení jednotlivých hodnot v populaci.

OS: Windows
Jazyk: Podle volby řešitele.

3) Katedrální nástěnka

Cílem je vyvinout Webovou aplikaci, která by mohla sloužit jako nástěnka, s vkládáním příspěvků pomocí mailu.

Požadavky:

• různé, za běhu doplňovatelné, typy příspěvků
  (např. upozornění na seminář, upozornění na přednášku, článek, recenze knihy, řešený problém, nabídka spolupráce...)
  - tj. ukládané uniformním způsobem
• editace příspěvků Webovým rozhraním
• vkládání příspěvků zasláním mailu dané struktury
  (pro každý typ příspěvků různé, autentikace heslem)
  - případné vyrozumění o nesprávnosti a nevložení
• personifikovatelný vzhled stránek složený z oken
  (barva, umístění, velikost, obsah - typ příspěvků, filtr)
  - např. všechny konference s deadline v nejlbližších 30 dnech, všechny příspěvky všech typů vložené za poslední týden atd.
  
• ...a připravené šablony těchto vzhledů
• přibližné vyhledávání
• volitelně mailové upozorňování na vložené příspěvky vyhovující daným filtrům

OS: Podle volby řešitele.
Jazyk: Podle volby řešitele.
DB: Volitelná, minimálně MySQL a PostgreSQL.

1) Nástroj pro generování WWW-PHP-MySQL aplikací

Generované aplikace by měly zvládat zobrazení obsahu tabulky, volitelně s nastavitelným filtrem a tříděním, přidávání nových záznamů, dotazy nad více tabulkami (join), prohlížení a úpravu jednotlivých záznamů i zobrazení seznamů ve vztahu master-detail.

Vytvářené testy by měly být co možno nejvíc odolné vůči změnám GUI, například pomocí pojmenovávání míst a objektův generovaných stránkách, odkazů pomocí struktury stránky (druhé políčko ve formuláři s nadpisem XYZ) atd.

Cílem je vytvořit knihovnu pro symbolické počítání, kterou bude možno volat ze standardního vysokoúrovňového interpretovaného jazyka, nejlépe Pythonu. Knihovna může být psaná v čemkoliv, nejlépe však Python a/nebo C/C++. Jedná se v zásadě o opensource alternativu k Maplu/Mathematice. Prioritou není rychlost počítání, ale aby knihovna byla co nejjednodušší a šla snadno rozšiřovat o další symbolické algoritmy a funkce a aby byla snadno použitelná.

Zakladní prototyp jsem napsal v pythonu:
http://code.google.com/p/sympy/

Sympy umí základní operace se symboly, funkce (sin, cos, ...), derivovat a z pokročilejších věcí limity. Na stránkách projektu najdete podrobnější informace a důvody, proč se vyplatí mít takovouto knihovnu. Tzn., to základní už je hotovo, zbývá dodělat pokročilejší věci: faktorizace polynomů, symbolická integrace, komplexní čísla, řešení rovnic (obyčejných i diferenciálních), asymptotický rozvoj, symbolické matice a tenzory, nekomutativní objekty.

Jako ročníkový projekt je možno se zaměřit na libovolnou z těchto věcí, přičemž nejzajímavější je symbolická integrace. Případnou matematiku vysvětlím, na algoritmy (např. na integraci) mám článek, nebo společně vymyslíme.

Nápady, na co všechno by šlo (nebo už lze) Sympy použít jsou zde:
http://code.google.com/p/sympy/wiki/Motivation

Už teď Sympy občas někdo (z celého světa) použije, a myslím si, že pokud se dodělají výše zmíněné věci, tak to bude skutečně velice užitečná knihovna, kterou bude hodně lidí používat.

1) Interface pro programy v Delphi

Součástí řešení je i návrh způsobu, kterým jiné programy budou s touto knihovnou komunikovat.

Program používající tuto knihovnu bude možné jiným programem ovládat a také číst hodnoty jeho komponent, předpokládané využití je například pro testování nebo možnost "dávkového spouštění" GUI programů.

Výstupem programu by měl být údaj udávající míru podobnosti.

Tato míra by přitom byla vypočítávána nějakým netriviálním skládáním hodnot dílčích měr (odhadovaný počet 10-20), počítajících podobnost co možno nejrůznějšími způsoby.

Kriteriem úspěšnosti programu je schopnost rozpoznat zdrojové texty odvozené jeden od druhého.

Výstupem programu by měl být údaj udávající míru podobnosti.

Tato míra by přitom byla vypočítávána nějakým netriviálním skládáním hodnot dílčích měr (odhadovaný počet 10-20), počítajících podobnost co možno nejrůznějšími způsoby.

Kriteriem úspěšnosti programu je schopnost rozpoznat texty odvozené jeden od druhého.

1) MIDI file

Obsahem projektu je navrhnout a implementovat objektové rozhraní (například jako ActiveX objekt), které umožní přistupovat k obsahu MIDI souboru způsobem odpovídajícím logice dat, tj. krom jiného místo událostí pracovat s notami, adresovat pomocí taktů a dob, pomocí výšek, zjistit, které noty znějí v daném okamžiku a podobně.