Repetitorien vor der Klausur

Benutzeravatar
marlic
Computerversteher
Computerversteher
Beiträge: 365
Registriert: 5. Okt 2006 11:09
Wohnort: Dietesheim

Beitrag von marlic »

tgp hat geschrieben:G 4.4 b) Lösungshinweise:

Wieso ermittelt Dijkstra für den Weg von A nach C die Länge 2? Wenn ich das mit dem im fünften Foliensatz vorgestellten Dijkstra mache, wird der (mit 1 bessere) Weg über B trotzdem gefunden.

Eine Möglichkeit wäre, dass ein Algorithmus den direkten Weg von A nach C (Länge 2) gefunden hat, und es dann nicht mehr über B versucht, da die Kante mit Länge 4 schon zu lang ist. Das wäre dann aber nicht mehr Dijkstra, denn beim "single-source shortest path"-Problem müsste diese trotzdem betrachtet werden, um den kürzesten Weg von A nach B zu finden.
zum Graph von b)

Naja, wie funktioniert denn Dijkstra?

Angenommen, es gibt keine negativen Kantengewichte.

Die Menge M1 (Also "kürzesten Weg bereits bestimmt") enthält zuerst nur A (0).
in M2 ist gespeichert, das C in zwei Schritten und B in 4 Schritten erreicht werden kann.

Das impliziert nach der Annahme, dass alle Wege die über B führen mindestens ebenfalls 4 Schritte benötigen.

Also darf der Knoten C in M1 aufgenommen werden, da 2 kleiner als 4 ist, also jeder Weg über B länger sein muss.

Da von C keine Kante ausgeht, wird im nächsten Schritt B zu M1 hinzugenommen und der Algorithmus terminiert, da alle Knoten in M1 sind.

Man sieht also, dass die Annahme, es existierten keine negativen Kantengewichte zu falschen Ergebnissen führt, falls diese doch existieren.

Klarer umrissen ist sogar eine Notwendige Bedingung dafür, dass Dijkstra funktioniert in der Musterlösung:

"Der Algorithmus von Dijkstra funktioniert nicht mehr, sobald ein negativer Weg
nachträglich eine bereits in M1 aufgenommenen Knoten verbessern würde."
"Copy & Passed"

Wahlspruch der Plagiatoren

tgp
Sonntagsinformatiker
Sonntagsinformatiker
Beiträge: 268
Registriert: 15. Nov 2006 21:41

Beitrag von tgp »

Ah ok ich seh jetzt, wo das Problem liegt: Der Algorithmus im fünften Foliensatz, Folie 61 überprüft nicht, ob die Nachbarn w von v in M1 sind. Das muss er auch nicht, da die darin enthaltenen Knoten nicht mehr verbessert werden können (vorrausgesetzt, es existieren keine negativen Kanten). Dies passiert aber genau beim Beispielgraph, der "else if"-Teil wird ausgeführt. So gesehen funktioniert Dijkstra bei negativen Kanten und dem Graph aus den Lösungshinweisen doch ;)

Ein Beispiel, bei dem Dijkstra (in der durch den Code dargestellten Form) nicht funktioniert:

A-(10)->B
A-(7)->C
B-(-4)->C
C-(2)->D


Danke marlic :)

banshee
Nerd
Nerd
Beiträge: 684
Registriert: 22. Okt 2006 18:46

Beitrag von banshee »

wieso munter? du musst einfach alphabetisch sortieren

aldara
Windoof-User
Windoof-User
Beiträge: 27
Registriert: 17. Sep 2007 12:16

Beitrag von aldara »

Mal ne andere Frage: Wo finden die Repetitorien denn statt? Ich hab bisher nur die Urzeit gefunden.

wzhang
Erstie
Erstie
Beiträge: 15
Registriert: 9. Mär 2006 10:59

Beitrag von wzhang »

es steht in der KW38, aber wo ist das?

tgp
Sonntagsinformatiker
Sonntagsinformatiker
Beiträge: 268
Registriert: 15. Nov 2006 21:41

Beitrag von tgp »

KW=Kalenderwoche=Woche vom 17.9. bis 23.9.

Benutzeravatar
unschuldslamm
Kernelcompilierer
Kernelcompilierer
Beiträge: 422
Registriert: 28. Okt 2004 09:24

Beitrag von unschuldslamm »

wo != wann

Das wo steht auf den Webseiten von GdI2.....
Maybe in Ohio, but not in America!

Benutzeravatar
Dirk
Windoof-User
Windoof-User
Beiträge: 33
Registriert: 17. Okt 2005 19:41
Wohnort: Darmstadt
Kontaktdaten:

Beitrag von Dirk »

Hallo!
Wir hängen gerade an folgendem etwas unverständlichen Satz über den Bellman und optimale binäre Suchbäume:
Folie 9 Seite 84: "•Einfach erweiterbar (s. Skript):
Suchwahrscheinlichkeiten für erfolglose Suche(Lücken) zwischen den vorhandenenSchlüsseln"

Könnte einer vielleicht kurz erklären was damit gemeint ist? Geht es da um eine Erweiterung des Algos über den Aufbau der Bäume oder um die Suche darin?
Eine Erklärung wäre nett ;)

Benutzeravatar
corn
Ehemalige Fachschaftler
Beiträge: 28
Registriert: 17. Okt 2004 19:08
Wohnort: Groß-Umstadt
Kontaktdaten:

Beitrag von corn »

Es geht darum, dass das Problem vereinfacht wurde. Man geht hier davon aus, dass nur nach den entsprechenden Schlüssel mit der gegebenen Suchwahrscheinlichkeit gesucht wird und nicht vorhandene Werte nicht berücksichtigt wurden.

Im Waldschmidt Skript ist eine Variante beschrieben, die auch Zwischenwerte berücksicht. (Siehe: Waldschmidt 2.4.5 S.164)

Also z.B. wenn die Schlüssel 1, 5. 9 im Baum sind könnte ja auch nach den Wert 4 gesucht werden, welcher nicht im Baum vorhanden ist. Das kann man in die Konstruktion des Baumes einrechnen, so das auch häufige erfolglose Suchen schnell abgebrochen werden können.

tgp
Sonntagsinformatiker
Sonntagsinformatiker
Beiträge: 268
Registriert: 15. Nov 2006 21:41

Beitrag von tgp »

Welchen Sinn hat die halbsequenzielle Darstellung bei Binärbäumen? Soweit ich das verstanden habe, kann man z.B. aus dem Ergebnis der G 6.3 b) iii) nicht wieder auf den Ursprungsbaum kommen. Das tritt m.E. immer auf, wenn ein Knoten zwar einen rechten, aber keinen linken Sohn hat.

Härder gibt in seinem Skript als Vorteile Speicherplatzersparnis, einfache Freispeicherverwaltung und effizienter Durchlauf des Binärbaums in Vorordnung an (S. 63). Ich finde, das wiegt den o.g. (vermeintlichen?) Nachteil nicht auf.

Christoph B
Computerversteher
Computerversteher
Beiträge: 370
Registriert: 15. Okt 2006 18:28
Wohnort: Wiesbaden
Kontaktdaten:

Beitrag von Christoph B »

klar kommt man auf den ursprungsbaum, wenn der "physikalische Nachbar" eines Knotens = der Nachfolger is, auf den verwiesen wird, dann weißt du doch das der Knoten nur einen Nachfolger hat, genauso weißt das du das es der rechte ist, von daher hast du alle Informationen die du brauchst.
Im gegensatz z.B. zur Vater-Darstellung

tgp
Sonntagsinformatiker
Sonntagsinformatiker
Beiträge: 268
Registriert: 15. Nov 2006 21:41

Beitrag von tgp »

Ah ich hatte übersehen, dass die Knoten in pre-order gespeichert sind - daraus ergibt sich das, was du geschrieben hast...

jah
Erstie
Erstie
Beiträge: 20
Registriert: 18. Sep 2007 20:02

Beitrag von jah »

Hi!

Ich habe mal ganz kurz eine Frage bezüglich der Komplexität
Im Skript 03 ist auf Folie 76 als Beispiel für Rekurrenzrelationen angegeben:

T(n) = 1 T(n) = 1+ 1/2 T(n-1)

so nach Aufrollen und finden einer geschlossenen Form kommt man auf
T(n) = 2 - 1/2 ^ (n-1)

allerdings würde mich bei dieser geschlossenen Form mal die abgschätzte Form interessieren... Laut Wikipedia ist c^n für jedes c im exponentiellen Bereich..

Aber laut Definition gilt ja für f € O(n) wenn
Es ex. ein n0 € N, so dass für alle n>=n0 gilt f(n) <= cg(n) für c € N

allerdings ist in unserer zu untersuchenden Funktion ja c < 1 also wird dieser Wert ja nie 1 übersteigen... Liegt sie dennoch in O(2^n) ???
Danke :)

wzhang
Erstie
Erstie
Beiträge: 15
Registriert: 9. Mär 2006 10:59

Beitrag von wzhang »

Bei Quadratische Sondieren in Hash habe ich noch Frage.
Ich verstehe das nicht in Uebung G11.8, das Problem bei Quadratische Sondieren,
mit m=4j+3( in K13,F41) kann das problem geloest werden?

Es waere net , wenn es in Repetitorien erklaert wird. danke

wzhang
Erstie
Erstie
Beiträge: 15
Registriert: 9. Mär 2006 10:59

Beitrag von wzhang »

bei Erweiterbarem Hash ist die Einfuegenreihenfolge unwichtig,oder?


in der Loesung von G11.9 lautet " Diese Einfuegenreihenfolge ist guenstig/unguestig..?"

Antworten

Zurück zu „Archiv“