Learning Outcomes
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.
Inhalt
- 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
Methoden
Präsentation, Übung
Literatur
- 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