Zur Seitennavigation oder mit Tastenkombination für den accesskey-Taste und Taste 1 
Zum Seiteninhalt oder mit Tastenkombination für den accesskey und Taste 2 

PRÄSENZ im SoSe22: Algorithmisches Beweisen - Einzelansicht

  • Funktionen:
Grunddaten
Veranstaltungsart Vorlesung/Übung Langtext
Veranstaltungsnummer 160072 Kurztext
Semester SS 2022 SWS 4
Teilnehmer 1. Platzvergabe 15 Max. Teilnehmer 2. Platzvergabe 15
Rhythmus Jedes Semester Studienjahr
Credits für IB und SPZ
E-Learning
Hyperlink
Sprache Deutsch
Belegungsfrist Zur Zeit keine Belegung möglich
Abmeldefristen
Nach Zulassung ist eine Abmeldung nur durch die Dozierenden möglich.

Nach Zulassung ist eine Abmeldung auch durch die Teilnehmenden möglich.

Nach Zulassung ist eine Abmeldung nur durch die Dozierenden möglich.
Termine Gruppe: 1-Gruppe iCalendar Export für Outlook
  Tag Zeit Rhythmus Dauer Raum Lehrperson (Zuständigkeit) Status Bemerkung fällt aus am Max. Teilnehmer 2. Platzvergabe
Einzeltermine anzeigen Di. 12:00 bis 14:00 w. 12.04.2022 bis
12.07.2022
Ernst-Abbe-Platz 2 - SR 3325   findet statt  
Einzeltermine anzeigen Do. 12:00 bis 14:00 w. 14.04.2022 bis
14.07.2022
Ernst-Abbe-Platz 2 - SR 3325   findet statt  
Gruppe 1-Gruppe:



Zugeordnete Person
Zugeordnete Person Zuständigkeit
Beyersdorff, Olaf, Universitätsprofessor, Dr.rer.nat. verantwortlich
Zuordnung zu Einrichtungen
Theoretische Informatik
Fakultät für Mathematik und Informatik
Inhalt
Literatur

Uwe Schöning, Jacobo Toran: Das Erfüllbarkeitsproblem SAT, Lehmanns 2012

Jan Krajicek: Bounded Arithmetic, Propositional Logic, and Complexity Theory, Cambridge University Press, 1995

Stasys Jukna: Boolean Function Complexity, Springer 2012

Voraussetzungen

Empfohlene bzw. erwartete Vorkenntnisse:

  • FMI-IN0001 Algorithmen und Datenstrukturen
  • FMI-IN0005 Automaten und Berechenbarkeit
Leistungsnachweis

Voraussetzung für die Zulassung zur Modulprüfung: Übungskriterien, die zum Modulbeginn festgelegt werden

Klausur oder mündliche Prüfung (Festlegung erfolgt zu Beginn des Moduls)

Lerninhalte

Inhalt:

Einführung in die Beweiskomplexität und algorithmische Aspekte von SAT mit den Themen:

  • Wichtige Beweissysteme
  • Harte Formeln für Resolution
  • Spieltechniken für untere Schranken
  • Algorithmen für Spezialfälle (Hornformeln, 2-SAT)
  • DPLL und CDCL Algorithmen
  • Zusammenhang zwischen Beweissystemen und SAT-Solvern
  • Geometrische und algebraische Beweissysteme
  • Frege-Kalküle
  • Quantifizierte Boolesche Formeln
  • Beweissysteme für modale Logik
  • Lokale Suchalgorithmen

Lern- und Qualifikationsziele:

  • Vertiefte Kenntnisse in Theoretischer Informatik, Logik und der algorithmischen Lösung von Erfüllbarkeitsproblemen.
  • Befähigung zur beweistheoretischen Einordnung konkreter Formelklassen
  • Kenntnisse über Techniken zum Nachweis unterer Schranken
  • Einsichten in Chancen und Grenzen moderner SAT-Solver
Zielgruppe
  • Wahlpflichtmodul (TIA, ALG) für den M.Sc. Informatik
  • Wahlpflichtmodul für den B.Sc. Informatik
  • Wahlpflichtmodul (Bereich Informatik) für den M.Sc. Bioinformatik
  • Wahlpflichtmodul (Angewandte Mathematik, Vertiefung Algorithmik, Nebenfach Informatik) für den M.Sc. Mathematik
  • Wahlpflichtmodul (Nebenfach Informatik) für den B.Sc. Mathematik 
  • Wahlpflichtmodul für den B.Sc. Wirtschaftswissenschaften, Schwerpunkt IMS
  • Wahlpflichtmodul für den B.A. Ergänzungsfach Informatik
Strukturbaum
Keine Einordnung ins Vorlesungsverzeichnis vorhanden. Veranstaltung ist aus dem Semester SS 2022 , Aktuelles Semester: SoSe 2024

Impressum | Datenschutzerklärung