|
Lecturer(s)
|
-
Jančar Petr, prof. RNDr. CSc.
-
Šebela Marek, prof. Mgr. Dr.
|
|
Course content
|
Binary search trees; average search time, average height. Catalan numbers. Optimal binary search trees, algorithm. Hashing; collision resolution and average operation time. Universal hashing and perfect hashing. Pagerank. R-trees, R*-trees, R+-trees. Hilbert trees and static R-trees. Optimization problems, approximation algorithms, basic concepts and examples. NPO and PO classes, NP-hard optimization problems, examples, properties. The set covering problem (SET-COVER): approximation algorithms and their properties. The traveling salesman problem and its variants: approximation algorithms and their properties. Approximation schemes and their examples. Linear programming: definition, variants, difficulty, duality principle. Relaxation method to linear programming: principle and example of its application.
|
|
Learning activities and teaching methods
|
Dialogic Lecture (Discussion, Dialog, Brainstorming)
- Preparation for the Exam
- 50 hours per semester
|
|
Learning outcomes
|
The subject represents a final oral exam.
|
|
Prerequisites
|
Successful completion of the requirements of the follow-up Master's degree
|
|
Assessment methods and criteria
|
Oral exam
The requirement is to demonstrate on the basis of theoretical and practical studies candidate's skills and the ability to focus on the issue of the examined discipline.
|
|
Recommended literature
|
-
Literatura uvedená u odpovídajícího předmětu.
|