EntwurfRZ
Inhaltsverzeichnis |
Problemklassifizierung
Einleitung
Jegliche Klassifizierung betrachtet immer gleichartige Dinge die ein gemeinsames Merkmal aufweisen.
Ein solches Merkmal sollte bei den betrachteten Dingen sehr unterschiedlich ausgeprägt sein, um Kategorien/Klassen bilden zu können.
Bei den Rest-Klassen in der Zahlentheorie z.B. werden Zahlen klassifiziert. Der Modulo bezüglich eines festgelegten Divisors ist das Klassifizierungsmerkmal.
Es lassen sich also Klassen von Zahlen bilden, die ein gemeinsames Merkmal haben: den gleichen Rest bei einem bestimmten Divisor.
Aber welches Merkmal weisen alle Probleme auf und könnte der Klassifizierung dienen?
Das wohl relevanteste Merkmal eines jeden Problems ist der Aufwand den die Lösung des Problems erfordert.
Die Einteilung in Komplexitätsklassen ..
>>Grafik empirische Analyse
Bei so abstrakten Dingen wie "Problemen" stellt sich außerdem die Frage ob diese überhaupt gleichartig und damit klassifizierbar sind.
Es gibt verschiedene Arten von Problemen: Suchprobleme wie "Finde die Knoten mit dem größten Grad in einem Graphen" oder Optimierungsprobleme wie "Wieviele verschiedene Farben sind zur Einfärbung deutschen Bundesländer notwendig" oder Entscheidungsprobleme wie "Ist ein Wort ein Palindrom".
Alle Probleme erweisen sich aber bei genauerer Betrachtung als Entscheidungsprobleme...
>>Tabelle
Da die Gleichartigkeit nun festgestellt ist, müssen bei weitergehender theoretischer Betrachtung also nur Entscheidungsprobleme berücksichtigt werden, um pauschale Aussagen machen zu können. Außerdem erlaubt diese Feststellung, dass auf Entscheidungen basierende Konzepte wie Grammatiken und Automaten ohne Einschränkungen für die Klassifizierung verwendet werden können.
- Zusammenfassung
- Bei der Problemklassifizierung werden Probleme nach ihrem Aufwand in Kategorien eingeordnet. Da nur Algorithmen belegbare Aufwände aufweisen, wird der beste bekannte Algorithmus zur Lösung des Problems als Grundlage verwendet.
Die Klasse P
- Definition
- P ist die Klasse aller Probleme, die mit deterministischen Algorithmen in polynomialer Zeit gelöst werden können.
Polynomiale Zeit?
In der Mathematik ist ein Polynom ein Term, der nur aus Summen und Produkten zusammengesetzt ist z.B. a+b*b.
Wenn die Laufzeit eines Algorithmus bezüglich einer Problemgröße n mit einem solchen Polynom ausgedrückt werden kann, dann ist es der Klasse P zuzuordnen.
Welche der folgenden Komplexitäten lassen auf Zugehörigkeit zur Klasse P schließen?
| a) | \mathcal{O}(1) |
| b) | \mathcal{O}(n) |
| c) | \mathcal{O}(log(n)) |
| d) | \mathcal{O}(\frac{2n}{n-1}) |
| e) | \mathcal{O}(n^2) |
| f) | \mathcal{O}(n\:log(n)) |
| g) | \mathcal{O}(n^{1000000}) |
| h) | \mathcal{O}(1^n) |
Lösung
Alle
Deterministisch Der Algorithmus zur Lösung des Problems geht ohne Umwege den kürzesten Weg zum Ziel.
- Zusammenfassung
- Durch die Klasse P werden die praktisch effizient lösbaren Probleme zusammengefasst. Dazu wird eine obere Schranke in Form eines Polynoms definiert und Determinismus gefordert, so dass nur Probleme in die Klasse fallen, deren Aufwand im Verhältnis zur Problemgröße ein bestimmtes Maß nicht übersteigt.
Die Klasse EXPTIME
- Definition
- EXPTIME ist die Klasse aller Probleme, die mit deterministischen Algorithmen in \mathcal{O}(2^{p(n)}) gelöst werden können, wobei p(n) eine Polynomfunktion von n ist.
Da p(n) auch 0 sein kann ist die Klasse EXPTIME damit eine Übergruppierung. Das bedeutet, dass P in EXPTIME enthalten ist. P ist dabei eine echte Teilmenge (P\subset EXPTIME), denn P ist nach oben begrenzt und es existieren nachweislich Probleme die nur von Algorithmen mit Aufwänden oberhalb dieser Schranke gelöst werden können.
- Beispiel
- Wieviele Untermengen der Menge von Zahlen M=\{x_1,x_2,\dots,x_n\} lassen sich bilden, deren Summe 0 ergibt?
- Es müssen alle Untermengen geprüft werden (Potenzmenge |P(M)|)
- |P(M)| = 2^{|M|} = 2^n \Rightarrow \mathcal{O}(2^n)
Für Probleme die einen höheren Aufwand als den exponentiellen für ihre Lösung erfordern, können beliebig Klassen der Form X-EXPTIME formuliert werden. Probleme mit doppelt exponentiellen Aufwand (\mathcal{O}(2^{n^{n}})) werden so der Klasse 2-EXPTIME zugeordnet. Analog kann die Klassenformulierung für höhere Aufwände nach dem gleichen Schema fortgesetzt werden. Die jeweilige Klasse wird in entsprechender Exponentationsstufe immer durch eine Polynomfunktion von n begrenzt.
- Zusammenfassung
- Alle lösbaren Probleme werden durch die EXPTIME-Klassen abgedeckt. P ist eine echte Teilmenge von EXPTIME.
Durch die Klassen EXPTIME und P sind alle lösbaren Problem im Prinzip vollständig klassifiziert. Eine weitere Klasse zwischen EXPTIME und P kann jedoch nicht mehr über den rein deterministischen Aufwand zur Problemlösung gebildet werden. Um trotzdem die "einfachereren" von den "schwierigen" EXPTIME Problemen abzugrenzen wird ein weiteres Merkmal zur Klassifizierung herangezogen: der Nichtdeterminismus.
Die Klasse NP
- Definition
- NP ist die Klasse aller Probleme, die mit nichtdeterministischen Algorithmen in polynomialer Zeit gelöst werden können.
Die Ähnlichkeit zur Definition der Klasse P suggeriert eine Verwandschaft der beiden Klassen. Aber die Klassen basieren auf unterschiedlichen Merkmalen.
