Computational Complexity in Optimization

Worum geht's

Du lernst Grundlagen der Komplexitätstheorie mit Fokus auf Optimierungsprobleme: formale Modelle, Klassen wie P und NP, NP-Vollständigkeit und typische NP-harte Optimierungsaufgaben. Am Ende kannst du die Schwierigkeit von Optimierungsproblemen einschätzen, passende Modellierungsrichtlinien anwenden und praktische Beispiele analysieren.

Was du danach kannst

• Verständnis von Alphabets, Sprachen und Problemen
• Kenntnis von Turingmaschinen sowie der Klassen P und NP
• Erklärung und Anwendung von NP-Vollständigkeit (inkl. Cook-Theorem)
• Analyse typischer NP-harter Optimierungsprobleme (SAT, ILP, Hamiltoncycles, Partitioning, Normmaximierung, feasible subsystems)
• Anwendung von Modellierungs- und Analysetechniken auf praktische Probleme

Aus was das Modul besteht

• VorlesungVermittlung der theoretischen Grundlagen und demonstrative Beispiele
• Übung/Practice sessionsBearbeitung von Aufgabenblättern und Vertiefung der Methoden; Selbstkontrolle durch Lösungen
• Hausaufgabenpraktische Anwendung und Einübung der relevanten Techniken

Lehrmethode

• Lehrvortrag (teacher-centered)Präsentation der Inhalte mit Beispielen zur Einführung und Motivation
• Übungen mit Hands-on-ArbeitSelbstständiges Vertiefen, Anwendung der Methoden und Überprüfung des Lernfortschritts