Theoretische Informatik II Universität Potsdam, Sommersemester 2009

Zielstellung

Die Lehrveranstaltung Theoretische Informatik II bietet eine Einführung die Berechenbarkeitstheorie und Komplexitätstheorie.

Während der ersten Hälfte des 20. Jahrhunderts entdeckten Mathematiker wie Kurt Gödel, Alan Turing und Alonzo Church, dass bestimmte grundlegende Probleme nicht mit Computern gelöst werden können. Ein Beispiel für dieses Phänomen ist das Problem, zu bestimmen, ob eine beliebige mathematische Aussage wahr oder falsch ist. Die Beschäftigung mit dieser Frage erforderte die Entwicklung eines präzisen Algorithmenbegriffs. Dieser Begriff ermöglicht es, in der Berechenbarkeitstheorie Fragen nach den prinzipiellen Grenzen von Computern zu untersuchen.

Wo die Berechenbarkeitstheorie nur nach der grundsätzlichen Lösbarkeit von Problemen fragt, ist es das Anliegen der Komplexitätstheorie, Probleme danach zu klassifizieren, ob sie einfach oder aufwändig zu lösen sind. Dazu werden Konzepte entwickelt, mit denen der Schwierigkeitsgrad eines Problems charakterisiert werden kann. Interessanterweise ist die zentrale Frage der Komplexitätstheorie, welche Eigenschaften eines Problems darüber entscheiden, ob das Problem algorithmisch handhabbar ist, bislang weitgehend ungeklärt.

Gliederung der Theoretischen Informatik II

Lehrveranstaltungen

Datenschutzerklärung · XHTML · CSS  Letzte Änderung:  tim at-Zeichen cs Punkt uni-potsdam Punkt de,  12.04.2009