Achtung: Aufgrund von Wartungsarbeiten des BRZ-SAP Systems können im TISS derzeit Fehler auftreten. Die Wartungsarbeiten sind bis 27.06.2022 angesetzt. Vielen Dank für Ihr Verständnis.

104.611 AKINF AKALG The Constraint Satisfaction Problem dichotomy
Diese Lehrveranstaltung ist in allen zugeordneten Curricula Teil der STEOP.
Diese Lehrveranstaltung ist in mindestens einem zugeordneten Curriculum Teil der STEOP.

2022S, SE, 2.0h, 3.0EC

LVA-Bewertung

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, den Algorithmus von Zhuk für endliche CSPs anzuwenden.

Literatur: D.Zhuk, A proof of the CSP dichotomy conjecture, https://arxiv.org/abs/1704.01914

Inhalt der Lehrveranstaltung

Constraint Satisfaction Probleme sind Berechnungsprobleme, bei denen Variablen und Bedingungen gegeben sind, und die Existenz von Werten für die Variablen, welche alle Bedingungen erfüllen, beantwortet werden soll. Bulatov und Zhuk haben 2017 gezeigt, dass, falls die erlaubten Werte aus einer endlichen Menge stammen, solche Probleme immer entweder in polynomieller Zeit lösbar oder NP-vollständig sind. Wir besprechen den Algorithmus von Zhuk, der dieses Resultat impliziert.

Methoden

Vorträge.

Prüfungsmodus

Prüfungsimmanent

Weitere Informationen

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
Mi.15:00 - 16:0002.03.2022 Besprechungszimmer FH grün 5. StockVorbesprechung
Mi.11:00 - 13:0023.03.2022 - 29.06.2022Sem.R. DA grün 02 C The Constraint Satisfaction Problem dichotomy
AKINF AKALG The Constraint Satisfaction Problem dichotomy - Einzeltermine
TagDatumZeitOrtBeschreibung
Mi.02.03.202215:00 - 16:00 Besprechungszimmer FH grün 5. StockVorbesprechung
Mi.23.03.202211:00 - 13:00Sem.R. DA grün 02 C The Constraint Satisfaction Problem dichotomy
Mi.30.03.202211:00 - 13:00Sem.R. DA grün 02 C The Constraint Satisfaction Problem dichotomy
Mi.06.04.202211:00 - 13:00Sem.R. DA grün 02 C The Constraint Satisfaction Problem dichotomy
Mi.27.04.202211:00 - 13:00Sem.R. DA grün 02 C The Constraint Satisfaction Problem dichotomy
Mi.04.05.202211:00 - 13:00Sem.R. DA grün 02 C The Constraint Satisfaction Problem dichotomy
Mi.11.05.202211:00 - 13:00Sem.R. DA grün 02 C The Constraint Satisfaction Problem dichotomy
Mi.18.05.202211:00 - 13:00Sem.R. DA grün 02 C The Constraint Satisfaction Problem dichotomy
Mi.25.05.202211:00 - 13:00Sem.R. DA grün 02 C The Constraint Satisfaction Problem dichotomy
Mi.01.06.202211:00 - 13:00Sem.R. DA grün 02 C The Constraint Satisfaction Problem dichotomy
Mi.08.06.202211:00 - 13:00Sem.R. DA grün 02 C The Constraint Satisfaction Problem dichotomy
Mi.15.06.202211:00 - 13:00Sem.R. DA grün 02 C The Constraint Satisfaction Problem dichotomy
Mi.22.06.202211:00 - 13:00Sem.R. DA grün 02 C The Constraint Satisfaction Problem dichotomy
Mi.29.06.202211:00 - 13:00Sem.R. DA grün 02 C The Constraint Satisfaction Problem dichotomy

Leistungsnachweis

Laufende Beurteilung.

LVA-Anmeldung

Von Bis Abmeldung bis
23.02.2022 12:00 01.04.2022 12:00 01.04.2022 12:00

Curricula

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

Literatur

Es wird kein Skriptum zur Lehrveranstaltung angeboten.

Sprache

Englisch