| Autor |
Beitrag |
    
Carsten (Morl99)
| | Veröffentlicht am Mittwoch, den 11. April, 2001 - 01:37: | 
|
Warum ist N = Np?????
wer das mit diesen Angaben rausbekommt der ist spitze. Allerdings muß es stimmen!!! Ist klar
Außerdem darf man net sagen weil es so ist oder ähnliches es muß ein mathematischer Beweis sein.
Sonst bringt es nix |
Xell
| | Veröffentlicht am Mittwoch, den 11. April, 2001 - 02:30: |
|
Vermutung:
Du meinst mit N=Np: N=N•p
Seien also N und p zwei Zahlen.
Somit stimmt die Gleichung für p=1 und N¹0
Auch stimmt die Gleichung für p beliebig und N=0
Þ Für p=1 und N bel. passt's.
mfG
Zu trivial oder geht es dabei um was völlig anderes? Die Fragestellung ist nicht gerade die präziseste... ;-) |
Lars Weiser
| | Veröffentlicht am Mittwoch, den 11. April, 2001 - 08:39: |
|
Vielleicht meint er ja das P-NP-Problem ???? |
Xell
| | Veröffentlicht am Mittwoch, den 11. April, 2001 - 14:22: |
|
Mhh... nie gehört. Was soll das sein? |
Kevin
| | Veröffentlicht am Mittwoch, den 11. April, 2001 - 18:45: |
|
Hallo Xell,
Was ist denn der schwarze Punkt? |
Xell
| | Veröffentlicht am Mittwoch, den 11. April, 2001 - 20:55: |
|
Der schwarze Punkt ist ein Mal-Zeichen, also •=*. |
Checker
| | Veröffentlicht am Mittwoch, den 18. April, 2001 - 09:59: |
|
Ich hab da noch ne Aufgabe:
H=Hp |
Xell
| | Veröffentlicht am Sonntag, den 22. April, 2001 - 06:44: |
|
P=NP
Hier geht es, etwas pathetisch ausgedrückt, um die Grenzen des Wissens.
Mathematiker wollen doch konkrete Probleme lösen: Man gibt gewisse Werte ein, rechnet eine Weile, und dann erhält man die Lösung. Es hat sich als günstig erwiesen, als einfach solche Probeme anzusehen, bei denen die Rechenzeit nicht zu stark mit der Problemgröße wächst. Genauer: Braucht man n Ziffern, um das Problem zu beschreiben, so soll die Rechenzeit durch eine feste Potenz von n abschätzbar sein. Nehmen wir zum Beispiel das Multiplizieren n-stelliger Zahlen. Da muss man im wesentlichen n2 Rechenoperationen durchführen, und deswegen ist Multiplizieren ein "einfaches" Problem.
Die meisten der in der Schule behandelten Algorithmen sind von dieser Art: Addieren, Multiplizieren, Gleichungssysteme lösen, Wurzeln ziehen. Der Fachausdruck dafür lautet: Probleme vom Typ P, das "P" steht für "polynomiell".
Längst nicht alle Probleme sind einfach: Möchte ich von einer n-stelligen Zahl wissen, ob es sich um eine Primzahl handelt, so ist der Aufwand nicht durch eine Potenz von n abschätzbar. Vielmehr ist er von der Größenordnung 10n, so viele Zahlen muss ich als potenzielle Teiler prüfen. Der Aufwand wächst also exponentiell mit n.
Mal angenommen, eine Zahl n ist das Produkt von zwei Zahlen: n=p·q. Einer dieser Faktoren soll gefunden werden. Wenn man das durch systematisches Probieren versucht zu lösen, ist das sicher kein Problem vom Typ P, der Aufwand wächst wieder exponentiell mit n. Allerdings: Wenn wir einfach einen Teiler p raten und Glück haben, geht es ganz schnell: Wir teilen n durch p (das ist einfach!), es geht auf, fertig.
Probleme, die sich durch mit viel Glück durch Raten auf Probleme vom Typ P zurückführen lassen, heißen vom Typ NP; das soll "nichtdeterministisch polynomiell" abkürzen.
Und nun das Problem: Man gebe wenigstens eine Situation an, in der ein Problem vom Typ NP, nicht aber vom Typ P ist (oder beweise, dass alle NP-Probleme schon vom Typ P sind). Prägnant zusammengefasst wird das als
P = NP ?
Naiv gesehen ist NP viel, viel schwieriger als P, aber bisher hat noch niemand ein Beispiel gefunden, wo das auch streng gezeigt werden könnte.
mfg, Damit auch jeder weiß, worum es geht... |
Andra
| | Veröffentlicht am Montag, den 23. April, 2001 - 03:50: |
|
Hallo Xell,
hast Du schon was vom Steiner-Problem gehört? Da hatte ich mal entsprechende Literatur in den Händen, die Titel weiß ich allerdings nicht mehr.
Ciao, Andra |
Xell
| | Veröffentlicht am Freitag, den 27. April, 2001 - 01:39: |
|
Hallo Andra!
Nein, hab ich noch nix von gehört! Erzähl mal...
mfG, Xell :-) |
Andra
| | Veröffentlicht am Freitag, den 27. April, 2001 - 09:51: |
|
Hallo Xell,
das Steiner-Problem hört sich einfach an, wird aber irsinnig kompiliziert zum rechnen, mit jedem weiteren Punkt. Also ein Beispiel für ein sogenanntes np-schweres Problem, dessen Lösungsalgorithmus sich exponential verhält.
Gegeben Punkte in der Ebene. Gesucht: kürzeste Verbindung zwischen diesen Punkten, Hilfspunkte erlaubt, d.h. minimaler Spannbaum von gegebenen und Hilfspunkten berechnen, Hilfspunkte unbekannt. Geometrische Lösung bei einfachst-Problemen: 120°-Winkel. Bei größeren Punktmengen nicht mehr berechenbar. Für bis zu 19 Punkte gibt es laut Literatur noch exakte Lösungen.
Also Beispiel hier mal die Eckpunkte eines Einheitsquadrats.
Verbindet man die miteinander, entsteht eine Strecke der Länge 3.
Nimmt man den Hilfspunkt (0,5|0,5) und verbindet diesen mit jeder Quadratecke, entsteht eine Strecke der Länge 2*Wurzel2 = 2,83 schon besser.
Nimmt man 2 Hilfspunkte auf der waagrechten Geraden durch (0,5|0,5). Den rechten Hilfspunkt mit den rechten Quadratecken verbinden und links analog. Wenn jetzt in jedem Hilfspunkt mit den Verbindungslinien zu den Eckpunkten und der waagrechten Geraden genau 120° rauskommen, dann hat man die kürzeste Verbindung der 4 Eckpunkte eines Quadrats gefunden.
Ich versuch mal ne Skizze mitzuschicken, hab ich noch nie probiert (mein Scanner ist grad mal 2 Wochen alt)
Ciao, Andra |
Zaph (Zaph)
| | Veröffentlicht am Samstag, den 28. April, 2001 - 12:28: |
|
Bist du sicher, dass es sich hier um ein NP-schweres Problem handelt?? Bei P oder NP geht es doch immer um diskrete Probleme. Aber hier ist doch etwas "kontinuierliches" gesucht, denn die Hilfs-Punkte brauchen doch nicht auf dem Gitter zu liegen. |
Carsten
Unregistrierter Gast
| | Veröffentlicht am Sonntag, den 20. Februar, 2005 - 22:06: |
|
haha
tschuldigung das ich diesen alten Schmarn hier ausbuddle, aber ... hihi ich lach mich tot
Ich muss erhlich gestehen ich erinnere mich nicht mehr an das N=NP problem, daher weiss ich nicht ob hier was richtig ist. *ggg*
Aber wie schön ihr drüber diskutiert habt.
*grübel*
ne ich komm nicht drauf ;)
Morl99 |
|
