Kein Gedächtnisprotokoll, weil die Klausur einfach viel zu umfangreich war, aber:

7 Aufgaben:

1. multiple Choice: hauptsächlich Laufzeitkomplexität von bekannten Algorithmen und Anzahlen von bekannten Graphen/Bäumen

2. Laufzeit berechnen: Drei Laufzeiten mit Hilfe des Master-Theorems ausrechnen

3. Laufzeitabschätzung: Einen rekursiven divide-and-conquer Algorithmus untersuchen und die asymptotische Laufzeit abschätzen. Ferner die Korrektheit des Algorithmus beweisen. Der Algorithmus sollte das maximale Element eines Arrays finden.

4. Hashtabellen: Sondierungsfolgen & Einfügereihenfolgen erklären, quadratische Sondierung anwenden

5. balancierte Suchbäume: Implementation in Pseudocode von einem Algorithmus, der alle Zahlen unter einem bestimmten Wert zusammenzählt. Änderung von einigen vorgegeben Algorithmen um diese Aufgabe zu erfüllen.

6. gerichtete Graphen: Algorithmus beschreiben, der Zyklen findet. Auch kompleltt disjunkte Zyklen.


7. minimale Spannbäume: minimalen Spannbaum anhand eines (beliebigen) Algorithmusses erstellen und diesen benennen können. Beweisen, ob eine Kante e mit minimalem Kantengewicht in a) einem Spannbaum drin ist und b) in allen Spannbaum drin ist.

Und einige ~Lösungen dazu:

zu 3. O(ld N)? (Weil der Algorithmus die Eingabemenge immer durch zwei teilt)

zu 4. Die Sondierungsfolge ist unabhängig von der Einfügereihenfolge weil sie keine Aussage darüber trifft, in welchem Sondierungsschritt das Element letztlich einsortiert wird.

zu 5. Jeder Knoten muss die Summe aller Knoten seinem linken Teilbaum gespeichert haben. Sie der bestimmte Wert x. In jedem Rekursionsschritt wird dann folgendes gemacht:
Es wird ähnlich vorgegangen wie bei der Suche nach Element x. Nur dass bei jedem Schritt noch falls nach rechts gegangen wird, zur Ergebnismenge der aktuelle Knoten plus die Summe der Kanten seiner linken Kanten hinzugezaehlt wird. Sollte dann x letztlich nicht im Baum sein, ist nicht schlimm. Die Ergebnismenge bleibt trotzdem richtig.

zu 7. Wenn e eine Kante mit minimalem Kantengewicht ist, taucht diese Kante mindestens in einem minimalen Spannbaum auf. Nämlichb in dem, bei dem der Algorithmus die Kante e als erstes wählt. Das ist garantiert.
Die Kante e taucht nicht in jedem minimalen Spannbaum auf, folgendes Gegenbeispiel. e sei (C,1,A):
G = {{A,B,C},{(A,1,B),(B,1,C),(C,1,A))}}
Wenn hier zuerst (A,1,B) dann (B,1,C) für den minimalen Spannbaum gewählt wird, kann (C,1,A) nicht mehr in den minimalen Spannbaum, da sonst ein Zyklus entstehen würde.
Allgemein also: Wenn in dem Graph G Kanten mit minimalem Kantengewicht shcon einen Zyklus bilden, taucht e nicht in allen minimalen Spannbäumen von G auf.

bei 6 solltest du einen Algo für Zyklen finden, die zwar keine gemeinsamen Kanten, aber (einen gemeinsamen / gemeinsame) Knoten haben.

Ja, 6 war: Schreiben sie einen Algorithmus in kommentiertem Pseudocode, der für einen Knoten aus einem gerichteten Graphen bestimmt, ob er in 2 Kantendisjunkten Zyklen vorkommt.

zu 3. O(ld N)? (Weil der Algorithmus die Eingabemenge immer durch zwei teilt)

Das wäre revolutionär, weil die Bestimmung des Maximums in [img]http://mokrates.de/cgi-bin/texstring?%5COmega(N)[/img] liegt.
Mit Rekurrenzgleichung [img]http://mokrates.de/cgi-bin/texstring?T(n)%20%3D%202*T(n%2F2)%20%2B%20c[/img] und Fall 1 des Master-Theorems kommt O(N) heraus.

zu 4. Die Sondierungsfolge ist unabhängig von der Einfügereihenfolge weil sie keine Aussage darüber trifft, in welchem Sondierungsschritt das Element letztlich einsortiert wird.

Jein… die Sondierungsfolge ist unabhängig von der Einfügereihenfolge der Elemente, weil die Hashfunktion h(k, i) die momentane Belegung der Hashtabelle nicht berücksichtigt.

Im Multiple Choice - Teil waren auch einige ziemlich schwere Fragen, die in anderen Klausuren eher als richtige Aufgabe drangekommen wären.
Was mir noch einfällt: "Auf jedem kürzesten Weg zwischen zwei Knoten eines Graphen gibt es eine Kante, die auch Teil eines minimalen Spannbaums des Graphen ist." ([Ja / Nein] + Begründung)

zu 4., genauere Aufgabe:
Hashfunktion: g(k) = k mod 11
Quadratisches Sondieren: h(k, i) = (g(k) + 1/2(i + i^2)) mod 11
1. Begründen Sie, warum die Sondierungsfolge nicht von der Einfügereihenfolge der Elemente abhängt.
2. Gefüllte Hashtabelle mit 11 Werten: Bestimmen Sie die Sondierungsfolge für die einzelnen Werte bis zu der Position, an der sie eingefügt worden. Für 4 Zahlen haben wir das schonmal eingetragen. Hier ist nochmal die Hashfunktion, damit sie nicht umblättern müssen.
3. Geben Sie eine Einfügereihenfolge für die Elemente an, die zur angegebenen Füllung der Hashtabelle führen würde. Begründen Sie dies für die ersten 3 Elemente.

zu 5., genaue Aufgabe:
1. Wie können Sie die Datenstruktur eines balancierten, binären Suchbaums so verändern, dass sich die Frage "Wie viele Elemente haben einen Wert kleiner als x" in O(log n) beantworten lässt? Begründen Sie Ihre Lösung.
2. Schreiben Sie einen Algorithmus, der das tut. (Stand da natürlich ein bisschen anders…)
3. Verändern Sie folgende Algorithmen zum Einfügen eines Elementes und für die Linksrotation, damit das mit der veränderten Datenstruktur auch passt. (So sinngemäß.)

zu 6.: Einmal das was Viprex schon sagte, und dann noch die Frage: Wie können Sie in …. Zeit für einen gerichteten Graphen entscheiden, ob er Zyklen enthält?

zu 7.: Es war also ein kantengewichteter Graph gegeben und man sollte den Spannbaum einzeichnen sowie beschreiben, wie man vorgegangen ist. Und den Namen des Algorithmus angeben, wenn Newton das richtig erinnert… kann ich mich gar nicht dran erinnern, aber gemacht hab ich's auch.

So, mehr fällt mir erstmal auch nicht ein.

zu 6.: Einmal das was Viprex schon sagte, und dann noch die Frage: Wie können Sie in …. Zeit für einen gerichteten Graphen entscheiden, ob er Zyklen enthält?

O(M+N)wenn ich mich recht erinnere.

Das (vorläufige) Ergebnis hängt im Prüfungsamt aus (Mail kam über den J2005 Verteiler):

Liebe Studierende, die Ergebnisliste der o.a. Klausur hängt anonymisiert im ZBH und im Dept.Informatik, Prüfungsamt Haus A, zur Einsicht aus. Da es sich um vorläufige Ergebnisse handelt, werden sie vorerst ohne Gewähr ausgehängt. Mit freundlichen Grüßen Doris Wilsdorf Doris Wilsdorf-Zamojcin Universität Hamburg (UHH) Fakultät für Mathematik, Informatik und Naturwissenschaften (MIN-Fakultät) Department Informatik Prüfungsamt Vogt-Kölln-Str. 30, 22527 Hamburg Tel: (040)428 83-2211 Fax:(040)428 83-2051 Öffnungszeiten des Dept.-Prüfungsamtes: Mo, Di, Do, Fr. 10 - 12 Uhr Di. 13 - 15 Uhr Mi geschlossen

Ist jemand so lieb und mag hinfahren und ein Foto machen?

Ist jemand so lieb und mag hinfahren und ein Foto machen?

Und es nicht hier reinstellen, sondern z. B. per SMS-Center Matrikelnummern und Noten austauschen. *sicherheitshalber daran erinnert*

Ja, schon klar ;-) Wir sind ja nun nicht mehr die Ersties *g
Aber gut, dass du drauf hinweist! Danke, hatte ich vergessen ;-(

Eben kam noch folgende Mail:

Liebe Studierende, ich weise im Namen von Herrn Prof. Rarey noch darauf hin, dass die Möglichkeit zur Klausureinsicht am 27. Februar 2007 in der Zeit von 10.00 bis 12.00 Uhr im ZBGH, Bundesstr. 43, Abt. AMD, besteht. Unabhängig davon können Sie Ihre Formelsammlungen gegen Vorlage des Studierendenausweises bis zum 31.03.07 während der Sprechstunde, DO 11-12 Uhr im Sekretariat von Prof. Rarey abholen. MFG Doris Wilsdorf Doris Wilsdorf-Zamojcin Universität Hamburg (UHH) Fakultät für Mathematik, Informatik und Naturwissenschaften (MIN-Fakultät) Department Informatik Prüfungsamt Vogt-Kölln-Str. 30, 22527 Hamburg Tel: (040)428 83-2211 Fax:(040)428 83-2051 Öffnungszeiten des Dept.-Prüfungsamtes: Mo, Di, Do, Fr. 10 - 12 Uhr Di. 13 - 15 Uhr Mi geschlossen
Klasse, dann bekommen wir sogar unsere Formelsammlungen wieder. Schade, dass ich nicht wirklich viel drauf geschriebne habe *g

Finde es gut, dass die Prüfer die Klausureinsicht von sich aus anbieten und uns da keine Steine mehr in den Weg legen. Mir ist schon klar, dass wir eh das Recht dazu haben, aber so ists doch deutlich einfacher, finde ich. Gute Entwicklung.

ich frage mich inwiefern die ergebnisse vorläufig sind. die bewertung werden sie wohl kaum im nachhinein verschärfen, oder?

Aus der Prüfungsordnung:

§19

Widerspruchsverfahren

Widersprüche gegen das Prüfungsverfahren und gegen Prüfungsentscheidungen sind, sofern eine Rechtsmittelbelehrung erteilt wurde, innerhalb eines Monats, sonst innerhalb eines Jahres nach Bekanntgabe bei dem oder der Vorsitzenden des Prüfungsausschusses einzulegen. Der Widerspruch sollte schriftlich begründet werden. Hilft der Prüfungsausschuss dem Widerspruch nicht oder nicht in vollem Umfang ab, so ist er dem Widerspruchsausschuss der Universität zuzuleiten.

§22

Einsicht in die Prüfungsakten

Bis zu einem Jahr nach Abschluss der einzelnen Modulprüfungen wird vom Vorsitzenden des Prüfungsausschusses auf schriftlichen Antrag des Prüflings in angemessener Frist Einsicht in seine schriftlichen Prüfungsarbeiten, die darauf bezogenen Gutachten und die Prüfungsprotokolle gewährt, soweit diese nicht bereits ausgehändigt worden sind.

Ich verstehe das so, dass sie vorläufig sind, weil man nach Einsichtnahme eventuell Einspruch einlegen will.