Das Student-Self-Service ist auf Grund eines technischen Problems derzeit nur eingeschränkt verfügbar. Wir bitten um Ihr Verständnis.

104.619 AKINF AKALG Promise Constraint Satisfaction Problems
Diese Lehrveranstaltung ist in allen zugeordneten Curricula Teil der STEOP.
Diese Lehrveranstaltung ist in mindestens einem zugeordneten Curriculum Teil der STEOP.

2022W, SE, 2.0h, 3.0EC

Merkmale

  • Semesterwochenstunden: 2.0
  • ECTS: 3.0
  • Typ: SE Seminar
  • Format der Abhaltung: Präsenz

Lernergebnisse

Nach positiver Absolvierung der Lehrveranstaltung sind Studierende in der Lage, die mathematischen Methoden für das Studium der Komplexität von Promise Constraint Satisfaction Problemen anzuwenden. Die Studenten sind dann sowohl mit den wesentlichen allgemeinen Reduktionen zwischen Promise Constraint Satisfaction Problemen als auch mit den wichtigsten Algorithmen vertraut.


Inhalt der Lehrveranstaltung

Promise Constraint Satisfaction Probleme (PCSPs) bieten einen Rahmen für das Studium der Komplexität von Approximation. Bei einem PCSP sind Variablen und Bedingungen gegeben, wobei  es von letzteren eine "strenge" und eine "nicht-strenge" Version gibt; das Ziel ist es, Instanzen, bei denen die strengen Bedingungen erfüllbar sind, von solchen zu unterscheiden, bei denen nicht einmal die nicht-strengen Bedingungen erfüllbar sind. Ein konkretes PCSP, dessen Komplexität ein bekanntes offenes Problem ist, ist das Problem, 3-färbbare Graphen von Graphen, welche nicht einmal 10-färbbar sind, zu unterscheiden. Wir werden Methoden aus der universellen Algebra sowie der algebraischen Topologie behandeln, welche es ermöglichen, die Komplexität von PCSPs zu klassifizieren.

Methoden

Vorträge

Prüfungsmodus

Prüfungsimmanent

Weitere Informationen

Literatur: L. Barto, J. Bulin, A. Krokhin, J. Oprsal, Algebraic approach to promise constraint satisfaction, Journal of the ACM 68/4 (2021), 1-66. https://arxiv.org/abs/1811.00970


Beachten Sie beim Verfassen der Ausarbeitung bitte die Richtlinie der TU Wien zum Umgang mit Plagiaten: Leitfaden zum Umgang mit Plagiaten (PDF)

Vortragende Personen

Institut

LVA Termine

TagZeitDatumOrtBeschreibung
Do.12:00 - 14:0006.10.2022 - 26.01.2023Sem.R. DA grün 02 B Promise Constraint Satisfaction Problems
AKINF AKALG Promise Constraint Satisfaction Problems - Einzeltermine
TagDatumZeitOrtBeschreibung
Do.06.10.202212:00 - 14:00Sem.R. DA grün 02 B Promise Constraint Satisfaction Problems
Do.13.10.202212:00 - 14:00Sem.R. DA grün 02 B Promise Constraint Satisfaction Problems
Do.20.10.202212:00 - 14:00Sem.R. DA grün 02 B Promise Constraint Satisfaction Problems
Do.27.10.202212:00 - 14:00Sem.R. DA grün 02 B Promise Constraint Satisfaction Problems
Do.03.11.202212:00 - 14:00Sem.R. DA grün 02 B Promise Constraint Satisfaction Problems
Do.10.11.202212:00 - 14:00Sem.R. DA grün 02 B Promise Constraint Satisfaction Problems
Do.17.11.202212:00 - 14:00Sem.R. DA grün 02 B Promise Constraint Satisfaction Problems
Do.24.11.202212:00 - 14:00Sem.R. DA grün 02 B Promise Constraint Satisfaction Problems
Do.01.12.202212:00 - 14:00Sem.R. DA grün 02 B Promise Constraint Satisfaction Problems
Do.15.12.202212:00 - 14:00Sem.R. DA grün 02 B Promise Constraint Satisfaction Problems
Do.22.12.202212:00 - 14:00Sem.R. DA grün 02 B Promise Constraint Satisfaction Problems
Do.12.01.202312:00 - 14:00Sem.R. DA grün 02 B Promise Constraint Satisfaction Problems
Do.19.01.202312:00 - 14:00Sem.R. DA grün 02 B Promise Constraint Satisfaction Problems
Do.26.01.202312:00 - 14:00Sem.R. DA grün 02 B Promise Constraint Satisfaction Problems

Leistungsnachweis

Laufende Beurteilung.

LVA-Anmeldung

Nicht erforderlich

Curricula

StudienkennzahlSemesterAnm.Bed.Info
860 GW Gebundene Wahlfächer - Technische Mathematik

Literatur

Es wird kein Skriptum zur Lehrveranstaltung angeboten.

Vorkenntnisse

Logik und/oder Algebra I

Sprache

Englisch