Algorithmen und Datenstrukturen (CS1001-KP08)

Dozent:
Prof. Dr. rer. nat. Ralf Möller

Übungsbetreuung:
Magnus Bender

Inhalt (für pptx sollte der Font Myriad Pro installiert sein):

  1. Einführung
    Algorithmen, Summenbildung, Entwurfsmuster: schrittweises Abarbeiten (linearer Aufwand), Berechnung mit konstantem Aufwand,Verkleinerungsprinzip: Sortieren durch Einfügen, Sortieren durch Auswählen, Problemkomplexität, Algorithmenanalyse: asymptotische Komplexität eines Algorithmus (O-Notation) (pdf, pptx)
  2. Sortierung durch Teile und Herrsche, Algorithmenanalyse
    Entwurfsmuster Teile-und-Herrsche: Mergesort, Quicksort, Omega- und Theta-Notation, Heaps als Datenstrukturen, Heapsort (pdf, pptx)
  3. Sortierung durch Verteilen
    Counting Sort, Mehrkriteriensortierung durch stabile Sortierverfahren, Radix-Sort, Bucket-Sort, Wiederholung: Listen, Keller, Schlangen (pdf, pptx)
  4. Prioritätswarteschlangen
    Realisierung mit binären Heaps, Binomial-Heaps und Fibonacci-Heaps, amortisierte Analyse (pdf, pptx, 19.5.23 mp4)
  5. Selektion
    K-Kleinstes Element (pdf, pptx)
  6. Mengen
    Selbstorganisierende Datenstrukturen, binäre Suchbäume, Iteratoren und Navigationsstrukturen, Ausgeglichenheit, Splay-Bäume, Rot-Schwarz-Bäume, AVL-Bäume (pdf, pptx)
  7. Mengen von Zeichenketten
    Tries, PATRICIA Tries (pdf, pptx)
  8. Disjunkte Mengen
    Union-Find-Datenstrukturen (pdf, pptx)
  9. Assoziation von Objekten
    Hash-Tabellen, Dynamisches Hashing (Kollisionslisten, Lineare Sondierung, Quadratische Sondierung, Doppeltes Hashing), Statisches Hashing, Familie universeller Hashfunktionen (pdf, pptx)
  10. Graphen
    Operationen auf Graphen, Graphrepräsentationen, Breiten- und Tiefensuche, Zusammenhangskomponenten, Kürzeste Wege, Single-Source-Shortest-Paths (Dijkstras Algorithmus, A*-Algorithmus, Bellman-Ford-Algorithmus), All-Pairs-Shortest-Paths, Transitive Hülle, Minimaler Spannbaum (Kruskals Algorithmus, Jarnik-Prim-Algorithmus), Netzwerkflüsse (Ford-Fulkerson-Algorithmus, Edmonds-Karp-Algorithmus), Bipartites Matching (pdf, pptx)
  11. Suchgraphen für Spiele
    Minimax-Suche, Suchraumaufbau, Alpha-Beta-Pruning zur Suchraumbeschneidung (pdf, pptx)
  12. Dynamische Programmierung, Gierige Verfahren
    Optimierungsprobleme, Sequenz-Alignment (Longest-Common-Subsequence, LCS), Rucksackproblem, Planungs- und Anordnungsprobleme, Wechselgeldbestimmung, Vollständigkeit von Algorithmen (pdf, pptx)
  13. Zeichenkettenabgleich
    Exakte Algorithmen (Knuth-Morris-Pratt, Boyer-Moore, Rabin-Karp, Suffix-Bäume und Felder), Approximativer Zeichenkettenabgleich durch dynamische Programmierung (pdf, pptx)
  14. Schwere Probleme
    Erfüllbarkeitsproblem 3-SAT, P=NP, Clique-Problem, Problemreduktion, NP-schwere und NP-vollständige Probleme, Algorithmische Entwurfsmuster zur Behandlung NP-schwerer Probleme (DPLL, Nicht-chronologisches Backtracking), Abbildung von Sudoku auf 3-SAT, 2-SAT, Constraint-Satisfaction-Probleme, Reduktion des Backtrackings durch Heuristiken (am Beispiel der Probleme Chromatische Zahl und n-Damen), Constraint-Propagierung (pdf, pptx)
  15. Eulerkreis, Eulerweg, Hamilton-Kreis (pdf, pptx)
  16. Pruning und Subgraph-Isomorphie
    Ullmanns Algorithmus, Anwendungen zur Zeichenerkennung, Erkennung von Proteinstrukturen, usw. (pdf, pptx)
  17. Approximation
    Aufgabe der optimalen Lösung und Verwendung von Näherungsverfahren? Approximationsgüte gieriger Verfahren, Beispiel: Lastbalancierung (pdf, pptx)
  18. Abspann

Julia-Code von den Vorlesungsfolien in einer Zip-Datei. (Die Datei wird mit den Vorlesungsfolien laufend aktualisiert.)

Herzlichen Dank an Christian Scheideler, Sven Groppe, Michael Bergau, Martin Wirsing und weitere Autoren für die Bereitstellung von Präsentationsmaterialien, die ich in teils modifizierter Form verwendet habe. Zitate in den Materialen kennzeichnen die ursprüngliche Herkunft.


Zielgruppe (Studiengänge):

  • Bachelor Informatik
  • Bachelor IT-Sicherheit
  • Bachelor Mathematik in Medizin und Lebenswissenschaften
  • Bachelor Medieninformatik
  • Bachelor Medizinische Informatik
  • Bachelor Medizinische Ingenieurwissenschaft
  • Bachelor Robotik und Autonome Systeme

Umfang:
Vorlesung (4 SWS) + Übung (2 SWS)

Ort und Zeit der Vorlesung:

  • Do    16:15 - 17:45 Uhr im AM 1
  • Fr     12:15 - 13:45 Uhr im AM 1

Beginn:
Vorlesung: Donnerstag, den 20. April 2023
Übung: Montag, den 24. April 2023

Weitere Informationen (Skripte, Einteilung der Übungsgruppen, Übungsmaterial, etc.) zur Vorlesung erhalten Sie im Moodle.