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)

Mengen Hashing Dictionaries als Baum und als Hashtabelle Iteration vs. Rekursion Typen der Rekursion und ihre Umwandlung in Iteration Iteratoren Übungen zu Rekursion und Iteration: Fakultät, Koch-Schneeflocke, Auflösung rekursiver Formeln, Umwandlung von Rekursion in Iteration Fronleichnam Abstrakte Datentypen Generizität: Required Interface, Adapter und Typattribute Funktoren (Beispiel: Ordnung für Sortieren) Übungen zur Generizität: Sortieren mit veränderter Ordnung, Adapterklassen Zahlendatentypen und Arithmetik, Byteorder, IEEE floating point Algebraische Konzepte Operator Overloading, Anwender-definierte Zahlentypen (z.B mit physikalischen Einheiten)

Getting started

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