Hörerkreis:
Studierende im Bachelorstudium Informatik
Studierende im Bachelorstudium Bioinformatik
Studierende im Bachelorstudium Wirtschaftsinformatik
ECTS: 5 Punkte
Voraussetzungen:
Elementare Grundkenntnisse in Informatik
Empfehlenswert für:
Grundkenntnisse im Bereich Algorithmen, Bioinformatik
Welche Art Beziehung zwischen Eingabe und Laufzeit?
Amortisationsanalyse
Aggregatmethode
Bankkontomethode
Potenzialmethode
Dynamische Arrays
Elementare Datenstrukturen
Stacks und Queues
Vektoren, Listen und Sequenzen
Bäume
Definitionen
Baumtraversierung
Implementierungen von Bäumen
Priority Queues und Heaps
Definitionen
Sortieren mit Priority Queues
PQ-Implementierung mit Heaps
Bottom-Up Heap-Konstruktion
Wörterbücher und Hashing
Definitionen
Hashfunktion
Strategien zur Kollisionsauflösung
Universelles Hashing
Suchbäume
Binäre Suchbäume
AVL-Bäume
(a,b)-Bäume
Sortieralgorithmen
MergeSort
Eine untere Schranke für vergleichsbasiertes Sortieren
Weiterführende bzw. verwandte Vorlesungen:
Effiziente Algorithmen und Datenstrukturen
Skript:
Kein Skript.
Literatur:
Die Vorlesung folgt in weiten Teilen dem Buch:
Michael T. Goodrich, Roberto Tamassia. Algorithm Design: Foundations, Analysis, and Internet Examples.
John Wiley & Sons, Inc., Hoboken, NJ, 2002.
Volker Heun. Grundlegende Algorithmen: Einführung in den Entwurf
und die Analyse effizienter Algorithmen.
2. Auflage, Vieweg, Braunschweig-Wiesbaden, 2003.
Vertiefendes und ergänzendes Material zur Vorlesung findet sich in:
Thomas H. Cormen, Charles E. Leiserson, Ronald
L. Rivest, Clifford Stein. Introduction to Algorithms.
2. Auflage, MIT Press, Cambridge, MA, 2001.
Jon Kleinberg, Eva Tardos. Algorithm Design.
Pearson Education, Boston, MA, 2005.