Ich packe in meinen Koffer:
- Formale Definition O-Kalkül (mhm, kann ich inzwischen eigentlich auch so)
- Reihen: Geometrische und Harmonische (könnte bei Rekurrenzgleichungen helfen oder um die Anzahl der Knoten irgendeines Baumes zu bestimmen)
- Master-Theorem
- [img]
http://mokrates.de/cgi-bin/texstring?A%20%5Cleq_p%20B[/img] bedeutet: A wird reduziert auf B (das verwechsel ich gerne)
- Selection Sort, Insertion Sort, Bubble Sort, Merge Sort, Heap Sort, Quick Sort, Counting Sort, Radix Sort: Grobe Funktionsweise (so viel, dass ich mich an Hand der Beschreibung wieder dran erinnere) und Laufzeiten (möglichst so, dass ich weiß, warum)
- Suchproblem: LINEAR-, BINARY- und EXPONENTIAL-SEARCH (Namen plus Laufzeiten)
- Auswahlproblem: TRIVIAL-, SORT- und RAND-SELECT (Namen plus Laufzeiten)
- Hashing: Laufzeiten für erfolglose Suche bei Verkettung = O(1 + alpha) und bei offener Addressierung mit uniformem doppeltem Hashing = O(1/(1 - alpha))
- BFS und DFS: Funktionsweise (auch: was sind pi[v] und d[v]) und Laufzeit
- Topologische Sortierung: Die beiden Funktionsweisen, die wir kennen
- MST-KRUSKAL und MST-PRIM: Funktionsweise und Laufzeit
- kürzeste Pfade: Funktionsweise von BELLMAN-FORD, DAG-SHORTEST-PATHS und DIJKSTRA mit Laufzeiten
So, das ist das, was ich mir bisher notiert habe, ich weiß noch nicht, was ich davon alles auf meinen Zettel übernehme, aber wenn ich klein genug schreibe… mal schaun. Erstmal muss ich aber noch die Folien zu Ende abgrasen, ich wollte mir noch ein paar Probleme aus NPC aufschreiben (so, dass ich den Namen und die Bedeutung kenne) und vielleicht was zu B&B.
/Edit: Achja, die Rot-/Schwarz-Eigenschaften natürlich auch.
@ethrandil: Nette Übersicht. Achtung: Bei INSERTION- und BUBBLE-SORT ist die Laufzeit allgemein O(N^2), Theta(N^2) ist sie nur im Worst Case. Beide haben einen Best Case von Theta(N). (Rarey will das in den Folien nochmal überarbeiten.)
