Loesungen

[yrucrem]

Ich dachte ich waere spaet dran, mit den Loesungen, dabei ist ja naechste Woche gar keine Uebung.

/edit 30.05.02:
Aber durch meinen DM-Abgabetermin bin ich nun doch ziemlich weit zurueckgefallen. Die Loesungen sollten aber bis zum Wochenende komplett sein.

- Beispiele 6, 8 und 10 wurden hinzugefuegt
- Beispiel 7 wurde korrigiert
- Beispiel 8 wurde korrigiert
- Pseudocode fuer Beispiel 10 wurde vereinfacht

seit 04.06.02, 17:11 ist die Version 1.0 online unter uebung.html (http://stud3.tuwien.ac.at/~e0125335/studium/algodat_1/uebung.html)

[yrucrem]

Ich versuche eigentlich das signal/noise Verhaeltnis meiner Posts auf einem ertraeglichen niveau zu halten, aber wenn ich den obigen Post nur geaendert haette, wuerde das keiner mitbekommen, darum dieser neue Beitrag.

Die html-Datei die vorher dort stand gibt es nicht mehr. Inzwischen ist eine pdf-Datei mit den meisten Loesungen verfuegbar.

[DoomedOne]

zu 9:
was passiert wenn die folge nur gleiche zahlen enthält?
dann sollt der baum wieder unbalanciert sein oder seh ich das falsch?
er wäre sogar eine lineare liste...

[eXe]

@ yrucrem

danke für deine lösungen ham mir sehr geholfen :)

(gottseidank muß ich jetz keine mehr machen , weil ich winfler bin ;) )

[yrucrem]

@DoomedOne:
Hmm, das stimmt. Aber andererseits steht in der Angabe, dass das normale Einfuegen() fuer natuerliche Suchbaeume verwendet werden soll (insbesondere kein AVL-Einfuegen) . Und da kann man irgendwie nicht verhindern, dass bei lauter gleichen Zahlen ein unbalancierter Baum herauskommt.

Man koennte vielleicht nach dem zweiten rekursiven Aufruf von erstelle() so eine Art Balance-Uberpruefung vornehmen und gegebenenfalls rotieren, aber das kommt schon ziemlich nah an AVL.

Ich denke die Angabe war schon so gemeint, dass man den Fall, dass nur gleiche Zahlen kommen, ignorieren kann (ich werde das jedenfalls tun ;-)).

[wescht]

ich wollte mich auch nur für die lösungen bedanken...
(soviel zum thema signal/noise ;-)

[DoomedOne]

jo glaub auch das man mit normalem einfügen keine besseren lösungen bekommen kann. Ich hab mir aber noch ein paar gedanken drüber gemacht und vielleicht gehts so:


erstelle(l, r, father, wo)
{
if ( l <= r)
{
m = floor((l + r) / 2);
father = einfügen(A[m], father, wo);
erstelle(l, m - 1, father, links);
erstelle(m + 1, r, father, rechts);
}
}

einfügen(x, where, wo)
{
t = new El(x);
if (start == null)
{
start = t; //wurzel
return start;
}

if (x < where.key)
where.left = t;
else if (x > where.key)
where.right = t;
else
{
if (wo == links)
where.left = t;
else
where.right = t;
}
return t;
}

aufruf mit; erstelle(0, n, null, links)
P.s: das ist sicher nicht die optimale lösung ;)

[VTEC]

@ DoomedOne: Dein Listing schaut im Dark-Style aus, als ob Du es tarnen wolltest :D, wenns markiert ist, gehts eh

@yrucrem: Vielen Dank für Die Lösungen wieder, ich hab leider nicht so viel Zeit mich selbst eingehend damit zu beschäftigen, sodaß ich ohne Anleitung selbst die Lösung find.

C YA

[Lukas]

könnte das beispiel 10 so funktionieren?

[edit] der algorithmus ist falsch

Zusammenhang(s)
initialisiere alle Knoten v € V mit markiert[v] = 0;
für alle Knoten v € V
{
ZH(v)
}
für alle Knoten v€V
{
if (markiert[v] == 1)
return nicht_stark_zusammenhängend
}
return stark_zusammenhängend


ZH(v)
für alle Knoten w € V
{
falls (es existiert keine Kante (w,v) oder es existiert keine Kante (v,w)
markiert[v] = 1;
}

[yrucrem]

@Lukas:
Wenn ich das richtig verstehe, sagt dein Algorithmus, dass der Graph nicht stark zusammenhaengend ist, sobald er zwei Knoten findet, die nicht durch eine Kante verbunden sind.

Ein Beispiel: V = {v, w, x, y}, E = {(v, x), (x, w), (w, y), (y, v)}. Deiser Graph, waere stark zusammenhaengend, obwohl es keine Kante (v, w) oder (w, v) gibt.

Ich wuerde vorschlagen, bei jeden Knoten eine Traversierung zu starten und dabei die Knoten immer mit anderen Zahlen zu markieren. Nach jeder Traversierung muessen alle Knoten die selbe Markierung haben. Wenn nicht, heiszt das, dass dieser eine Knoten nicht erreicht werden konnte.

[Lukas]

ja stimmt. hab mich bei der definition von stark zusammenhängend irgendwie verlesen...

[DoomedOne]

zu 10:
warum musst du imer in jedem knoten einen marker neu setzen?
würde es nicht reichen zu zählen wie viele knoten gefunden wurde? also ne int variable global machen und immer wenn ein unbesuchter knoten auf besucht gesetzt wird die var um 1 zu erhöhen.
wenn dann nach einem durchgang traversiere der zähler != gesamt-knotenanzahl -1 ist, ist es nicht stark zusammenhängend.

außerdem kann man noch schauen ob von einem knoten überhaupt eine verbindung weg geht, wenn nicht kann es gar nicht stark zusammenhängend sein

[yrucrem]

Ja stimmt eigentlich. An einen Zaehler hatte ich gar nicht gedacht (globale Variablen sind mir etwas unangenehm ;-)). Wie gesagt, die Idee ist einfach fuer jeden Knoten zu pruefen, ob man alle anderen Knoten erreichen kann, wie man das macht ist egal. Danke fuer den Hinweis, mit dem Zaehler ist es viel leichter zu pruefen, ob alle Knoten erreicht wurden. Leider ist es immer noch quadratisch ;-).

Hat eigentlich jemand eine Idee, fuer Beispiel 8? Bei dem bin ich mir noch nicht sicher.

[Navett]

Hab ich da was falsch gemacht, oder funktioniert deine 2. Hashfunktion nicht so wie sie sollte?
Beim Wert -311 bekomme ich mit deiner Funktion h2(k) = 5 - 311 mod 17 auf
h2(k) = 0 !! (-306/17 = -18 und 0 Rest!)
Und damit haben wir einen Teufelskreis...

Wie kommst du für h2(k) auf 17?

[yrucrem]

Punkt vor Strich! Modulo bindet staerker als Plus oder Minus.

[steve]

zum thema 6
würd ich sagen, dass er ganz eindeutig nicht stimmt (es sei denn, ich hab die angabe falsch verstanden).

bsp 8:
meiner meinung nach stimmt der algorithmus. er nimmt ja schließlich immer das "billigste" element, das den bedingungen entspricht. (hundertprozentig sicher bin ich mir nicht, aber mein hirn konnte bisher keinen gegenbeweis ausspucken...) gegenstimmen?

[dose]

Ein paar Ergänzungen / Korrekturen für Blatt 5...

ad 7: Nur der Vollständigkeit halber: Der Knoten g (25) wurde vergessen...ist zwischen f und b/p, ist aber nicht in der Lösung (Kreis zwischen 3, 4, 2, 8)

ad 8: Hätte mir ursprünglich auch gedacht, daß der Algorithmus funktionieren könnte, heute in unserer Übungsstunde hatte jedoch jemand ein Beispiel gebracht, das das Gegenteil beweist - und auch die Tutorin überrascht hat :) Zu finden is eine "Skizze" auf http://www.dose-xp.org/algodat5_8.gif (nicht schlagen für die Ausführung, ich werd kein Medieninformatiker ;)) - für d(max)=2 z.B. würde der Algorithmus nicht die richtige Lösung liefern.

ad 10:
Meine Lösung beruht auf folgendem Prinzip: Da es zu jedem Knoten von jedem Knoten aus einen Weg geben soll (per Definition), müßte die erreichbare Knotenzahl von jedem Knoten (AnzahlKnoten - 1) sein, mit einem etwas modifizierten Tiefensuchealgorithmus (DFS_mod) läßt sich das leicht für jeden Knoten herausfinden, dann noch eine weitere Funktion rundherum (StarkZus), die das für alle Knoten "errechnet", vergleicht, und fertig ist das ganze. Die Laufzeit mag zwar nicht optimal sein, aber was solls...es müßte funktionieren (zumindest theoretisch sollte ich nicht allzu falsch liegen...)


DFS_mod(x);
{
markiere(x);
push(x);
pop(x);
erreichbar=0;
solange (x!=NULL)
{
y=naechster_unmarkierter_nachbar(x);
falls (y!=NULL)
{
markiere(y);
push(y);
erreichbar++;
}
sonst
{
y=pop();
}
x=pop();
}
return(erreichbar);
}

StarkZus(V)
{
x=0;
y=DFS_mod(V[x]);
solange ((x==y) && (x<AnzahlKnoten))
{
x++;
y=DFS_mod(V[x]);
}
falls (x==y)
{
return(wahr);
}
sonst
{
return(falsch);
}
}

[steve]

10-1-3-4-5 ist auf deiner skizze der richtige Stammbaum, oder?
hast recht, ist verblüffend...

[dose]

Ja, 10-1-3-4-5 wär die optimale Lösung, aber mit dem veränderten Kruskal kommt ma auf 1-2-4-5-100 :)

[steve]

stimmt!
den algorithmus fürs 10er hab ich wie folgt: einerseits wird in einer steuerfunktion für jeden knoten jedes knoten.markiert=false gesetzt und der counter=0.
dann gibts einen DFS(knoten)-aufruf für eine DFS-suche mit mitlaufendem counter.
counter wird returned an steuerfunktion. ist der counter zu klein ausgefallen, schreit er. :eek: ;)

[JimmyNeutron]

hat irgendwer schon die lösungen für das 6 und letzte ü-blatt??

[yrucrem]

Sind in Arbeit. Wird vermutlich etwas knapp, wegen der DeathMatch-Pruefung.