- Wintersemester 2023/24

Kontakt und Sprechstunden

Dominik Scheder

Haus G II, Zimmer 105

vorname.nachname@gmail.com

Kontaktieren Sie mich persönlich oder per E-Mail oder kommen einfach auf Verdacht vorbei

Algorithmen und Komplexität im Modulkatalog

Hier ist AuK im Wintersemester 2022.

Prüfung

Prüfungsvorleistung (VT) als Voraussetzung zur Teilnahme an der mündlichen Prüfung (20 Minuten).

  • Vorleistung: Bearbeiten Sie die Testataufgaben in Kapitel 8 und geben Sie sie bis zum Donnerstag, den 1. Februar 2024 bei mir ab (per Email).
  • Prüfung: 5. Februar 2024.

Schwerpunktliste für die mündliche Prüfung

Ein paar Worte zum Ablauf der Prüfung: ich werde je Teilnehmer/-in circa. drei Problemstellungen vorbereiten. Pro Problemstellung were ich, angefangen von einer vergleichsweise einfachen Einstiegsfrage zu komplexeren fortschreiten.
  • Suchen und Sortieren. Binäre Suche. Die drei "guten" Sortieralgorithmen Mergesort, Quicksort, Heapsort. Binäre Suchbäume und wie man erreicht, dass sie einigermaßen balanciert sind (z.B. Treaps).
  • Komplexität arithmetischer Operationen. Addition, Multiplikation, Exponentiation.
  • Grundlegende Graphenalgorithmen. Tiefensuche, Breitensuche, topologisches Sortieren. Konzepte wie Zusammenhangskomponenten (und in Digraphen starke Zusammenhangskomponenten).
  • Weiterführende Graphenalgorithmen. Kürzeste Pfade (Dijkstra) und leichteste Spannbäume (Dijkstra, Kruskal). Hilfs-Datentypen wie Union-Find. Der Bellman-Ford-Algorithmus zum finden billigster Wege in Graphen, wo Kanten mit negativen Kosten erlaubt sind. Der Edit-Distanz-Problem.
Generell sollten Sie in der Lage sein, für einen Algorithmus die Laufzeit mit \(O\)- und \(\Omega\) zu bestimmen und zu erkennen, ob Bit-Komplexität (Darstellungslänge von Zahlen) eine Rolle spielen könnte.

Literatur

  • Algorithmen und Komplexität. Wagenknecht, Christian. Leipzig: Fachbuchverlag im Hanser Verlag München, 2003.
  • Introduction to Algorithms bzw. Algorithmen - eine Einführung von Cormen, Leiserson, Rivest und Stein (im Volksmund einfach CLRS genannt). Wenn Sie sich im Hochschulnetz befinden, können Sie bei de Gruyter auf eine pdf-Version zugreifen. .

Algorithmen und Komplexität in früheren Jahren:

Webseite des Kurses unter meinem Vorgänger Professor Christian Wagenknecht