Meno:Lenka
Priezvisko:Trojaková
Názov:Štúdium niektorých vlastností náhodne indukovaných podgrafov n-rozmernej hyperkocky
Vedúci:doc. RNDr. Eduard Toman, CSc.
Rok:2011
Blok:INF
Kľúčové slová:Náhodné grafy, prahové funkcie, jadrová podkocka, regulárny vrchol, iredundantná disjunktívna normálna forma.
Abstrakt:Boolovské funkcie majú veľa praktických využití. Ako príklad spomenieme ich súvis s kryptografiou, symetrickou šifrou, či navrhovaním obvodov a čipov pre výpočtovú techniku. Problém zjednodušenia boolovských funkcií sa dá previesť na problém vrcholového pokrytia podgrafu hyperkocky menšími hyperkockami. Keďže tento problém je NP-úplný, jeden z možných prístupov k jeho riešeniu je zmenšovanie množiny vrcholov, ktoré treba pokryť. Tu sa dostávame k pojmom regulárny vrchol a jadrová podkocka. Nakoľko sa zaoberáme náhodnými funkciami, venujeme sa v práci aj základným charakteristikám niektorých náhodných premenných súvisiacich s jadrovými podkockami. Zaoberáme sa strednou hodnotou počtu jadrových podkociek v náhodnom grafe a odhadujeme disperziu počtu takýchto podkociek. Zaujímavá je aj otázka počtu iredundantných disjunktívnych normálnych foriem pre náhodnú booleovskú funkciu. Odpoveď na ňu úzko súvisí s pokrývaním náhodného podgrafu hyperkocky maximálnymi podkockami. V práci poskytujeme horný a dolný odhad počtu týchto foriem, ktoré získavame na základe výsledkov niekoľkých autorov, ktorí sa venovali tematike náhodne indukovaných podgrafov hyperkocky.

Súbory diplomovej práce:

trojakova.pdf