.svg)
Laufzeit, Korrektheit, Datenstrukturen: So lernst du Algorithmen und Datenstrukturen in 5 Schritten und gehst vorbereitet in die AuD-Klausur.
"Die AuD-Klausur fragt nicht, ob du programmieren kannst, sondern ob du Laufzeit und Korrektheit begruenden kannst."
Du kannst programmieren, aber die AuD-Klausur fragt etwas anderes ab: warum dein Verfahren korrekt ist und wie schnell es bei einer Million Datensätzen noch läuft. Genau daran scheitern Klausuren, nicht am fehlenden Code. Algorithmen und Datenstrukturen ist ein Beweis- und Analysefach mit Programmieranteil — und es lässt sich systematisch lernen, wenn du die drei Anforderungen trennst: Datenstruktur wählen, Laufzeit begründen, Korrektheit zeigen. Dieser Plan führt dich in fünf Schritten dorthin.
Ein Blick in die Modulbeschreibungen zeigt, was wirklich geprüft wird. Das Modul „Algorithmen und Datenstrukturen" an der Universität zu Lübeck schließt mit einer 90-minütigen Klausur ab, die 100 Prozent der Modulnote ausmacht; inhaltlich stehen dort Sortierverfahren samt Komplexitätsanalyse, Heaps, Prioritätswarteschlangen, Graphen sowie dynamische Programmierung und gierige Verfahren an Optimierungsproblemen wie dem Rucksackproblem. An der Universität Marburg nennt das Basismodul als Kompetenzziel ausdrücklich, „Aufwandsbeurteilung und -abschätzung zu betreiben" — nicht, Programme zu schreiben.
Das erklärt die typische Erfahrung: Wer die Übungsblätter mit Code löst und dann aufhört, hat den kleineren Teil der Arbeit erledigt. In der Klausur steht selten „Implementiere X", sondern „Gib die Laufzeit in O-Notation an und begründe sie" oder „Zeige, dass der Algorithmus terminiert".
Der zweite Punkt ist der Zeitrahmen. Für ein 6-Credit-Modul rechnet die Hochschule Niederrhein mit rund 150 Stunden im Semester, also etwa acht Stunden pro Woche, davon nur etwa 30 Stunden für die eigentliche Klausurvorbereitung. In Lübeck sind es bei 8 ECTS 240 Stunden, davon 25 Stunden Prüfungsvorbereitung. Die Botschaft ist in allen Modulhandbüchern dieselbe: Das Fach wird während des Semesters bestanden, nicht in der Woche davor. Wenn du im Erstsemester noch beim Programmieren-Einstieg stehst, hilft dir zuerst der Leitfaden zum Programmieren lernen in den ersten zwei Semestern — AuD baut darauf auf.
Der häufigste Lernfehler ist, Datenstrukturen als Liste von Definitionen durchzugehen. In der Klausur wirst du aber gefragt, welche Struktur ein Problem löst. Sortiere deshalb von Anfang an nach Einsatzzweck: Welche Operation muss schnell sein? Dann ergibt sich die Struktur fast von selbst.
| Was schnell sein muss | Passende Struktur | Typische Laufzeit |
|---|---|---|
| Zugriff über einen Index | Array / dynamisches Array | Zugriff O(1), Einfügen in der Mitte O(n) |
| Einfügen und Löschen an bekannter Position | Verkettete Liste | Einfügen/Löschen O(1), Suchen O(n) |
| Zuletzt abgelegtes Element zuerst | Stack | push/pop O(1) |
| Zuerst abgelegtes Element zuerst | Queue | enqueue/dequeue O(1) |
| Suche über einen Schlüssel | Hashtabelle | im Mittel O(1), im schlechtesten Fall O(n) |
| Sortierte Schlüssel, Bereichsanfragen | Balancierter Suchbaum (AVL, Rot-Schwarz) | Suchen/Einfügen/Löschen O(log n) |
| Immer das Minimum zuerst | Heap / Prioritätswarteschlange | Einfügen O(log n), Minimum lesen O(1) |
Lege dir zu jeder Struktur einen kurzen Steckbrief an: Operationen mit Laufzeit, Speicherbedarf, eine Situation, in der sie die richtige Wahl ist, und eine, in der sie die falsche ist. Dieser letzte Punkt ist der wertvollste — er ist genau die Begründung, die in der Klausur Punkte bringt. Wenn du solche Steckbriefe aus deinem Vorlesungsskript ziehst, kannst du sie dir in Learnboost als Karteikarten erzeugen lassen und musst sie nicht abtippen.
Der gleiche Zugriff funktioniert bei den Sortierverfahren. Statt vier Algorithmen einzeln auswendig zu lernen, lerne die Unterscheidungsmerkmale, nach denen die Klausur fragt:
| Verfahren | Laufzeit im schlechtesten Fall | Merkmal |
|---|---|---|
| Insertionsort | O(n²) | sehr schnell bei fast sortierten Daten (O(n)) |
| Mergesort | O(n log n) | stabil, braucht zusätzlichen Speicher |
| Quicksort | O(n²) | im Mittel O(n log n), arbeitet in-place |
| Heapsort | O(n log n) | in-place, aber nicht stabil |
Die O-Notation beschreibt eine obere Schranke für das Wachstum einer Funktion, wenn die Eingabe groß wird. Praktisch heißt das: konstante Faktoren und Terme niedrigerer Ordnung fallen weg, übrig bleibt der dominierende Term. Aus 3n² + 40n + 500 wird O(n²).
Arbeite beim Analysieren immer in dieser Reihenfolge:
Drei Fehler kosten regelmäßig Punkte. Erstens die Verwechslung von O und Θ: O ist nur eine obere Schranke, ein linearer Algorithmus liegt formal auch in O(n²) — wenn nach der genauen Größenordnung gefragt ist, ist Θ gemeint. Zweitens der Griff zum Worst Case, wo die Aufgabe nach amortisierter Laufzeit fragt: Ein dynamisches Array verdoppelt sich gelegentlich in O(n), über viele Einfügungen gemittelt kostet eine Einfügung aber O(1). Drittens vergessene Speicherkosten — Mergesort ist nur mit dem Hinweis auf den zusätzlichen Speicher vollständig beschrieben.
Der Beweisteil schreckt viele ab, ist aber der am stärksten formalisierte Teil des Fachs: Es gibt zwei Muster, und beide folgen einem festen Schema.
Die Schleifeninvariante ist eine Aussage über den Zustand, die bei jedem Schleifendurchlauf gilt. Du zeigst sie in drei Teilen: Initialisierung (die Aussage gilt vor dem ersten Durchlauf), Erhaltung (gilt sie vor einem Durchlauf, dann auch danach) und Terminierung (beim Verlassen der Schleife liefert die Aussage das gewünschte Ergebnis). Bei Insertionsort lautet die Invariante etwa: Der Teilbereich links vom aktuellen Index enthält dieselben Elemente wie zu Beginn, jetzt aufsteigend sortiert.
Die vollständige Induktion nutzt du bei rekursiven Verfahren: Induktionsanfang für den Basisfall, Induktionsschritt unter der Annahme, dass die rekursiven Aufrufe auf kleineren Eingaben korrekt arbeiten. Dass die Rekursion überhaupt endet, zeigst du separat über ein Maß, das bei jedem Aufruf echt kleiner wird und nicht unter den Basisfall fallen kann.
Das Beweishandwerk selbst — Aussage sauber formulieren, Schritte begründen statt behaupten — ist dasselbe wie in der Mathe-Vorlesung. Wenn dir das schwerfällt, lohnt sich der Umweg über den Ratgeber zum Mathe lernen im Studium mit Übungsblättern und Beweisen, bevor du dich an AuD-Beweise setzt.
Übungsblätter sind in vielen Studiengängen nicht optional. In Marburg verlangt die Studienleistung mindestens 50 Prozent der Punkte aus den wöchentlichen Übungsaufgaben plus die mündliche Präsentation von mindestens zwei Lösungen. Das ist kein Hindernis, sondern der eigentliche Lernweg: Die Hochschule Niederrhein hält in ihrer Veranstaltungsbeschreibung fest, dass gute Mitarbeit in den Übungen die Vorbereitungszeit für die Prüfung verkürzt und die Bestehenschance erhöht.
Entscheidend ist, was nach der Korrektur passiert. Gehe jedes zurückgegebene Blatt einmal durch und ordne jeden Fehler einer von drei Kategorien zu: Verständnisfehler (du hast das Konzept nicht verstanden), Begründungsfehler (Ergebnis richtig, Herleitung fehlt) und Flüchtigkeitsfehler. Nur die erste Kategorie erfordert erneutes Lernen, die zweite ist reine Darstellungssache — und sie ist in AuD-Klausuren der häufigste Punkteverlust.
Rechne Aufgaben danach ohne Lösung nach. Sich selbst abzufragen statt noch einmal zu lesen ist der besser belegte Weg: Roediger und Karpicke zeigten 2006 in Psychological Science, dass Abrufen den Langzeitbehalt deutlich stärker verbessert als wiederholtes Lesen. Wie du dieses Prinzip planvoll einsetzt, steht im Ratgeber zu Active Recall in vier Schritten; die passenden Abstände dazu liefert der Ratgeber zu Spaced Repetition und Wiederholungsintervallen.
Altklausuren kommen zuletzt, etwa drei bis vier Wochen vor dem Termin. Ihr Wert liegt weniger in den Aufgaben selbst als im Antwortformat: Du siehst, wie ausführlich eine Begründung sein muss und wie die Punkte verteilt sind. Wie du sie systematisch auswertest, beschreibt der Ratgeber zum Altklausuren nutzen in fünf Schritten. Aus deinen eigenen Übungsblättern und Skripten kannst du dir in Learnboost zusätzlich Probeklausuren erzeugen lassen, um unter Zeitdruck zu üben statt nur zu lesen.
Ein realistischer Rhythmus für das Semester: wöchentlich das Übungsblatt und direkt danach die Fehlerauswertung, alle zwei Wochen ein kurzer Durchgang durch die Datenstruktur-Steckbriefe, ab vier Wochen vor der Klausur zusätzlich eine Altklausur unter Zeitbedingungen. Wie du das in einen Gesamtplan einbettest, zeigt der 6-Wochen-Zeitplan für die Klausurphase.
Trenne die drei Anforderungen des Fachs und übe sie getrennt: Datenstrukturen nach Einsatzzweck statt nach Definition, Laufzeit in vier festen Schritten hergeleitet, Korrektheit über Invariante oder Induktion nach Schema. Halte die Übungsblätter wöchentlich durch und werte jeden Fehler nach Kategorie aus — das ist der Teil, der die Note macht. Wenn du deine Skripte und Übungsblätter in Learnboost für die Klausurvorbereitung hochlädst, bekommst du daraus Karteikarten, Zusammenfassungen und Probeklausuren, mit denen du den Abrufteil abdeckst — die Beweise bleiben deine Arbeit.
Das Fach gilt als eines der anspruchsvollsten Pflichtmodule im Informatikstudium, weil es Programmierung, Mathematik und Beweisführung verbindet. Schwer wird es vor allem dann, wenn man es wie eine Programmiervorlesung behandelt und den Analyse- und Beweisteil erst kurz vor der Klausur angeht. Wer die Übungsblätter wöchentlich mitmacht und Fehler direkt auswertet, verteilt die Arbeit über das Semester und kommt mit deutlich weniger Prüfungsstress aus.
Die Modulhandbücher geben dafür klare Richtwerte: Die Hochschule Niederrhein rechnet bei 6 Credit Points mit rund 150 Stunden im Semester, also etwa acht Stunden pro Woche. In Lübeck sind es bei 8 ECTS insgesamt 240 Stunden, davon nur 25 Stunden reine Prüfungsvorbereitung. Die Zahlen zeigen, dass das Fach über das Semester bestanden wird und nicht in der Woche vor der Klausur.
In der Regel nicht. Geprüft wird meist, ob du die passende Datenstruktur auswählen, die Laufzeit in O-Notation herleiten und die Korrektheit begründen kannst. Sinnvoller als auswendig gelernter Code ist deshalb, zu jedem Verfahren die Idee, die Laufzeit in allen Fällen und die typischen Einsatzszenarien parat zu haben — und Pseudocode lesen und schreiben zu können.
O beschreibt nur eine obere Schranke für das Wachstum: Ein linearer Algorithmus liegt formal auch in O(n²), weil n² eine gültige obere Schranke ist. Θ beschreibt dagegen die exakte Größenordnung, also obere und untere Schranke zugleich. Wenn eine Aufgabe nach der genauen Laufzeit fragt, ist Θ gemeint — diese Verwechslung kostet in Klausuren regelmäßig Punkte.
Für Schleifen nutzt du eine Schleifeninvariante und zeigst sie in drei Teilen: Initialisierung vor dem ersten Durchlauf, Erhaltung über einen Durchlauf hinweg und Terminierung beim Verlassen der Schleife. Für rekursive Verfahren nimmst du vollständige Induktion mit Basisfall und Induktionsschritt. Dass die Rekursion endet, zeigst du zusätzlich über ein Maß, das bei jedem Aufruf echt kleiner wird.
