Ročníkové projekty (NPRG045)#

Aktualizované informace o pravidlech, podmínkách a průběhu NPRG045 jsou vždy k dispozici na https://teaching.mff.cuni.cz/nprg045-web/.

Tato stránka obsahuje především informace o tom, co typicky očekávám u projektů, u kterých jsem vedoucí – tj. především vhodné okruhy témat a návaznost na bakalářskou práci.

Seznam témat dole je dost obecný, dostatečné rozšíření jakéhokoliv (i vyřešeného) tématu je možné použít i na diplomovou práci, softwarový projekt, apod.

Obecné informace#

Vhodnost témat#

Téma projektu by mělo souviset se specializací nebo odborným zájmem vedoucího. V mém případě ideálně zamiřte na Google Scholar nebo GitHub, najděte si nějaké projekty na kterých jsem pracoval a příbuzná/rozšiřující/podobně tvarovaná témata budou nejspíš OK. Velmi vhodné okruhy témat pro RP/BP jsou:

použití funkcionálního programování
velmi low-level projekty (C, malé systémy)
užitečné UNIXovité pomůcky zjednodušující život jiným programátorům
síťové/distribuované aplikace
post-kvantovou (nebo jinak okrajovou) kryptografii
HPC pomůcky
Bioinformatika a hry jsou OK

Budu preferovat ročníkové projekty, u kterých se počítá s rozšíření na BP.

Níže témata najdete prozepsaná, okomentovaná, a s příklady.

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. Zásadním cílem RP je materializovat jistotu o tom, že vypsaný bakalářský projekt je možné úspěšně dokončit (a obhájit). V ideálním případě je výsledkem RP prototyp programu a finalizované zadání bakalářky.

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í alespoň na 3 různé práce (včetně hodnocení oponentů).

Materiál#

Udržuju alternativní (kompatibilní ale poněkud zaujatější) šablonu na BP/DP/RP: github.com/exaexa/better-mff-thesis
- Text v šabloně obsahuje velké množství doporučení a pomůcek pro psaní, především o struktuře práce a použítí TeXu.
- Doporučená literatura o psaní (Sparling, Glasman-Deal) jde většinou sehnat v knihovně, pokud ne, dejte vědět.
- Pokud si myslíte, že šablona není kompatibilní s oficiálním doporučením, taky dejte vědět.
Pro účely obhajob (a obecně prezentací) se může hodit jednoduchá šablona posteru, jednoduchá šablona prezentace, a pokročilejší (zaujatější #betterposterová) šablona posteru.
LaTeXová šablona na specifikaci RP

Co napsat do mailu?#

Komunikace je neformální, prosím nevyrábějte kolem informace zbytečnou omáčku, úplně strohý obsah je OK. Omáčka z GPT a podobných rozmazávačů informace je vyloženě otravná. Generovaný obsah celého mailu je na hranici slušnosti.
Místo omáčky k hlavní informaci přidejte stručně následující:
- Odkaz na něco (nebo slovní popis něčěho), co jste už udělali (např. hotové projekty, hotové předměty, a podobné úspěchy). Před zahájením projektu je nejčastěji potřeba z(a)jistit, že téma je pro studenta ve stanoveném čase zvládnutelné. Předchozí zkušenost z podobných projektů (ač třeba výrazně menších) je většinou nejlepší důkaz.
- Co vás baví a/nebo jakou máte osobní motivaci pro dané téma/okruh témat. Vždycky je lepší se zamyslet, jestli téma nejde mírně přiohnout osobním cílům. Kromě motivace je to vhodné i kvůli tomu, že potenciální pokračování/zlepšení/nové verze projektu budete udržovat a rozvíjet podstatně radši. To je důležité hlavně pro projekty, ze kterých má být úspěšný open-source.

Nevhodná témata#

Closed-source nebo obecně témata, které nejde publikovat/zveřejnit/použít kdekoliv jinde. Kooperace s průmyslem neopodstatňuje výjimky.
Ryze implementační práce bez vztahu k nějakému současnému výzkumnému tématu nebo nevyřešenému teoretičtějšímu problému. (Tvrzení “tento software ještě neexistuje” není samo o sobě dostatečný problém.)
Z etických důvodu nepovedu práce, které využívají (závisejí na, dotýkají se, …) následující:
- velké cloudové služby
- produkty “big tech” společností
- advertising (aka. spam)
- monitorování a profilování jednotlivců/uživatelů
- tradiční kryptoměny
- použití jazykových modelů jako “umělé inteligence”
(Práce které tyto problémy nahrazují, sabotují, zesměšňují nebo jinak odstraňují jsou samozřejmě OK.)
Observační “machine learning” a “data science”, typicky práce, kde výsledkem je jen vytvoření nějakého prediktoru z existujících dat, bez většího příspěvku k metodologii.

Konkrétní témata#

Ve většině případů uvedených níže mám konkrétní představu o tom, jak by práce měla vypadat a jak splní požadavky “bakalářskosti” shrnuté nahoře. Některá témata jsou dost ad-hoc a jde mi hlavně o efektní výsledek (hlavně v případě her a simulací), což pro účely BP nemusí být úplně vhodné, ale většinou v nich jde najít zajímavý problém.

V případě zájmu a dotazů mi každopádně napište mail.

Pozn.: Nejsem příznivce programování “do šuplíku”, výsledky projektů je vhodné publikovat (typicky jako open-source). 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#

BIKE key encapsulation#

Implementace post-kvantové výměny klíčů v Haskellovém ekosystému, např. do balíku Crypton, podobně jako už existující MLKEM.

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.

Pravděpodobně může navazovat/stavět na hgg.

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. (téma je zabrané)

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

DSL pro specifikaci a design fontů#

Výroba fontů je pořád dost manuální práce. Cílem by bylo vyrobit nějaký metajazyk na popis a kombinování glyfů, kterým by fonty (a hlavně jejich varianty jako light/bold, slanted/deslanted, condensed/wide, a kombinované glyfy (čěšťíňá)) šly generovat rozumně automaticky a bez větších manuálních úprav. Pravděpodobně hodně 2D matematiky, CADovítých prostorových constraintů a složitých křivek. Nejspíš včetně nějakého uživatelského rozhraní (freeCAD-like?) na prohlížení a mírnou editaci.

Praktickým cílem by asi bylo vyrobit dobrý regenerovatelný a parametrizovatelný open-source DIN font.

mini-git#

Haskellová nativní knihovna pro ovládání gitových úložišť už existuje. Pěkná práce by se mohla pokusit vytvořit maličký alternativní gitový interface, ideálně specializovaný na trochu jiný workflow než kanonický git (tj. s indexem a jedinou větví) ale pořád poněkud kompatibilní s normálním gitem.

Zajímavé experimenty:

přímá podpora pro tokenové diffy a merge
řešení merge konfliktů uložené přímo v historii
podpora pro práci na víc větvích současně (uživatel pracuje na tzv. “merged view”)

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&authenticated chat přes IRC
Trénování jazyka (jako s Duolingem), kde věty generuje a kontroluje nějaké jednodušší LLM

RDF, Data linking & management#

Excel-like interface pro úložiště RDF: Cílem je zničit SPARQL jako primární (špatnou) metodu interakce s RDF, a místo toho dát uživatelům něco výrazně užitečnějšího i intuitivnějšího. (Nutno znát React a TypeScript, nebo nějakou ekvivalentně silnou technologii.)
Blob storage pro úložiště RDF: Binární data se do semantických databází úplně nehodí, ale je občas potřeba je někam ukládat. Cílem je vyrobit malou “pomocnou” databázi která umožní uživatelům (přes API) jednoduše ukládat malé datové bloby a ty pak linkovat ze sémantické linked-data databáze. (Nutné znát nějaký dobrý serverový jazyk, ideálně Haskell/Rust/Go)
Virtualizované úložiště dat. Něco jako iRODS, jen s interfacem, technologiemi a komplexitou zvládnutou jako v současném tisíciletí. Cílem je mít distribuovaný software který umí managovat poměrně velké datasety, a pomocí nějakých deklarativních pravidel je vhodně přesouvat mezi servery, přidělovat k nim přístupy uživatelům pomocí všemožných kanálů (SFTP, S3, HTTP, …). K tomu je samozřejmě potřeba nějaký boční systém na metadata management, ale ten bychom chtěli ze softwarovo-inženýrských důvodů udržet co možná nejvíc oddělený. (Nutné znát dobrý serverový jazyk, opět ideálně Haskell.)
Sémantický metadata management systém pro předchozí, v RDF.

Strukturované indexování kódu#

Kód je možné si představit jako DAG – skoro jako AST, ale stejné větve (např. stejná použití jedné proměnné) 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).
Vizualizace by ideálně byla vhodná přímo jako reactová komponenta. Bylo by dost užitečné mít možnost udělat “zoom out” a interaktivně si prohlídnout větší množství zdrojáků najednou. Vizualizace je vzhledem k množství dat a potenciálních podobností dost komplexní problém. Možná nějaký mouse-over highlighting jako ve sleepwalku?
full-source doplněk hooglu (výhoda: data už jsou k dispozici celkem pěkně předzpracovaná)

Research software#

Machine learning, redukce dimenzionality#

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

MaBoSS (maboss.curie.fr) je stochastický simulátor signálních sítí, výsledky jsou bohužel příliš stochastické než aby šly jednoduše prohledávat. Co taky zkusit samoorganizační mapy? (relwork)

Networking#

Několik témat je na webu DecentraLabu.

Fungování a bezpečnost v různých chaoticky vytvořených ad-hoc sítích.

Předchozí studenti řešili post-kvantové SSL a post-kvantovou streamovou autentikaci. Nešlo by obojí slepit dohromady a vyrobit nějaké SSH úplně bez použití “trapdoorových” kryptografických primitiv? (téma je zabrané)
Je možné volně pokračovat v předchozích bakalářkách na téma QoS a adresování.
AuFi: jako WiFi, ale pakety se posílají přes (vyšší) audio frekvence. Vhodné pro milovníky zvuků z dial-up modemů a pásek do ZX spekter.
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ů? Obecně, jakékoliv vylepšení a využití protokolů z BitTorrentu je vhodné téma.
Náhrada DNS nějakým komunitním schématem, ideálně kryptograficky odolným dost na to, aby nepotřebovalo centrální management. Při dostatečně intenzivní decentralizaci centralizované pojmenovávání věcí samozřejmě selže, takže jedním z hlavních problémů je transfer a adopce petnames, a vyrovnání se s tím že konceptu “subdomén” chybí doménový kořen (protože ten by byl moc centrální).
Jde nějaké takové “local petname” DNS vyrobit nad DHT?

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/*”.

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.

Potenciálně vhodné nápady:

Remake Freeways:
- s editovatelnými silnicemi a optimálními křivkami (CAD-style konstrukce, geometrické constrainty, track transition curves jsou matematicky zajímavé)
- s podporou pro víceproudé silnice a simulacemi řazení v takových silnicích
- s podporou pro koleje, vlaky, návěští a semafory (potenciálně remake a zlepšení Transport Tycoonu aka 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.).

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:

Open-source verze OpenCycleMap.
Automaticky generovaná verze CyclingCols.
Praktické renderování cyklotras pro navigaci tak, aby cesta byla nakreslená vždycky “rovně” na úzkém vyrovnaném proužku mapy, a kolem bylo vidět jen rozumné okolí podstatné pro navigaci: druhy silnic, tvary křižovatek, města a jejich jména, amenities (kempy a obchody apod.). Bylo by super umět i “dynamický zoom”, aby např. 20km prázdné silnice nezabíralo 200× víc místa než 100 metrů zajímavého města. Ve výsledku by si cyklista před cestou nemusel tisknout obrovskou 2D mapu, ale jen kompaktní 1D proužek (který jde různě zfoldovat). Podle možností jde projekt rozšířit např. o výškové a povrchové profily, ukazatele na amenities které jsou blízko ale nevešly se na mapu (“1km zajížďka na hrad tudy →”), apod.