Main Page
From Alda
Getting started
- Wiki Editierhilfe (markup syntax usw.)
- MediaWiki Manual (für Administratoren)
- Sandbox (zum ungefährlichen Ausprobieren von Änderungen)
Vorlesung Algorithmen und Datenstrukturen SS 08
Organisatorisches (9.4.2008)
- Übungsbetrieb
- Scheinbedingungen, Credit points
- Klausurtermin
Gliederung der Vorlesung (als PDF mit Übungsthemen)
- Einführung (9.4.2008)
- Definition von Algorithmen und Datenstrukturen, Geschichte
- Fundamentale Algorithmen: create, assign, copy, swap, compare etc.
- Fundamentale Datenstrukturen: Zahlen, Container, Handles
- Container (10.4.2008)
- Anforderungen von Algorithmen an Container
- Einteilung der Container
- Grundlegende Container: Array, verkettete Liste, Stack und Queue
- Sequenzen und Intervalle (Ranges)
- Sortieren (16. und 17.4.2008)
- Spezifikation des Sortierproblems
- Selection Sort
- Merge Sort
- Quick Sort und seine Varianten
- Vergleich der Anzahl der benötigten Schritte
- Laufzeitmessung in Python
- Korrektheit (23. und 24.4.2008)
- Definition von Korrektheit, Algorithmen-Spezifikation
- Korrektheitsbeweise versus Testen
- Vor- und Nachbedingungen, Invarianten, Programming by contract
- Testen, Execution paths, Unit Tests in Python
- Ausnahmen (exceptions) und Ausnahmebehandlung in Python
- Effizienz (24. und 30.4.2008)
- Laufzeit und Optimierung: Innere Schleife, Caches, locality of reference
- Laufzeit versus Komplexität
- Komplexitätsklassen
- Bester, schlechtester, durchschnittlicher Fall
- Amortisierte Komplexität
- Suchen (7. und 8.5.2008)
- Binäre Suche in sortierten Arrays
- Suchbäume
- balancierte Bäume
- selbst-balancierende Bäume, Rotationen
- Komplexität der Suche
- Prioritätswarteschlangen (14.5.2008)
- Heap-Datenstruktur
- Einfüge- und Löschoperationen
- Heapsort
- Komplexität des Heaps
- Dictionaries (15.5.2008)
- Implementation mit Bäumen
- Hashing
- Implementation als Hashtabelle
- Iteration versus Rekursion (21.5.2008)
- Typen der Rekursion und ihre Umwandlung in Iteration
- Iteratoren
- Generizität (28.und 29.5.2008)
- Abstrakte Datentypen, Typspezifikation
- Required Interface versus Offered Interface
- Adapter und Typattribute, Funktoren
- Beispiel: Algabraische Konzepte und Zahlendatentypen
- Operator overloading in Python
- Graphen und Graphenalgorithmen (4. bis 12.6.2008)
- Einführung
- Graphendatenstrukturen, Adjazenzlisten und Adjazenzmatrizen
- Gerichtete und ungerichtete Graphen
- Vollständiger Graph
- Pfade, Zyklen
- Tiefensuche und Breitensuche
- Zusammenhang, mehrfacher Zusammenhang, Komponenten
- Gewichtete Graphen
- Minimaler Spannbaum
- Kürzeste Wege, Best-first search (Dijkstra)
- Most-Promising-first search (A*)
- Prinzipien des Algorithmenentwurfs (18.6.2008)
- Repetition
- Orthogonale Zerlegung des Problems
- Hierarchische Zerlegung der Daten (Divide and Conquer)
- Randomisierung
- Optimierung, Zielfunktionen
- Systematisierung von Algorithmen aus der bisherigen Vorlesung
- Analytische Optimierung (19.6.2008)
- Methode der kleinsten Quadrate
- Approximation von Geraden
- Randomisierte Algorithmen (25. und 26.6.2008)
- Zufallszahlen, Zyklenlänge, Pitfalls
- Zufallsverteilungen, Box-Muller Transformation
- Randomisierte vs. deterministische Algorithmen
- Las Vegas vs. Monte Carlo Algorithmen
- Beispiel für Las Vegas: Randomisiertes Quicksort
- Beispiele für Monte Carlo: randomisierte Integration, randomisierter Primzahltest
- RANSAC-Algorithmus, Erfolgswahrscheinlichkeit
- Greedy-Algorithmen (2.7.2008)
- Prinzip
- Bedingung für Optimalität
- Beispiele für Greedy-Algorithmen
- Dynamische Programmierung (3. und 9.7.2008)
- Erschöpfende Suche (10. und 16.7.2008)
- Beispiele: u.a. Problem des Handlungsreisenden
- Exponentielle Komplexität, NP-Vollständigkeit
- Approximation bei NP-vollständigen Problemen
- Quantum computing (17.7.2008)
