Mathematical Principles of Computer Science (FSI-VZI-A)

Academic year 2025/2026
Supervisor: doc. Ing. Jakub Kůdela, Ph.D.  
Supervising institute: ÚAI all courses guaranted by this institute
Teaching language: English
Aims of the course unit:
 
Learning outcomes and competences:
 
Prerequisites:
 
Course contents:
 
Teaching methods and criteria:
 
Assesment methods and criteria linked to learning outcomes:
 
Controlled participation in lessons:
 
Type of course unit:
    Lecture  13 × 3 hrs. optionally                  
    Computer-assisted exercise  13 × 2 hrs. compulsory                  
Course curriculum:
    Lecture 1. Introduction.
2. The list, queue, stack structures, designs of representation and implementation.
3. Breadth-first and depth-first search of graph, combined search; the use of queue and stack. AND/OR graphs.
4. Eulerian trails, Hamiltonian paths.
5. The shortest path, minimum spanning tree.
6. Network flows, graph colouring.
7. Voronoi diagrams and Delaunay triangulation.
8. Formal languages and grammars. Chomsky’s classification.
8. Regular grammars and finite automata.
9. Finite automata without stack, representation.
10. Context-free grammars and finite automata with stack.
11. Turing machine, enumeratibility, algorithm complexity.
12. Sorting algorithms
13. Recapitulation.
    Computer-assisted exercise 1. Principles of code security improvement, separation of overhead and data classes.
2. Implementation of list.
3. Implementation of queue and stack.
4. Implementation of tree.
5. Implementation of general oriented graph, search in graph I.
6. Implementation of general oriented graph, search in graph II.
7. Approaches to implementation of graph evaluation.
8. Searching in special graph topologies; examples of use.
9. Solution designs of simple problems realized through search in oriented evaluated graph.
10. Object implementation of finite automaton without stack.
11. Object implementation of finite automaton with stack.
12. Linguistic variable implementation, if-then operation.
13. Accreditation.
Literature - fundamental:
1. Greenshaw, R. and Hoover, H.J.: Fundamentals of the Theory of Computation Principle and Practice. Morgan Kaufmann, 1998.
2. Jungnickel, D: Graphs, networks and algorithms, 4th edition. Springer Berlin, Heidelberg, 2013.
3. Meduna, A., Švec, M.: Grammars with context conditions and their applications. Wiley, 2005.
4. Sipser, M.: Introduction to the Theory of Computation, 3rd edition. Cengage Learning, 2013.
Literature - recommended:
1. Meduna, A.: Formal Languages and Computation. New York, Taylor & Francis, 2014.
2. Brookshear, J.G. : Theory of Computation: Formal Languages, Automata, and Complexity, The Benjamin/Cummings Publishing Company, Inc, Redwood City, California, 1989.
The study programmes with the given course:
Programme Study form Branch Spec. Final classification   Course-unit credits     Obligation     Level     Year     Semester  
N-ENG-Z visiting student --- no specialisation -- Cr,Ex 6 Recommended course 2 1 W