Informatik II

Informatik II
SS 2011

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:

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

Aktuelles

Auch eine Noten-Statistik ist nun vorhanden.
US Debt Crisis Explained

Folien

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

Woche	Thema	Folien	Übungs- aufgaben
1.	Organisation, Typsysteme (dynamic / static / inferred), Algorithmenbegriff, Einführung in Python (Basics)	PDF1 PDF2 PDF3 PDF4	PDF
2.	Strings und Arrays, Funktionen, Module, Klassen in Python; höhere Datenstrukturen allgemein (Verbünde, Arrays); Einfache Datenstrukturen 1 (Verbund, Array, Listen)	PDF1 PDF2	PDF
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)	PDF	PDF
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)	PDF1 PDF2 PDF3	PDF
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)	PDF1 PDF2 PDF3	PDF
6.	Sortieren 2 (Bubblesort, Insertion Sort, Selection Sort, Quicksort, Heapsort, Mergesort, Introsort)	PDF	PDF
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)	PDF1 PDF2	PDF
8.	Divide-and-Conquer (Multiplikation mit Karatsuba/Ofman; Schnelle Matrix-Multiplikation; das Closest-Pairs Problem [closest points])	PDF	PDF
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)	PDF	PDF Framework
10.	Greedy-Algorithmen (Activity-Selection-Problem, fraktionales Knapsack-Problem, abstrakte Definition von Greedy-Algorithmen, Scheduling, Huffman-Kodierung, arithmetische Kodierung)	PDF	PDF
11.	Backtracking (4-Farben-Problem, 8-Damen-Problem); Precomputation (Definition, Vorgänger im Baum, Polynomauswertung an äquidistanten Stellen, String Matching, weitere Anwendungen von Precomputation)	PDF1 PDF2	PDF Framework
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)	PDF1 PDF2	PDF
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)	PDF1 PDF2

Zu den Video-Aufzeichnungen der Vorlesung (aus dem SS 2010).

Literatur

Folgende Literatur eignet sich als begleitende Lehrbücher (in Klammern die oben verwendeten Kürzel):

Robert Sedgewick: Algorithms in C++, Parts 1-4; 3rd Edition, Addison Wesley. (RS)

Auch die Titel Algorithms in C oder Algorithms in Java tun's genauso gut.

T. Ottmann, P. Widmayer: Algorithmen und Datenstrukturen; 4-te Auflage, Spektrum Akademischer Verlag. (OW)
Cormen, Leiserson, Rivest, Stein: Introduction to Algorithms, Prentice Hall (CLRS)
Gustav Pomberger, Heinz Dobler: Algorithmen und Datenstrukturen; Pearson Studium (PoDo)

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 30% der maximal erhältlichen Punkte erreichen. (Achtung: ein zusätzlicher Verwendungszweck wird in der ersten Vorlesung erklärt!) Teilnahme an den kleinen Übungen ist Pflicht.

Eine "Schein"-Klausur findet nicht statt.

Klausur

Termin: 4. 10. 2011
Ort: T2 & T3, Albrecht-von-Groddeck-Straße 4 (gelbes Hörsaalgebäude)
Dauer: 90 Minuten.

Mitzubringen sind: Personalausweis (oder Paß), Studentenausweis, Stift.
Erlaubte Hilfsmittel: Traubenzucker u.ä und ein 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 und nicht kopiert sein! Sie dürfen die Vorder- und Rückseiten beschreiben.
Nicht erlaubte Hilfsmittel sind insbesondere: Wörterbuch, Handy, Taschenrechner, sonstige Zettel, Bücher.

Die Klausurnoten

Matr.Nr. Note

386850 2.3

390868 3.7

391364 1.7

391072 3.7

390521 2.3

397793 2.3

392114 3.3

398134 3.0

391687 3.0

393122 1.7

390703 5.0

393751 3.3

382083 3.0

393397 4.0

391429 3.7

398213 3.0

391436 3.7

372086 5.0

Und hier eine Klausur-Statistik:

Klausureinsicht: 14.12. 14⁰⁰ - 15⁰⁰ in Raum 205.

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:

bei Frau Cronjäger in Raum 202 anmelden und sich in die Liste eintragen für den Termin;
mit diesem Termin im Prüfungsamt bei Frau Lenk anmelden zur Nachprüfung;
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 30% 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.

Übungsscheine

Matr.Nr.	Note
388168	4.0
391687	2.7
391072	3.3
390868	3.0
386197	3.3
392114	2.0
391436	2.3
396194	4.0
398213	2.7
393751	2.3
393122	1.3
397793	2.3
315506	3.0
393397	3.7
358002	4.0

Matr.Nr.	Note
391429	3.0
391364	1.0
390703	3.7
390521	1.3
398134	2.7
396101	3.7
347798	3.0
396015	5.0
394147	5.0
401247	5.0
380438	5.0
387136	5.0
400473	5.0
379179	5.0
398718	5.0
398615	5.0

Falls Sie denken, dass sich dabei ein Fehler eingeschlichen hat, sprechen Sie mich bitte einfach darauf an.

Downloads zu den Übungsblättern

Online Literatur zu Python

Eine recht locker, aber gut geschriebene Einführung in Python: ACM Python Learning Path (erfordert einen kostenlosen ACM Web Account.)
Zentrale Anlaufstelle für offizielle Python-Dokumentation (Tutorial, Library Reference, HOWTOs, FAQs, etc.)
Die Homepage von Python enthält alles, was man braucht: Downloads, Software, Links, etc.
Nach ein paar Wochen (und später immer wieder einmal) sollten Sie sich den Google Python Style Guide zu Gemüte führen. Auch ich entdecke immer wieder etwas darin. (Wie man einem Satz im Abschnitt Background entnehmen kann, scheinen viele Programmierer bei Google den Editor Vim zu verwenden ... yes! vielleicht sollte ich bei Google anheuern :-) )
Learning to Program (Quelle). Sehr gut für absolute Programmier-Anfänger. Bitte ignorieren Sie die Einsprengsel zu JavaScript und VBScript!
Non-Programmers Tutorial For Python (Quelle1, Quelle2, Alternative, ). Auch gut für absolute Programmier-Anfänger.
Python Referenz. Recht ausführlich, in deutsch, auch für Anfänger.
Instant Python (Quelle). Für erfahrene Programmierer zum schnellen Einstieg.
Python Quick Reference: als HTML, als PDF on screen und als PDF zum Drucken (Quelle); eignet sich, wie der Name schon sagt, hauptsächlich zum Nachschlagen.
Falls Sie noch andere Tutorials zu Python suchen, finden Sie es bestimmt auf dieser Liste von über 200 Python Tutorials, sortiert nach Topics (Anfänger, Threads-, GUI-Programmierung, etc.)
Für Programmier-Anfänger hier eine kleine Einführung in die Begriffe und Konzepte eines Debuggers (Quelle)

Interessante weiterführende Literatur

Introduction to dynamically typed languages (by Laurence Tratt and Roel Wuyts). In: IEEE Software, Sep/Oct 2007.
Literatur zu Float-Arithmetik, Rundungsfehlern und Kahan's Summation Algorithmus:
- W. Kahan: How Futile are Mindless Assessments of Roundoff in Floating-Point Computation?. (Quelle)
- David Goldberg: What Every Computer Scientist Should Know About Floating-Point Arithmetic. (Quelle 1, Quelle 2)
- Kahan & Darcy: How Java's Floating-Point Hurts Everyone Everywhere. (Quelle)
Zwei recht gut zu lesende Einführungen bzw. Motivationen in amortisierte Laufzeitanalyse: ein Artikel von Sleator, und eine Zusammenfassung des entspr. Kapitels aus CLRS.
Eine Visualisierung von Sortier-Algorithmen, insbesondere Insertion Sort, Selection Sort, Mergesort, und Bubblesort (ab 4:40). Ein Gag des Films ist, dass die Algorithmen-Animation mit echten Menschen durchgeführt wird :-) (und Obama tritt am Ende auch noch auf). (Quelle. In der Suggestions-Liste findet man noch viele weitere interessante oder hübsche Algorithmen-Animationen; unter anderem auch diese Sonifikation!)
Einige Notizen aus dem Internet zu van-Emde-Boas-Trees:
- Skript zu vEB-Trees von Gudmund S. Frandsen aus 2004 (Quelle: Direktlink , Homepage der VL)
- Lecture 1 und Lecture 2 (sog. "scribe notes" aus der Vorlesung von Erik Demaine aus dem Jahr 2003)
Zum A-Star (A*-) Algorithmus:
- Eine Demo zum A-Star-Algorithmus (Quelle)
- Zum allerersten Einstieg finden Sie hier ein Tutorial (Quelle)
- Und hier finden Sie sehr ausführliche Informationen zum A*-Algorithmus, einschließlich aller möglicher Varianten, Optimierungen, etc. (Quelle)
Zum Arithmetic Coding:
- Eric Bodden, Malte Clasen, Joachim Kneis: Arithmetische Kodierung; Ausarbeitung zu einem Proseminar 2002 an der RWTH Aachen. (Quelle)
- Eric Bodden, Malte Clasen, Joachim Kneis: Arithmetic Coding revealed; Sable Technical Report No. 2007-5, McGill University School of Computer Science. (Quelle)
Ein unterhaltsamer, aber dennoch ernst gemeinter Artikel zum Thema "Kommentare im Source-Code": Literate Coding (Quelle, mit weiteren Leser-Kommentaren)
Ein witziger Audio-Beitrag zum Thema "Wieviel Englisch verträgt die deutsche Sprache?": Das Digitale Logbuch - downGEloadet.

Change Monitoring:

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: Tue Jan 10 21:10:33 MET 2012

Informatik II SS 2011