Semester | |
Modulnummer | INF-ALG-14 |
Veranstaltungsnummer | INF-ALG-015 , INF-ALG-016 |
Studiengänge | Informatik Master, Informations-Systemtechnik Master, Wirtschaftsinformatik Master |
IBR Gruppe | ALG (Prof. Fekete) |
Art | Vorlesung & Übung |
Dozent | |
Assistent | Dr. Christiane Schmidt Ehemalige Wissenschaftliche Mitarbeiterin |
LP | 5 |
SWS | 2+1+1 |
Ort & Zeit | Lecture: Tuesday, 15:00 - 16:30 Room IZ161 |
Beginn | Vorlesung: 17.04.2012, Grosse Uebung: 26.04.2012, Kleine Uebung: 02.05.2012 |
Voraussetzungen | |
Scheinerwerb | (Homework assignments during the semester, and)* an oral exam at the end. (*=Studienleistung) |
Inhalt | Many interesting and natural algorithmic problems (e.g., the Traveling Salesman Problem) are NP-complete - hence, we cannot expect to find a "perfect" algorithm that (i) always and (ii) fast finds (iii) an optimal solution. However, hard problems still need to be solved! In this class we consider algorithms that do not necessarily find an optimal solution, but that (i) always and (ii) fast find a (iii) provably good solution. Prerequisites are knowledge of algorithms and data structures, basic graph problems and graph algorithms (e.g., as provided in the lecture "Netzwerkalgorithmen"); basic knowledge from theoretic computer science (NP-completeness) are helpful, but will definitely be supplemented. Among the topics of this class are: (1) A basic introduction to NP-completeness and approximation (2) Approximation for vertex and set cover (3) Packing problems (4) Tour problems and variations (5) Current research problems In the context of various problems, a wide spectrum of techniques and concepts will be provided. |
Announcements and DatesGeneral Information
Homework Sets
Literature:
mailing listmaterial for the classmaterial for the class (videos) |
Technische Universität Braunschweig
Universitätsplatz 2
38106 Braunschweig
Postfach: 38092 Braunschweig
Telefon: +49 (0) 531 391-0