Ročníkové projekty (NPRG045)#

Vhodné okruhy témat#

Hodí se projekty co obsahují hodně tvrdé použití C, funkcionální programování, Haskell, SIMD/paralelní/cache-efficient (nebo jinak vysoce výkonné a efektivní) algoritmy, hodně UNIXu, internety/sítě/distribuované věci, kryptografii. Dostatečně akční nebo zajímavé hry jsou vítány (viz. sekce níže). Bioinformatika je OK.

Prakticky každý ročníkový projekt je vhodné rozšířit na bakalářskou práci, oddělené RP a BP jsou spíše výjimka kterou rozhodně nejde doporučit.

Dostatečné rozšíření jakéhokoliv (i vyřešeného) tématu je možné použít i na diplomovou práci.

Jak se pozná bakalářská práce?#

Volně přeloženo: Jak poznat bakaláře z MFF/Informatiky od náhodného člověka, který umí číst, psát, počítat a programovat?

Cílem bakalářské práce je (1.) provést mírnou rešerši současného (nebo nedávného) výzkumu o jednom konkrétním informatickém tématu, (2.) pomocí získaných vědomostí vyřešit nějaký úzce specializovaný a dobře definovaný problém, následně (3.) standardnímí a reprodukovatelnými metodami určit, jak moc dobré je vzniklé řešení, a konečně (4.) celý příběh srozumitelně a přehledně vyjádřit ve zhruba 20- až 60-tistránkové monografii, které se říká bakalářská práce. Bakalář odevzdáním práce prokazuje, že dokáže rozumět výsledkům současného výzkumu, podle nich vědecky řídit a analyzovat svou vlastní práci, a výsledek srozumitelně předat dál.

V rámci ročníkového projektu se většinou připravujete na hlavní část programování na práci, tj. vyzkoušíte si všechny knihovny co budete potřebovat, prozkoumáte cílové prostředí, vyrobíte prototyp, načtete si odbornou literaturu, apod.

Před výběrem tématu ročníkového projektu je vhodné si položit otázky odpovídající bodům 1-4 výše, a pokusit se na ně odpovědět:

Je můj nápad vůbec relevantní? Pro odpověď zamiřte na Google Scholar a zkuste najít nějaký článek (nebo víc článků), které nejsou moc staré (max. cca 15-25 let) nebo viditelně překonané, a týkají se vašeho tématu.
Je problém, který chci řešit, vhodný? Neočekává se od vás vyřešení něčeho naprosto revolučního a nového: metoda, jak váš problém správně vyřešit by už měla být známá a dobře prozkoumaná (nikdo od vás nechce, abyste dělali vědecké objevy!). Vy ji ale např. jen použijete na něco, na co ji ještě nikdo použít nezkusil, nebo mírně modifikujete tak, aby šla použít i na něco zdánlivě nesouvisejícího. Ve zkratce: problém by měl být netriviální, ale měli byste předem vědět, jak ho vyřešíte.
Je problém, který chci řešit, dobře definovaný? Řešte jeden problém a řešte ho kvalitně. Tradičně potkáte člověka (oponenta), který vám řekne, že váš problém ve skutečnosti není problém (to je zcela typické u bakalářek, kde téma bylo “vyrobím počítačovou hru na téma X”). Je vhodné mít po ruce přímý nepopiratelný důkaz, že po vyřešení vašeho problému bude svět mnohem krásnější a civilizace pokročilejší, nebo lépe odbornou literaturu (tj. články, viz. výše), která tvrdí, že to problém opravdu je.
- Jak poznat dobře definovaný problém: Přepište váš návrh jako hypotézu a navrhněte experiment který umíte provést tak, že výsledky experimentu hypotézu buď potvrdí, nebo vyvrátí, nebo jasně určí hranici, kde platí a neplatí.
Nechci řešit moc velký problém, nebo víc problémů najednou? V takových případech si “házíte granát do bot” minimálně ze dvou příčin: Ztratíte zbytečně moc času na něco, co není pro splnění práce potřeba, a oponent vám vyčte, že práce není monografie. Bakalářky, které řeší víc malých problémů najednou, je musí správně pojmenovat jako jednu velkou a dobře definovanou skupinu problémů.
Jak obhájím výsledky? V práci budete muset prokázat, že jste opravdu něco vyřešili, a oponent bude pochybovat, že vaší zásluhou vůbec k nějakému vyřešení došlo. Připravte si jasnou metodu, jak zhodnotíte výsledek. V případě informatiků to může být např. změření rychlosti implementace, spotřeby disku a paměti, správnosti a přesnosti výsledků, apod. Vždycky je fajn ukázat trochu statistiky.
Jak budu interpretovat výsledky? Výsledek je potřeba zařadit mezi ostatní výsledky jiných lidí, kteří řešili stejný nebo podobný problém: Kromě měření svého programu většinou budete muset změřit i alternativní implementace, nebo pro svoje měření použít stejnou metodiku jako použil někdo jiný, aby bylo související výsledky možné férově porovnávat. Nikdo po vás ale nechce, aby vaše řešení toto srovnání vyhrálo! Negativní výsledek je taky výsledek a oponenti to pochopí. Rozhodně ale nepochopí nereprodukovatelnou nebo neférovou metodiku měření.
Čím naplním práci? Zvládnete o tom napsat 20 nenudných stránek? Dost informací na vyrobení kvalitního textu získáte čtením související odborné literatury (viz. výše). Z rešerše dvou až tří článků se bakalářka dá pohodlně napsat celá.

Obraz o očekávaném výsledku si můžete udělat průzkumem bakalářek, které už jsou obhájené. Důrazně doporučuju podívat se do Repozitáře závěrečných prací aspoň na 3 různé práce (včetně hodnocení oponentů).

Témata#

Ve většině případů mám konkrétní představu o tom, jak by práce měla vypadat a jak splní body uvedené nahoře. V případě zájmu a dotazů mi napište mail.

Pozn.: Nejsem příznivce programování “do šuplíku”, výsledky projektů je vhodné publikovat (např. jako opensource). Většina témat má po dokončení RP/BP potenciál být poměrně užitečná a začít žít vlastním životem.

Haskell#

Metabolic modelling#

Reimplementace částí COBREXA.jl a ConstraintTrees.jl v Haskellu (kvůli rychlosti a spolehlivosti).

Funkcionální ggplot#

Něco co dokáže rychle a jednoduše z CSV-style dat produkovat vizualizace na úrovni COW Fundamentals.

Kompilátory#

Zlepšení libovolného programovaciho jazyka pomocí Haskellového (nebo podobného) typověho systému.

Nějaká extrémně odlehčená varianta LLVM by se dost hodila.

Reprezentace a kompilace arrayových výpočtů, podobně jako v Accelerate. Práce na Accelerate je taky super.

Open-source#

FOSS reimplementace jakéhokoliv softwaru, který je dostupný jen jako služba nebo closed-source.

Vhodné nápady:

Google Keep (s aplikací)
streamovací služby a aplikace (např. pokračování této práce)
IRC backend ve kterém servery nemusí tvořit strom
E2E-encrypted chat pres IRC

Strukturované indexování kódu#

Kód je možné si představit jako DAG – skoro jako AST, ale stejné větve se sloučí. Z takového DAGu je možné vytrhávat malé kousky (malinké podgrafy) a používat je podobně jako n-gramy v textu, na počítání strukturální podobnosti kódu a na indexování.

Aplikace:

Rychlé šablonové vyhledání v kódu: Např., dotaz ?x[?i] = ?x[?i+1] najde array[index] = array[index+1] a a[b[c]]=a[b[c]+1], ale ne xxx[i] = yyy[i+1]. Implementace pomocí invertovaných indexů.
Pěkné měření a vizualizace strukturální podobnosti programů (např., ve vizualizaci bude vidět, že jeden program je jen přeformátovaná a přeházená verze druhého s přejmenovanými proměnnými).

Machine learning, redukce dimenzionality#

Aplikace samoorganizačních map a/nebo EmbedSOMu jsou super.

Search engines/Big data#

Běžná datová struktura pro ukládání dat v search enginech jsou skip-listy, s různými vylepšeními (především delta-encoding, zmenšování indexů slovníkem, Elias gamma coding, …). Cíl: Implementovat pěknou a moderní (a drasticky rychlejší) alternativu Apache Lucene/Lucy. Poměrně jednoduché téma s velmi dobrým využitím. Velmi vhodné pro počítačovou lingvistiku, potenciální aplikace v bioinformatice. (vyřešeno)
Hlavní nevýhoda invertovaných indexů je nemožnost efektivně zkombinovat skiplistovou metodu filtrování a “join” známy z SQL. Cíl: Prozkoumat co se s tím běžně dělá a naimplementovat/změřit/vylepšit nějaké existující řešení. Distribuované vyhodnocování podobných dotazů je super téma na diplomovou práci.
Asi nejrozumnější open-source distribuovaný search-engine (ElasticSearch) je napsaný v Javě a docela (dost) tím trpí. Cíl: Z dostupných lokálních C search enginů (Apache Lucy? CLucene? Xapian? Nebo předchozí nápady? Nebo něco vlastního v Haskellu?) a nevelkého množství distribuovaných algoritmů udělat něco škálovatelného a podstatně úspornějšího než ES.
Dost lidí má na disku velké množství velmi důležitých PDFek, typicky článků, ve kterých se nejde moc dobře vyznat. Vyhledat v takové hromadě název článku, autora nebo text není úplně jednoduchá zábava. Co takhle nějakou malou aplikaci (commandline a/nebo GUI) na textové indexování a prohledávání PDF? Co takhle to spojit s bibtexem a udělat z toho funkční bibliography/reference management system?
V “normálních” souborových systémech se invertované indexy musí ukládat do speciálního souboru, který typicky musí nějak obsluhovat ostatní uložená data. Co takhle mít souborový systém který adresářovou strukturu už ukládá invertovaně “sám”, a umí nějaké jednoduché dotazy vyhodnotit sám? Tj. každý soubor může patřit do nějakého nenulového velkého množství adresářů (stovek až tisíců), a uživatel pokládá dotazy na průnik adresářů a jejich podadresářů, např. “najdi všechny soubory otagované fotky/*, datum/2025/říjen/* a geo/Praha/*”.

Autotools z aktuálního století#

Pokud používáte UNIX, asi jste si všimli, že většina “ručně” nainstalovatelného software se instaluje trojkombinací ./configure; make; make install. Konfigurační skript (který je napsaný v čistém shellu a produkuje Makefile) je v 99.999% softwaru výsledkem použití programů autoconf a automake (dohromady autotools) které se zabývají tím, jak software dostatečně dobře zabalíkovat tak, aby šel postavit na jakémkoliv unixu, cross-kompilovat, přizpůsobovat, konfigurovat na místě, portovat, atd. apod. Interface configure je poměrně přímočarý a na všech platformách víceméně stejný, a výsledek je jednoduché použít správně i pro velice složité věci.

Hlavní vlastností systému je naprostá nezávislost na softwarovém vybavení cílového počítače: configure jde spustit na jakémkoliv počítači kde je POSIXový shell, bez jakékoliv nutnosti instalovat cokoliv dalšího.

Dokonalost tohoto systému je bohužel překonána jen jeho zastaralostí — autotools jsou napsány v divném template-shellu, který se jmenuje m4 a pro programátory narozené po roce 1900 je značně neprůhledný. Za léta používání se navíc nabalila tradiční hromada kompatibilitních pomůcek, které dnes už nejsou úplně potřebné.

Pokusy autotools překonat skončily fiaskem (scons apod.), nepřenositelností a vyrobením úplně nového spektra potíží následovaných progresivním neuchopitelným fiaskem (cmake apod.) nebo totálním zapomenutím kvůli různým hloupostem v návrhu (mkconfigure, bmake, apod.).

m4 je každopádně jen poměrně jednoduchý generativní jazyk, pomocí kterého se (s dodatkem poměrně velké knihovny triků) seskládá shellový configure. Ten je následně schopný zkontrolovat cílovou platformu a podle výsledku z nějakého vzoru Makefile.in sestavit výsledný Makefile. Požadavek na shellovost je daný přenositelností — shell je jediný jazyk, který smíte očekávat na opravdu každém unixu.

Takže — co takhle z procesu vytrhnout m4 a kompilátor configure-skriptu napsat v něčem rozumnějším, modernějším, typovaném a hezkém? Co třeba v Haskellu, který je na psaní DSL naprosto nepřekonatelný? Nebo to přestřelit a celý systém vyrobit jen v make (protože standardní make je taky na každém unixu)?

Téma je extrémně vhodné pro UNIXově smýšlející studenty, výsledek má šanci posunout open-source svět o dost dopředu.

Simulace/fyzika#

Vírníky (a.k.a. autogyro a.k.a. gyrocopter) vypadají jako vrtulníky, s tím rozdílem, že vrchní vrtule není poháněná motorem, ale fyzikální magií. Jejich pohyb se od klasických letadel a vrtulníků následně odlišuje v několika podstatných a značně neintuitivních detailech (např. “zatočit dolů” je poměrně nebezpečné a je potřeba to dělat jinak). Kvalitní softwarová simulace letu vírníku zatím není k dispozici.
Dostatečně dobrá simulace pískových přesýpacích obrázků co se prodávají kolem Václaváku je ve skutečnosti dost složitá a výpočetně náročná zábava. Simulaci by bylo vhodné provést na GPU.
Kvalitní/otevřený software na simulaci a počítání parametrů rádiových antén v současnosti úplně chybí (téma návrhu antén je obecně považováno za temnou černou magii, což je samozřejmě potřeba vyvrátit kvalitní bakalářkou). Inspirace: proč funguje tohle?
Dnešní fotorealistický ray-tracing není fotorealistický, protože ignoruje rychlost světla! ( :D ) Co takhle nasimulovat, jak vypadá průlet nějaké výkonné stíhačky Malostranským náměstím rychlostí 0.8c, 1c a 1.5c (zevnitř i zvenku)? Inspirace zde.

Networking#

QoS v různých ad-hoc sítích. Jaké předpoklady jsou potřeba k dosažení optimálního rozložení kvality komunikace např. v dynamických hejnech robotů/dronů/družic?

Umí se roboti vůbec domluvit na vhodném adresování celého hejna?

Jde to udělat bezpečně? Umí se dostatečně velký počet robotů vůbec na něčem spolehlivě domluvit?

Je možné volně pokračovat v předchozí bakalářce na téma QoS.

Immediate-mode GUI#

Styl programování uživatelských rozhraní známý z ImGui je, mírně řečeno, s obrovským odstupem nepřekonaný způsob výroby GUI. Immediate-mode interfacy se ale moc nehodí na běžné desktopoviny, protože je potřeba je pořád dokola překreslovat.

Nešlo by vymyslet immediate-mode GUI, které by fungovalo i s pomalejšími kreslícími metodami? Konkrétně: Nebylo by možné (za použití několika extra předpokladů o uživatelském kódu) kreslící funkci rozumně pozastavovat, případně spouštět jen částečně, aby nemuselo docházet k takovému množství kreslení?

Nešlo by ImGui předělat do terminálovité podoby? Tím by se výroba kvalitních terminálových aplikací mohla v porovnání s běžným ncurses značně zjednodušit. (Téma je hodně unixové a určitě dobrý kandidát na užitečný open-source.)

Jak udělat podobné super GUI v čistém Haskellu (bez blbostí jako IORef nebo Ptr)? Nebudou na to náhodou potřeba Lensy?

Hry#

Předem, uvědomte si, že “obyčejná hra typu X” není dobré téma na bakalářskou práci. Hry už umí programovat každý. Pokud chcete dělat hru, je potřeba do ní propašovat nějakou zajímavost — třeba algoritmus, který je výsledkem současného vývoje, není moc známý (ideálně neexistuje veřejně dostupná implementace) a neotřele a efektivně dělá něco extrémně užitečného a/nebo složitého. O související teorii budete muset napsat cca 20 nenudných stránek.

To ale určitě neznamená, že hry vhodné pro RP/BP neexistují! Nápady:

Remake a zlepšení Transport Tycoonu (OpenTTD). Nejvetší otrava v tom původním je omezení na “čtverečkovitý” tvar/směr/kombinace kolejí, tunelů a mostů (kvůli tomu nejde např. vyrobit několik populárních tvarů křižovatek, nájezdních systémů apod.). Znalcům OpenTTD doporučuju navštívit a důkladně projít tento archiv. Na podobné práci je možné bakalářek vymyslet několik:
- Hledání optimálních cest v dynamicky zacpaném grafu kolejiště není úplně jednoduché (vyřešeno)
- Uživatelský interface umožňující dostatečně dobrou konstrukci složitých křižovatek a systémů nájezdů apod. hraničí s možnostmi CAD-like systémů. Práce se může zabývat hledáním optimálního tradeoffu mezi složitostí systému, možnostmi, a rychlostí stavění.
- Ekonomika v původním Transport Tycoonu není nijak dokonalá ani složitá; systém je možné přepracovat tak, aby víc vyhovoval potřebám hry.
- Generování mapy. Jednorázově to je dost primitivní, problém je, že mapa se v TTD vyvíjí postupně, tj. je potřeba generovat i malé časové změny, které celý systém nevyvedou z “rozumného” stavu. Konkrétně např. simulovat vývoj od vesnice, přes městečko (s úplně jiným systémem silnic a hlavních budov, který zhruba odpovídá původní vesnici), až po velkoměsto (opět s úplně jiným systémem, který ale stále zhruba odpovídá původní vesnici).
Nebo remake Nidhoggu ( v2 ) kde jsou světelné meče a lejzry. Místo Wurma je možné použít libovolnou zrůdu ze SW (je jich tam dost). Možná extra featury? Komba? 2v2?
Nebo třeba remake Die by the sword. Trik: hráč ovládá pohyb meče přímo myší, takže multiplayer je docela (dost) zábava. V tomhle případě taky světelné meče, samozřejmě. Možná slow-motion (mimochodem slowmotion ve hvězdných válkách až do předposledního dílu dost chyběl). Kombinace s předchozím by byla extrémně dobrá.
Nebo třeba nějakou hru, kde kouzlit magii je opravdu těžké (ne úplně realisticky těžké, tedy nemožné, ale rozhodně těžší než dokola mačkat klávesovou zkratku Č jako čaruj). Např. kreslením různých kombinací a konvolucí nějakých run/tvarů, třeba hůlkou nebo do písku (tady v té hře je “pozemních” run vůbec kupa). Čím komplexnější obrázek, tím větší efekt kouzla. Rozpoznávat runy za běhu hry (hlavně jejich konvoluce) je pěkný a zajímavý problém vhodný na bakalářku (téma už bylo vyřešené ). Volné pokračování: multiplayer (kooperativní kreslení produkuje složitější obrazce, tj. víc zábavy). (částečně vyřešeno)
Nebo třeba ještě jednou to samé s magií, akorát místo obrázků použít komba/mantry/jiné časové sekvence. Částečná inspirace zde.

OpenStreetMap#

Práce s mapami je poměrně zábavná — kvalitních dat je hodně a výsledek je okamžitě užitečný a pěkný. Moje nápady jsou biasované směrem k cyklistice, ale je možné pracovat na čemkoliv jiném:

Automatická normalizace označených tras (např. spojení rozpojených segmentů cyklostras nějakou heuristikou).
Pěkné renderování cyklotras. Např. mapa českých cyklotras spojená s výškovými a povrchovými profily a různými extra featurami jako jsou města, památky, obchody, hospody a kempy v okolí.
Open-source alternativa webů a funkcionality jako má např. Bikemap zcela chybí. (částečně vyřešeno)
Open-source verze OpenCycleMap.
Automaticky generovaná verze CyclingCols.

Pro podobné “veřejně užitečné” projekty je většinou možné sehnat finanční podporu na provoz výsledku.

Decentralizace (internetu apod.)#

Je zajímavé a vhodné vyrábět bezpečné P2P alternativy tradičně centrálních systémů jako DNS, vyhledávače, sociální sítě, mail, herní lobby, atd. Extrémem je decentralizace celé administrativní monstrozity IANA/ICANN/RIRs.

Jakákoliv zlepšení/rozšíření protokolu Kademlia (aka Mainline DHT pro BitTorrent) jsou super. Šlo by routování (v DHT extrémně náhodné a ne úplně efektivní) nějak vylepšit aby využívalo lokalitu zdrojů?

Cokoliv fungujícího podobně jako BitTorrent je super.