Contact
Teaching
 |
 |
|
| Courses | ||
 |
 |
|
|
|
| Komplexitätstheorie |
 |
|||||||||||||||||||||||||||||||||
| held by: |
Univ.-Prof. Dr. Helmut Veith † Dr. Christian Schallhart Prof. Dr. Stefan Katzenbeisser |
||||||||||||||||||||||||||||||||
| held in: | WS 2004/2005 | ||||||||||||||||||||||||||||||||
| schedule: | Wednesday, 10:15 - 12:00 (MI 00.04.011) start date: 2004-11-03 / end date: 2005-02-09 Thursday, 10:15 - 13:00 (MI 00.04.011) start date: 2004-10-28 / end date: 2005-02-10 |
||||||||||||||||||||||||||||||||
| sws: | 4 | ||||||||||||||||||||||||||||||||
| Die Komplexitätstheorie ist eine Methode zum algorithmischen Vergleich von Problemstellungen aus verschiedenen Gebieten der Informatik. Die ermittelten oftmals erstaunlichen Zusammenhänge sind wertvoll für das Design und Verständnis von Algorithmen, und ermöglichen eine natürliche Klassifikation von Problemen. Insbesonders kennt man tausende als "NP-vollständig'' klassifizierte Probleme, von denen man weiss, dass ein effizienter Algorithmus für eines dieser Probleme sich zu einem Algorithmus für alle dieser Probleme erweitern lässt. Das Clay-Institut hat einen Preis von US$ 1.000.000 für einen solchen Algorithmus (oder den Beweis seiner Unmöglichkeit) ausgesetzt. Das Ziel der Lehrveranstaltung ist die Vermittlung der notwenigen Kenntnisse, um selbständig die Komplexität von Problemen bestimmen zu können, und mit den algorithmischen Konsequenzen umgehen zu können. | |||||||||||||||||||||||||||||||||
| more information: | http://archive.model.in.tum.de/um/courses/complexity/ws0405 | ||||||||||||||||||||||||||||||||
| downloadable material: | |||||||||||||||||||||||||||||||||
slides
|
|||||||||||||||||||||||||||||||||
problem sets
|
|||||||||||||||||||||||||||||||||
other
|
|||||||||||||||||||||||||||||||||
 |
 |
||||||||||||||||||||||||||||||||
