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í 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.
Machine learning, redukce dimenzionality#
Embedding#
Na světě je hodně zajímavých databází s obrovským objemem vysokodimenzionálních dat, které by bylo fajn nakreslit jako jeden přehledný obrázek pomocí embedování do 2D. Třeba pomocí něčeho jako t-SNE nebo UMAP . Některé databáze jsou bohužel na tyto metody příliš velké nebo příliš mnohadimenzionální (typickým příkladem je PubChem, ve kterém je přes 200 milionů chemických struktur, které mají přes milion identifikovatelných “featurových” domenzí). Vizualizace celého PubChemu která je dostatečně úsporná na to, aby šla např. spočítat na notebooku, je fajn bakalářská až diplomová práce.
Jiné nápady k vizualizaci: celý obsah wikipedie, data z scRNAseq, diskografie nějaké kapely z 80tých let, celý obsah githubu, všechny série Simpsonů, apod.
Jakákoliv práce na samoorganizačních mapách a/nebo EmbedSOMu je OK.
Vyhledávání v multimediálních datech#
Řešení problému automatické anotace videa. Například: Na internetu se vyskytuje obrovská hromada nahraných přednášek a slajdů, v nich ale není možné moc dobře vyhledávat. Bylo by fajn je převést na text a nějakou prohledávatelnou obrázkovou informaci (metody na extrakci těchto dat už existují), a nechat je uživatele prohledávat textově.
Velice dobré a dobře obhajitelné téma s okamžitým praktickým využitím.
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?) 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 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í reference management system?
Použitelný uživatelský interface na e-mail#
GoogleMail/Inbox killer: Interface na maily který umí tagy, pořádný fulltext search (jako např. notmuch-web), a má interface co vypadá jako z aktuálního tisícíletí (dobrý příklad: Google Inbox, špatný příklad: gmail, outlook).
Aktuálnost tématu je navíc zvýšená tím, že google se v březnu 2019 rozhodl Inbox přestat provozovat.
Poměrně jednoduché téma s dobrým využitím, velmi vhodné na BP. Je potřeba umět programovat pro web, tj. znát javaskript a nějaký “backendový” jazyk. Nebo to napsat v haskellu .
(téma už bylo částečně vyřešené ale je možné volně pokračovat, především prací na serverové části)
wdiff, wpatch, wmeld#
(většinově vyřešeno)
Běžné UNIXové utility diff a patch se hodí na zpracovávání line-by-line
patchů, které jsou dost vhodné na zdrojový kód a podobné dobře odřádkované
věci. Existuje i hromada nástrojů usnadňujících mergování, kromě tradičního
gitu i vizuální, např. kdiff3 nebo meld.
Pokud ale gitem zpracováváte např. “lidský” text, ve kterém rozdělení na víc
řádků nemá velký význam, používat standardní diff, patch na mergování je dost
otrava. Typická problémová situace nastává při mergování dvou malých změn v
jednom odstavci textového dokumentu — výstup standardního diffu v obou
případech nahradí celý odstavec a vznikne automaticky neřešitelný konflikt.
Naštěstí existuje wdiff (který místo nahrazování celých řádek v souboru
ukazuje rozdíly na úrovni jednotlivých slov), případně git diff --word-diff
(který je navíc pěkně barevný). Odpovídající nástroje pro patchování pomocí
takovýchto patchů (wpatch) ani pro mergování (např. wmeld) bohužel zatím
neexistují. Cílem projektu by samozřejmě bylo je prozkoumat, vhodně navrhnout a
vytvořit.
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.
Kompilátory a programovací jazyky#
Typový systém Haskellu kupodivu není složité implementovat — základní verze je mnohem jednodušší než např. typový systém C a vejde se na zhruba 250 řádků kódu.
Cílem práce by bylo zkombinovat C s typovým systémem Haskellu; výsledný jazyk by částečně kombinoval výhody obojího (rychlost a značnou odolnost proti chybám).
Na výsledku lze stavět další práce — např.:
- drobným vylepšením o lineární typy vznikne jazyk prokazatelně lepší než Rust
- drobným rozšířením o číselné typové literály vznikne jazyk prokazatelně silnější než C
- vhodným zapojením defunkcionalizace vznikne jazyk podstatně rychlejší než (ale stejně expresivní jako) Haskell
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.
Grafová databáze#
Malá a rychlá grafová databáze (tj. bez Javy, ne jako Neo4J apod.) která transparentně řeší problém lokality dat pomocí líné volné hierarchie. (Myšlenka je (velmi implicitně) podobná dynamickému hledání malých separátorů.)
Kryptografie/bezpečnost#
Existuje kategorie “low-tech” šifer, které jdou poměrně pohodlně a dostatečně spočítat “ručně” bez pomoci počítače. Například ElsieFour, nebo moje oblíbená varianta LS47. Cílem práce by bylo vytvořit low-tech hashovací funkci, následně např. low-tech podpis (pomocí např. Merkleho stromů) nebo v extrémním případě přijít na nějakou low-tech metodu výroby společného tajemství (a.k.a. Key exchange, podobně jako Diffie-Hellman) nebo úplné asymetrické šifry (ale to už je dost obtížné).
Kdysi jsem zpracovával postkvantovou kryptografii ( https://github.com/exaexa/codecrypt ). Na MFF už vznikla i částečná post-kvantová náhrada SSL, knihovna využívající SIDH se kterou jde jednoduše vyrobit postkvantové bezpečná komunikace, konkrétně třeba něco jako SSH. Na RP/BP je možné jeden z projektů rozšířit o novou funkcionalitu.
Vhodné pro studenty s určitým přehledem/zájmem o bezpečnost a související matematiku (stačí si pamatovat něco málo z lineární a obecné algebry a z pravděpodobnosti). Konkrétní nápady:
- Implementace/ladění SPHINCS podpisu podle Bernstein et al. (2014)
- Post-kvantová náhrada CA hierarchie. Problém: postkvantové certifikáty jsou značně nepraktické. Půjde to vyřešit interaktivně (třeba pomocí SIDH)? Nebo třeba decentralizovaně v kombinaci s předchozím?
CPU/FPGA#
Vývoj nějaké netradiční, rozumně výkonné architektury, kde neexistují anomálie typu Meltdown/Spectre a je vhodná na provozování mikrokernelů.
Detekce anomálií#
Software který dostává (velké) hromady nějak označených časových dat (např. výstupy z nějakého monitorovacího systému, pingy, teploty nebo přenosové rychlosti různých počítačů v čase) nějak je zpracovává aby neukládal všechno, a je schopný upozornit na anomálie chování (náhlé změny, jiný průběh než minulý týden) nebo předpovědět problém (např. že něco postupně roste a vypadá že za nějaký čas přeroste nějakou nastavenou hodnotu).
Cíl: zjednodušit audit rozsáhlých systémů tím, že se program o systému naučí všechno sám a oznámí např. top 100 aktuálně nejvíc podezřelých věcí.
Možno pojmout statisticky, entropicky, nebo nervovo-síťově.
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.
Další zajímavý problém: Efektivní automatický routing v obrovské nestabilní síti —- Internet s jedinou obrovskou, pokudmožno spolehlivou a proti nepřátelům odolnou routovací doménou, dynamická adresace pro minimalizaci velikosti routovací tabulky, proof-of-work-like důkaz existence. (Nápad: setrvačnost jde vyrobit pomocí onetime/fewtime signatures)