Main Page

Vorlesung Algorithmen und Datenstrukturen SS 08

Vorläufiger Inhalt der Vorlesungen und Übungen

1. Einführung (9.4.2008)
   • Organisatorisches: Übungsbetrieb, Scheinbedingungen, Klausurtermin, Gliederung der Vorlesung
   • Definition von Algorithmen und Datenstrukturen, Geschichte
   • Fundamentale Algorithmen: create, assign, copy, compare etc.
   • Fundamentale Datenstrukturen: Zahlen, Container, Handles
2. Container (10.4.2008)
   • Anforderungen von Algorithmen an Container
   • Einteilung der Container
   • Grundlegende Container: Array, verkettete Liste, Stack und Queue
   • Ranges in Containern
3. 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
4. Korrektheit (23. und 24.4.2008)
   • Definition von Korrektheit, Algorithmen-Spezifikation
   • Korrektheitsbeweise versus Testen
   • Programming by contract, Vor- und Nachbedingungen, Invarianten
   • Testen, Execution paths, Unit Tests in Python
   • Ausnahmen (exceptions) und Ausnahmebehandlung in Python
5. 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
6. 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
7. Prioritätswarteschlangen (14.5.2008)
   • Heap-Datenstruktur
   • Einfüge- und Löschoperationen
   • Heapsort
   • Komplexität des Heaps
8. Dictionaries (15.5.2008)
   • Implementation mit Bäumen
   • Hashing
   • Implementation als Hashtabelle
9. Iteration versus Rekursion (21.5.2008)
   • Typen der Rekursion und ihre Umwandlung in Iteration
   • Iteratoren
10. Generizität (28.und 29.5.2008)
    • Abstrakte Datentypen, Typspezifikation
    • Required Interface versus Offered Interfvace
    • Adapter und Typattribute, Funktoren
    • Beispiel: Algabraische Konzepte und Zahlendatentypen
    • Operator overloading in Python

Getting started

• Wiki Hilfe (für alle, die Seiten ändern wollen)
• MediaWiki Manual (für Administratoren)
• Sandbox (zum ungefährlichen Ausprobieren von Änderungen)