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 | Übungs- aufgaben |
Literatur |
|---|---|---|---|
| 1. | Orga, Einleitung | ||
| 2. | Typsysteme (dynamic typing / static typing, weakly typed / strongly typed), Python Basics, höhere Python-Konstrukte (Lists, Tupel, Dicts, Funktionen, Klassen) | ||
| 3. | Einfache Datenstrukturen (Array, Liste, Multi-Liste), Stack (elementare Operationen darauf, Implementierung mittels Array und Liste, Postfix-Auswertung, Infix to Postfix, Klammerausrücke), Queue (Operationen, Implementierung mittels Liste und Array), Suchalgorithmen 1 (lineare Suche, binäre Suche) | ||
| 4. | Suchalgorithmen 2 (Beweis für average case der Binärsuche, exponential search, interpolation search, golden section search); Schleifeninvarianten (Definition, Beispiele); Einführung in die Komplexitätsanalyse (Kostenmaße, Funktionenklassen, Groß-O-Notation, Groß-O-Kalkül, Einfache Beziehungen, Problemgröße und Rechenzeit, wichtige Funktionenklassen) | ||
| 5. | Komplexitätsanalyse 2 (Beispiele zur Bestimmung des Aufwandes mittels Groß-O, Average-Case-Komplexität, Beispiel dazu mittels serieller Addierer, Maxsummen-Problem als Beispiel für die Scanline-Technik); Einführung in Bäume (Definition, einfache Eigenschaften, Binärbäume, Auswertung von Parse-Trees, preorder, postorder, inorder, breadth-first search, threaded trees, Visitor Pattern); Sortieren 1 (Klassifikation, Bubblesort mit Aufwand und Korrektheit, Quicksort, Implementierung in Python, Visualisierung, Algo-Animationen, Korrektheitsbeweis der Partitionierung, Worst-Case- und Best-Case-Laufzeit, der Heap als Datenstruktur) | ||
| 6. | Sortieren 2 (Heapsort, ausführliches Beispiel zu BuildHeap im Array, Mergesort); Himmelfahrt | ||
| 7. | Sortieren 3: Untere Schranke für Sortierverfahren im worst-case, und im average-case, Counting-Sort, Bucket-Sort, MSD-Radix-Sort, LSD-Radix-Sort | ||
| 8. | Pfingstwoche | ||
| 9. | Hashing (Einführung, Idee, Begriffe, Wahrscheinlichkeit einer Kollision, Divisionsmethode, Multiplikative Methode, universelles Hashing, Chaining, lineares Sondieren, quadratisches Sondieren, double hashing, Brent's Verfahren) | ||
| 10. | Algorithmendesigntechniken: Divide and Conquer (Schnelle Multiplikation mit Karatsuba-Ofman, schnelle Matrix-Multiplikation, das Closest Points Problem); Dynamische Programmierung 1 (Matrix Chain Multiplication Problem, die Technik der dynamischen Programmierung) | ||
| 11. | Dynamische Programmierung 2 (das Rucksack-Problem (knapsack problem), längste gemeinsame Teilfolge (longest common subsequence), Memoisierung, Zusammenfassung); Greedy Algorithmen (Das Activity-Selection-Problem, fractional knapsack problem, allg. Greedy-Strategie, Scheduling, Kompression, Huffman Code) | ||
| 12. |
Backtracking (Allgemeine Beschreibung, Färbung von Landkarten,
8-Damen-Problem); Precomputation (Vorgänger im Baum, Wiederholte Auswertung eines Polygons, Knuth-Morris-Pratt-Algo) |
||
| 13. |
Precomputation Rest (Boyer-Moore-Algorithmus zum String-Matching); Search Trees 1 (binary search trees, AVl-Bäume, AVL-Rotationen, Konstruktion optimaler Suchbäume, m-Weg-Bäume, B-Bäume) |
||
| 14. |
Search Trees 2 (Einfügen / Löschen in B-Bäumen, Digitale Suchbäume, Binary Tries,
Anwendung: Routing in Netzwerken); Numerisch robuste Algorithmen 1 (Der IEEE-Standard, das Maschinen-Epsilon, Rundungsfehler, numerisch robustere Berechnung der Standardabweichung) |
||
| 15. |
Numerisch robuste Algorithmen 2 (Kahan's Summation Formula,
Catastrophic Cancellation, Techniken gegen Overflow-Errors,
Test auf Gleichheit mit Epsilon-Guard); Amortisierte Laufzeitanalyse und Fibonacci-Heaps |
Literatur zu Python ist online ausreichend verfügbar; einige Links finden Sie unten.
Eine "Schein"-Klausur findet nicht statt.
Nicht klausurrelevant ist das Kapitel "amortisierte Laufzeit".
|
|
Klausureinsicht: 17.11. 1400 - 1500 in Raum 205.
Wer nicht bestanden hat kann sich zur Nachprüfung anmelden. Diese wird mündlich sein.
Termin für die Nachprüfung: 21.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.
Falls Ihre Matrikelnummer nicht dabei ist, und Sie denken, dass es sich dabei um einen Fehler handelt, sprechen Sie mich bitte einfach darauf an.