192.136 Frontiers of Algorithms and Complexity
Diese Lehrveranstaltung ist in allen zugeordneten Curricula Teil der STEOP.
Diese Lehrveranstaltung ist in mindestens einem zugeordneten Curriculum Teil der STEOP.

2022W, VU, 2.0h, 3.0EC

LVA-Bewertung

Merkmale

  • Semesterwochenstunden: 2.0
  • ECTS: 3.0
  • Typ: VU Vorlesung mit Übung
  • Format der Abhaltung: Präsenz

Lernergebnisse

Nach positiver Absolvierung der Lehrveranstaltung sind Studierende in der Lage aktuellen Entwicklungen in der Forschung zu Algorithmen und Komplexität zu folgen, aufbauend auf dem bestehenden Wissen zu Algorithmen und Datenstrukturen und anknüpfend an die Komplexitätstheorie und verschiedene Anwendungsgebiete (z.B. Netzwerkdesign, geometrische Probleme, Algorithmen auf planaren Graphen). Die Studierenden können

    - Begriffe und grundlegende Problemstellungen aus der Vorlesung erklären;
    - verfeinerte Komplexitätsannahmen und Folgerungen daraus formal beschreiben und intuitiv erklären;
    - Algorithmen für ausgewählte schwere Probleme intuitiv und formal beschreiben, analysieren und über deren Eigenschaften Beweise führen;
    - mithilfe der Techniken aus der Vorlesung eigene Algorithmen für unbekannte algorithmische Probleme entwerfen und analysieren;
    - die Grenzen aktueller Forschungsergebnisse in Algorithmen und Komplexität beschreiben und erklären;
    - aktuelle Forschungsergebnisse erarbeiten und einordnen.

Inhalt der Lehrveranstaltung

Inhalt dieser Lehrveranstaltung sind neuere Entwicklungen in der Algorithmenforschung, deren Einordnung in die Literatur und die Grenzen des Bekannten. Themenblöcke (exemplarisch):
    - Grundlagen der Komplexitätstheorie (Wiederholung NP-schwere, Reduktionen)
    - Verfeinerte Komplexitätsanalysen unter Zusatzannahmen, z.B. (starke) Exponentialzeithypothese
    - Schwere Probleme aus dem Gebiet der Logik (z.B. untere und obere Schranken für das aussagenlogische Erfüllbarkeitsproblem)
    - Allgemeine algorithmische Techniken (Teilmengenfaltungen, Inklusion-Exklusion, Formulierung als Polynome) und Anwendungen der Techniken (z.B. Steinerbäume)
    - Ergebnisse zur Nicht-Reduzierbarkeit bestimmter Probleme
    - Schwere Probleme auf planaren Graphen in subexponentieller Zeit (wenn Zeit ist)
    - Schwere Geometrische Probleme in subexponentieller Zeit (wenn Zeit ist)

Methoden

Die Veranstaltung wird in Blockvorlesungen abgehalten, die Themen zum Stand der Forschung in Algorithmen und Komplexität abdecken. Sie finden in einem Seminar-ähnlichen Rahmen statt und sind interaktiv, d.h. von den Studierenden wird erwartet, sich an Diskussionen im Plenum zu beteiligen. Jede Technik die im Kurs eingeführt wird, wird an mehreren Beispielen gezeigt.

Prüfungsmodus

Mündlich

Vortragende Personen

Institut

LVA Termine

TagZeitDatumOrtBeschreibung
Di.13:00 - 16:3010.01.2023 - 24.01.2023Seminarraum FAV EG C (Seminarraum Gödel) Lectures
Mi.09:00 - 12:3011.01.2023 - 18.01.2023Seminarraum FAV EG C (Seminarraum Gödel) Lectures
Mi.09:00 - 12:3025.01.2023Seminarraum FAV EG B (Seminarraum von Neumann) Lectures
Mo.13:00 - 16:3006.02.2023Seminarraum FAV EG C (Seminarraum Gödel) Final Presentations for Frontiers of Algorithms and Complexity
Frontiers of Algorithms and Complexity - Einzeltermine
TagDatumZeitOrtBeschreibung
Di.10.01.202313:00 - 16:30Seminarraum FAV EG C (Seminarraum Gödel) Lectures
Mi.11.01.202309:00 - 12:30Seminarraum FAV EG C (Seminarraum Gödel) Lectures
Di.17.01.202313:00 - 16:30Seminarraum FAV EG C (Seminarraum Gödel) Lectures
Mi.18.01.202309:00 - 12:30Seminarraum FAV EG C (Seminarraum Gödel) Lectures
Di.24.01.202313:00 - 16:30Seminarraum FAV EG C (Seminarraum Gödel) Lectures
Mi.25.01.202309:00 - 12:30Seminarraum FAV EG B (Seminarraum von Neumann) Lectures
Mo.06.02.202313:00 - 16:30Seminarraum FAV EG C (Seminarraum Gödel) Final Presentations for Frontiers of Algorithms and Complexity

Leistungsnachweis

Die Note ergibt sich aus einer kurzen muendlichen Pruefung ueber die Themen aus der Vorlesung. Die Studierenden duerfen ein Schwerpunktthema fuer die Pruefung auswaehlen. Insbesondere kann die Pruefung auch in Form von einer Praesentation einer aktuellen Forschungsarbeit aus dem Themengebiet der Vorlesung erfolgen.

LVA-Anmeldung

Von Bis Abmeldung bis
17.10.2022 01:00 10.01.2023 23:59

Curricula

StudienkennzahlSemesterAnm.Bed.Info
066 645 Data Science
066 931 Logic and Computation

Literatur

Es wird kein Skriptum zur Lehrveranstaltung angeboten.

Sprache

Englisch