e-x-a.org » NPRG045 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.

Témata, která mám už dlouho v hlavě a chtělo by je zpracovat jsou seřazená 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 rozšiřovat.

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í.

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.

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 teorii konečných grup a těles (stačí si pamatovat něco málo z lineární a obecné algebry), jinak to je ale celkem jednoduché.

Konkrétní nápady:

  • Implementace/ladění SPHINCS podpisu podle Bernstein et al. (2014)
  • Post-kvantové podpisy typu CFS (Courtois, Finiasz, Sendrier 2001) jsou celkově dost super, ale podepsání dokumentu trvá slušně dlouho (je to nedeterministické podobně jako invertování hashů). Co takhle použít to jako proof-of-work signature? Nemělo by to nějakou zajímavou vlastnost se kterou by šel např. zlepšit blockchain, vyrobit nějaký altcoin, nebo něco podobného?
  • 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

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). Cíl: Implementovat pěknou a moderní (a drasticky rychlejší) alternativu Apache Lucene/Lucy. Poměrně jednoduché téma s dobrým využitím.

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ápad?) a nevelkého množství distribuovaných algoritmů udělat něco škálovatelného a podstatně úspornějšího než ES.

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 .

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 neznamená, že hry vhodné pro RP/BP neexistují. Nápady:

  • Třeba remake Starfighteru 3000. (hlavní featura: dynamická scéna, realistické bourání kopců a domů laserem z letadla.)
  • 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 zábava. V tomhle případě taky světelné meče, samozřejmě. 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). Třeba 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. 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é sekvence.
Simulace/fyzika/paralelismus

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.

Kvalitní/otevřený software na simulaci a počítání parametrů rádiových antén v současnosti dost chybí.

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 fajn 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

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.

Framework pro uživatelskou aplikaci

Univerzální systém pro jednoduchou tvorbu CRUD-type aplikací založený na grafech. Hlavní featura je programátora úplně oprostit od nutnosti přemýšlet nad uživatelským interfacem — systém se “zprovozní” jen tím, že “programátor” nadefinuje, jak vypadají a souvisejí data a jaké jsou strukturní požadavky. Interface pro aplikaci pak bude univerzální.

Hlavnější featura by měl být pomyslný hřebík do rakve borcům, co institucím prodávají neskutečně předražený a směšně nekvalitní software — napadlo mě to v okamžiku naprostého šílenství nad zpracováním nejmenovaného účetního systému.

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 nebo nervovo-síťově.

Decentralizace internetu

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/RIR.

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, blockchain jako důkaz existence.