Logik in der Informatik Prof. Dr. Nicole Schweikardt

Aktuelles

• In folgender PDF-Datei finden Sie die endgültigen Ergebnisse der Klausur vom 09.04.2015.

• In folgender PDF-Datei finden Sie die endgültigen Ergebnisse der Klausur vom 02.03.2015.

• Hier finden Sie eine Zusammenstellung von Hinweisen zur Klausur.
  Weitere Hinweise finden Sie im letzten Eintrag des Logbuchs.

• Zur Unterstützung Ihrer Klausurvorbereitungen findet am Dienstag, den 24.2., von 10:15 bis 13:00 im Hörsaal 0'110 ein "Help-Desk" statt.

• Die am Dienstag, den 10.2., ausgefallene Prolog-Übung wird am Dienstag, dem 17.2., von 15:15 bis 17:00 in Raum 3.213 nachgeholt.

• Am 12.02.15 ab 11h15 findet in Raum 3.408 ein Vortrag von Prof. Leonid Libkin (Univ. of Edinburgh) zum Thema "Incomplete Data: What Went Wrong, and How to Fix It" statt. Interessenten sind herzlich eingeladen! Die Vortragsankündigung findet sich hier.

• Bitte beachten Sie folgende Hinweise für die Anmeldung zur ersten schriftlichen Prüfung:
  Wie im PDF ersichtlich beginnt die Anmeldungsfrist am 12.01.2015 und endet am 23.02.2015. Melden Sie sich bitte online über Agnes an. Nach Ablauf der Anmeldefrist wird über die Zulassung zur Prüfung entschieden.

• Der Fragebogen zur Evaluation der Veranstaltung wurde zu Beginn der Vorlesung am Freitag, den 9. Januar 2015 ausgeteilt.

• Wir wünschen Ihnen alles Gute für das Jahr 2015!

• Bitte beachten Sie: Das Goya System sichert täglich zwischen 2.oo Uhr und 4.oo Uhr morgens seine Daten. D.h. in dieser Zeit sind elektronische Abgaben nicht möglich.
• Beachten Sie für Ihre Abgaben der Übungen:
  • Auf dem abgegebenen Übungsblatt müssen Name, Matrikelnummer und Übungsgruppe vermerkt sein.
  • Mehrseitige Abgaben müssen per Tacker zusammengeheftet werden. Büroklammern oder kreative Faltungen o.ä. sind nicht ausreichend.
  • Abgaben, welche (direkt) vor der Vorlesung abgegeben werden, sind in die entsprechende Box der Übungsgruppe zu werfen.
  Erfüllt Ihre Abgabe eine der obigen Bedingungen nicht, erhalten Sie ab einschließlich Blatt 4 Punktabzug von 2^{(Blattnr. - 3)} Punkten. Das Blatt selbst wird aber minimal mit 0 Punkten bewertet.
• Auf vielfachen Wunsch hin findet in Raum 3.213 ab dem 14.11. jeden Freitag eine zweite Prolog-Übung statt.
• Die in der 1. Übungsstunde verwendeten Folien finden Sie hier.
• Den in der Vorlesung vorgestellten Formelchecker "(tks.AL)" für die Aussagenlogik finden Sie hier.
• Die aktuellen Folien und Teile des Skripts, Literaturhinweise, sowie Informationen dazu, welche Themen in welcher Vorlesungsstunde behandelt wurden, finden Sie im Logbuch.
• Die Eröffnungsvorlesung fand am Mittwoch, den 15.10.2014 statt.
• Die Übungsgruppen trafen sich erstmalig in der zweiten Vorlesungswoche, also in der Woche vom 20.-24.10.2014.
• Die Prolog-Übung fand erstmalig in der zweiten Vorlesungswoche, also in der Woche vom 20.-24.10.2014, in Raum 3.213 statt.

Einführung

Logik spielt eine grundlegende Rolle in vielen Bereichen der Informatik, etwa dem Schaltkreisentwurf, dem Software-Engineering, der künstlichen Intelligenz, der Datenbanken und der theoretischen Informatik. Die Logik in der Informatik baut auf der mathematischen Logik auf, die sich etwa seit Ende des 19. Jahrhunderts herausgebildet hat. In den letzten 30 Jahren hat sich die Logik in der Informatik aber in eine eigenständige, von den Anwendungen bestimmte Richtung entwickelt.

Die Vorlesung ist eine Einführung in die Logik und ihre Anwendungen in der Informatik. Darüber hinaus wird die logikbasierte Programmiersprache Prolog eingeführt.

Inhalt

• Kapitel 1: Einleitung (Skript, Folien)
• Kapitel 2: Aussagenlogik (Skript, Folien)
• Kapitel 3: Logik-Programmierung (Skript, Folien, aktualisiert am 22.12.2014)
• Kapitel 4: Logik erster Stufe (Skript, Folien)
• Kapitel 5: Grundlagen des automatischen Schließens (Skript, Folien)

Das komplette Vorlesungsskript inkl. Titelseite und Inhaltsverzeichnis (Version vom 17.02.2015) ist hier erhältlich.

Neben den Folien wird auch die Tafel verwendet, insbesondere um Beispiele und Beweise zu entwickeln.

Beachten Sie: In den Vorlesungs- und Übungsstunden werden viele wichtige Dinge (insbesondere Beweise, aber auch einiges andere) an der Tafel erklärt. Diese Dinge sind für die Veranstaltung wesentlich und daher auch dann prüfungsrelevant, wenn sie nicht in den auf den Webseiten erhältlichen Materialien enthalten sind.
Zur Vorbereitung auf eine Prüfung wird dringend empfohlen, das gesamte in den Vorlesungs- und Übungsstunden (mit Folie oder an der Tafel) vermittelte Material durchzuarbeiten.
Es ist daher wichtig, dass Sie sich während der Vorlesungs- und Übungsstunden Notizen machen.

Logbuch

Hier finden Sie (nach den Vorlesungen) Informationen zum Inhalt der einzelnen Vorlesungsstunden, die in der Vorlesung verwendeten Folien, Teile des Skripts und gelegentlich auch Korrekturen und sonstige ergänzende Bemerkungen.

Informationen zum Vorlesungsbetrieb

Zeiten und Räume

Mittwochs 09:15-11:00 im Schrödinger Zentrum (Rudower Chaussee 26), Raum 0'110 und
Freitags 13:15-15:00 im Schrödinger Zentrum (Rudower Chaussee 26), Raum 0'115

 

Dozentin

Prof. Dr. Nicole Schweikardt

Informationen zum Übungsbetrieb

Ergänzend zu den Vorlesungen finden 2-stündige Übungen in kleinen Gruppen statt, in denen Fragen zur Vorlesung diskutiert und die Übungsaufgaben besprochen werden. Eine Liste mit allen Übungsgruppen finden Sie hier.

Melden Sie sich bitte bis zum 16.10.2014 mittels GOYA für eine Übungsgruppe an.

Übungsgruppenleiter/innen

Joachim Bremer

André Frochaux

Lucas Heimberg

 

Tutoren/innen

Christoph Burschka

Maria Tammik

 

Zeiten und Räume der Übungsgruppen

Montags 11-13, Schrödinger-Zentrum, Raum 0'313 bei André Frochaux

Montags 15-17, Schrödinger-Zentrum, Raum 1'306 bei André Frochaux

Dienstags 09-11, Schrödinger-Zentrum, Raum 1'307 bei Joachim Bremer

Dienstags 13-15, Schrödinger-Zentrum, Raum 1'305 bei Lucas Heimberg

Mittwochs 11-13 Schrödinger-Zentrum, Raum 1'303 bei Joachim Bremer

 

Informationen zur Prolog-Übung

Ergänzend zu den Vorlesungen und Übungen findet jede Woche (ab dem 14.11. an zwei Terminen) eine 2-stündige Prolog-Übung statt, in der Sie darin unterstützt werden, sich in die Programmiersprache Prolog einzuarbeiten. In der Übung werden zusätzliche Programmierbeispiele behandelt und Anleitungen zur Lösung der Prolog-bezogenen Übungsaufgaben gegeben. Die Teilnahme an der Prolog-Übung ist freiwillig und bedarf keiner Anmeldung.

Den Quellcode der in der Prolog-Übung verwendeten Beispiele finden Sie hier.

Zeiten und Räume

Dienstags 15:15-17:00 im Johann von Neumann-Haus (Rudower Chaussee 25), Raum 3.213

Freitags 11:15-13:00 im Johann von Neumann-Haus (Rudower Chaussee 25), Raum 3.213

 

Dozent

Dipl.-Inf. Lucas Heimberg

Übungsaufgaben

Ab der zweiten Vorlesungswoche wird wöchentlich ein Übungsblatt ausgegeben. Jedes Übungsblatt enthält drei theoretische und eine praktische Aufgabe. Auf jedem Übungsblatt können bis zu 100 Punkte erreicht werden.

Das aktuelle Übungsblatt ist jeweils spätestens mittwochs nach der Vorlesung an dieser Stelle zu finden und wird außerdem mittwochs in gedruckter Form am Ende der Vorlesung ausgeteilt.

• Blatt 1 (ausgeteilt am 22.10., Abgabe bis zum 29.10., 9:15)
• Blatt 2 (ausgeteilt am 29.10., Abgabe bis zum 5.11., 9:15)
• Blatt 3 (aktualisiert) (ausgeteilt am 05.11., Abgabe bis zum 12.11., 9:15)
• Blatt 4 (aktualisiert) (ausgeteilt am 12.11., Abgabe bis zum 19.11., 9:15)
• Blatt 5 (ausgeteilt am 26.11., Abgabe bis zum 3.12., 9:15)
• Blatt 6 (ausgeteilt am 3.12., Abgabe bis zum 10.12., 9:15)
• Blatt 7 (aktualisiert) (ausgeteilt am 10.12., Abgabe bis zum 17.12., 9:15)
• Blatt 8 (ausgeteilt am 17.12., Abgabe bis zum 7.1., 9:15)
• Blatt 9 (ausgeteilt am 7.1., Abgabe bis zum 14.1., 9:15)
• Blatt 10 (ausgeteilt am 14.1., Abgabe bis zum 21.1., 9:15)
• Blatt 11 (ausgeteilt am 21.1., Abgabe bis zum 28.1., 9:15)
• Blatt 12 (ausgeteilt am 28.1., Abgabe bis zum 4.2., 9:15 — dies ist das letzte Übungsblatt dieses Semesters)

Die Abgabe der bearbeiteten Aufgaben erfolgt in der jeweils darauf folgenden Woche mittwochs, bis spätestens 9:15 Uhr vor Beginn der Vorlesung (oder alternativ im Briefkasten zwischen Raum 3.402 und 3.401 im 4. Stock von Haus 3 des Johann von Neumann-Hauses) in Papierform.

Obwohl es sicherlich sinnvoll ist, über die Aufgaben mit Kommilitonen/innen gemeinsam zu reden und nachzudenken, sollte jede/r Student/in seine eigene Lösung aufschreiben und abgeben.

Achtung:

• Auf dem abgegebenen Übungsblatt müssen Name, Matrikelnummer und Übungsgruppe vermerkt sein. Fehlt eine dieser Angaben, müssen Sie mit Punktabzug rechnen.
• Mehrseitige Abgaben müssen per Tacker zusammengeheftet werden. Büroklammern oder kreative Faltungen o.ä. sind nicht ausreichend.
• Eine verspätete Abgabe ist nicht möglich.
• Abgaben, welche (direkt) vor der Vorlesung abgegeben werden, sind in die entsprechende Box der Übungsgruppe zu werfen.

Die von Ihnen abgegebenen Lösungen werden von unseren Tutoren korrigiert und in den Übungsstunden der darauffolgenden Woche zurückgegeben. Die Theorie-Aufgaben werden in den Übungsstunden besprochen; die Prolog-basierten Aufgaben werden in der Prolog-Übung besprochen.

Wichtig:
Für den Erwerb eines Übungs- oder Teilnahmescheins müssen insgesamt 40% der erreichbaren Übungspunkte erzielt werden, und es muss mindestens einmal erfolgreich in der Übungsstunde vorgerechnet werden.
Der Erwerb eines Übungsscheins ist die Voraussetzung für die Teilnahme an der Klausur.

Prüfung

Die Klausur dauert 3 Stunden und findet am Montag, den 02.03.2015 ab 10:00 Uhr im Schrödinger-Zentrum in den Räumen 0'115 und 0'110 statt. Einlass ist ab 9:45 Uhr.

Eine Wiederholungsprüfung (ebenfalls als 3-stündige Klausur) findet am Donnerstag, den 09.04.2015 ab 10:00 Uhr im Schrödinger-Zentrum in Raum 0'115 statt. Einlass ist ab 9:45 Uhr.

Literatur

Haupthema der Vorlesung ist die Logik. Folgende Bücher seien dazu zur Vertiefung des Vorlesungstoffes empfohlen:

[B]	S. Burris, Logic for Mathematics and Computer Science. Prentice Hall, 1998.
[KK]	M. Kreuzer, S. Kühling. Logik für Informatiker. Pearson, 2006.
[S]	U. Schöning, Logik für Informatiker. 5. Auflage, Spektrum Akademischer Verlag, 2000.

Als Ergänzung seien auch noch folgende Bücher genannt:

[EFT]	Heinz-Dieter Ebbinghaus, Jörg Flum, Wolfgang Thomas, Einführung in die Mathematische Logik. 5. Auflage, Spektrum Akademischer Verlag, 2007.
[L]	Leonid Libkin, Elements of Finite Model Theory. Springer, 2004. Die für die Vorlesung relevanten Teile des Buchs sind hier unter dem mit "Download table of contents and a sample chapter" beschrifteten Link erhältlich.
[FG]	Jörg Flum, Martin Grohe, Parameterized Complexity Theory. Springer, 2005.
[C]	P. J. Cameron, Sets, Logic and Categories. Springer Verlag, 1998.
[vD]	D. van Dalen, Logic and Structure. 4th Edition, Springer Verlag, 2004.
[HR]	M. Huth and M. Ryan, Logic in Computer Science – Modelling and Reasoning About Systems . 2nd Edition, Cambridge University Press, 2004.

Im praktischen Teil der Vorlesung beschäftigen wir uns mit der Programmiersprache Prolog. Hier basiert die Vorlesung auf den folgenden beiden Büchern:

[BBS]	Patrick Blackburn, Johan Bos, Kristina Striegnitz, Learn PROLOG Now!. Kings College Publications, 2006. Online version.
[SS]	Ehud Shapiro, Leon Sterling, The Art of PROLOG: Advanced Programming Techniques. 2nd Edition, MIT Press, 1994.

Auch hier ergänzend noch einige weitere Bücher:

[DEC]	Pierre Deransart, AbdelAli Ed-Dbali, Laurent Cervoni, Prolog: The Standard: Reference Manual. Springer Verlag, 1996.
[CM]	William F. Clocksin, Christopher S. Mellish, Programming in Prolog: Using the ISO Standard. 5th Edition, Springer Verlag, 2010.
[Clo]	William F. Clocksin, Clause and Effect: Prolog Programming for the Working Programmer. Springer Verlag, 1997.

Programmierresourcen

Wir verwenden in der Vorlesung SWI-Prolog. Ein Kurzanleitung für den Einstieg in SWI-Prolog finden Sie hier.