Grundlagen: Algorithmen und Datenstrukturen

Administrativa

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

• Organisatoren:
  • Vorlesungen: Tobias Lasser
  • Übungen: Bernhard Radke, Christoph Anneser, Sebastian Wolf
• Kontakt:
  • Chat-Plattform https://chat.ciip.in.tum.de (Login mit TUM ID)
  • in Ausnahmefällen: via Email
• Termine:
  • Vorlesung: Dienstags, 14:15 - 15:45, via via Livestream
  • Vorlesung: Mittwochs, 13:20 - 14:05, via via Livestream
  • Übungen: in Gruppen, siehe TUMonline und Moodle
• Erste Vorlesung: 22. April 2020
• Prüfungen:
  • reguläre Prüfung: 3. August 2020, 14:15 - 15:45
  • Wiederholungsprüfung: 7. Oktober 2020, 14:15 - 15:45
• Kurssprache: Deutsch
• Tutorübungen: timetable.pdf

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).
Zur Kontaktaufnahme benutzen Sie bitte die Chat-Plattform https://chat.ciip.in.tum.de (Login mit TUM ID).