PDA

View Full Version : [FRAGE] - was kommt zum UE Test 2?

scheity
15-05-2002, 09:18
ist dies schon bekannt???????
Länz
15-05-2002, 10:10
außer Kapitel 6.1.4 (kommt nicht!) entspricht die Stoff-Abgrenzung jener für Studierende der Mathematik und WInf. - Skriptum Seite 8
skytale
15-05-2002, 13:51
also auch der gesamte Stoff, der schon zum vorherigen UE-Test gekommen ist ??
phlow
15-05-2002, 13:54
jap, so ist es
scheity
15-05-2002, 14:37
also sozusagen das gesammte skriptum ausser kapitel 6.1.4?!?
RoadRash
15-05-2002, 14:50
ja, aber nur bis (einschließlich) 6.3 Dynamische Programmierung
SinusDiabolicus
15-05-2002, 17:47
Original geschrieben von scheity
also sozusagen das gesammte skriptum ausser kapitel 6.1.4?!?
Original geschrieben von RoadRash
ja, aber nur bis (einschließlich) 6.3 Dynamische Programmierung
falsch, zumindest als antwort auf die frage nachm ganzen skriptum, 3.6 & 6.1.3 kommen auch nicht
seimen
18-05-2002, 20:09
hat der kraml im repetitorium am freitag noch irgendwelche tipps gegeben was kommen könnte??

wär echt nett, weil ich selber nur kurz da war, und nur weiss dass pseudocode für baumdurchmusterung kommt.
Zentor
18-05-2002, 20:18
Also es kommt bis auf Kruskal nur Stoff von Kapitel 1-5
Weiters wäre es gut sich den Pseudocode für die Tiefenen/Breitensuchen für Bäume und AVL-Baum,B-Bäume,Hashverfahren anzuschaun.
mfg Zentor
gck
19-05-2002, 12:54
In der Übungsgruppe hat uns de Tutor gesagt, es komme
1-3.5, 4, 5, 6.1.1, 6.1.2, 6.2, 6.3

d.h. faktisch alles außer dem Kruskal mit Union-Find und den Tries...
eXe
19-05-2002, 13:09
dann warst du wohl net im repetitiorium - ich würd mich an das von zentor halten ;)
Lukas
19-05-2002, 13:11
@gck: im repetitorium is genau das gesagt worden was der zentor gepostet hat. und nachdem der georg kraml die angaben schon gekannt hat kann man sich darauf sicher verlassen.
scheity
19-05-2002, 13:28
@gck:es steht auch so auf der homepage wie zentor schreibt
GetStoopid
19-05-2002, 16:46
bissl verwirrend fand ich es dennoch... weil auf die frage ob optimierung kommt sagte kraml "nein, keine greedy-algorithmen oder sonstwas", dann später hat er gesagt, daß kruskal kommt?!
gck
19-05-2002, 16:51
ok, auf der Algodat UE Website heißts, Kapitel 1-6.1.2, außer 3.6 (Tries).

Aber die Tries kommen auf keinen Fall, die sind ja nicht Stoff für Mathematiker und Wirtschaftsinformatiker, die aber denselben Test wie wir haben... außerdem waren die Tries doch noch nicht in der VO, oder?

Stimmt das jetzt so?
seimen
19-05-2002, 17:34
gibt es eigentlich irgendwo übungsbeispiele (nicht die UE-blätter) zum 2. UE-Test ??
GetStoopid
21-05-2002, 11:45
die frage ist immernoch, kommt kruskal, oder nicht???
daß tries nicht kommen und auch sonst keine greedy-algorithmen ist mir klar! das hat er im rep ja eh explizit gesagt
laut ihm kommt ja gar nix ausm 6. kapitel + 3.6 tries
aber kurz darauf sagte er was von kruskal... leider hab ich net so gut aufgepasst um mitzubekommen ob das jetzt stoff ist, oder nicht! =(
Chris
21-05-2002, 13:47
laut georg kommt kruskal zum test (ohne union find, oder wie das zeugs heißt)

mfg, chris
GetStoopid
21-05-2002, 15:00
hm... also doch! sehr unschön... hab nämlich keine ahnung was der können soll! =(
kann mir das jemand kurz und knapp erklären, oder ein bsp dazu bringen?
gck
21-05-2002, 15:08
das ist ganz einfach

du hast einen Graphen mit Knoten und Kanten.
Jede Kante hat einen Wert, du möchtest die "billigste" Kantenmenge, mit der jeder Knoten von jedem anderen erreichbar ist, ie die den Graphen komplett aufspannt

Der Alg ist:

1) du sortierst die Kanten nach ihrem Wert, von billig zu teuer.
2) Du fängst an mit einer leeren Kantenmenge
3) Du nimmst jetzt in jedem Schritt die billigste Kante und gibst sie in deine Kantenmenge.
4) Jetzt checkst du, ob kein Kreis entstanden ist (dann wäre diese Kante ja sinnlos, weil du damit keinen neuen Punkt in deinen Graphen mitaufspannst). Wenn sie einen Kreis erzeugt, verwirf sie und gehe wieder zu 3)
5) wenn sie keinen Kreis erzeugt, nimm sie in deine Kantenmenge auf und gehe wieder zu 3)
6) höre auf, wenn du genug Kanten hast, dass der ganze Graph aufgespannt wird. Diese Kantenmenge ist jetzt die billigste, die den Graph aufspannen kann, klar, weil du hast ja immer nur die billgst-möglichen Kanten genommen!!!!

hoffe, das ist so einigermaßen einsichtig.

Wenn du hingegen den teuersten MST kriegen willst, dann sortierst du im ersten Schritt einfach absteigend und fährst sonst genauso fort, wie beim billigsten Graph...

also, wenn so ein Beispiel zum Zeichnen kommt, das wär schon toll, weil das wirklich einfach ist. Programmiertechnisch ist das Erkennen eines Kreises zwar ein bissl kompliziert (klar, man kann jedes Mal DFS dazu verwenden, das wird dann aber ineffizient), aber beim Zeichnen sieht man es eh sofort!!
#!/usr/bin/perl
21-05-2002, 15:11
Soweit ich weiß is das doch der Algorithmus, der einen MST eines gewichtetn Graphens bestimmt, also einen minimalen aufspannenden Baum. Dazu ordnet er die Kanten aufsteigend nach ihren gewichten ( w<sub>k1</sub><=w<sub>k2</sub> ...) , dann nimmt der den Startknoten und schaut, ob der MST T ( der ja noch leer ist ) auch nach dessen Vereiniung mit der Kante w<sub>k1</sub> die MST Eigenschaften erfuellt ( Kreisfrei, minimales Gewicht, zusammenhaengend, aufspannden ), das macht er immer weiter so, nach dem Greedy Prinzip halt.

hoffe das stimmt so.

Oliver
GetStoopid
21-05-2002, 15:16
ojeojeoje... =( hat da wer ein graphisches bsp dazu?!
Lukas
21-05-2002, 15:36
Original geschrieben von Chris
laut georg kommt kruskal zum test (ohne union find, oder wie das zeugs heißt)

mfg, chris
wann soll er das gesagt haben? ich war im repetitorium und ab nix davon gehört. ausserdem hat er doch eindeutig gesagt das optimierung nicht kommt, und kruskal gehört zur optimierung.
Chris
21-05-2002, 16:40
das hat er bei den graphenalgorithmen dazugesagt.. dass da der kruskal auch noch dazu zählt...
#!/usr/bin/perl
21-05-2002, 17:00
die Idee hinter Kruskal ist doch eh simpel, und ausprogrammieren werden wirs nicht muessen, also sollte das doch machbar sein
Walter Huber
21-05-2002, 17:24
ich war auch dort... und soweit ich das richtig verstanden hab, hat er noch viel mehr veraten. er hat doch gesagt es kommt ein beispiel zu bäumen, eines zu hash-tabellen und eines zu graphen. und er hat auch gesagt, das keine optimierung kommt. ich glaube das ist eindeutig und das mit kruskal ist meiner ansicht nicht so ernst zu nehmen, da wir den algorithmus witklich noch nicht gemacht haben.
SinusDiabolicus
21-05-2002, 19:31
Original geschrieben von Walter Huber
ich war auch dort... und soweit ich das richtig verstanden hab, hat er noch viel mehr veraten. er hat doch gesagt es kommt ein beispiel zu bäumen, eines zu hash-tabellen und eines zu graphen. und er hat auch gesagt, das keine optimierung kommt. ich glaube das ist eindeutig und das mit kruskal ist meiner ansicht nicht so ernst zu nehmen, da wir den algorithmus witklich noch nicht gemacht haben.

du sagst es...
ein beispiel zu graphen!
und in die kategorie fällt der kruskal auch ;-)

also ich würd schon mit ihm rechnen, was sollte zu graphen auch sonst kommen? (bäume werden ja als eigene kategorie geführt...)
pedro
21-05-2002, 21:48
@seimen

weitere bsps zum thema algodat bzw pt gibts auf dem
<a href="http://winf.htu.tuwien.ac.at/studienplan.php?a=1&tpid=2299&lva=186099&ptpid=0&st=2001&zid=2220#2220">Link</a> der FS WINF

und zusätzlich schließe ich mich der aussage von SinusDiabolicus
an, dass kruskla zum thema graphen gehört
Shade
21-05-2002, 22:14
ein beispiel zu graphen!
und in die kategorie fällt der kruskal auch ;-)
also ich würd schon mit ihm rechnen, was sollte zu graphen auch sonst kommen?
naja,ich würd mal schätzen das entweder DFS kommt oder BFS.gehört ja zu graphen.
eXe
21-05-2002, 22:48
wahrscheinlich beides , gibt ja wieder gruppen