[FRAGE] - was kommt zum UE Test 2?
Results 1 to 30 of 30
  1. #1
    scheity's Avatar
    Title
    Hero
    Join Date
    Feb 2002
    Location
    schwaz/vienna
    Posts
    177
    Thanks
    0
    Thanked 0 Times in 0 Posts

    was kommt zum UE Test 2?

    ist dies schon bekannt???????

  2. #2
    Länz's Avatar
    Title
    Principal
    Join Date
    Feb 2002
    Posts
    78
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Arrow

    außer Kapitel 6.1.4 (kommt nicht!) entspricht die Stoff-Abgrenzung jener für Studierende der Mathematik und WInf. - Skriptum Seite 8

  3. #3

    Title
    Master
    Join Date
    Mar 2002
    Posts
    158
    Thanks
    0
    Thanked 0 Times in 0 Posts
    also auch der gesamte Stoff, der schon zum vorherigen UE-Test gekommen ist ??

  4. #4

    Title
    Mag.rer.soc.oec
    Join Date
    Nov 2001
    Location
    dzt. München
    Posts
    1,270
    Thanks
    0
    Thanked 0 Times in 0 Posts
    jap, so ist es

  5. #5
    scheity's Avatar
    Title
    Hero
    Join Date
    Feb 2002
    Location
    schwaz/vienna
    Posts
    177
    Thanks
    0
    Thanked 0 Times in 0 Posts
    also sozusagen das gesammte skriptum ausser kapitel 6.1.4?!?

  6. #6
    RoadRash's Avatar
    Title
    Elite
    Join Date
    Jan 2002
    Location
    Oberwart / Wien
    Posts
    274
    Thanks
    0
    Thanked 0 Times in 0 Posts
    ja, aber nur bis (einschließlich) 6.3 Dynamische Programmierung
    Ceterum censeo, carthaginem esse delendam.

  7. #7
    SinusDiabolicus's Avatar
    Title
    Elite
    Join Date
    Jan 2002
    Location
    Wien
    Posts
    383
    Thanks
    0
    Thanked 0 Times in 0 Posts
    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

  8. #8

    Title
    Hero
    Join Date
    Mar 2002
    Posts
    184
    Thanks
    0
    Thanked 0 Times in 0 Posts
    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.

  9. #9
    Zentor's Avatar
    Title
    CO-Administrator
    Join Date
    Dec 2001
    Location
    Wien???
    Posts
    1,156
    Thanks
    2
    Thanked 9 Times in 6 Posts
    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

  10. #10

    Title
    Elite
    Join Date
    Feb 2002
    Posts
    482
    Thanks
    0
    Thanked 0 Times in 0 Posts
    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...

  11. #11
    eXe's Avatar
    Title
    Principal
    Join Date
    Feb 2002
    Posts
    99
    Thanks
    0
    Thanked 0 Times in 0 Posts
    dann warst du wohl net im repetitiorium - ich würd mich an das von zentor halten

  12. #12

    Title
    Hero
    Join Date
    Feb 2002
    Location
    Wien
    Posts
    185
    Thanks
    0
    Thanked 0 Times in 0 Posts
    @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.

  13. #13
    scheity's Avatar
    Title
    Hero
    Join Date
    Feb 2002
    Location
    schwaz/vienna
    Posts
    177
    Thanks
    0
    Thanked 0 Times in 0 Posts
    @gck:es steht auch so auf der homepage wie zentor schreibt

  14. #14

    Title
    Elite
    Join Date
    Jan 2002
    Location
    vienna/austria
    Posts
    471
    Thanks
    0
    Thanked 1 Time in 1 Post
    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?!
    "Von allen Dingen die mir verloren gegangen, hab ich am meisten an meinem Verstand gehangen"

  15. #15

    Title
    Elite
    Join Date
    Feb 2002
    Posts
    482
    Thanks
    0
    Thanked 0 Times in 0 Posts
    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?

  16. #16

    Title
    Hero
    Join Date
    Mar 2002
    Posts
    184
    Thanks
    0
    Thanked 0 Times in 0 Posts
    gibt es eigentlich irgendwo übungsbeispiele (nicht die UE-blätter) zum 2. UE-Test ??

  17. #17

    Title
    Elite
    Join Date
    Jan 2002
    Location
    vienna/austria
    Posts
    471
    Thanks
    0
    Thanked 1 Time in 1 Post
    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! =(
    "Von allen Dingen die mir verloren gegangen, hab ich am meisten an meinem Verstand gehangen"

  18. #18

    Title
    Elite
    Join Date
    Jan 2002
    Posts
    314
    Thanks
    0
    Thanked 0 Times in 0 Posts
    laut georg kommt kruskal zum test (ohne union find, oder wie das zeugs heißt)

    mfg, chris
    hi, i'm a signature virus. copy me into your signature to help me spread.

  19. #19

    Title
    Elite
    Join Date
    Jan 2002
    Location
    vienna/austria
    Posts
    471
    Thanks
    0
    Thanked 1 Time in 1 Post
    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?
    "Von allen Dingen die mir verloren gegangen, hab ich am meisten an meinem Verstand gehangen"

  20. #20

    Title
    Elite
    Join Date
    Feb 2002
    Posts
    482
    Thanks
    0
    Thanked 0 Times in 0 Posts
    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!!

  21. #21
    #!/usr/bin/perl's Avatar
    Title
    Elite
    Join Date
    Jan 2002
    Posts
    291
    Thanks
    0
    Thanked 1 Time in 1 Post
    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
    this is Unix land. In silent nights, you can hear Windows machines reboot...

  22. #22

    Title
    Elite
    Join Date
    Jan 2002
    Location
    vienna/austria
    Posts
    471
    Thanks
    0
    Thanked 1 Time in 1 Post
    ojeojeoje... =( hat da wer ein graphisches bsp dazu?!
    "Von allen Dingen die mir verloren gegangen, hab ich am meisten an meinem Verstand gehangen"

  23. #23

    Title
    Hero
    Join Date
    Feb 2002
    Location
    Wien
    Posts
    185
    Thanks
    0
    Thanked 0 Times in 0 Posts
    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.

  24. #24

    Title
    Elite
    Join Date
    Jan 2002
    Posts
    314
    Thanks
    0
    Thanked 0 Times in 0 Posts
    das hat er bei den graphenalgorithmen dazugesagt.. dass da der kruskal auch noch dazu zählt...
    hi, i'm a signature virus. copy me into your signature to help me spread.

  25. #25
    #!/usr/bin/perl's Avatar
    Title
    Elite
    Join Date
    Jan 2002
    Posts
    291
    Thanks
    0
    Thanked 1 Time in 1 Post
    die Idee hinter Kruskal ist doch eh simpel, und ausprogrammieren werden wirs nicht muessen, also sollte das doch machbar sein
    this is Unix land. In silent nights, you can hear Windows machines reboot...

  26. #26
    Walter Huber's Avatar
    Title
    Elite
    Join Date
    May 2002
    Posts
    387
    Thanks
    11
    Thanked 5 Times in 3 Posts
    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.

  27. #27
    SinusDiabolicus's Avatar
    Title
    Elite
    Join Date
    Jan 2002
    Location
    Wien
    Posts
    383
    Thanks
    0
    Thanked 0 Times in 0 Posts
    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...)

  28. #28

    Title
    Veteran
    Join Date
    May 2002
    Posts
    22
    Thanks
    0
    Thanked 0 Times in 0 Posts
    @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&s t=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
    Last edited by pedro; 21-05-2002 at 21:51.

  29. #29
    Shade's Avatar
    Title
    Elite
    Join Date
    Mar 2002
    Posts
    484
    Thanks
    0
    Thanked 0 Times in 0 Posts
    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.
    ALL GLORY TO THE HYPNO TOAD...

  30. #30
    eXe's Avatar
    Title
    Principal
    Join Date
    Feb 2002
    Posts
    99
    Thanks
    0
    Thanked 0 Times in 0 Posts
    wahrscheinlich beides , gibt ja wieder gruppen

Bookmarks

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •