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