Theoretische Informatik für Medieninformatiker
Lehrveranstaltung, 3-std., Di 14-17 Uhr, Johannsen
Aktuelles
- Die Klausureinsicht zur Nachklausur findet am Montag, den 15.11. von 16-18 Uhr im Raum L 109 (Oettingenstraße 67) statt. Dort kann auch die erste Klausur vom Sommersemester 2010 noch einmal eingesehen werden.
- Die Nachklausur fand am Do. den 14.10. um 14-17 Uhr im Hörsaal B 201 statt.
Inhalt
Es wird eine Einführung in die zentralen Konzepte und Ergebnisse der Theoretischen Informatik gegeben, mit Anwendungsbeispielen aus der Medieninformatik. Die folgenden Themen werden vertiefend behandelt:
- Automaten und Formale Sprachen
Deterministische und nicht-deterministische endliche Automaten, reguläre Ausdrücke, Grammatiken, kontextfreie Sprachen, Pushdown-Automaten - Berechenbarkeit
Turing-Maschinen, Church'sche These, Unentscheidbarkeit, Halteproblem, Reduktion - Komplexitätstheorie
Die Klassen P und NP, NP-vollständige Probleme
Organisation
- Umfang: 3 Semesterwochenstunden
-
Vorlesung & Übung: Dr. Jan Johannsen
- Korrektoren: Stephan Link ( links [at] cip [dot] ifi [dot] lmu [dot] de ), Janislav Malahov ( malahov [at] cip [dot] ifi [dot] lmu [dot] de ), Barry Norman ( norman [at] cip [dot] ifi [dot] lmu [dot] de )
- Hausaufgaben sind einzeln abzugeben, sie werden korrigiert und bewertet. Wer 50% der Punkte aus den Hausaufgaben erreicht, erhält dafür Bonuspunkte für die Klausur. Dabei werden 100% der Übungspunkte ungefähr dem Umfang von einer (von sechs) Klausuraufgaben entsprechen.
Zeit und Ort
| Veranstaltung | Zeit | Ort | Beginn |
|---|---|---|---|
| Vorlesung & Übung |
Di, 14:00 - 16:30 Uhr |
Hörsaal B005 (Theresienstr. 39) | 20.04.2010 |
Material zur Vorlesung
Annotierte Vorlesungsfolien
- Folien 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 waren hier erhältlich.
Klausur
Die Nachklausur findet am Do. den 14.10. um 14-17 Uhr im Hörsaal B 201 (Geschwister-Scholl-Platz 1) statt. Anmeldung über UniWorx bis zum 10.10.
