Instituts-Logo Logik in der Informatik
Prof. Dr. Martin Grohe
Humboldt-Logo

Inhalt der Vorlesung Theoretische Informatik I


Das folgende Inhaltsverzeichnis wird im Laufe der Vorlesung noch ergänzt und verfeinert.

Die Folien werden vor der jeweiligen Vorlesungsstunde hier zur Verfügung gestellt. Durch Anklicken des entsprechenden Paragraphen erhalten Sie die Folien, manchmal mit einigen Ergänzungen, im PDF-Format. Denken Sie daran, dass der Vorlesungstoff nicht nur aus den Folien besteht, sondern auch das an der Tafel präsentierte Material umfasst.


Kapitel 1: Einführung
Kapitel 2: Mathematische Grundlagen
§2.1. Mengen, Relationen und Funktionen
§2.2. Induktion und Rekursion
§2.3. Beispiele: Arithmetische Terme und eine einfache Programmiersprache
Kapitel 3: Aussagenlogik
§3.1. Grundbegriffe
§3.2. Anwendung: Data Mining
§3.3. Erfüllbarkeit
§3.4. Folgerungen und Formale Argumente
§3.5. Anwendung: Planungsprobleme in der künstlichen Intelligenz
§3.6. Anwendung: Schaltkreisverifikation
§3.7. Äquivalenz
§3.8. Boolesche Algebra
§3.9. Die Adäquatheit der Junktoren
§3.10. Normalformen
§3.11. Anwendung: Schaltkreisentwurf
Kapitel 4: Aussagenlogische Deduktion
§4.1. Ein aussagenlogisches Beweissystem
§4.2. Resolution
§4.3. Hornformeln
Kapitel 5: Strukturen
§5.1. Zweistellige Relationen
§5.2. Graphen
§5.3. Algebren
§5.4. Strukturen
Kapitel 6: Die Logik der ersten Stufe
§6.1. Syntax
§6.2. Semantik
§6.3. Anwendung: Wissensrepräsentation
§6.4. Äquivalenz und Normalformen
§6.5. Auswertung von Formeln in endlichen Strukturen
§6.6. Anwendung: Relationale Datenbanken
§6.7. Folgerungen und Beweise
Kapitel 7: Berechenbarkeit
§7.1. Das Halteproblem in JAVA
§7.2. Entscheidbarkeit und Aufzählbarkeit
§7.3. GOTO-Programme (dazu ein GOTO Interpreter)
§7.4. Turingmaschinen (dazu ein Turingmaschinensimulator)
§7.5. Berechenbare Funktionen auf den natürlichen Zahlen
§7.6. Das Halteproblem für GOTO-Programme
§7.7. Unentscheidbarkeit der Logik der ersten Stufe
Die Folien im Format “eine Folie pro Seite”: Kapitel 1, Kapitel 2, Kapitel 3, Kapitel 4, Kapitel 5, Kapitel 6, Kapitel 7.
Alles in einem File.


Last modified: Tue Nov 30 14:51:42 CET 2010
Martin Grohe