Lösungsstrategie foo #5 Bellman-Ford

Rene Eichler
Mausschubser
Mausschubser
Beiträge: 57
Registriert: 13. Apr 2015 15:25

Re: Lösungsstrategie foo #5 Bellman-Ford

Beitrag von Rene Eichler »

Jap hab auch ne ziemlich gute Bilanz:

1/11 Richtig

Glaub ich bin für GDI 2 nicht geeignet. Kann nicht gut genug Kopfrechnen.

Mal zum Vergleich:

B-Tree : Remove (welches angeblich das schwierigste Thema sein soll) habe ich zu 70% bestanden und Bellman-Ford zu 14% (Bei mittlerweile 14 Versuchen).

Haben die Veranstalter die Aufgabe eigentlich mal selber gemacht? Würde mich mal interessieren wie hoch da die Erfolgsquote ist.

headhumper
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 118
Registriert: 13. Aug 2009 21:25

Re: Lösungsstrategie foo #5 Bellman-Ford

Beitrag von headhumper »

Ich fand' B-Tree: remove ehrlich gesagt auch ziemlich einfach - wenn man es mal verstanden hat. Das "Verstehen" dauerte zwar länger, aber zum Schluss konnte ich die Aufgaben im Übungsmodus in 60-90 Sekunden zu 100% lösen. Da habe ich auch nicht verstanden, warum die Aufgabe im Testatmodus nochmal deutlich einfacher war.

Bellman-Ford hat man in einem Satz erklärt und sofort verstanden - "nimm dern kürzesten Pfad mit maximal i+1 Kanten". Geschenkt. Im Übungsmodus bin ich aber nie über 50% Erfolgsquote gekommen und habe pro Aufgabe mehrere Minuten gebraucht, meistens war nur ein Weg falsch. Beim Testat hat es zum Glück beim ersten Mal geklappt, da gab es auch einen Knoten weniger.

Insgesamt finde ich nach wie vor, dass die Aufgabe Bellman-Ford in der jetzigen Form komplett am Ziel vorbeischießt. Ich möchte das wirklich als konstruktive Kritik verstanden wissen: Der Algo ist nicht schwer, man soll die Invariante verstehen. Das ist super, aber die Aufgabe in Foo setzt das leider so gar nicht um, denn wie bereits angemerkt wurde ist i häufig groß genug um einfach stumpf immer den kürzesten Pfad nehmen zu können, von allen Aufgaben die ich gemacht habe gab es genau eine, wo ich einen kürzesten Pfad nicht nehmen konnte, weil er eine Kante zu lang war.

Dazu kommt die unnötige Verkomplizierung, dass man die Pfade "sehen muss" und sie sich nicht herleiten kann.

Aufgaben wie diese sorgen wirklich für extremen Frust, auch oder gerade weil man nichts über den Algorithmus lernt.

Mein Verbesserungsvorschlag wäre, i (nur) im Bereich 1-3 variieren zu lassen. Zusätzlich sollte es auch im Übungsmodus mindestens einen (vielleicht auch zwei) Knoten weniger geben. Das würde die Fehlerwahrscheinlichkeit deutlich senken und man müsste vielleicht auch tatsächlich mal an die Invariante denken.

Rene Eichler
Mausschubser
Mausschubser
Beiträge: 57
Registriert: 13. Apr 2015 15:25

Re: Lösungsstrategie foo #5 Bellman-Ford

Beitrag von Rene Eichler »

Ja kann ich absolut bestätigen. Bei B-Tree: Remove hat es anfangs ewig gedauert um zu verstehen, wann denn eigentlich ein Shift und wann ein Rotate gemacht wird usw. Das Wissen was man daraus gewonnen hat ist aber um einiges brauchbarer wie bei Bellman-Ford. Bei B-Tree hat man etwas falsch gemacht, weil man noch nicht mit den ganzen Invarianten vertraut war. Bei Bellman-Ford macht man Fehler, weil der Graph einfach viel zu komplex ist. Man übersieht so schnell einen kürzeren Pfad. Das hat einfach überhaupt nichts mit Wissen oder Können zu tun. Ich habe sage und schreibe 7 % richtig bei über 20 Versuchen. Um genau zu sein habe ich nur ein einziges Mal die Aufgabe richtig lösen können. Meistens war nur ein Knoten falsch und das ist nach 7-10 Minuten dermaßen frustrierend. Ich hatte gerade mein Testat und kann schon mal alle beruhigen, die es noch vor sich haben. Die Komplexität ist auf jeden Fall geringer wie im Übungsmodus und die Aufgabe mit etwas Konzentration auch machbar. Es ist halt wirklich schade, dass man bei diesem Algorithmus einfach nur gut einen kürzesten Weg erkennen muss und die Kanten richtig addiert. Das hat doch nichts mit Verstehen eines Algorithmus zu tun. Bei meinen 25 Versuchen (inkl. Testat) musste ich nicht ein Mal darauf achten, ob ich die Invariante einhalte....

Die Komplexität war zwar im Testat geringer aber ich finde so eine willkürliche Aufgabe darf nicht herangezogen werden um die Kompetenz für die Prüfung zu erwerben, bzw. die Prüfungszulassung zu erhalten. Ich hätte mich wahrscheinlich auch umgehend beschwert, wenn ich das Testat wegen dieser Aufgabe nicht bestanden hätte.

Naja ich hoffe einfach mal, dass die Verantwortlichen die Konsequenz daraus ziehen und wünsche allen, die ihr Testat noch vor sich haben, viel Erfolg (und auch ein wenig Glück :D )

Prof. Karsten Weihe
Dozentin/Dozent
Beiträge: 1824
Registriert: 21. Feb 2005 16:33

Re: Lösungsstrategie foo #5 Bellman-Ford

Beitrag von Prof. Karsten Weihe »

Rene Eichler hat geschrieben: Die Komplexität war zwar im Testat geringer aber ich finde so eine willkürliche Aufgabe darf nicht herangezogen werden um die Kompetenz für die Prüfung zu erwerben
Ich finde das Wort "willkürlich" ehrlich gesagt nicht angemessen.

Sie dürfen gerne konstruktive Vorschläge für einen anderen Aufgabentyp zu Bellman-Ford machen, würden wir dann bei Gelegenheit implementieren.

KW

headhumper
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 118
Registriert: 13. Aug 2009 21:25

Re: Lösungsstrategie foo #5 Bellman-Ford

Beitrag von headhumper »

Prof. Karsten Weihe hat geschrieben:Sie dürfen gerne konstruktive Vorschläge für einen anderen Aufgabentyp zu Bellman-Ford machen, würden wir dann bei Gelegenheit implementieren.
Was halten Sie von dem Vorschlag, die Knotenzahl sowohl im Übuns- als auch im Testatmodus auf 5 zu beschränken und die Anzahl Iterationen im Bereich 1-3 zu variieren?
Selbst wenn die Knotenzahl nicht verändert wird: i sollte deutlich kleiner werden, damit man auch tatsächlich mal an die Invariante denken muss.

Rene Eichler
Mausschubser
Mausschubser
Beiträge: 57
Registriert: 13. Apr 2015 15:25

Re: Lösungsstrategie foo #5 Bellman-Ford

Beitrag von Rene Eichler »

Wenn mein Beitrag unangemessen war, dann möchte ich mich dafür entschuldigen. Wie wäre es denn z.B. statt einem ungerichteten Graphen einen gerichteten zu nehmen und wie schon gesagt, dass i etwas geringer zu wählen. Dann braucht man auch nicht so einen komplexen Graphen, denn man muss ja darauf achten, nicht zu viele Kanten zu nehmen und schauen, ob von einem Knoten aus jeder andere Knoten überhaupt erreichbar ist. Dann könnte auch mal das 'INF' zur Anwendung kommen.

headhumper
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 118
Registriert: 13. Aug 2009 21:25

Re: Lösungsstrategie foo #5 Bellman-Ford

Beitrag von headhumper »

Bei einem gerichteten Graphen funktioniert der "Trick" dann aber nicht mehr, dass man nur die Hälfte der Pfade "berechnen" muss aka die Matrix symmetrisch ist, also muss man auf jeden Fall die Knoten-/Kantenzahl angemessen verringern.

Bellman-Ford mit einem gerichteten Graphen klingt ansonsten aber ganz interessant.

h_ar
Mausschubser
Mausschubser
Beiträge: 99
Registriert: 16. Apr 2015 19:56

Re: Lösungsstrategie foo #5 Bellman-Ford

Beitrag von h_ar »

Ich fand das Testat ehrlich gesagt nicth schwer und hatte BF glaube ich insgesamt 3mal am Abend davor und dann 3mal vorm Testat geübt.

Das einzige was man verbessern könnte wäre echt das mit dem INF, denn das habe ich nicht einmal benutzen müssen.

Antworten

Zurück zu „Archiv“