Prüfungsübungen

[hub]

http://www.ads.tuwien.ac.at/teaching/LVA/AlgoDat1/altePruef/ad1-20021206.pdf

@ Aufgabe 3.B
d=3 bedeutet jeder Knoten max. 3 Kanten oder?
stimmt das A C I H J M E L B D F G K

[yrucrem]

Ja, d = 3 bedeutet, dass jeder Knoten maximal 3 Kanten haben darf. Aber bezieht sich deine Frage wirklich auf 3.B? Wie kommst du auf diese Reihenfolge der Knoten? Ich habe die Angabe nur kurz ueberflogen, aber ich denke die billigste Kante ist [C, I] (und danach [J, M], ...).

Ad B:

Nein, dieser modifizierte Kruskal funktioniert nicht immer.

Gegeben sei folgender gewichteter Graph:

G = <V = {1, 2, 3, 4, 5}, E = {[1, 2], [1, 3], [1, 5], [2, 3], [4, 5]}, f>

f([1, 2]) = 1
f([1, 3]) = f([2, 3]) = 2
f([1, 5]) = 3
f([4, 5]) = 4

Die Gradbeschraenkung des Graphen sei 2. Hier befindet sich ein Bild (http://stud3.tuwien.ac.at/~e0125335/studium/algodat_1/ue5-bsp8.png) des Graphen und des gradbeschraeankten minimalen Spannbaums.

Es existiert in diesem Graphen ein gradbeschraenkter minimaler Spannbaum, naemlich mit den Kanten [2, 3], [1, 2], [1, 5] und [4, 5]. Dieser Spannbaum ist sogar absolut minimal, auch wenn man die Gradbeschraenkung weglassen wuerde, koennte man keinen minimaleren Baum finden. Es koennte aber sein, dass der Algorithmus die Kante [1, 3] vor der Kante [2, 3] ansieht. Zu diesem Zeitpunkt spricht noch nichts dagegen, diese Kante hinzuzufuwgen, also macht der Algorithmus das auch. Die Kante [2, 3] kann nun nicht mehr hinzugefuegt werden, weil ja sonst ein Kreis (1 - 2 - 3) entstehen wuerde. Außerdem kann die Kante [1, 5] nicht mehr hinzugefuegt werden, weil sonst die Gradbeschraenkung fuer den Knoten 1 verletzt werden wuerde. Die naechste Kante die hinzugefaegt wird ist [4, 5]. Nun existiert aber keine Verbindung zwischen 4 (bzw. 5) und dem Rest des Graphen, also habe wir keinen aufspannenden baum erhalten, obwohl ein solcher existieren wuerde.

[hub]

hab mich mit den knoten oben vertan weil ich den primalgo angewandt hab,hab dein bsp soweit verstanden.... :) thx

hab jetzt mittels kruskal das obige nochmals gemacht, bekomme aber keinen mst der zusammenhängend ist :awake:
I-C; J-M; I-H; J-E; J-F; I-B; M-L; C-A; F-K; F-G; E-D =?

@4B b was sind eigtl primärkollisionen ? wenn das erste mal 1 stelle besetzt ist
detto sekundärk. ? wenn das 2te mal eine stelle schon besetzt ist ?
antwort wäre ja wenn ich richtig recherchiert habe : bei pk kein vorteil, bei sk keine klusterbildung

[yrucrem]

Nach der Kante [E, J] betrachtest du zuerst die Kante [I, J], die ist naemlich billiger als [J, F].

Bei mir kommt ein Baum mit folgenden Kanten heraus:

[C, I], [J, M], [H, I], [E, J], [I, J], [L, M], [A, C], [B, H], [F, G], [F, K], [D, F], [D, E]

Die Kanten mit den Gewichten 6, 7, 8, 10, 11 und 14 fallen fallen aus wegen der Gradbeschraenkung oder wegen Kreisen.

Ad 4.b
Ich wuerde auch sagen, der Vorteil von quadratischem Sondieren gegenueber Linearem ist, dass es zu weniger Clusterbildung kommt.

[hub]

was genau =clusterbildung ?

@20020128 aufgabe 1 notationen
i versteh diese notationen leider nicht :cuss:
ganz allgemein mal:
heißt
o(n²) funktion wächst max n²
und theta (n²) f wächst mind n²
und omega(n²) f wächst ungefähr n² ???

[martin]

hub wrote:
> was genau =clusterbildung ?

Naja, das tritt in der Praxis bei Hashing (v.a. beim normalen linearen
Sondieren) auf: Wenn sich Einträge einmal an einer bestimmten Stelle in
der Tabelle zu 'sammeln' beginnen, wird die Tabelle dort immer voller
und viel mehr Probing nötig. Im worst-case hast du dann eine halb
gefülltt Tabelle, deren Einträge sich an einer Stelle häufen.
Wenn du dir darunter nichts vorstellen kannst, zeichne dir eine
Hashtabelle (Größe zw. 15 und 25 sollte ausreichen) und füll die
gleichen Schlüsseln mit Linear Probing, Double Hashing,... ein und schau
was passiert

> @20020128 aufgabe 1 notationen
> i versteh diese notationen leider nicht :cuss:
> ganz allgemein mal:
> heißt
> o(n²) funktion wächst max n²

Ja.

> und theta (n²) f wächst mind n²
> und omega(n²) f wächst ungefähr n² ???

Umgekehrt. Die Theta-Notation muss, wenn du so willst, den Anforderungen
für Omikron und für Omega genügen.

[hub]

thx...
also wenn f= o(n²) --> f= theta(n²)
und wenn f=omega(n²) --> f=theta(n²)
und wenn f=o(n²) folgt daraus NICHT f=omega(n²)

@clusterbildung:
aber was ist daran so schlimm wenn die tabelle so aussieht
1 2 3 4 5 6 7 8 9 10 11 12 und alle nebeneinander kleben?
5 6 7 4 6

[patricasso]

Original geschrieben von yrucrem
Bei mir kommt ein Baum mit folgenden Kanten heraus:
[C, I], [J, M], [H, I], [E, J], [I, J], [L, M], [A, C], [B, H], [F, G], [F, K], [D, F], [D, E]


genau das krieg ich auch raus. Die Summe ist dann 115.

@cluster:
Das hab ich in einem Buch gelesen (im Wesentlichen nix neues):
"[...] Lineares Sondieren neigt zur Bildung von "Klumpen", in denen alle Positionen bereits besetzt sind, und sich daher lange Sondierfolgen aufbauen [...]"
Damit ist ja auch nix anderes wie die "Primäre Häufung" aus dem Skriptum gemeint, oder?

viel Glück allen für morgen!