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:
- Bäume
- Such- und Sortier-Algorithmen
- 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.
- RS = Robert Sedgewick: Algorithms in C++, Parts 1-4; 3rd Edition, Addison Wesley.
Auch die Titel Algorithms in C oder Algorithms in Java tun's genauso gut.
- OW = T. Ottmann, P. Widmayer: Algorithmen und Datenstrukturen; 4-te Auflage, Spektrum Akademischer
Verlag.
- CLRS = Cormen, Leiserson, Rivest, Stein: Introduction to Algorithms, Prentce Hall
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:
- bei Frau Cronjäger in Raum 202 anmelden und sich in die Liste eintragen für einen der beiden
Termine;
- 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
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.
Quellcode zu Aufgabe 4: huffman_encoding.tar.gz
Quellcode zu Aufgabe 3: avl_tree_incomplete.tar.gz
Quellcode zu Aufgabe 2,3: heaps.tar.gz
Quellcode zu Aufgabe 3: 4gewinnt.tar.gz
Online Literatur
Interessante Literatur
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:
Thu Jun 07 15:29:41 MDT 2007
