272-0300-00L Algorithmics for Hard Problems
|Semester||Spring Semester 2015|
|Lecturers||J. Hromkovic, H.‑J. Böckenhauer, D. Komm|
|Periodicity||two-yearly recurring course|
|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.
F. Fomin, D. Kratsch: Exact Exponential Algorithms, 2010.