VVZ API is not affiliated with ETH Zurich. Data might be outdated or incorrect. Please view the official ETHZ Vorlesungsverzeichnis for binding information.
Content
Diskrete Optimierung II waere besser als Titel. In der SS Vorlesung "Diskrete Optimierung" werden exakte Methoden diskutiert, die leider selten vorhanden sind. Hier werden (NP-)schwere Probleme "behandelt". In letzter Zeit wurde gezeigt, dass für viele kombinatorische Probleme nicht nur das Finden einer Optimallösung, sondern auch das Finden einer Lösung, die a% ans Optimum kommt, NP-schwer ist. Eine Einführung in solche Fragestellungen (Cook-, PCP-Theorem) bildet eine erste Facette der Vorlesung. Eine zweite beschäftigt sich damit, wie man zum Lösen solcher Probleme mittels Heuristiken vorgehen kann. Dazu werden einerseits Meta-Heuristiken (Tabu, Simulated Annealing, GRASP) und andererseits heuristische Konzepte (Randomisierung/Derandomisierung, disjunktive Graphen) besprochen. Die letzte Facette bilden Performance Garantien von Heuristiken (Worst-Case, Average-Case) sowie Schrankenberechnungen. Diese Vorlesung richtet sich an Personen, die sich einen Einblick verschaffen möchten, welche Art Resultate (und Fragen) im Zusammenhang mit Heuristiken existieren. Sie liefert kein Kochrezept für das Problem 'Welche Heuristik soll für ein bestimmtes Problem am besten angewendet werden?', sondern sie gibt lediglich Hinweise, auf was man bei solchen Entscheidungen achten soll.
General Information
- Language
- German
- Frequency
- Yearly recurring
Examination
- Type
- session examination
- Mode
- oral 30 minutes
Course Components
| Type | Title | Time & Place | Hours |
|---|---|---|---|
| lecture |
Heuristiken in kombinatorischer Optimierung
Does not take place this semester.
|
No time listed | 2 h weekly |
| exercise |
Heuristiken in kombinatorischer Optimierung
Does not take place this semester.
|
No time listed | 1 h weekly |