zur Kursübersicht

Theoretische Informatik 1 - Vorlesungsskript

Bachelor-Studium Informatik

Dominik Scheder, TU Chemnitz

Diese Vorlesung führt Sie ein in die Themen der Algorithmen, Datenstrukturen und asymptotischer Laufzeitanalyse.
  1. Einführung
    1. Suchen und Sortieren
      1. Binäre Suche
      2. Maximum finden in unimodalen Arrays
      3. Naive Sortieralgorithmen
      4. Mergesort
      5. Heapsort
      6. Quicksort
      7. Quickselect
      8. Deterministisches Auswählen: Median-of-Medians
    2. Laufzeitabschätzung mit O und Ω
      1. Numerische Experimente und Grenzwerte
      2. Formale Definition von O und Ω
    3. Einfügen, Suchen, Löschen: ein paar Datenstrukturen
      1. Hintergrund: der Speicherplatz im Rechner
      2. Beschränkter Zugriff: Stack und Queue
      3. Binäre Suchbäume
      4. Treaps: Zufällige Einfüge-Reihenfolge simulieren
      5. B-Bäume
      6. Rot-Schwarz-Bäume
      7. Hashtabellen
    4. Arithmetische Algorithmen
      1. Einfache Operationen
      2. Schnelle Matrix-Exponentiation
      3. Multiplikation
      4. Polynommultiplikation und die schnelle Fourier-Transformation
    5. Graphen
      1. Beispiele, Definitionen, Repräsentierung
      2. Zusammenhang, Kreise finden, Tiefensuche, Breitensuche
      3. Gerichtete Graphen
      4. Topologisches Sortieren
      5. Starke Zusammenhangskomponenten
    6. Graphen mit Kantenkosten
      1. Kürzeste Wege: Dijkstras Algorithmus
      2. Kürzeste Wege mit positiven und negativen Kosten: der Bellman-Ford-Algorithmus
      3. Minimale Spannbäume und Kruskals Algorithmus
      4. Union-Find-Datenstrukturen
      5. Union by Rank
      6. Union by Rank with Path Compression
    7. Netzwerkflüsse
      1. Netzwerkflüsse: Beispiele und Definitionen
      2. Die Ford-Fulkerson-Methode
      3. Effiziente Algorithmen für Max Flow: Edmons-Karp und Dinic
      4. Anwendungen von Netzwerkflüssen