Theoretische Informatik I (Wintersemester 2011/2012)

Dozent: Prof. Dr. Christoph Kreitz

Allgemeine Information

Semesterwochenstunden: 4
ECTS: 6
Benotet: Ja
Einschreibefrist: 1.10.2011 - 31.3.2012
Lehrform: VU
Belegungsart: Pflichtmodul

Studiengänge, Modulgruppen & Module

IT-Systems Engineering BA

Beschreibung

Aktualisierter Text unter:

apache.cs.uni-potsdam.de/de/profs/ifi/theorie/lehre/ws1112/ti1-ws1112

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 Sprachenist 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 befasst sich mit den prinzipiellen Grenzen des Berechenbaren und der Relation zwischen verschiedenen Computer- und Programmiermodellen.

· Die Komplexitätstheorie 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.

Berechenbarkeitstheorie und Komplexitätstheorie sind Themen des zweiten Semesters

Gliederung der Theoretischen Informatik I

· Einführung in die Theoretische Informatik

o Automaten, Sprachen und Berechenbarkeit

o Informale und formale Beweisführung

· Endliche Automaten und Reguläre Sprachen

o Deterministische und nichtdeterministische endliche Automaten

o Reguläre Ausdrücke und Typ-3 Grammatiken

o Charakterisierung und Abschlusseigenschaften regulärer Sprachen

o Minimierung von Automaten

o Grenzen regulärer Sprachen (Pumping Lemma)

· Kontextfreie Sprachen

o Kontextfreie Grammatiken

o Pushdown Automaten

o Charakterisierung und Abschlusseigenschaften kontextfreier Sprachen

o Grenzen und Normalformen kontextfreier Sprachen

· Allgemeine und kontextsensitive Sprachen

o Turingmaschinen

o Modelle für Typ-0 und Typ-1 Sprachen

o Eigenschaften von Typ-0 und Typ-1 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 2005

· A. Asteroth, C. Baier: Theoretische Informatik. Pearson 2002

Auch lesenswert:

· I. Wegener: Theoretische Informatik. 3. Auflage, Teubner Verlag 2005.

· U. Schöning: Theoretische Informatik - kurzgefaßt. Spektrum-Verlag 2008.

· K. Erk, L. Priese: Theoretische Informatik. Springer Verlag 2000

· H. Ehrig: Mathematisch-strukturelle Grundlagen der Informatik. Springer 2001

· G. Vossen, K.-U. Witt: Grundkurs Theoretische Informatik. 3. Auflage, Vieweg 2004

· H. Lewis, C. Papadimitriou: Elements of the Theory of Computation. Prentice-Hall 1998

Lesenswertes zur Arbeitsethik

· Code of Academic Integrity (Cornell University)

· Aufdeckung von Plagiaten (FHTW Berlin)

Missverständnisse zum Urheberrecht

Lern- und Lehrformen

· Die wichtigste Komponente jeder Veranstaltung ist das Selbststudium. Sie lernen am besten durch aktives Erarbeiten des Themas aus bereitgestellten Vorlesungsunterlagen oder Literatur und durch eigenes Bearbeiten von Problemstellungen.

· In der Vorlesung werden die zentralen Konzepte der theoretischen Informatik vorgestellt und an Beispielen illustriert. Sie werden ein grösseres Verständnis erreichen, wenn Sie jede Vorlesungsstunde vor- und nachbereiten. Daher werden die in der Vorlesung verwendeten Folien auf den Servern des Lehrgebiets im Voraus bereitgestellt.

· Die Übungen dienen der Vertiefung und Anwendung der in der Vorlesung vorgestellten Themen. Dies geschieht durch Bearbeitung von ad hoc Übungsaufgaben unter Betreuung von Tutoren, einem kurzen Quiz zur Überprüfung eigener Kenntnisse, durch Diskussion von Fragen zur Vorlesung, und durch die Korrektur von Lösungen zu Hausaufgaben. Die Übungsblaetter werden wöchentlich herausgegeben.

· Das Tutorium ist eine freiwillige Zusatzveranstaltung, die zur Besprechung allgemeiner Fragen vorgesehen ist. Auf Wunsch werden auch Lösungen zu den Hausaufgaben vorgestellt und ausführlich besprochen.

Im Kontrast zum Tutorium dienen die Sprechstunden der persönlichen Beratung. Das Ziel ist dabei vor allem Optimierung des individuellen Lernstils und die Klärung von spezifischen Schwierigkeiten.