Theoretische Informatik II (Sommersemester 2006)
Dozent:
Prof. Dr. Christoph Kreitz
Allgemeine Information
- Semesterwochenstunden: 4
- ECTS: 6
- Benotet:
Ja
- Einschreibefrist: 05.05.2006
- Lehrform:
- Belegungsart: Pflichtmodul
Studiengänge
- IT-Systems Engineering BA
Beschreibung
siehe:
http://www.cs.uni-potsdam.de/ti/lehre/06-Theorie-II/uebungen.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 (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.
Berechenbarkeitstheorie
o Turingmaschinen
o Rekursive Funktionen
o Lambda-Kalkül und arithmetische Repräsentierbarkeit
o Die Churchsche These
o Berechenbarkeit, Aufzählbarkeit und Entscheidbarkeit
o Unlösbare Probleme
Komplexitätstheorie
o Konkrete Komplexitätsanalyse
o Komplexitätsklassen
o Handhabbarkeit: das P - NP Problem
o NP-vollständige Problem
o Jenseits von NP-vollständigkeit
o Pseudopolynomielle und approximierende Algorithmen
o Probabilistische Lösung nichthandhabbarer Probleme
In der Vorlesung werden die zentralen Konzepte der theoretischen Informatik vorgestellt und an Beispielen illustriert. Die in der Vorlesung verwendeten Folien werden auf den Servern des Lehrgebiets (wenn möglich 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 5-Minuten "Quiz" zur Überprüfung eigener Kenntnisse, durch Diskussion von Fragen zur Vorlesung, und durch die Korrektur von Lösungen zu Hausaufgaben. Die Übungsblätter werden wöchentlich herausgegeben.
Das Tutorium 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
Die Übungsblätter werden wöchentlich als pdf-Dateien bereitgestellt. Jedes Übungsblatt enthält ein Quiz, Präsenzaufgaben und Hausaufgaben. Das Quiz und die Präsenzaufgaben sollen während der wöchentlichen Übungen bearbeitet werden. Aufgaben, für die in den Übungen die Zeit nicht ausreicht, empfehlen wir zum Selbststudium.
Die Hausaufgaben werfen Sie bitte bis zum jeweiligen Abgabetermin in den gekennzeichneten Schrank im Foyer des ersten Stocks im Informatik-Gebäude. Die korrigierten Hausaufgaben erhalten Sie dann ein bis zwei Wochen später in Ihrer Übungsgruppe zurück. Zu einigen ausgewählten Aufgaben werden wir Ihnen auf dieser Seite Musterlösungen anbieten.
Sie werden nur dann zur Klausur zugelassen, wenn Sie am Ende des Semesters mindestens 50% der Punkte in den Hausaufgaben erreicht haben (siehe auch Schein/Klausur).
Nutzen Sie die Sprechstunden der Veranstalter und der Tutoren, falls Sie Fragen zu den Hausaufgaben haben.
Literatur
: J. Hopcroft, R. Motwani, J. Ullman: Einführung in die Automatentheorie, Formale Sprachen und Komplexitätstheorie. Pearson 2002
Folien der Vorlesung. / G. Vossen, K.-U. Witt: Grundkurs Theoretische Informatik. 3. Auflage, Vieweg 2004 /
M. Sipser: Introduction to the Theory of Computation. PWS 1997 (weitere Angaben siehe Link)
Lern- und Lehrformen
2 SWS Vorlesung; 2 SWS Übung
Leistungserfassung
Klausur am Ende des Semesters bei Zulassung (s.o.)
Termine
Vorlesung: Die 11.00-12.30 Uhr, HPI HS 1
Übung:
HPI-G1 Di 13.30-15.00Uhr HPI A1.1
HPI-G2 Di 15.15-16.45Uhr HPI A1.1
HPI-G3 Do 13.30-15.00Uhr (Institut f Inform. 03.04.0.02)
Einteilung in die Übungsgruppen mit der Belegung (ab 10.April möglich) durch Eintragung auf ausliegende Listen bei Frau Pamperin
Tutorium:
Mi 15.15.-16.45Uhr HS 1 an den Terminen 26.04; 10.05; 24.5; 7.6; 21.6; 5.7; 19.7
Aktualisierungen unter
http://www.cs.uni-potsdam.de/ti/lehre/06-Theorie-II/uebungen.html
Zurück
