192.122 Algorithmic Meta-Theorems Algorithmische Meta-Theoreme

2021W, VU, 2.0h, 3.0EC
Lecture TubeTUWEL

Merkmale

  • Semesterwochenstunden: 2.0
  • ECTS: 3.0
  • Typ: VU Vorlesung mit Übung
  • LectureTube Lehrveranstaltung
  • Format der Abhaltung: Hybrid

Lernergebnisse

Nach positiver Absolvierung der Lehrveranstaltung sind Studierende in der Lage

  • fundamentale Konzepte, die hinter algorithmischen Meta-Theoremen stecken, zu erklären,
  • die vorgestellten Algorithmen zu erklären, zu begreifen, und zu analysieren, und
  • neue Probleme zu analysieren und zu modellieren, um sie mittels algorithmischer Meta-Theoreme zu lösen.

Inhalt der Lehrveranstaltung

Ein algorithmisches Meta-Theorem besagt, dass man alle Probleme, die in einem gewissen logischen Formalismus ausgedrückt werden können, auf bestimmten Klassen von Problemeingaben effizient lösen kann. Das erlaubt einen sehr allgemeinen Ansatz zur algorithmischen Problemlösung, der über einzelne Probleme hinausgeht.

Einige der Themen, die In der Lehrveranstaltung behandelt werden, sind:

  • Lösung von Problemen auf dünnen Graphen, die in Logik erster Ordung ausgedrückt werden können.
  • Lösung von Problemen auf baumartigen Graphen, die in monadischer Logik zweiter Ordung ausgedrückt werden können.
  • Die Sätze von Gaifman und Feferman-Vaught.

 

Methoden

Das Kernstück dieser Lehrveranstaltung sind die Vorlesungseinheiten, in welchen die inhalte vorgestellt werden. Die Vorlesungen werden in einer informellen, seminarartigen Weise abgehalten und sind sehr interaktiv; von den Studierenden wird erwartet, dass sie sich aktiv einbringen. Jede neue Methode und jedes neues Konzept das in den Vorlesungen eingeführt wird, wird mit verschiedenen Beispielen erläutert.  

Prüfungsmodus

Prüfungsimmanent

Vortragende Personen

Institut

LVA Termine

TagZeitDatumOrtBeschreibung
Di.11:00 - 13:0012.10.2021 - 25.01.2022Seminarraum FAV 01 B (Seminarraum 187/2) Vorlesung
Di.13:00 - 14:0012.10.2021 - 25.01.2022Seminarraum FAV 01 B (Seminarraum 187/2) Wechselzeit
Fr.11:00 - 13:0029.10.2021 - 21.01.2022Seminarraum FAV 01 B (Seminarraum 187/2) Übung
Fr.13:00 - 14:0029.10.2021 - 21.01.2022Seminarraum FAV 01 B (Seminarraum 187/2) Wechselzeit
Algorithmic Meta-Theorems Algorithmische Meta-Theoreme - Einzeltermine
TagDatumZeitOrtBeschreibung
Di.12.10.202111:00 - 13:00Seminarraum FAV 01 B (Seminarraum 187/2) Vorlesung
Di.12.10.202113:00 - 14:00Seminarraum FAV 01 B (Seminarraum 187/2) Wechselzeit
Di.19.10.202111:00 - 13:00Seminarraum FAV 01 B (Seminarraum 187/2) Vorlesung
Di.19.10.202113:00 - 14:00Seminarraum FAV 01 B (Seminarraum 187/2) Wechselzeit
Fr.29.10.202111:00 - 13:00Seminarraum FAV 01 B (Seminarraum 187/2) Übung
Fr.29.10.202113:00 - 14:00Seminarraum FAV 01 B (Seminarraum 187/2) Wechselzeit
Di.09.11.202111:00 - 13:00Seminarraum FAV 01 B (Seminarraum 187/2) Vorlesung
Di.09.11.202113:00 - 14:00Seminarraum FAV 01 B (Seminarraum 187/2) Wechselzeit
Fr.12.11.202111:00 - 13:00Seminarraum FAV 01 B (Seminarraum 187/2) Übung
Fr.12.11.202113:00 - 14:00Seminarraum FAV 01 B (Seminarraum 187/2) Wechselzeit
Di.16.11.202111:00 - 13:00Seminarraum FAV 01 B (Seminarraum 187/2) Vorlesung
Di.16.11.202113:00 - 14:00Seminarraum FAV 01 B (Seminarraum 187/2) Wechselzeit
Di.23.11.202111:00 - 13:00Seminarraum FAV 01 B (Seminarraum 187/2) Vorlesung
Di.23.11.202113:00 - 14:00Seminarraum FAV 01 B (Seminarraum 187/2) Wechselzeit
Fr.26.11.202111:00 - 13:00Seminarraum FAV 01 B (Seminarraum 187/2) Übung
Fr.26.11.202113:00 - 14:00Seminarraum FAV 01 B (Seminarraum 187/2) Wechselzeit
Di.30.11.202111:00 - 13:00Seminarraum FAV 01 B (Seminarraum 187/2) Vorlesung
Di.30.11.202113:00 - 14:00Seminarraum FAV 01 B (Seminarraum 187/2) Wechselzeit
Di.07.12.202111:00 - 13:00Seminarraum FAV 01 B (Seminarraum 187/2) Vorlesung
Di.07.12.202113:00 - 14:00Seminarraum FAV 01 B (Seminarraum 187/2) Wechselzeit

Leistungsnachweis

Übungen und mündliche Prüfung.

LVA-Anmeldung

Von Bis Abmeldung bis
23.09.2021 19:00 24.10.2021 19:00 21.11.2021 19:00

Curricula

StudienkennzahlSemesterAnm.Bed.Info
No records found.

Literatur

Es wird kein Skriptum zur Lehrveranstaltung angeboten.

Vorkenntnisse

Es werden Grundkenntnisse in Graphentheorie, Algorithmen und Datenstrukturen und Logik, auf Bachelor-Niveau erwartet.

Vorausgehende Lehrveranstaltungen

Begleitende Lehrveranstaltungen

Sprache

Englisch