|
Lecturer(s)
|
-
Kadavý Tomáš, Ing.
-
Šenkeřík Roman, prof. Ing. Ph.D.
|
|
Course content
|
- Introduction to algorithms. - Computational complexity, the definition of computational complexity, time and spatial computational complexity, asymptotic classes. - The computational problem, P-complexity, complexity classes. - Languages and grammar. - Regular expressions. - Finite automata (FA), FA with one and two stacks, Transition graphs, Kleen's theorem, Moore's equivalence theorem. - Turing machines (TM). Definition of TM and language receiving by TM. - Modification of TM, the problem of decidability and undecidability, the problem of stopping of TM, nondeterministic TM. - Post machines, Finite machines with stacks, RASP machines, the equivalence of automatas, and machines. - Predicate calculus, syntax, and semantics. - Verification of programs and correctness, partial and total correctness, - Program schemes, and their formalization, syntax and interpretation, properties of programs and program schemes, Fixed points of programs, Recursive programs. - Introduction to graph theory.
|
|
Learning activities and teaching methods
|
|
Lecturing, Exercises on PC
|
| prerequisite |
|---|
| Knowledge |
|---|
| Knowledge from areas: Mathematics Fundamentals of Informatics Programming |
| Knowledge from areas: Mathematics Fundamentals of Informatics Programming |
| learning outcomes |
|---|
| The student can define basic types of algorithms and explain concepts of computational complexity, including time and space complexity, and asymptotic classes. |
| The student can define basic types of algorithms and explain concepts of computational complexity, including time and space complexity, and asymptotic classes. |
| The student can describe and analyze various computational models, such as Turing machines, Post machines, and finite automata, and their significance in theoretical computer science. |
| The student can describe and analyze various computational models, such as Turing machines, Post machines, and finite automata, and their significance in theoretical computer science. |
| The student is able to delineate and distinguish between different types of languages and grammars, including regular expressions and their applications. |
| The student is able to delineate and distinguish between different types of languages and grammars, including regular expressions and their applications. |
| The student is capable of clarifying the basic principles of predicate calculus, including its syntax and semantics. |
| The student is capable of clarifying the basic principles of predicate calculus, including its syntax and semantics. |
| The student can analyze program schemata and methodologies for program verification to ensure their correctness. |
| The student can analyze program schemata and methodologies for program verification to ensure their correctness. |
| Skills |
|---|
| The student can design and create efficient algorithms considering time and space complexity. |
| The student can design and create efficient algorithms considering time and space complexity. |
| The student is able to implement and simulate various computational models, such as Turing machines and finite automata, for solving specific problems. |
| The student is able to implement and simulate various computational models, such as Turing machines and finite automata, for solving specific problems. |
| The student uses regular expressions for analyzing and processing text data and can analyze the structure of languages. |
| The student uses regular expressions for analyzing and processing text data and can analyze the structure of languages. |
| The student applies principles of predicate calculus to solve specific logical and mathematical problems. |
| The student applies principles of predicate calculus to solve specific logical and mathematical problems. |
| The student can perform program verification and suggest improvements to increase their efficiency and reliability. |
| The student can perform program verification and suggest improvements to increase their efficiency and reliability. |
| teaching methods |
|---|
| Knowledge |
|---|
| Lecturing |
| Lecturing |
| Exercises on PC |
| Exercises on PC |
| assessment methods |
|---|
| Written examination |
| Written examination |
|
Recommended literature
|
-
Demel J. Grafy a jejich aplikace. Academia, 2002.
-
Eric C.R. Hehner, A. Practical Theory of Programming. Springer, 1993.
-
Koubková A., Pavelka J. Uvod do teoretické informatiky. Matfyzpress, 2003.
-
Linz, Peter. An introduction to formal languages and automata. 4th ed. Sudbury, Mass. : Jones and Bartlett Publishers, 2006. ISBN 0-7637-3798-4.
-
Manna Z. Matematická teorie programů. SNTL, 1981.
-
Martin J.C. Introduction to Languages and the Theory of Computation. 2002. ISBN 0-072-32200-4.
-
Vaníček J., Papík M., Pregl R., Vaníček T. Teoretické základy informatiky. Alfa Publishing, 2006.
|