Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.
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?
Aufgabe 7
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);
}
}
}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.
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.
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?
Dazu siehe Aufgabenstellung:
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.
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?
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.
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.
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?
Was spricht dagegen, beides in einer zu machen?
Ups nichts, ich hätte mir wohl mal deinen code genauer anschauen sollen. :rolleyes:
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.
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.