Main Page

Vorlesung Algorithmen und Datenstrukturen

apl. Prof. Dr. Ullrich Köthe, Universität Heidelberg, Sommersemester 2020

Die Vorlesung findet dienstags um 14:15 Uhr und donnerstags um 16:15 Uhr online auf Discord und Twitch statt. Die Links haben in Müsli angemeldete Teilnehmer per Email erhalten.

Klausur und Nachprüfung

Der Termin der Abschlussklausur steht noch nicht fest.

Übungsbetrieb

• Die Übungsgruppen werden über MÜSLI verwaltet.
• Übungsblätter werden auf Moodle veröffentlicht.

Literatur

• R. Sedgewick: Algorithmen (empfohlen für den ersten Teil, bis einschließlich Graphenalgorithmen)
• J. Kleinberg, E.Tardos: Algorithm Design (empfohlen für den zweiten Teil, einschließlich Graphenalgorithmen)
• T. Cormen, C. Leiserson, R.Rivest: Algorithmen - eine Einführung (empfohlen zum Thema Komplexität)
• Wikipedia und andere Internetseiten (sehr gute Seiten über viele Algorithmen und Datenstrukturen)

Gliederung der Vorlesung

(Termine werden nach und nach aktualisiert)

1. Einführung (21. und 23.4.2020)
   • Definition von Algorithmen und Datenstrukturen, Geschichte
   • Fundamentale Algorithmen: Konstruktoren, Kopierfunktionen, swap.
   • Fundamentale Datenstrukturen: Zahlen, Container, Handles
   • Python-Grundlagen
2. Container (28.4.2020)
   • Abstrakte Datentypen und algebraische Spezifikation
   • Grundlegende Container: Array, Stack, Queue, assoziatives Array
3. Sortieren (some day in 2020)
   • Spezifikation des Sortierproblems
   • Selection Sort und Insertion Sort
   • Merge Sort
   • Quick Sort und seine Varianten
   • Anzahl der benötigten Vergleiche
4. Korrektheit (29.4. und 6.5.2014 -- ab hier altes Datum)
   • 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
5. Effizienz (8. und 13.5.2014)
   • Laufzeit und Optimierung: Innere Schleife, Caches, locality of reference
   • Laufzeit versus Komplexität
   • Landausymbole (O-Notation, <math>\Omega</math>-Notation, <math>\Theta</math>-Notation), Komplexitätsklassen
   • Bester, schlechtester, durchschnittlicher Fall
   • Amortisierte Komplexität
6. Suchen (15. und 20.5.2014)
   • Sequentielle Suche
   • Binäre Suche in sortierten Arrays, Medianproblem
   • Suchbäume, balancierte Bäume
   • selbst-balancierende Bäume, Rotationen
   • Komplexität der Suche
7. Sortieren in linearer Zeit (22.5.2014)
   • Permutationen
   • Sortieren als Suchproblem
   • Bucket Prinzip, Bucket Sort
8. Prioritätswarteschlangen (27.5.2014)
   • Heap-Datenstruktur
   • Einfüge- und Löschoperationen
   • Heapsort
   • Komplexität des Heaps
9. Assoziative Arrays (3.6.2014)
   • Datenstruktur-Dreieck für assoziative Arrays
   • Definition des abstrakten Datentyps
   • JSON-Datenformat
   • Realisierung durch sequentielle Suche und durch Suchbäume
10. Hashing und Hashtabellen (5. und 10.6.2014)
    • Implementation assoziativer Arrays mit Bäumen
    • Hashing und Hashfunktionen
    • Implementation assoziativer Arrays als Hashtabelle mit linearer Verkettung bzw. mit offener Adressierung
    • Anwendung des Hashing zur String-Suche: Rabin-Karp-Algorithmus
11. Iteration versus Rekursion (12.6.2014)
    • Typen der Rekursion und ihre Umwandlung in Iteration
    • Auflösung rekursiver Formeln mittels Master-Methode und Substitutionsmethode
12. Generizität (17.6.2014)
    • Abstrakte Datentypen, Typspezifikation
    • Required Interface versus Offered Interface
    • Adapter und Typattribute, Funktoren
    • Beispiel: Algebraische Konzepte und Zahlendatentypen
    • Operator overloading in Python
13. Graphen und Graphenalgorithmen (24.6. bis 10.7.2014)
    • Einführung
    • Graphendatenstrukturen, Adjazenzlisten und Adjazenzmatrizen
    • Gerichtete und ungerichtete Graphen
    • Vollständige Graphen
    • Planare Graphen, duale Graphen
    • Pfade, Zyklen
    • Tiefensuche und Breitensuche
    • Zusammenhang, Komponenten
    • Gewichtete Graphen
    • Minimaler Spannbaum
    • Kürzeste Wege, Best-first search (Dijkstra)
    • Most-Promising-first search (A*)
    • Problem des Handlungsreisenden, exakte Algorithmen (erschöpfende Suche, Branch-and-Bound-Methode) und Approximationen
    • Erfüllbarkeitsproblem, Darstellung des 2-SAT-Problems durch gerichtete Graphen, stark zusammenhängende Komponenten
14. Randomisierte Algorithmen (10. und 15.7.2014)
    • Zufallszahlen, Zyklenlänge, Pitfalls
    • Zufallszahlengeneratoren: linear congruential generator, Mersenne Twister
    • Randomisierte vs. deterministische Algorithmen
    • Las Vegas vs. Monte Carlo Algorithmen
    • Beispiel für Las Vegas: Randomisiertes Quicksort
    • Beispiele für Monte Carlo: Randomisierte Lösung des k-SAT Problems
    • RANSAC-Algorithmus, Erfolgswahrscheinlichkeit, Vergleich mit analytischer Optimierung (Methode der kleinsten Quadrate)
15. Greedy-Algorithmen und Dynamische Programmierung (17.7.2014)
    • Prinzipien, Aufwandsreduktion in Entscheidungsbäumen
    • bereits bekannte Algorithmen: minimale Spannbäume nach Kruskal, kürzeste Wege nach Dijkstra
    • Beispiel: Interval Scheduling Problem und Weighted Interval Scheduling Problem
    • Beweis der Optimalität beim Scheduling Problem: "greedy stays ahead"-Prinzip, Directed Acyclic Graph bei dynamischer Programmierung
16. NP-Vollständigkeit (22.7.2014)
    • die Klassen P und NP
    • NP-Vollständigkeit und Problemreduktion
17. Wiederholung (24.7.2014)

Übungsaufgaben

(im PDF Format). Die Abgabe erfolgt am angegebenen Tag bis 14:00 Uhr per Email an den jeweiligen Übungsgruppenleiter. Bei verspäteter Abgabe bis zu drei Tagen werden noch 50% der erreichten Punkte angerechnet. Danach wird die Musterlösung freigeschaltet.

Die Übungsaufgaben sind zur Zeit nicht freigeschaltet.

Sonstiges

• Gnuplot Kurztutorial
• Git Kurztutorial
• mögliche neue Startseite