Original title: Logické obvody jako výpočetní modely
Translated title: Logic circuits as models of computation
Authors: Naumenko, Mykhailo ; Kazda, Alexandr (advisor) ; Kompatscher, Michael (referee)
Document type: Bachelor's theses
Year: 2020
Language: eng
Abstract: [eng] [cze]
This work focuses on the study of logic circuits. We investigated the basics of the theory of logic circuits following the textbook "Models of Computation" by John E. Savage and we used this knowledge to solve some of the examples and problems suggested in the textbook. In this work, you can find key concepts related to logical circuits. Our main topic is the estimation of the lower bounds of the circuit size and formula size of general Boolean function. We constructed simple examples of some known circuits and showed how the circuit designs may be offered. 1 Tato práce se zaměřuje na studium logických obvodů. Vykládáme v ní teorii logických obvodů podle učebnice "Models of Computation" od Johna E. Savage a řešíme některé úlohy a cvičení z této učebnice. V této práci najdete klíčové pojmy související s logickými obvody. Věnovali jsme znač- nou pozornost hlavně odhadům dolních mezí velikostí obvodů a velikostí formulí obecných booleovských funkcí. Sestrojili jsme také několik jednoduchých příkladů známých obvodů a ukázali jsme, jak lze navrhnout další obvody. 1
Keywords: algorithms; Boolean functions; computational complexity; logical circuits; algoritmy; booleovské funkce; logické obvody; výpočetní složitost

Institution: Charles University Faculties (theses) (web)
Document availability information: Available in the Charles University Digital Repository.
Original record: http://hdl.handle.net/20.500.11956/120675

Permalink: http://www.nusl.cz/ntk/nusl-434648


The record appears in these collections:
Universities and colleges > Public universities > Charles University > Charles University Faculties (theses)
Academic theses (ETDs) > Bachelor's theses