Anmelden

Modulbeschreibung

Skip Navigation LinksTHUDEModulbeschreibung

Algorithmen u. Datenstrukturen

Inhalt

  • Analyse von Algorithmen: Korrektheit, Terminierung, Laufzeitanalyse, asymptotische Notation, amortisierte Analyse

  • Effizientes Sortieren: effiziente vergleichsbasierte Verfahren (Heapsort, Mergesort, Quicksort), untere Schranke f. vergleichsbasiertes Sortieren, nicht vergleichsbasierte Sortierverfahren (Bucketsort, Radixsort)

  • Einfache Datenstrukturen: Abstrakte Datentypen, Stack, Warteschlange, Prioritgesort, Quicksort

  • Hashverfahren: Hashfunktionen, Kollisionsauflösung mit Verkettung der Ãœberläufer und mit Sondierung, dynamisches Hashing

  • Bäume: AVL-Bäume, B-Bäume, Rot-Schwarz-Bäume, selbstorganisierende Bäume (Splay-Trees), digitale Bäume (Tries)

  • Graphenalgorithmen: Breiten- und Tiefen-Suche, Zyklenerkennung, topologische Sortierung, kürzeste Wege (Bellman-Ford, Dijkstra), minimale Spannbäume (Kruskal, Prim), Flüsse in Netzwerken (Ford-Fulkerson), bipartites Matching

  • Entwurfsmethoden: Divide and Conquer, Greedy-Verfahren, Backtracking, Dynamisches Programmieren, Randomisierte Algorithmen

  • Ausblick: Komplexitätsklassen P, NP, NP-Vollständigkeit

Lernergebnisse

Nach Abschluss des Moduls können die Studierenden

Fachkompetenz

  • wichtige Algorithmen und Datenstrukturen für das Sortieren, für das Suchen und für graphbasierte Problemstellungen erklären und anwenden

  • beurteilen, welche Auswirkungen die Wahl von Datenstrukturen auf die Effizienz von Algorithmen hat

  • die Grenzen für die algorithmische Lösbarkeit von Problemen erläutern

Methodenkompetenz

  • grundlegende algorithmische Problemstellungen in Anwendungsproblemen erkennen und geeignete Algorithmen und Datenstrukturen dafür auswählen

  • Techniken für die Laufzeitabschätzung von Algorithmen anwenden

  • eigene effiziente Algorithmen auf der Basis allgemeiner Entwurfsmethoden entwickeln

Sozial- und Selbstkompetenz

  • Problemstellungen und Lösungsvorschläge mit Fachexperten diskutieren

ECTS

5 Punkte

Studien- und Prüfungsleistungen

Prüfungsleistungen:
  • Algorithmen und Datenstrukturen (90 min, Klausur)
Studienleistungen:
  • Algorithmen und Datenstrukturen (Laborarbeit)

Lehr- und Lernformen

  • Algorithmen und Datenstrukturen (3 SWS, Vorlesung)
  • Algorithmen und Datenstrukturen (1 SWS, Labor)

Studiengänge

  • Elektrotechnik und Informationstechnik(ET) - Wahlpflichtmodul
  • Computer Science International Bachelor(ICS) - Pflichtmodul
  • Informatik(INF) - Pflichtmodul
  • Medizintechnik(MT) - Wahlpflichtmodul

Modulverantwortliche

Prof. Dr.-Ing. Georg Schied

Dozenten

Prof. Dr.-Ing. Georg Schied, Prof. Dr. Alfred Franz

Literatur

T.H. Corman, et. al.. Algorithmen. Oldenbourg, 2010. ISBN 978-3486582628.
Ottman und Widmayer. Algorithmen und Datenstrukturen. Spektrum, 2002. ISBN 978-3827410290.
G. Saake, K.-U. Sattler. Algorithmen und Datenstrukturen. dpunkt.verlag, 2006. ISBN 3-89864-385-9.
Steven S. Skiena. The Algorithm Design Manual. 978-1-84800-069-8, 2008.

Quicklinks