Autor Beitrag
Xart
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starofftopic star
Beiträge: 18

XP
D6 Pers
BeitragVerfasst: Di 30.03.04 18:13 
Hallo Leute,
ich habe ein problem zu Np... Nehmen wir mal an eine Aufgabe würde lauten: "Was sind in der Info. n-p-Probleme?

Meine Antwort würde lauten: " Es sind Probleme welche sich nicht in polynomineller Zeit lösen lassen, d.h. z.B. bei 120 Rechenschritten kann dies exponentiell z.B. 2^120 Schritte => 100te Jahre Rechendauer bedeuten"

Ist das richtig? könnte man das so sagen? Oder was muss man auf jeden Fall ergänzen? Zudem eine andere Verständnisfrage... was genau heißt eigentlich polynominal... ich habe irgendwo etwas von "erfüllbar" gelesen. Ist das korrekt?

Vielen Dank schonmal im vorraus

Xart

p.s. Sorry das ich nicht direkt ein neues thread gemacht habe ;)


Moderiert von user profile icontommie-lie: Topic verschoben
Gausi
ontopic starontopic starontopic starontopic starontopic starontopic starofftopic starofftopic star
Beiträge: 8554
Erhaltene Danke: 481

Windows 7, Windows 10
D7 PE, Delphi XE3 Prof, Delphi 10.3 CE
BeitragVerfasst: Di 30.03.04 23:20 
[Im folgenden gebe ich keine exakte Beschreibung von NP usw., wenn also mein Info-Prof das liest: Ich versuche, das einem Laien verständlich zu machen....]

Nein, das ist nicht korrekt. Zumindest wird das sehr stark vermutet.

Benötigt werden zum Verständnis von NP die nichtdeterministischen Turingmaschinen (NDTM). Das waren die, die möglicherweise Wahlmöglichkeiten in ihrem Programm haben und ein Problem lösen, wenn es eine Abfolge von Wahlen gibt, die zum Ziel führt. Und das ist der Knackpunkt beim Nichtdeterminismus, den man verstehen muss. Das Problem ist gelöst, wenn es eine Abfolge von "richtigen" Entscheidungen gibt. Wie diese gefunden werden, spielt gar keine Rolle. Man spricht da auch von einem "Entscheidungsbaum". Wenn es vom Start einen Weg durch diesen Baum gibt, der zum Ergebnis führt, dann reicht das, auch wenn es Millionen anderer Wege gibt, die in eine Endlosschleife führen oder es zu einer "Fehlermeldung" kommt...
Wenn es für ein Problem ein solche (theoretische) Maschine gibt, die das Problem in Polynomzeit löst, dann ist diese Problem in der Klasse NP. Das heißt: (N)ichtdeterministisch (P)olynomiell. In Polynomzeit heisst hier: Wenn ein "richtiger Weg" polynomiell viele Schritte lang ist.

Wenn es eine deterministische Turingmaschine (DTM) gibt (also eine, die eher unseren Computern und den Programmen entspricht, also eine ohne diese Art Wahlmöglichkeiten), die das Problem in Polynomzeit löst, dann ist das Problem in der Klasse P.

Es ist bis heute unbekannt, ob P=NP, oder P "ungleich" NP. Daher ist deine Aussage "Es sind Probleme welche sich nicht in polynomineller Zeit lösen lassen" falsch, weil man es noch nicht weiss (obwohl fast alle davon ausgehen). Außerdem lassen sie sich ja in Polynomzeit lösen, aber eben mit einer nichtdeterministischen Turingmaschine.

Ausserdem: Jede DTM ist auch eine NTDM, aber eben eine, die immer nur eine "Wahl zwischen einer Möglichkeit" hat. Somit ist jedes Problem in der Klasse P auch in der Klasse NP, d.h. es gibt viele Probleme in NP, die auch mit unseren Rechnern in Polynomzeit lösbar sind.

!!! NP heisst nicht "nicht polynomiell" !!!

--------------

Soviel erstmal dazu. Jetzt zur Polynomiellen Laufzeit. Das hat nix mit erfüllbar zu tun. Erfüllbar in Zusammenhang mit NP kann nur das SAT oder 3SAT Problem sein, wobei Boolsche Formeln erfüllbar sein sollen. (Hat nix mit Fernsehen zu tun, das sind zwei grundlegende "NP-vollständige" Probleme. Was genau NP-vollständig heisst, erklär ich später mal. Ganz kurz sind es die Probleme, für die man noch keinen polynomiellen Lösungsalgotithmus für eine DTM gefunden hat; also wahrscheinlich mit unseren Rechnern nicht polynomiell lösbar sind)

Ein Polynom ist ein Ding der Form p(x)=a_n*x^n + a_{n-1}*x^{n-1} + ... + a_2*x^2 + a_1*x + a_0. Kennt man wohl aus der Schule, n ist dabei eine natürliche Zahl, z.b. 2, dann hat man eine Parabel.

Praktisch jeder Algorithmus verlangt ja eine Eingabe. Diese Eingabe hat ein gewisse Größe. Zum Beispiel möchte man ein paar Zahlen sortieren, 100, 1000, oder 10Millionen. Oder man möchte kürzeste Wege zwischen 2 bestimmten Städten aus 100 oder 10.000 Städten bestimmen. Diese Größe ist das "x" in dem Polynom. Das p(x) (oder meinetwegen das y), was am Ende rauskommt, sollte die Laufzeit (die Anzahl der Rechenschritte) sein.
Ein Algorithmus hat eine Polynomielle Laufzeit, wenn es ein Polynom gibt (d.h. ein n und die Vorfaktoren a_n ....a_1 und die Konstante a_0), so dass für jede beliebige Eingabegröße (bis auf ein paar kleine am Anfang) die Anzahl der Rechenschritte, die der Algorithmus benötigt kleiner oder gleich dem Wert p(x) ist.

Ein ganz einfaches Beispiel:

ausblenden Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
Eingabe: ein Zahlen-Array A mit x vielen Einträgen
Aufgabe: Suche das kleinste Element

min:=A[1]   (1 Schritt)
für alle i:=2,....,x do
    wenn A[i] < min dann min:=A[i]   (x-1 Schritte)

Ausgabe: min   (1 Schritt)

Das Ding hat offensichtlich eine Polynomielle Laufzeit. Wähle z.B. n=1, a_1=1 und a_0=1. In diesem Fall (n=1) spricht man auch von linearer Laufzeit.

Ich hoffe, ich konnte da etwas weiterhelfen...

_________________
We are, we were and will not be.
Xart Threadstarter
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starofftopic star
Beiträge: 18

XP
D6 Pers
BeitragVerfasst: Mi 31.03.04 18:38 
NP Probleme sind Problemstellungen in der theoretischen Informatik, für die kein Algorithmus besteht, der in einer deterministisch polynomiellen Maximallaufzeit auf das perfekte Ergebnis kommt. NP steht daher für nichtdeterministisch polynominell. Im Detail bedeutet dies, das die NP-Probleme zwar nach einer gewissen, nicht klar definierten Zeit vielleicht auf ein Ergebnis stoßen, aber es ist weder garantiert, dass das Ergebnis richtig ist, noch ist garantiert ob überhaupt ein Ergebnis geliefert werden wird. In gewisser Weise ist dies mit dem Versuch und Irrtum („Trial and Error“) Prinzip gleichzusetzen. Die Algorithmen, die sich mit NP-Problemen beschäftigen, versuchen ein Ergebnis zu finden und die Erfolgschancen erkennt man erst nach deren Ablauf. Berühmte NP-Problem sind das TSP („Travelling Salesman Problem“) und das Rucksackproblem. Beide überfordern ab einer bestimmten Anzahl an Variablen den Rechner und können nicht nach der Brute-Force Methode alle Möglichkeiten ausschöpfen. NP-Probleme konnten bisher noch nicht gelöst werden und somit setzt das technisch Mögliche die Grenzen für die Erfolgschancen und die Effizienz der modernen Algorithmen, die NP-Probleme zu lösen versuchen.

hab ich das so richtig zusammengefasst/verstanden?
vielen dank für die bisherige Antwort ;)
Gausi
ontopic starontopic starontopic starontopic starontopic starontopic starofftopic starofftopic star
Beiträge: 8554
Erhaltene Danke: 481

Windows 7, Windows 10
D7 PE, Delphi XE3 Prof, Delphi 10.3 CE
BeitragVerfasst: Mi 31.03.04 21:40 
Zitat:
NP Probleme sind Problemstellungen in der theoretischen Informatik, für die kein Algorithmus besteht, der in einer deterministisch polynomiellen Maximallaufzeit auf das perfekte Ergebnis kommt.

Soweit richtig, wenn du "für die kein Algorithmus besteht" durch "für die kein Algorithmus bekannt ist" ersetzt. Und ersetze bitte im folgenden immer NP-Probleme durch "NP-vollständige" Probleme. Auch das Problem, x Zahlen zu sortieren, ist in der Klasse NP, aber es ist nun wirklich nicht schwer zu lösen.

--------------
Einschub: Kurz-Definition "NP-Vollständig": Ein Problem P heisst NP-vollständig, wenn es erstens in NP ist (oft sehr einfach zu überprüfen, das geht meistens so: Rate die Entscheidungen und prüfe nach, man mit diesen Entscheidungen in Polynomziet zum Ziel kommt).
Zweitens: Das Problem ist NP-schwer. D.h. Jedes andere Problem läßt sich in Polynomzeit auf das Problem P reduzieren. Ein Beispiel: Ich möchte zeigen, das TSP NP-schwer ist. Ich weiss bereits, dass SAT NP-Schwer ist (is jetzt mal egal, was SAT ist). Wenn ich eine beliebige Eingabe für SAT in Polynomzeit so umbauen kann, dass es eine Eingabe für TSP wird, die genau dann lösbar ist, wenn die Ursprungseingabe für SAT lösbar ist, dann ist TSP NP-schwer (d.h. für TSP gibt es scheinbar keinen schnellen Algo.). Ansonsten hätte ich ja mit dem schnellen Verfahren für mein neues Problem TSP direkt auch ein schnelles Verfahren für SAT: Einfach SAT zu TSP umwandeln und TSP lösen.
Der Trick ist: Wenn ich auch nur für ein einziges NP-Vollständiges Problem einen Polynomiellen Algorithmus finde, dann habe ich damit automatisch für ALLE anderen auch einen. Und es gibt viele NP-vollständige Probleme.

hierbei meint "lösen" immer eine Entscheidung der Art mit "JA" zu beantworten: "Gibt es eine Rundreise, die kürzer als x km ist"
--------------

Zitat:
Im Detail bedeutet dies, das die NP-Probleme zwar nach einer gewissen, nicht klar definierten Zeit vielleicht auf ein Ergebnis stoßen, aber es ist weder garantiert, dass das Ergebnis richtig ist, noch ist garantiert ob überhaupt ein Ergebnis geliefert werden wird

Probleme stoßen nie auf ein Ergebnis. Nur die Algorithmen zur Lösung derselben. Auch bei NP-vollständigen Problemen läßt sich die Laufzeit der Lösungs-Algorithmen sehr wohl abschätzen. Sie ist nur in der Regel exponentiell in der Eingabegröße. Außerdem ist bei einem Algorithmus immer klar, ob ein Ergebnis geliefert wird oder nicht. Zum Algorithmenentwurf gehört nämlich IMHO auch, dass man sicherstellt, dass der Algorithmus irgendwann terminiert, und das dass richtige Ergebnis geliefert wird. Sonst hat man Schei*e gebaut.

Zitat:
Die Algorithmen, die sich mit NP-Problemen beschäftigen, versuchen ein Ergebnis zu finden und die Erfolgschancen erkennt man erst nach deren Ablauf.

Nein, nicht ganz. Es gibt da zwei Ebenen. Einerseits die theoretische nichtdeterministiche Maschine, die ein Problem in Polynomialzeit lösen kann; und dann die "reale" Ebene mit unseren Rechnern, die das bisher nicht schaffen (und fast alle Informatiker glauben, dass das auch nicht geht. Wenn doch, könnte man viele Verschlüsselungsalgorithmen wegschmeissen...). In der realen Welt müssen die verschiedenen Wahlmöglichkeiten der NDTM hintereinander ausgeführt werden. Die NDTM macht quasi beliebig viele Schritte gleichzeitig. Das hintereinanderausführen benötigt natürlich viel Zeit, wodurch das ganze i.d.R. exponentiell oder noch fieser wird.

Ich versuch da mal am Rucksackproblem klarzumachen. Eine NDTM hat beliebig viele kleine Helfer, die alle verschiedene Rucksäcke packen. Wenn einer dieser Helferlein den Rucksack mit Dingen füllt, die den Nutzwert über- und das Maximalgewicht unterschreiten, schreit der "hier" und die Maschine gibt dem sein Ergebnis aus. Das tolle ist, wenn man 10 Helfer benötigt, hat die Maschine 10 Helfer, und wenn 10.000.000.000.000.000.000 benötigt werden, hat sie 10.000.000.000.000.000.000 zur Verfügung.
Ein Computer hat nur einen Helfer. Seine CPU. Evtl auch 2 oder 16 oder ein paar mehr, das sind dann die Parallelrechner. Aber die Anzahl der CPUs ist durch die Hardware beschränkt. Daher kann der Computer immer nur einen (oder 2, oder 16...) Rucksack nach dem anderen füllen, also praktisch alle Möglichkeiten hintereinander durchprobieren, und immer nur eine gelcihzeitig.

Trotzdem können NP-vollständige Probleme gelöst werden. Zum einen natürlich für kleine Eingaben (z.B. 100 Städte), oder mit viel Geduld und Zeit (aber leider oft mehr als 10^17 Sekunden, was dem Alter des Universums entspricht...). Zum anderen gibt es dann die Approximationsalgorithmen. Z.B. für den Handlungsreisenden. Es reicht ja oft, einen Rundweg zu finden, der "ziemlich kurz ist", d.h. z.B. nicht mehr als 50% länger als der optimale. Und das geht oft viel schneller.

Ein Tipp noch: Das ist ein recht kompliziertes Thema, und schwer in so kurzen Posts ohne genaue Mathematische Beweise und Definitionen genau zu erläutern. Wenn du wirklich mehr darüber wissen willst, empfehle ich eine Suche im Netz nach "NP-Vollständig(keit)" oder "NP-complete(ness)". Oder das Buch
Michael R. Garey und David S. Johnson; Computers and Intractability, A Guide to the Theory of NP-Completeness; Freeman; 1979

_________________
We are, we were and will not be.
DocZoidberg
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic star
Beiträge: 17

WIN 2000
D7
BeitragVerfasst: Do 01.04.04 00:29 
Du kannst auch mal in den Schöning schauen.
Uwe Schöning, Theoretische Informatik kurz gefasst.
Dürfte in jeder Informatik Bibi zu finden sein.

Alles zum Thema NP-Vollständigkeit ist hier auf 12 Seiten zusammengefasst. Alle Definitionen und Erläuterungen.
In den Kapiteln zuvor findest du aber auch noch die restlichen Grundlagen, falls du dich auf dem Gebiet wirklich schlau machen willst.
Ist zwar mit Sicherheit der ekeligste Teil der Informatik, aber trotzdem durchaus überschaubar.
Ist wirklich Standardlektüre. Automaten, Sprachen, Berechenbarkeit und damit auch die Turingmaschiene und schließlich die Komplexitätstheorie (Also NP).

Vielleicht hilft dir das ja weiter, je nachdem, wie tief du dich in das Thema reinhängen willst.

MfG Michael