Vorlesung: Theoretische Informatik (Informatik IV)

VL: Theoretische Informatik (Informatik IV)

VL 12054

Theoretische Informatik (Informatik IV)

Prof. Dr. R. Loogen

Dienstags, 11:15-13:00 Uhr, HG 5 (Biegenstrasse)

Mittwochs, 11:15-13:00 Uhr, HG 113 (Biegenstrasse)

Beginn: 12. April 2005

UE 12055

Beginn: 2. Vorlesungswoche

Tutor(in)	Termin	Raum	Infos
Philipp Imhof	Mi, 14-16 Uhr	Seminarraum V (Ebene D5, Lahnberge)	Tutoriumsseite
Matthias Schmidt	Mi, 14-16 Uhr	Seminarraum II (Edene D3, Lahnberge)
Michael Heidt	Do, 14-16 Uhr	Hörsaal II (Ebene D3, Lahnberge)
Carina M. Ringler	Do, 16-18 Uhr	Hörsaal II (Ebene D3, Lahnberge)
Ivo Pacák	Fr, 14-16 Uhr	Seminarraum II (Ebene D3, Lahnberge)	Tutoriumsseite

Hinweis: Falls donnerstags ein Feiertag ist, finden die Übungen am darauffolgenden Montag im Hörsaal I, Ebene D3, Lahnberge statt.

Fachgebiet	Klassifikation	Semester	Fortsetzung	Skript
Informatik	Grundstudium	>= 2	nein	nein

Voraussetzungen: Mathematische Grundkenntnisse, wie sie etwa in der Vorlesung Mathematik I vermittelt werden

Querverbindungen: Theoretische Informatik, Software- und Systementwurf, Compilerbau, Effiziente Algorithmen

Scheinkriterien: Unbenoteter Leistungsnachweis:

Regelmäßige und aktive Teilnahme an den Übungen
Vorrechnen von mindestens zwei Aufgaben
Erwerb von mindestens 50% der erreichbaren Punkte in den Übungsaufgaben
höchstens zwei unbearbeitete Zettel
mind. 25 Punkte aus den beiden Leistungskontrollen (inkl. Zusatzpunkten aus dem Vorrechnen mündlicher Aufgaben)
Durch das Vorrechnen von mündlichen Aufgaben in den Übungsgruppen können pro vollständig und richtig vorgerechneter mündlicher Aufgabe 2 Sonderpunkte erworben werden, mit denen der Punktestand aus den Leistungskontrollen aufgestockt werden kann. Die Beschränkung auf maximal 10 Sonderpunkte entfällt.
Benoteter Leistungsnachweis: Zusätzlich Bestehen der Klausur am Semesterende
Achtung: Unbenotete Leistungsnachweise aus Vorjahren werden nicht anerkannt!

Übungsablauf:

Die Ausgabe der Übungszettel und die Abgabe der Hausaufgaben erfolgen dienstags vor der Vorlesung.

Die Abgabe ist in Zweiergruppen möglich.

Die Rückgabe und Besprechung findet in den Übungsgruppen statt.

Abgabe von abgeschriebenen Lösungen ergibt 0 Punkte für die Kopien und das Original

Termine:

1. Leistungskontrolle: Dienstag , 10. Mai 2005, 11:15 - 11:40 Uhr, HG 5
2. Leistungskontrolle: Dienstag, 7. Juni 2005, 11:15 - 12:00 Uhr, HG 5
Die Ergebnisse der 2. Leistungskontrolle sind gegenüber dem Informatik-Sekretariat auf Ebene D5 (Lahnberge) ausgehängt.

Klausur: Dienstag, 12. Juli 2005, 11.15 Uhr - 13.15 Uhr, HG 214 (Audimax), Biegenstraße 14
Klausureinsicht und -rückgabe: Dienstag, 19. Juli 2005, 11 - 12 Uhr, Seminarraum V (Ebene D5, Lahnberge)
Das Klausurergebnis ist durch Aushang auf der Ebene D5 (gegenüber dem Informatik-Sekretariat) bekanntgegeben. Von 74 Teilnehmern haben 31 bestanden.
Es ergab sich folgendes Notenspektrum:
| 1,0 | 1,3 | 1,7 | 2,0 | 2,3 | 2,7 | 3,0 | 3,3 | 3,7 | 4,0 | |-----|-----|-----|-----|-----|-----|-----|-----|-----|-----| | 2 | 1 | 2 | 1 | 2 | 1 | 2 | 1 | 5 | 14 |
Die benoteten Scheine können ab Donnerstag, 21. Juli 2005, im Informatik-Sekretariat auf Ebene D5 abgeholt werden.

Nachholklausur: Neu! Dienstag, 30. August 2005, 9.00-11.30 Uhr, HG 114 (Hörsaalgebäude, Biegenstraße)
Klausureinsicht und -rückgabe: Dienstag, 6. September 2005, 11.00 - 11.45 Uhr, Seminarraum V (Ebene D5, Lahnberge)
Das Klausurergebnis ist durch Aushang auf der Ebene D5 (gegenüber dem Informatik-Sekretariat) bekanntgegeben. Zum Bestehen der Klausur sind 32 Punkte erforderlich. Von 36 Teilnehmern haben 12 bestanden.

Übungsblätter:	Blatt 1 (.ps, .pdf), Abgabe: 19.04.2005
	Blatt 2 (.ps, .pdf), Abgabe: 26.04.2005
	Blatt 3 (.ps, .pdf), Abgabe: 03.05.2005
	Blatt 4 (.ps, .pdf), Abgabe: 10.05.2005
	Blatt 5 (.ps, .pdf), Abgabe: 17.05.2005
	Blatt 6 (.ps, .pdf), Abgabe: 24.05.2005
	Blatt 7 (.ps, .pdf), Abgabe: 31.05.2005
	Blatt 8 (.ps, .pdf), Abgabe: 07.06.2005
	Blatt 9 (.ps, .pdf), Abgabe: 14.06.2005
	Blatt 10 (.ps, .pdf), Abgabe: 21.06.2005
	Blatt 11 (.ps, .pdf), Abgabe: 28.06.2005
	Blatt 12 - letztes Blatt(.ps, .pdf), Abgabe: 05.07.2005
	Zum Üben: Klausur aus dem Jahr 2003 (.ps, .pdf), Leistungskontrollen aus diesem Semester (L1.pdf, L2.pdf)

Literatur:	E. Hopcroft, R. Motwani, J.D. Ullman: Einführung in die Automatentheorie, Formale Sprachen und Komplexitätstheorie, 2. überarbeitete Auflage (Pearson-Studium (Addison-Wesley), 2002) U. Schöning: Theoretische Informatik - kurzgefasst (Spektrum Akademischer Verlag, 2001) A. Asteroth, Chr. Baier: Theoretische Informatik, Pearson Studium 2002. M. Broy: Informatik - Eine grundlegende Einführung, Teil IV (Springer-Verlag, 1995) G. Vossen, K.-U. Witt: Grundlagen der Theoretischen Informatik mit Anwendungen (Vieweg-Verlag, 2000) van Leuwwen (Hrsg.): Handbook of Theoretical Computer Science, Vols. A und B, Elsevier, 1990 (Übersichtsartikel zu verschiedenen Themenbereichen)
Links:	Visual Automata Simulator (VAS)
	Programme zur Theoretischen Informatik (Übersichtsseite der Univ. Mainz)

Inhalt:

Automatentheorie und formale Sprachen

Grammatiken, Chomsky-Hierarchie
Endliche Automaten und reguläre Sprachen
Kellerautomaten und kontextfreie Sprachen
Turingmaschinen und rekursiv aufzählbare Sprachen

Berechenbarkeitstheorie

Berechenbarkeitsbegriff, Churchsche These
Unentscheidbarkeit

Komplexitätstheorie

Aufwand von Berechnungen
Die Klassen P und NP
Reduktionen und NP-Vollständigkeit

Zuletzt geändert: Wednesday, 31-Aug-2005 16:47:32 CEST

Voraussetzungen:	Mathematische Grundkenntnisse, wie sie etwa in der Vorlesung Mathematik I vermittelt werden
Querverbindungen:	Theoretische Informatik, Software- und Systementwurf, Compilerbau, Effiziente Algorithmen
Scheinkriterien:	Unbenoteter Leistungsnachweis: Regelmäßige und aktive Teilnahme an den Übungen Vorrechnen von mindestens zwei Aufgaben Erwerb von mindestens 50% der erreichbaren Punkte in den Übungsaufgaben höchstens zwei unbearbeitete Zettel mind. 25 Punkte aus den beiden Leistungskontrollen (inkl. Zusatzpunkten aus dem Vorrechnen mündlicher Aufgaben) Durch das Vorrechnen von mündlichen Aufgaben in den Übungsgruppen können pro vollständig und richtig vorgerechneter mündlicher Aufgabe 2 Sonderpunkte erworben werden, mit denen der Punktestand aus den Leistungskontrollen aufgestockt werden kann. Die Beschränkung auf maximal 10 Sonderpunkte entfällt. Benoteter Leistungsnachweis: Zusätzlich Bestehen der Klausur am Semesterende Achtung: Unbenotete Leistungsnachweise aus Vorjahren werden nicht anerkannt!
Übungsablauf:	Die Ausgabe der Übungszettel und die Abgabe der Hausaufgaben erfolgen dienstags vor der Vorlesung. Die Abgabe ist in Zweiergruppen möglich. Die Rückgabe und Besprechung findet in den Übungsgruppen statt. Abgabe von abgeschriebenen Lösungen ergibt 0 Punkte für die Kopien und das Original