Thesis Details

Knihovna pro binární rozhodovací diagramy

Bachelor's Thesis Student: Paulovčák Martin Academic Year: 2019/2020 Supervisor: Lengál Ondřej, Ing., Ph.D.
Language
Slovak
Abstract

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.

Keywords

binary decision diagrams, boolean functions, ROBDD, BDD, ZDD, CBDD, CZDD, TBDD, ESRBDD

Department
Department of Intelligent Systems FIT BUT
Degree Programme
Information Technology
Files
Status
defended, grade A
Date
9 July 2020
Reviewer
Holík Lukáš, doc. Mgr., Ph.D.
Committee
Rogalewicz Adam, doc. Mgr., Ph.D. (DITS FIT BUT), předseda
Burgetová Ivana, Ing., Ph.D. (DIFS FIT BUT), člen
Grézl František, Ing., Ph.D. (DCGM FIT BUT), člen
Smrčka Aleš, Ing., Ph.D. (DITS FIT BUT), člen
Vašíček Zdeněk, doc. Ing., Ph.D. (DCSY FIT BUT), člen
Citation
PAULOVČÁK, Martin. Knihovna pro binární rozhodovací diagramy. Brno, 2020. Bachelor's Thesis. Brno University of Technology, Faculty of Information Technology. 2020-07-09. Supervised by Lengál Ondřej. Available from: https://www.fit.vut.cz/study/thesis/22985/
BibTeX 
@bachelorsthesis{FITBT22985,
    author = "Martin Paulov\v{c}\'{a}k",
    type = "Bachelor's thesis",
    title = "Knihovna pro bin\'{a}rn\'{i} rozhodovac\'{i} diagramy",
    school = "Brno University of Technology, Faculty of Information Technology",
    year = 2020,
    location = "Brno, CZ",
    language = "slovak",
    url = "https://www.fit.vut.cz/study/thesis/22985/"
}

Theses

Back to top