Study programmes / C-SE System engineering and informatics / Theoretical Informatics
Course code:TI
Course title in language of instruction:Teoretická informatika
Course title in Czech:Teoretická informatika
Course title in English:Theoretical Informatics
Mode of completion and number of credits:Exam (6 credits)
(1 ECTS credit = 28 hours of workload)
Mode of delivery/Timetabled classes:full-time, 4/1
(full-time, hours of lectures per week / hours of seminars per week)
Language of instruction:Czech
Level of course:master continuing
Semester:WS 2019/2020 - FBE
Name of lecturer:Mgr. Tomáš Foltýnek, Ph.D. (supervisor)
Prerequisites:Theory of Programming Languages or now Theory of Programming Languages
 
Aims of the course:To provide adequate theoretical bases for successful application of modern informatics algorithms to students of the program System engineering and informatics, especially the progress of basic formal apparatus, the concept of algorithm complexity and complexity classes, advanced data structures, graph and network algorithms, parallel programming.
Course contents:
1.Mathematics and its relationship to informatics (allowance 9/3)
 
a.Introduction to problems, concept of formalism
b.Repetition of basic mathematic formalisms -- number theory, set theory, logic
c.Algebra, algebraic systems, formalization by algebra

2.Computer formalization by formal languages and automata (allowance 6/2)
 
a.Formal languages and type-0 grammars
b.Models of computation, Turing machine
c.Church's thesis, RAM machine

3.Complexity of algorithms (allowance 10/3)
 
a.Concept of complexity, definition of complexity by Turing machine
b.Presumption of space and time complexity of common algorithms
c.Determinism, non-determinism, complexity classes
d.Decidability and undecidability of problems

4.Advanced data structures (allowance 4/1)
 
a.Tree data structures and their representation
b.Operations in tree structures and their complexity

5.Graph and network algorithms (allowance 7/3)
 
a.Graph representation
b.Searching graphs (depth-first, breadth-first), minimal path in graph
c.Minimal skeleton of graph
d.Representation of networks, flow networks

6.Parallel programming (allowance 6/2)
 
a.Concept of parallelism, modeling parallel systems
b.The CCS language for parallel system description, bisimulation games
c.Petri nets as models of parallel control systems

Learning outcomes and competences:
Generic competences:
 
-ability to analyse and synthesize
-ability to comment on performance of others and to self-reflect
-capacity to learn
-professional knowledge
-skilled at utilizing and processing information
-work in team

Specific competences:
 
-Ability of critical evaluation, understandable and objective argumentation in mathematical problems solving
-ability to solve the issues using the formal instruments of theoretical informatics
-Analysis and synthesis of knowledge gained in different courses
-Efficient usge of advanced data structures in programming practise
-To think about boundaries of solvability of real problems

Type of course unit:required
Year of study:Not applicable - the subject could be chosen at anytime during the course of the programme.
Work placement:There is no compulsory work placement in the course unit.
Recommended study modules:none
Assessment methods:Final oral exam. Evaluation is also based also on students' activity (discussion during seminars, individual work on exercises and projects).
 
Learning activities and study load (hours of study load)
Type of teaching methodDaily attendance
Direct teaching
     lecture56 h
     practice14 h
Self-study
     preparation for exam56 h
     preparation for regular assessment42 h
Total168 h

Basic reading list
  • Introduction to the theory of computation. 2nd ed. Boston: Thomson Course Technology, 431 p. ISBN 0-534-95097-3.
  • VANÍČEK, J. et al. Teoretické základy informatiky. 1st ed. Praha: Kernberg, 2007. 431 p. Informatika studium. ISBN 978-80-903962-4-1.
  • ČEŠKA, M. et al. Vyčíslitelnost a složitost. Brno: CERM, 1992.
Recommended reading list
  • ČEŠKA, M. Petriho sítě: Úvod do teorie a nástrojů pro aplikaci Petriho sítí. Brno: CERM, 1994.
  • TICHÝ, Z. -- ŠKRÁŠEK, J. Základy aplikované matematiky I. SNTL, 1983.
  • PLESNÍK, J. Grafové algoritmy. Bratislava: VEDA, 1993.