Course detail

Mathematical Principles of Computer Science

FSI-VZIAcad. year: 2023/2024

The course provides students with the introduction to mathematical computer science. Formal languages and grammars and word processing tools in these languages are discussed.
The course completes predicate calculus, methods of proving the truth of logical formulas and classification of complexity problems with the definition of classes P and NP.
C/Python is used as an implementation tool. Practical use of theorems and consequents is demonstrated on the implementation of simple technical applications.
The course completes fundaments of graph theory, they cover graph search, Eulerian trails, Hamiltonian paths, shortest paths, minimum spanning trees, network flows, graph colouring and applications of computational geometry structures.

Language of instruction

Czech

Number of ECTS credits

6

Mode of study

Not applicable.

Guarantor

prof. RNDr. Ing. Miloš Šeda, Ph.D.

Department

Institute of Automation and Computer Science (ÚAI)

Entry knowledge

The understanding of algorithmization principles, structured approach to problem solving and methodology knowledge of non-object program making is expected.

Rules for evaluation and completion of the course

Course-unit credit requirements: Individually elaborated software project. Project must consistently use lectured methodology. The elaboration of project is continuously checked and consulted. Exam is held in the usual manner.
The attendance at lectures is recommended while at seminars it is obligatory. Education runs according to week schedules. The form of compensation of missed seminars is fully in the competence of a tutor.

Aims

The course objective is to make students familiar with basic mathematical structures of the branch and with the methodology of their possible implementations. It is the introduction to the applicability and adequacy of their use.
Competent development and use of nontrivial object oriented implementations of basic mathematic structures of the branch.

Study aids

Not applicable.

Prerequisites and corequisites

Not applicable.

Basic literature

Češka, M., Vojnar, T.: Studijní text k předmětu Teoretická informatika, 2020 (http://www.fit.vutbr.cz/study/courses/TIN/public/Texty/TIN-studijni-text.pdf). (CS)
Greenshaw, R. and Hoover, H.J.: Fundamentals of the Theory of Computation Principle and Practice. Morgan Kaufmann, 1998. (EN)
Jungnickel, D: Graphs, networks and algorithms, 4th edition. Springer Berlin, Heidelberg, 2013. (EN)
Matoušek, J., Nešetřil, J.: Kapitoly z diskrétní matematiky. 3., upr. a dopl. vyd. V Praze: Karolinum, 2007. (CS)
Meduna, A., Švec, M.: Grammars with context conditions and their applications. Wiley, 2005. (EN)

Recommended reading

Not applicable.

Classification of course in study plans

  • Programme N-AIŘ-P Master's 1 year of study, winter semester, compulsory

Type of course unit

 

Lecture

52 hod., optionally

Teacher / Lecturer

prof. RNDr. Ing. Miloš Šeda, Ph.D.

Syllabus

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

26 hod., compulsory

Teacher / Lecturer

Ing. Petr Šoustek, Ph.D.

Syllabus

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.