Dijikstra Algorithmus (Klausur)

Sehr schön, aber für die Laufzeit reicht das noch nicht ganz aus: anstatt das Maximum ab “k < i-2” zu suchen, solltest du bei der Variante das Maximum zwischen i-2 und i-5 suchen. Sonst müsste die Laufzeit doch 1+2+3+4+… werden, was nur mehr quadratisch nach oben abgeschätzt werden kann (kleiner Gauß), nicht mehr linear.

Hab alle bis auf das erste, das war mir dann doch zu einfach um draufzukommen.

Ich denk mal die erste Eigenschaft haben viele vergessen, weil der Name “Rot-Schwarz Baum”, bereits implizieren könnte dass der baum rote und schwarze knoten hat.
Natürlich ist das für einen aussenstehenden nicht 100% trivial, aber ich bin leider auch nicht drauf gekommen das hinzuschreiben

Wenn ein RS-Baum stattdessen xyz-Baum heißen würde, hätten es wahrscheinlich viele nicht vergessen hinzuschreiben.

Das ist ein bisschen so, als würde man bei den Merkmalen des Eiffelturms als erstes das Merkmal: “Turm” auflisten, obwohl es eigtl klar ist dass es sich um einen Turm handelt.

Wenn der Eiffelturm hingegen nur Eiffel hieße, wäre das Merkmal Turm schon um einiges sinnvoller^^

war wohl als “geschenkte”-punkte-aufgabe gedacht - und ging zumindest bei mir ordentlich nach hinten los …

gab’s denn auf jede eigenschaft einen punkt oder nen halben?

wie viele punkte gabs für die teilaufgabe mit der dyn programmierung?

ist die aussage: der kuerzeste weg in einem graph liegt immer auf einem minimalen spannbaum wahr oder falsch?

Micotom hat Folgendes geschrieben:

war wohl als “geschenkte”-punkte-aufgabe gedacht - und ging zumindest bei mir ordentlich nach hinten los … gab’s denn auf jede eigenschaft einen punkt oder nen halben?

Nein! Man bekommt bei der Klausur allgemein nur Punkte wenn man alles komplett richtig hat. Teillösungen fließen nicht in die Wertung mit ein. (Klar gibts das! )

6

Falsch

ich meinte die teilaufgabe b) die sich auf das dyn programmieren bezog. die gesamte aufgabe gab ja 6 punkte. (a+b+c)

Wir sind noch nicht mit dem Korrigieren fertig, kann sich also noch ändern.

Julien Oster hat Folgendes geschrieben:

Hallo, Lotta hat Folgendes geschrieben: -Wie ging die Aufgabe mit der dynamischen Programmierung? Ich kenne Longest Subsequence und Matrizenmultiplikation, aber bin leider immer noch nicht dahintergekommen, wie man die bzw. einen von denen modifizieren muss, damit auch die Lücken berücksichtigt werden (vielleicht habe ich auch zu kompliziert gedacht? bin nur immer wieder daran gescheitert, dass es doch auch Lösungen geben muss, wo mehr als 2 ausgelassen werden, um an eine bestimmte Sternanzahl zu kommen, die man sonst auslassen müsste) Und woher hätte man das können sollen (Hausaufgabe, Skript?!)? Als ich sie gelöst habe hab ich mich an Longest Increasing Subsequence orientiert, im Grunde ist das Problem ganz ähnlich. Und zwar so: Für jede Kirche i ist der Weg bis zu ihr (aber nicht notwendigerweise einschließlich der Kirche selbst!) das Maximum aus entweder der Summe an Sternen des Wegs bis zur Kirche unmittelbar vor ihr, also i-1, ohne die Sterne der Kirche i selbst, oder der Summe an Sternen des Wegs bis zur Kirche zwei Plätze vor ihr, also i-2, ebenfalls ohne die Kirche i selbst, oder der Summe an Sternen bis zur Kirche drei Plätze vor ihr, also i-3, diesmal einschließlich der Sterne der Kirche i selbst. Sonderfälle sind in den ersten drei Plätzen: dort muss man für Kirche i jeweils einfach nur das Maximum aus den vorherigen und der Kirche i selbst nehmen (und nicht etwa einfach nur die Anzahl Sterne der Kirche i selbst, wie es die meisten, die den Rest richtig haben gemacht haben). Einfach geht das, wenn man für (nicht existierende) Kirchen mit Index 0 oder kleiner einfach “0 Sterne” setzt. Daraus ergibt sich folgende Rekurrenz: die sich sehr leicht mit dynamischer Programmierung in einer Schleife angeben lässt. Danach sucht man einfach von hinten anfangend das maximale p_i und hat die maximale Anzahl Sterne. (Wenn man noch will kann man Vorgänger speichern um sich am Ende dann durchzuhangeln und so an die tatsächliche Sequenz zu kommen, aber in der Klausur war nur die Summe der Sterne verlangt.) Mindestens eine Variante ist noch möglich, bei der stattdessen die Indizes i-3, i-4 und i-5 angesehen und die Sterne der aktuellen Kirche immer dazugezählt werden. EDIT: Klarer gemacht, Rechtschreibfehler asugebessert

finds ehrlich gesagt unfair, so eine aufgabe zu stellen ohne jegliche tips/hinweise, die formel zu finden. denn wenn man nicht dahinter gekommen ist, konnte man auch schlecht etwas implementieren. erinnert mich mehr an ne aufgabe aus nem knobelheft, da die umsetzung in pseudocode ja trivial ist, sobald man hinter die formel gekommen ist. dazu natürliich die zeitliche begrenzung :/ .

das einzige, was einem das wissen aus der vorlesung gebracht hatte, war dass die lösung schrittweise aus teillösungen aufgebaut wird => dyn. programmierung, laufzeit O(n).

R-S-Bäume funktionieren auch mit gelben und grünen Blättern.

dann sinds aber G-G-Bäume xD

Informatiker malen sich ihre Bäume an, wie es Ihnen gefällt!

Weiß eigentlich jemand noch wie echte Bäume aussehen?

Naja, in der Vorlesung geht es eben um Algorithmen und Datenstrukturen, und eben auch darum, sich Algorithmen selbst zu überlegen. Nicht nur stures ausprogrammieren.

Das geht sogar soweit, dass nicht mal Pseudocode verlangt war. Das bloße Hinschreiben der Formal hat ausgereicht!

Und zum Thema “Knobelaufgaben”: Willkommen in der Informatik! Genau darum geht’s hier. Ohne zeitliche Begrenzung und Klausurdruck macht’s dann vielleicht auch mehr Spaß ;-D

Genau, und das Aufspalten in Teillösungen ist schon die halbe Miete. (O(n) ist es übrigens nicht unbedingt, nur weil es mit dynamischer Programmierung gelöst ist. In dem Fall aber schon.)

Wie werden egtl. die Punkte für die “Algorithmusersellungsaufgaben” vergeben?
Muss alles stimmen also Laufzeit und dass er funktioniert um überhaupt Punkte zu kriegen oder hat es gereicht, dass der Algorithmus fktioniert um überhaupt Punkte zu kriegen?
Und wenn der ALgorithmus nicht funktioniert krigt man trozdem Punkte wenn man eine gute Idee hatte aber einen kleinen Fehler hat und der Algorithmus deswegen nicht funktioniert?

Ein funktionierender Algorithmus gibt auf keinen Fall 0 Punkte, auch wenn er kleinere Fehler hat oder die Laufzeit nicht ganz stimmt. Wenn die Idee erkennbar ist, ist das meist schon was.

Was anderes sind allerdings (theoretisch doch irgendwie korrekte) Lösungen die, als Text formuliert, so etwas machen sollen wie “probiere alle möglichen Kombination aus und nehme die beste”. Dass das funktioniert ist klar, aber, äh.

Ich hab’s mit Greedy gelöst und denke, dass es sehr wohl funktioniert. Hab das ähnlich, wie die Aufgabe mit den Vorlesungen und der Raumverteilung gemacht.
Hab als Anfangswert i und als Endwert i+3 genommen, dann alle kompatiblen Möglichkeiten mit Greedy herausgefunden. So habe ich alle möglichen Wege erhalten. Bei jedem hinzunehmen eines (i, i+3) habe ich die Sterne von i dem Weg dazuaddiert.
Am Ende wird einfach der Weg mit dem größten “Sternwert” ausgegeben.

Ich hoffe mal, dass das so passt und auch so verstanden wird… hab da in der Klausur eeend viel geschrieben

“Greedy” ist allerdings kein Algorithmus sondern eine Klasse von Algorithmen, und bedeutet vereinfacht ausgedrückt nichts anderes, als immer die momentan beste Teillösung zu nehmen.

Der Algorithmus zur Raumverteilung ist ein Beispiel für einen Greedy Algorithmus.

Wenn ich mich nicht irre hast du damit nur 3 Wege angelegt. Alle besuchen jede 3. Kirche, nur die erste besuchte Kirche und damit der weitere Versatz ist anders. Wege, die vielleicht mal 3 oder 4 statt 2 Kirchen auslassen gibt’s hier gar nicht.

Wie schon gesagt gab es oft den Versuch, einen Greedy-Algorithmus für dieses Problem zu konstruieren (die meisten wesentlich einfacher: Summe der Sterne immer mit der momentan besten Kombination hochzählen).

Das geht aber nicht! Egal wie man es macht, wenn man sich vorzeitig auf eine momentan beste Teillösung festlegt (anstatt sich wie in allgemeinerer dynamischer Programmierung mehrere Teillösungen offen zu halten), dann kann man mit Pech immer auf das Problem stoßen, dass eine Kirche die viereinhalb Milliarde Sterne bringen würde nicht mehr besucht werden kann, weil der bisherige Weg genau vor ihr hält.

ja mist…. in der Klausur erschien der mir (und anscheinend vielen anderen) logisch…

Um es nochmal ganz klar zu machen: es gibt nicht “den Greedy Algorithmus”, das ist ein Missverständnis! Sieh das Wort “greedy” (zu deutsch “gierig”) eher als adjektiv, also als Eigenschaft eines Algorithmus.

Dieser Raumverteilungsalgorithmus löst ein ganz spezielles Problem. Ein anderes Beispiel für einen Greedy Algorithmus ist der Dijkstra-Algorithmus zum Finden kürzester Wege, der selbe der auch in der Klausur vorkam und Namensgeber dieses Threads ist! 8)

Der funktioniert zum Beispiel ganz anders, hat aber mit allen Greedy Algorithmen gemein, dass alle anderen Teillösungen zu Gunsten der momentan günstigsten verworfen werden.

was die Korrektoren davon gehalten haben siehst du ja bei der Einsicht…. ist ja müßig sich zu “beschweren” bevor das Ergebnis da ist(bald???)

Wo/wann/in welcher Form haben wir denn longest increasing subsequence != longest common subsequence gemacht?

Und: Habe ich das richtig verstanden, es hätte also die Formel gereicht? Man will ja vorbereitet sein für Klausur 2!

Das war eines der späteren Übungsblätter, welches genau müsste ich jetzt auch nachschauen…

Nachdem in der Angabe stand, dass es ausreicht, die Rekurrenz niederzuschreiben: ja! 8)

Julien Oster hat Folgendes geschrieben:

Nachdem in der Angabe stand, dass es ausreicht, die Rekurrenz niederzuschreiben: ja!

ich glaube den Fachbegriff hat keiner verstanden…. vor allem weil da so viel Platz zum schreiben war ^^

*unterschreib*