Diese Vorlesung ist hauptsächlich eine Einführung in Algorithmen, Datenstrukturen, und allgemeine Algorithmentechniken. Die Übungsaufgaben werden teils theoretisch, teils praktisch sein, wobei die praktischen Aufgaben mit Python (einer very-high-level Programmiersprache) gelöst werden sollen.
Aus dem Inhalt:
Woche | Thema |
---|---|
1. | Organisation, Typsysteme (dynamic / static / inferred), Algorithmenbegriff, Einführung in Python (Basics) |
2. | Strings und Arrays, Funktionen, Module, Klassen in Python; höhere Datenstrukturen allgemein (Verbünde, Arrays); Einfache Datenstrukturen 1 (Verbund, Array, Listen) |
3. | Einfache Datenstrukturen 2 (Stack und Queue, jeweils mit Implementierung auf einem Array bzw. einer Liste) plus Anwendungen (Postfix-Auswertung, Infix-nach-Postfix-Konvertierung, Call-Stack) |
4. |
Such-Algorithmen (lineare Suche, Binärsuche, exponentielle Suche,
Interpolation Search, Golden Section Search) Korrektheitsbeweise mit Schleifeninvarianten, Komplexitätsanalyse mit Groß-O, Teil 1 (Kostenmaße, Beispiele, Wachstum von Funktionen, Groß-Omega, Groß-O-Kalkül) |
5. |
Komplexitätsanalyse mit Groß-O, Teil 2 (wichtige Funktionenklassen,
Bestimmung des Zeitaufwands mit Groß-O, average-case Komplexität,
average-case Laufzeit, Maximum Subarray Problem, Kadane's Algorithmus); Bäume (Definitionen, Eigenschaften, Anwendungen, Traversierung); Sortieren 1 (Einleitung) |
6. | Sortieren 2 (Bubblesort, Insertion Sort, Selection Sort, Quicksort, Heapsort, Mergesort, Introsort) |
7. |
Sortieren 3 (Untere Schranke für Worst-Case; lineare Sortierverfahren, e.g.,
Counting sort, Bucket-Sort, Radix-Sort); Hashing (Begriffe, Hash-Funktionen, Universelles Hashing, Kollisionswahrscheinlichkeit, Chaining, Lineares Sondieren, Quadratisches Sondieren, Double Hashing) |
8. | Divide-and-Conquer (Multiplikation mit Karatsuba/Ofman; Schnelle Matrix-Multiplikation; das Closest-Pairs Problem [closest points]) |
9. | Dynamische Programmierung (Matrix Chain Multiplication Problem, die Technik der dynamischen Programmierung, das Rucksack-Problem (knapsack problem), längste gemeinsame Teilfolge (longest common subsequence), Memoisierung, Zusammenfassung) |
10. | Greedy-Algorithmen (Activity-Selection-Problem, fraktionales Knapsack-Problem, abstrakte Definition von Greedy-Algorithmen, Scheduling, Huffman-Kodierung, arithmetische Kodierung) |
11. |
Backtracking (4-Farben-Problem, 8-Damen-Problem); Precomputation (Definition, Vorgänger im Baum, Polynomauswertung an äquidistanten Stellen, String Matching, weitere Anwendungen von Precomputation) |
12. |
Search Trees (binary search trees, AVL-Bäume,
optimale Suchbäume, B-Bäume, PATRICIA trees, Anwendung Routing); Van-Emde-Boas-Trees (Einführung) |
13. |
Van-Emde-Boas-Trees (Datenstruktur, Operationen Insert und FindSuccessor,
Laufzeit & Platzbedarf); Anwendungen von P-Queues; der A*-Algorithmus; Numerische Robustheit (Eigenschaften der Floating-Point-Darstellung, relativer Fehler, ULP, Maschinen-Epsilon, numerisch robuster Algorithmus für die Standardabweichung) |
Literatur zu Python ist online ausreichend verfügbar; einige Links finden Sie unten.
Eine "Schein"-Klausur findet nicht statt.
|
Wer nicht bestanden hat kann sich zur Nachprüfung anmelden. Diese wird mündlich sein.
Termin für die Nachprüfung: 27.1.2011
Wer sich anmelden möchte geht folgendermaßen vor:
Hier finden Sie eine Musterlösung zur Klausur.
Auch bei der Scheinvergabe wirkt sich eine aktive Teilnahme an den Übungen in Grenzfällen positiv aus.
|
|