Die Suche ergab 7 Treffer

von apandi
25. Feb 2009 08:51
Forum: Archiv
Thema: 14. Übungsblatt
Antworten: 13
Zugriffe: 1238

Re: 14. Übungsblatt

Kann man nicht 2*3*5*7*11*13+1 für p nehmen? Ich war mir ziemlich sicher, aber jetzt fällt mir der Beweis nicht mehr ein..
von apandi
5. Jan 2009 01:31
Forum: Archiv
Thema: 9. Übungsblatt
Antworten: 10
Zugriffe: 1025

Re: 9. Übungsblatt

ah ok, danke!
von apandi
31. Dez 2008 15:56
Forum: Archiv
Thema: 9. Übungsblatt
Antworten: 10
Zugriffe: 1025

G5

Eine Frage zur G5:

In der p-1 Methode muss man ja gcd(a^k-1,n) berechnen, wobei k=2^3*3*5*7=840. Ich habe a=2 gewählt. Wie mache ich das per Hand? Mit dem euklidischen Algorithmus?
Kann mir vielleicht jemand helfen?
von apandi
2. Mär 2008 19:21
Forum: Effiziente Graphenalgorithmen
Thema: Goal directed Search Dijkstra
Antworten: 8
Zugriffe: 1138

Re: Goal directed Search Dijkstra

Die ersten beiden Ungleichungen addieren
(1) d(w) >= d(v)
(2) b(w,t) + l(v,w) >= b(v,t)
Dann kommt man auf
d(w) + b(w,t) + l(v,w) >= d(v) + b(v,t)
Dann b(s,t) dann auf beiden Seiten abziehen, dann kommt man auf die gewünschte Gleichung.
von apandi
2. Mär 2008 15:47
Forum: Effiziente Graphenalgorithmen
Thema: Detecting negative cycles
Antworten: 5
Zugriffe: 857

Re: Detecting negative cycles

@sandra: pred(s) kann sich ja schon ändern, wenn ein negativer Zyklus über s läuft. Ignorieren dieses Zyklus würde dann ja zu einem "falschen" Ergebnis führen. Ich denke auch man müsste s mitbetrachten und wie sYsChOs sagte entweder abbrechen, wenn d(s) < 0 oder halt pred(v) = NULL abfangen..
von apandi
2. Mär 2008 15:33
Forum: Effiziente Graphenalgorithmen
Thema: Goal directed Search Dijkstra
Antworten: 8
Zugriffe: 1138

Re: Goal directed Search Dijkstra

Es gilt sogar, dass in dem Fall d'(v)>d'(w) nicht möglich ist. Das folgt aus der Konsistenzbedingung der unteren Schranken und der Vorgabe positiver Kantenlängen. Offensichtlich gilt ja d(w) >= d(v) Zusammen mit der Konsistenzbedingung für die unteren Schranken b(w,t) + l(v,w) >= b(v,t) ergibt sich ...
von apandi
2. Mär 2008 15:11
Forum: Effiziente Graphenalgorithmen
Thema: Komplexität des Augmenting Path Algorithm
Antworten: 14
Zugriffe: 1278

Re: Komplexität des Augmenting Path Algorithm

Es gibt auch eine einfachere Erklärung. Betrachte einfach den Cut mit S=V\{t} und S'={t}. Dann gibt es maximal n Kanten von S nach S'. Daraus folgt dann, dass die Kapazität des Schnittes durch nU (und nicht mU) begrenzt ist.

Zur erweiterten Suche