Diskussion der einzelnen Aufgabe der Klausur "Algorithmen und Datenstrukturen" vom SS 2023
Im folgenden wird jede einzelne Aufgaben im Detail diskutiert, in Bezug auf ihren Schwierigkeitsgrad, welches Wissen aus der Vorlesung dazu nötig war und wieviel Nachdenken darüber hinaus noch nötig war. Ab und zu wird erwähnt, dass oft Punkten liegen gelassen wurden. Das war aber im Grunde bei allen Aufgaben der Fall. Unser FAZIT aus dieser Diskussion haben wir vornean gestellt.
FAZIT (aus der Diskussion der Aufgaben unten)
Präambel: Es gibt in jedem Jahrgang Personen, die aufgrund fehlender Voraussetzungen oder weil sie sehr wenig Aufwand investieren nur sehr wenig von dem Stoff verstehen (etwa 20%, eher mehr). Es gibt auch in jedem Jahrgang sehr begabte Personen, die unter fast allen Umständen sehr gut abschneiden (etwa 5%, eher weniger). Um diese beiden extremen Personenkreise soll es hier nicht gehen, sondern um den Personenkreis zwischen diesen beiden Extremen (etwa 75%).
Schematisches Wissen vs. Verständnis: Damit ist Wissen gemeint, dass in der Vorlesung vermittelt wurde, und dass man dann genauso (ohne Variation) auf ein konkretes Beispiel anwenden kann. Das hat gut funktioniert, allerdings gab es auch hier erstaunlich viele Flüchtigkeitsfehler (siehe nächster Punkt). Sobald allerdings eine kleine Variation eingebaut wurde, die das Verständnis prüft, wurde es für viele schwierig. Anhand einiger von den Wahr-Falsch-Frage konnte man sehen, dass es vielen auch schwer fällt zu beurteilen, ob sie etwas verstanden haben oder nicht. Dieser Aspekt des Lernens wurde sehr oft in der Vorlesung thematisiert.
Aufmerksamkeit: Sehr viele Punkte wurden wegen mangelnder Aufmerksamkeit liegen gelassen, selbst bei den schematischen Aufgaben. Dazu gehört: die Aufgabe nicht richtig lesen (die Aufgabenstellungen waren alle sehr kompakt und auch sehr genau), einfache Rechenfehler und einfache Denkfehler. Uns ist nicht ganz klar, woran es liegt: wird einfach nicht die Zeit investiert, bei jeder Rechnung noch einmal nachzuprüfen, stimmmt das auch (das wurde in der Vorlesung immer wieder empfohlen) oder wird die Zeit investiert und die Fehler trotzdem übersehen. Oder reicht tatsächlich die Zeit (die eigentlich großzügig bemessen war) für manche nicht?
Vorlesungsinhalte: Viele der Aufgaben bezogen sich unmittelbar auf Inhalte aus den Vorlesungen, teilweise ohne Variation. Auch bei diesen Aufgaben wurden viele Punkte liegengelassen. Das deutet entweder auch lückenhaftes Lernen hin oder hat auch etwas mit Aufmerksamkeit zu tun, siehe vorheriger Punkt.
Programmieraufgaben: Es gab in der Klausur drei Programmieraufgaben, zwei einfache und eine etwas aufwendigere. Es war ein wesentlicher und großer Teil der Übungen, Code zu schreiben, und zwar in wesentlich größerem Umfang und weitaus schwierigier als für die Klausur. Trotzdem waren die Ergebnisse bei diesen Aufgaben nicht gut. Eine große Gefahr bei den Übungen ist, dass mal so lange Code schreibt, bis die Tests durchlaufen, ohne es wirklich verstanden zu haben. Eine Vermutung ist, dass das bei vielen passiert ist.
Mathematische Beweise: Den meisten Informatikstudierenden fällt das einfach schwer und sie lernen es nie richtig. Das war leider schon immer so. In der Vorlesung wurden viele Anstrengungen unternommen, in dieser Hinsicht zu unterstützen. Das ist zwar ehrenwert, aber wir sind uns sehr unsicher, ob das in der Praxis auch etwas genützt hat.
GANZKURZZUSAMMENFASSUNG: Mit rein schematischem Wissen, genügend Aufmerksamkeit und der Fähigkeit, einfache Programm zu schreiben, konnte man diese Klausur gut bestehen, selbst wenn man die mathematischen Aufgaben alle weggelassen hat. Das rein schematische Wissen hat gut funktioniert, es haperte aber an der Aufmerksamkeit, den Programmierfähigkeiten und zu beurteilen, ob man etwas verstanden hat oder nicht.
Es stellt sich hier die fundamentale Fragen, ob rein schematischem Wissen für ein Universitätsstudium ausreichend ist. Die meisten würden diese Frage wohl mit Nein beantworten. Wenn es beim mathematischen Verständnis hapert (wie bei vielen), sollten zumindest die anderen Bereiche (insbesondere das Programmieren) sitzen.
Aufgabe 1.1 (6 Punkte, Sortieren, wenn ein Element falsch)
Diese Aufgabe ist algorithmisch sehr einfach: die Position des falsch einsortierten Elements ist gegeben, man muss also herausfinden, an welche Stelle es gehört und es dann dahin verschieben. Man kann es entweder dahin "tauschen" (so macht es die Musterlösung), oder man erzeugt ein neues Feld, in das man die Elemente geeignet kopiert.
Diese Aufgabe prüft im Wesentlichen, ob man eine Funktion mit einer einfachen Spezifikation implementieren kann. Zu unserer Überraschung konnten das viele nicht, obwohl die Hälfte der Übungsaufgaben von dieser Art war (für deulich anspruchsvollere Probleme).
Aufgabe 1.2 (6 Punkte, ist HeapSort stabil)
Bei dieser Aufgabe wurden zwei Themen aus verschiedenen Vorlesungen miteinander verbunden (Sortiere und binärer Heap). Sie ist dadurch etwas schwieriger als die übliche Aufgabe. Sehr schwierig ist sie allerdings nicht: man muss es nur anhand eines Beispiels durchspielen (drei Elemente reichen schon), dann sieht man, dass es nicht stabil ist. Das Prinzip, etwas erstmal anhand eines kleinen Beispiels zu verstehen, wurde in der Vorlesung sehr viele Male vorgemacht und auch immer wieder als Lern- bzw. Verständnismethode empfohlen.
Aufgabe 1.3 (8 Punkte, Wahr-Falsch-Fragen zum Sortieren)
Frage 1 ("MergeSort immer Theta(n * log n)"): Einfache Verständnisfrage.
Frage 2 ("Muss die Eingabegröße eine Zweierpotenz sein"): Geschenkt, wenn man das Übungsblatt gemacht hat.
Frage 3 ("Die Vergleiche von MinSort hängen von der Eingabe ab"): Einfach, wenn man sich den Algorithmus (den wir über drei Vorlesungen hinweg genauestens analysiert haben) vergegenwärtigt. Es ergibt sich auch direkt aus der I/E-Analyse in Vorlesung 3.
Frage 4 ("BogoSort vs. HeapSort"): Ein bisschen gemein, weil sich manche nicht gemerkt haben, wie BogoSort funktioniert. Sonst trivial (BogoSort rät die Sortierung und kann auch mal Glück haben).
Aufgabe 2.1 (6 Punkte, I/E-Sequenz für Programm)
Bei dieser Aufgabe gab es keine Tricks, man musste es einfach nur machen. I/E-Sequenzen waren das wesentliche Element von Vorlesung 3. Trotzdem gab es bei dieser Aufgabe viele Abgaben, die sehr oder total falsch waren.
Aufgabe 2.2 (6 Punkte, Wahr-Falsch-Fragen zur O-Notation)
Frage 1 ("n3 + 6n2 + n log n = Theta(0.5 n3)"): Einfach, wenn man O-Notation verstanden hat, die Inhalt einer ganzen Vorlesung war.
Frage 2 ("n! = O(nn)"): Einfach, da sogar n! <= nn, was man leicht sieht und auch in Vorlesung 3 vorkam (da spielt die Fakultät eine wichtige Rolle).
Frage 3 ("log(n!) = o(n·log n)"): Hier musste man ein zentrales Element von Vorlesung 3 (log(n!) >= C·n·log n für eine Konstante C > 0) mit einem zentralen Element von Vorlesung 4 (Verbindung zwischen O, Omega, Theta, o, omega und Grenzwerten) verbinden.
Aufgabe 2.3 (8 Punkte, Transitivität von O und o)
Diese Aufgabe war etwas schwieriger, weil bei der Definition o die Konstante C allquantifiziert ist. Viele haben schon die Definition falsch hingeschrieben, weil sie sie offenbar gar nicht verstanden haben. Dann gab es keine Punkte. Darüberhinaus zeigte sich bei dieser Aufgabe die Schwierigkeit vieler, mathematische Beweise zu führen. Ein, zwei solcher Aufgaben waren bisher bei jeder Klausur dabei.
Aufgabe 3.1 (5 Punkte, Hashing mit offener Adressierung)
Diese Aufgabe war sehr einfach, mit dem einzigen Kniff, dass man sich das Leben hier deutlich einfacher machen kann und sollte, indem man die Hashfunktion zuerst zu h(x) = x - 2 mod 5 vereinfacht. Dass man hier nicht 26 · 1981 - 137 ausrechnen musste, ergab sich aus vielen Hinweisen aus der Vorlesung.
Aufgabe 3.2 (7 Punkte, schlechtes Verkleinerungsregel bei dynamischem Feld)
Wie das im Pinzip geht, war wesentlicher Inhalt von Vorlesung 6 (es stand auf Folie 20). Man musste es nur noch für die konkret in der Aufgabe gegebene Regel ausarbeiten. Dabei wurde sehr viele Fehler gemacht. Zum Beispiel haben sehr viele gesagt, dass das Feld schon nach einen pop wieder verkleinert wird, was einfach nicht so ist, wenn man sie die Zahlen anschaut.
Aufgabe 3.3 (8 Punkte, Wahr-Falsch-Fragen zum Mastertheorem)
Frage 1 ("Summe Ti = O(n + Φ0)"): Einfach, das war genau das Mastertheorem aus der Voesung 6 (Folie 29).
Frage 2 ("Alternative Bedingungen"): Dazu muss man sich den Beweis des Mastertheorems hinschreiben.
Frage 3 ("Frage bezüglich der Bedinungen"): Dito.
Frage 4 ("Erfüllt Ti = O(1) und Φi = i die Bedinungen"): Man muss es einfach nachprüfen, kein besonderer Trick.
Viele haben Frage 2 und Frage 3 falsch beantwortet, weil sie das Mastertheorem nicht richtig verstanden haben. Dadurch haben sie dann 0 Punkte für die ganze Aufgabe bekommen (wobei auch viele noch eine der anderen beiden Aufgaben falsch beantwortet haben). Sie hätten diese beiden Fragen unbeantwortet lassen sollen. Es fehlt offenbar die Wahrnehmung dafür, ob man es verstanden hat oder nicht (eines der größten Hindernisse beim Lernen und Verstehen).
Aufgabe 4.1 (6 Punkte, Blockoperationen im besten und schlechtesten Fall)
Das war die denkbar einfachste Aufgabe, die man zu dem Thema stellen kann.
Aufgabe 4.2 (6 Punkte, minimale und maximale Anzahl Knoten bei Tiefe d)
Eine leichte Variation des Beweises aus Vorlesung 8 (Folie 27). Bei manchen war das Maximum eins zu groß, weil sie die Aufgabe nicht richtig gelesen haben, dafür gab es (nur) einen Punkt Abzug.
Aufgabe 4.3 (8 Punkte, Funktion is_valid_bst)
Hier war die Musterlösung erst falsch. Tatsächlich haben es aber alle, die überhaupt etwas Sinnvolles für diese Aufgabe gemacht haben, so gemacht (bis auf eine Person). Dafür gab es dann nur einen Punkt Abzug, wenn sonst alles korrekt war.
Wir haben diese Aufgabe lange diskutiert und uns die Abgaben nochmal gründlich angeschaut und konnten nicht erkennen, dass die Tatsache, dass die Musterlösung zuerst falsch war (und dadurch die Aufgabe in Richtung dieser ersten Musterlösung gestellt war) zu dadurch bedingten Problemen bei der Bearbeiung geführt hat. Bis auf eine Person, für die wir im Einvernehmen eine gute Lösung gefunden haben.
Aufgabe 5.1 (5 Punkte, 4 Operationen auf einem binären Heap ausführen)
Die denkbar einfachste Aufgabe zu dem Thema. Trotzdem haben hier viele Leute Punkte liegen lassen.
Aufgabe 5.2 (10 Punkte, Funktion zum mergen von k Listen)
Die aufwendigste von den Programmieraufgaben in dieser Klausur. Der Algorithmus wurde in Vorlesung 12 (Folie 12) erklärt und sogar anhand eines Beispiels genau vorgemacht. Dass es in der Klausur eine etwas aufwendigere Programmieraufgabe (und eine etwas schwieriger mathematische Aufgabe) gibt, ist normal.
Aufgabe 5.3 (5 Punkte, Teilpfad von kürzestem Pfad ist auch kürzester Pfad)
Das wurde 1-1 in Vorlesung 10 (Folie 26) erklärt. Die Aussage steht auf den Folien, der Beweis dazu allerdings nicht (wurde allerdings in der Vorlesung erklärt). Dass auch bei dieser Aufgabe viele Punkte liegengelassen wurden, deutet daraufhin, dass viele die Vorlesungen nicht (oder zumindet nicht aufmerksam) verfolgen. Aber selbst beim Lernen nur aus den Folien, sollte man natürlich Aussagen, die auf den Folien stehen, nicht einfach hinnehmen.