Grundlagen: Algorithmen und Datenstrukturen - IN0007
Administrativa
- Vorlesung: PD Dr. Tobias Lasser
- Dienstag, 14:15 - 15:45
- MW 0001 (Gustav-Niemann-Hörsaal)
- 102 (Interims Hörsaal 2) - Video-Übertragung
- Mittwoch, 13:20 - 14:05
- MW 0001 (Gustav-Niemann-Hörsaal)
- 101 (Interims Hörsaal 1) - Video-Übertragung
Kontakt
Materialien
Aktuelles
- Stellen Sie sicher, dass Sie zu einer der Übungsgruppen in TUMonline angemeldet sind. Nur so haben Sie Zugriff auf Moodle, also auf die Materialien zu Vorlesung und Übung, sowie die Hausaufgabenabgabe.
Inhalts-Übersicht
- Grundlagen Algorithmen und Datenstrukturen
- Komplexitätsanalyse (Effizienzmaße, Landau-Symbole, Maschinenmodell)
- Datenstrukturen für Sequenzen (Arrays, Listen, Stacks, Queues)
- Hashing (Verkettung, universelles Hashing, Sondierverfahren, perfektes Hashing)
- Sortieren (Einfache Verfahren wie SelectionSort, InsertionSort, MergeSort, QuickSort, untere Schranke für vergleichsbasiertes Sortieren, Rang-Selektion, RadixSort, externes Sortieren)
- Priority Queues (binäre Heaps, Binomialheaps)
- Suchstrukturen (binäre Suchbäume, AVL-Bäume, (a,b)-Bäume)
- Graphen (Repräsentation, Traversierung mit BFS und DFS, Zusammenhang, topologische Sortierung, kürzeste Wege, minimale Spannbäme)
- Pattern Matching (naive Suche, KMP Algorithmus)
- Optional: Datenkompression (Huffman Codes, Lempel-Ziv Verfahren)
Literatur
- Mehlhorn, Sanders: Algorithms and Data Structures - The Basic Toolbox_. Springer, 2008.
- Cormen, Leiserson, Rivest, Stein: Algorithmen - Eine Einführung. Oldenbourg, 2010.
- Goodrich, Tamassia: Algorithm Design: Foundations, Analysis and Internet Examples. John Wiley & Sons, 2003.
- Heun: Grundlegende Algorithmen. Einführung in den Entwurf und die Analyse effizienter Algorithmen. Vieweg+Teubner, 2003.
- Kleinberg, Tardos: Algorithm Design. Pearson Education, 2013.
- Schöning: Algorithmik. Spektrum, 2011.
- Sedgewick: Algorithmen in Java, Pearson Studium, 2003.
