| Arbeitsbereich: |
Theoretische Informatik / Formale Sprachen |
| Dozent(en): |
H. Fernau |
| Sprechstunde: |
Mo 9.00-10.00 Uhr, Raum 007, Sand 13, Tel. 29-77565 |
| Zeit: |
ab jetzt: Do 10:00-12:00 |
| Umfang: |
2 |
| Beginn: |
erste Semesterwoche |
| Ort: |
ab jetzt: Kleiner Seminarraum Sand 6/7 |
| Turnus: |
alle zwei Jahre |
| Prüfungsfach: |
Theoretische Informatik |
| Home page: |
|
| Beschreibung: |
| Näherungsalgorithmen stellen neben den randomisierten und parameterisierten
Algorithmen eine weitere Klasse von Algorithmen dar, die helfen, kombinatorisch
schwierige Probleme zu lösen, zu deren exakter Lösung kein polynomieller
Algorithmus bekannt ist. Die Idee dabei ist, einen Polynomialzeitalgorithmus
zu entwickeln, der das Problem zwar nicht exakt, aber in mathematisch beschreibbarer
Weise approximativ zu lösen im Stande ist. Manche Studierende mögen
sich darin erinnern, dass solche Algorithmen auch in der Vorlesung ``Algorithmen
und Komplexität'' angesprochen werden. |
| Voraussetzungen: |
| Grundstudium Informatik |
| Literatur: |
G. Ausiello et al. Complexity and Approximation. Springer,
1999.
|
|
|
|