D120.de/forum

OK, Bei Dijkstra ist delta(als Dreieck) nicht deklariert. Nach einer halben Stunde :evil: kam ich auf die Idee es könnte der optimale Weg sein von einem Knoten v zu s. Stimmt das? PS: Hier könnte man sich vieeeeeeeeeeeel unnötige Zeit sparen wenn irgendwo einfach stehen würde delta(dreieck):= [...]...

Das ist für den zweiten Fall durchaus richtig. Genau dasselbe habe ich mir dabei auch gedacht. Allerdings denke ich auch, dass es nicht sinnvoll ist den Algorithmus absichtlich zu verlangsamen, indem man dafür sorgt, dass die Werte berechnet und zwischengespeichert und erst am Ende in M eingetragen...

Dasselbe Problem tritt übrigens auch auf, wenn bei einem Graph a --1--> b --1--> c --1--> d --1--> e während der 1. Iteration der Weg (a,d) bestimmt wird. Da in derselben Iteration vorher (a,c) mit Distanz "2" in die Matrix M geschrieben wurde, kann nun auch der Weg M(a,d) = M(a,c)+L(c,d) = 3 besti...

Hallo, ich habe eine Frage zum Begriff des inneren Knoten in Verbindung mit der Floyd-Warshall Invariante, die sinngemäß besagt: Nach i>=0 Iterationen, steht im Matrixeintrag (v,w) die Länge eines kürzesten Weges zwischen v und w, dessen innere Knoten Element der Menge {v1, ..., vi} sind(wobei die K...

Ich habe eine Frage zu der Invariante 2.2)- 2.4) Wenn i1=2 wäre,dann läge j=1: i1 kann gemäß Induction Basis aber nicht 2 sein, da i1 für alle Elemente die schon richtig positioniert sind ein Index weitergeschoben wird. In diesem Fall würde i1 also mit 4 initialisiert werden und es gilt i1=m1. Die ...

Ok danke. Aber jetzt stell ich mir eine andere Frage. Wann wird bei insert und extract Minimum der Index k eigentlich initialisiert? Habe auf den Wiki Seiten nichts derartiges gefunden und da k nicht zum Input der Methode gehört, muss das doch irgendwann getan werden oder? (wie z.B. bei decrease Key...

Mal ne andere Frage zum Thema Heap as array: Wenn ich richtig verstanden habe, ist die ID dafür da um unabhängig von dem aktuellen Zustand des Heaps (und somit der Position eines Elementes) schnell über das array Positions darauf zugreifen zu können. Das heißt wenn "ich" ein Element in den Heap einf...

Das hab ich wohl überlesen.

Naja dann ist deine Frage glaub ich berechtigt
Andererseits, wenn der Beweis speziell für 2 Funktionen gefragt ist, dann könnte man den Umkehrschluss ziehen, dass für die anderen Funktionen keine Begründung für die Reihenfolge (Beweis) nötig ist.

Ich glaub bei 15 Punkten, wird die Reihenfolge alleine nicht ausreichen

onbes hat geschrieben:Zumal gesagt worden ist, dass der Implementation Teil aus dem Wiki nicht relevant ist (sofern ich das noch richtig im Kopf habe)

Diese Aussage bezieht sich auf die Implementation der Induction Basis bzw. des Induction Steps.

Hier geht es aber um die Implementationsinvarianten von Datenstrukturen.

Müssen in der Klausuraufgabenstellung für die Methoden einer Datenstruktur auch die Impelemtationsinvarianten betrachtet werden? Selbstverständlich! KW Dann muss IMHO die Aufgabenstellung gemäß "Infoblatt zur Klausur" geändert werden: „Aus dem Wiki kennen Sie den iterativen Algorithmus X (bzw. die ...

NACHTRAG: https://hermes.algo.informatik.tu-darmstadt.de/mediawiki/index.php?title=Special:Log&limit=500&type=newusers&month=&year= Über 1000(!) Neuanmeldungen im Wiki mit kryptischen Usernamen im Monat August . Würde vielleicht das ein oder andere erklären... Gibts nicht irgendne pragmatische Mögli...

Hallo, ich glaube es wäre hilfreich das Wiki zumindest bis zur Klausur zu sperren, sodass nur Admins Änderungen vornehmen dürfen. Aktuell scheint wieder irgenden Quatsch gemacht zu werden, so wurde zum Beispiel die Pivot Partioning by Scanning Seite gelöscht oder u.A. folgende Seite angelegt: https:...

Hallo, (...) Wählt man den Pivot-Wert = 5, so erhält man die Teilsequenzen S'1 = (4,3), S'2 = (5), S'3 = (6,9). Die Ergebnisse dieser Rekursionsschritte sind die sortierten Teilsequenzen S'1 = (3, 4), S'2 = (5), S'3 = (6,9). Genau genommen werden doch eigentlich nur die Sequenzen S1 und S3 rekursiv...

Hi, 1.) Der Graph F_i = (V,E_i), der aus den bisher ausgewählten Kanten besteht (e_1 bis e_i), ist Teilmenge des Endergebnisses (also des fertigen, maximalen Spannbaums) F'_i = (V,E'_i), s.d. E_i Teilmenge von E'_i. Falls das so stimmt, stelle ich mir die Frage wieso man den fertigen Spannbaum als ...