Ročníkové projekty a práce

---

Hlavní stránka

Zde naleznete mnou nabízená témata na ročníkové projekty a bakalářské, diplomové a disertační práce. Uvedená témata jsou pouze pro ilustraci, máte-li o nějaké z nich zájem, tak mě, prosím, kontaktujte e-mailem (balko (AT) kam.mff.cuni.cz) a můžeme se osobně domluvit na podrobnostech. Můžete přijít i s vlastním návrhem na projekt či práci. Rád jej povedu, bude-li zajímavý a budu-li se v daném tématu dostatečně orientovat. Před přihlášením k projektu či práci je třeba se se mnou osobně domluvit.

Nabízená témata:	nahoru

• Masivně paralelní řešič her
  • Cílem by bylo navázat na úspěšný projekt, jehož výsledkem (publikovaným na A* konferenci AAAI'26) je nejrychlejší známý řešič SPOTS pro hru Sprouts, který je zhruba 10 000krát rychlejší než předešlé programy. SPOTS v principu funguje na jakékoli kombinatorické hře a je založený na nové paralelní verzi PNS-PDFPN algoritmu Proof Number Search, která jako první dobře škáluje i na stovkách CPU jader. Cílem projektu by bylo řešič SPOTS rozšířit i na jiné hry než je Sprouts a spočítat v nich nové rekordy, které by se následně daly publikovat. Případně se pokusit některé hry úplně vyřešit. Na projektu by jako konzultant pomáhal Tomáš Čížek, hlavní autor SPOTS. V případě rozšíření na bakalářskou nebo diplomovou práci je možné zkusit vylepšit i samotný algoritmus PNS-PDFPN metodami strojového učení.

Dokončené projekty:	nahoru

• Počítačové důkazy – výpočty uspořádaných Ramseyových čísel
  • Ročníkový projekt + bakalářská práce (Marian Poljak). Obhájeno 2019/2020, ohodnoceno cenou rektora za nejlepší bakalářskou práci.
  • Cílem projektu je navrhnout program k odhadování a k přesnému výpočtu Ramseyovských čísel uspořádaných grafů s vizualizacemi optimálních obarvení. Program by mohl využívat dostupné SAT solvery s ověřovači a případně i známé metaheuristiky jako je například simulované žíhání. Na projekt by ideálně mohla navazovat teoretičtější práce, provedené výpočty by případně mohly potvrdit či vyvrátit některé z domněnek v dané oblasti.

• Počítačové důkazy – průsečíková čísla a editor grafových nakreslení
  • Ročníkový projekt + bakalářská práce (Filip Čermák). Obhájeno 2020/2021.
  • Jedním z cílů projektu by bylo vytvořit program, který by umožňoval kreslení grafů s danými podmínkami (úsečková nakreslení, nakreslení x-monotónními křivkami, atd.) a dynamické změny v daných nakresleních (změny pozic vrcholů, přetahování hran a podobně). Jinou (či další) možností je pojmout tento projekt jako řešení různých extremálních problémů nad grafovými nakresleními (například odhadování jistých variant průsečíkových čísel či odhady pro různá tvrzení Ramseyova typu) pomocí počítače a případně jej rozšířit na práci teoretičtějšího charakteru.

• Implementace kombinatorických her
  • Ročníkový projekt + bakalářská práce (Tomáš Čížek). Obhájeno 2020/2021, ohodnoceno cenou děkana za nejlepší bakalářskou práci a Cenou Jiřího Matouška.
  • Cílem je implementovat danou kombinatorickou hru více hráčů, nastudovat známé herní mechanismy, optimální strategie a heuristiky a navrhnout umělou inteligenci protivníka. Samotná hra by ideálně mohla být pěkně graficky vyvedená a je vhodné pokusit se danou hru v různých směrech zobecnit a studovat herní mechanismy nad nově vzniklými situacemi. V úvahu připadají například hry Gomoku, Sprouts a jiné. Spousta her se dá nalézt v knize Winning Ways for your Mathematical Plays (Berlekamp, Conway, Guy). Možností je naprogramovat různé implementace umělé inteligence protivníka a porovnat je nad vybranou hrou.