Hasso-Plattner-Institut
Hasso-Plattner-Institut
  
Login
  • de
 

Theoretische Informatik II (Sommersemester 2006)

Dozent: Prof. Dr. Christoph Kreitz

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 Dieses Buch bildet den Leittext für diese Veranstaltung.

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

 

        

Allgemeine Information

  • Semesterwochenstunden : 4
  • ECTS : 6
  • Benotet : Ja
  • Einschreibefrist : 05.05.2006
  • Programm : IT-Systems Engineering BA
  • Lehrform :
  • Belegungsart : Pflicht

Zurück