Theoretische Informatik II - Sommersemester 2024

Hinweis zur mündlichen Prüfung: Es wird einen Aufgabenzettel geben, anhand dessen wir uns durch den Stoff bewegen werden. Wichtig: Ich erwarte nicht, dass wir alle Fragen in den 20 Minuten schaffen. Die Fragen dienen als Gerüst für die mündliche Prüfung. Hier sehen Sie zwei solcher Zettel aus meiner Zeit an der Hochschule Zittau/Görlitz, die ähnliche Themen wie hier abgedeckt haben, damit Sie sich einen Eindruck machen können (Zettel 1 und Zettel 2). Die Themenauswahl auf diesen beiden Zetteln ist als Beispiel zu betrachten. Die Themen der Modulprüfung muss nicht auf die Themen beschränkt sein, die auf diesen Zetteln vorkommen!

Hinweis zu den Übungen: Sie können die gegebenen Aufgaben bereits vor der Übung lösen. Während der Übung werden Sie, je nach Menge und Komplexität der Aufgaben, ebenfalls Zeit bekommen, diese zu bearbeiten.

Hinweis: Das zwölfte Übungsblatt ist online.

Vorlesungsskript

Mein Vorlesungsskript liegt ausschließlich online vor. Sie finden es hier. Über Hinweise zu Fehlern, toten Links etc. freue ich mich!

Übungsblätter

• Übungsblatt 1
• Übungsblatt 2
• Übungsblatt 3
• Übungsblatt 4
• Übungsblatt 5
• Übungsblatt 6
• Übungsblatt 7
• Übungsblatt 8
• Übungsblatt 9
• Übungsblatt 10
• Übungsblatt 11
• Übungsblatt 12

Sprechstunden

Dienstag, 15:30 - 17:00 und Mittwoch, 9:15 - 10:45. An anderen Tagen gerne auch, dann aber online und nach Verabredung!

Inhalt

1. Boolesche Schaltkreise.
2. Unendliche Mengen.
3. Berechenbarkeitsbegriff auf natürlichen Zahlen: Primitive Rekursion.
4. Formale Sprachen, insbesondere: reguläre Sprachen, endliche Automaten, reguläre Ausdrücke.
5. Kontextfreie Sprachen. Parser.
6. Turingmaschinen und Berechenbarkeit.
7. Komplexitätstheorie: Laufzeit und Speicherbedarf.

Literatur

• Michael Sipser: Introduction to the Theory of Computing
• Uwe Schöning: Theoretische Informatik - kurz gefasst