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:

  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. 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):
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. 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: 27.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 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

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