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

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)
    - Schwere Probleme auf planaren Graphen in subexponentieller Zeit (z.B. Independent Set)
    - Schwere Geometrische Probleme in subexponentieller Zeit (z.B. Rektilineare Steinerb ̈aume)
    - Allgemeine algorithmische Techniken (Teilmengenfaltungen, Inklusion-Exklusion, Formulierung als Polynome) und Anwendungen der Techniken (z.B. Steinerbäume)
    - Ergebnisse zur Nicht-Reduzierbarkeit bestimmter Probleme

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
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

Leistungsnachweis

Die Bewertung erfolgt in einem zweistufigen Prozess. In der ersten und verpflichtenden Stufe wählt jeder Teilnehmer eine aktuelle Forschungsarbeit (nach Anleitung durch den Dozenten) über Algorithmen und Komplexität und bereitet eine Präsentation über deren Inhalte vor. Das ist hinreichend, um den Kurs zu bestehen. Im zweiten Schritt können Studierende, die auf eine bessere Note aus sind, freiwillig eine mündliche Prüfung absolvieren, in der sie ihr Verständnis der Vorlesungsthemen unter Beweis stellen können.

LVA-Anmeldung

Nicht erforderlich

Curricula

StudienkennzahlSemesterAnm.Bed.Info
066 931 Logic and Computation

Literatur

Es wird kein Skriptum zur Lehrveranstaltung angeboten.

Sprache

Englisch