Theoretische Informatik für Medieninformatiker

Aktuelles

• Die Ergebnisse der Nachholklausur sind bei UniWorx veröffentlicht. Wenn Sie Ihre Klausur einsehen möchten, machen Sie bitte bis zum 14.11. per Email einen Termin mit Herrn Johannsen aus.

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
  
• Korrektoren:  Magdalena Benkard, Oliver Hein
  
• Hausaufgaben sind einzeln abzugeben, sie werden korrigiert und bewertet. Die Lösungen können über UniWorx oder vor der Vorlesung auf Papier abgegeben werden, im zweiten Fall ist bei UniWorx eine leere Lösung abzugeben und die Lösungs-ID auf dem Blatt zu vermerken.
  Wer bei den Hausaufgaben 50% der Punkte erreicht, erhält einen Bonus für die Klausur. Dabei entsprechen 100% der Übungspunkte einem Bonus in Höhe von ca. 10% der Klausurpunkte.
  Plagiate bei der Lösung der Hausaufgaben werden mit der Nichtwertung des gesamten Blattes geahndet. Im Wiederholungsfall können weitergehende Sanktionen in Erwägung gezogen werden.
  
  

Zeit und Ort

Material zur Vorlesung

Annotierte Vorlesungsfolien

• Vorlesung 1 vom 10. April
• Vorlesung 2 vom 17. April
• Vorlesung 3 vom 24. April
• Vorlesung 4 vom 8. Mai
• Vorlesung 5 vom 15. Mai
• Vorlesung 6 vom 29. Mai
• Vorlesung 7 vom 5. Juni
• Vorlesung 8 vom 12. Juni
• Vorlesung 9 vom 19. Juni
• Vorlesung 10 vom 26. Juni
• Vorlesung 11 vom 3. Juli
• Vorlesung 12 vom 17. Juli

Videoaufzeichnungen aus dem Jahr 2013.

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

• Blatt 1 vom 10. April, Musterlösung
• Blatt 2 vom 17. April, Musterlösung
• Blatt 3 vom 24. April, Musterlösung
• Blatt 4 vom 8. Mai, Musterlösung
• Blatt 5 vom 15. Mai, Musterlösung
• Blatt 6 vom 29. Mai, Musterlösung
• Blatt 7 vom 5. Juni, Musterlösung
• Blatt 8 vom 12. Juni
• Blatt 9 vom 19. Juni, Musterlösung
• Blatt 10 vom 26. Juni
• Blatt 11 vom 3. Juli, Musterlösung (aktualisiert)
• Blatt 12 vom 17. Juli (Zusatzblatt, Musterlösung)

Klausuren

Die Klausur fand am Montag, den 30.7. ab 14:00 Uhr im Hörsaal A 240 im Hauptgebäude statt. Eine Klausureinsicht findet am Di 14.8. von 14 - 15 Uhr im Raum L 109 (Oettingenstr. 67) statt.

Die Nachholklausur fand am Mttwoch, den 24.10. ab 18:00 Uhr im Hörsaal M 018 im Hauptgebäude statt. Die Ergebnisse sind in UniWorx veröffentlicht.