Vorlesung: Einführung in die Theoretische Informatik
Dozent: Prof. Johannes Köbler
| Termine: |
VL VL UE UE UE UE UE UE UE UE UE TU TU |
Mo Mi Mo Di Di Di Mi Mi Do Fr Fr Mo Di |
15-17 15-17 9:00-10:30 9-11 11-13 13-15 9-11 9-11 9-11 9-11 11-13 13-15 17:00-18:30 |
RUD 26, 0'115 RUD 26, 0'115 RUD 26, 1'305 RUD 26, 0'313 RUD 26, 1'307 RUD 26, 0'313 RUD 26, 1'306 RUD 26, 1'303 RUD 26, 1'306 RUD 26, 1'306 RUD 26, 1'306 RUD 26, 1'306 RUD 26, 1'303 |
J. Köbler J. Köbler A. Passen W. Kössler W. Kössler A. Passen P. Lenzner M. Hellwig M. Hellwig S. Verbücheln P. Lenzner S. Lowski S. Lowski |
Vorlesungsbeginn: 17.10.2012
Übungsbeginn: ab 22.10.2012
Inhalte und Lernziele
Die VL führt in die Kerngebiete der Theoretischen Informatik ein, wobei die Themengebiete Automaten und formale Sprachen im Mittelpunkt stehen. Die hierbei behandelten Fragen sind nicht nur aus theoretischer Sicht interessant, sondern bilden zugleich die Grundlage für so praktische Anwendungsgebiete wie den Compilerbau.
Aufbauend auf dem Automatenmodell der Turingmaschine lässt sich der Begriff des Algorithmus formalisieren, der in allen Bereichen der Informatik eine zentrale Rolle spielt. Die Frage, welche algorithmischen Probleme lösbar sind, beantwortet die Berechenbarkeitstheorie, indem sie uns die Grenzen der Berechenbarkeit aufzeigt.
Schließlich untersuchen wir die Komplexität von algorithmischen Problemen, indem wir den benötigten Rechenaufwand möglichst gut nach oben und unten abschätzen. Eine besondere Rolle spielen hierbei die NP-vollständigen Probleme, deren Komplexität bis heute offen ist.
Prüfung
Die Nachklausur findet am 25.7.2013 um 9:15 Uhr (Einlass: 9:00 Uhr) im Raum RUD26 0'310 statt. Hilfsmittel sind zugelassen (z.B. Skript).
Die Ergebnisse gibt es hier.
Die Klausur findet am 22.2.2013 um 9:15 Uhr (Einlass: 9:00 Uhr) in den Räumen RUD26 0'115 und RUD26 0'110 statt. Hilfsmittel sind zugelassen (z.B. Skript). Die Liste der Noten nach ID ist hier zu finden (aktualisiert nach der Einsicht am 17.4.2013).
Empfohlene Literatur
- Blum: Theoretische Informatik. Oldenbourg 1998.
- Emden-Weinert, Hougardy, Kreuter, Prömel, Steger: Einführung in Graphen und Algorithmen, Vorlesungsskript, 450 Seiten, Berlin 1996.
- Garey, Johnson: Computers and Intractability - A Guide to the Theory of NP-Completeness. W.H. Freeman and Company, 1979.
- Hoffmann: Theoretische Informatik. Hanser 2009.
- Hopcroft, Ullman: Einführung in die Automatentheorie, Formale Sprachen und Komplexitätstheorie. Addison Wesley, 1994.
- Lewis, Papadimitriou: Elements of the Theory of Computation. Prentice-Hall, 1981.
- Motwani, Raghavan: Randomized Algorithms. Cambridge University Press, 1995.
- Papadimitriou: Computational Complexity. Addison-Wesley, 1994.
- Rich: Automata, Computability, and Complexity. Pearson Prentice Hall, 2008.
- Schöning: Perlen der Theoretischen Informatik. BI-Wissenschaftsverlag, 1995.
- Schöning: Theoretische Informatik - kurz gefaßt. Spektrum Akademischer Verlag, 2008.
- Sipser: Introduction to the Theory of Computation. PWS Publishing Company, 2006.
- Wagner: Einführung in die Theoretische Informatik, Grundlagen und Modelle. Springer Verlag, 1994.
- Wegener: Theoretische Informatik - eine algorithmenorientierte Einführung. Teubner Verlag, 1999.
- Wegener: Kompendium Theoretische Informatik - eine Ideensammlung. Teubner Verlag, 1996.
- Harry Mairson : The Pumping Lemma (poem)
Aufgabenblätter (Abgabe im EG von Haus 4 in RUD 25)
Blatt 1
Blatt 2
Blatt 3
Blatt 4
Blatt 5
Blatt 6
Blatt 7
Blatt 8
Blatt 9
Blatt 10
Blatt 11
Blatt 12
Blatt 13
Blatt 14
Probeklausur
Skript
Folien
Organisatorisches
Reguläre Sprachen (Teil 1)
Relationalstrukturen
Reguläre Sprachen (Teil 2)
Kontextfreie Sprachen
Kontextsensitive Sprachen
Entscheidbare und semi-entscheidbare Sprachen
Komplexität