EntwurfRZ

Wiki-Quelltext dieser Seite.

=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.

==Die Klasse P==
<div style= "background-color:#F5D0A9; padding:10px">
;Definition: P ist die Klasse aller Probleme, die mit deterministischen Algorithmen in polynomialer Zeit gelöst werden können.
</div>
===Polynomiale Zeit?===
Polynom ist aus dem Griechischen abgeleitet und bedeutet "mehrnamig".
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 der Klasse P zuzuordnen.
Welche der folgenden Komplexitäten lassen auf Zugehörigkeit zur Klasse P schließen?<br>
a) $\mathcal{O}(1)$<br>
b) $\mathcal{O}(n)$<br>
c) $\mathcal{O}(log(n))$<br>
d) $\mathcal{O}(\frac{2n}{n-1})$<br>
e) $\mathcal{O}(n^2)$<br>
f) $\mathcal{O}(n log{n})$<br>
g) $\mathcal{O}(n^{1000000})$<br>
h) $\mathcal{O}(1^n)$<br>
<popup name="Lösung">
Alle
<popup>


==Die Klasse EXPTIME==
==Die Klasse NP==
==P=NP?==
==Polynomiale Reduktion==
==NP-Schwere==
==NP-Vollständigkeit==
==Satz von Steven A. Cook==