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!
    (Die Defintion von eulersch ist nun in Definition 2.2.
    Die Definition von Rang k wurde an die Vorlesung angepasst.
    Es gab einen Fehler in Abbildungen 3.9 und 3.10: Hier dürfen keine Mengenklammern genutzt werden. Stand: 31.01.20 09:36 Uhr)
  • 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

Für alle Hausaufgaben gelten die Punkte auf dem Hinweiszettel.

  • Blatt 0a: HIER. Dieses muss nicht abgegeben werden und wird in der ersten kleinen Übung (in der Woche ab 11.11.19) besprochen.
  • Blatt 1: HIER. Abgabe bis 18.11.19, 10:00 Uhr.
  • Blatt 2: HIER. Abgabe bis 02.12.19, 10:00 Uhr.
  • Blatt 3: HIER. Abgabe bis 16.12.19, 10:00 Uhr.
  • Blatt 4: HIER. Abgabe bis 13.01.20, 10:00 Uhr.
    Es gab zwei kleinere Fehler in Algorithmus 2 (rechts). Sie sind mittlerweile behoben. Bitte ladet das Blatt erneut herunter. (Stand: 18.12.19, 13:48 Uhr)
  • Blatt 5: HIER. Abgabe bis 27.01.20, 10:00 Uhr.
    Es gab zwei kleine Änderungen: (1) Algorithmus 1 besitzt nun am Anfang eine if-Bedingung, (2) die dritte Rekursionsgleichung in Hausaufgabe 2 wurde korrigiert (statt -17n steht dort nun +17n). (Stand: 14.01.20, 10:22 Uhr)

Merkzettel: Pseudocode, Beweistechniken, Wachstum von Funktionen.

Vorlesung 0

  • Datum: Dienstag, 29.10.2019
  • Inhalt: Einstieg und Überblick
  • Folien: HIER (PDF, 2MB)