Informatik wert Algorithmus theoretische Informatik Begriff zwischenprüfung NP

Theoretische Informatik : Polynomialzeit

Von: , Frage gestellt am Mi, 5. Dez 2001

Ich habe ein kleineres Problem aus der theoretischen Informatik.
Für Probleme aus P und NP gibt es ja das Charakteristikum "in Polynomialzeit lösbar". Mein Problem ist genau dieser Begriff.Mir ist vollkommen unklar in welchen Zusammenhang die länge der codierung und die Polynomialzeit liegen die zur Lösung benötigt wird.
Wenn mir jemand helfen kann ,wäre das klasse,es steht nämlich eine Zwischenprüfung an!
Mathes

5 Antworten zu dieser Frage

1. Antwort von nach 12 Stunden 0 hilfreich

   Re: Theoretische Informatik : Polynomialzeit

   Hi.
   Du hast einen Algorithmus, der auf einer Eingabe der Laenge n arbeitet (z.B. sollen n Elemente sortiert werden). Wenn du die Zeit, die der Algorithmus benoetigt, (also die Anzahl der Befehle) betrachtest, kannst du diese als Funktion von n angeben, z.B. T(n)=n^5+6n^2+e^n+5. Polynomialzeit bedeutet, dass diese Laufzeitfunktion durch ein Polynom nach oben begrenzt ist. Das oben genannte Beispiel ist also nicht polynomiell, da der Summand e^n sich nicht durch ein Polynom beschraenken laesst. Wenn dir die O-Notation was sagt, kann man das auch so ausdruecken, das Polynomialzeit sich durch O(n^a) angeben laesst, mit a beliebig, aber konstant.
   Ich hoffe, das hilft dir weiter,
   CU,
   Sebastian.
   

   • Antwort von nach 20 Stunden 0 hilfreich

     Re^2: Theoretische Informatik : Polynomialzeit

     Das heisst also,das z.B. PRIMZAHL deswegen aus NP ist,da sich die Bearbeitungszeit zur Eingabe exponentiell verhält.Also brauch ich für den Test ob 113 Pz. mit Länge der Codierung 3 unverhältnismäßig ,also exponentiell, lange;auf die Codierung bezogen.
     Und wie merkt man sowas beim "Durchschnittsproblem";gibt es da eine bestimmte Vorgehensweise oder nur den gesunden Menschenverstand?
     Auf jeden Fall schon mal Danke.
     Mathias
     

     • Antwort von nach 21 Stunden 0 hilfreich

       Re^3: Theoretische Informatik : Polynomialzeit

       Ich würde sagen, man schaut sich den Algorithmus an und versucht die Laufzeit zu bestimmen. Dann kann man es sehen. Wie man es vorher merken kann, weiss ich nicht genau. Aber da gab es doch noch die NP-vollständigen (hießen die so?) Probleme, auf die man andere NP Probleme zurückführen kann. Wenn man also einen Algorithmus hat, der sich auf den NP-vollständigen zurückführen lässt, ist dieser auch NP. Aber das solltest du vielleicht nochmal genauer nachlesen (z.B. in "Theoretische Informatik" oder in "Kompendium Theoretische Informatik" [beide von Ingo Wegener] oder auch in anderen Büchern, aber diese beiden fand ich eigentlich ganz in Ordnung (mag daran liegen, das das der Prof war, der die Vorlesung gehalten hat und sich dabei nach seinen Büchern gerichtet hat, aberman konnte gut danach lernen)).
       CU,
       Sebastian.
       

       • Antwort von nach einem Tag 0 hilfreich

         Re^4: Theoretische Informatik : Polynomialzeit

         Dann glaub ich hab ich es jetzt,danke.
         Ach so,ja die heißen NP-vollständige Probleme
         

     • Antwort von nach 12 Tagen 0 hilfreich

       Re^3: Theoretische Informatik : Polynomialzeit

       Das heisst also,das z.B. PRIMZAHL deswegen aus NP ist,da sich
       die Bearbeitungszeit zur Eingabe exponentiell verhält.
       Hallo,
       das Problem ist aus NP, da es eine nichtdeterministische
       Turing Maschine gibt, die ihn in polynomialer Zeit
       löst. Die Frage ob das gleichwertig mit exponentiellen Aufwand
       bei einer deterministischen Turing Maschine ist, ist ein/das
       offene/s Problem. Also
       brauch ich für den Test ob 113 Pz. mit Länge der Codierung 3
       unverhältnismäßig ,also exponentiell, lange;auf die Codierung
       bezogen.
       Vermutlich ja. Und wie merkt man sowas beim "Durchschnittsproblem";gibt es da
       eine bestimmte Vorgehensweise oder nur den gesunden
       Menschenverstand?
       Um zu zeigen, daß ein Problem NP-vollständig ist, zeigst Du
       zuerst, daß es in NP ist, dann das sich ein wohlbekanntes
       NP-vollständiges Problem mit polynomialen Aufwand auf dieses
       Problem reduzieren läßt. Die Liste der bekannten NP-vollstän-
       digen Probleme ist mittlerweise schon ziemlich umfangreich,
       mit ein bisschen Glück findet sich recht bald ein ähnlich
       geartetes Problem.
       
       Gruss
       Enno
       

Keine passende Antwort gefunden? Jetzt eigene Frage stellen!