BIN302: Algorithmen und Datenstrukturen

Lernpfad Informatisches Denken und Konzepte

BIN302: Algorithmen und Datenstrukturen

Kurzporträt BIN302: Algorithmen und Datenstrukturen
Worum geht es? Das Modul behandelt grundlegende Verfahren zur Organisation und Verarbeitung von Daten. Die Studierenden lernen wichtige Datenstrukturen, Such- und Sortierverfahren, Entwurfsmethoden und Graphalgorithmen kennen. Dabei steht immer auch die Frage im Mittelpunkt, ob eine Lösung korrekt und wie effizient sie ist.
Wofür braucht man es? Algorithmen und Datenstrukturen sind eine Kernkompetenz für Softwareentwicklung, Datenverarbeitung, Simulation, Optimierung und technische Systemgestaltung. Wer geeignete Datenstrukturen auswählt und Aufwände beurteilt, kann Programme robuster und skalierbarer entwickeln. Die Kompetenzen werden in vielen späteren Informatikmodulen vorausgesetzt.
Wieso ist es interessant? Eine gute Idee allein reicht nicht. Entscheidend ist auch, wie diese Idee konkret umgesetzt wird. Das Modul macht sichtbar, warum scheinbar kleine Entwurfsentscheidungen große Auswirkungen auf Laufzeit und Speicherbedarf haben. Dadurch entsteht ein technischer Blick für elegante und tragfähige Problemlösungen.
Modulverantwortung

Prof. Dr. Jochen Rethmann

Lehrperson(en)

Prof. Dr. Jochen Rethmann

Verwendbarkeit

Bachelor Informatik

Fächergruppe

Informatik

Modultyp
Pflicht
Sprache

Deutsch

Angebot

Sommersemester

Dauer

1 Semester

Credits

5 ECTS

Benotung

Deutsche Notenskala 1-5

SWS

2 V | 2 Ü | - P | - S

Workload
Präsenzstudium: 45 Std. Selbststudium: 90 Std.
Engl. Titel

Algorithms and Data Structures

Empfohlene Voraussetzungen
  • BIN004: Einführung in die Programmierung: Variablen, Kontrollstrukturen, Funktionen, einfache Datenstrukturen.
  • BIN003: Mathematik-Grundlagen der Informatik: mathematische Verfahren, logisches Denken, Beweise.
Lernergebnisse / Kompetenzen
WAS

Mit erfolgreichem Abschluss des Moduls sind die Studierenden in der Lage, für typische algorithmische Problemstellungen geeignete, korrekte und effiziente Lösungen unter Verwendung angemessener Datenstrukturen systematisch zu entwickeln.

WOMIT

Die Studierenden erreichen dieses Lernergebnis, indem sie

  • Problemstellungen abstrahieren und mithilfe geeigneter abstrakter Datentypen und Datenstrukturen modellieren,
  • Datenstrukturen anhand ihrer Operationen sowie ihres Zeit- und Speicherbedarfs untersuchen und auswählen,
  • grundlegende Entwurfsparadigmen auf algorithmische Problemstellungen anwenden,
  • die Korrektheit einfacher Algorithmen insbesondere mithilfe von Invarianten begründen,
  • iterative und rekursive Algorithmen asymptotisch sowie experimentell analysieren,
  • Algorithmen und Datenstrukturen beschreiben, programmieren und testen,
  • typische Operationen wie Suchen, Einfügen und Löschen beispielhaft für Datenstrukturen durchführen,
  • Lösungsalternativen unter Berücksichtigung von Laufzeit, Speicherbedarf, Eingabeeigenschaften und Implementierungsaufwand bewerten.
WOZU

Die Studierenden nutzen diese Kompetenzen, um softwarebasierte Problemlösungen hinsichtlich Effizienz und Skalierbarkeit fachlich fundiert einschätzen und gestalten zu können. Dies unterstützt spätere Module und Projekte, in denen Datenmengen, Ressourcenbedarf oder algorithmische Korrektheit eine zentrale Rolle spielen.

Inhalte
  • Datenstrukturen: Arrays, Stacks, verkettete Listen, Bäume, Hash-Tabellen, Heaps und Warteschlangen
  • Komplexität und asymptotische Aufwandsabschätzung
  • Landau-Symbole und grundlegende Komplexitätsklassen
  • Entwurfsmethoden: Divide und Conquer, Greedy, dynamische Programmierung, Backtracking und Branch and Bound
  • Sortierverfahren: Quicksort, Mergesort, Heapsort, Radixsort, Bucketsort sowie untere Schranken
  • Graphalgorithmen: Breitensuche, Tiefensuche, minimale Spannbäume, kürzeste Wege
Prüfungsvorleistung

Keine angegeben.

Prüfungsleistung

Klausurarbeit (120 Minuten).

Literatur
  • Thomas Ottmann; Peter Widmayer: Algorithmen und Datenstrukturen. 5. Auflage, Spektrum Akademischer Verlag, 2012.
  • Thomas H. Cormen; Charles E. Leiserson; Ronald L. Rivest; Clifford Stein: Algorithmen: Eine Einführung. 4. Auflage, Oldenbourg Verlag, 2013.
  • Robert Sedgewick; Kevin Wayne: Algorithmen. 4. Auflage, Pearson Studium, 2014.
  • Volker Heun: Grundlegende Algorithmen. Vieweg+Teubner, 2008.