TernarySearch
Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.
Aufgabe 4.6
Ich habe mal eine Frage aus dem Vorgehen des TernarySearch-Algorithmus, die am besten mit einem Beispiel erklärt ist:
Nimmt man als Funktion f(x) = -x^3 + 10x^2 - 3x + 1 (http://www.wolframalpha.com/input/?i=-x^3+%2B+10+x^2+-+3x+%2B+1), so kann man (durch probieren) feststellen, dass f(8) ungefähr gleich f(4.74165) ist. Wählt man sein Untersuchungsintervall so, dass diese beiden Stellen gerade die Drittel des Intervalls sind, dann schlägt Wikipedia vor, entweder das mittlere Intervall auszuwählen oder die linken 2/3 oder die rechten 2/3. Da das Minimum der Funktion aber gerade auf dem rechten Rand des Intervalls liegt, führen die ersten beiden Möglichkeiten nicht zur richtigen Lösung.
Meine Frage daher: Was ist zu tun, um solche (pathologischen) Fälle zur richtigen Lösung zu führen? Oder soll man davon ausgehen, dass das Minimum im Inneren des Intervalls liegt (womit dann aber die Testfälle in TernarySearchTest.java schiefgehen)?
Kannst du erklären, welcher Test in TernarySearchTest bei welcher Implementierung schief gehen kann?
Das lineare Polynom und das quadr. Polynom 0.5x^2 - x haben auf dem gegebenen Intervall ihr Minimum auf dem Rand, weswegen die Option, den Rand auszuschließen wegfällt.
Aber es hat sich schon durch weitere Internetrecherche erübrigt. Der Algorithmus liefert nur für Funktionen gesichert das richtige Ergebnis, wenn sie links vom Minimum streng monoton fallen und rechts davon streng monoton steigen. Damit kann mein Beispiel gar nicht auftreten (vorausgesetzt die Funktionen sind stetig).
Darf dann angenommen werden, dass die übergebenen Funktionen diese Eigenschaft erfüllen?
Ah stimmt, die Option das mittlere Drittel zu nehmen ist nicht vorgesehen.
Welche der Beiden anderen Lösungen bei Gleichheit implementiert wird ist egal.
Dass der Algorithmus nicht immer das richtige Ergebnis liefert wird berücksichtigt 
Es werden nur Polynome uebergeben → die Funktionen sind stetig
Das ist mir schon bewusst :). Es ging eher um die Monotoniebedingung (die Polynome nicht zwangsläufig erfüllen).
Danke für das Klarstellen mit der Wahl des Teilintervalls. Im Wikipedia war das ja nur als Bemerkung in Klammern angegeben.
Ich hab auch mal ne Frage zu der Aufgabe:
Ich hab jetzt die a) meiner Meinung nach genau so Implementiert wie sie auf der Wiki-Seite als Pseudo-Code steht
Leider bekomm ich beim Testen immer noch folgende Fehlermeldung vom Testcase:
“TernarySearch 0: 0 solutionSequential: -1.0 result: 0.9999999999592042”
Wenn ich das jetzt richtig versteh verschieb ich die Grenzen des Intervalls ja dann genau in die falsche Richtung oder?
Hat jemand ne Ahnung wo bei mir der Fehler liegen könnte?
ja, und zwar hier:
lies nochmal was der code macht und was du berechnen sollst
hmm ja der Code auf Wiki berechnet ja ein Maximum und kein Minimum, aber ich grenze ja bei beiden Varianten gleich ein, deswegen sollte da ja nicht das Problem liegen…
deswegen weiß ich jetzt nicht was ich da anders machen sollte
doch :scared:
Du musst aaaaaaaaaaaaaaaaaaaaaaalles abändern :rolleyes:
Einmal drüber nachdenken und die Änderung dauert weniger als eine Sekunde.
Also jetzt nochmal
Die Frage mit dem TestCase bleibt aber trotzdem wie man auch an NeubauMa’s Ausgabe sehen kann.
Es kommt alles auf die Genauigkeit an. Wir haben keine gegeben, uns wird nicht gesagt ob wir da dann runden sollen oder nicht, gar nichts.
Das fuehrt dazu dass meine Implementierung im allerersten TestCase ab -0.9999999999999997 einfach nicht mehr weiterschachtelt, da ab dieser Genauigkeit die Intervallgrenzen sich nicht mehr aendern.
Ist ja auch logisch, nur brauch ich irgend eine Art Ansage was ich in diesem Fall tun soll, da ich so offensichtlich nicht vorgehen kann da assert sich nicht um Genauigkeit schert sondern einen eindeutigen Wertvergleich macht, und da logischerweise -0.9999999999999997 nicht gleich 1 ist.
Noch dazu dass mein Programm so wie es ist hier dann logischerweise endlos weiterlaeuft, weil die erforderte Genauigkeit nie erreicht wird(werden kann).
Daher die Frage: Soll ich runden, einfach abbrechen wenn die Intervallgrenzen gleich sind (Ergebnis ist dann logischerweise falsch, also keine gute Option) oder was sonst kann ich tun?
Ja, wenn du dir die Testcases anschaust, siehst du dass die Ausgaben prinzipiell als Fehler ausgegeben werden (auch wenn der Test durchläuft).
Edit: gleich ist zu stark, du willst ja keine doubleWerte mit == vergleichen.
Ich nehme aber an, dass du das richtige meinst.
Edit2:
MethodeSchau dir den Testcase mal genau an und schau dir die an, die da verwendet wird. Dann wirst du feststellen, dass der Vergleich schon funktioniert.
Allerdings darf deine Methode halt trotzdem kein Maximum suchen, sondern muss ein Minimum finden.
Waren ziemlich genau 2 Sekunden Danke für den Anstoss!
Ich kann TernarySearchTest gar nicht erst kompilieren
TernarySearchTest.java:3: error: package org.junit does not exist
import static org.junit.Assert.*;Was mache ich falsch, bzw. was habe ich noch nicht richtig gemacht?
Class Path mit dem Parameter [m]-cp[/m] anpassen und Pfad zur JUnit.jar hinzufügen.
vielen dank
4.6 b
Hi! Hab ich die Aufgabenstellung richtig verstanden: das min. von jeder übergebenen Funktionen soll mit Hilfe von nThreads gesucht werden?
Z.b., wenn ich eine Ausschnitt hab, wo die linke Grenze -1 und die rechte 1 ist und nThreads gleich 4, dann soll ich über 4 Abschnitte laufen, die zwischen -1 und 1 liegen und für jeden Abschnitt einen neuen thread starten?
Danke!
4.6 c
Hallo,
soll man bei der 4.6 c einen newFixedThreadPool für nThreads erstellen; könnte es dann nicht sein, dass zu viele Callable-Objekte vorhanden sind und der Thread Pool voll ist?
Falls wir das wirklich so machen sollen: Wie kann man abfragen, ob zum Thread-Pool ein Callable-Objekt hinzugefügt werden kann, um sicherzustellen, dass ein submit möglich ist?
Ich frage deshalb, weil es aus meiner Sicht sinnvoller wäre, wenn man direkt einen Thread-Pool mit Kapazität für f.length Callable-Objekte erstellt.
Danke
Hallo. Ist bei (a) rekursiv zu berechnen erlaubt? Danke im Voraus.