Aktuelles

Inhalt

Es wird eine Einführung in die zentralen Konzepte und Ergebnisse der Theoretischen Informatik gegeben, mit Anwendungsbeispielen. Die folgenden Themen werden vertiefend behandelt:

1. Automaten und Formale Sprachen
   Deterministische und nicht-deterministische endliche Automaten, reguläre Ausdrücke, Grammatiken, kontextfreie Sprachen, Pushdown-Automaten
2. Berechenbarkeit
   Turing-Maschinen, Church'sche These, Unentscheidbarkeit, Halteproblem, Reduktion
3. Komplexitätstheorie
   Die Klassen P und NP, NP-vollständige Probleme

Organisation

• Umfang: 3 Semesterwochenstunden
• Vorlesung & Übung: Dr. Jan Johannsen
  
• Korrektor: Sinisa Kurtusic
• Hausaufgaben sind einzeln abzugeben, sie werden korrigiert und bewertet. Wer bei den Hausaufgaben 40% der Punkte erreicht, erhält einen Bonus für die Klausur. Dabei entsprechen 100% der Übungspunkte einem Bonus in Höhe von einer von sechs Klausuraufgaben (ca. 16%).

Zeit und Ort

Material zur Vorlesung

Annotierte Vorlesungsfolien

Die Vorlesungsfolien mit Anmerkungen waren hier erhältlich.

Es gibt ein Forum zur Vorlesung auf die-informatiker.net, das von den Veranstaltern gelesen wird. Bitte nutzen Sie dies für Feedback und Fragen!

Literatur

• John E. Hopcroft, Rajeev Motwani und Jeffrey D. Ullman: Einführung in die Automatentheorie, Formale Sprachen und Komplexitätstheorie, 2. Auflage, Pearson Studium, 2002.
• Alexander Asteroth und Christel Baier: Theoretische Informatik, Pearson Studium 2002.
• Uwe Schöning: Theoretische Informatik - kurz gefasst, 5. Auflage, Spektrum Akademischer Verlag, 2008.

Übungen

Übungsblätter und Musterlösungen waren hier erhältlich.

Klausur

Die Klausur fand am Samstag, den 30.07. um 10 Uhr c.t. in den Hörsälen B 101 und A 140 im Hauptgebäude statt.

Die Wiederholungsklausur fand am Freitag, den 21.10. um 16 Uhr c.t. im Hörsaal B 101 im Hauptgebäude statt.