Main page | Study Branches/Specializations | Groups of Courses | All Courses | Roles                Instructions

A course is the basic teaching unit, it's design as a medium for a student to acquire comprehensive knowledge and skills indispensable in the given field. A course guarantor is responsible for the factual content of the course.
For each course, there is a department responsible for the course organisation. A person responsible for timetabling for a given department sets a time schedule of teaching and for each class, s/he assigns an instructor and/or an examiner.
Expected time consumption of the course is expressed by a course attribute extent of teaching. For example, extent = 2 +2 indicates two teaching hours of lectures and two teaching hours of seminar (lab) per week.
At the end of each semester, the course instructor has to evaluate the extent to which a student has acquired the expected knowledge and skills. The type of this evaluation is indicated by the attribute completion. So, a course can be completed by just an assessment ('pouze zápočet'), by a graded assessment ('klasifikovaný zápočet'), or by just an examination ('pouze zkouška') or by an assessment and examination ('zápočet a zkouška') .
The difficulty of a given course is evaluated by the amount of ECTS credits.
The course is in session (cf. teaching is going on) during a semester. Each course is offered either in the winter ('zimní') or summer ('letní') semester of an academic year. Exceptionally, a course might be offered in both semesters.
The subject matter of a course is described in various texts.

MI-PAM Efficient Preprocessing and Parameterized Algorithms Extent of teaching: 2P+1C
Instructor: Completion: Z,ZK
Department: 18101 Credits: 4 Semester: L

Annotation:
There are many optimization problems for which no polynomial time algorithms are known (e.g. NP-complete problems). Despite that it is often necessary to solve these problems exactly in practice. We will demonstrate that many problems can be solved much more effectively than by naively trying all possible solutions. Often one can find a common property (parameter) of the inputs from practice-e.g., all solutions are relatively small. Parameterized algorithms exploit that by limiting the time complexity exponentially in this (small) parameter and polynomially in the input size (which can be huge). Parameterized algorithms also represent a way to formalize the notion of effective polynomial time preprocessing of the input, which is not possible in the classical complexity. Such a polynomial time preprocessing is then a suitable first step, whatever is the subsequent solution method. We will present a plethora of parameterized algorithm design methods and we will also show how to prove that for some problem (and parameter) such an algorithm (presumably) does not exist. We will also not miss out the relations to other approaches to hard problems such as moderately exponential algorithms or approximation schemes.

Lecture syllabus:
1. Introduction. Bounded Search Trees, Basic definitions.
2. Kernelization as a formalization of the term "efficient preprocessing". Examples of simple kernelizations.
3. Interleaving kernelization with bounded search trees. More complex bounded search trees.
4. Kernelization based on global rules.
5. Non-existence of polynomiál size kernels for some problems.
6. Dynamic programming, exploitation of the inclusion-exclusion principle. Color Coding.
7. Iterative compression. Greedy localization.
8. Tree-width and basic properties.
9. Dynamic programming on graphs of bounded tree-width. Courcelle's Theorem.
10. Baker's style approximation schemes.
11. Minors, their usage in design of parameterized algorithms
12. Parameterized algorithms for planar graphs (Bidimensionality).
13. Classes of parameterized intractability, parameterized reduction, relations to Exponential Time Hypothesis

Seminar syllabus:
Seminars consist of problem solving on the topics of the course.

Literature:
M. Cygan, F.V. Fomin, Ł. Kowalik, D. Lokshtanov, D. Marx, Ma. Pilipczuk, Mi. Pilipczuk, S. Saurabh: Parameterized Algorithms, Springer, 2015.
Rodney G. Downey, Michael R. Fellows: Fundamentals of Parameterized Complexity, Springer, 2013. Rolf Niedermeier: Invitation to Fixed-Parameter Algorithms, Oxford University Press, 2006.

Requirements:
The lecture is intended rather for students of higher years of studies, eventually Ph.D. students. However, only basic knowledge of Graph Theory and Computational Complexity (e.g., BIE-GRA, BIE-AG1, BIE-AG2) is required for understanding. Hence, the lecture can be also attended by students in the third year of bachelor studies.

Informace o předmětu a výukové materiály naleznete na https://courses.fit.cvut.cz/MI-PAM/

The course is also part of the following Study plans:
Study Plan Study Branch/Specialization Role Recommended semester
MI-ZI.2016 Knowledge Engineering V Není
MI-ZI.2018 Knowledge Engineering V Není
MI-SP-TI.2016 System Programming V Není
MI-SP-SP.2016 System Programming V Není
MI-SPOL.2016 Unspecified Branch/Specialisation of Study V Není
MI-WSI-WI.2016 Web and Software Engineering V Není
MI-WSI-SI.2016 Web and Software Engineering V Není
MI-WSI-ISM.2016 Web and Software Engineering V Není
MI-NPVS.2016 Design and Programming of Embedded Systems V Není
MI-PSS.2016 Computer Systems and Networks V Není
MI-PB.2016 Computer Security V Není
NI-TI.2018 Computer Science V 2
MI-WSI-ISM.2016 Web and Software Engineering V 4


Page updated 28. 3. 2024, semester: Z/2023-4, L/2019-20, L/2022-3, Z/2019-20, Z/2022-3, L/2020-1, L/2023-4, Z/2020-1, Z,L/2021-2, Send comments to the content presented here to Administrator of study plans Design and implementation: J. Novák, I. Halaška