| Meno: | Jakub
|
|---|
| Priezvisko: | Husár
|
|---|
| Názov: | Niektoré metrické vlastnosti čiastočných náhodných booleovských funkcií
|
|---|
| Vedúci: | doc. RNDr. Eduard Toman, CSc.
|
|---|
| Rok: | 2013
|
|---|
| Blok: | INF
|
|---|
| Kľúčové slová: | čiastočná náhodná boolovská funkcia, jadrové hrany, regulárne vrcholy, Quinova DNF, DNF typu suma T
|
|---|
| Abstrakt: | V našej práci sa zaoberáme štúdiom niektorých merických vlastností čiastočných náhodných booleovských funkcií.
Prezentujeme v nej a dokazujeme tvrdenia o asymptotických odhadoch počtu jadrových hrán a regulárnych vrcholov obsiahnutých v grafoch, ktoré sú geometrickou reprezentáciou týchto funkcií. Na základe týchto výpočtov odhadujeme zložitosť Quinovej DNF a DNF typu suma T. Tieto výsledky porovnávame so známymi zisteniami o zložitosti skrátenej DNF.
|
|---|