Wintersemester 96 / 97

Seminar

Ganzzahlige lineare und andere schwere Optimierungsprobleme

Grundlagen zu effizienten Algorithmen, Zeitkomplexität, Graphen

• 14. 10. 96

Arten der Nichtlösbarkeit von Problemen, NP-Vollständigkeitsaussagen

• 21. 10. 96

Entscheidbarkeits-, Zahl- und Optimierungsvariante allgemein, Beispiele BPP und CLIQUE

• 28. 10. 96
• Lit.: WEGENER: Informatik

Zugehörigkeit verschiedener Varianten linearer Optimierungsprobleme zu P, NP bzw. NPC

• 04. 11. 96 und 11. 11. 96
• Lit.: WAGNER, WECHSUNG: Computational Complexity

Lösungsmöglichkeiten linearer und ganzzahliger linearer Optimierungsprobleme

• 18. 11. 96
• Lit.: WAGNER, WECHSUNG: Computational Complexity, BIALY, OLBRICH: Optimierung, u.a.

Simplexmethode

• 25. 11. 96
• Lit.: OLBRICH: Optimierung,

NP-Vollständigkeitsbeweise

• 02. 12. 96
• Lit.: HOPCROFT, ULLMAN: Einführung in die Automatentheorie, Formale Sprachen und Komplexitätstheorie

NP-Vollständigkeit des ganzzahligen LOP

• 09. 12. 96
• Lit.: HOPCROFT, ULLMAN: Einführung in die Automatentheorie, Formale Sprachen und Komplexitätstheorie

Nachweis und Lösung einiger schwerer Optimierungsprobleme, Varianten von KP und TSP

• 17. 12. 96
• Literatur: WEGENER: Theoretische Informatik

KP und TSP als Spezialfälle ganzzahliger LOP

• 07. 01. 97
• Literatur: WEGENER: Theoretische Informatik

Beweis der NP-Vollständigkeit des ganzzahligen LOP

• 13. 01. - 20. 01. 97
• Lit.: HOPCROFT, ULLMAN: Einführung in die Automatentheorie, Formale Sprachen und Komplexitätstheorie

Pseudopolynomielle Algorithmen für KP als spezielles LOP

• 27. 01. 97
• Lit.: WEGENER: Theoretische Informatik

Starke NP-Vollständigkeit, Zahlprobleme bei KP und TSP

• 27. 01. 97

Varianten von KP und Transformationen

• 07. 02. 97