Veranstaltungs-Nr.:	18.216 

Titel:	KomplexitŠtstheorie

Veranstalter:	Matthias Jantzen 

Zeit / Ort:	Di 10-12,   C-221

Lernziel:	
Die Vorlesung soll in das Gebiet der (strukturellen)
KomplexitŠtstheorie einfŸhren und gleichzeitig die in dieses Gebiet
fallenden und schon in anderen Vorlesungen erworbene Kenntnisse der
Teilnehmer(innen) vertiefen und erweitern. Weiterhin sollen einige
neuere Ergebnisse der KomplexitŠtstheorie und Forschungsschwerpunkte,
die in letzter Zeit in den Vordergrund der KomplexitŠtstheorie getreten
sind, vorgestellt werden. 

Inhalt:	
In der KomplexitŠtstheorie
beschŠftigt man sich im wesentlichen mit der Frage, welcher Aufwand an
Rechenzeit und Speicherplatz erforderlich ist, um ein gegebenes Problem
zu lšsen. Besonders interessiert ist man natŸrlich an unteren Schranken
fŸr ein Problem, also an der Menge an Betriebsmitteln wie Rechenzeit
oder Speicherplatz, die mindestens gebraucht wird, um das Problem zu
lšsen. Leider stellt sich diese Fragestellung in den allermeisten FŠllen
als zu schwer heraus, so dass man in der KomplexitŠtstheorie dazu
Ÿbergegangen ist, verschiedene Probleme miteinander zu vergleichen, um
so wenigstens eine Aussage Ÿber deren relative KomplexitŠten zu
bekommen. 

In der Vorlesung sollen zentrale, grundlegende Konzepte der
strukturellen KomplexitŠtstheorie prŠsentiert werden (Platzklassen,
Zeitklassen, Reduktionen, VollstŠndigkeit etc.). Ziel ist es dabei, eine
Vorstellung davon zu vermitteln, dass und inwiefern die strukturelle
KomplexitŠtstheorie einen Klassifikationsrahmen fŸr entscheidbare
Probleme liefert. 

Stell. im Studienplan:	
Hauptstudium, [SP:BV, SV, WV, SEM, eigenes Theorie-Profil; VG: Th2, Th3, P3, P5]

Voraussetzungen:	Grundstudium 

Vorgehen:	Vorlesung

Literatur:	J.E. Hopcroft, J.D. Ullman: Introduction to Automata
Theory, Languages, and Computation, Addison-Wesley Publishing Company,
Reading, Mass., 1979. J.L. Balcazar, J. Diaz, J. Gabarro:  Structural
Complexity I . Springer-Verlag, Berlin-Heidelberg-New York, 1988. K.R.
Reischuk. EinfŸhrung in die KomplexitŠtstheorie. B. G. Teubner,
Stuttgart, 1990. C. Papadimitriou. Computational Complexity. Addison-
Wesley Publishing Company, Reading, Mass., 1994. I. Wegener:
KompexitŠtstheorie, Springer-Verlag, Berlin-Heidelberg-New York, 2003.

PeriodizitŠt:	unregelmŠ§ig 
FŸr LehrerInnen nicht / fŸr NebenfŠchlerInnen geeignet.