Theoretische Grundlagen der Informatik II (HPI + ifi) (Sommersemester 2005)

Lecturer:
Course Website: http://www.cs.uni-potsdam.de/ti/lehre/05-Theorie-II/index.html">Webseiten

General Information

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 (Thema des ersten Semesters)

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 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.

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

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

Zum Lesen und Drucken der Folien und der Übungsblätter kann der kostenlose Adobe Acrobat Reader verwendet werden.

In der Vorlesung (wöchentlich Mittwochs 17:00-18:30, HPI HS1) werden die zentralen Konzepte der theoretischen Informatik vorgestellt und an Beispielen illustriert. Die in der Vorlesung verwendeten Folien werden auf den Servern des Lehrgebiets bereitgestellt.
Die Übungen (wöchentlich 2 Stunden, in Gruppen) dienen der Vertiefung und Anwendung der in der Vorlesung vorgestellten Themen. Dies geschieht durch Bearbeitung von ad hoc Übungsaufgaben unter Betreuung von Tutoren, einem 5-Minuten "Quiz" zur Überprüfung eigener Kenntnisse, durch Diskussion von Fragen zur Vorlesung, und durch die Korrektur von Lösungen zu Hausaufgaben. Die <a href="http://www.cs.uni-potsdam.de/ti/lehre/05-Theorie-II/uebungen.html"> Übungsblätter werden wöchentlich herausgegeben.
Das Tutorium (zweiwöchentlich Dienstags 9:25-10:45, HPI HS2) ist eine freiwillige Zusatzveranstaltung die zur Besprechung allgemeiner Fragen vorgesehen ist.
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.

Zur Leistungsbewertung wird ausschließlich eine abschließende Klausur herangezogen.

Eine Nachklausur wird angeboten für Studenten, die in der ersten Klausur durchgefallen sind. In dieser Nachklausur kann maximal die Note 4.0 erreicht werden
Zur Klausur wird zugelassen, wer an der Probeklausur teilnimmt und mindestens 50% der Punkte in den Hausaufgaben erreicht.
Hausaufgaben werden wöchentlich auf den Servern des Lehrgebiets bereitgestellt. Gruppen von bis zu 3 Studenten dürfen eine gemeinsame Lösung zur Korrektur einreichen.