Meno:Peter
Priezvisko:Herman
Názov:Výskum online problémov z hľadiska advice complexity
Vedúci:RNDr. Michal Forišek, Phd.
Rok:2013
Blok:INF
Kľúčové slová:poradná zložitosť, online farbenie grafov, alokovanie disjunktných ciest, primitívna rekurzia s radou
Abstrakt:Práca sa zaoberá online problémami z hľadiska advice complexity - teda minimálneho množstva informácie, ktoré musí byť poskytnuté orákulom pre dosiahnutie určitého aproximačného pomeru, respektíve optimality. Venovali sme sa farbeniu grafov, konkrétne farbeniu všeobecných grafov prehľadávaných do hĺbky a grafov vnoriteľných do mriežky. Ďalej sme navrhli nový model pre advice complexity, ktorý umožňuje meniť rýchlosť, ktorou je rada čítaná, a analyzovali jeho správanie na problémoch alokovania disjunktných ciest a pri hľadaní maximálnej súvislej podpostupnosti. Navyše sme sa pokúsili zakomponovať radu do rekurzívnych funkcií, a to konkrétne návrhom triedy primitívnej rekurzie s radou.

Súbory diplomovej práce:

main.pdf