Komplexität Berechenbarkeit

Aus ProgrammingWiki
Archivierte Version vom 2018-09-13T11:00:57+00:00. Aktuelle Version
Komplexität von Sortieralgorithmen

Komplexitätsuntersuchung von Sortieralgorithmen
== Praktisch unlösbare Probleme ==

=== Schachcomputer ===

Es hat viele Jahre gedauert, ehe mit enormem Aufwand ein Schachprogramm vorgelegt werden konnte, dass sich mit einem Weltklassespieler messen konnte.<br />
Dabei ist der erforderliche Algorithmus einfach:<br />
Erzeuge zu jedem Zug des Gegners ''alle'' nach den Spielregeln mögliche Gegenzüge. Danach erzeuge ''alle'' Antwortzüge des Gegners usw.<br />
Unter der Annahme, dass es in jeder Stellung nur 5 Fortsetzungsmöglichkeiten für den nächsten Spielzug gibt, ein Spiel im Mittel aus 60 Zügen (120 Halbzügen) besteht und zur Speicherung jedes Zustandes nur ein Byte gebraucht wird, würde der gesamte Speicherbedarf

<blockquote>
<math>5^0+5^1+5^2+ ... +5^{120} = 1 \cdot \frac{5^{121}-1}{5-1} \approx 9.404 \cdot 10^{83} \mbox{Byte}</math>
</blockquote>

betragen. Zumindest in den nächsten Jahren wird es nicht gelingen, den kompletten "Schachbaum" zu speichern. Der gewaltige Aufwand an Rechenzeit und Speicher verhindert eine ''praktische'' Realisierung.

=== Ackermannn-Peter-Funktion ===


Es ist möglich, algorithmisch prinzipiell lösbare Probleme anzugeben, die auch von zukünftigen "Supercomputern" nicht bewältigt werden können. Ein Beispiel ist die ''Ackermann-Peter-Funktion'', benannt nach dem deutschen Mathematiker '''Wilhelm Friedrich Ackermann''' (* 29. März 1896; † 24. Dezember 1962) und der ungarischen Mathematikerin '''Rózsa Péter''' (* 17. Februar 1905; † 16. Februar 1977):


Dabei handelt es sich um eine extrem schnell wachsende Funktion, die für die ''Klassifikation berechenbarer Funktionen'' eine große Bedeutung besitzt.<br />
Die nachfolgende Tabelle veranschaulicht einige Funktionswerte:

<table border="1" cellspacing="1" cellpadding="4">
<tr>
<th>n \ m</th><th width="50">0</th><th width="50">1</th><th width="50">2</th width="50">
<th width="50">3</th><th width="50">4</th><th width="50">5</th><th width="50">...</th>
</tr>
<tr align="center">
<th>0</th><td>1</td><td>2</td><td>3</td><td>4</td><td>5</td><td>6</td><td>...</td>
</tr>
<tr align="center">
<th>1</th><td>2</td><td>3</td><td>4</td><td>5</td><td>6</td><td>7</td><td>...</td>
</tr>
<tr align="center">
<th>2</th><td>3</td><td>5</td><td>7</td><td>9</td><td>11</td><td>13</td><td>...</td>
</tr>
<tr align="center">
<th>3</th><td>5</td><td>13</td><td>29</td><td>61</td><td>125</td><td>253</td><td>...</td>
</tr>
<tr align="center">
<th>4</th><td>13</td><td>65533</td><td>...</td><td>...</td><td>...</td><td>...</td><td>...</td>
</tr>
<tr align="center">
<th>5</th><td>65533</td><td>...</td><td>...</td><td>...</td><td>...</td><td>...</td><td>...</td>
</tr>
<tr align="center">
<th>...</th><td>...</td><td>...</td><td>...</td><td>...</td><td>...</td><td>...</td><td>...</td>
</tr>
</table>

Bereits der Funktionswert von <tt>(ack 4 2)</tt> besitzt 19729 Dezimalstellen!<br />
Sollte mit einem Computer die Berechnung <tt>(ack n m)</tt> möglich sein, so wird es immer einen Funktionswert <tt>(ack (+ n 1) (+ m 1))</tt> geben, dessen Berechnung nicht mehr möglich ist. Es gibt also objektive ''Grenzen bei praktischen Problemlösungen''.

== P-Probleme und NP-Probleme ==


Problemen sieht man im Allgemeinen nicht an, ob sie bezüglich ihres Zeitaufwands schwer oder leicht lösbar sind.<br />
Mitunter führt eine geringe Abweichungen in der Formulierung vergleichbarer Problemstellungen dazu, dass der Zeitaufwand zur Lösung fundamental verschieden ist, z.B.:

<table border="1" cellspacing="1" cellpadding="4">
<tr>
<th width="300">leicht, d.h. in <math>\mathcal{O}(n^k),k \ge 1</math></th>
<th width="300">schwer, d.h. in <math>\mathcal{O}(k^n),k > 1</math></th>
</tr>
<tr>
<td>
Finde den ''kürzesten'' Weg zwischen zwei Orten A und B in einem Straßennetz mit angegebenen Entfernungen.
</td>
<td>
Finde den ''längsten'' Weg zwischen zwei Orten A und B in einem Straßennetz mit angegebenen Entfernungen.
</td>
</tr>
</table>

Die Klasse der leichten Probleme heißen ''P-Probleme''. Als ''NP-Probleme'' bezeichnet man schwere Probleme.

'''P''' ist die Klasse von Problemen, die mit ''deterministischen'' Algorithmen in ''polynomialer'' Zeit gelöst werden können.<br />
Die Klasse der '''NP'''-Probleme ist die Menge aller Probleme, die ''nichtdeterministisch'' in Polynomialzeit gelöst werden können.

Wie muss man sich eine nichtdeterministische Problemlösung vorstellen?<br />
* '''1. Schritt:''' Der Algorithmus "errät" einen Lösungskandidaten.
* '''2. Schritt:''' Der Algorithmus verifiziert, ob der Kandidat tatsächlich eine Lösung ist.
Beide Schritte erfordern einen polynomialen Zeitaufwand.<br />
Jedes Problem aus P liegt auch in NP.
Es konnte aber bisher nicht gezeigt werden, dass es ein Problem gibt, das nachweislich zu NP aber nicht zu P gehört.<br />
Damit ist offen, ob
<blockquote><math>\mbox{P}=\mbox{NP}</math> oder <math>\mbox{P}\subset\mbox{NP}</math></blockquote>
gilt. An die Äquivalenz beider Klassen glaubt allerdings niemand.
<br><br>

'''NP-vollständige Probleme'''

Es gehört zu den herausragenden Leistungen der theoretischen Informatik, die schwersten Probleme zu einer separaten Klasse mit folgender Eigenschaft zusammenfassen zu können: Diese Probleme können in polynomialer Zeit ineinander überführt werden. Probleme dieser Klasse heißen ''NP-vollständig''.<br />
Sollte es je gelingen, einen effizienten (d.h. deterministisch polynomialen) Lösungsalgorithmus für ''ein'' Problem dieser Klasse zu finden, lassen sich auf einen Schlag ''alle'' Probleme dieser Klasse effizient lösen.<br />
Derzeit sind mehr als 1000 NP-vollständiger Probleme bekannt. Dass es bisher nicht gelungen ist, einen effizienten Lösungsalgorithmus zu finden, spricht für die Vermutung <math>\mbox{P}\subset\mbox{NP}</math>.

'''Einige Beispiele für NP-vollständige Probleme:'''

[[Bild:Rucksack1.gif|miniatur|Rucksackproblem]]

<ul>
<li>'''Rucksackproblem:'''<br /> 
Verschiedene Gegenstände sind mit ihrem Gewicht und ihrem Nutzwert gegeben. Eine Auswahl soll in einen Rucksack mit vorgegebenem Maximalgewicht gepackt werden, so dass der Gesamtwert der eingepackten Gegenstände maximal wird.<br>
Interessante [http://www.math-it.de/Mathematik/OR/Rucksack_de.html Visualisierung] ''<u>(funktioniert nur noch mit Internet Explorer 11 oder älter!)''</u> ausprobieren. <br>
Anzahl der Gegenstände schrittweise erhöhen!<br>
Auf Bedeutung der Spalten achten!
</li>
<li>'''Stundenplanproblem:'''<br /> 
Eine Zuordnung von Klassen und Fachlehrern zu Unterrichtsräumen und -zeiten soll so vorgenommen werden, dass eine möglichst große Zahl an vorgegebenen Nebenbedingungen erfüllt wird.<br>
Diese sind:

Gütekriterien für Stundenpläne
*	Minimale Anzahl von Freistunden für die Schüler.
*	Die Unterrichtseinheiten finden vorzugsweise am Vormittag und am frühen Nachmittag statt und sind für Schüler gleichmässig über die Wochentage verteilt.
*	Die freien Zwischenstunden für Lehrer sollten eine individuell festzulegende Anzahl nicht überschreiten. Die Anzahl der Unterrichtseinheiten pro Tag sollte so festgelegt sein, dass eine ausgewogene Aufteilung der Einheiten erreicht wird.
*	Die Anzahl der Raumwechsel für Schüler sollte gering sein. Ein Wechsel zwischen entfernten Gebäudeteilen sollte höchstens einmal pro Tag erfolgen.
*	Anstrengende oder ermüdende Unterrichtseinheiten (z.B. Sport) sollten für Schüler möglichst nur am Anfang oder am Ende eines Unterrichtstages geplant werden.
*	Eine Klasse soll möglichst viele Unterrichtseinheiten bei ihrem Klassenlehrer bzw. in ihrem Klassenzimmer verbringen.

Die bei der Stundenplanung zwingend vorgeschriebenen Restriktionen sind teilweise komplexe Beziehungen zwischen Unterrichtseinheiten. Ein Stundenplan, der alle Restriktionen erfüllt, heisst vollständiger Plan.<br>
Bestimmungen für einen vollständigen Plan:<br>
# Eine Unterrichtseinheit kann nur zu einer Zeit stattfinden. Alle Lehrer und Gruppen, die an der Einheit beteiligt sind, und mindestens ein ihr zur Auswahl stehender Raum müssen diese Zeit zur Verfügung haben.
# Eine Veranstaltung besteht aus Blöcken. Tauscht man in einem Plan die Zeit- und Raumzuordnungen mehrerer gleich grosser Blöcke untereinander aus, so entsteht ein anderer Plan, der aber die gleichen Eigenschaften wie der Ausgangsplan besitzt.
# Lehrer und Gruppen können nicht zur gleichen Zeit an mehreren Unterrichtseinheiten teilnehmen, deshalb sind die Zeiten aller Unterrichtseinheiten eines Lehrers bzw. einer Gruppe verschieden.
# In einem Raum können zu einer bestimmten Zeit nicht mehrere Unterrichtseinheiten stattfinden, deshalb sind die Räume aller Unterrichtseinheiten, die zur gleichen Zeit stattfinden, verschieden.
sowie
# Eine Zeiteinheit kann höchstens so oft verplant werden, wie Räume diese Zeit verfügbar haben.
# Fachunterricht findet häufig in einem dafür vorgesehenen Fachraum statt (z.B. Sport). Die Zeiten der Unterrichtseinheiten, die nur in einem solchen Fachraum durchgeführt werden, sind verschieden.

</li>
<li>'''Problem des Handlungsreisenden:'''<br /> 
Die Reihenfolge für den Besuch mehrerer Orte so zu wählen, dass die gesamte Reisestrecke des Handlungsreisenden nach der Rückkehr zum Ausgangsort möglichst kurz ist und jeder Ort nur einmal besucht wird.<br>
hierzu: [http://www.sueddeutsche.de/wissen/mathematik-problem-not-eines-handlungsreisenden-1.588630 Beitrag der Süddeutschen Zeitung]


<br>
</li>
</ul>

== Algorithmisch unlösbare Probleme ==

Hier ein Ausblick auf ''absolut unlösbare Probleme''.


'''Das Halteproblem: ''' Das Halteproblem ist ein Problem aus der Theoretischen Informatik. Es besteht darin, in einem bestimmten Berechnungskalkül zu entscheiden, ob die Ausführung einer bestimmten Berechnungsvorschrift zu einem Ende gelangt.
<br><br>
Die Entdeckung der '''Nichtentscheidbarkeit''' des Halteproblems hatte eine erschütternde Wirkung auf das herrschende mathematische Weltbild. Man versuchte gerade, die Mathematik durch eine strikte Formalisierung zu vereinheitlichen und den Regeln der Logik zu unterwerfen. ''Man ging davon aus, dass sich jedes mathematische Problem durch eine geeignete Formalisierung lösen lässt; dass es also immer möglich sei, eine Aussage so zu formulieren, dass man durch die Regeln der Logik und Mathematik erkennen kann, ob sie wahr oder falsch ist – gesucht war also ein vollständiges und widerspruchfreies System.''<br>
Nach den Erkenntnissen von Turing (vergleiche [http://de.wikipedia.org/wiki/Alan_Turing Alan Turing] oder [http://www.matheprisma.uni-wuppertal.de/Module/Turing/index.htm Turingmaschine]) und Gödel ist so etwas jedoch grundsätzlich nicht möglich: in jedem System, das die Mächtigkeit der Arithmetik besitzt, lassen sich Aussagen formulieren, die ''weder bewiesen noch widerlegt'' werden können: solche Systeme sind grundsätzlich unvollständig. ''Oder anders ausgedrückt: es gibt Funktionen, die zwar wohldefiniert sind, deren Werte sich dennoch im Allgemeinen nicht berechnen lassen.''<br>
Das Halteproblem bedeutet nur, dass es Aufgabenstellungen gibt, die nicht mechanisch gelöst werden können. Eine Beschränkung der Mittel setzt aber keineswegs die Logik außer Kraft.

zum Weiterlesen: [http://theo.cs.uni-magdeburg.de/lehre06s/ti_iif/folien/halteproblem-naiv.pdf Uni Magdeburg]
<br>

== weitere Beispiele ==


Königsberger Brückenproblem ''<u>(auch hier mit Internet Explorer 11 arbeiten --> Java-Einstellungen ggf. anpassen)''</u> [http://www.matheprisma.uni-wuppertal.de/Module/Koenigsb/index.htm in Matheprisma]
<br>
Vierfarbenproblem [http://www.matheprisma.uni-wuppertal.de/Module/4FP/index.htm auch hier]
<br> 
[http://de.wikipedia.org/wiki/Damenproblem Damenproblem]

<br>
[http://programmingwiki.de/Berechenbarkeitstheorie Begleitwiki zum Buch "EAGLE-Starthilfe Berechenbarkeitstheorie" von Prof. Wagenknecht (HS Zittau/Görlitz)]
Komplexität Berechenbarkeit

Komplexität von Sortieralgorithmen

Suche
