Formale Grundlagen der Informatik I
Die Vorlesung umfasst zwei inhaltliche Blöcke:
-
Automatentheorie, formale Sprachen und Logik
Logikkalküle sind Grundlage für eine formale Semantik von sprachlichen Beschreibungen wie auch von Anweisungen in Programmier-, Spezifikations-, und Repräsentationssprachen. In der Vorlesung werden grundlegende Anteile der Aussagenlogik behandelt. Automaten dienen als einfache mathematische Modelle von Computern oder auch Algorithmen. Formale Sprachen dienen der Beschreibung des prinzipiellen, strukturellen Aufbaus von Programmier- und Spezifikationssprachen.
-
Berechenbarkeit und Komplexität
Die Theorie der Berechenbarkeit untersucht, in Verbindung mit der formalen Beschreibung von Komplexität, die Abgrenzung zwischen effektiv Ausführbarem und prinzipiell niemals Möglichem. Beweisverfahren sind ein grundlegendes Verfahren in diesem Bereich, das grundlegend eingeführt und behandelt wird.
Im Zentrum der Vorlesung steht insbesondere auch die mathematische Beschäftigung mit den oben genannten Themen, d.h. das Aufstellen und formale Beweisen von Behauptungen.
Allgemeine Informationen
Veranstalter: Prof. Dr. Petra Berenbrink und Dr. Daniel Moldt
Organisation: Dr. Dominik Kaaser, Lena Otterbach
Übungsgruppenleiter: Prof. Dr. Petra Berenbrink, Simon Bott, Christopher Hahn, Anna Lina Heinzke, Lukas Hintze, Melf Johannsen, Dr. Dominik Kaaser, Dr. Mikko Lauri, Dr. Daniel Moldt, David Mosteller, Lena Otterbach, Dimitri Popov, Kim Wittenburg
Zeit & Ort der Vorlesung:
Klausurtermine (Achtung: geänderte Zeiten und Räume):
- Erster Termin: Do. 19.07.2018 um 12:30 - 14:30 Uhr in Chemie - Hörsaal A + Hörsaal B
- Zweiter Termin: Do. 20.09.2018 um 09:30 - 11:30 Uhr in Rechtshaus Hörsaal
Bedingungen für den Übungsschein:
- Mindestens drei Aufgaben erfolgreich an der Tafel vorrechnen
- Von sechs Pflichtaufgaben müssen vier erfolgreich abgegeben worden sein
- Erfolgreiches Kreuzen (50 % Regel)
- Bestehen der OpenOlat-Tests (12/14)
Materialien
Vorlesungsfolien und Aufgabenblätter werden in OpenOLAT hochgeladen.
Aufgabenblätter
Es wird wöchentlich ein neues Aufgabenblatt herausgegeben. Die Aufgaben des Aufgabenblattes werden in der darauffolgenden Woche in den Übungen besprochen. Schriftliche Aufgaben (Pflichtaufgaben) sind ebenfalls in der darauffolgenden Woche beim jeweiligen Übungsgruppenleiter abzugeben. Wir empfehlen die Bearbeitung in Gruppen von 2 Personen. Im folgenden finden Sie die Termine für die Aufgabenblätter.
- Aufgabenblatt 1
- Ausgabe: 09. April 2018
- Besprechung: 17. April - 20. April
- Aufgabenblatt 2
- Ausgabe: 16. April 2018
- Besprechung: 24. April - 27 April
- Aufgabenblatt 3
- Ausgabe: 23. April 2018
- Besprechung: 02. Mai - 04. Mai
- Aufgabenblatt 4
- Ausgabe: 30. April 2018
- Besprechung: 08. Mai - 11. Mai
- Aufgabenblatt 5
- Ausgabe: 07. Mai 2018
- Besprechung: 15. Mai - 18. Mai
- Aufgabenblatt 6
- Ausgabe: 14. Mai 2018
- Besprechung: 29. Mai - 01. Juni
- Aufgabenblatt 7
- Ausgabe: 28. Mai 2018
- Besprechung: 05. Juni - 08. Juni
- Aufgabenblatt 8
- Ausgabe: 04. Juni 2018
- Besprechung: 12. Juni - 15. Juni
- Aufgabenblatt 9
- Ausgabe: 11. Juni 2018
- Besprechung: 19. Juni - 22. Juni
- Aufgabenblatt 10
- Ausgabe: 18. Juni 2018
- Besprechung: 26. Juni - 29. Juni
- Aufgabenblatt 11
- Ausgabe: 25. Juni 2018
- Besprechung: 03. Juli - 06. Juli
- Aufgabenblatt 12
- Ausgabe: 02. Juli 2018
- Besprechung: 10. Juli - 13. Juli
Literatur
Vorlesungsmaterialien sind zum Teil auf Deusch und zum Teil auf Englisch. Die Vorlesung stützt sich insbesondere auf das Buch:
- Sipser, Michael. Introduction to the Theory of Computation.
Weitere Literatur zur Vertiefung sind z.B.
- Schöning, Uwe (2000). Logik für Informatiker.
- Hopcroft, John E., Motwani, Rajeev, and Ullman, Jeffrey D. Introduction to Automata Theory, Languages, and Computation.
- Hromkovic, Juraj. Theoretische Informatik.