Grundlagen: Algorithmen und Datenstrukturen

Administrativa

Vorlesung mit Übungen für Bachelor-Studenten (IN0007).

  • Organisatoren:
  • Kontakt: via Email (bitte alle Anfragen nur an diese Adresse richten)
  • Termine:
    • Vorlesung: Dienstags, 14:15 - 15:45, MW 2001 und MI Hörsaal 1 (Video-Übertragung)
    • Vorlesung: Mittwochs, 13:20 - 14:05, MW 2001 und MI Hörsaal 1 (Video-Übertragung)
    • Übungen: in Gruppen, siehe TUMonline
  • Erste Vorlesung: 21. April 2020
  • Klausuren: (to be announced)
  • Kurssprache: Deutsch

Inhaltsübersicht

  • Grundlagen Algorithmen und Datenstrukturen
  • Komplexitätsanalyse (Effizienmaße, Landau-Symbole, Maschinenmodell)
  • Datenstrukturen für Sequenzen (Arrays, Listen, Stacks, Queues)
  • Hashing (Verkettung, universelles Hashing, Sondierverfahren, perfektes Hashing)
  • Sortieren (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äsentationen, Traversierung mit BFS und DFS, Zusammenhang, topologische Sortierung, kürzeste Wege, minimale Spannbäume)
  • Pattern Matching (naive Suche, KMP Algorithmus)
  • optional: Datenkompression (Huffman Codes, Lempel-Ziv Verfahren)

Kursmaterialien

Alle Materialien werden über Moodle bereitgestellt (Zugang beschränkt auf Kursteilnehmer, Registrierung via TUMonline).