Název: Třídy Booleovských funkcí umožňující efektivní hledání minimálních reprezentací.
Překlad názvu: Třídy Booleovských funkcí umožňující efektivní hledání minimálních reprezentací.
Autoři: Kuřík, Stanislav ; Gregor, Petr (oponent) ; Čepek, Ondřej (vedoucí práce)
Typ dokumentu: Diplomové práce
Rok: 2010
Jazyk: eng
Abstrakt: [eng] [cze]
This thesis deals with the Boolean minimization problem. We discuss its time complexity in the general case for various representations of the input. Since this problem is known to be NP-complete, a survey of some of important classes for which it is polynomially solvable follows. The main part of this thesis presents a definition of a new class of Boolean functions, along with an algorithm for finding a minimal representation of a given function from this class in polynomial time. Finally, a generalization of this class is obtained and its minimization-related properties are discussed. Tématem práce je problém minimalizace Booleovských funkcí. Rozebírá složitost minimalizace v obecném případě pro různé vstupní reprezentace a protože ve všech zde uvažovaných případech jde o NP-úplný problém, následuje přehled několika důležitých tříd funkcí, pro něž je řešitelný efektivně. Těžištěm práce je difinice nové třídy Booleovských funkcí spolu s prezentací algoritmu, který pro funkce této třídy nalezne minimální reprezentaci v polynomiálním čase. Nakonec je diskováno zobecnění této třídy a jeho vlastnosti vzhledem k minimalizaci.

Instituce: Fakulty UK (VŠKP) (web)
Informace o dostupnosti dokumentu: Dostupné v digitálním repozitáři UK.
Původní záznam: http://hdl.handle.net/20.500.11956/26940

Trvalý odkaz NUŠL: http://www.nusl.cz/ntk/nusl-282033


Záznam je zařazen do těchto sbírek:
Školství > Veřejné vysoké školy > Univerzita Karlova > Fakulty UK (VŠKP)
Vysokoškolské kvalifikační práce > Diplomové práce