Dozent: Prof. Albers
Termine
Beginn der Vorlesung: 14.10.2009.| VL | Montag | 15:00 - 17:00 | RUD 26, 0.115 |
|---|---|---|---|
| Mittwoch | 15:00 - 17:00 | RUD 26, 0.115 | |
| UE | Dienstag | 09:00 - 11:00 | RUD 26, 1.306, Pascal Lenzner |
| Dienstag | 11:00 - 13:00 | RUD 26, 1.306, Falk Hüffner | |
| Mittwoch | 13:00 - 15:00 | RUD 26, 1.306, Falk Hüffner | |
| Mittwoch | 13:00 - 15:00 | RUD 26, 1.307, Matthias Hellwig | |
| Donnerstag | 09:00 - 11:00 | RUD 26, 0.307, Matthias Hellwig | |
| Donnerstag | 09:00 - 11:00 | RUD 26, 0.310, Pascal Lenzner |
Klausurtermin
Die Klausur findet am 24.02.2010 von 11-13 Uhr im Hörsaal RUD 26, 0.115 statt.Die Wiederholungsklausur wird am 25.03.2010 von 11-13 Uhr im Hörsaal RUD 25, 3.001 stattfinden.
Inhalte und Lernziele
Die Veranstaltung gibt eine Einführung in grundlegende Konzepte der theoretischen Informatik. Sie untersucht insbesondere Fragestellungen im Bereich der Berechenbarkeit und Komplexität, die für die Informatik als Wissenschaft von zentraler Bedeutung sind.Ein Schwerpunkt der Vorlesung bildet die Thematik "Automatentheorie und formale Sprachen". Wir studieren unter anderem endliche Automaten, Kellerautomaten und Turingmaschinen und stellen Verbindungen zu entsprechenden Klassen von Grammatiken und formalen Sprachen her. Ein weiterer Schwerpunkt bildet die Berechenbarkeitstheorie, die auch die Grenzen der Berechenbarkeit in der Informatik aufzeigt. Schließlich untersuchen wir die Komplexität von Problemen und behandeln die Klasse der "schweren" NP-vollständigen Probleme.
Die Vorlesungen werden ergänzt durch wöchentliche Übungen. Erfolgreiche Teilnahme an den Übungen ist Voraussetzung zur Prüfungszulassung. Es sind mindestens 50% der Gesamtpunkte aus den Übungsserien und zweimaliges Präsentieren einer Aufgabe in den Übungen notwendig, um an der Abschlussklausur teilnehmen zu können.
Literatur
Hauptliteratur
- U. Schöning: Theoretische Informatik kurzgefasst, Spektrum Hochschultaschenbuch, 5. Auflage, 2008, Spektrum Akademischer Verlag, Heidelberg. ISBN 978-3-8274-1824-1
Ergänzende Literatur
- I. Wegener: Theoretische Informatik - eine algorithmenorientierte Einführung, 2. Auflage 1999, Teubner, Stuttgart. ISBN 3-5191-2123-9.
- H. Lewis, C. Papadimitriou: Elements of the Theory of Computation, 2. Auflage, 1997, 361 Seiten, kart., Prentice Hall, New Jersey. ISBN 0-13-262478-
- J. Hopcroft, J. Ullman: Einführung in die Automatentheorie, Formale Sprachen und Komplexitätstheorie, 3. Auflage 1994, 461 Seiten, kart., Addison Wesley, Bonn. ISBN 3-89319-744-3
- M. Sipser: Introduction to the Theory of Computation, 2. Auflage, 2006, Thomson Course Technology, Boston. ISBN 0-534-95097-3
- J. Hromkovic: Theoretische Informatik, 3. Auflage, 2007, Teubner Verlag, Wiesbaden. ISBN 978-3-8351-0043-5
