Informatik II


Diese Vorlesung soll die Einführung in die Informatik abschlieflen. Der Schwerpunkt liegt nun auf Algorithmen und Datenstrukturen, aber auch andere grundlegende Themen, wie z.B. GUI-Programmierung oder Aspekte von Betriebssystemen, sollen behandelt werden. Die Übungsaufgaben werden wieder teils theoretisch, teils praktisch sein, wobei die praktischen Aufgaben, wie im WS, mit Python gelöst werden sollen.

Aus dem Inhalt:

  1. Bäume
  2. Such- und Sortier-Algorithmen
  3. Algorithmentechniken (u.a. Divide-and-Conquer, Greedy, Precomputation, Dynamic Programming)

Aktuelles

Musterlösung zur Klausur.

Folien

Die folgende Tabelle enthält die behandelten Themen und die dazugehörigen Folien. Je nach Bedarf können sich Verschiebungen ergeben.

Datum Thema Folien, 4up Folien, 2up Übungs-
aufgaben
Literatur
19.4. Orga, Wdhg. Big-Oh PDF PDF
21.4. Wdhg. Kompl.-Analyse, Wahrschl.keitsrechnung PDF PDF PDF
26.4. Wahrscheinlichkeitsrechnung Rest PDF PDF
28.4. Skip-Listen und selbstorganisierende Listen PDF PDF PDF
3.5. Bäume 1 (Def., einfache Eigenschaften) PDF PDF
5.5. Bäume 2 (Traversierung, Visitor-Pattern, Suchbäume) PDF PDF PDF
10.5. Bäume 3 (Balancierung, AVL) PDF PDF
12.5. Bäume 4 (B-Bäume, B*, B+) PDF PDF PDF
17.5. Bäume 5 (Komplexität in B-Bäumen, DSTs, binäre Tries) PDF PDF
19.5. Bäume 6 (Routing, m-way Tries, Patricia) PDF PDF PDF
24.5. Korrektheitsbeweise durch Schleifeninvarianten
Sortieren 1 (Bubble-, Selection-, Insertion-Sort)
PDF1 PDF2 PDF1 PDF2
26.5. Sortieren 2 (Shell-, Quick-sort) PDF PDF PDF
31.5. Sortieren 3 (Quicksort fertig, Heaps) PDF PDF
2.6. Projektor defekt PDF
14.6. Sortieren 4 (Heap-, Mergesort, lower bounds, Counting-Sort) PDF PDF
16.6. Sortieren 5 (Bucket-, Radix-Sort) PDF PDF PDF
21.6. Hashing 1 (Intro, Hash-Funktionen) PDF PDF
23.6. Hashing 2 (Kollisionsauflösungsstrategien) PDF PDF PDF
28.6. Hashing 3 (Beweis Double Hashing, Brent's Algo, Vergleich)
Algorithmentechnik: Divide-and-Conquer 1 (Langzahl-Mult., Matrix-Mult.)
PDF1 PDF2 PDF1 PDF2
30.6. Algorithmentechnik: D-&-C 2 (Closest-Points);
Algotechnik: Dynamische Programmierung 1 (Matrix-Chain-Mult.)
PDF1 PDF2 PDF1 PDF2 PDF
5.7. Dyn. Progr. 2 (MCMP fertig, allgemeine Prinzipien, opt. Suchbäume) PDF PDF
7.7. Dyn. Progr. 3 (Knapsack Problem, Longest Common Subsequence, Memoisierung) PDF PDF PDF
12.7. Greedy-Algorithmen 1 (Activity-Selection, fractional knapsack, Scheduling) PDF PDF
14.7. Greedy-Algorithmen 2 (Huffman-Kodierung, allg. Prinzipien) PDF PDF PDF
19.7. Backtracking (Allg., 4-Färbung, 8-Damen-Problem) PDF PDF
21.7. Vorberechnung 1 (Allg., Vorgänger im Baum, Polynomauswertung) PDF PDF
26.7. Vorberechnung 2 (Suche in Texten, KMP-, Boyer-Moore-Algo) PDF PDF
28.7. Ausblick: amortisierte Laufzeit, Fibonacci-Heaps (nicht Klausur-relevant); Wrap-Up PDF1 PDF2 PDF1 PDF2

Unter Linux können Sie die PDF-Files mit acroread, xpdf oder gv lesen.

Literatur

Folgende Literatur eignet sich als begleitende Lehrbücher, auf die auch in obiger Tabelle mit den entsprechenden Kürzeln verwiesen wird.
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.

Scheinerwerb

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

Eine "Schein"-Klausur findet nicht statt.

Klausur

Termin: 10. 10. 2006 um 1100 im Audimax;
Dauer: 3 Stunden.
Mitzubringen sind: Personalausweis (oder Pafl), Studentenausweis, Stift.
Erlaubte Hilfsmittel: Traubenzucker u.ä.
Nicht erlaubte Hilfsmittel sind insbesondere: Wörterbuch, Handy, Taschenrechner, Zettel, Bücher.

Zur Prüfungsvorbereitung finden Sie hier Aufgaben, wie sie in der Prüfung gestellt werden könnten.

Hier befindet sich die Tabelle der Noten.

Klausureinsicht: 23.10. ab 1600 in Raum 218.

Wer nicht bestanden hat kann sich zur Nachprüfung anmelden. Diese wird mündlich sein.
Es gibt 2 Termine für die Nachprüfung: 31.10. und 7.11. 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 einen der beiden Termine;
  2. 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 befindet eine Musterlösung zur Klausur.

Übungsbetrieb

Anmeldung zu den Übungen
Die Anmeldung zu den Übungen erfolgt online über das eVE-System des Instituts für Informatik (www.in.tu-clausthal.de/~eve/). Nach einer kurzen Anmeldung kann man dort ganz einfach seine Wunschübungsgruppe (S1102-U1 ... S1102-U5) auswählen. Die Listen werden allerdings erst nach der ersten Vorlesung freigeschaltet.

Kandidatinnen und Kandidaten mit einem existierenden eVE-Account werden gebeten darauf zu achten, dafl Ihre persönlichen Angaben aktuell sind!

Übungsblätter
Die Übungsblätter werden jeweils am Freitag im Lauf des Tages auf der Homepage der VL (also hier) ins Netz gestellt.

Die Abgabe der Lösungen ist jeweils in der übernächsten Woche direkt beim Tutor. Theoretische Aufgaben werden schriftlich abgeliefert, die Abgabe von praktischen Aufgaben klären Sie bitte mit Ihrem Tutor (Mail, CD, live, etc.).

Die Tutoren

Übungsgruppe Name Email Zeit Ort
S1102-U1 Yike Hu yike.hu   tu-clausthal.de Di. 15-17 T4
S1102-U2 Anneli Moeller anneli.moeller   tu-clausthal.de Di. 15-17 T1
S1102-U3 Jan-Michael Sunkel jan-michael.sunkel   tu-clausthal.de Di. 15-17 R308 Mathe-Gebäude
S1102-U4 Jessica Brinkmann jessica.brinkmann   tu-clausthal.de Do. 15-17 T5
S1102-U5 Sven Arnhold Sven.Arnhold   tu-clausthal.de Fr. 13-15 T2

Die Räume T1, T4 und T5 befinden sich im Hörsaalgebäude auf der Tannenhöhe (gelbes Haus).

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 60% 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.

Punktestände
Ihren aktuellen Punktestand können Sie hier einsehen.

Hinweise und Downloads zur Bearbeitung der Übungsblätter

Übungsblatt Nr. 1
Übungsblatt Nr. 2
Hinweis zu Aufgabe 4
Gleichverteilte Zufallszahlen können Sie mit der Funktion "random()" generieren. Hierzu müussen Sie das Modul "random" importieren. Vergessen Sie nicht, den Zufallszahlengenerator mit "seed()" zu initialisieren.
Übungsblatt Nr. 3
Quellcode zu Aufgabe 4: huffman_encoding.tar.gz
Übungsblatt Nr. 4
Quellcode zu Aufgabe 3: avl_tree_incomplete.tar.gz
Übungsblatt Nr. 7
Quellcode zu Aufgabe 2,3: heaps.tar.gz
Übungsblatt Nr. 12
Quellcode zu Aufgabe 3: 4gewinnt.tar.gz

Online Literatur

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: Thu Jun 07 15:29:41 MDT 2007