Wofür braucht man eigentlich diese Komplexitätsklassen?

von Torben Scheffel

Zu diesem Talk wurde kein Video veröffentlicht.

11.11.2016

Dieser Vortrag beschäftigt sich mit Komplexitätsklassen und insbesondere deren Nutzen. Folgende Punkte werden behandelt:

• Was sind Komplexitätsklassen und wofür sind diese da? Dabei werden auch für den Vortrag nötige Grundlagen nochmal wiederholt und es soll Intuition für deren Benutzung geschaffen werden.
• Es werden verschiedene Komplexitätsklassen vorgestellt. Dazu gehören sehr bekannte wie P, NP und PSPACE aber auch auf exotischere Klassen wird eingegangen.
• Es wird auf den Nutzen von Komplexitätsklassen eingegangen. Insbesondere soll dabei auch der mögliche Nutzen von Komplexitätsklassen in der Praxis bzw. beim Programmieren erläutert werden.
• Welche offenen Forschungsfragen gibt es?

Es sollten die Grundlagen aus der Vorlesung “Theoretische Informatik” bekannt sein. Genauer genommen heißt dies, man sollte das Wort “Komplexitätsklassen” schon einmal gehört haben, muss sich aber nicht mehr genau daran erinnern, wie diese funktionieren. Benötigte Grundlagen werden im Vortrag wiederholt.

Lizenz:
This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License (CC BY NC ND 4.0).

Melden