Scalable Algorithms (ITI)

Parametrisierte Algorithmen

Dozent: Thomas Bläsius

Übungsleiter: Marcus Wilhelm

Sehr viele in der Praxis auftretende Probleme sind NP-schwer und damit im Allgemeinen (vermutlich) nicht in polynomieller Zeit lösbar. Dennoch können diese Probleme häufig effizient gelöst werden, da die Eingaben “gutartig” sind. Eine Möglichkeit diese Gutartigkeit der Instanzen formal zu fassen bietet die Betrachtung der parametrisierten Komplexität. Dabei assoziiert man mit jeder Instanz einen Parameter k, der ein Maß für die Komplexität der Eingabe darstellt. Ziel ist es dann, einen Algorithmus zu finden, dessen Laufzeit nur polynomiell von der Eingabegröße n aber ggf. exponentiell von dem Parameter k abhängt. Im Vergleich zur groben Klassifizierung eines Problems als polynomiell lösbar bzw. NP-schwer bietet die parametrisierte Betrachtungsweise eine deutlich differenziertere Sicht auf schwere Probleme.

Ablauf

Wir treffen uns zum ersten Termin am Montag den 12.4.21 um 10 Uhr in digitaler Form. Der Link zum Zoom Meeting steht im Ilias. Im ersten Treffen wird der weitere Ablauf der Vorlesung besprochen. Danach treffen wir uns wöchentlich jeweils montags um 10 und mittwochs um 14 Uhr.

Termine

Montag (10 Uhr) Mittwoch (14 Uhr)
12.4. Vorlesung 14.4. Übung
19.4. Vorlesung 21.4. Aktiv-Session
26.4. Vorlesung 28.4. Übung
3.5. Vorlesung 5.5. Aktiv-Session
10.5. Vorlesung 12.5. Übung
17.5. Vorlesung 19.5. Aktiv-Session
24.5. Pfingsten 26.5. Pfingsten
31.5. Vorlesung 2.6. Übung
7.6. Vorlesung 9.6. Aktiv-Session
14.6. Vorlesung 16.6. Übung
21.6. Vorlesung 23.6. Aktiv-Session
28.6. Vorlesung 30.6. Übung
5.7. Vorlesung 7.7. Aktiv-Session
12.7. Vorlesung 14.7. Übung
19.7. Vorlesung 21.7. Aktiv-Session

Vorlesung

Übungsblätter

Sei i gerade. Das i/2-te Übungsblatt wird am Mittwoch in Woche i ausgegeben und kann bis zum Mittwoch in Woche i+2 abgegeben werden.