Informatik II
SS 2010


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:

  1. Einführung in Python, als Vertreter einer Sprache mit dynamischer Typisierung
  2. Bäume
  3. Such- und Sortier-Algorithmen
  4. Algorithmentechniken (u.a. Divide-and-Conquer, Greedy, Precomputation, Dynamic Programming)
  5. Viele Beispiele für in der Praxis relevante Algorithmen
  6. Komplixtätsanalyse

Aktuelles

Klausurnoten

Folien

Die folgende Tabelle enthält die behandelten Themen und die dazugehörigen Folien.

Woche Thema Folien Übungs-
aufgaben
Literatur
1. Orga, Einleitung PDF1 PDF2 PDF
2. Typsysteme (dynamic typing / static typing, weakly typed / strongly typed), Python Basics, höhere Python-Konstrukte (Lists, Tupel, Dicts, Funktionen, Klassen) PDF1 PDF2 PDF3 PDF
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) PDF1 PDF2 PDF3 PDF
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) PDF1 PDF2 PDF3 PDF
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) PDF1 PDF2 PDF3 PDF4 PDF
6. Sortieren 2 (Heapsort, ausführliches Beispiel zu BuildHeap im Array, Mergesort); Himmelfahrt PDF PDF
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 PDF1 PDF2 PDF
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) PDF1 PDF2 PDF
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) PDF1 PDF2 PDF
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) PDF1 PDF2 PDF3 PDF
12. Backtracking (Allgemeine Beschreibung, Färbung von Landkarten, 8-Damen-Problem);
Precomputation (Vorgänger im Baum, Wiederholte Auswertung eines Polygons, Knuth-Morris-Pratt-Algo)
PDF1 PDF2 PDF
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)
PDF1 PDF2 PDF3 PDF
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)
PDF1 PDF2 PDF
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
PDF1 PDF2

Zu den Video-Aufzeichnungen der Vorlesung.

Literatur

Folgende Literatur eignet sich als begleitende Lehrbücher (in Klammern die oben verwendeten Kürzel):
Falls Sie sich diese Bücher anschaffen möchten, sollten Sie vielleicht überlegen, gebrauchte Exemplare zu erwerben -- oft gibt es diese zu einem Bruchteil des Neupreises. Zwei gute Internetadressen sind Abebooks und BookButler.

Literatur zu Python ist online ausreichend verfügbar; einige Links finden Sie unten.

Scheinerwerb

Einen Schein erwirbt man durch erfolgreiche Teilnahme an den Übungen. Das heißt, Sie müssen insgesamt mindestens 50% der maximal erhältlichen Punkte erreichen und wenigstens einmal vorgerechnet haben. Teilnahme an den kleinen Übungen ist Pflicht.

Eine "Schein"-Klausur findet nicht statt.

Klausur

Termin: 5. 10. 2010 um 1400 im Hörsaal B der Mathematik (Erzstraße);
Dauer: 1 Stunde.
Mitzubringen sind: Personalausweis (oder Paß), Studentenausweis, Stift.
Erlaubte Hilfsmittel: Traubenzucker u.ä; persönlicher "Spickzettel".
Der persönliche Spickzettel ist folgendermaßen definiert: nicht mehr als 3 DIN-A4-Blätter, die in der eigenen Handschrift beschrieben sein müssen! Sie dürfen insbesondere nicht maschinell beschrieben sein! Sie dürfen die Vorder- und Rückseiten beschreiben.
Nicht erlaubte Hilfsmittel sind insbesondere: Wörterbuch, Handy, Taschenrechner, sonstige Zettel, Bücher.

Nicht klausurrelevant ist das Kapitel "amortisierte Laufzeit".

Die Klausurnoten
Matr.Nr. Note
335720 4.0
350516 5.0
362405 4.0
364782 5.0
371339 5.0
372574 3.7
380476 3.3
380689 2.3
380902 3.7
380933 3.0
381178 2.7
Matr.Nr. Note
381185 1.7
381264 2.3
381295 3.0
382148 5.0
383503 4.0
383871 3.0
384645 3.0
386094 3.7
387174 2.3
387208 4.0
387497 2.7

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:

  1. bei Frau Cronjäger in Raum 202 anmelden und sich in die Liste eintragen für den Termin;
  2. mit diesem Termin im Prüfungsamt bei Frau Lenk anmelden zur Nachprüfung;
  3. am Prüfungstermin zur entsprechenden Uhrzeit in Raum 205 (mein Büro) melden. (Bitte möglichst eine halbe Stunde früher erscheinen, falls ein Kandidat vor Ihnen ausfällt.)

Hier finden Sie eine Musterlösung zur Klausur.

Übungsbetrieb

Übungsblätter
Theoretische Aufgaben werden schriftlich abgeliefert, die Abgabe von praktischen Aufgaben klären Sie bitte mit Ihrem Tutor (üblich ist, diese vorab per Mail an den Tutor zu schicken und in der Übung das Programm vorzuführen).

Aktive Teilnahme an den Übungen
Durch Vorrechnen von Übungsaufgaben an der Tafel ist es möglich, zusätzliche Punkte zu erhalten. Davon sollten Sie insbesondere dann Gebrauch machen, wenn Sie nicht die erforderlichen 50% der Gesamtpunkte haben. Dabei ist es keinesfalls notwendig, die richtige Lösung an der Tafel vorzurechnen -- es reicht schon eine Idee für einen Ansatz (selbst wenn dieser dann nicht direkt zum Ziel führt).

Auch bei der Scheinvergabe wirkt sich eine aktive Teilnahme an den Übungen in Grenzfällen positiv aus.

Übungsschein
Hier finden Sie die Liste der Scheine aus den Übungen, die gleichzeitig die Voraussetzung sind, an der Klausur teilnehmen zu dürfen.

Falls Ihre Matrikelnummer nicht dabei ist, und Sie denken, dass es sich dabei um einen Fehler handelt, sprechen Sie mich bitte einfach darauf an.

Downloads zu den Übungsblättern

Übungsblatt Nr. 2
kant.txt , liste_framework.py .
Übungsblatt Nr. 3
Stack.py , postfix_framework.py .
Übungsblatt Nr. 4
search_benchmark.py .
Übungsblatt Nr. 6
Das Framework zur Heap-Aufgabe: heaps2.py . Achtung: dieses Framework ist so noch nicht lauffähig, da einige Funktionen noch nicht "ausgefüllt" sind! (Wenn Sie für eine Funktion gerne zunächst eine "Dummy"-Implementierung einfügen möchten, so geht dies am einfachsten mit der Anweisung pass im Funktionsrumpf.)
Übungsblatt Nr. 7
sort.py .
Übungsblatt Nr. 10
select.py .
Übungsblatt Nr. 11
labyrinth.zip .

Online Literatur zu Python

Interessante Literatur

Change Monitoring:

 by ChangeDetection (it's free and it's private).
 by ChangeDetect (it's free and private, too).
If you enter your email adress in one of the boxes above and then press one of the "Monitor" buttons, then either ChangeDetection or ChangeDetect will send you an email whenever I make changes to this page.
Gabriel Zachmann
Last modified: Wed Mar 23 04:12:15 MET 2011