Lehrveranstaltung im Sommersemester 2009

Theoretische Informatik 2

Kurs (4 SWS, 2VL+2Ü) im Informatik-Grundstudium

(VAK 03-601.02, ECTS 6)

Die Lehrveranstaltung beginnt mit einer Einführung in die Komplexitätstheorie. Dabei geht es vor allem um die Frage, wie schnell Lösungen von Datenverarbeitungsproblemen ausführbar sind. Für diesen Zweck wird die formale Spezifikationssprache CE-S eingeführt, die es erlaubt, Algorithmen auf Zeichenketten zu modellieren, als korrekt nachzuweisen und ihren Berechnungsaufwand zu ermitteln. Außerdem werden grundlegende Probleme der Berechenbarkeit und der formalen Sprachen, wie sie aus Theoretischer Informatik 1 bekannt sind, aufgegriffen und näher behandelt. Insbesondere spielt das Wortproblem eine wichtige Rolle, und es werden drei Berechnungsmodelle (while-Programmierung, CE-S und Turing- Maschinen) miteinander verglichen.
Dieses Modul ist als Wahlpflicht in der Theorie-Säule des Diplom-Grundstudiums der Informatik geeignet. Nach der neuen Bachelor-Prüfungsordnung ist es für Bachelor-Studierende Pflicht. Es wird insbesondere für das vierte Semester empfohlen, weil die zeitliche Belastung im zweiten Semester nach dem Studienplan bereits sehr groß ist. Inhaltlich passt das Modul auch ins zweite Semester. Es gibt ein Skript

Termine
Vorlesung: 2 SWS Mo von 10:15 - 11:45 NW2 Stufenhörsaal (A0242)
Übungen: 2 SWS (Beginn: 14.4.)
- Mo von 15:15 - 16:45 MZH 7250,
- Di von 08:30 - 10:00 MZH 7220,
- Di von 10:15 - 11:45 MZH 7220,
- Di von 10:15 - 12:45 MZH 7050,
- Mi von 08:15 - 9:45 MZH 7210,
- Mi von 10:15 - 11:45 MZH 4194
- Do von 08:15 - 9:45 MZH 7210,
TutorInnen
- Marcus Ermler (maermler@informatik.uni-bremen.de)
- Dr. Stefan Göller (goeller@informatik.uni-bremen.de)
- Dr. Sabine Kuske (kuske@informatik.uni-bremen.de)

Skript
Folien: CE-S, Aufwand, Aufwandsklassen, Aufwand von Matrizenmultiplikation, Grammatiken, Turingmaschinen, Entscheidungsprobleme
Aufgabenblätter: Blatt 1, Blatt 2, Blatt 3, Blatt 4, Blatt 5
Fragenkatalog
Videoaufzeichnungen der Vorlesung vom Sommersemester 2008


	Research Group Theoretical Computer Science
	Lehrveranstaltung im Sommersemester 2009 Theoretische Informatik 2 Kurs (4 SWS, 2VL+2Ü) im Informatik-Grundstudium (VAK 03-601.02, ECTS 6) Die Lehrveranstaltung beginnt mit einer Einführung in die Komplexitätstheorie. Dabei geht es vor allem um die Frage, wie schnell Lösungen von Datenverarbeitungsproblemen ausführbar sind. Für diesen Zweck wird die formale Spezifikationssprache CE-S eingeführt, die es erlaubt, Algorithmen auf Zeichenketten zu modellieren, als korrekt nachzuweisen und ihren Berechnungsaufwand zu ermitteln. Außerdem werden grundlegende Probleme der Berechenbarkeit und der formalen Sprachen, wie sie aus Theoretischer Informatik 1 bekannt sind, aufgegriffen und näher behandelt. Insbesondere spielt das Wortproblem eine wichtige Rolle, und es werden drei Berechnungsmodelle (while-Programmierung, CE-S und Turing- Maschinen) miteinander verglichen. Dieses Modul ist als Wahlpflicht in der Theorie-Säule des Diplom-Grundstudiums der Informatik geeignet. Nach der neuen Bachelor-Prüfungsordnung ist es für Bachelor-Studierende Pflicht. Es wird insbesondere für das vierte Semester empfohlen, weil die zeitliche Belastung im zweiten Semester nach dem Studienplan bereits sehr groß ist. Inhaltlich passt das Modul auch ins zweite Semester. Es gibt ein Skript Termine Vorlesung: 2 SWS Mo von 10:15 - 11:45 NW2 Stufenhörsaal (A0242) Übungen: 2 SWS (Beginn: 14.4.) Mo von 15:15 - 16:45 MZH 7250, Di von 08:30 - 10:00 MZH 7220, Di von 10:15 - 11:45 MZH 7220, Di von 10:15 - 12:45 MZH 7050, Mi von 08:15 - 9:45 MZH 7210, Mi von 10:15 - 11:45 MZH 4194 Do von 08:15 - 9:45 MZH 7210, TutorInnen Marcus Ermler (maermler@informatik.uni-bremen.de) Dr. Stefan Göller (goeller@informatik.uni-bremen.de) Dr. Sabine Kuske (kuske@informatik.uni-bremen.de) Skript Folien: CE-S, Aufwand, Aufwandsklassen, Aufwand von Matrizenmultiplikation, Grammatiken, Turingmaschinen, Entscheidungsprobleme Aufgabenblätter: Blatt 1, Blatt 2, Blatt 3, Blatt 4, Blatt 5 Fragenkatalog Videoaufzeichnungen der Vorlesung vom Sommersemester 2008	Mail Address University of Bremen Dept. for Math. & Computer Science P.O. Box 330 440 28334 Bremen Germany Physical Address Linzer Strasse 9a OAS 3002 28359 Bremen Phone ++49 (421) 218 3697 Fax ++49 (421) 218 4322 Email (Secr.) Helga Reinermann helga@tzi.de
		© / 23.06.09