e-x-a.org » NPRG045 Ročníkový projekt

Na ročníkový projekt můžete přijít prakticky s jakýmkoliv vlastním tématem. Budou se mi líbit projekty co obsahují např. C++, funkcionální programování, Haskell, UNIX, internety/sítě, distribuované věci, kryptografii. Dostatečně akční hry jsou vítány.

Předem několik slov o tom, na co se zaměřit.

Jak se pozná kvalitní bakalářská práce?

Volně přeloženo: Jak poznat bakaláře z MFF/Informatiky od normálního člověka který umí 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ýsledků 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 je takto schopný vědecky řídit a analyzovat svou vlastní práci.

Ročníkový projekt s bakalářkou souviset nemusí (především u teoreticky orientovaných bakalářek), ale je poměrně rozšířeným zvykem, že souvisí. 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í, 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 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ší 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í.
  • Nechcete ř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ů.
  • 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.
  • 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 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í. Na tu druhou stranu rozhodně nepochopí nereprodukovatelnou nebo neférovou metodiku měření.
  • 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 dá bakalářka napsat celá.

Témata

Témata, která mám už dlouho v hlavě a chtělo by je zpracovat jsou seřazená níže podle velmi hrubého odhadu obtížnosti — nahoře jsou dobře `usazené’ a poměrně přímočaře obhajitelné práce, dole nápady kde bude potřeba trochu vysvětlování a studentovy vlastní iniciativy. *Zabraná témata jsou označená, ale je možné (a vhodné!) je i přesto rozšiřovat.*

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.

Networking

Nápad: Jednoduchý distribuovatelný traffic scheduler pro internet, založený na principech podobných CoDel a SFQ . Výsledkem bude užitečný algoritmus a zlepšení internetu, které všichni chtějí. (téma je zabrané)

Vhodné pro studenty, kteří vědí něco o počítačových sítích a jejich napojení na operační systémy (třeba jak fungují iptables/tc). Téma je poměrně jednoduché a navazující bakalářská práce má potenciál být velmi dobrá. Je potřeba umět C.

Jiný nápad: 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 (téma je zabrané)? Jde to udělat bezpečně? Umí se dostatečně velký počet robotů vůbec na něčem spolehlivě domluvit?

Kryptografie/bezpečnost

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 ještě míň z pravděpodobnosti), jinak to je ale celkem jednoduché.

Konkrétní nápady:

  • Implementace/ladění SPHINCS podpisu podle Bernstein et al. (2014) (téma je zabrané)
  • 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?

Search engines, text/language processing

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

(2) 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í.

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

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.). Vhodné jak z hlediska simulace (hledání cest v dynamicky zacpaném grafu kolejiště není úplně sranda) tak z hlediska ekonomické analýzy. Znalcům OpenTTD doporučuju navštívit a důkladně projít tento archiv.
  • 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 poslední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. Taky dobré téma na multiplayer (kooperativní kreslení produkuje složitější obrazce, tj. víc zábavy). (téma je zabrané)
  • 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.
Autotools z aktuálního století

Pokud používáte UNIX, asi jste si všimli, že většina “ručně” nainstalované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, atd apod. Interface configure je poměrně přímočará a na všech platformách stejná. 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 co se narodili po roce 1900 je značně neprůhledný.

Pokusy autotools překonat skončily fiaskem (scons apod.), nepřenositelností a vyrobením úplně nového spektra potíží (cmake apod.) nebo totálním zapomenutím kvůli růzým blbostem (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 a make jsou jediné jazyky, které smíte očekávat na opravdu každém unixu.

Takže co z procesu vytrhnout m4 a kompilátor kompilátoru Makefilu 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?

Použitelný uživatelský interface na e-mail

(téma je zabrané)

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

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 .

Simulace/fyzika/paralelní počítání

(1) 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 celkem složitá zábava.

(2) Kvalitní/otevřený software na simulaci a počítání parametrů rádiových antén v současnosti dost 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).

(3) 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 v 0.8c, 1c a 1.5c (zevnitř i zvenku)? Inspirace zde.

Framework pro uživatelskou aplikaci

V okamžiku naprostého šílenství nad zpracováním jednoho nejmenovaného známého účetního systému z Plzně (toho, který avantgardností návrhu konkuruje už jen tomu z Jihlavy) mě napadlo, že by všechny formulářovíté aplikace typu účetnictví, evidence, komunikace, procesní řízení, apod. mohly sdílet jeden interface — celý systém je stejně většinou možné odvodit od nějaké specifikace toho, jak mají vypadat uložená data a kdo s nimi může co dělat.

Výsledkem by měl být univerzální systém pro jednoduchou tvorbu CRUD-type aplikací založený na nějaké obecné databázové struktuře (ideálně na grafech). Programátora by to mělo úplně oprostit od nutnosti přemýšlet nad uživatelským interfacem nebo kódem — systém by se měl “zprovoznit” jen tím, že “programátor” nadefinuje, jak vypadají a souvisejí různě pojmenovaná data a jaké jsou strukturní požadavky. Interface pro všechny takové aplikace pak bude univerzální.

Bonus: Pozitivní karma za finální zničení předražených a směšně nekvalitních účetních systémů.

Funkcionální programování

Psát programy v Haskellu je fajn: Člověk napíše 100x míň řádků kódu, programy mu pak nechcípají, a většinou se toho i dost naučí. Je super to v rozumné míře aplikovat na jakýkoliv jiný tady uvedený problém. Nebo třeba:

  • malinké jednoúčelové funkcionální jazyky, např. pro automatické generování obsahu ve hrách
  • optimalizátory, inlinery, částečné vyhodnocovače a podobné zrychlovače programů
  • nestandardní a/nebo experimentální typové systémy— třeba chytrý doplňovač správného tvaru const/move referencí do C++ založený na lineárních typech
  • jakékoliv webové věci, použití Yesod, Servant, Reflex-DOM.

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

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)