252-0057-00L  Theoretische Informatik

SemesterHerbstsemester 2019
DozierendeJ. Hromkovic, H.‑J. Böckenhauer
Periodizitätjährlich wiederkehrende Veranstaltung
LehrspracheDeutsch


KurzbeschreibungKonzepte zur Beantwortung grundlegender Fragen wie: a) Was ist völlig automatisiert machbar (algorithmisch lösbar) b) Wie kann man die Schwierigkeit von Aufgaben (Problemen) messen? c) Was ist Zufall und wie kann er nützlich sein? d) Was ist Nichtdeterminisus und welche Rolle spielt er in der Informatik? e) Wie kann man unendliche Objekte durch Automaten und Grammatiken endlich darstellen?
LernzielVermittlung der grundlegenden Konzepte der Informatik in ihrer geschichtlichen Entwicklung
InhaltDie Veranstaltung ist eine Einführung in die Theoretische Informatik, die die grundlegenden Konzepte und Methoden der Informatik in ihrem geschichtlichen Zusammenhang vorstellt. Wir präsentieren Informatik als eine interdisziplinäre Wissenschaft, die auf einer Seite die Grenzen zwischen Möglichem und Unmöglichem und die quantitativen Gesetze der Informationsverarbeitung erforscht und auf der anderen Seite Systeme entwirft, analysiert, verifiziert und implementiert.

Die Hauptthemen der Vorlesung sind:

- Alphabete, Wörter, Sprachen, Messung der Informationsgehalte von Wörtern, Darstellung von algorithmischen Aufgaben
- endliche Automaten, reguläre und kontextfreie Grammatiken
- Turingmaschinen und Berechenbarkeit
- Komplexitätstheorie und NP-Vollständigkeit
- Algorithmenentwurf für schwere Probleme
SkriptDie Vorlesung ist detailliert durch das Lehrbuch "Theoretische Informatik" bedeckt.
LiteraturBasisliteratur:
1. J. Hromkovic: Theoretische Informatik. 5. Auflage, Springer Vieweg 2014.

2. J. Hromkovic: Theoretical Computer Science. Springer 2004.

Weiterführende Literatur:
3. M. Sipser: Introduction to the Theory of Computation, PWS Publ. Comp.1997
4. J.E. Hopcroft, R. Motwani, J.D. Ullman: Einführung in die Automatentheorie, Formale Sprachen und Komplexitätstheorie.
Pearson 2002.
5. I. Wegener: Theoretische Informatik. Teubner
Weitere Übungen und Beispiele:
6. A. Asteroth, Ch. Baier: Theoretische Informatik
Voraussetzungen / BesonderesWährend des Semesters werden zwei freiwillige Probeklausuren gestellt.