Zentrale Gegenstände der Informatik sind Algorithmen und ihre sprachlichen Realisierungen als Programme sowie Problemlösungen durch Berechnungsverfahren. Die Vorlesung behandelt Grundlagen der theoretischen Informatik, mit denen zunächst eine Fundierung von Programmiersprachen gelegt werden soll. Im Teil I geht es um formale Sprachen und Grammatiken bis hin zu einer Typisierung von Sprachklassen nach ihrer Leistungsfähigkeit (Chomsky-Hierarchie). Unter dem Gesichtspunkt der Spracherkennung betrachtet der Teil II formale Sprachen und Automaten (deterministische und nichtdeterministische endliche Automaten, Kellerautomaten, Turing-Maschinen und RAM-Maschinen). Im Teil III folgen Einführungen in die Berechenbarkeitstheorie, die sich mit grundsätzlichen Möglichkeiten und Grenzen der Algorithmisierbarkeit befasst, und in die Komplexitätstheorie, die untersucht, mit welchem Aufwand an Berechnungsressourcen (Rechenzeit, Speicherplatz) algorithmische Aufgaben gelöst werden können.
Die Vorlesung findet in Präsenz statt, soweit die Situation dieses erlaubt
Kenntnisse A und D waeren wuenschenswert
Es wird ein Skript im ekVV zur Verfuegung gestellt.
(Zur Vertiefung gedacht):
Hopcroft, J.E., Motwani, R., Ullman, J.D.: Einführung in die Automatentheorie, Formale Sprachen und Komplexitätstheorie. Addison-Wesley, 2002 (zur Vertiefung)
Kelly, J.: Logik im Klartext, Pearson Studium, 2003 (viele Beispiele!)
Lewis, H.R., Papadimitriou, C.H.: Elements of the theory of computation. Englewood Cliffs, N.J.: Prentice Hall, 1981 (zur Vertiefung)
Schöning, U.: Theoretische Informatik kurz gefaßt. (2. Auflage) Heidelberg: Spektrum Akademische Verlag, 1995
Schöning, U.: Logik für Informatiker (4. Aufl.). Heidelberg: Spektrum Akdademischer Verlag, 1995 (in Auszügen)
Sipser, M.: Introduction to the theory of computation. PWS Publishing Company, 1996 (wird wegen guter Didaktik gelobt)
Wegener, I.: Kompendium Theoretische Informatik - eine Ideensammlung. Stuttgart: Teubner, 1996 (zur Ergänzung)
Frequency | Weekday | Time | Format / Place | Period |
---|
Module | Course | Requirements | |
---|---|---|---|
39-Inf-6 Grundlagen Theoretischer Informatik | Theoretische Informatik | Student information | |
- | Graded examination | Student information | |
39-Inf-6_ver1 Grundlagen Theoretischer Informatik | Theoretische Informatik | Ungraded examination
Graded examination |
Student information |
The binding module descriptions contain further information, including specifications on the "types of assignments" students need to complete. In cases where a module description mentions more than one kind of assignment, the respective member of the teaching staff will decide which task(s) they assign the students.
Degree programme/academic programme | Validity | Variant | Subdivision | Status | Semester | LP | |
---|---|---|---|---|---|---|---|
Studieren ab 50 |
A corresponding course offer for this course already exists in the e-learning system. Teaching staff can store materials relating to teaching courses there: