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

Academic year 2019/2020
Supervisor: prof. RNDr. Ing. Miloš Šeda, Ph.D.  
Supervising institute: ÚAI all courses guaranted by this institute
Teaching language: Czech
Aims of the course unit:
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.
Learning outcomes and competences:
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.
Course contents:
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.
Teaching methods and criteria:
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.
Controlled participation in lessons:
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.
Type of course unit:
    Guided consultation in combined form of studies  1 × 17 hrs. optionally                  
    Controlled Self-study  1 × 35 hrs. compulsory                  
Course curriculum:
    Guided consultation in combined form of studies 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.
    Controlled Self-study 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. R. Greenshaw, H.J. Hoover: Fundamentals of the Theory of Computation Principle and Practice.
Literature - recommended:
1. M.Chytil: Automaty a gramatiky.
2. J.Plesník: Grafové algoritmy.
The study programmes with the given course:
Programme Study form Branch Spec. Final classification   Course-unit credits     Obligation     Level     Year     Semester  
M2I-K combined study M-AIŘ Applied Computer Science and Control -- Cr,Ex 4 Compulsory 2 1 W
M2I-K combined study M-AIŘ Applied Computer Science and Control P linked to branch B-AIR Cr,Ex 4 Compulsory 2 1 W