Vorlesung: Theoretische Informatik (Informatik IV)

VL: Theoretische Informatik (Informatik IV)

VL 12043

Theoretische Informatik (Informatik IV)

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

Freitags, 9:15-11:00 Uhr, HG 113 (Biegenstrasse)

Beginn: 23. 4. 2003

UE 12044

Tutor(in)	Termin	Raum	Infos
Björn Struckmeier	Mi, 14-16 Uhr	Seminarraum VIII (Ebene A6, Lahnberge)
Gjergji Kasneci	Mi, 14-16 Uhr	Hörsaal II (Edene D3, Lahnberge)
Raphael Bürger	Mi, 16-18 Uhr	Seminarraum IV (Ebene D5, Lahnberge)
Philipp Imhof	Mi, 16-18 Uhr	Seminarraum VIII (Ebene A6, Lahnberge)	Die Übung vom 25.6. wird auf Dienstag, den 24.6., 11-13 Uhr, SR III vorverlegt.
Jiaen Guo	Do, 14-16 Uhr	Seminarraum VIII (Ebene A6, Lahnberge)
Dorian Dai	Do, 16-18 Uhr	Seminarraum VIII (Ebene A6, Lahnberge)
Ivo Pacák	Fr, 14-16 Uhr	Seminarraum VIII (Ebene A6, Lahnberge)
Jost Berthold	Fr, 14-16 Uhr	Seminarraum V (Ebene D5, Lahnberge)

Hinweis: Falls donnerstags ein Feiertag ist, finden die Übungen am darauffolgenden Montag 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

Scheinkriterien: Unbenoteter Leistungsnachweis:

Regelmässige und aktive Teilnahme an den Übungen
Vorrechnen mindestens einer mündlichen Aufgabe
Erwerb von mindestens 50% der erreichbaren Punkte in den Übungsaufgaben
höchstens zwei unbearbeitete Zettel
mind. 26 Punkte aus den beiden Leistungskontrollen (inkl. Zusatzpunkten aus dem Vorrechnen mündlicher Aufgaben)
Benoteter Leistungsnachweis: Zusätzlich Bestehen der Klausur am Semesterende

Übungsablauf:

Ausgabe der Übungszettel mittwochs in der Vorlesung

Abgabe in Zweiergruppen möglich

Abgabe und Rückgabe erfolgt in den Übungsgruppen

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

Termine:

1. Leistungskontrolle: Freitag, 23. Mai 2003, 9:15 Uhr
Die Ergebnisse der 1. Leistungskontrolle sind gegenüber dem Informatik-Sekretariat auf Ebene D5 (Lahnberge) ausgehängt.

2. Leistungskontrolle: Freitag, 20. Juni 2003, 9:15 - 9:45 Uhr
Die Ergebnisse der 2. Leistungskontrolle sind gegenüber dem Informatik-Sekretariat auf Ebene D5 (Lahnberge) ausgehängt.

Klausur: Mittwoch, 16. Juli 2003, 8.00 Uhr - 10.00 Uhr, HG 214 (Audimax), Biegenstraße 14
Wegen der Klausurkorrektur fällt die Vorlesung am Mittwoch, dem 16. Juli 2003 aus!
Die Klausurergebnisse werden am Donnerstag, dem 17. Juli, nachmittags durch Aushang auf der Ebene D5 (gegenüber dem Informatik-Sekretariat) bekanntgegeben. Von 116 Teilnehmern haben 57 bestanden.
Klausureinsicht und -rückgabe: Dienstag, den 22. Juli 2003, 13:30 - 14:15 Uhr, Seminarraum V, Ebene D5, Lahnberge

Nachholklausur: Donnerstag, 14. August 2003, 9:15 - 11:15 Uhr, Hörsaal A im Hörsaalgebäude der Chemie, Lahnberge
Die Ergebnisse der Nachholklausur sind gegenüber dem Informatik-Sekretariat auf Ebene D5 (Lahnberge) ausgehängt. Von 48 Teilnehmern haben 19 bestanden.
Klausureinsicht und -rückgabe: Dienstag, den 19. August 2003, 13:30 - 14:00 Uhr, Seminarraum V, Ebene D5, Lahnberge
Die benoteten und die unbenoteten Scheine sowie die Klausuren können ab Mittwoch, 20. August 2003, im Informatik-Sekretariat auf Ebene D5 abgeholt werden.

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) 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)
Übungsblätter:	Blatt 1 (.ps, .pdf)
	Blatt 2 (.ps, .pdf)
	Blatt 3 (.ps, .pdf)
	Blatt 4 (.ps, .pdf)
	Blatt 5 (.ps, .pdf)
	Blatt 6 (.ps, .pdf)
	Blatt 7 (.ps, .pdf)
	Blatt 8 (.ps, .pdf)
	Blatt 9 (.ps, .pdf)
	Blatt 10 (.ps, .pdf)
	Blatt 11 (.ps, .pdf)
	Blatt mit Wiederholungsaufgaben (.ps, .pdf)
	Blatt 12 (.ps, .pdf)
Links:	Fleißige Biber

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

Die Klassen P und NP
NP-Vollständigkeit

Zuletzt geändert: Tuesday, 19-Aug-2003 18:00:29 CEST

Voraussetzungen:	Mathematische Grundkenntnisse, wie sie etwa in der Vorlesung Mathematik I vermittelt werden
Querverbindungen:	Theoretische Informatik, Software- und Systementwurf, Compilerbau
Scheinkriterien:	Unbenoteter Leistungsnachweis: Regelmässige und aktive Teilnahme an den Übungen Vorrechnen mindestens einer mündlichen Aufgabe Erwerb von mindestens 50% der erreichbaren Punkte in den Übungsaufgaben höchstens zwei unbearbeitete Zettel mind. 26 Punkte aus den beiden Leistungskontrollen (inkl. Zusatzpunkten aus dem Vorrechnen mündlicher Aufgaben) Benoteter Leistungsnachweis: Zusätzlich Bestehen der Klausur am Semesterende
Übungsablauf:	Ausgabe der Übungszettel mittwochs in der Vorlesung Abgabe in Zweiergruppen möglich Abgabe und Rückgabe erfolgt in den Übungsgruppen Abgabe von abgeschriebenen Lösungen ergibt 0 Punkte für die Kopien und das Original