Course detail
Theoretical Informatics
FEKT-GTINAcad. year: 2019/2020
Object oriented design. Abstract datat types, theoretical models, directed and undirected graphs, graph representation methods. Deterministic and nondeterministic automata. Data structures and objects. Spanning tree, shortest paths in graphs, Parallel and sequential algorithms. Distributed algorithms. Optimization, genetic algorithms.
Supervisor
Department
Learning outcomes of the course unit
Students have skills of design and implementation of various forms of abstract data types and its application to solve specific problems. To solve them the stduents can use linear, tree and graph data structures, furthemore they can search in the data structures and used genetic algorithms for search in a search space and optimization.
Prerequisites
The subject knowledge on the Bachelor degree level is required.
Co-requisites
Not applicable.
Recommended optional programme components
Not applicable.
Recommended or required reading
LEUWEN, J., WATANABE, O., HAGIYA, M. Exploring New Frontiers of Theoretical Informatics. Springer, 2000. (EN)
GOODRICH, T.M., TAMASSIA, R. Data Structures and Algorithms in Java. 2000. (EN)
BATTISTA, G., TOLLIS, I. Graph Drawing: Algorithms for the Visualization of Graphs. Prentice Hall, 1998. (EN)
Planned learning activities and teaching methods
Techning methods include lectures, computer laboratories and practical laboratories. Course is taking advantage of e-learning (Moodle) system. Students have to write a single project/assignment during the course.
Assesment methods and criteria linked to learning outcomes
final examination
Language of instruction
English
Work placements
Not applicable.
Course curriculum
Lectures:
1. Information representation, objective oriented design.
2. Information representation, introduction to data structures.
3. Complexity, computability and automata theory.
4. Information representation, linear data structures and sorting.
5. Information representation - tree data structures.
6. Information representation - graph theory.
7. Information acccess - spanning tree.
8. Information acccess - graph search.
9. Information acccess - data mining.
10. Information acccess - decision trees.
11. Information acccess - genetic algorithms.
12. Information acccess - genetic programming.
13. Multithreaded computations, parallelization.
Computer excercises:
1. Introduction to OON.
2. Information representation I.
3. Information representation II.
4. Linear data structures.
5. Binary search trees.
6. Graphs theory.
7. Search in Graphs.
8. Midexam.
9. Search in Graphs - Dijkstra algorithm.
10. Data mining - decision trees.
11. Optimization - genetic algorithms.
Aims
To provide theoretical knowledge of information gathering, processing and sharing in communication systems, and of their structure, behaviour and mutual interaction.
Specification of controlled education, way of implementation and compensation for absences
The content and forms of instruction in the evaluated course are specified by a regulation issued by the lecturer responsible for the course and updated for every academic year.
Type of course unit
eLearning
eLearning: currently opened course