Not logged in. · Lost password · Register

Danplan
Member since Oct 2016
40 posts
Subject: Klausur WS15 - Lösungsdiskussion
Hey,
da die Lösung zur WS15 noch unvollständig ist, habe ich mal begonnen mein Lösungsvorschlag reinzusetzen.
Unklarheiten würde ich hier besprechen.

Vieleicht findet sich ja noch einer, der an der Lösung mitarbeitet?
This post was edited 2 times, last on 2017-03-08, 17:52 by Danplan.
Danplan
Member since Oct 2016
40 posts
Subject: Aufgabe 7
void sammle(boolean[][] am, int k, Set<Integer> verb, Set<Integer> bes) {
        if (!bes.contains(k)) {
            verb.add(k);
            bes.add(k);
            for (int i = 0; i < am[k].length; i++) {
                if (am[k][i]){
                    sammle(am, i, verb, bes);
                }
            }
 
            for (int i = 0; i < am.length; i++) {
                if (am[i][k]){
                    sammle(am, i, verb, bes);
                }
            }
        }
    }

Eine Schleife würde meines erarchtens hier ausreichen, da am "wohlgeform [...] (also quadratisch und ohne null-Zeilen)" ist.

void sammle(boolean[][] am, int k, Set<Integer> verb, Set<Integer> bes) {
        if (!bes.contains(k)) {
            verb.add(k);
            bes.add(k);
            for (int i = 0; i < am[k].length; i++) {
                if (am[k][i])
                    sammle(am, i, verb, bes);
       
                if (am[i][k])
                    sammle(am, i, verb, bes);
               
            }
        }
    }
This post was edited on 2017-03-17, 14:06 by Danplan.
uv35imat
Member since Dec 2016
5 posts
In reply to post #1
Hi Danplan,

ich würde mithelfen (so gut ich kann).

Bis jetzt ist mir aufgefallen, dass bei Aufgabe 1c) auch die erste Aussage stimmen müsste, da die lineare Suche in so einem Fall sofort abbrechen kann.
Dass die Länge des Feldes keine 2er-Potenz ist, dürfte irrelevant sein.


Zu Aufgabe 2b):
Stimmen die Kollisionsarten hier?
Laut Vorlesungsfolien liegt eine Primärkollision dann vor, wenn versucht wird einen Wert in einem Fach zu speichern, dort aber schon ein anderer Wert "regulär", also ohne Sondieren abgelegt wurde. Eine Sekundärkollision hingegen, wenn der Platz von einem Überlaufelement belegt wurde. Deswegen ist meine Lösung diese:
A 1
B 3
C 3 (P)→ 4
D 3 (P)→ 4 (S)→ 0
E 0 (S)→ 1 (P)→ 4 (S)→ 2   // S bei 0, weil  D dort nach Überlauf/Sondieren abgelegt wurde, P bei 1 weil A hier ohne Sondieren (sondern direkt als Ergebnis von h(x)) abgelegt wurde.
Kann aber auch sein, dass ich da was falsch verstehe.
Danplan
Member since Oct 2016
40 posts
Hey,
ich habe die 2b nicht eingefügt und Stimme dir zu, dass die so nicht richtig ist.
So wie du es formulierst macht es allerdings Sinn.
Ich war mir nicht sicher ob es auch eine sekundärkolison ist, wenn das einzufügende element mit einem Überlauf element einer anderen hashfunktion kollidiert. Daher hab ich dazu auch keine LSG gemacht.
Danplan
Member since Oct 2016
40 posts
Bis jetzt ist mir aufgefallen, dass bei Aufgabe 1c) auch die erste Aussage stimmen müsste, da die lineare Suche in so einem Fall sofort abbrechen kann.

Bzgl der linearen suche, vergleicht die doch im Normalfall nur, ob dass gesuchte Element = dem i-ten Element ist.
Sicher kann man eine lineare Suche Methode fuer Reihen machen, die sortiert sind und dann einen Abbruchsfall implementieren, wenn das element kleiner als das erste.

Dazu muss man dann sicherstellen, dass die Zahlenreihe auch aufsteigend sortiert ist und nicht absteigend.

Aber bei einer allgemeinen linearen Suche kann ich nicht davon ausgehen, dass die Methode eine aufsteigend sortierte Zahlenreihe erhaelt. Oder verlangt die Frage nicht, daran zu denken?
This post was edited on 2017-04-07, 12:32 by Danplan.
yq53ykyr
Member since Oct 2016
112 posts
Quote by Danplan:
Bis jetzt ist mir aufgefallen, dass bei Aufgabe 1c) auch die erste Aussage stimmen müsste, da die lineare Suche in so einem Fall sofort abbrechen kann.

Bzgl der linearen suche, vergleicht die doch im Normalfall nur, ob dass gesuchte Element = dem i-ten Element ist.
[...]
Dazu muss man dann sicherstellen, dass die Zahlenreihe auch aufsteigend sortiert ist und nicht absteigend.

Dazu siehe Aufgabenstellung:
Quote by Aufgabenstellung:
Unter welchen Umständen ist die sequentielle (lineare) Suche nach einem Wert v in einem
aufsteigend sortierten Feld
schneller als die binäre Suche?
Grundsätzlich finde ich aber den ersten Punkt interessanter und auch richtiger. IMHO wäre mit einer solchen Implementierung nicht mehr unbedingt der worstcase von O(n) (mit n:=#v) gegeben, und damit wäre der Algorithmus nicht mehr per se als die "Lineare Suche" beschreibbar. Somit sollte 1c)-A nicht gelten dürfen.
RiederJo
Member since Oct 2016
23 posts
Bei der 1g) sollten doch 1 und 4 richtig sein, 2 ergibt doch überhaupt keinen Sinn, dass *für alle* n größer n0 gilt dass das dazwischen liegt. Sobald h und g unterschiedliche Laufzeiten haben ist das falsch.

Bei der f): wie soll man bitteschön mit Graham das Knapsackproblem lösen? Google findet auch nix

Und warum ist bei der c) die 1 nicht richtig? Es steht dort, dass man von einem aufsteigend sortierten Feld ausgehen kann - dann ist die Lineare Suche mit = und < doch sinnvoll?
This post was edited on 2017-04-09, 14:37 by RiederJo.
pda
Member since Sep 2016
22 posts
Quote by RiederJo:
Und warum ist bei der c) die 1 nicht richtig? Es steht dort, dass man von einem aufsteigend sortierten Feld ausgehen kann - dann ist die Lineare Suche mit = und < doch sinnvoll?

Ich denke auch dass in diesem Fall (1) die sequentielle Suche schneller ist, da ja bereits beim ersten Feld erkannt wird, dass v nicht im Feld enthalten ist.
Bei 1c) stimme ich daher für die Antworten 1 und 2.
Johanno
Johanno
Member since Mar 2017
24 posts
In reply to post #2
Quote by Danplan on 1970-01-01, 02:44:
Aufgabe 7:

Eine Schleife würde meines erarchtens hier ausreichen, da am "wohlgeform [...] (also quadratisch und ohne null-Zeilen)" ist.


Ich denke, da es ein gerichteter Graph ist, ist
am[k][i] != am[i][k]
und somit müssen 2 schleifen gemacht werden, um "ungeachtet der gerichteten Kanten"  die knoten hinzuzufügen.
Johanno
Johanno
Member since Mar 2017
24 posts
Subject: Aufgabe 8 c)
hab mich mal an der 8 c) versucht:
Mein Grundgedanke ist: Wenn es keine Kante auf X gibt muss es eine Wurzel sein.
Jetzt kann ich aber nicht wirklich aus (collect(g)) irgend etwas rausnehmen.

Meine Idee war jetzt: isRoot(Edge(g, a, b), x) = NICHT path(g, collect(g), x))

aber path(g,SET, x) ist nicht definiert. Aber alle anderen meiner Ansätze würden nur Aussagen über a und b treffen können und somit nicht allgemein gelten.
Und ich weiß auch nicht wie man das rekursiv runter brechen soll. Jmd. bessere Ansätze?
This post was edited on 2017-04-09, 18:30 by Johanno.
Danplan
Member since Oct 2016
40 posts
In reply to post #9
Quote by Johanno:
Quote by Danplan on 1970-01-01, 02:44:
Aufgabe 7:

Eine Schleife würde meines erarchtens hier ausreichen, da am "wohlgeform [...] (also quadratisch und ohne null-Zeilen)" ist.


Ich denke, da es ein gerichteter Graph ist, ist
am[k][i] != am[i][k]
und somit müssen 2 schleifen gemacht werden, um "ungeachtet der gerichteten Kanten"  die knoten hinzuzufügen.
Was spricht dagegen, beides in einer zu machen?
Johanno
Johanno
Member since Mar 2017
24 posts
Ups nichts, ich hätte mir wohl mal deinen code genauer anschauen sollen. :rolleyes:
Andimaddin
Member since Sep 2017
1 post
In reply to post #10
Mein Vorschlag für die 8c) wäre gewesen:

isRoot (Edge(g,a,b),x) = false, falls x=b; isRoot(g,x) , sonst. Damit hätte man zumindest ne Rekursion drin und verwendet auch nur axiome, die es auch wirklich gibt ;)
LasagneAlForno
LasagneAlForno
Member since Dec 2017
80 posts
Quote by Andimaddin on 2018-03-08, 20:29:
Mein Vorschlag für die 8c) wäre gewesen:

isRoot (Edge(g,a,b),x) = false, falls x=b; isRoot(g,x) , sonst. Damit hätte man zumindest ne Rekursion drin und verwendet auch nur axiome, die es auch wirklich gibt ;)

Ja, das ist richtig.
Ich verstehe außerdem nicht, warum man bei der a) doppelt add hat. Denn a und b sind ja in G enthalten, so fügt man die nur doppelt ein.
TOKAMAK
Member since Oct 2014
125 posts
Bei der 8c) fehlt noch

true        falls x=a && !IsIn(collect(g), x)

was offensichtlich TRUE ausgeben sollte, im Fall der aktuellen Loesung aber zu FALSE fuehren wuerde, weil x/a nicht in g enthalten sind und es somit nie zu der Situation "(x = n) ∧ ¬ isIn(collect(g), x)" kommen kann. Wodurch es dann bis zum Basisfall "isRoot(New, x) = false" durchfaellt und FALSE zurueckgibt.
Close Smaller – Larger + Reply to this post:
Verification code: VeriCode Please enter the word from the image into the text field below. (Type the letters only, lower case is okay.)
Smileys: :-) ;-) :-D :-p :blush: :cool: :rolleyes: :huh: :-/ <_< :-( :'( :#: :scared: 8-( :nuts: :-O
Special characters:
Go to forum
Datenschutz | Kontakt
Powered by the Unclassified NewsBoard software, 20150713-dev, © 2003-2011 by Yves Goergen