Dozent: Prof. Johannes Köbler
Termine
| VL | Montag | 10:00 - 12:00 | (UL 6, 3094) |
|---|---|---|---|
| Mittwoch | 08:00 - 10:00 | (UL 6, 3075) | |
| UE | Montag | 12:00 - 14:00 | (DOR 24, 309) Prof. J. Köbler |
| Mittwoch | 12:00 - 14:00 | (DOR 24, 309) Dr. C. Gröpl | |
| Mittwoch | 12:00 - 14:00 | (DOR 24, 307) Dr. T. Nierhoff | |
| Mittwoch | 14:00 - 16:00 | (DOR 24, 309) Dr. T. Nierhoff | |
| Donnerstag | 13:00 - 15:00 | (RUD 25, 3.321) Dr. C. Gröpl |
Zuordnung
- Grundstudium, 3. Semester
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äßt sich der Begriff des Algorithmus formalisieren, der in allen Bereichen der Informatik eine zentrale Rolle spielt. Die für den praktischen Einsatz wichtige Frage, welcher Rechenaufwand zur Lösung algorithmischer Problemstellungen nötig ist, führt uns einerseits zu verschiedenen Entwurfsmethoden für effiziente Algorithmen (wobei sich Kenntnisse über algebraische und relationale Strukturen, insbesondere Graphen, als überaus nützlich erweisen). Da die gefundenen Algorithmen "nur" obere Schranken für den benötigten Rechenaufwand liefern, versuchen wir andererseits mit Methoden der Komplexitätstheorie, diesen Aufwand auch nach unten abzuschätzen.
Übungen
Leiter: Prof. J. Köbler, Dr. C. Gröpl und Dr. T. Nierhoff- Übung 1: Aufgaben 1-4
- Übung 2: Aufgaben 5-8
- Übung 3: Aufgaben 9-13
- Übung 4: Aufgaben 14-18
- Übung 5: Aufgaben 19-24
- Übung 6: Aufgaben 25-28
- Übung 7: Aufgaben 29-31
- Übung 8: Aufgaben 32 - 35
- Übung 9: Aufgaben 36 - 39
- Übung 10: Aufgaben 40 - 43
- Übung 11: Aufgaben 44 - 47
- Übung 12: Aufgaben 48 - 52
- Übung 13: Aufgaben 53 - 56
- Übung 14: Aufgaben 57 - 60
- Probeklausur
Empfohlene Literatur
- , Theoretische Informatik, Oldenbourg 1998
- , Einführung in Graphen und Algorithmen
- , Computers and Intractability - A Guide to the Theory of NP-Completeness, W.H. Freeman and Company, 1979
- , Introduction to Automata Theory, Languages, and Computation, Addison Wesley, 1979
- , Elements of the Theory of Computation, Prentice-Hall, 1981
- , Randomized Algorithms, Cambridge University Press, 1995
- , Computational Complexity, Addison-Wesley, 1994
- , Perlen der Theoretischen Informatik, BI-Wissenschaftsverlag, 1995
- , Theoretische Informatik - kurz gefaßt, Spektrum Akademischer Verlag, 1997
- , Introduction to the Theory of Computation, PWS Publishing Company, 1997
- , Einführung in die Theoretische Informatik, Grundlagen und Modelle, Springer Verlag, 1994
- , Theoretische Informatik, Teubner Verlag, 1993
English