Algorithmik

Die Studierenden können praktische Problemstellungen durch effiziente Algorithmen lösen, indem sie

• die Problemstellung formal beschreiben und charakterisieren,
• für die Problemstellung geeignete Datenstrukturen zur Speicherung von Daten auswählen,
• einen effizienten Algorithmus auswählen und implementieren und
• die Laufzeit und den Speicherbedarf des Algorithmus analysieren,

um später komplexe Probleme durch Algorithmen in möglichst geringer Laufzeit und geringem Speicherbedarf lösen zu können.

• Laufzeitanalyse durch Asymptotische Notation
• Abstrakte Datentypen:
  • Liste, Stapel, Warteschlange, Tabelle
  • Prioritätswarteschlange
• Datenstrukturen:
  • Array, Verkettete Liste
  • Hashtabelle
  • Binäre Suchbäume
  • AVL Baum
  • Heap
• Graphen:
  • Kürzeste Pfade
  • Topologisches Sortieren
  • Minimale Spannbäume
  • ADT Disjunkter Mengen
• Entwurf von Algorithmen:
  • Insertionsort, Selectionsort, Mergesort, Quicksort, Heapsort, etc.
  • Greedy Algorithmen
  • Dynamische Programmierung
  • Caching

Präsentation, Übung

• Thomas Cormen, Charles E. Leiserson, Ronald E. Rivest, Clifford Stein. Algorithmen - Eine Einführung. De Gruyter Oldenbourg. 2013 4. Auflage ISBN-13: 978-3486748611
• Sara Baase, Allen Van Gelder. Computer Algorithms. 3rd Edition Addison Wesley 2000, ISBN: 0201612445
• Michael T. Goodrich, Roberto Tamassia. Algorithm Design. Wiley 2002. ISBN 0471383651