FH-Hof
Schwierigkeit von Aufgabenstellungen
Richard Göbel
FH-Hof
Fragestellungen
Gibt es Aufgabenstellungen die nicht lösbar
sind?
Gibt es unterschiedlich schwierige
Aufgabenstellungen?
Schwierigkeit einer Aufgabenstellung:
Laufzeit
Speicherplatzverbrauch
. . .
FH-Hof
Existieren unlösbare Aufgabenstellungen?
Betrachte die folgende Aufgabenstellung:
Existiert ein Programm U für eine RAM,
das für ein anderes Programm P einer RAM
und dessen Eingabe E entscheidet,
ob das Programm P mit der Eingabe E nach
endlich vielen Schritten anhält (terminiert)?
Ausgabe für Programm U:
Programm hält (‘1’, ‘true’, ‘yes’ oder 'Ja' )
Programm hält nicht (‘0’, ‘false’, ‘no’ oder 'Nein')
STOPS? : PRAM A* { true, false }
Bezeichnung: Halteproblem
FH-Hof
Beispiel einer Eingabe für die RAM
1 r e a d ; 2 i f 1 t h e n 2 ;
3 w r i t e 0 ; 4 e n d ; / 1 /
FH-Hof
Programm U für das Halteproblem - Analyse
Annahme: es gibt ein solches Programm U
Modifiziere das Programm U wie folgt:
Programm U gibt „false“ aus, falls das Programm
P mit Eingabe E nicht anhält
Programm U läuft unendlich lang, falls das
Programm P mit Eingabe E anhält (i: goto i)
Starte das Programm U mit dem Programm U
als Eingabe sowie dem Programm U als Daten
Wie verhält sich das Programm U in diesem
Fall?
FH-Hof
Menge aller denkbaren Funktionen
Wie groß ist die Menge der Funktionen?
Eine Funktion ordnet jeder Zeichenkette aus A*:
entweder eine Zeichenkette oder
den Wert „undefiniert“ zu
Eine Funktion lässt sich durch eine unendliche
lange Sequenz von Zeichenketten darstellen
Diese unendliche lange Zeichenkette lässt sich
als reelle Zahl kodieren
Wie ist die Mächtigkeit der Menge der reellen
Zahlen?
FH-Hof
Menge aller denkbaren Programme
Jedes Programm besteht aus einer endlichen
Menge von Anweisungen
Jedes Programm lässt sich als natürliche Zahl
darstellen
Wie ist die Mächtigkeit der Menge der
natürlichen Zahlen?
FH-Hof
Vergleich der Mengen
Die Menge der Programme bildet eine
abzählbar unendliche Menge
Die Menge der Funktionen bildet eine
überabzählbar unendliche Menge
Die Menge der Funktionen ist deutlich größer
als die Menge der Programme!
FH-Hof
Gruppen unlösbarer Probleme
Entscheidungsprobleme haben ein binäres
Ergebnis (true, false)
Fall 1: Es gibt ein Programm das immer
terminiert falls das Ergebnis „true“ ist.
Fall 2: Es gibt ein Programm das immer
terminiert falls das Ergebnis „false“ ist.
Fall 3: Es gibt kein Programm das für einen
dieser beiden Fälle terminiert
Programme mit anderen Ausgaben
Semientscheidbare Probleme
FH-Hof
Beispiel für verschiedene unlösbare Probleme
Hält ein Programm mit einer Eingabe an
(Halteproblem)?
Erfüllt ein Programm eine Bedingung für alle
Ausgaben?
Liefern zwei Programme dieselbe Ausgabe für
jede Eingabe?
FH-Hof
Schwierige Probleme
Gibt es lösbare Aufgabenstellungen, die aber
trotzdem schwierig sind?
Schwierig kann bedeuten:
viel Speicherplatzverbrauch
lange Laufzeit
. . .
Komplexitätsmaß
FH-Hof
Diskussion –was wird gemessen?
Laufzeit ist zum Beispiel abhängig von:
der Rechnertechnologie
dem Befehlssatz des Rechners
weiteren Prozessen auf diesem Rechner
der Menge der zu verarbeitenden Daten
Zentral: Schwierigkeit des Aufgabenstellung
und nicht Laufzeit eines Programms
Der Aufwand wächst mindestens linear mit der
Menge der zu verarbeitenden Daten!
FH-Hof
Ansatz - Zielsetzung
Wähle ein Komplexitätsmaß
Analysiere das Verhältnis zwischen Menge der zu
verarbeitenden Daten und dem Komplexitätsmaß
Betrachte nur den qualitativen Verlauf, wie zum
Beispiel:
linear: O(n)
quadratisch: O(n2)
exponentiell: O(2n)
Die Komplexität einer Aufgabenstellung ist die
Komplexität des effizientesten Programm
RAM als Referenzmaschine
FH-Hof
Ansatz - Methode
Ober- und Untergrenze für die Komplexität einer
Aufgabenstellung A:
Die Komplexität eines Programms für A ist eine
Obergrenze für die Komplexität von A
Ein Untergrenze ergibt sich aus der
Transformation von A in eine Aufgabenstellung B
mit bekannter Komplexität
Transformation von A in B
Transformiere die Eingabe von B in A
Transformiere die Ausgabe von A in B
Aufwand für die Transformation muss im
Verhältnis zur Komplexität der Problems B gering
sein.
FH-Hof
Aufgabenstellung – Erfüllbarkeit logischer Ausdrücke
Logischer Ausdruck in konjunktiver Normalform
Klauseln mit logisches UND verknüpft
Jede Klausel enthält mit logischem ODER
verknüpfte Literale
Jedes Literal besteht aus einer Variable und
optional einem logischen NICHT
(l11 l12 . . . l1n1) (l21 l22 . . . l1n2
) . . .
(lm1 lm2 . . . lmnm) mit lij : xij oder xij
Für welche Werte ist dieses Ausdruck erfüllt?
Beschränkung auf drei Literale pro Klausel: 3SAT
(l11 l12 l13) (l21 l22 l13) . . . (lm1 lm2 lm3)
FH-Hof
Aufgabenstellung - Rucksackproblem
Optimales Füllen eines Rucksacks
Gegeben:
n Gegenstände
Gewichte: g1, g2, . . ., gn
Nutzen: a1, a2, . . ., an
Gesamtgewicht von G nicht überschreiten
Finde Auswahl von Gegenständen mit
maximalem Nutzen
Modifiziertes Problem
Gewicht G muss genau erreicht werden
Nutzen wird nicht berücksichtigt
FH-Hof
Aufgabenstellung – Problem des Handlungsreisenden
Kürzeste Rundweg durch n Orte
Für je zwei Orte i und j wird die Entfernung dij
angegeben (nicht direkt erreichbar: )
Ergebnis ist die Reihenfolge in der die Orte zu
besuchen sind
FH-Hof
Transformation - 3SAT mod. Rucksackproblem
Erzeuge einen Gegenstand:
für jede Variable
für jede negierte Variable
Gewicht für einen Gegenstand ist eine
Dezimalzahl mit einer Stelle für jede Klause
Die Stelle gibt die Anzahl an, in der dieses
Literal in der zugehörigen Klausel vorkommt
Ziel: Summe der Gewichte muss an jeder Stelle
größer als Null sein
Beispiel:
(x1 x2 x3) (x2 x3 x4) (x1 x2 x4)
FH-Hof
Transformation - Themen
Zielgewicht muss genau eingehalten werden
Definiere „hohes“ Zielgewicht . . .
. . . sowie Füllgewicht . . .
. . . die bei einer Summe von 1 oder größer das
Zielgewicht erreichbar machen
Variable und negierte Variable dürfen nicht
gleichzeitig gewählt werden
Führe eine weitere Stelle für jede Variable ein . . .
. . . an dieser Stelle Wert 1 für zugehörige
Variable . . .
. . . sonst 0 . . .
. . . sowie Zielgewicht hat 1 an dieser Stelle
FH-Hof
Ergebnisse
Mit diesem Ansatz konnten verschiedene
Komplexitätsklassen identifiziert werden
Es gibt keinen Beweis, dass zwei Klassen
wirklich unterschiedliche Komplexitäten haben
Es fehlen also Referenzprobleme mit bekannter
Komplexität
FH-Hof
Diskussion
Eventuell existieren keine unterschiedlichen
Komplexitätsklassen?
Dann müssten alle Aufgabenstellungen mit
linearer Komplexität lösbar sein: Sehr
unwahrscheinlich!
Eventuell existieren nur wenige
Komplexitätsklassen?
Dann würden Komplexitätsklassen ohne
Aufgabenstellungen existieren:
Unwahrscheinlich!
Die identifizierten Komplexitätsklassen
werden heute allgemein akzeptiert!
FH-Hof
Zwei bekannte Klassen
Zeitaufwand für die Lösung einer Aufgabenstellung wird durch ein Polynom begrenzt:
Rechenoperation wir Addition und Subtraktion
Sortieren
. . .
Zeitaufwand für die Lösung einer Aufgabenstellung wächst mindestens exponentiell:
Rucksackproblem
Problem des Handlungsreisenden
Erfüllbarkeit eines booleschen Ausdrucks in konjunktiver Normalform
. . .
FH-Hof
Nichtdeterministische Turingmaschine
Mehrere Regeln sind in einem Zustand
anwendbar
Rechenaufwand
Sequenz von Regeln
welche die Aufgabenstellung löst
Minimale Sequenz definiert den Rechenaufwand
Diese Maschine löst zum Beispiel das 3SAT-
Problem mit einem polynomialen Aufwand
Lässt sich eine solche Maschine herstellen?
FH-Hof
Klassen von Aufgabenstellungen - Begriffe
P: Polynomialer Zeitaufwand auf einer
deterministischen Turingmaschine
NP: Polynomialer Zeitaufwand auf einer
nichtdeterministischen Turingmaschine
NP-Hart: Problem lässt sich auf einer
deterministischen Turingmaschine nicht mit
polynomialen Zeitaufwand lösen.
NP-Vollständig: Problem ist NP-Hart und lässt
sich auf einer nichtdeterministischen
Turingmaschine mit polynomialen Aufwand
lösen
FH-Hof
Komplexitätsskala
P
NP-Hart
NP-Vollständig
Linearer Zeitaufwand
Polynomialer Zeitaufwand
Exponentieller Zeitaufwand
FH-Hof
Bedeutung für die Praxis
Vermeide
unlösbare Probleme
NP-harte Probleme
Ändere ggf. die Spezifikation . . .
. . . oder finde einen einfach zu lösenden
Spezialfall
FH-Hof
Merkmale schwieriger Aufgabenstellungen
Unlösbare Probleme beziehen sich auf eine
unendlich große Menge
Die Lösung NP-harter Probleme besteht in der
Regel aus einer Vielzahl von einzelnen
„Entscheidungen“, wie zum Beispiel:
ganze Zahlen in einem Gleichungssystem
Planungsentscheidungen
. . .