104.568 AKALG Lokale Konsistenz von Bedingungserfüllungsproblemen
Diese Lehrveranstaltung ist in allen zugeordneten Curricula Teil der STEOP.
Diese Lehrveranstaltung ist in mindestens einem zugeordneten Curriculum Teil der STEOP.

2020W, SE, 2.0h, 3.0EC
Diese Lehrveranstaltung wird nach dem neuen Modus evaluiert. Mehr erfahren

LVA-Bewertung

Merkmale

  • Semesterwochenstunden: 2.0
  • ECTS: 3.0
  • Typ: SE Seminar
  • Format der Abhaltung: Hybrid

Lernergebnisse

Nach positiver Absolvierung der Lehrveranstaltung sind Studierende in der Lage...

 

After successful completion of the course, students will be able to apply recent methods from universal algebra to distinguish those constraint satisfaction problems which are solvable by local consistency methods from those which are not. They will be prepared to follow research talks on constraint satisfaction problems.

Inhalt der Lehrveranstaltung

Some constraint satisfaction problems can be solved by checking whether the given constraints in an instance are consistent locally, i.e. on subsets of the instance of a fixed bounded size. This implies in particular that they are solvable in polynomial time. We will obtain algebraic characterizations of those constraint satisfaction problems which enjoy this property.

Methoden

Students present and discuss specific research articles on the topic.

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

Institut

LVA Termine

TagZeitDatumOrtBeschreibung
Do.17:00 - 18:0001.10.2020 Zoom meetingVorbesprechung
Mi.15:00 - 16:3014.10.2020 - 27.01.2021Zeichensaal 1 Seminar
AKALG Lokale Konsistenz von Bedingungserfüllungsproblemen - Einzeltermine
TagDatumZeitOrtBeschreibung
Do.01.10.202017:00 - 18:00 Zoom meetingVorbesprechung
Mi.14.10.202015:00 - 16:30Zeichensaal 1 Seminar
Mi.21.10.202015:00 - 16:30Zeichensaal 1 Seminar
Mi.28.10.202015:00 - 16:30Zeichensaal 1 Seminar
Mi.04.11.202015:00 - 16:30Zeichensaal 1 Seminar
Mi.02.12.202015:00 - 16:30Zeichensaal 1 Seminar
Mi.09.12.202015:00 - 16:30Zeichensaal 1 Seminar
Mi.16.12.202015:00 - 16:30Zeichensaal 1 Seminar
Mi.13.01.202115:00 - 16:30Zeichensaal 1 Seminar
Mi.20.01.202115:00 - 16:30Zeichensaal 1 Seminar
Mi.27.01.202115:00 - 16:30Zeichensaal 1 Seminar

Leistungsnachweis

Continuous assessment.

LVA-Anmeldung

Von Bis Abmeldung bis
01.10.2020 12:00 29.10.2020 12:00 29.10.2020 12:00

Curricula

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

Literatur

Barto, L., The collapse of the bounded width hierarchy, Journal of Logic and Computation, Volume 26, Issue 3, June 2016, Pages 923–943 

Barto, L. and Kozik, M., Constraint Satisfaction Problems solvable by local consistency methods. J. ACM 61, 1, Article 3 (January 2014), 19 pages

 

 

Vorkenntnisse

Basic knowledge in logic and/or alebra.

Sprache

Englisch