Die Suche ergab 73 Treffer

von NonStop
20. Sep 2015 10:31
Forum: Archiv
Thema: Fehler im Wiki
Antworten: 12
Zugriffe: 899

Re: Fehler im Wiki

Das wird ggf. eindeutig aus der Aufgabenstellung hervorgehen. KW Und was ist damit? Ist das jetzt die richtige Komplexität für Kruskal? http://wiki.algo.informatik.tu-darmstadt.de/images/math/a/6/a/a6a901c37a9b16c0c1eeec607a6b3f8f.png Auf dem Video haben Sie gesagt, die Komplexität sei m log m + n ...
von NonStop
19. Sep 2015 09:02
Forum: Archiv
Thema: Fehler im Wiki
Antworten: 12
Zugriffe: 899

Re: Fehler im Wiki

wobei m Anzahl der Kanten und n Anzahl der Kanten ist. :?: m ist die Anzahl der Kanten, n ist die Anzahl der Knoten :) Und dann noch eine Frage. Wenn in der Klausur nach der Komplexität eines Algorithmus gefragt wird, müssen wir auch dieses T angeben? Z.B. Für Bubblesort, reicht es zu schreiben, da...
von NonStop
18. Sep 2015 21:01
Forum: Archiv
Thema: Fehler im Wiki
Antworten: 12
Zugriffe: 899

Re: Fehler im Wiki

Ist korrigiert. Wir hatten das Wiki vor einiger Zeit neu implementiert. Bei der Portierung der Texte war viel Handarbeit nötig, da können sich merkwürdige Dinge einschleichen, ohne dass man es beim Korrekturlesen sofort bemerkt... KW Ist das jetzt die richtige Komplexität für Kruskal? http://wiki.a...
von NonStop
18. Sep 2015 14:43
Forum: Archiv
Thema: Frage zu 5.1
Antworten: 6
Zugriffe: 702

Frage zu 5.1

Hallo, soll man in der Aufgabe 1 den gesamten Graph zeichnen oder reicht es, wenn man für jede Variablle aus Klausel 1 einen eigenen Teilgraph zeichnet? Ich habe versucht einen gesamten zu zeichnen und der sieht total unübersichtlich aus, es sind zu viele Kanten, sodass man keine Cliquen ablesen kan...
von NonStop
17. Sep 2015 19:26
Forum: Archiv
Thema: Frage zur Invariante
Antworten: 1
Zugriffe: 410

Frage zur Invariante

Hallo, ich habe mir die Flipcharts zu Rep. 1 angeschaut und habe auf der Seite 5 folgendes Beispiel zu einer Invariante gefunden: http://img4web.com/i/6Y8L1V.png Aber ist die Verkleinerung einer Liste nicht das, was sich von Iteration zu Iteration ändert? Oder habe ich das Konzept der Invariante/Var...
von NonStop
17. Sep 2015 18:47
Forum: Archiv
Thema: Ein paar Einsichten aus dem Repetitorium vom 17.9.
Antworten: 3
Zugriffe: 401

Re: Ein paar Einsichten aus dem Repetitorium vom 17.9.

2. Unterscheiden Sie bitte Rekursionsschritt und Induktionsschritt - ersteres ist ein Ablauf im Algorithmus, letzteres ein Teil eines Textes, nämlich des Korrektheitsbeweises. Und wie sieht es bei iterativen Algorithmen aus? In der wiki gibt es für jeden Algorithmus Induction basis und Induction st...
von NonStop
16. Sep 2015 20:11
Forum: Archiv
Thema: Prim
Antworten: 11
Zugriffe: 1122

Re: Prim

Und warum wird in diesem Fall die Kante (c,b) und nicht (d,e) gewählt? Der Startknoten ist hier d. Weil b lexikographisch niedriger ist als e. Es sind doch zwei verschiedene Knoten, die "angesteuert" werden. Siehe Situation 1 wie bei mir oben und bei meiner ursprünlichen Lösungsstrategie beschriebe...
von NonStop
16. Sep 2015 18:47
Forum: Archiv
Thema: Prim
Antworten: 11
Zugriffe: 1122

Re: Prim

https://foo.algo.informatik.tu-darmstad ... 1dc4deecd0

Und warum wird in diesem Fall die Kante (c,b) und nicht (d,e) gewählt? Der Startknoten ist hier d.
Bild
Bild
von NonStop
16. Sep 2015 16:08
Forum: Archiv
Thema: Prim
Antworten: 11
Zugriffe: 1122

Re: Prim

Habe genau das gleiche Problem. Hier ist Versuch 1: http://www.bilder-upload.eu/thumb/69bc71-1442413200.png Habe gewählt (a,d), die Musterlösung lautet: http://www.bilder-upload.eu/thumb/b0947d-1442413216.png Versuch 2: http://www.bilder-upload.eu/thumb/c95512-1442413227.png Habe gewählt (a,i), die ...
von NonStop
16. Sep 2015 15:43
Forum: Archiv
Thema: Shortest path single source, single target Strategie
Antworten: 3
Zugriffe: 400

Re: Shortest path single source, single target Strategie

Man kann einen Pfad natürlich nur zurück verfolgen, wenn sich der Graph nicht ändert. In deinem Beispiel hat sich ja auch der kürzeste Pfad, den man von A nach G erhält, verändert. Ich glaube, ich habe die Idee falsch verstanden. So habe ich es aus dem Video verstanden: Iteration 1 bleibt gleich. I...
von NonStop
16. Sep 2015 14:19
Forum: Archiv
Thema: Shortest path single source, single target Strategie
Antworten: 3
Zugriffe: 400

Shortest path single source, single target Strategie

Hallo, im Foliensatz zu Dijkstra gab es Folien mit dem Überschrift "Kürzesten Pfad rekonstruieren". Auf dem Video wurde gesagt, dass man den kürzesten Pfad zu jedem Knoten rückwärts berechnen kann. Ändert man aber den Wert für den Pfeil von S nach G, so klappt diese Strategie nicht mehr, hier ist ei...
von NonStop
15. Sep 2015 18:54
Forum: Archiv
Thema: Foo Aufgaben für die Klausur
Antworten: 18
Zugriffe: 2211

Re: Foo Aufgaben für die Klausur

Bei mir beginnen beide ab der 1. Iteration. Wurde glaube eben geupdatet. Habe gerade beide Aufgaben noch mal getestet, es ist immer noch so. Hier ist Iteration 1 von Insert: http://www.bilder-upload.eu/thumb/0bcd6c-1442336580.png Das neue Heap-Element wird nur eingefügt. Vertauscht wird es erst ab ...
von NonStop
15. Sep 2015 18:11
Forum: Archiv
Thema: Fehler im Foliensatz HashTablesComplexity?
Antworten: 1
Zugriffe: 388

Fehler im Foliensatz HashTablesComplexity?

Hallo,

auf Folie 17 steht im 2. Faktor im Zahler einfach N. Sollte da nicht Nmax stehen?
von NonStop
15. Sep 2015 17:46
Forum: Archiv
Thema: Foo Aufgaben für die Klausur
Antworten: 18
Zugriffe: 2211

Re: Foo Aufgaben für die Klausur

Hallo allerseits, Methode decrease key von Heap sollte keine falschen Lösungen mehr liefern, der Off-by-One-Error ist korrigiert. KW Hallo, ich habe noch eine Frage bezüglich der Iterationenzahl. - Heap: decrease key beginnt ab der 0. Iteration und es wird schon in der 0. Iteration nach dem Verring...
von NonStop
12. Sep 2015 14:00
Forum: Archiv
Thema: Komplexität Dijkstra
Antworten: 1
Zugriffe: 457

Komplexität Dijkstra

Hallo, in dem Video zu Dijkstra wurde gesagt, dass die Komplexität linear in der Anzahl der Knoten plus in der Anzahl der Kanten * log(Knotenzahl). Also O(Knotenzahl + Kantenzahl * log (Knotenzahl)). In der Wiki steht http://wiki.algo.informatik.tu-darmstadt.de/images/math/c/3/9/c39ca6a61955c9fae4f7...

Zur erweiterten Suche