Název: Knihovna pro binární rozhodovací diagramy
Překlad názvu: A Library for Binary Decision Diagrams
Autoři: Paulovčák, Martin ; Holík, Lukáš (oponent) ; Lengál, Ondřej (vedoucí práce)
Typ dokumentu: Bakalářské práce
Rok: 2020
Jazyk: slo
Nakladatel: Vysoké učení technické v Brně. Fakulta informačních technologií
Abstrakt: [slo] [eng]
Cieľom tejto práce je vytvoriť jednoducho použiteľnú knižnicu, ktorá bude poskytovať základné prostriedky pre manipuláciu booleovských funckií prostredníctvom šiestich rôznych variánt binárnych rozhodovacích diagramov - BDD, ZDD, CBDD, CZDD, TBDD a ESRBDD. Knižnica je implementovaná v ISO C, používa zatvorené hashovanie, referencovanie uzlov založené na indexoch, garbage collector na princípe mark and sweep algoritmu a vytváranie diagramov založené na depth-first prechode. Implementované varianty týchto diagramov boli porovnané na benchmarkoch a hoci optimálna voľba varianty závisí na riešenom probléme, vo všeobecnosti sa ako najlepšia voľba z pohľadu veľkosti výsledného grafu a zároveň CPU času ukázali TBDD. The aim of this thesis is to create an easy-to-use library that will provide the basic means for Boolean function manipulation based on six different variants of Binary Decision Diagrams - BDD, ZDD, CBDD, CZDD, TBDD, and ESRBDD. The library is implemented in the ISO C programming language, uses closed hashing, index-based node referencing, mark and sweep based garbage collector and diagram construction is based on classical depth-first traversal. The implemented variants of these diagrams were compared on benchmarks and although the optimal choice of decision diagram variant depends on given problem, in general TBDD proved to be the best choice in terms of the resulting graph size and also CPU time.
Klíčová slova: BDD; binary decision diagrams; boolean functions; CBDD; CZDD; ESRBDD; ROBDD; TBDD; ZDD

Instituce: Vysoké učení technické v Brně (web)
Informace o dostupnosti dokumentu: Plný text je dostupný v Digitální knihovně VUT.
Původní záznam: http://hdl.handle.net/11012/191672

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


Záznam je zařazen do těchto sbírek:
Školství > Veřejné vysoké školy > Vysoké učení technické v Brně
Vysokoškolské kvalifikační práce > Bakalářské práce