Logic circuits as models of computation

• Název práce v češtině: Logické obvody jako výpočetní modely
• Název v anglickém jazyce: Logic circuits as models of computation
• Klíčová slova: logické obvody, výpočetní složitost, algoritmy, booleovské funkce
• Klíčová slova anglicky: logical circuits, computational complexity, algorithms, Boolean functions
• Akademický rok vypsání: 2019/2020
• Typ práce: bakalářská práce
• Jazyk práce: angličtina
• Ústav: Katedra algebry (32-KA)
• Vedoucí / školitel: RNDr. Alexandr Kazda, Ph.D.
• Řešitel: skrytý - zadáno a potvrzeno stud. odd.
• Datum přihlášení: 11.10.2019
• Datum zadání: 30.10.2019
• Datum potvrzení stud. oddělením: 21.11.2019
• Datum a čas obhajoby: 08.09.2020 10:00
• Datum odevzdání elektronické podoby: 29.07.2020
• Datum odevzdání tištěné podoby: 29.07.2020
• Datum proběhlé obhajoby: 08.09.2020
• Oponenti: Michael Kompatscher, Ph.D.

Zásady pro vypracování

Student pochopí a vlastními slovy vysvětlí obsah kapitoly 2 ("Logic Circuits") a vybraných částí kapitoly 9 ("Circuit Complexity") knihy John E. Savage: "Models Of Computation," dále samostatně vyřeší netriviální množství cvičení z těchto kapitol.

Seznam odborné literatury

John E. Savage. "Models Of Computation: Exploring the Power of Computing." elektronická edice http://cs.brown.edu/people/jsavage/book/

Sanjeev Arora, Boaz Barak. "Computational Complexity: A Modern Approach." Cambridge University Press, 2009.

Předběžná náplň práce

Programovat v Pascalu nebo Pythonu umí každý... V téhle práci se naučíte, jak naplánovat výpočet pomocí logických obvodů. Logický obvod sestává z navzájem propojených bran a každá brána provádí nějakou jednoduchou binární operaci; abstraktní obovod tak modeluje reálné elektronické součástky a zároveň umožňuje matematicky zkoumat výpočetní složitost různých operací.

Předběžná náplň práce v anglickém jazyce

Anybody can write code in Pascal or Python... We are going to learn how to do computation using logical circuits. A logical circuit consists of an interconnected network of gates with each gate performing a simple Boolean operation. In this way, logical circuits model real circuits in electronics, while allowing us to study the computational complexity of various operations.