Logik in der Informatik Prof. Dr. Nicole Schweikardt

Aktuelles

• Die Prüfungen finden am 31.07.2017 und am 11.10.2017 statt.
• Die erste Lehrveranstaltung findet am 18.04. statt.
• Im Logbuch finden Sie nach den Vorlesungen Informationen zum Inhalt der einzelnen Vorlesungsstunden und Materialien.

Einführung

Die Beweiskomplexität (engl. propositional proof complexity) ist ein Forschungsgebiet innerhalb der theoretischen Informatik, das die Länge von Beweisen in aussagenlogischen Beweissystemen untersucht. Der Forschungszweig entstand aus der Frage heraus, ob die Klasse NP aller Entscheidungsprobleme mit Beweisen polynomieller Länge unter Komplement abgeschlossen ist (NP vs. co-NP Problem) und befasst sich heutzutage hauptsächlich mit der Verbindung zwischen Beweissystemen und Algorithmen für NP-schwere Probleme. Bekanntestes Beispiel hierfür ist der Resolutionskalkül, welcher die Grundlage für nahezu alle modernen SAT-Solver bildet. Die Lehrveranstaltung bietet eine Einführung in das Forschungsgebiet und seine Methoden. Einen besonderen Schwerpunkt bilden hierbei die vielfältigen Verbindungen zu benachbarten Gebieten, wie der Logik, der künstlichen Intelligenz und der linearen Optimierung.

Inhalte und Materialien

Ein Logbuch zur Vorlesung und ergänzende Materialien gibt es HIER.

Termine

Vorlesung und Übung

Montags 11:15-12:45 im Schrödinger Zentrum (Rudower Chaussee 26), Raum 1'303

Dienstags 15:15-16:45 im Schrödinger Zentrum (Rudower Chaussee 26), Raum 1'303

Dozent: Dr. Christoph Berkholz

Die Lehrveranstaltung findet im Umfang von 4 SWS an den angegebenen Terminen statt. In diesem Rahmen wird sowohl eine Vorlesung (im Umfang von 3 SWS), als auch eine Übung (im Umfang von 1 SWS) angeboten. Die Entscheidung über das Format der einzelnen Lehrveranstaltungen trifft der Dozent nach didaktischen Gesichtspunkten.

Übungsblätter

Es werden insgesamt 5-6 Übungsblätter ausgegeben, welche an dieser Stelle bereitgestellt werden.

• Blatt 1: Ausgabe: 24.04. Abgabe: 08.05. 11:15.
• Blatt 2: Ausgabe: 03.05. Abgabe: 15.05. 11:15.
• Blatt 3: Ausgabe: 30.05. Abgabe: 12.06. 11:15.
• Blatt 4: Ausgabe: 20.06. Abgabe: 26.06. 11:15.
• Blatt 5: Ausgabe: 04.07. Abgabe: 11.07. 15:15.

Agnes und Moodle

• Bitte schreiben Sie sich HIER bei AGNES in die Übung ein.
• Den Moodle-Kurs zur Lehrveranstaltung finden Sie HIER. Bitte schreiben Sie sich auch dort ein. Das Zugangspasswort wird in der Vorlesung bekannt gegeben.

Prüfung

Zur Vorbereitung auf eine Prüfung (Modulabschlussprüfung) ist es unbedingt notwendig, das gesamte in den Vorlesungs- und Übungseinheiten vermittelte Material durchzuarbeiten.

Die Modulabschlussprüfung wird durch eine mündliche Prüfung abgelegt. Termine für mündliche Modulabschlussprüfungen können ab 03.07.2017 bei Frau Sandig angefragt werden. Die Prüfungen finden am 31.07.2017 und am 11.10.2017 statt.

1. Eine aktive Teilnahme an der Lehrveranstaltung und
2. Erreichen von mindestens 50 Prozent der Gesamtpunktzahl aller Übungsaufgaben, welche schriftlich zu bearbeiten sind.