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