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, wie korrekt und effizient eine Lösung ist.
Wofür braucht man es? Algorithmen und Datenstrukturen sind eine Kernkompetenz für Softwareentwicklung, Datenverarbeitung, Simulation, Optimierung und technische Systemgestaltung. Wer geeignete Strukturen 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? Oft entscheidet nicht nur die Idee einer Lösung, sondern ihre konkrete Struktur darüber, ob ein Programm bei großen Datenmengen noch praktikabel ist. 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 and Conquer, Greedy, dynamische Programmierung, Branch and Bound und Backtracking
  • Suchverfahren: binäre Suche, Interpolationssuche, Suchbäume und Hashverfahren
  • Sortierverfahren: Quicksort, Mergesort, Heapsort, Radixsort sowie untere und obere Schranken
  • Graphalgorithmen: Breitensuche, Tiefensuche, minimale Spannbäume, kürzeste Wege, TSP, Planarität, Färbungen und maximaler Fluss
Prüfungsvorleistung

Keine angegeben.

Prüfungsleistung

Klausurarbeit (120 Minuten).

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