Meno:Lukáš
Priezvisko:Ivan
Názov:Predpovedanie času riešenia pre ťažké logické úlohy
Vedúci:RNDr. Michal Forišek, PhD.
Rok:2019
Blok:INF
Kľúčové slová:analýza stavového grafu, predpovedanie času, Rush Hour, významné vlastnosti, strojové učenie, zber dát
Abstrakt:Cieľom práce je skúmanie spôsobu, akým ľudia riešia konkrétne výpočtovo ťažké logické úlohy a analýza ako syntaktické vlastnosti inštancií problémov ovplyvňujú obtiažnosť danej inštancie. Riešenie problematiky má základ v analýze stavového grafu vytvoreného z konkrétnych inštancií problému. V práci sa zaoberáme logickou úlohou Rush Hour patriacou do množiny PSPACE-úplných problémov, pre ktorú sme vytvorili webový portál na zber reálnych dát z riešenia úloh ľudským riešiteľom. Na účely analýzy stavových grafov sme vytvorili program na vykresľovanie a manipuláciu 3D grafov stavového priestoru. Zahŕňa aj grafy stavového priestoru vážené dátami z portálu, návštevami a časom pobytu riešiteľov v grafových prvkoch. Na predpovedanie času riešenia sme dáta z portálu spolu s externými dátami ďalej analyzovali pomocou modelov strojového učenia. Pre zjednodušenie predikcie obtiažnosti sme vybrali len niektoré vlastnosti stavového priestoru. Metódou prehľadávania mriežky sme získali najlepšie modely a následne sme urobili extrakciu najvýznamnejších vlastností pomocou metódy rekurzívneho eliminovania vlastností. Výsledkom práce je prediktor obtiažnosti Rush Hour a identifikované významné vlastnosti, čo je možné v praxi použiť na automatické generovanie primerane obtiažnych inštancií problému.

Súbory diplomovej práce:

appendix.zip
predpovedanie_casu_riesenia_pre_tazke_logicke_ulohy.pdf