Course detail

Mathematical Principles of Computer Science

FSI-VZI-A Acad. year: 2027/2028 Winter semester

The course provides an introduction to the mathematical and theoretical foundations of computer science, focusing on formal models of computation, computability, computational complexity, and algorithm design. It aims to establish a systematic understanding of the capabilities and limitations of computational methods and the principles underlying the selection of appropriate algorithms for computer science and engineering problems.

The first part covers formal languages and automata theory, including deterministic and nondeterministic finite automata, regular languages, regular expressions, context-free grammars, pushdown automata, and Turing machines. These models are used to introduce fundamental concepts of computation, decidability, and undecidability. The course then addresses the analysis of algorithmic time complexity and the classification of computational problems, particularly the complexity classes P and NP.

The second part focuses on the design and analysis of classical algorithms. Topics include graph traversal, shortest-path algorithms, minimum spanning trees, matching and maximum-flow algorithms, and selected problems solved using greedy algorithms and dynamic programming. Practical examples illustrate algorithm correctness, computational complexity, and the suitability of different solution approaches.

The course combines mathematical models and theoretical results with practical implementations in Python. Computer-assisted exercises involve constructing and testing selected automata and algorithms, analyzing their behavior, and interpreting computational results.

Language of instruction

English

Number of ECTS credits

6

Entry knowledge

Students are expected to have a basic understanding of algorithms and structured programming, including variables, data types, conditional statements, loops, functions, and fundamental data structures.

They should be able to independently design and implement a simple algorithm in Python or a comparable programming language, execute the program, and verify its correctness using selected test inputs.

Basic familiarity with set theory, mathematical logic, functions, and relations is expected. 

Rules for evaluation and completion of the course

Course-unit credit: Active participation in the seminars, elaboration of a given project. Examination: Written and oral.
Attendance at lectures and seminars is required. An absence can be compensated for via solving additional problems.

Aims

Upon successful completion of the course, students will be able to:

  1. Formally describe, construct, and analyze deterministic and nondeterministic finite automata, determine the languages they recognize, and apply relationships between finite automata, regular languages, and regular expressions to selected problems.

  2. Construct and apply context-free grammars and pushdown automata to describe simple formal languages, perform basic syntactic analysis, and explain differences in the expressive power of selected formal models.

  3. Describe and simulate computations using Turing machines, distinguish between decidable and undecidable problems, and use examples to justify fundamental limitations of algorithmic computation.

  4. Analyze and compare the time complexity of selected algorithms using asymptotic notation, distinguish the fundamental characteristics of the complexity classes P and NP, and explain relationships between problem properties and computational requirements.

  5. Design, implement, and justify the correctness of selected algorithms for graph and combinatorial problems using graph traversal, greedy techniques, dynamic programming, and network algorithms.

  6. Test and experimentally evaluate implementations of selected formal models and algorithms in Python, design appropriate test cases, compare computational requirements, and assess the suitability of different solution approaches.

Study aids

To support their studies, students are provided with materials for lectures and computer exercises. These materials are made available via the university's e-learning environment.

The study programmes with the given course

Programme N-AIŘ-P: Applied Computer Science and Control, Master's, compulsory

Type of course unit

 

Lecture

39 hours, compulsory

Syllabus

1. Deterministic finite automata.
2. Nondeterministic finite automata.
3. Regular languages.
4. Context-free grammars.
5. Turing machines.
6. Decidability.
7. Time complexity, class P.
8. Class NP.
9. Algorithms for problems: Stable matching, Graph connectivity, Topological ordering.
10. Algorithms for problems: Interval scheduling, Shortest paths, Minimum spanning tree.
11. Algorithms for problems: Huffman coding, Weighted interval scheduling, Knapsack problem.
12. Algorithms for problems: Sequence alignment, Maximum flow, Bipartite matching.
13. Summary of the material covered.

Computer-assisted exercise

26 hours, compulsory

Syllabus

The exercises build upon the material covered in the lectures by providing practical demonstrations of the issues in question.

1. Deterministic finite automata – simple lock problem.
2. Nondeterministic finite automata – gesture recognition.
3. Regular languages – event logs.
4. Context-free grammars – parsing a small robot language.
5. Push-down automata – call logs.
6. Turing machine simulator.
7. Halting in a tiny bytecode language.
8. Sorting algorithms and running time.
9. Graph search and complete tours.
10. Algorithms for problems: Stable matching, Graph connectivity, Topological ordering.
11. Algorithms for problems: Interval scheduling, Shortest paths, Minimum spanning tree.
12. Algorithms for problems: Huffman coding, Weighted interval scheduling, Knapsack problem.
13. Algorithms for problems: Sequence alignment, Maximum flow, Bipartite matching.