Informatik II

von Prof. Dr. Gabriel Zachmann

\

Beschreibung

- Algorithmentechniken (u.a. Divide-and-Conquer, Greedy Precomputation, Dynamic Programming)
- "Grundlegende Algorithmen (u.a. Sortieren und Suchen, Hashing, einfache numerische Algorithmen, Bäume, Optimierung, ...)
- Komplexitätsanalyse

4.2010

Vorlesungsaufzeichnungen

08.04.201001:29:062.126
Organisation und Spezifikation, Algorithmus, Programm
Organisation, Spezifikation, Algorithmus, Programm, Das "algorithmisches Denken", Die drei Ebenen des Algorithmenentwurfs, Beschreibung von Spezifikationen, Zum Begriff des Algorithmus, Begriffe in der Definition für "Algorithmus", Korrektheit, The Model of Computation (computational model), Exkurs: andere Computational Models, Darstellung / Beschreibung von Algorithmen, Pseudocode, Beispiel: ggT, Flussdiagramm (flow chart), Struktogramme, Anwendung von Moore's Law auf Algorithmen
12.04.201001:18:53657
Typsysteme
Der Ariane-Bug, Wozu Datentypen?, Definitionen, Static Typing (z.B. C / Java), Dynamic Typing (z.B. Python), Ändern eines Integers, Strongly Typed / Weakly Typed, Typing-Quadrant, Hierarchie bzgl. Typisierung
15.04.201001:30:42875
Einführung in Python
Höhere Datenstrukturen, Strings, Listen / Arrays, Mehrdimensionale Listen / Arrays, Beispiel: Diffusion Limited Aggregation, Tupel, Hierarchie von Sequenz-Typen, Dictionary, Funktionen, Parameterübergabe, Rückgabewerte, Keyword-Parameter, Default-Werte, Scope von Variablennamen, Module, Definition von Klassen, Instanzen, Dokumentation
19.04.201001:21:06590
Einfache Datenstrukturen
Records, Structs, Klassen (Verbunde), Das Array, Mathematische Interpretation, Verkettete Strukturen (linked structures), Verkettete Liste (Linked List), Stack und Queue, StackArray
22.04.201001:15:09445
Einfache Datenstrukturen und Suchen
Einfache Datenstrukturen: Implementierung, An Ancient Calculator, Beispiel-Anwendung für Stack: Postfix-Auswertung Der Algorithmus, Infix ? Postfix, Queue, Operationen. Suchen: Lineare Suche, Binäre Suche, Der rekursive Algorithmus, Analyse
26.04.201058:43505
Suchen und Schleifeninvarianten
Suchen: Binäre Suche, Der rekursive Algorithmus, Analyse, Exponentielle Suche, Interpolation search, Key-Indizierte Suche. Schleifeninvarianten
29.04.201001:28:301
Komplexität von Algorithmen
Leistungsverhalten, Laufzeit, Kostenmaße, Aufwandsberechnung, Funktionenklassen, Groß-O, O-Notation, Ω -Notation, Θ-Notation, Additionsregel, Multiplikationsregel, Einfache Beziehungen, Komplexitätsklasse, Funktionenklassen, Problemgröße und Rechenzeit
03.05.201001:24:271
Komplexität von Algorithmen und Bäume
Komplexität von Algorithmen: Groß-O, Zeitaufwand, Laufzeitabschätzung, Average-Case-Komplexität, Maxsummen-Problem, Analyse des naiven Algorithmus, Der clevere Algorithmus. Bäume: Terminologie, Baumtiefe, Eigenschaften, Binärbäume, Vollständige Bäume, Nummerierung der Knoten, Maximale Anzahl Knoten
06.05.201039:211
Bäume und Sortieralgorithmen
Bäume: Maximale Anzahl Knoten, Implementierung, Anwendung: Parse-Tree von Ausdrücken, Baumtraversierungen - Preorder-Traversierung, Postorder-Traversierung, Inorder-Traversierung, Nicht-rekursive Varianten mit threaded trees, Lokalität und Bäume, Levelorder-Traversierung (aka breadth-first search, BFS), Exkurs - Visitor Pattern. Sortieralgorithmen: Klassifikation / Kriterien von Sortierverfahren, Exkurs - Tape Libraries, Bubblesort, Effiziente Python-Implementierung, Korrektheits-Beweis, Quicksort, Algo-Animation
06.05.201030:11336
Sortieralgorithmen
Demo Quicksort, Algo-Animation, Demo Partitioning, Python-Implementierung, Korrektheit der Partitionierung, Laufzeit des Algorithmus, Auswahl des Pivot-Elementes, Programm für Median-of-3-Quicksort, Der Heap
10.05.201001:19:45296
Sortieralgorithmen
Heapsort, BuildHeap, Externes Sortieren, Mergesort
17.05.201056:311
Sortieralgorithmen
(Auf Wunsch des Dozenten ohne Videobild) Untere Schranke für allgemeine Sortierverfahren, Der Entscheidungsbaum (decision tree), Untere Schranke für Worst-Case, Untere Schranke für Average-Case, Beweis des Lemmas, Beweis des Satzes, Lineare Sortierverfahren, Counting-Sort, Der Algorithmus, Illustration von Countingsort, Analyse, Bucketsort
20.05.201001:15:28224
Sortieralgorithmen
Bucketsort, Der Algorithmus, Korrektheit, Laufzeit, Radix-Sort, Ausführlicher Algorithmus, Analyse, Counting-Sort, Die optimale Wahl von r, Visualisierung des Algorithmus'
31.05.201001:19:581
Hashing
Das Datenbank-Problem "revisited", Hash-Tabellen, Typische Implementierung einer Hash-Klasse, Kollisionen und Belegungsfaktor, Die beiden Bestandteile eines Hash-Verfahrens, Hash-Funktionen, Multiplikative Methode, Universelles Hashing
03.06.201001:16:49296
Hashing
Universelles Hashing, Eine universelle Klasse von Hash-Funktionen, Möglichkeiten der Kollisionsbehandlung, Chaining, Offene Hash-Verfahren (open adressing), Lineares Sondieren, Quadratisches Sondieren, Double Hashing, Brents Verfahren
07.06.201001:19:121
Divide & Conquer
Chaining, Algorithmen-Design-Techniken, Schnelle Multiplikation, Algorithmus von Karatsuba und Ofman, Schnelle Matrix-Multiplikation, Idee von Strassen, Das Closest Points Problem, Ein Divide-and-Conquer-Algorithmus, Zeit-Komplexit
10.06.201001:15:191
Dynamische Programmierung
Matrix Chain Multiplication Problem (MCMP), Multiplikation zweier Matrizen, Anzahl der verschiedenen Klammerungen, Die Struktur der optimalen Klammerung, Ein naiver rekursiver Algorithmus, Formulierung mittels Dynamischer Programmierung, Gewinnung der optimalen Reihenfolge, Algorithmus mittels dynamischer Programmierung, Die Technik der dynamischen Programmierung, Das Rucksack-Problem (Knapsack Problem), Der Rekursionsbaum
14.06.201001:23:101
Dynamische Programmierung und Greedy-Algorithmen
Dynamische Programmierung: Lösung mittels Dynamischer Programmierung, (Re-)konstruktion der Lösung, Die längste gemeinsame Teilfolge, Ein naiver Algorithmus, Die Struktur des LCSP, Eine Rekursion für die Länge der LCS, Berechnung der Werte c[i,j], Memoisierung (Top-down-Ansatz). Greedy-Algorithmen: Das Activity-Selection-Problem (ASP), Die optimale Unterstruktur, Die Greedy-Choice-Eigenschaft, Ein greedy Algorithmus für das ASP
17.06.201001:30:021
Greedy-Algorithmen
Das fraktionale Rucksack-Problem, Elemente der Greedy-Strategie, Allgemeine abstrakte Formulierung des Greedy-Algos, Scheduling in (Betriebs-) Systemen, Optimalitätsbeweis, Das SMS-Aufkommen der letzten Jahre, Kodierung und Kompression, Eindeutige Codes, Herleitung der Huffman-Kodierung, Der Huffman-Code, Der Algorithmus zur Erzeugung des Codes, Dekodierung mit Huffman-Codes
21.06.201001:18:581
Backtracking
Allgemeines Problem-Statement, Zusammenhang zu Depth-First-Search, Ein Färbungsproblem, Naive Lösung: erschöpfende Suche (exhaustive search), Eine Backtracking-Lösung, Beispiel-Implementierung in Python, Komplexität, Anwendungen, Das Acht-Damen-Problem, Der Algorithmus im Detail
24.06.201001:26:491
Precomputation
Definitionen, Der Vorgänger im Baum, Wiederholte Auswertung eines Polynoms, Auswertung an äquidistanten Stellen, Das Verfahren, Suchen in Texten (String Matching), Die Aufgabe, Das naive Verfahren, Aufwand, Das Verfahren nach Knuth-Morris-Pratt (KMP), Implementierung, Korrektheit des Algorithmus, Laufzeit
28.06.201001:13:211
Precomputing und Bäume zum effizienten Information Retrieval
Precomputing: Berechnung des next-Arrays, Die Gesamtlaufzeit von KMP, Das Verfahren nach Boyer-Moore (BM), Die "Bad Character"-Heuristik (Vorkommensheuristik), BM-Algorithmus, 1. + 2. Version. Bäume zum effizienten Information Retrieval: Binäre Suchbäume (binary search tree, BST), Einfügen, Suchen, Löschen, Balancierte Bäume, AVL-Bäume, Minimale Knotenanzahl von AVL-Bäumen, Die maximale Höhe von AVL-Bäumen, Der AVL Search Tree, Einfügen von Knoten, Löschen von Knoten
01.07.201001:13:081
Bäume zum effizienten Information Retrieval
Löschen von Knoten, AVL-Rotationen, RR-Rotation, LL-Rotation, LR-Rotation, Code, Algo-Animation, Optimale Suchbäume, Die optimale Unterstruktur, Bottom-up-Berechnung einer optimalen Lösung, Mehrwegbäume, m-Wege-Bäume, Einfügen in einen 4-Wege-Baum, B-Bäume
05.07.201001:30:171
Bäume zum effizienten Information Retrieval
B-Bäume, Algorithmus zum Einfügen in einen B-Baum, Der B*-Baum, Löschen in einem B-Baum, Allgemeiner Lösch-Algorithmus, Beispiel (k = 2), Komplexitätsanalyse für B-Bäume, Kosten für Insert und Löschen, Digitale Suchbäume (DST = digital search trees), Binäre Tries, Routing und Forwarding, 1. (Brute-Force) Ansatz: Lineare Suche, 2. Ansatz: Sortierte Bereiche, 3. Ansatz: Lösung mit DST / Trie
08.07.201001:27:471
Numerische Robustheit
Das IEEE-754-Format, Alle darstellbaren Werte in single precision (float), Der relative Fehler und ULPs, Fehlerquellen beim Rechnen mit Floats, Das Maschinen-Epsilon, Akkumulation von Rundungsfehlern, Berechnung der Standardabweichung, Nachteile des naiven Algorithmus, Error-Free Transformations (EFT)
12.07.201001:02:541
Numerische Robustheit
Der Fehler der naiven Summationsformel, Die "Kahan Summation Formula", Cancellation, Overflow-Errors, Ein robuster Test auf "Gleichheit" mit Epsilon-Guard, Das Minimum an Take-Home Messages.
15.07.201048:051
Fibonacci-Heaps und Amortisierte Komplexität und Wrapping Up
Fibonacci-Heaps und Amortisierte Komplexität: Die Amortisierte Laufzeit, Bankkonto-Paradigma, Fibonacci-Heaps, Das API, Implementationsmöglichkeit 1 - Liste, Implementationsmöglichkeit 2 - Heap, Repräsentation von Bäumen, Child-Sibling-Repräsentation. Wrapping Up: Einordnung in eine Landschaft, Alle Themen.