Course detail

Mathematical Principles of Computer Science

FSI-VZI-KAcad. year: 2017/2018

The course provides students with the introduction to mathematical computer science. Basic mathematical structures of the branch are discussed, their properties and implementation. C# is used as an implementation tool. Practical use of theorems and consequents is demonstrated on the implementation of simple technical applications.

Language of instruction

Czech

Number of ECTS credits

4

Mode of study

Not applicable.

Guarantor

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

Department

Institute of Automation and Computer Science (ÚAI)

Learning outcomes of the course unit

Competent development and use of nontrivial object oriented implementations of basic mathematic structures of the branch.

Prerequisites

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

Co-requisites

Not applicable.

Planned learning activities and teaching methods

The course is taught through lectures explaining the basic principles and theory of the discipline. Exercises are focused on practical topics presented in lectures.

Assesment methods and criteria linked to learning outcomes

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.

Course curriculum

Not applicable.

Work placements

Not applicable.

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.

Specification of controlled education, way of implementation and compensation for absences

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.

Recommended optional programme components

Not applicable.

Prerequisites and corequisites

Not applicable.

Basic literature

R. Greenshaw, H.J. Hoover: Fundamentals of the Theory of Computation Principle and Practice.

Recommended reading

J.Plesník: Grafové algoritmy.
M.Chytil: Automaty a gramatiky.

Classification of course in study plans

  • Programme M2I-K Master's

    branch M-AIŘ , 1 year of study, winter semester, compulsory
    branch M-AIŘ , 1 year of study, winter semester, compulsory

Type of course unit

 

Guided consultation

17 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. Generalization of the list; oriented graph, its representation and implementation.
4. Breadth-first and depth-first search of graph, combined search; the use of queue and stack.
5. Approaches to implementation of evaluated graph, search in evaluated graph.
6. Special graph topologies (sp. trees, binary trees), representation and implementation, basics of use. AND/OR graphs.
7. Languages and grammars. Chomsky’s classification of languages.
8. Finite automatons and grammars, representation.
9. Finite automaton without stack, representation.
10. Finite automaton with stack, representation.
11. Turing machine, enumeratibility, algorithm complexity.
12. Basic concepts of fuzzy sets theory.
13. Recapitulation.