Meno:Peter
Priezvisko:Koscelanský
Názov:Neuniformné výpočtové modely - branching programy a rozhodovacie stromy
Vedúci:RNDr. Andrej Bebják
Rok:2009
Kľúčové slová:branching programy, neuniformné výpočtové modely, dolné odhady zložitosti, natural proofs
Abstrakt:V práci sa zaoberáme neuniformnými výpočtovými modelmi, s dôrazom na branching programy, využívané hlavne na reprezentáciu postupností booleovských funkcií, skúmanie ich vlastností a výpočtovej zložitosti. Analyzujeme najvýznamnejšie výsledky z oblasti zložitosti branching programov, študujeme vplyv rôznych ohraničení na základný model. Pre explicitne definované postupnosti funkcií sa získavanie netriviálnych dolných odhadov považuje za ťažký problém. Prezentované náročné techniky na získavanie dolných odhadov sú aplikované na konkrétne postupnosti funkcií a jazykov. Na príkladoch ilustrujeme limity použiteľnosti a hranice kvality dolných odhadov dokázateľných jednotlivými technikami. Zjednocujúci pohľad na doteraz známe techniky a koncept bariér, ktoré treba prekonať, naznačuje smerovanie v študovanej oblasti.

Súbory bakalárskej práce:

BC_2009_PK.pdf