Die Suche ergab 67 Treffer

von Dreamdancer
21. Feb 2009 14:23
Forum: Archiv
Thema: 9. Übungsblatt
Antworten: 10
Zugriffe: 1143

Re: 9. Übungsblatt

Egal ist gut gesagt. Also in der Übung spektulierte der Aufgabensteller wohl darauf, dass man auf 27 aufrundet, um schnell und einfach an das Ergebnis zu kommen. Ob das mit 26 auch so gegangen wäre? 8)
von Dreamdancer
21. Feb 2009 14:10
Forum: Archiv
Thema: 9. Übungsblatt
Antworten: 10
Zugriffe: 1143

Re: 9. Übungsblatt

Kann mir jemand erklären, warum in der Lösung der Übung die Wurzel von 713 zur Bestimmung von m aufgerundet wird? Im Buch wird sie abgerundet...
von Dreamdancer
20. Feb 2009 17:19
Forum: Archiv
Thema: Pseudo Primzahlen...
Antworten: 3
Zugriffe: 638

Re: Pseudo Primzahlen...

Interessiert mich auch gerade. Obwohl: Da es ja kein Kampfrechnen geben soll, ist das scheinbar wirklich nur eine Interessens-Frage.
von Dreamdancer
20. Feb 2009 17:06
Forum: Archiv
Thema: 8. Übungsblatt
Antworten: 4
Zugriffe: 705

Re: 8. Übungsblatt

:P , na dann ist ja alles klar! Dachte schon, das sei eine Falle für Leute, die in der Vorlesung verhindert waren.
von Dreamdancer
20. Feb 2009 15:30
Forum: Archiv
Thema: 8. Übungsblatt
Antworten: 4
Zugriffe: 705

Re: 8. Übungsblatt

Kann mir jemand bitte erläutern, was die "in der Vorlesung gezeigten Methode" ist?

VG und danke
von Dreamdancer
9. Feb 2009 20:13
Forum: Effiziente Graphenalgorithmen
Thema: Übung 7.2 b)
Antworten: 10
Zugriffe: 655

Re: Übung 7.2 b)

Vorschlag: - Distanzlabel durch BFS von s aus. Excess-Knoten werden in einen FIFO-Queue gesteckt: Also werden die, die am nächsten zu s sind, auch zuerst abgearbeitet. O(m+n) - Solange Queue nicht leer: Nehme Knoten aus Queue und suche (kürzesten) Pfad im Residualgraphen nach s. O(n), da die Richtun...
von Dreamdancer
9. Feb 2009 19:57
Forum: Effiziente Graphenalgorithmen
Thema: Übung 7.2 b)
Antworten: 10
Zugriffe: 655

Re: Übung 7.2 b)

Also es kommt drauf an, wie ich Euch verstehen soll. Z.B. Graph G = (V,A) mit V = {s,v1,v2,v3,v4,t} und A = { (s,v1), (s,v2), (v1,v3), (v2,v3), (v3,v4), (v4,t }. Der Max-PreFlow ist aufgebaut: (s,v1): 5/5 [Flow/Kapazität] (s,v2): 5/5 (v1,v3): 5/5 (v2,v3): 5/5 (v3,v4): 10/10 (v4,t): 2/2 v4 hat 8 Über...
von Dreamdancer
9. Feb 2009 19:21
Forum: Effiziente Graphenalgorithmen
Thema: Übung 7.2 b)
Antworten: 10
Zugriffe: 655

Re: Übung 7.2 b)

Es kann sein, dass man eine Entscheidung revidieren muss, weil ein Knoten zwei Eingangspfade haben kann, diese sich wieder verästeln können etc. Wenn ein Knoten einen Überschuss von 500 hat, heißt das nicht, dass dieser von einen Pfad kommen muss und dass man diesen wieder über einen Pfad zurückschi...
von Dreamdancer
9. Feb 2009 18:57
Forum: Effiziente Graphenalgorithmen
Thema: Klausurvorbereitung
Antworten: 3
Zugriffe: 482

Re: Klausurvorbereitung

Als Vorschlag für die nächste Klausur: Beidseitig beschriebenes Blatt hat immer Wunder gewirkt. Die Gegenargumente fallen weg: Niemand blättert herum und niemand wird lange Suchen. Aber zwei Vorteile kommen hinzu: Die Klausurvorbereitung läuft nicht auf Auswendiglernen von Sachen hinaus, die im Grun...
von Dreamdancer
9. Feb 2009 16:04
Forum: Effiziente Graphenalgorithmen
Thema: Johnson´s Algorithmus F.151
Antworten: 2
Zugriffe: 241

Re: Johnson´s Algorithmus F.151

Wie können die negativ werden, wenn es genau eine (s-v)-Kante gibt für jeden v € V mit c(s,v) = 0 ?

<auf-dem-schlauch-steh>

EDIT:
Ah ich habs. Vielen Dank!
von Dreamdancer
9. Feb 2009 15:42
Forum: Effiziente Graphenalgorithmen
Thema: Johnson´s Algorithmus F.151
Antworten: 2
Zugriffe: 241

Johnson´s Algorithmus F.151

In Zeile 1 setzen wir c(s,v) = 0 für alle v € V. Demnach gilt in Zeile 4 h(v) = shortest-s-v-path(s,v) = 0 für alle v € V. Zeile 5 sagt doch dann aus, dass c' (u,v) = c(u,v) + h(u) - h(v) = c(u,v) Sei c(u,v) negativ, so folgt daraus, dass auch c'(u,v) negativ ist und die Transformierung der Kosten i...
von Dreamdancer
9. Feb 2009 14:24
Forum: Effiziente Graphenalgorithmen
Thema: Übung 4.1 + 4.2
Antworten: 2
Zugriffe: 201

Re: Übung 4.1 + 4.2

Ach so, LÄNGSTE Wege. Da hast Du sicher recht. Das würde gehen. Aber ein Deadlock käme nicht zustande, da Knoten mit Eingangsgrad 0 garnicht in Q reinkommen können (mit Ausnahme s)
von Dreamdancer
9. Feb 2009 13:15
Forum: Effiziente Graphenalgorithmen
Thema: Übung 4.1 + 4.2
Antworten: 2
Zugriffe: 201

Übung 4.1 + 4.2

4.1 Da würde mir nur Dials Implementierung von Dijkstra einfallen, der Rest läuft mindestens auf etwas x log(y) hinaus. Oder? 4.2 Ich würde den Dijkstra in der Select-Zeite das min(bla) durch ein max(bla) abändern (da die Werte strictly decreasing sind für nicht-permanent gelabelte Knoten ) und corr...
von Dreamdancer
8. Feb 2009 21:46
Forum: Effiziente Graphenalgorithmen
Thema: Cycle-Canceling F.220
Antworten: 2
Zugriffe: 164

Re: Cycle-Canceling F.220

Wie praktisch. Danke!
von Dreamdancer
8. Feb 2009 20:37
Forum: Effiziente Graphenalgorithmen
Thema: Cycle-Canceling F.220
Antworten: 2
Zugriffe: 164

Cycle-Canceling F.220

Wieso steht als Output ein MinCostFlow?

Also ich nehme einen feasible Flow, der ja nicht unbedingt MinCost ist, dann Cancel ich Zyklen, indem ich sie "verstopfe". Wer sagt mir, dass das Resultat ein MinCostFlow ist?

Zur erweiterten Suche