Online-Vorlesungen Logo

Suchbegriff

Informatik I

Informatik II

Informatik III

Künstliche Intelligenz

Programmierkurs I

Grundlagen der Programmierung

Betriebssystemarchitektur

Betriebssystemarchitektur II

Operating Systems and System Programming

Linux-Crashkurs

Seite 1 von 4

>>

Informatik II

Informatik / Grundvorlesung

Universität: TU Clausthal
Dozent: Prof. Dr. Gabriel Zachmann
Aufzeichnungsdatum: Sommersemester 2010
Sprache: Deutsch


Link zur Vorlesung!


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 | 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 | 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 | Records, Structs, Klassen (Verbunde), Das Array, Mathematische Interpretation, Verkettete Strukturen (linked structures), Verkettete Liste (Linked List), Stack und Queue, StackArray | 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: Binäre Suche, Der rekursive Algorithmus, Analyse, Exponentielle Suche, Interpolation search, Key-Indizierte Suche. Schleifeninvarianten | Leistungsverhalten, Laufzeit, Kostenmaße, Aufwandsberechnung, Funktionenklassen,Additionsregel, Multiplikationsregel, Einfache Beziehungen, Komplexitätsklasse, Funktionenklassen, Problemgröße und Rechenzeit | 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: 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 | 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 | Heapsort, BuildHeap, Externes Sortieren, Mergesort | 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 | Bucketsort, Der Algorithmus, Korrektheit, Laufzeit, Radix-Sort, Ausführlicher Algorithmus, Analyse, Counting-Sort, Die optimale Wahl von r, Visualisierung des Algorithmus' | 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 | 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 | 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 | 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: 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 | 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 | 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 | 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: 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 | 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-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 | 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) | 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: 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.

Online Vorlesungen Bottom Line Grafik
Sitemap