Video-Server > Vorlesungen > Informatik II

Informatik II

von Prof. Dr. Gabriel Zachmann

33:49 Std11.033 Aufrufe09.04.2010
Kamera Anja Michaela Kaiser

Hinweise zum Player

Um die Aufzeichnungen auf dieser Webseite wiedergeben zu können, muss Javascript aktiviert sein. Zudem wird für alle Browser die aktuelle Version des Adobe Flash Players benötigt.



Vorlesungen


Organisation und Spezifikation, Algorithmus, Programm

Vorlesung Nr. 1

01:29 Std08.04.20102.030 Aufrufe

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

01:18 Std12.04.2010608 Aufrufe

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

01:30 Std15.04.2010807 Aufrufe

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

01:21 Std19.04.2010539 Aufrufe

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

01:15 Std22.04.2010412 Aufrufe

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

01:15 Std26.04.2010474 Aufrufe

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

01:28 Std29.04.2010693 Aufrufe

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

01:24 Std03.05.2010483 Aufrufe

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

39:20 Min06.05.2010456 Aufrufe

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

30:11 Min06.05.2010322 Aufrufe

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

01:19 Std10.05.2010287 Aufrufe

Vorlesung starten

Inhalt:
Heapsort, BuildHeap, Externes Sortieren, Mergesort

Sortieralgorithmen

Vorlesung Nr. 12

56:30 Min17.05.2010257 Aufrufe

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

01:15 Std20.05.2010217 Aufrufe

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

01:19 Std31.05.2010424 Aufrufe

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

01:16 Std03.06.2010291 Aufrufe

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

01:19 Std07.06.2010359 Aufrufe

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

01:15 Std10.06.2010349 Aufrufe

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

01:23 Std14.06.2010296 Aufrufe

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

01:30 Std17.06.2010215 Aufrufe

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

01:18 Std21.06.2010215 Aufrufe

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

01:26 Std24.06.2010178 Aufrufe

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

01:13 Std28.06.2010225 Aufrufe

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

01:13 Std01.07.2010231 Aufrufe

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

01:30 Std05.07.2010203 Aufrufe

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

01:27 Std08.07.2010134 Aufrufe

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

01:02 Std12.07.2010121 Aufrufe

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

48:05 Min15.07.2010207 Aufrufe

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.


Impressum · Kontakt© TU Clausthal 2017