Grundlagen: Algorithmen und Datenstrukturen - IN0007
Administrativa
- Vorlesung: PD Dr. Tobias Lasser
- Dienstag, 14:15 - 15:45
- MW 0001 (Gustav-Niemann-Hörsaal)
- Mittwoch, 13:20 - 14:05
- MW 0001 (Gustav-Niemann-Hörsaal)
Kontakt
- Erste Anlaufstelle: die Tutoren Ihrer Übungsgruppe
- Fragen und Antworten: Piazza Forum (access code 'gad')
- Für alles andere: Kontakt-Email der Übungsleitung
Materialien
Aktuelles
- Stellen Sie sicher, dass Sie zu einer der Übungsgruppen in TUMonline angemeldet sind. Nur so haben Sie Zugriff 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.
