Die Mathe-Redaktion - 08.12.2019 17:55 - Registrieren/Login
Auswahl
ListenpunktHome
ListenpunktAktuell und Interessant ai
ListenpunktArtikelübersicht/-suche
ListenpunktAlle Links / Mathe-Links
ListenpunktFach- & Sachbücher
ListenpunktMitglieder / Karte / Top 15
ListenpunktRegistrieren/Login
ListenpunktArbeitsgruppen
Listenpunkt? im neuen Schwätz
ListenpunktWerde Mathe-Millionär!
ListenpunktFormeleditor fedgeo
Schwarzes Brett
Aktion im Forum
Suche
Stichwortsuche in Artikeln und Links von Matheplanet
Suchen im Forum
Suchtipps

Bücher
Englische Bücher
Software
Suchbegriffe:
Mathematik bei amazon
Naturwissenschaft & Technik
In Partnerschaft mit Amazon.de
Kontakt
Mail an Matroid
[Keine Übungsaufgaben!]
Impressum

Bitte beachten Sie unsere Nutzungsbedingungen, die Distanzierung, unsere Datenschutzerklärung und
die Forumregeln.

Sie können Mitglied werden. Mitglieder können den Matheplanet-Newsletter bestellen, der etwa alle 2 Monate erscheint.

Der Newsletter Okt. 2017

Für Mitglieder
Mathematisch für Anfänger
Wer ist Online
Aktuell sind 631 Gäste und 24 Mitglieder online.

Sie können Mitglied werden:
Klick hier.

Über Matheplanet
 
Zum letzten Themenfilter: Themenfilter:
Matroids Matheplanet Forum Index
Moderiert von matroid
Informatik » Algorithmen / Datenstrukturen » Klasse NP, polynomial/exponentielle Algorithmen
Druckversion
Druckversion
Autor
Universität/Hochschule J Klasse NP, polynomial/exponentielle Algorithmen
wiwi_student
Ehemals Aktiv Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 25.03.2006
Mitteilungen: 131
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Themenstart: 2007-04-14


Morgen,

zwei Aufgaben verstehe ich leider gar nicht. Bin ziemlich neu in dem Gebiet, habe bisher in meinem Studium kaum was mit Informatik zu tun gehabt und tu mich deshalb sehr schwer.

1. Zeigen Sie, wie ein Algorithmus, der polynomial-beschränkte Subroutinen(eine Subroutine umfasst mehrere Operationen der Art: Rechenoperation, Logikoperation, Vergleichsoperation) polynomial häufig aufruft, zu einem nicht-polynomialen Algorithmus führen kann. (Tip: Reihenentwicklung der Exponentialfunktion)

2. Zeigen Sie, dass für jedes Problem der Klasse NP ein Lösungsverfahren angegeben werden kann, das im Zeitaufwand durch eine Funktion der Form
fed-Code einblenden

Evtl. kann einer von euch mir da ein paar Tips geben, wie ich da rangehen kann?

Besten Dank, Paul

[ Nachricht wurde editiert von wiwi_student am 14.04.2007 09:52:27 ]



  Profil  Quote  Link auf diesen Beitrag Link
valentin
Senior Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 19.03.2005
Mitteilungen: 1478
Aus: Berlin
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.1, eingetragen 2007-04-14


Hallo Paul,

zu 1)
fed-Code einblenden

Zu 2) Wie habt ihr die Klasse NP definiert, kennst du schon die Charakterisierung über Zertifikate ?

-- Valentin




  Profil  Quote  Link auf diesen Beitrag Link
wiwi_student
Ehemals Aktiv Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 25.03.2006
Mitteilungen: 131
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.2, vom Themenstarter, eingetragen 2007-04-14


Hallo Valentin,

zu 1. Bist du dir sicher mit der Funktion X(y)=y² ?
Ich denke da z.B. an das Quadrieren der Zahl 2=0*2^0 + 1*2^1 (=2 bits)
2^2=4=0*2^0 + 0*2^1 + 1*2^2 (=3bits), also ungleich Verdoppelung.

zu 2. Also unsere Definition ist ziemlich abstrakt(für mich). Über Zertifikate hab ich noch nix gehört. Unsere Definition (leider auf Englisch)

NP:
The class of all decision problems where each input x with an yes output has a certificate y, such that |y| is bounded by a polynomial in |x| and there is polynomial -time algorithm to verify that y is a valid certfificate for x is denoted as NP.

Was habe ich denn unter einen "yes output" zu verstehen ?

Nachtrag: Oh, ich glaube diese Definition ist doch das was du mit Zertifikate meinst.. :)


[ Nachricht wurde editiert von wiwi_student am 14.04.2007 19:48:56 ]



  Profil  Quote  Link auf diesen Beitrag Link
valentin
Senior Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 19.03.2005
Mitteilungen: 1478
Aus: Berlin
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.3, eingetragen 2007-04-14


2007-04-14 15:29 - wiwi_student schreibt:
zu 1. Bist du dir sicher mit der Funktion X(y)=y² ?
Ich denke da z.B. an das Quadrieren der Zahl 2=0*2^0 + 1*2^1 (=2 bits)
2^2=4=0*2^0 + 0*2^1 + 1*2^2 (=3bits), also ungleich Verdoppelung.

Das Quadrat von 3 (2 Bit) ist 9 (4 Bit), das Quadrat von 15 (4 Bit)
ist 225 (8 Bit), ganz allgemein ist das Quadrat einer N Bit Zahl mindestens 2N-1 Bit und maximal 2N Bit lang...

2007-04-14 15:29 - wiwi_student schreibt:
zu 2. Also unsere Definition ist ziemlich abstrakt(für mich). Über Zertifikate hab ich noch nix gehört. Unsere Definition (leider auf Englisch)

NP:
The class of all decision problems where each input x with an yes output has a certificate y, such that |y| is bounded by a polynomial in |x| and there is polynomial -time algorithm to verify that y is a valid certfificate for x is denoted as NP.

Was habe ich denn unter einen "yes output" zu verstehen ?

Decision problem ist übersetzt: Entscheidungsproblem. Entscheidung ist: Ja oder Nein...

Du hast also eine Eingabe und willst wissen, ob irgend eine Eigenschaft für diese Eingabe gilt. Ein Algorithmus, der diese Eigenschaft entscheiden kann, wird also entweder Ja oder Nein ausgeben. Das gute an der Klasse NP ist, dass du solch einem Algorithmus nicht blind glauben brauchst. Denn wenn die Eingabe die zu entscheidende Eigenschaft besitzt, so gibt es ein Zertifikat dafür.

Ein Beispiel: Du willst wissen, ob die Zahl 17357 zusammengesetzt (d.h. keine Primzahl) ist. Ein korrekter Algorithmus für dieses Problem würde dir die Antwort "Ja" liefern. Ein Zertifikat für diese Antwort wäre ein Teiler von 17357, in diesem Fall zB 17.

Deshalb kann man jedes Problem in NP entscheiden, in dem man einfach alle möglichen Zertifikate durchprobiert (dauert natürlich exponentiell lange)

-- Valentin



  Profil  Quote  Link auf diesen Beitrag Link
wiwi_student
Ehemals Aktiv Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 25.03.2006
Mitteilungen: 131
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.4, vom Themenstarter, eingetragen 2007-04-14


ein wenig klarer ist mir das ganze nun glaube ich. Danke schonmal dafür.
Aber richtig versteh ich immer noch nicht.

Wenn ich dein Beispiel aus deinem 1. Post nehme, dann soll doch eine Eingabe eine Zahl quadriert werden, diese wieder, das Ergebnis wieder uws. Aber nicht jedes mal ist die Ausgabe auch wirklich doppelt so lang,  wenn man bei 3 startet und dann 9 quadriert ist das ja dann wieder keine Verdoppelung, dann kommt man ja auch nicht auf 2^N, oder wie?

Wieso dauert das Überprüfen exponentiell lang? Weil bei jedem Zertifikat(hier doch jede Zahl >2, da man doch noch gar nicht weiss welche Zahl ein Zertifikat sein kann??) die Antwort: Ja oder Nein sein kann und dieses polynomial oft wiederholt wird? Deshalb auch 2^(O(n^k)) oder wie? Bzw. wie soll ich denn die 2. Frage beantworten mit der Funktion?

Paul
[ Nachricht wurde editiert von wiwi_student am 14.04.2007 20:34:30 ]



  Profil  Quote  Link auf diesen Beitrag Link
valentin
Senior Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 19.03.2005
Mitteilungen: 1478
Aus: Berlin
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.5, eingetragen 2007-04-16


Sorry, dass ich erst jetzt antworte, habe viel um die Ohren. Niemand anderes hier, der mitmacht ?

2007-04-14 20:16 - wiwi_student schreibt:
Wenn ich dein Beispiel aus deinem 1. Post nehme, dann soll doch eine Eingabe eine Zahl quadriert werden, diese wieder, das Ergebnis wieder uws. Aber nicht jedes mal ist die Ausgabe auch wirklich doppelt so lang,  wenn man bei 3 startet und dann 9 quadriert ist das ja dann wieder keine Verdoppelung, dann kommt man ja auch nicht auf 2^N, oder wie?

Naja, selbst wenn immer nur der Fall 2N-1 eintritt, so hast du insgesammt nach k Schritten einen Faktor von 2^(k-1)+1 oder so...

2007-04-14 20:16 - wiwi_student schreibt:
Wieso dauert das Überprüfen exponentiell lang? Weil bei jedem Zertifikat(hier doch jede Zahl >2, da man doch noch gar nicht weiss welche Zahl ein Zertifikat sein kann??) die Antwort: Ja oder Nein sein kann und dieses polynomial oft wiederholt wird? Deshalb auch 2^(O(n^k)) oder wie? Bzw. wie soll ich denn die 2. Frage beantworten mit der Funktion?

Das überprüfen eines Zertifikates dauert polynomial lange.
Um ein NP Entscheidungsproblem zu lösen, kannst du alle möglichen Zertifikate testen. Ist mindestens ein Zertifikat echt, dann ist die Antwort "Ja", ist kein Zertifikat echt, so ist die Antwort "Nein"

Wenn die Länge eines Zertifikates durch O(n^k) beschränkt ist, so gibt es maximal 2^(O(n^k)) viele Zertifikate, die du testen mußt.
Dies ist eigentlich schon die Antwort auf Aufgabe 2.

-- Valentin


[ Nachricht wurde editiert von valentin am 16.04.2007 14:27:51 ]



  Profil  Quote  Link auf diesen Beitrag Link
wiwi_student
Ehemals Aktiv Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 25.03.2006
Mitteilungen: 131
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.6, vom Themenstarter, eingetragen 2007-04-18


Hallo, das macht nix wenn ich hier mal bisschen länger warte. Bin ja froh, dass hier überhaupt wer antwortet.


Das überprüfen eines Zertifikates dauert polynomial lange.
Um ein NP Entscheidungsproblem zu lösen, kannst du alle möglichen Zertifikate testen. Ist mindestens ein Zertifikat echt, dann ist die Antwort "Ja", ist kein Zertifikat echt, so ist die Antwort "Nein"

Wenn die Länge eines Zertifikates durch O(n^k) beschränkt ist, so gibt es maximal 2^(O(n^k)) viele Zertifikate, die du testen mußt.
Dies ist eigentlich schon die Antwort auf Aufgabe 2.

Mir leuchtet irgendwie nicht ein, wieso ich als Obergrenze 2^(O(n^k)) habe. Woher kommt die 2. Ich würde spontan doch an c*O(n^k) denken, wenn das Überprüfen eines  Zertifikates polynomial lange dauert und ich endlich viele davon habe.

Grüße, Paul.

[ Nachricht wurde editiert von valentin am 16.04.2007 14:27:51 ]



  Profil  Quote  Link auf diesen Beitrag Link
Plex_Inphinity
Senior Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 01.05.2002
Mitteilungen: 3601
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.7, eingetragen 2007-04-18


Hallo,

Die Anzahl der Zertifikate, die man testen muß ist natürlich endlich, aber nicht konstant, d.h. sie hängt von n ab.

fed-Code einblenden

Gruß
Plex

[ Nachricht wurde editiert von Plex_Inphinity am 18.04.2007 21:00:51 ]



  Profil  Quote  Link auf diesen Beitrag Link
wiwi_student
Ehemals Aktiv Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 25.03.2006
Mitteilungen: 131
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.8, vom Themenstarter, eingetragen 2007-04-18


Hi Plex,

danke für die ausführliche Erklärung. Aber wo ist denn mein Denkfehler wenn ich sage, dass man mit einem Bitvektor der Länge 2^a auch alle Bitvektoren kleinerer Länge darstellen kann, indem man einfach die führenden Bits auf 0 setzt? Dann müsste man ja nur die Länge 2^a betrachten und nicht noch alle Bitvektoren kleinerer Länge.



  Profil  Quote  Link auf diesen Beitrag Link
Plex_Inphinity
Senior Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 01.05.2002
Mitteilungen: 3601
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.9, eingetragen 2007-04-18


Naja, für die Abschätzung spielt es eh keine Rolle, ob alle Zertifikate die gleiche Länge haben, oder nur höchstens die Länge O(n^k).
Nach eurer Definition von NP:

NP:
The class of all decision problems where each input x with an yes output has a certificate y, such that |y| is bounded by a polynomial in |x| and there is polynomial -time algorithm to verify that y is a valid certfificate for x is denoted as NP.
soll die Zertifikatlänge jedoch nur durch ein Polynom in |x|(=n) beschränkt sein. Es haben also nicht alle Zertifikate die gleiche Länge.
Dann kann man kleinere Zertifikate, also Bitvektoren, nicht durch größere darstellen, weil es ja nunmal zwei verschiedene Zertifikate sind.
1000000 ist ein anderes Zertifikat als 1.
Je nachdem, wie diese Zertifikate von dem Algorithmus interpretiert werden, könnte 1000000 zu einer anderen Berechnung führen als 1.
Man muß also alle Zertifikate durchtesten.





  Profil  Quote  Link auf diesen Beitrag Link
wiwi_student
Ehemals Aktiv Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 25.03.2006
Mitteilungen: 131
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.10, vom Themenstarter, eingetragen 2007-04-18


Ahso, hm okay. Dann nochmals vielen Dank für eure Zeit.



  Profil  Quote  Link auf diesen Beitrag Link
wiwi_student hat die Antworten auf ihre/seine Frage gesehen.
wiwi_student hat selbst das Ok-Häkchen gesetzt.
Neues Thema [Neues Thema]  Druckversion [Druckversion]

 


Wechsel in ein anderes Forum:
 Suchen    
 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2019 by Matroids Matheplanet
This web site was made with PHP-Nuke, a web portal system written in PHP. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
[Seitenanfang]