Dozent: Prof. Albers
Aktuelles
Klausurzulassungen: Die Liste der zur Klausur zugelassenen Studenten ist HIER zu finden.
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.
Übungsserien
- Blatt 01, Abgabe bis 26.10.
- Blatt 02, Abgabe bis 02.11.
- Blatt 03, Abgabe bis 09.11.
- Blatt 04, Abgabe bis 16.11.
- Blatt 05, Abgabe bis 23.11.
- Blatt 06, Abgabe bis 30.11.
- Blatt 07, Abgabe bis 07.12.
- Blatt 08, Abgabe bis 14.12.
- Blatt 09, Abgabe bis 04.01.
- Blatt 10, Abgabe bis 11.01.
- Blatt 11, Abgabe bis 18.01.
- Blatt 12, Abgabe bis 25.01.
- Blatt 13, Abgabe bis 01.02.
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
