Komplexität Berechenbarkeit

Aus ProgrammingWiki

Wechseln zu: Navigation, Suche

Inhaltsverzeichnis

Komplexität von Sortieralgorithmen

Komplexitätsuntersuchung von Sortieralgorithmen_1

Komplexitätsuntersuchung von Sortieralgorithmen_2


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.
Dabei ist der erforderliche Algorithmus einfach:
Erzeuge zu jedem Zug des Gegners alle nach den Spielregeln mögliche Gegenzüge. Danach erzeuge alle Antwortzüge des Gegners usw.
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

$5^0+5^1+5^2+ ... +5^{120} = 1 \cdot \frac{5^{121}-1}{5-1} \approx 9.404 \cdot 10^{83} \mbox{Byte}$

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.
Die nachfolgende Tabelle veranschaulicht einige Funktionswerte:

n \ m012 345...
0123456...
1234567...
235791113...
35132961125253...
41365533...............
565533..................
........................

Bereits der Funktionswert von (ack 4 2) besitzt 19729 Dezimalstellen!
Sollte mit einem Computer die Berechnung (ack n m) möglich sein, so wird es immer einen Funktionswert (ack (+ n 1) (+ m 1)) 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.
Mitunter führt eine geringe Abweichungen in der Formulierung vergleichbarer Problemstellungen dazu, dass der Zeitaufwand zur Lösung fundamental verschieden ist, z.B.:

leicht, d.h. in $\mathcal{O}(n^k),k \ge 1$ schwer, d.h. in $\mathcal{O}(k^n),k > 1$

Finde den kürzesten Weg zwischen zwei Orten A und B in einem Straßennetz mit angegebenen Entfernungen.

Finde den längsten Weg zwischen zwei Orten A und B in einem Straßennetz mit angegebenen Entfernungen.

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

  • 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.
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.
Damit ist offen, ob

$\mbox{P}=\mbox{NP}$ oder $\mbox{P}\subset\mbox{NP}$

gilt. An die Äquivalenz beider Klassen glaubt allerdings niemand.

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.
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.
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 $\mbox{P}\subset\mbox{NP}$.

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

Rucksackproblem
  • Rucksackproblem:
    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.
    Interessante Visualisierung (funktioniert nur noch mit Internet Explorer 11 oder älter!) ausprobieren.
    Anzahl der Gegenstände schrittweise erhöhen!
    Auf Bedeutung der Spalten achten!
  • Stundenplanproblem:
    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.
    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.
    Bestimmungen für einen vollständigen Plan:
    1. 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.
    2. 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.
    3. 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.
    4. 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
    1. Eine Zeiteinheit kann höchstens so oft verplant werden, wie Räume diese Zeit verfügbar haben.
    2. 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.
  • Problem des Handlungsreisenden:
    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.
    hierzu: Beitrag der Süddeutschen Zeitung

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.

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.
Nach den Erkenntnissen von Turing (vergleiche Alan Turing oder 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.
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: Uni Magdeburg

weitere Beispiele

Königsberger Brückenproblem in Matheprisma
Vierfarbenproblem auch hier
Damenproblem [1]


Begleitwiki zum Buch "EAGLE-Starthilfe Berechenbarkeitstheorie" von Prof. Wagenknecht (HS Zittau/Görlitz) in der (funktionalen) Sprache SCHEME

Von „https://programmingwiki.de/PMG2022/Komplexit%C3%A4t_Berechenbarkeit“
Persönliche Werkzeuge