Die Klausur
fand am Freitag, 19.7. von 9.00 bis 12 Uhr im Hörsaal 201
statt.
Hier finden Sie die Ergebnisse.
Die Scheine können ab Montag, den 5.8. bei Sandra
Nentwich-Mertel (Raum Z1.05) abgeholt werden.
Die Klausuren können ab Montag, 11.8. jederzeit bei Jan
Johannsen (Raum D1.05) eingesehen werden.
Die Präsenzübungen werden in der folgenden Woche in den Übungsgruppen besprochen. Die Hausaufgaben sind jeweils am übernächsten Mittwoch vor der Vorlesung abzugeben. Sie sind mit Punktzahlen gewichtet, zur Zulassung zur Klausur müssen 50% der möglichen Punktzahl erreicht werden.
| Nr. | Tag | Zeit | Ort | Tutor |
|---|---|---|---|---|
| 1 | Mo | 14-16 Uhr | HS 113 | Markus Veith |
| 2 | Mo | 16-18 Uhr | HS 113 | Markus Veith |
| 3 | Di | 14-16 Uhr | HS 113 | Prof. Hofmann |
| 4/5 | Di | 16-18 Uhr | HS 113 | Martin Lange |
| 6 | Di | 18-20 Uhr | HS 113 | Andreas Abel |
| 7 | Do | 14-16 Uhr | E.40 | Martin Lange |
| 8 | Do | 16-18 Uhr | E.05 | Jan Johannsen |
Hörsäle HS 122, HS 113, E.40 und E.05 in der
Theresienstraße 39
Hörsäle HS 201, HS 217 im Hauptgebäde
Hier finden Sie die Liste der Teilnehmer, die zur Klausur zugelassen sind.
zurück zum Inhaltsverzeichnis dieser Seite
Die Vorlesung führt in grundlegende Algorithmen und Datenstrukturen ein, welche in fast allen Gebieten der Informatik und verwandten Disziplinen Anwendung finden. Wir lehnen uns eng an das Lehrbuch von Cormen et al. an, das in mehreren Präsenzexemplaren in der Bibliothek vorhanden ist.
zurück zum Inhaltsverzeichnis dieser Seite
| Datum | Wer | behandelte Themen |
|---|---|---|
| Mi 17.4. | MH | Organisatorisches. Was sind Algorithmen, warum muss man sich mit Algorithmik beschäftigen? Überblick über die Vorlesung mit Anwendungsbeispielen. Laufzeitanalyse von Insertion-Sort. Entwurfsprinzip Divide-and-conquer. |
| Fr 19.4. | MH |
Merge-Sort als Beispiel für Divide and Conquer. Herleitung
der Rekurrenz T(n)=2T(n/2)+Theta(n) für die Laufzeit von
Merge-Sort. Formale Definition der asymptotischen Notationen
Theta,O,Omega,o,omega.
Folgendes Beispiel einer Asymptotik
steht so nicht im Buch: log(n!)=Omega(n log n). Beweis: log
n!=log 1+log 2+...+log n >= log(n/2)+log(n/2+1)+...+log(n)
>= n/2 (log(n/2)) = Omega(n log n). Die Master-Methode als Kochrezept für die Lösung von Rekurrenzen der Form T(n)=aT(n/b)+f(n). Beispiele für die Anwendung. |
| Mi 24.4. | MH |
Matrizenmultiplikation zweier nxn-Matrizen mit O(n^2,81)
arithmetischen Operationen nach Strassen als Beispiel eines
Divide-and-Conquer Verfahrens. Sortieren einer Liste in Zeit
O(n log n) ohne Verwendung zusätzlichen Speicherplatzes mit
Heapsort. Definition der Datenstruktur "Heap", die
Hilfsprozeduren Heapify, Build-Heap und Heap-Sort. |
| Fr 26.4. | MH | Prioritätsschlangen als weitere Anwendung von Heaps. Quicksort: Das Verfahren, Laufzeit im besten Theta(n log n) und schlechtesten Fall Theta(n^2). Randomisiertes Quicksort: Erwartungswert der Laufzeit ist Theta(n log n). Detaillierter Beweis dieser Tatsache wurde vorgeführt. untere Schranke Omega(n log n) für jedweden vergleichsbasierten Sortieralgorithmus. < |
| Fr 3.5. | MH |
Wdh der unteren Schranke Omega(n log n) für vergleichsbasiertes
Sortieren. Begriff der Vergleichskomplexität. Maximum, Minimum,
Maximum und Minimum simultan. Für letzteres wurde die
Vergleichskomplexität zu V(n)=3n/2-2 bestimmt. Begriff des
Medians und des i-kleinsten Elements. Anwendungen des Medians auf
Interpolation und Positionierung von Zentrallagern. Berechnung des
i-kleinsten Elements in erwarteter und auch worst case Zeit
Theta(n). Hier noch die korrekte Lösung der Rekurrenz
T(n)<=2/n Summe(k=n/2..n-1,T(k))+O(n). Der O(n)-Term sei ab n0 durch
dn beschränkt. Falls wir c genügend groß wählen,
können wir erreichen, dass T(n)<=cn für alle n im Bereich
n0/2..n0. Für größere n arbeiten wir mit
Induktion. Sei also n>n0 fest aber beliebig vorgegeben und gelte
bereits T(k)<=ck für alle k=n0/2..n-1.
|
| Mi 8.5. | MH |
Dynamische Mengen, Hash-Tabellen. Kollisionsauflösung durch
Verkettung, sinnvolle Hashfunktionen. Offene Adressierung,
Probiersequenzen, sinnvolle Hashfunktionen, Probleme mit linearem
Probieren (primary clustering), double hashing als gute Approximation
an uniform hashing, Analyse von Hashing mit Verkettung und Offener
Adressierung. Bitte beachten Sie die Preisaufgaben unter "Material zur Vorlesung". |
| Fr 10.5. | JJ |
Binäre Suchbäme. Operationen Search, Successor, Insert,
Delete in Zeit O(Höhe). Erwartete Höhe zufällig
erzeugter binärer Suchbäume ist O(log n). Nachtrag zum Beweis von E[depth[T]] = O(log n): Pr[ |Gj| >= t/2 ] <= Pr[ |S| >= t/2 ], denn: Sei Hj = { ki ; i <= n und kl < ki für alle l < i mit kl > kj }. Da Hj Obermenge von Gj ist, gilt Pr[ |Gj| >= t/2 ] <= Pr[ |Hj| >= t/2 ]. ObdA sind k1, ..., kn gerade die Zahlen 0,...,n-1. Dann ersetze jedes kl durch kl-kj-1 mod n. Dann ist S für die transformierte Anordnung mindestens so groß wie Hj für die ursprüngliche, also Pr[ |Hj| >= t/2 ] <= Pr[ |S| >= t/2]. |
| Mi 15.5. | JJ |
Präsentation der Lösung der Preisaufgabe durch Timo Bingmann
(s.u.). Balancierte binäre Suchbäume, Rotation. Rot-Schwarz-Bäume: Definition, Höhe ist höchstens 2 log2(n+1), Einfügeoperation. |
| Fr 17.5. | JJ |
Löschen aus Rot-Schwarz-Bäumen. B-Bäume: Definition, logarithmische obere Schranke an die Höhe, Suchen, Einfügen, Löschen. |
| Mi 22.5. | JJ |
Dynamische Programmierung: Konzept und Beispiele. Optimale
Klammerung bei der Multiplikation von mehreren (nichtquadratischen) Matrizen,
Berechnung einer längsten gemeinsamen Teilfolge zweier Folgen. Greedy-Algorithmen: Konzept, einfache Beispiele. |
| Fr 24.5. | JJ |
Ein einfaches Auswahlproblem als Beispiel für
Greedy-Algorithmen.
Huffman-Codes: Definition, Nutzen zur Datenkompression,
Greedy-Algorithmus zur Konstruktion; Beweis, das dieser einen
optimalen Code liefert. |
| Mi 29.5. | JJ |
Amortisierungs-Analyse: Konzept, Beispiel Binärzähler,
worst-case-Komplexität von Increment ist O(log n).
Amortisierungs-Analyse des Binärzählers
mit den genannten Methoden: amortisierte Komplexität von
Increment ist O(1). Datenstruktur für Familien disjunkter dynamischer Mengen. Einfache Realisierung durch verkettete Listen (nur kurz erwähnt), bessere als Wälder. Optimierungen mit Rangfunktion und Pfadkompression, amortisierte Komplexität ist O(log n) ohne und O(log* n) mit Pfadkompression. |
| Fr 31.5. | MH |
Diskrete Fouriertransformation. Motivation durch Fouriers Lösung
der Gleichung der schwingenden Saite. Definition der DFT. Wiederholung der komplexen Zahlen: Definition, Grundrechenarten, Polardarstellung, Einheitswurzeln. Zahlreiche Beispiele vorgerechnet. Interpretation der DFT mithilfe von Einheitswurzeln. Konkretes Beispiel der DFT für n=4 vorgerechnet. Translationsinvarianz des Intensitätsspektrums. Anwendung derselben auf Mustererkennung. Inverse DFT. Deutung der DFT als Frequenzspektrum. |
| Mi 5.6. | MH |
Polynome als formale Ausdrücke. Polynomfunktion, Gewinnung des
Polynoms aus Polynomfunktion mit Lagrange
Interpolation. Auswertung von Polynomen mit
Hornerschema. Repräsentation von Polynomen als Koeffizientenliste:
Addition, Auswertung in O(n); Multiplikation in O(n^2) (jeweils
Rechenoperationen als Funktion der Gradschranke). Repräsentation von
Polynomen als Punkt-Wert-Liste. Addition, Multiplikation in O(n),
Auswertung in O(n^2). Deutung der DFT als Punkt-Wert Repräsentation eines Polynoms zu den n-ten Einheitswurzeln als Stützstellen. Daraus Multiplikationsverfahren für Polynome in Koeffizientenrepräsentation: fülle mit Nullen auf, transformiere, multipliziere die Transformierten punktweise, transformiere zurück. Bestimmung der DFT mit O(n log n) Rechenoperationen durch divide-and-conquer (FFT), daraus O(n log n) Verfahren zur Multiplikation von Polynomen. Konkretes Beispiel mit n=8 vorgerechnet. Inverse DFT in O(n log n). Bitte beachten Sie auch die beiden neuen Preisaufgaben unter "Material". |
| Fr 7.6. | MH | Faltung: Definition, Berechnung mit DFT, Anwendungen in der Bildverarbeitung. Geometrische Algorithmen: Begriff, Motivation, Anwendungsbeispiele. Punkte, Vektoren, Strecken und Geraden in der Ebene. Kreuzprodukt. Schneiden zweier Strecken. Entwurfsprinzip "bounding box", Entwurfsprinzip "Überstreichen". |
| Mi 12.6. | MH | Ausführliche Behandlung des Entscheidungsverfahren für Schnittpunktfreiheit einer Liste von Strecken. Beispiel durchgerechnet, Verifikation mit Invarianten. Konvexe Hülle: Definition, Anwendungen, Verfahren (kursorisch). Zur konvexen Hülle wurde eine neue Preisaufgabe gestellt, Details siehe "unten". Detaillierte Beschreibung von Graham's scan (angefangen). |
| Fr 14.6. | MH |
Graham's scan zur Findung der konvexen Hümlle in O(n log n). Implementierung mit
Stack. Komplexitätsanalyse mit Aggregatmethode der amortisierten
Komplexität. Jarvis' march oder "gift wrapping": Eine Methode, die
die konvexe Hülle in O(nh) Operationen bestimmt, wobei h die Zahl der
Punkte auf der konvexen Hülle ist. Besser als Graham's scan wenn
h=o(log n). Finden des minimalen Abstands zweier Punkte in einer Liste in O(n log n) durch divide-and-conquer. |
| Mi 19.6. | JJ | Graphalgorithmen: Repräsentation von Graphen durch Adjazenzlisten oder Adjazenzmatrix, Vergleich des Platzbedarfs. Breitensuche und Tiefensuche, Klassifikation der Kanten bei der Tiefensuche. Prüfen, ob ein gerichteter Graph Zyklen hat, und topologische Sortierung eines dags mittels Tiefensuche. |
| Fr 21.6. | JJ |
Minimale Spannbäme: Definition, Verfahren allgemein: Kriterium
für sichere Kanten, die in den Baum eingefügt werden
können. Algorithmen von Kruskal mit Laufzeit O(|E| log |E|), und
Prim mit Laufzeit O(|E| log |V|). Verbesserung der Komplexität
beim Prim-Algorithmus durch Verwendung Fibonacci-Heaps. Kürzeste Wege, Optimale Teillösungseigenschaft und Probleme mit negativen Kantengewichten, Technik der Relaxation. |
| Mi 26.6. | JJ | Invarianten einer beliebigen Folge von Relaxationen. Algorithmen zum Finden kürzester Wege von einem Startpunkt: Dijkstras Algorithmus für nichtnegative Kantengewichte und ein einfacher Algorithmus für dags mit negativen Kantengewichten, mit Korrektheitsbeweisen. |
| Mi 3.7. | JJ |
Bellman-Ford Algorithmus für kürzeste Wege in allgemeinen
Graphen mit negativen Gewichten. Kürzeste Wege zwischen allen Knotenpaaren: Berechnung durch Matrizenmultiplikation, schneller mit iteriertem Quadrieren. Floyd-Warshall Algorithmus, auch für transitive Hülle. Flüsse in Netzwerken: Problemstellung und Definitionen. |
| Fr 5.7. | JJ |
Flüsse in Netzwerken: Restnetzwerke und Erweiterungspfade,
Ford-Fulkerson Methode zur Berechnung maximaler
Flüsse, Konkretisierung als Edmonds-Karp Algorithmus. Anwendung zum Auffinden maximaler Matchings in bipartiten Graphen (kurz skizziert). Nächstes Mal liest Martin Hofmann über Algorithmen auf Strings. |
| Mi 10.7. | MH | Suchen von Mustern in Zeicvhenketten (string matching). Problemstellung und Anwendungen. Das Rabin-Karp Verfahren: Bestimme Hashwert des Musters, sowie sukzessiver Textsegmente. Bei Uebereinstimmung der Hashwert ueberpruefen (Oberflaechlicher Test). String matching mit Automaten. Grundidee und Motivation. Konstruktion des Automaten fuer das Muster ababaca. |
| Fr 12.7. | MH | String matching mit Automaten. Beweis der Korrektheit des Verfahrens. Knuth-Morris-Pratt Verfahren: Die Praefixfunktion als Kurzfassung der Zustandsuebergangsfunktion des Automaten. Formaler Beweis der Korrektheit des KMP Verfahrens, Komplexitaetsanalyse mit Potentialmethode. Kurze Beschreibung ohne Beweis des heuristischen Boyer-Moore Verfahrens. |
zurück zum Inhaltsverzeichnis dieser Seite
zurück zum Inhaltsverzeichnis dieser Seite
