Wiederholungsprüfung Komplexitätstheorie

Viele Konzepte der strukturellen Komplexitätstheorie stammen ursprünglich aus der Rekursionstheorie. Dort befasste man sich mit der Frage, welche Probleme überhaupt algorithmisch lösbar sind. Außerdem bemühte man sich, die unlösbaren Probleme zu klassifizieren. In der Komplexitätstheorie fragt man nun danach, welche Probleme mit vertretbarem Aufwand gelöst werden können. Dabei hat sich inzwischen die Übereinstimmung ergeben, dass ein Problem mit vertretbarem Aufwand gelöst werden kann, wenn es in polynomialer Rechenzeit gelöst werden kann. Dies führte zur Klasse P. Man bemühte sich nun, die Probleme zu klassifizieren, die nicht in P zu liegen scheinen. Bei diesen Untersuchungen hat man viele Konzepte aus der Rekursionstheorie auf den subrekursiven Bereich übertragen. Die dabei aufgetretenen Fragen und Probleme zählen vielfach zu den bedeutensten der (theoretischen) Informatik. Sie berühren unmittelbar unser Verständnis von dem, was algorithmisch mit vertretbarem Aufwand gelöst werden kann. Die Vorlesung ist wie folgt aufgebaut: * Kapitel 1: Turing Maschinen Das benutzte Rechnermodell wird vorgestellt, und Rechenzeit- und Speicherplatzbedarf werden als Komplexitätsmaße eingeführt. * Kapitel 2: Probleme mit hoher Komplexität: Optimierungsprobleme versus Spracherkennungsprobleme, polynomielle Reduktionen zur Herleitung unterer Schranken, NP-vollständige Probleme. * Kapitel 3: Der Einsatz der NP-Vollständigkeit bei der Analyse von Problemen: Analyse von Teilproblemen, starke NP-Vollständigkeit und NP-Schwierigkeit als untere Schranke. * Kaptiel 4: Techniken zur Lösung NP-vollständiger Probleme: Approximationsalgorithmen und NP-Vollständigkeit, Probabilistische Algorithmen. - J.L. Balcazar, J. Diaz, J. Gabborro: Structural Complexity, I und II EATCS Monographs on Theoretical Computer Science, Vol. 11 und 22, Springer, 1988. - M.R. Garey, D.S. Johnson: Computers and Intractability - A Guide to the Theory of NP-Completeness Freeman, San Francisco, 1979. - J.E. Hopcraft, J.D. Ullman: Introduction to Automata Theory, Languages and Computation Addison-Wesley, 1979. - K.R. Reischuk: Komplexitaetstheorie, Band I: Grundlagen Teubner, Stuttgart, 1999. Voraussetzungen Theoretische Informatik I oder entsprechende Kenntnisse Leistungsnachweis Mündliche Prüfung am Ende des Semesters. Aktive Teilnahme an den Übungen sowie erfolgreiche Bearbeitung der wöchentlichen Übungsaufgaben sind Voraussetzungen für die Zulassung zur Abschlussprüfung. FB 16 Elektrotechnik / Informatik Theoretische Informatik I oder entsprechende Kenntnisse Mündliche Prüfung am Ende des Semesters. Aktive Teilnahme an den Übungen sowie erfolgreiche Bearbeitung der wöchentlichen Übungsaufgaben sind Voraussetzungen für die Zulassung zur Abschlussprüfung. Uni Kassel WiSe 2011/12 Informatik Mathematik Professor Otto Friedrich Professor