Video-Server > Vorlesungen > Informatik II

Informatik II


Kamera Anja Michaela Kaiser
von Prof. Dr. Gabriel Zachmann

im Sommersemester 2010

Vorlesungskennung: S 1102

- 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

Weitere Informationen zur Vorlesung:
Institut für Informatik oder im Vorlesungsverzeichnis

10.872 Aufrufe

Vorlesungen


Organisation und Spezifikation, Algorithmus, Programm

Vorlesung Nr.1
Aufgezeichnet am 08.04.2010 | 2.003 Aufrufe

01:29 h

Vorlesung starten

Inhalt:
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

Typsysteme

Vorlesung Nr.2
Aufgezeichnet am 12.04.2010 | 598 Aufrufe

01:18 h

Vorlesung starten

Inhalt:
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

Einführung in Python

Vorlesung Nr.3
Aufgezeichnet am 15.04.2010 | 792 Aufrufe

01:30 h

Vorlesung starten

Inhalt:
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

Einfache Datenstrukturen

Vorlesung Nr.4
Aufgezeichnet am 19.04.2010 | 526 Aufrufe

01:21 h

Vorlesung starten

Inhalt:
Records, Structs, Klassen (Verbunde), Das Array, Mathematische Interpretation, Verkettete Strukturen (linked structures), Verkettete Liste (Linked List), Stack und Queue, StackArray

Einfache Dtanestrukturen und Suchen

Vorlesung Nr.5
Aufgezeichnet am 22.04.2010 | 401 Aufrufe

01:15 h

Vorlesung starten

Inhalt:
Einfache Dtanestrukturen: 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

Suchen und Schleifeninvarianten

Vorlesung Nr.6
Aufgezeichnet am 26.04.2010 | 461 Aufrufe

01:15 h

Vorlesung starten

Inhalt:
Suchen: Binäre Suche, Der rekursive Algorithmus, Analyse, Exponentielle Suche, Interpolation search, Key-Indizierte Suche. Schleifeninvarianten

Komplexität von Algorithmen

Vorlesung Nr.7
Aufgezeichnet am 29.04.2010 | 686 Aufrufe

01:28 h

Vorlesung starten

Inhalt:
Leistungsverhalten, Laufzeit, Kostenmaße, Aufwandsberechnung, Funktionenklassen, Groß-O, O-Notation, Ω -Notation, Θ-Notation, Additionsregel, Multiplikationsregel, Einfache Beziehungen, Komplexitätsklasse, Funktionenklassen, Problemgröße und Rechenzeit

Komplexität von Algorithmen und Bäume

Vorlesung Nr.8
Aufgezeichnet am 03.05.2010 | 478 Aufrufe

01:24 h

Vorlesung starten

Inhalt:
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

Bäume und Sortieralgorithmen

Vorlesung Nr.9
Aufgezeichnet am 06.05.2010 | 452 Aufrufe

39:20 min

Vorlesung starten

Inhalt:
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

Sortieralgorithmen

Vorlesung Nr.10
Aufgezeichnet am 06.05.2010 | 320 Aufrufe

30:11 min

Vorlesung starten

Inhalt:
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

Sortieralgorithmen

Vorlesung Nr.11
Aufgezeichnet am 10.05.2010 | 285 Aufrufe

01:19 h

Vorlesung starten

Inhalt:
Heapsort, BuildHeap, Externes Sortieren, Mergesort

Sortieralgorithmen

Vorlesung Nr.12
Aufgezeichnet am 17.05.2010 | 254 Aufrufe

56:30 min

Vorlesung starten

Inhalt:
(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

Sortieralgorithmen

Vorlesung Nr.13
Aufgezeichnet am 20.05.2010 | 215 Aufrufe

01:15 h

Vorlesung starten

Inhalt:
Bucketsort, Der Algorithmus, Korrektheit, Laufzeit, Radix-Sort, Ausführlicher Algorithmus, Analyse, Counting-Sort, Die optimale Wahl von r, Visualisierung des Algorithmus'

Hashing

Vorlesung Nr.14
Aufgezeichnet am 31.05.2010 | 420 Aufrufe

01:19 h

Vorlesung starten

Inhalt:
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

Hashing

Vorlesung Nr.15
Aufgezeichnet am 03.06.2010 | 288 Aufrufe

01:16 h

Vorlesung starten

Inhalt:
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

Divide & Conquer

Vorlesung Nr.16
Aufgezeichnet am 07.06.2010 | 357 Aufrufe

01:19 h

Vorlesung starten

Inhalt:
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

Dynamische Programmierung

Vorlesung Nr.17
Aufgezeichnet am 10.06.2010 | 346 Aufrufe

01:15 h

Vorlesung starten

Inhalt:
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

Dynamische Programmierung und Greedy-Algorithmen

Vorlesung Nr.18
Aufgezeichnet am 14.06.2010 | 287 Aufrufe

01:23 h

Vorlesung starten

Inhalt:
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

Greedy-Algorithmen

Vorlesung Nr.19
Aufgezeichnet am 17.06.2010 | 209 Aufrufe

01:30 h

Vorlesung starten

Inhalt:
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

Backtracking

Vorlesung Nr.20
Aufgezeichnet am 21.06.2010 | 211 Aufrufe

01:18 h

Vorlesung starten

Inhalt:
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

Precomputation

Vorlesung Nr.21
Aufgezeichnet am 24.06.2010 | 173 Aufrufe

01:26 h

Vorlesung starten

Inhalt:
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

Precomputing und Bäume zum effizienten Information Retrieval

Vorlesung Nr.22
Aufgezeichnet am 28.06.2010 | 223 Aufrufe

01:13 h

Vorlesung starten

Inhalt:
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

Bäume zum effizienten Information Retrieval

Vorlesung Nr.23
Aufgezeichnet am 01.07.2010 | 230 Aufrufe

01:13 h

Vorlesung starten

Inhalt:
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

Bäume zum effizienten Information Retrieval

Vorlesung Nr.24
Aufgezeichnet am 05.07.2010 | 202 Aufrufe

01:30 h

Vorlesung starten

Inhalt:
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

Numerische Robustheit

Vorlesung Nr.25
Aufgezeichnet am 08.07.2010 | 132 Aufrufe

01:27 h

Vorlesung starten

Inhalt:
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)

Numerische Robustheit

Vorlesung Nr.26
Aufgezeichnet am 12.07.2010 | 120 Aufrufe

01:02 h

Vorlesung starten

Inhalt:
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.

Fibonacci-Heaps und Amortisierte Komplexität und Wrapping Up

Vorlesung Nr.27
Aufgezeichnet am 15.07.2010 | 203 Aufrufe

48:05 min

Vorlesung starten

Inhalt:
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.

Hinweise zum Player

Bitte aktivieren Sie zur Wiedergabe JavaScript.


Impressum · Kontakt© TU Clausthal 2017