Lernplan: 9. November 2026 – 31. Januar 2027

Zwölf Wochen bis zur mündlichen Prüfung (ca. Februar). Bei CompGeo geben die Praktikumsfristen den Takt vor: Jede Aufgabe muss man dem Professor vorstellen und Zeile für Zeile erklären können. Wer die Aufgaben ehrlich durchdringt, hat einen großen Teil der Prüfung schon gelernt. Daneben läuft die Vorlesung mit §6–§9 weiter, und ältere Kapitel werden kurz wiederholt.

Zum Abhaken

Die Wochen und die Abgabetermine stehen auch im Lernplan-Kalender, zusammen mit den anderen Fächern.

Annahmen

• Abgaben laut 📄 00-intro.pdf: A2 am 23.11., A3 am 21.12., A4 am 18.01. (A1 war am 2.11.). Was im Moodle steht, hat Vorrang.
• Welches Kapitel in welcher Woche dran ist, ist geschätzt aus dem Folienumfang (§6: 38, §7: 37, §8: 23 Folien; §9 gibt es noch nicht). Verschiebt sich die Vorlesung, verschiebt sich nur die Spalte „Neu“.
• Weihnachtspause etwa 21.12.–6.1. ohne Vorlesung.
• Das Skript reicht bis §5. Für §6–§9 sind die Folien verlinkt, bis die Skriptseiten dazukommen.
• 20 h Arbeit pro Woche und jeden zweiten Samstag unterwegs, siehe Kalender.

Der Wochenrhythmus

Rund 3–4 Stunden pro Woche plus die Zeit für den Praktikumscode. Die Tage passen zum Numa-Rhythmus.

Wann	Was	Dauer
Mo	Vorlesung und Praktikum	3 h
Mi oder Do	Nacharbeiten: Folien der Woche durchgehen, jeden Algorithmus einmal an einem eigenen Beispiel von Hand durchspielen (5–8 Punkte, Skizze!)	1–1.5 h
Fr	Praktikumscode: kleine Schritte, jede Woche etwas, damit die Abgabe nicht in die letzte Nacht rutscht	1–2 h
So	Wiederholung: 4–6 Prüfungsfragen aus älteren Kapiteln laut, mit Skizze	20–30 min

Freie Samstage sind wie bei Numa Puffer, vor allem in den Wochen vor einer Abgabe.

Das Schema für jeden Algorithmus

Problem → Idee → Datenstrukturen → Ablauf → Laufzeit → Speicher → Sonderfälle → untere Schranke. Beim Nacharbeiten jeden neuen Algorithmus einmal in genau diesem Schema aufschreiben. Die Zettel sind am Ende das Prüfungsmaterial (siehe Hints).

Überblick

Woche	Datum	Neu (Vorlesung)	Praktikum	Wiederholung
1	9.–15.11.	§6 Punktlokalisierung, Trapezzerlegung	A2 anfangen	Kap. 1–2
2	16.–22.11.	§6 Suchstruktur, randomisiert	A2 fertig, Vorstellen üben	Kap. 3
3	23.–29.11.	§7 Art Gallery, monotone Zerlegung	A2 Abgabe 23.11., A3 anfangen	Kap. 2
4	30.11.–6.12.	§7 Triangulierung monotoner Polygone	A3 Grundgerüst	Kap. 4
5	7.–13.12.	§8 Konvexe Hülle in 3D	A3 Anfragen	Kap. 5
6	14.–20.12.	§8 Analyse	A3 fertig	Kap. 6
7	21.–27.12.	Pause	A3 Abgabe 21.12.	Großwiederholung §1–§3
8	28.12.–3.1.	Pause	A4 Grundgerüst	Großwiederholung §4–§5
9	4.–10.1.	ggf. Rest §8	A4 Kernalgorithmus	Kap. 6–7
10	11.–17.1.	§9 Triangulierung von Punktwolken	A4 fertig	Kap. 8
11	18.–24.1.	§9 Rest	A4 Abgabe 18.1.	Kap. 1–5 schnell
12	25.–31.1.	letzte Vorlesung	–	Probeprüfungen

Woche für Woche

Woche 1 (9.–15.11.): Punktlokalisierung

• Vorlesung §6 nacharbeiten: Problem (in welcher Fläche liegt $q$?), Trapezzerlegung (📄 06-point-location.pdf). Warum hat jedes Trapez höchstens zwei vertikale Seiten?
• Eine Trapezzerlegung für 3 Segmente von Hand zeichnen.
• A2 anfangen: iso-orientierte Segmente noch einmal lesen, Ereignisse und Sweep-Status im Code anlegen.
• Wiederholung: Prüfungsfragen Kapitel 1 und Kapitel 2. A1 ist gerade frisch, also Graham und Jarvis einmal laut erklären.

Woche 2 (16.–22.11.): Suchstruktur

• §6: Suchstruktur (DAG mit $x$- und $y$-Knoten), randomisiert inkrementeller Aufbau, erwartete Größe $O(n)$ und Anfrage $O(\log n)$.
• Ein Segment in eine kleine Trapezzerlegung einfügen und die Suchstruktur mitführen.
• A2 fertig. Sonderfälle testen: gemeinsame Endpunkte, gleiche $x$-Koordinaten.
• A2 vorstellen üben: Ablauf, Laufzeit $O(n\log n+k)$, welche Annahme über allgemeine Lage, wie im Code gelöst.
• Wiederholung: Prüfungsfragen Kapitel 3.

Woche 3 (23.–29.11.): Art Gallery

• Abgabe A2 am Montag, 23.11.
• §7: Art-Gallery-Problem, $\lfloor n/3\rfloor$ Wächter über die 3-Färbung (📄 07-polygon.pdf). Den Beweis an der Tafel können.
• Monotone Zerlegung: Knotentypen (Start, End, Split, Merge, regulär) an einem eigenen Polygon bestimmen.
• A3 anfangen: 2d-Baum lesen, Aufbau mit Median planen.
• Wiederholung: Kapitel 2 (untere Schranke $\Omega(n\log n)$ an der Tafel).

Woche 4 (30.11.–6.12.): Triangulierung von Polygonen

• §7: Triangulierung monotoner Polygone in $O(n)$, insgesamt $O(n\log n)$. Ein monotones Polygon mit 8 Ecken von Hand triangulieren.
• A3: Aufbau des 2d-Baums läuft, an kleinen Beispielen gegen Handrechnung prüfen.
• Wiederholung: Prüfungsfragen Kapitel 4.
• Prüfungsanmeldung im Dezember im Blick behalten.

Woche 5 (7.–13.12.): Konvexe Hülle in 3D

• §8: Komplexität in 3D (Euler: $\le 3n-6$ Kanten, $\le 2n-4$ Facetten), randomisiert inkrementeller Algorithmus, Konfliktgraph (📄 08-ch.pdf).
• Verbindung zu §2 und §5 herstellen: Delaunay = untere Hülle der auf das Paraboloid gehobenen Punkte.
• A3: Bereichsanfrage, Laufzeit $O(\sqrt n+R)$ im Code nachvollziehbar.
• Wiederholung: Prüfungsfragen Kapitel 5.

Woche 6 (14.–20.12.): Analyse 3D-Hülle

• §8: erwartete Laufzeit $O(n\log n)$, Rückwärtsanalyse.
• A3 fertig. Sonderfälle: gleiche Koordinaten (strikte Vergleiche!), leere Anfragen.
• A3 vorstellen üben: Aufbau, Anfrage, Rekursion $Q(n)=2+2Q(n/4)$.
• Wiederholung: §6 Punktlokalisierung.

Woche 7 (21.–27.12.): Großwiederholung §1–§3

• Abgabe A3 am Montag, 21.12.
• Spickzettel Kapitel 1–3: jede Zeile in eigenen Worten.
• Alle Prüfungsfragen zu Kapitel 1–3 laut, Fragen mit Zögern markieren.
• Beweise an der Tafel: untere Schranke konvexe Hülle, Graham amortisiert $O(n)$.

Woche 8 (28.12.–3.1.): Großwiederholung §4–§5

• Prüfungsfragen Kapitel 4–5 laut.
• Beweise: kd-Baum $O(\sqrt n+R)$, Range-Tree, Voronoi $\le 2n-5$ Knoten, Fortune $O(n\log n)$.
• A4 Grundgerüst: randomisierte Delaunay-Triangulierung lesen, Datenstruktur für Dreiecke und Nachbarn anlegen.
• Liste „kann ich noch nicht“ anlegen.

Woche 9 (4.–10.1.): Delaunay im Code

• Ggf. Rest §8 in der Vorlesung.
• A4 Kernalgorithmus: Punkt einfügen, Kanten legalisieren (Umkreistest).
• Wiederholung: §6 und §7 (Trapezzerlegung und monotone Zerlegung je einmal skizzieren).

Woche 10 (11.–17.1.): Punktwolken

• §9 Triangulierung von Punktwolken nacharbeiten (Folien kommen noch).
• A4 fertig. Zufällige Reihenfolge der Punkte, Sonderfall vier Punkte auf einem Kreis.
• A4 vorstellen üben: warum randomisiert, erwartete Laufzeit, Korrektheit (Satz 11).
• Wiederholung: §8.

Woche 11 (18.–24.1.): Letzte Abgabe

• Abgabe A4 am Montag, 18.1.
• §9 Rest.
• Kapitel 1–5 im Schnelldurchlauf: pro Kapitel ein Algorithmus im Schema an der Tafel.
• Einstiegsthema wählen (falls es eins gibt) und in 5 Minuten an der Tafel aufbauen üben.

Woche 12 (25.–31.1.): Probeprüfungen

• Zwei bis drei Probeprüfungen à 40 min mit Kommiliton:innen aus der Fragenliste.
• Querverbindungen, die gern gefragt werden:
  • Sweep-Line in §3 ↔ Fortune in §5 ↔ monotone Zerlegung in §7
  • randomisiert inkrementell in §5 ↔ §6 ↔ §8, immer mit Rückwärtsanalyse
  • konvexe Hülle in 2D (§2) ↔ 3D (§8) ↔ Delaunay als gehobene Hülle (§5)
  • untere Schranken $\Omega(n\log n)$ durch Reduktion von Sortieren
• Alle vier Praktikumsaufgaben noch einmal je 5 Minuten vorstellen.
• Ab Februar bis zum Termin: täglich 30–60 min Fragen laut, sonst nichts Neues mehr.

Wenn es mal nicht klappt

• Abgabe wird knapp? Wiederholung dieser und der nächsten Woche streichen, die Abgabe hat Vorrang. Lieber eine saubere, erklärbare Lösung als eine mit allen Extras.
• Arbeitswoche zu voll? Nacharbeiten nicht schieben (es geht nur, solange die Vorlesung frisch ist), den Code auf den nächsten freien Samstag.
• Stoff fehlt hier noch? Skriptseiten zu §6–§9 können im gleichen Stil ergänzt werden, sobald die Vorlesung da ist.