Theoretische Informatik I (Wintersemester 2007/2008)

Dozent: Prof. Dr. Christoph Kreitz

Allgemeine Information

Semesterwochenstunden: 4
ECTS: 6
Benotet: Ja
Einschreibefrist: 02.11.2007
Lehrform:
Belegungsart: Pflichtmodul

Studiengänge

IT-Systems Engineering BA

Beschreibung

Aktualisierter Text unter:

http://www.cs.uni-potsdam.de/ti/lehre/07-Theorie-I/index.html

Die Theoretische Informatik beschäftigt sich mit den grundlegenden Fragestellungen der Informatik. Hierzu werden Computer- und Automatenmodelle idealisiert und mathematisch untersucht.

Die Automatentheorie und die Theorie der formalen Sprachen ist grundlegend für die Entwicklung von Programmiersprachen und Compilern. Sie untersucht, mit welchen Techniken welche Arten von Sprachen effizient analysiert werden können.

Die Berechenbarkeitstheorie (Thema des zweiten Semesters) befasst sich mit den prinzipiellen Grenzen des Berechenbaren und der Relation zwischen verschiedenen Computer- und Programmiermodellen.

Die Komplexitätstheorie (Thema des zweiten Semesters) untersucht Effizienz von Algorithmen im Hinblick auf Platz- und Zeitbedarf und kümmert sich insbesondere um die Frage, wie effizient man bestimmte Probleme lösen kann.

Einführung in die Theoretische Informatik
- Automaten, Sprachen und Berechenbarkeit
- Informale und formale Beweisführung
Endliche Automaten und Reguläre Sprachen
- Deterministische und nichtdeterministische endliche Automaten
- Reguläre Ausdrücke und Typ-3 Grammatiken
- Lexikalische Analyse
- Charakterisierung und Abschlusseigenschaften regulärer Sprachen
- Minimierung von Automaten
- Grenzen regulärer Sprachen (Pumping Lemma)
Kontextfreie Sprachen
- Kontextfreie Grammatiken
- Syntaxanalyse und Semantik
- Pushdown Automaten
- Charakterisierung und Abschlusseigenschaften kontextfreier Sprachen
- Grenzen und Normalformen kontextfreier Sprachen

Literatur

J. Hopcroft, R. Motwani, J. Ullman: Einführung in die Automatentheorie, Formale Sprachen und Komplexitätstheorie., Pearson 2002 Dieses Buch bildet den Leittext für diese Veranstaltung.
Folien der Vorlesung.
M. Sipser: Introduction to the Theory of Computation. PWS 1997
A. Asteroth, C. Baier: Theoretische Informatik. Pearson 2002
Mitschriften von Kommilitonen früherer Semester liegen auf dem Server des Lehrgebiets "Didaktik der Informatik" bereit: Theorie I Theorie II

Auch lesenswert:

I. Wegener: Theoretische Informatik. Teubner Verlag 1993
U. Schöning: Theoretische Informatik - kurzgefaßt. Spektrum-Verlag 1994
K. Erk, L. Priese: Theoretische Informatik. Springer Verlag 2000
H. Lewis, C. Papadimitriou: Elements of the Theory of Computation. Prentice-Hall 1998

Lesenswertes zur Arbeitsethik

Leistungserfassung

Die Klausur findet am 14.Februar 2008 von 11:15Uhr bis 13:45Uhr im HS 03 und HS 04 des Neuen Hörsaalgebäude der Uni Potsdam statt.

Zurück