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(pdf, pptx)
    Algorithmen, Summenbildung, Entwurfsmuster: schrittweises Abarbeiten (linearer Aufwand), Berechnung mit konstantem Aufwand,Verkleinerungsprinzip: Sortieren durch Einfügen
  2. Sortierung durch Teile und Herrsche, Algorithmenanalyse (pdf, pptx)
    Sortieren durch Auswählen, Problemkomplexität, Algorithmenanalyse: asymptotische Komplexität eines Algorithmus (O-Notation), Entwurfsmuster Teile-und-Herrsche: Mergesort, Quicksort, Omega- und Theta-Notation, Heaps als Datenstrukturen, Heapsort
  3. Sortierung durch Verteilen (pdf, pptx)
    Counting Sort, Mehrkriteriensortierung durch stabile Sortierverfahren, Radix-Sort, Bucket-Sort, Wiederholung: Listen, Keller, Schlangen
  4. Prioritätswarteschlangen (pdf, pptx)
    Realisierung mit binären Heaps, Binomial-Heaps und Fibonacci-Heaps, amortisierte Analyse
  5. Selektion (pdf, pptx)
    K-Kleinstes Element
  6. Mengen (pdf, pptx)
    Selbstorganisierende Datenstrukturen, binäre Suchbäume, Iteratoren und Navigationsstrukturen, Ausgeglichenheit, Splay-Bäume, Rot-Schwarz-Bäume, AVL-Bäume
  7. Mengen von Zeichenketten(pdf, pptx)
    Tries, PATRICIA Tries
  8. Disjunkte Mengen (pdf, pptx)
    Union-Find-Datenstrukturen
  9. Assoziation von Objekten (pdf, pptxmp4 Teil 1 , mp4 Teil 2 (Passwort: MjA6M3Qc))
    Hash-Tabellen, Dynamisches Hashing (Kollisionslisten, Lineare Sondierung, Quadratische Sondierung, Doppeltes Hashing), Statisches Hashing, Familie universeller Hashfunktionen
  10. Graphen (pdf, pptx)
    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, Eulerkreis, Eulerweg, Hamilton-Kreis
  11. Suchgraphen für Spiele (pdf, pptx)
    Minimax-Suche, Suchraumaufbau, Alpha-Beta-Pruning zur Suchraumbeschneidung
  12. AlphaGo und AlphaZero (pdf, pptx)
  13. Dynamische Programmierung, Gierige Verfahren (pdf, pptx)
    Optimierungsprobleme, Sequenz-Alignment (Longest-Common-Subsequence, LCS), Rucksackproblem, Planungs- und Anordnungsprobleme, Wechselgeldbestimmung, Vollständigkeit von Algorithmen
  14. Zeichenkettenabgleich (pdf, pptx)
    Exakte Algorithmen (Knuth-Morris-Pratt, Boyer-Moore, Rabin-Karp, Suffix-Bäume und Felder), Approximativer Zeichenkettenabgleich durch dynamische Programmierung
  15. Schwere Probleme (pdf, pptx)
    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
  16. Pruning und Subgraph-Isomorphie (nicht im SoSe 22)
    Ullmanns Algorithmus, Anwendungen zur Zeichenerkennung, Erkennung von Proteinstrukturen, usw.
  17. Approximation (nicht im SoSe 22)
    Aufgabe der optimalen Lösung und Verwendung von Näherungsverfahren? Approximationsgüte gieriger Verfahren, Beispiel: Lastbalancierung

 

Julia-Code von den Vorlesungsfolien in einer Zip-Datei.

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.

Videomaterial

Die Vorlesung wird live in Präsenz gehalten, die folgenden Videos stammen aus dem letzten Jahr und können daher kleine Differenzen zu den diesjährigen Inhalten aufweisen. Insbesondere sind die Pseudocodes noch nicht mit Julia realisiert.

Das Passwort für die Videos lautet MjA6M3Qc, die in den Videos genutzten Folien sind bei den Videos verlinkt.

KW

Video & Folien
Vorlesung Donnerstag

Video & Folien
Vorlesung Freitag

14

01, mp4, pdf
02a, mp4, pdf

02b, mp4, pdf
02c, mp4, pdf

15

03a, mp4, pdf
03b, mp4, pdf
03c, mp4, pdf

04a, mp4, pdf
04b, mp4, pdf

16

04c, mp4, pdf

04d, mp4, pdf

17

05 mp4, pdf

06a, mp4, pdf

18

06b, mp4, pdf

06c, mp4, pdf

19

06d, mp4, pdf

06e, mp4, pdf

20

07, mp4, pdf

08, mp4, pdf

21

09a, mp4, pdf

09b, mp4, pdf

22

10a, mp4, pdf

10b, mp4, pdf

23

10c, mp4, pdf

10d, mp4, pdf

24

10e, mp4, pdf

10f, mp4, pdf

25

10g, mp4, pdf

10h, mp4, pdf

26

11, mp4, pdf
12a, mp4, pdf

12b, mp4, pdf

27

12c, mp4, pdf

13, mp4, pdf

28

14, mp4, pdf

15, mp4, pdf
16, mp4, pdf

Zielgruppe:

  • Bachelor Informatik vor 2014 (Pflicht: fachliche Eignungsfeststellung), Grundlagen der Informatik, 2. Fachsemester
  • Bachelor Informatik ab 2014 (Pflicht: fachliche Eignungsfeststellung), Grundlagen der Informatik, 2. Fachsemester
  • Bachelor Informatik neu ab 2016 (Pflicht: fachliche Eignungsfeststellung), Grundlagen der Informatik, 2. Fachsemester
  • Bachelor Medizinische Informatik vor 2014 (Pflicht), Informatik, 2. Fachsemester
  • Bachelor Medizinische Informatik ab 2014 (Pflicht), Informatik, 2. Fachsemester
  • Bachelor MIW vor 2014 (Pflicht), Grundlagen der Informatik, 4. Fachsemester
  • Bachelor MIW ab 2014 (Wahlpflicht), Informatik/Elektrotechnik, 4. oder 6. Fachsemester
  • Bachelor Medieninformatik (Pflicht), Grundlagen der Informatik, 2. Fachsemester
  • Bachelor MML (Pflicht), Grundlagen der Informatik, 2. Fachsemester
  • Bachelor Robotik und Autonome Systeme in Planung (Pflicht), Informatik, 2. Fachsemester

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 07. April 2022
Übung Montag, den 11. April 2022

Weitere Informationen (Skripte, Einteilung der Übungsgruppen, Übungsmaterial, etc.) zur Vorlesung erhalten Sie im Moodle der Universität zu Lübeck.