Abteilung Formale Konzepte

Universität Stuttgart
Institut für Informatik
Breitwiesenstr. 20/22
D-70565 Stuttgart
 Lageplan
Stadtplan
Abteilung
Institut
Fakultät
Universität

Vorlesung: Theoretische Informatik II (inf)

Vorlesung2V+1Ü
Dozenten:Claus
Lewandowski, Schmid
Termin:Mittwoch, 8:30 - 10:00 Uhr, Hörsaal V 20.02
Übungen:Gruppe 1: Mittwoch 13.15-14.45 Uhr, Raum 2.026, 8.11., 22.11., 6.12., 20.12., 17.1., 31.1., 14.2.
Gruppe 2: Mittwoch 15.00-16.30 Uhr, Raum 2.026, 8.11., 22.11., mangels Beteiligung zusammen mit Gruppe 5
Gruppe 3: Donnerstag 15.00-16.30 Uhr, Raum 1.035, 9.11., 23.11., 7.12., 21.12., 18.1., 1.2., 15.2.
Gruppe 4: Mittwoch 13.15-14.45 Uhr, Raum 2.026, 15.11., 29.11., 13.12., 10.1., 24.1., 7.2., 14.2.
Gruppe 5: Mittwoch 15.00-16.30 Uhr, Raum 2.026, 15.11., 29.11., 13.12., 10.1., 24.1., 7.2., 14.2.
Gruppe 6: Donnerstag 15.00-16.30 Uhr, Raum 1.035, 16.11., 30.11., 14.12., 11.1., 25.1., 8.2., 15.2.
Einen Übungsschein erhält, wer mindestens 50% der Punkte erreicht (200 Punkte werden auf 7 Übungsblätter und 2 Tests verteilt) und mindestens zweimal in der Übungsgruppe vorgetragen hat.

Bitte HIER in die Listen eintragen!

Übungsblätter

Beschreibung

Wie im ersten Teil der Vorlesung stehen folgende Fragen im Mittelpunkt: Nachdem endliche Akzeptoren/Automaten, Grammatiken und Turingmaschinen eingeführt sind, wenden wir uns nun dem Nicht-Berechenbaren zu. Danach werden „mittelschwere Probleme“ behandelt: Kontextfreie und kontextsensitive Grammatiken und Polynomialzeit-Sprachen. Übungen sind für das Verstehen der Abstraktionen unverzichtbar. Auch stecken viele Probleme im Detail, deren Auswirkungen nur durch effektives Durchrechnen klar werden. Wer nicht übt, bekommt rasch Verständnisprobleme. Geplanter Aufbau des zweiten Teils der Vorlesung 
2.	Aufzählbare Mengen
	2.1 Turingmaschinen
	2.2 Berechenbare Funktionen
	2.3 Grammatiken 
	2.4 Aufzählbarkeit
	2.5 Entscheidbarkeit                              im SS 00
	2.6 Registermaschinen	                          18.10.00
	2.7 Churchsche These	                          25.10.00
3.	Unentscheidbarkeit	                          08.11.00
	3.1 Codierungen und Universelle Turingmaschinen	  08.11.00
	3.2 Halteproblem	                          15.11.00
	3.3 Postsches Korrespondenzproblem	          15.11.00
	3.4 Satz von Rice, nicht-berechenbare Funktionen  22.11.00
4.	Kontextfreie Sprachen	                          29.11.00
	4.1 Normalformen	                          29.11.00
	4.2 Pumping-Lemma, Abschlusseigenschaften	  06.12.00
	4.3 Charakterisierung	                          13.12.00
	4.4 Pushdown Akzeptoren	                          20.12.00
	4.5 deterministischer PDA, LR(k)                  20.12.00
5.	Kontextsensitive Sprachen	                  10.01.01
	5.1 Normalform	                                  10.01.01
	5.2 Linear beschränkte Automaten, Erweiterungstyp 17.01.00
6.	Komplexitätsklassen	                          17.01.01
7.	(NP-)Vollständige Probleme	                  31.01.01
8.	Netze	                                          14.02.01

Prüfung

Die Inhalte von Theorie II werden im Vordiplom als eines von vier Gebieten (Logik, Theorie I, Theorie II, Diskrete Math.) in der Klausur über Theoretische Informatik geprüft. Diese Prüfung ist derzeit schriftlich und dauert 3 Stunden. Sie findet in der Regel am Ende des vierten Semesters statt.

Literatur

Katrin Erk, Lutz Priese, Theoretische Informatik - eine umfassende Einführung,
Springer-Verlag, Berlin, Heidelberg, New York, 2000

J. E. Hopcroft, J. D. Ullman: Introduction to Automata Theory, Languages, and
Computation, Addison-Wesley, seit 1969, diverse Neuauflagen; es gibt auch eine
deutsche Übersetzung

Uwe Schöning: Theoretische Informatik - kurz gefaßt, Spektrum, Heidelberg,
3. Auflage, 1997

Klaus W. Wagner: Einführung in die Theoretische Informatik: Grundlagen und
Modelle, Springer-Verlag, Berlin, Heidelberg, New York, 1994

Ingo Wegener: Theoretische Informatik: Eine algorithmenorientierte Einführung
Teubner-Verlag, Stuttgart, 2. Auflage 1999. Zusätzlich gibt es hierzu ein
erläuterndes Kompendium.

Das Gebiet ist durch Lehrbücher gut aufbereitet, wie folgende Liste von weiteren
Autoren von Theorie-Einführungsbüchern zeigt: L. Balke und K.H.Böhling, H. Becker
und H. Walter, E. Börger, M.A. Harrison, H. Hermes, G. Hotz und K. Estenfeld,
H. Lewis and C. Papadimitriou, R. McNaughton, A. Salomaa, V. Sperschneider und
B. Hammer, F. Stetter, D. Wätjen, K. Weihrauch, D. Wood. Durchstöbern Sie einmal die
Bibliothek und lesen Sie sich in das eine oder andere Buch ein. Mindestens eines der
Bücher sollten Sie sich anschaffen.

Impressum
Last modified: Wed Feb 7 10:23:34 MET 2001