T max Summe < Algor.+Datenstr. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
Hallo liebes Forum,
habe mal wieder ein kleines Problem. Habe folgendes Java-Prog geschrieben, welches für die Folge "folge" die Teilfolge maximaler Summe berechnet und dann das Tripel (<firstElem>, <lastElem>, <Summe>) ausgibt. Funktioniert prima - hat mir schon einiges Kopfzerbrechen bereitet.
Vielen Dank im voraus und liebe Grüße, Janine
P.S. Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 12:18 Sa 13.05.2006 | | Autor: | Frank05 |
> Hallo liebes Forum,
Hallo Janine,
> habe mal wieder ein kleines Problem. Habe folgendes
> Java-Prog geschrieben, welches für die Folge "folge" die
> Teilfolge maximaler Summe berechnet und dann das Tripel
> (<firstElem>, <lastElem>, <Summe>) ausgibt. Funktioniert
> prima - hat mir schon einiges Kopfzerbrechen bereitet.
Das hat DP am Anfang so an sich  wenn man sich aber mal dran gewöhnt hat ists nicht der Rede wert.
> public class Maxsumme {
>
> int[] TeilfolgeMaxSumme(final int[] folge) {
>
> int[][] s = new int [folge.length] [folge.length];
> int[] max = new int[3];
> max[2] = Integer.MIN_VALUE;
>
> int[] leer = new int[3];
> leer[0] = 0;
> leer[1] = 0;
> leer[2] = 0;
>
> for (int i = 0; i < folge.length; i++) {
> for (int j = 0; j < folge.length; j++) {
> s[j] = 0;
> }
> }
>
> s[0][0] = folge[0];
>
> for (int bis = 1; bis < folge.length; bis++) {
> s[0][bis] = s [0][bis - 1] + folge[bis];
> }
>
> for (int von = 1; von < folge.length; von++) {
> for (int bis = von; bis < folge.length; bis++) {
> s[von][bis] = s[von - 1][bis] - folge[von - 1];
> }
> }
>
> for (int von = 0; von < folge.length; von++) {
> for (int bis = 0; bis < folge.length; bis++) {
> if (max[2] < s[von][bis]) {
> max[0] = von; max[1] = bis;
> max[2] = s[von][bis];
> }
> }
> }
>
> if (folge.length == 0)
> return leer;
>
> else
> return max;
> }
>
> public static void main(String[] args) {
>
> Maxsumme t = new Maxsumme();
> final int[] folge = {-1, 3, 2, -4, 5, -7, 2, 2, -3, 5, -2,
> 3, -8, 2};
> //final int[] folge = {0};
>
> int[] erg = new int[2];
> erg = t.TeilfolgeMaxSumme(folge);
>
> System.out.println((erg[0]+1) + " " + (erg[1]+1) + " " +
> erg[2]); //+1, weil wir das Array bei 1 anfangen zu zählen
> }
> [i]}[/i][/blue]
>
> Meine Fragen dazu:
> a) wie kann ich zeigen/begründen, dass mein Algorithmus
> terminiert?
> b) Wie kann ich zeigen/begründen, dass der Algorithmus die
> Spezifikation erfüllt, dass wenn mehrere Teilfolgen
> maximaler Länge existieren, diejenige mit minimalem Beginn
> "von" und als 2. Kriterium mit minimaler Länge "bis-von"
> gewählt wird? -> Korrektheit
>
> Vielen Dank im voraus und liebe Grüße, Janine
>
> P.S. Ich habe diese Frage in keinem Forum auf anderen
> Internetseiten gestellt.
Zur Terminierung:
Da gibt es nicht viel zu zeigen. Du hast keine einzige Anweisung, die zu einer eventuellen Nichtterminierung führen könnte. Das Problem ist eher relevant, wenn du Rekursionen, oder while Schleifen hast.
Wenn du es ganz formal zeigen willst könntest du dein Programm als LOOP Programm angeben. Damit ist Terminierung automatisch gegeben.
Zur Korrektheit:
Zerlege den Algorithmus in seine Bestandteile:
1. DP-Array initialisieren
2. DP-Array füllen
3. Ergebnis ermitteln
Der interessante Teil ist dann bei 2. zu zeigen, dass in s[i][j] immer die Summe der Folgenwerte von i bis j steht. Das machst du am besten mit einer Induktion (bietet sich auch an, wenn du einen Blick auf die Implementierung wirfst, da du ja dort im Prinzip auch nur von der Induktionshypothese Verwendung machst).
In Schritt 2 wirst du einen Induktionsanfang benötigen, den dir Schritt 1 liefern sollte.
In Schritt 3 kannst du dann noch die Argumentation bezüglich mehrdeutigen Lösungen einbringen. Hier führst du am besten einen Widerspruchsbeweis und nimmst an du hättest zwei maximale Lösungen. Dann kannst du zeigen, dass dein Algorithmus diejenige mit dem kleineren 'von' Wert nimmt (bei zwei unterschiedlichen 'von' Werten), oder eben diejenige mit minimaler Länge.
hth,
Frank
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 12:26 Sa 13.05.2006 | | Autor: | Frank05 |
Hier sind noch ein paar Anmerkungen zum Programm, die jetzt nicht direkt mit deiner Frage zu tun haben:
> public class Maxsumme {
>
> int[] TeilfolgeMaxSumme(final int[] folge) {
>
> int[][] s = new int [folge.length] [folge.length];
Das ist ziemlich viel Speicher bei entsprechender Folgenlänge. Es genügt auch:
int [] [] s = new int [folge.length][2];
> int[] max = new int[3];
> max[2] = Integer.MIN_VALUE;
>
> int[] leer = new int[3];
> leer[0] = 0;
> leer[1] = 0;
> leer[2] = 0;
>
> for (int i = 0; i < folge.length; i++) {
> for (int j = 0; j < folge.length; j++) {
> s[j] = 0;
> }
> }
Diese Initialisierung kannst du dir sparen. Du belegst s[0][i] sowieso nochmal manuell und der eigentliche DP Algorithmus wird keinen Wert betrachen, der nicht schon vorher belegt wurde.
>
> s[0][0] = folge[0];
>
> for (int bis = 1; bis < folge.length; bis++) {
> s[0][bis] = s [0][bis - 1] + folge[bis];
> }
>
> for (int von = 1; von < folge.length; von++) {
> for (int bis = von; bis < folge.length; bis++) {
> s[von][bis] = s[von - 1][bis] - folge[von - 1];
> }
> }
>
> for (int von = 0; von < folge.length; von++) {
> for (int bis = 0; bis < folge.length; bis++) {
> if (max[2] < s[von][bis]) {
> max[0] = von; max[1] = bis;
> max[2] = s[von][bis];
> }
> }
> }
Diesen zweiten Durchlauf kannst du auch in den ersten und die Initialisierung integrieren (aber natürlich ist es so sauber getrennt und verständlicher, was sich auch für den Beweis vorteilhaft gestaltet)
>
> if (folge.length == 0)
> return leer;
>
> else
> return max;
> }
>
> public static void main(String[] args) {
>
> Maxsumme t = new Maxsumme();
> final int[] folge = {-1, 3, 2, -4, 5, -7, 2, 2, -3, 5, -2,
> 3, -8, 2};
> //final int[] folge = {0};
>
> int[] erg = new int[2];
> erg = t.TeilfolgeMaxSumme(folge);
Du legst also ein Array der Größe 2 an, und weißt ihm das Ergebnisarray der Größe 3 zu. Quizfrage: Warum funktionierts trotzdem? 
>
> System.out.println((erg[0]+1) + " " + (erg[1]+1) + " " +
> erg[2]); //+1, weil wir das Array bei 1 anfangen zu zählen
> }
> }
|
|
|
| |
|
Hallo Frank,
also erstmal vielen Dank für Deine Antworten! Die Termination und die Korrektheit bekomme ich jetzt problemlos bewiesen. Auch deine Anmerkungen weiss ich sehr zu schätzen, danke. Manchmal mach ichs was kompliziert oder umständlich, dafür ist es aber (für mich) besser verständlich/nachvollziehbar.
Zur Quizfrage: es funktioniert trotzdem, da max[3] nie gefüllt wird, es also eigentlich "nur" ein 3-elementiges Array ist und deshalb die Zuweisung funktioniert. max[2]->erg[2] Oder?
LG, Janine
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 15:35 Sa 13.05.2006 | | Autor: | Frank05 |
> Hallo Frank,
Hallo Janine,
> also erstmal vielen Dank für Deine Antworten! Die
> Termination und die Korrektheit bekomme ich jetzt
> problemlos bewiesen. Auch deine Anmerkungen weiss ich sehr
> zu schätzen, danke. Manchmal mach ichs was kompliziert oder
> umständlich, dafür ist es aber (für mich) besser
> verständlich/nachvollziehbar.
Sollte auch kein Vorwurf sein. Gerade wenn man etwas darauf beweisen will ist es oft besser so. Optimierungen können warten. Ob die Laufzeit nun O(3*n*n) oder O(30*n*n) ist spielt ja nicht wirklich die große Rolle
> Zur Quizfrage: es funktioniert trotzdem, da max[3] nie
> gefüllt wird, es also eigentlich "nur" ein 3-elementiges
> Array ist und deshalb die Zuweisung funktioniert.
> max[2]->erg[2] Oder?
Vorsicht.. max ist ein 3-elementiges Array, hat also nur max[0], max[1] und max[2]. Auf max[3] zuzugreifen würde eine Exception verursachen. Genauso wie es eigentlich bei erg passieren würde. Du legst es als 2-elementiges Array an, und damit gibt es erg[0] und erg[1]. In der Ausgabe greifst du aber auf erg[2] zu und nichts passiert. Du bist also etwas an der eigentlichen Frage vorbeigefahren
Viel Spaß beim Grübeln,
Frank
|
|
|
| |
|
Hey Frank,
also: habe herausgefunden, dass es bei der Initialisierung des Arrays
int[] erg = new int[2];
völlig egal ist, ob man new int[2] oder new int[8] oder gar new int[0] nimmt, also muss die Länge des Arrays von "etwas anderem" noch beeinflusst werden.
Denke mir, dass durch die Init. von
Maxsumme t = new Maxsumme();
in dieser Methode nachgeschaut wird, welche Variable zurückgegeben wird (-> max[]) um dann schließlich an dem Punkt
erg = t.TeilfolgeMaxSumme(folge);
das Array erg[] *irgendwie* zu modifizieren... !?!?!
Also wenn's das nicht ist, sag' mir doch bitte, Frank, warum mein Java-Programm so mysteriöse Dinge tut... Bin etwas verwirrt und mich würde echt mal interessieren, was da passiert.
Liebe Grüße, Janine
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 12:04 So 14.05.2006 | | Autor: | Frank05 |
> Hey Frank,
Morgen,
> also: habe herausgefunden, dass es bei der Initialisierung
> des Arrays
>
> int[] erg = new int[2];
>
> völlig egal ist, ob man new int[2] oder new int[8] oder gar
> new int[0] nimmt, also muss die Länge des Arrays von "etwas
> anderem" noch beeinflusst werden.
Richtig und dann auch wieder nicht. Bei der Initialisierung wird erg tatsächlich der Array zugewiesen, den du angibst.
> Denke mir, dass durch die Init. von
>
> Maxsumme t = new Maxsumme();
>
> in dieser Methode nachgeschaut wird, welche Variable
> zurückgegeben wird (-> max[])
Nein. Soviel Magie passiert da nicht. Vor allem schonmal gar nicht zur Laufzeit. Wenn du das weiterdenkst, dann muss das bei jeder Objektinstanzierung passieren und den gesamten Quellcode überprüfen.. das ist nicht sinnvoll.
> um dann schließlich an dem
> Punkt
>
> erg = t.TeilfolgeMaxSumme(folge);
>
> das Array erg[] *irgendwie* zu modifizieren... !?!?!
An dieser Stelle passierts.. und zwar wird der Array nicht modifiziert, sondern schlichtweg überschrieben. Wie du ihn initialiasiert hast spielt keine Rolle, weil die Zuweisung dafür sorgt, dass erg auf das zurückgegebene Array zeigt. Das Initialisierungsarray kassiert an dieser Stelle übrigens der Garbage Collector ein.
Langer Rede kurzer Sinn, das folgende hätts auch getan:
int [] erg = t.TeilfolgeMaxSumme(folge);
> Also wenn's das nicht ist, sag' mir doch bitte, Frank,
> warum mein Java-Programm so mysteriöse Dinge tut... Bin
> etwas verwirrt und mich würde echt mal interessieren, was
> da passiert.
Mysteriös würd ich das jetzt nicht nennen.. da solltest du erstmal C programmieren und ein paar Zeiger durch die Gegend biegen ;)
Trotzdem weiterhin viel Spaß mit Java,
Frank
|
|
|
|
