Startseite

Algorithmen und Datenstrukturen

Die Vorlesung Algorithmen und Datenstrukturen ist eine Pflichtveranstaltung für Studierende der Informatik, Wirtschaftsinformatik, Informations- und Systemtechnik; außerdem ist sie wichtig und von Interesse für Studierende anderer Studiengänge, die mit Informatik zu tun haben.

Algorithmen sind das methodische Herz der theoretischen und praktischen Informatik; Datenstrukturen ermöglichen die effiziente Umsetzung von Algorithmen und den effizienten Zugriff auf Input- und Outputdaten. In dieser Einstiegsvorlesung werden die folgenden grundlegenden Begriffe erarbeitet:

  • Algorithmenbegriff
  • Graphen
  • Suche in Graphen
  • Korrektheit und Komplexität von Algorithmen
  • Datenstrukturen
  • Sortieren
  • Rekursionen

Literatur

  • Video: Der Videotrailer zur Vorlesung.
  • Skript: Zu dieser Vorlesung gibt es ein SKRIPT.
    Achtung: Das ist ein dünner (und farbloser) Ersatz für eine lebende Vorlesung!
    (Update 16.12.20: Tabelle 4.2 auf Seite 52 wurde korrigiert.
    Update 25.02.20: Laufzeit von Radixsort wurde korrigiert.)
  • Literaturempfehlung (englisch): Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein: Introduction to Algorithms, MIT Press, 2001
  • Literaturempfehlung (deutsch): Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein: Algorithmen – Eine Einführung, Oldenbourg Wissenschaftsverlag, 2010

Übungsblätter

Hausaufgaben

Für alle Hausaufgaben gelten die Punkte auf dem Hinweiszettel. Eine Liste mit den e-Mail-Adressen der Tutoren gibt es hier.

  • Blatt 1: HIER. Abgabe bis 16.11.20 20.11.20 (siehe Mailprobleme), 14:00 Uhr.
  • Blatt 2: HIER. Abgabe bis 30.11.20, 14:00 Uhr.
  • Blatt 3: HIER. Abgabe bis 14.12.20, 14:00 Uhr.
  • Blatt 4: HIER. Abgabe bis 18.01.21, 14:00 Uhr.
  • Blatt 5: HIER. Abgabe bis 01.02.21, 14:00 Uhr.

Merkzettel: PseudocodeBeweistechnikenWachstum von Funktionen.

Präsenzblätter

Diese Blätter werden nicht abgegeben und werden in den kleinen Übungen besprochen. Um gemeinsam an Dokumenten zu arbeiten bieten sich folgende Dienste an: Google Docs (Du kennst Alternativen? Lass es uns wissen, dann können wir die Liste erweitern!)

  • Blatt P0: HIER. (Besprechung: 09.11.20 – 13.11.20)
  • Blatt P1: HIER. (Besprechung: 23.11.20 – 27.11.20)
  • Blatt P2: HIER. (Besprechung: 07.12.20 – 11.12.20)
  • Blatt P3: HIER. (Besprechung: 11.01.21 – 15.01.21)
  • Blatt P4: HIER. (Besprechung: 25.01.21 – 29.01.21)
  • Blatt P5: HIER. (Besprechung: 08.02.21 – 12.02.21) (Update 10.02.21: Korrektur für Algorithmus 1, Zeile 14)

Quiz

Kapitel 1: [pdf]
Kapitel 2: [pdf]
Kapitel 3-1: [pdf]
Kapitel 3-2: [pdf]Fragen
Kapitel 4: [pdf]
Kapitel 5-1: [pdf]
Kapitel 5-2: [pdf]
Übungsquiz: [pdf]

Vorlesungen

  • Online-Prüfung Informationen
    Dieser Artikel enthält wichtige Informationen zur Durchführung der Klausur. Bitte vollständig und aufmerksam lesen.
  • Übung 8
    Die letzte große Übung von AuD mit Spiel, Spaß, Spannung und vielen Fragen.
  • Vorlesung 25
    Diese Vorlesung markiert das Ende der Vorlesungszeit. Es werden noch einmal einige Hinweise zur Klausur und Klausurvorbereitung gegeben. Zudem gab es noch einmal die Möglichkeit Fragen zu stellen.
  • Vorlesung 24
    In dieser Vorlesung beenden wir das Kapitel zum Thema Sortieralgorithmen und werfen abschließend einen Blick auf parallelisierte Sortierverfahren.
  • Übung 7
    In dieser Übung schauen wir uns noch einmal das Sortierverfahren Quicksort an und sprechen über die Berechnung von Medianen. Außerdem schauen wir uns mit den kd-Bäumen eine spezielle Datenstruktur für mehrdimensionale Daten an.
  • Vorlesung 23
    In dieser Vorlesung beschäftigen wir uns mit Sonderfällen für Sortieralgorithmen, durch die Sortieren in linearer Zeit ermöglicht wird.
  • Vorlesung 22
    In dieser Vorlesung beschäftigen wir uns mit Medianen.
  • Vorlesung 21
    In dieser Vorlesung kehren wir zurück zu Sortieralgorithmen und stellen den Quicksort-Algorithmus vor.
  • Vorlesung 20
    In dieser Vorlesung haben wir einen Exkurs in die nichtlineare Rekursion gemacht.
  • Übung 6
    Wir betrachten ein weiteres Beispiel für Mergesort und leiten erneut die Laufzeit des Sortieralgorithmus her, indem das Master-Theorem benutzt wird. Außerdem betrachten wir einen weiteren Sortieralgorithmus: Heapsort.