Na této stránce najdete omezení a návrhy témat pro ročníkové projekty a bakalářské práce, které bych byl schopen a ochoten vést.
Nezbytné okolnosti:
Napište mail na adresu bojar@ufal.mff.cuni.cz a dohodneme se na dalším postupu. Obecně vám téma zarezervuji. Až se napevno přihlásíte, odeženu všechny další zájemce ve frontě za vámi.
Velmi široce představené náměty témat naleznete v této prezentaci. Témata mohou posloužit jako ročníkové práce/projekty, bakalářky, diplomky i týmové SW projekty. Často je totiž možné téma napřed zúžit pro účely ročníkových projektů a následně rozvinout do navazující práce.
Můžete též přijít s vlastním návrhem, nevzdalujte se však prosím příliš od těchto oborů:
Rád odpovím na jakékoli otázky a vyjasním tajemné záležitosti v návrzích témat, tohle vysvětlení bude nejsnazší provést osobně, stavte se za mnou.
Už se mi stalo, že jsem vedl a velmi kladně hodnotil práce, u kterých pak oponent někdy i velmi důrazně kritizoval zejména vývojovou dokumentaci. Řiďte se proto prosím doporučeními a prohlédněte si některé ukázkové práce z následujících odkazů.
Nejlepším vysvětlením je příklad:
Další poznámky:
Cílem projektu je navrhnout a implementovat několik automatických metod pro zjišťování, jak moc dvě věty v přirozeném jazyce (třeba češtině) říkají totéž. Primitivní možností je počítání slov, která se vyskytla v obou větách. Některé z navržených metod by měly též vycházet ze závislostního (větného) rozboru, který je pro české texty v současné době (s určitou mírou chybovosti) možné generovat automaticky. Podobnost vět je pak možné počítat i na základě nějaké podobnosti grafů (stromů) vět.
Téma projektu je vhodné jako základ pro bakalářskou práci a lze plynule navázat prací diplomovou.
Projekt Enti je studentský softwarový projekt z roku 2001, simulátor přirozeného prostředí lidského světa. Více v dokumentacích projektu (zejména v tzv. Teoretické dokumentaci) nebo v projektu samém: Projekt Enti.
Stránka dalších návrhů kolegy Broma.
Cílem navrhovaného ročníkového projektu ev. bakalářského projektu je reimplementace serveru prostředí v jazyce Mercury, C/C++ nebo Javě. Důraz je kladen na efektivitu, rozšitelnost a konfigurovatelnost.
Strojový ent (viz Programátorská dokumentace), je vybaven pamětí o předmětech, které viděl ap. V paměti pak hledá podle různých kritérií (podle potřeb skriptů). Cílem projektu je reimplementovat paměť tak, aby byla podstatně zvýšena efektivita různých potřebných způsobů hledání v paměti, např. aby paměť podporovala indexování podle různých vlastností předmětů.
Cílem práce je vytvořit nástroj pro bezpečné provádění náhrad podle množiny regulárních výrazů. Nástroj na první pohled bude velmi připomínat schopnosti příkazů pro nahrazování z Perlu nebo sedu, ev. lexikálních analyzátorů typu flex, ale se dvěma významnými odlišnostmi:
Nástroj musí podporovat Unicode (UTF-8). Vítána je platformně nezávislá implementace, postačí však implementace pro OS Linux s řádkovým uživatelským rozhraním.
Důraz je kladen zejména na velmi rychlý běh. Vítána jsou například řešení, kdy nástroj hledání a náhrady zkompiluje do programu v jazyce C/C++, podobně jako pracuje flex. Vytvořený kód C/C++ bude jiný pro ostrý a pro ladicí běh. Podobně práce s Unicodem vyžaduje pečlivou analýzu, s cílem maximálně zrychlit chod. (Konečný automat pro hledání vzorků ve vstupu je třeba determinizovat nejen podle stavů, ale i podle přechodů.)
Jako rozšíření je možné uvažovat o řetězení skupin náhrad, jako kdyby uživatel zapojil více nahrazovačů rourou za sebe, jen v efektivnější implementaci.
Součástí bakalářské práce bude porovnání nově vytvořeného nástroje s nástroji podobnými, a to z hlediska možností použití i z hlediska rychlosti na úlohách stejného typu.
Structsheet je náhradou za spreadsheet (tabulkový procesor, Excel), je určitým zobecněním, ale též určitou specializací. Structsheet je technologie pro přípravu tabulek k prezentování z (dynamických a velkých) dat tabulkové nebo množinové povahy (např. z SQL databází), není přímo cílena na vytváření grafů. O technologii structsheetu slyšíte prvně, protože jsem ji vymyslel a nedostatečně uspokojivě implementoval. Stručný popis technologie structsheetu.
Cílem projektu je implementovat technologii popsanou v návrhu, s rozšířeními dle vlastních představ, s úpravou syntaxe structsheetu dle potřeb. Výsledný program bude kompilátor structsheetu do C/C++, Javy, Mercury, nebo jiného "rychlého" jazyka a výsledné programy budou pracovat nad neomezeně velkými daty (tj. ve vnější paměti).
Cílem projektu je navrhnout a implementovat automatický veršovač textů. Pro daný český text program bude na základě vestavěného slovníku navrhovat mírné proházení slov a volbu synonym, tak aby se text rýmoval podle zvoleného typu rýmu a metra (viz letmý úvod s odkazy).
V úvodní analýze problému je úkolem též zvážit možnost automatické identifikace rýmu a metra ze zadané básně. Bude-li úloha řešitelná, výsledný program by měl podporovat na vstupu místo popisu požadovaného typu verše prostě vzorek básně. (Chci předpověď počasí jako tento Borovského epigram.)
Kromě literatury doporučené v odkazovaném letmém úvodu doporučuji tyto zdroje (a další na požádání):
Při editaci českého textu se často stává, že z důvodu nějaké reformulace potřebujeme změnit vazbu mezi slovesem a jmennou skupinou. (Např. "Výše popsanou stručnou dokumentaci rozšiřuje kniha 2." měníme na "Ve druhé knize najdete vše z výše popsané stručné dokumentace podrobněji rozpracováno.") Po reformulaci je nutné opravit koncovky u každého slova zahrnutého v přesouvané jmenné skupině.
Cílem projektu je navrhnout a implementovat experimentální uživatelské rozhraní a inteligentní automatický korektor pro pohodlnější reformulace textů a eventuelně automatické doplňování koncovek při psaní delších jmenných skupin. Je třeba umět spolehlivě detekovat, kdy uživatel provádí reformulaci, a správně připravit potřebný nový tvar jmenné skupiny. Uživatel pak musí být srozumitelným způsobem informován o navžené možnosti a musí pro něj být snadné návrh přijmout, odmítnout či opravit.
Důraz není kladen na implementaci textového editoru, projekt je možné implementovat jako nadstavbu nad libovolným textovým editorem (včetně [chm] MS Wordu). Implementace by měla být realizována tak, že s textovým editorem pouze spolupracuje pomocí předem dohodnutého rozhraní, aby bylo možné relativně snadno včlenit toto rozšíření do jiného editoru.
Problém slovníku pro skloňování českých slov je vyřešen a stačí použít hotový balík Czech Free Morphology.
Strojový překlad z češtiny do angličtiny je možné relativně úspěšně provádět jednoduchou statistickou metodou, pokud ovšem napřed všechna česká slova převedeme na základní tvary. ("Ema mít maso." "Máma mít mísa.") Redukce textu na základní tvary je nutná s ohledem na zbytečné "ředění" trénovacích dat. (Řečeno velmi nahrubo "cat"="kočka/kočky/kočce/kočku/kočko/kočkou". Bez převedení na základní tvar musí stroj získat slovník se sedminásobným počtem položek, čili při předem daném trénovacím textu uvidí každou překladovou dvojici sedmkrát méně často.)
Chceme-li použít systém statistického překladu na opačný směr, z angličtiny do češtiny, máme v zásadě dvě možnosti: buď budeme pracovat s nevhodně ředěnými daty, nebo necháme systémem vygenerovat nezohýbanou češtinu a slovní tvary na základě kontextu doplníme až dodatečně.
Cílem projektu je implemetovat automatické ohýbání slov na základě kontextu. (Z technického hlediska jde o podobnou úlohu jako doplňování háčků a čárek, různé algoritmy jsou známy.)
Projekt je dobrým základem pro bakalářskou práci (srovnání úspěšností různých metod generování českého textu z anglického originálu) a téma lze jistě rozvinout i do práce diplomové.
Cílem práce je implementovat komplexní nástroj, který na základě zadané dvojice požadovaných jazyků (např. čeština a angličtina) a seznamu zdrojových URL nebo seznamu dvojic URL vytvoří soubor vyčištěných paralelních textů, tzv. paralelní korpus. Paralelním korpusem se rozumí množina dvojic dokumentů, které jsou jeden v jednom a druhý ve druhém jazyce, a které jsou sobě (velmi pravděpodobně) překladem. Pro jednotlivé dvojice dokumentů systém odhadne kvalitu párování a umožní tak požadovat menší, ale spojehlivější paralelní korpus. Pomocí již dostuných navazujících nástrojů bude text dále rozčleněn na slova a věty a budou k sobě přiřazeny paralelní věty.
V implementaci musí být kladen důraz na modularitu systému pro snadné zapojení jazykově závislých externích nástrojů, např. pro rozdělení textu na slova a věty, a zároveň na časové nároky použitých algoritmů, aby bylo možno systém použít ke sběru velkého množství dat. Použitelnost nástroje bude doložena sběrem česko-anglického paralelního korpusu pro vybranou doménu, např. doménu cestovního ruchu (ubytování, doprava, ap.).
Volitelně je možné obohatit systém o automatické dohledávání zdrojových URL na základě malého vzorku požadovaného typu korpusu. Toto rozšíření využije vyhledávacích serverů jako Google k identifikaci kandidátských URL.
Práci je možné spojit s ročníkovým projektem a téma je dobrým základem pro případnou navazující diplomovou práci.
(a další odkazovaná literatura). Uvedené práce rád poskytnu, kontaktujte mne mailem: bojar zav. ufal.mff.cuni.cz.
Mercury je programovací jazyk syntakticky podobný Prologu, ale s statickou typovou kontrolou, funkcionálními rysy. Kompilátor Mercury generuje C a to je dále kompilováno běžným gcc (jiné backendy jsou i assembler, Java a kdysi to vypadalo i na .NET). Stručný úvod jsem kdysi napsal v seriálu na serveru Root.cz.
Cílem projektu je implementovat generátor serializujícího a deserializujícího kódu. Pro daný uživatelem definovaný datový typ (např.: strom prvků typu P je buď "nil", nebo "trojice levý podstrom, prvek typu P, pravý podstrom") generátor připraví kód v Mercury, který načítá strom ze souboru nebo z řetězce (deserializace), a kód, který daný strom vypisuje (serializace).
Důraz je kladen na kompaktnost zápisu datové struktury a rychlost čtení i psaní a schopnost pracovat s velmi rozsáhlými datovými strukturami. Žádoucí je zavést vlastní binární formát, který nemusí být přenositelný mezi platformami nebo různými verzemi Mercury. Binární formát bude rovněž jiný, jakmile se byť malinko změní definice ukládaného datového typu. (De)serializace je určena pro případy, kdy program potřebuje komunikovat sám se sebou.
Generátor musí umožňovat pohodlné dodání vlastních (de)serializujících predikátů pro datové typy, které si uživatel raději (de)serializuje sám.
V první verzi není třeba řešit "structure sharing", tj. případy, kdy jsou dvě části hlouběji v datové struktuře identické. První verze může takové části načítat tolikrát, kolikrát jsou ve struktuře použity. Zda sdílené struktury bude program vůbec ošetřovat, je předmětem další diskuse. Cyklické struktury jsou z definice datových typů v Mercury vyloučeny.
Ročníkový projekt bude možné rozšířit do bakalářské práce. Ta by měla navíc řešit mírnou optimalizaci čtecích a zapisovacích predikátů podle předložených ukázkových zapisovaných datových struktur. (V podstatě stačí spočítat, zda strom je častěji ten "nil" nebo ta "trojice" a nejprve testovat častější variantu.)
Pro efektivní ladění a testování algoritmů strojového překladu je nezbytné mít k dispozici velmi rychlou a spolehlivou automatickou metodu meření "kvality" překladu. Většinou "kvalitou" rozumíme nějakou podobnost k překladu, který vyrobili lidé. Řada konkrétních automatických metrik kvality překladu již byla navržena (zejména BLEU, NIST, Word-Error-Rate ad.) a existují standardní implementace.
Cílem projektu je implementovat standardní metriky velmi efektivně (C/C++/Java) a doplnit další informace o překladu, zejména odhad rozptylu zjištěných hodnot a přehledné výpisy úseků textu, které překladu "nejvíce ubližují" (měřeno danou metrikou).
Ročníkový projekt představuje velmi dobrý základ pro navazující bakalářskou práci a v tématu lze jistě pokračovat i v rámci diplomové práce (např. navržení vlastních úprav a nebo zcela nových způsobů měření kvality překladu.)
Restartovací automaty jsou speciálním typem automatů (jako např. konečné automaty či Turingovy stroje) s vyjadřovací silou na rozhraní bezkontextových a kontextových gramatik. Restartovací automaty byly navrženy jako nástroj pro syntaktickou analýzu (přirozených) jazyků s volným slovosledem, jako je např. čeština.
Podrobný přehled o motivaci i základních vlastnostech restartovacích automatů dává článek Jančar P., Mráz F., Plátek M., Vogel J.: On Monotonic Automata with a Restart Operation (ps).
Cílem projektu je implementovat prostředí pro simulaci restartovacích automatů různé síly. Grafické uživatelské rozhraní nebo grafická simulace chodu automatu v žádném případě není součástí projektu. Důraz je naopak kladen na efektivní a rozšiřitelnou implementaci. (Musí být možné snadno přikompilovat vlastní reprezentaci symbolů jazyka. Simulátor by měl být navržen tak, aby jeho chod byl efektivní i v případě velmi rozsáhlých automatů o stovkách tisíc stavů.)