272-0300-00L Algorithmics for Hard Problems
| Semester | Spring Semester 2018 |
| Lecturers | J. Hromkovic |
| Periodicity | two-yearly recurring course |
| Course | Does not take place this semester. |
| Language of instruction | German |
| Comment | This course d o e s n o t include the Mentored Work Specialised Courses with an Educational Focus in Computer Science A. |
| Abstract | This course unit looks into algorithmic approaches to the solving of hard problems. The seminar is accompanied by a comprehensive reflection upon the significance of the approaches presented for computer science tuition at high schools. |
| Objective | To systematically acquire an overview of the methods for solving hard problems. |
| Content | First, the concept of hardness of computation is introduced (repeated for the computer science students). Then some methods for solving hard problems are treated in a systematic way. For each algorithm design method, it is discussed what guarantees it can give and how we pay for the improved efficiency. |
| Lecture notes | Unterlagen und Folien werden zur Verfügung gestellt. |
| Literature | J. Hromkovic: Algorithmics for Hard Problems, Springer 2004. R. Niedermeier: Invitation to Fixed-Parameter Algorithms, 2006. M. Cygan et al.: Parameterized Algorithms, 2015. F. Fomin, D. Kratsch: Exact Exponential Algorithms, 2010. |