Ausgearbeitete Prüfungsfragen!?
Results 1 to 20 of 20
  1. #1

    Title
    Principal
    Join Date
    Mar 2002
    Posts
    92
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Ausgearbeitete Prüfungsfragen!?

    hoi!

    gibts zufällig irgendwo die ausgearbeiteten prüfungen des letzten termines online?

    mir sind einige lösungen nicht klar..

    wäre sehr hilfreich.. danke..

  2. #2
    wolk's Avatar
    Title
    Baccalaureus
    Join Date
    Jun 2002
    Posts
    986
    Thanks
    0
    Thanked 0 Times in 0 Posts
    nein, ich habs auch schon vergebens versucht

    aber wir könnten ja mal damit anfangen unsere privaten lösungen reinzuposten und dann werden andere es hoffentlich korrigieren

  3. #3

    Title
    Principal
    Join Date
    Mar 2002
    Posts
    92
    Thanks
    0
    Thanked 0 Times in 0 Posts
    könntet ihr bitte eure lösungen für folgende fragen posten:

    1) Gegeben sei ein gerichteter Graph G = (V, E) mit Knotenmenge V und Kantenmenge E.
    Erstellen Sie einen detallierten Pseudocode für einen Algorithmus, der für einen
    gegebenen Knoten u Î V feststellt, ob ein gerichteter Kreis in G existiert, der u
    beinhaltet. Gibt es einen solchen Kreis, so sollen alle darauf liegenden Knoten
    ausgegeben werden.

    Aufgabe 5.D: Optimierung
    Beantworten Sie folgende Punkte in möglichst wenigen, aber genauen Worten.
    a) (2 Punkte)
    Nennen Sie drei klassische NP-schwere Probleme (die Namen reichen).
    b) (2 Punkte)
    Was bedeutet hohe Lokalität bei Simulated Annealing?
    c) (2 Punkte)
    Was bedeutet es, wenn Sie für ein Minimierungsproblem einem e-approximativen
    Algorithmus haben?
    d) (4 Punkte)
    Beschreiben Sie das Grundprinzip eines evolutionären Algorithmus in Pseudocode.


    danke...

  4. #4

    Title
    Veteran
    Join Date
    Apr 2002
    Posts
    24
    Thanks
    0
    Thanked 0 Times in 0 Posts
    Also der Pseudocode bei der Tiefensuche mit einem gerichteten Graph würde mich auch sehr interessieren ... ich komme da einfach nicht drauf.
    Irgendwie habe ich sowieso Probleme mit den Graphen und verstehe es nicht ganz.
    Vielleicht würde es helfen, wenn jemand das Beispiel posten könnte ...

  5. #5
    wolk's Avatar
    Title
    Baccalaureus
    Join Date
    Jun 2002
    Posts
    986
    Thanks
    0
    Thanked 0 Times in 0 Posts
    @swida a) 8-damen-problem, rucksackproblem, minimal aufspannende bäume

    b)Eine Nachbarlösung muss aus ihrer Ausgangslösung durch eine "kleine" Änderung abgeleitet werden können, Dieser kleine Unterschied muss im Allgemeinen auch eine kleine Änderung der Bewertung bewirken. Sind diese Voraussetzungen erfüllt, spricht man von hoher Lokalität - eine effiziente Optimierung ist möglich

    c) falls ca(P) / copt(P) <= epsilon
    für alle Probleminstanzen P und epsilon > 0, dann heißt A ein epsilon-approximativer Algorithmus und die Zahl epsilon heißt gütegarantie von Algorithmus A (eprog skript seite 146)

    d) k.a.

  6. #6
    AntiBit's Avatar
    Title
    Baccalaureus
    Join Date
    Feb 2002
    Location
    Wien
    Posts
    738
    Thanks
    0
    Thanked 6 Times in 3 Posts
    Na gut, ich hab mich heute hingesetzt und gegrübelt und gegrübelt...

    Also ich hab den Algorithmus mit der Kreissuche in einem gerichteten Graphen folgendermassen gemacht:

    DFS1(V,E,Startknoten x)
    {
    Lösungs[];
    i=1;

    Für alle v€V: makiert(v)=0;
    falls x !€ V return Fehler;
    DFS2(x);
    Ausgabe("Kein Kreis mit x gefunden");
    }

    DFS2(v)
    {
    falls markiert(v) != 1 { markiert(v)=1; }

    für alle Knoten n € N-(v) /* Dieses N- bedeutet ausgehende
    Nachbarmenge, siehe Skriptum Seite 110 */
    {
    falls markiert(n) != 1
    {
    Lösungs[ i ] = n; i++;
    DFS2(n);
    }
    sonst { Ausgabe aller Elemente in Lösungs[], +x; Programm
    beenden, Kreis gefunden }
    }
    }
    Also, laut meinen Testüberlegungen gibt der Algorithmus einen Kreis aus, wenn es einen gibt mit dem Knoten x. Aber wenn es mehrere Kreise mit x gibt, dann gibt er nur einen aus... Besser hab ichs nicht geschafft. Die Angabe verlangt ja aber glaub ich auch nur einen gerichteten Kreis!
    Wenn euch Fehler auffallen, bitte posten!

    P.S. Hab auch noch einen Algorithmus gemacht, der in einem Graphen alle Knoten mit der Nummer der Zusammenhangskomponente ausgibt, in der sich der Knoten befindet. Ähnlich dem Skriptum DFS2-Alg., aber mit Dynamisch Disjunkter Menge, weils verlangt war. Wenn den wer braucht...

    P.S. Habt ihr noch andere Angaben von Fragestellungen zu Algorithmen der letzten Prüfung? Denn wenn man die nicht geübt hat, dann siehts düster aus bei der Prüfung

    Gruss,
    AntiBit
    Last edited by AntiBit; 10-10-2002 at 01:23.
    Hätten uns Spiele wie Pac-Man in unserer Jugend beeinflusst, würden wir heute durch dunkle Räume irren, elektronische Musik hören und Pillen fressen.

  7. #7
    wolk's Avatar
    Title
    Baccalaureus
    Join Date
    Jun 2002
    Posts
    986
    Thanks
    0
    Thanked 0 Times in 0 Posts
    ja notationen

    angenommen (schon gekürzt, durchdividiert und so)

    0 <= c <= 1/n3 + 1/6n9

    gibt es hier ein c ?
    ich glaub nicht oder ?

    mfg

  8. #8
    AntiBit's Avatar
    Title
    Baccalaureus
    Join Date
    Feb 2002
    Location
    Wien
    Posts
    738
    Thanks
    0
    Thanked 6 Times in 3 Posts
    @wolk:

    6n9?

    Nein da gibts kein c, weil beide Teile von f(n) gegen null streben.

    @Swida:

    ad d.)

    P = Menge von Ausgangslösungen
    bewerte(P);

    wiederhole
    {
    Qs= Selektion(P);
    // hier werden einige Lösungen zufällig per FitnessProp.- oder TournamentSelection ausgewählt

    Qr=Rekombination(Qs);
    // Entspricht der Lokalität beim Simulated Annealing: Aus 2 slekt. Lösungen werden neue Lösungen durch kleine Änderungen erzeugt.

    P=Mutation(Qr);
    //Bringt verlorengegangene Merkmale in die Lösung ein, ähnlich der Nachbarschaftsunktion in Sim. Annealing.

    bewerte(P);
    }
    bis Abbruchkriterium erfüllt ist (z.B. die Bewertung der Lösung ist um ein gewisses Maß gestiegen)

    Hope that helps. Zeit zu schlafen
    Last edited by AntiBit; 10-10-2002 at 02:37.
    Hätten uns Spiele wie Pac-Man in unserer Jugend beeinflusst, würden wir heute durch dunkle Räume irren, elektronische Musik hören und Pillen fressen.

  9. #9

    Title
    Principal
    Join Date
    Feb 2002
    Posts
    30
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Aufgabe 1b, GruppeD (Notationen)

    Hi an Alle

    Ich hätte da eine Frage, zu einem Beispiel, wo ich mir nicht ganz sicher bin:

    es ist gegeben: f(n) ist (log10n)/3n+5n^3 für 2^n<10^8
    und 1/3n+1/6n^4+1/9n^5 für 2^n=10^8

    kann man hier zur Überprüfung der Notation die 1. Bedingung vernachlässigen? (wegen 2^n < 10^8, d.h. für kleine n)

    Ich würde ja sagen, allerdings gibt es für die 2. Bedingung ja nur 1 n, das irritiert mich ziemlich;

    THX

  10. #10

    Title
    Veteran
    Join Date
    Apr 2002
    Posts
    24
    Thanks
    0
    Thanked 0 Times in 0 Posts
    Ich glaube, dass die Angabe falsch ist ... und das die 2te Bedingung >= sein soll ... dann kann man die erste Funktion vernachläßigen ...
    Wenn es wirklich = wäre (war bei meiner Angabe damals sicher nicht .. da war es >=), dann bin ich auch etwas ratlos, dann müßten aber wohl beide Bedingungen erfüllt werden ... wäre aber schon irgendwie komisch .. da müßte man sich vorher das n ausrechnen bei dem die Bedingung erfüllt wäre ... also ich kann es mir nicht ganz vorstellen ... aber gut falls doch, dann kann n ja auch den Wert annehmen und es müßten beide erfüllt werden ...

  11. #11
    patricasso's Avatar
    Title
    Baccalaureus
    Join Date
    Feb 2002
    Posts
    750
    Thanks
    1
    Thanked 2 Times in 2 Posts
    Kann man für die Konstanten jede beliebige Zahl nehmen ( mein vom Wertebereich - z.B: reele positive)?
    Last edited by patricasso; 10-10-2002 at 18:44.
    http://www.svkukmirn.com + http://www.swc-kukmirn.com

    Topfield TF 5000 PVR 80GB (incl. Alphacrypt) + TF 3000 CIpro (incl. Cryptoworks) + D-BoxII (Sagem - Neutrino :-) + SAB-Explorer CISC + Panasonic DMR-EH52EG-S (80 GB HD/DVD Recorder)... 19,2°E, 13° E
    -----------SUCHE MÜNZTAUSCHPARTNER/INNEN-----------

  12. #12

    Title
    Master
    Join Date
    Feb 2002
    Posts
    141
    Thanks
    0
    Thanked 0 Times in 0 Posts
    hab eine ähnliche Frage...
    es geht darum ob f(n) = O(log n) mit
    f(n) = 1/125 * log n + 5 für n > 125
    und
    f(n) = 1/125 * n³ + 25n² +5n für n < 125

    also, kann man bei der Berechnung von O das f(n) für Werte unter einer bestimmten Grenze vernachlässigen oder nicht?

    (dann gilt das gleiche nämlich auch für die Berechnung von omega für f(n) über einer bestimmten Grenze)

  13. #13
    AntiBit's Avatar
    Title
    Baccalaureus
    Join Date
    Feb 2002
    Location
    Wien
    Posts
    738
    Thanks
    0
    Thanked 6 Times in 3 Posts
    @ Patricasso: Versteh deine Frage nicht ganz(?)

    @ MrBurnst:

    Jo also die Aussage stimmt, f(n)=O(log n), für n index 0 = 126 und c = 6. Nur die n > 125 Bedingung interessiert uns, da wir einfach ein grosses n wählen
    Hätten uns Spiele wie Pac-Man in unserer Jugend beeinflusst, würden wir heute durch dunkle Räume irren, elektronische Musik hören und Pillen fressen.

  14. #14
    Jokeman's Avatar
    Title
    Hero
    Join Date
    Feb 2002
    Location
    near Vienna
    Posts
    210
    Thanks
    0
    Thanked 0 Times in 0 Posts
    Original geschrieben von AntiBit
    Also, laut meinen Testüberlegungen gibt der Algorithmus einen Kreis aus, wenn es einen gibt mit dem Knoten x. Aber wenn es mehrere Kreise mit x gibt, dann gibt er nur einen aus... Besser hab ichs nicht geschafft. Die Angabe verlangt ja aber glaub ich auch nur einen gerichteten Kreis!
    Wenn euch Fehler auffallen, bitte posten!
    Gruss,
    AntiBit [/B]
    ich wollt grad schimpfen, weil Du vergessen hast, zu ueberpruefen, ob der markierte knoten nicht eigentlich der vater is...
    dann hab ich mir aufs hirn gegriffen, und gecheckt, dass das ja ein gerichteter graph is, und Du durch das N- ja nicht zurückmaschieren kannst...

    is denk, der code sollte so passen
    Command & Conquer
    =Return of the Dawn=

    TS to TD total conversion

  15. #15

    Title
    Principal
    Join Date
    Feb 2002
    Posts
    30
    Thanks
    0
    Thanked 0 Times in 0 Posts

    zur Kreissuche:

    Ich hab mir auch einen Algorithmus überlegt, bei dir werden nämlich, sofern ich deine Lösung richtig verstanden habe, auch die Knoten , die nicht zum Kreis gehören, ausgegeben:

    KREISSUCHE(u)
    {
    für alle v€G setze markiert = NULL /*hab 3 zustände für markiert, wobei knoten mit zustand 1 zum Kreis gehören, mit zustand 2 schon angesehen und nicht zum Kreis gehören */
    v=u
    DFS(v)
    return "kein Kreis"
    }

    DFS(v)
    {
    für alle Knoten w !=0 und w!=1 aus N-(v)
    {
    falls w==u
    {KREIS()}
    sonst falls !€N-(v) oder mariert(w)==0
    {v=0}
    sonst falls w==NULL
    {markiere w=1}
    DFS(w)
    }
    }

    KREIS()
    {
    return v mit markiert ==1 und u
    abbruch
    }

    kann sein, dass die Lösung völliger Mist ist, daher bitte ich, falls möglich um Korrektur.
    Last edited by josi; 11-10-2002 at 02:04.

  16. #16
    wolk's Avatar
    Title
    Baccalaureus
    Join Date
    Jun 2002
    Posts
    986
    Thanks
    0
    Thanked 0 Times in 0 Posts
    kommt ihr vielleicht ne halbe stunde früher zum test ? so halb 3
    dann könnten wir ja noch die kreissuche im graphen diskutieren

    ich glaub dass keiner der oben genannten codes 100%ig das richtige ergebnis liefert

    ich kann mich aber auch irren
    mfg wolk

  17. #17

    Title
    Master
    Join Date
    Apr 2002
    Location
    burgenland
    Posts
    163
    Thanks
    0
    Thanked 0 Times in 0 Posts
    post #11:
    Damit war gemeint ob z.B c 1/6 oder so sein kann! also
    0 < c < 1

  18. #18

    Title
    Principal
    Join Date
    Feb 2002
    Posts
    30
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Treffen vor der Prüfung

    ok, ich würd sagen, um halb 3 beim unteren Eingang vom AudiMax (colaautomat)

  19. #19
    Jokeman's Avatar
    Title
    Hero
    Join Date
    Feb 2002
    Location
    near Vienna
    Posts
    210
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Re: zur Kreissuche:

    Original geschrieben von josi
    Ich hab mir auch einen Algorithmus überlegt, bei dir werden nämlich, sofern ich deine Lösung richtig verstanden habe, auch die Knoten , die nicht zum Kreis gehören, ausgegeben:

    kann sein, dass die Lösung völliger Mist ist, daher bitte ich, falls möglich um Korrektur.
    also mir gefallt antibits loesung besser...
    wobei Du glaub ich recht hast, mit der ausgabe aller knoten... man muesste, statt die knoten in einem array zu speichern, sie in einem baum abspeichern... und dann kann man zurueck zur wurzel maschieren und den kreis ausgeben
    bei Deinem algorithmus blick ich noch nicht so ganz durch... Du hast 3 zustaende... ich sehe aber in Deinem code keine zeile, wo der zustand auf 2 gesetzt wird... oder hab ich da was uebersehen?
    Command & Conquer
    =Return of the Dawn=

    TS to TD total conversion

  20. #20

    Title
    Principal
    Join Date
    Feb 2002
    Posts
    30
    Thanks
    0
    Thanked 0 Times in 0 Posts
    meine zustände sind null, 0 und 1

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
  •