FB18 - Das Forum für Informatik

fb18.de / Bachelorstudieng / PM Praktische Informatik

Gedaechtnisprotokoll der 1. AD Klausur

Gedaechtnisprotokoll der 1. AD Klausur 2010-03-17 17:31
Anonymer User
Gibt es irgendwo ein Gedaechtnisprotokoll von der ersten AD Klausur?

Hab beim GProt und Wiki nix gefunden von diesem Jahr.

RE: Gedaechtnisprotokoll der 1. AD Klausur 2010-03-18 22:14
Anonymer User
Paar Fragen, die mir noch einfallen:

Welche der folgenden Bäume sind keine AVL-Bäume. 3 Gegeben, +1 für richtig, -1 für falsch. Ein Baum war kein AVL-Baum, da nicht balanciert und der andere war nicht mal ein Suchbaum, obwohl balanciert.

Geben Sie eine Funktion an, die in o(log(n)) liegt. Gab noch ein paar weitere Fragen dieser form, sowas wie: Wenn f element o(g), gilt dann auch g element kleinomega(f)? Das richtige Kreuz (Ja/Nein) brachte Punkte sowie eine zusätzliche Begründung noch weitere.

Es war ein Heap grafisch aufgemalt gegeben, dazu sollte man die Arraydarstellung aufschreiben. Dann das Wurzelelement entfernen und den Heap reorganisiert hinmalen und auch in Arraydarstellung angeben.

Dann war bei einer Aufgabe ein Graph gegeben und man sollte einen Spannbaum mit Prim bestimmen und beschreiben, wie man vorgeht.

Eine weitere Frage war, ob das Problem, zu entscheiden, ob ein Graph einen Kreis hat, np-vollständig ist. Wieder Ja/Nein mit Begründung.

Es gab 2 Aufgaben zum Mastertheorem (war im Anhang gegeben) wo man die Komplexität bestimmen musste. Dazu gab es noch eine Aufgabe, wo man die Komplexität mit der Substitutionsmethode bestimmen musste. Das sollte ohne Summenzeichen sein, die geometrische Reihe war aber im Anhang gegeben. An die einzelnen Rekurrenzgleichungen erinnere ich mich nicht mehr.

Bei einer anderen Aufgabe waren 3 Algorithmen gegeben, Counting Sort, Heap Sort und Merge Sort und man sollte ankreuzen, welche davon stabil sind. 2 Punkte, +1 für richtig, -1 für falsch.

Auch waren ein paar Algorithmen gegeben und dort war dann nach der Komplexität gefragt.

Zum Schluss gab es noch paar Fragen zur NP-Vollständigkeit, wobei ich mich an die nicht mehr genau erinnere. Angenommen werden sollte dabei, dass P != NP gilt.

Also in der Klausur kam so ziemlich genau das dran, was angekündigt wurde.

RE: Gedaechtnisprotokoll der 1. AD Klausur 2010-03-19 07:01
ElFitz
Es kam auch eine Rekurrenzgleichung dran, die man durch Stubstitution lösen sollte.

Eine Reduktionsaufgabe eines NP-vollständigen Problems, die so ähnlich war, wie die in der Übung … etwas leichter.