Algorithmen und Datenstrukturen (CS1001-KP08)


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

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 Vergleichen, Algorithmenanalyse Teil a: (pdfpptx), Teil b: (pdf pptx), Teil c: (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 Teil a: (pdfpptx), Teil b: (pdf pptx), Teil c: (pdfpptx)
    Counting Sort, Mehrkriteriensortierung durch stabile Sortierverfahren, Radix-Sort, Bucket-Sort, Wiederholung: Listen, Keller, Schlangen
  4. Prioritätswarteschlangen Teil a: (pdf, pptx), Teil b: (pdf, pptx), Teil c: (pdf, pptx), Teil d: (pdf, pptx)
    Realisierung mit binären Heaps, Binomial-Heaps und Fibonacci-Heaps, amortisierte Analyse
  5. Selektion (pdf, pptx)
    K-Kleinstes Element
  6. Mengen, selbstorganisierende Datenstrukturen, binäre Suchbäume, Iteratoren und Navigationsstrukturen, Ausgeglichenheit, Splay-Bäume, Rot-Schwarz-Bäume, AVL-Bäume Teil a: (pdf, pptx), Teil b: (pdfpptx), Teil c: (pdf, pptx), Teil d: (pdf, pptx), Teil e: (pdf, pptx)
  7. Mengen von Zeichenketten (pdf, pptx)
    Tries, PATRICIA Tries
  8. Disjunkte Mengen (pdf, pptx)
    Union-Find-Datenstrukturen
  9. Assoziation von Objekten Teil a: (pdf, pptx), Teil b: (pdf, pptx) 
    Hash-Tabellen, Dynamisches Hashing (Kollisionslisten, Lineare Sondierung, Quadratische Sondierung, Doppeltes Hashing), Statisches Hashing, Familie universeller Hashfunktionen
  10. Graphen Teil a: (pdf, pptx), Teil b: (pdf, pptx), Teil c: (pdf, pptx), Teil d: (pdf, pptx), Teil e: (pdf, pptx), Teil f: (pdf, pptx), Teil g: (pdf, pptx), Teil h: (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. Dynamische Programmierung, Gierige Verfahren Teil a: (pdfpptx), Teil b: (pdfpptx), Teil c: (pdfpptx)
    Optimierungsprobleme, Sequenz-Alignment (Longest-Common-Subsequence, LCS), Rucksackproblem, Planungs- und Anordnungsprobleme, Wechselgeldbestimmung, Vollständigkeit von Algorithmen
  13. Zeichenkettenabgleich (pdf, pptx)
    Exakte Algorithmen (Knuth-Morris-Pratt, Boyer-Moore, Rabin-Karp, Suffix-Bäume und Felder), Approximativer Zeichenkettenabgleich durch dynamische Programmierung
  14. 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
  15. Pruning und Subgraph-Isomorphie (pdf, pptx)
    Ullmanns Algorithmus, Anwendungen zur Zeichenerkennung, Erkennung von Proteinstrukturen, usw.
  16. Approximation (pdf, pptx)
    Aufgabe der optimalen Lösung und Verwendung von Näherungsverfahren? Approximationsgüte gieriger Verfahren, Beispiel: Lastbalancierung
  17. Abspann (keine pdf oder pptx)

 

Das Passwort für die Videos lautet: MjA6M3Qc

KW

Vorlesung 
Donnerstag 

Video

Vorlesung 
Freitag

Video

14

8.4.2021

mp4 (01)
mp4 (02a)

9.4.2021

mp4 (02b)
mp4 (02c)

15

15.4.2021

mp4 (03a)
mp4 (03b)
mp4 (03c)

16.4.2021

mp4 (04a)
mp4 (04b)

16

22.4.2021

mp4 (04c)

23.4.2021

mp4 (04d)

17

29.4.2021

mp4 (05)

30.4.2021

mp4 (06a)

18

6.5.2021

mp4 (06b)

7.5.2021

mp4 (06c)

19

13.5.2021

Chr. Himmelfahrt

14.5.2021

Brückentag

20

20.5.2021

mp4 (06d)

21.5.2021

mp4 (06e)

21

27.5.2021

mp4 (07)

28.5.2021

mp4 (08)

22

3.6.2021

mp4 (09a)

4.6.2021

mp4 (09b)

23

10.6.2021

mp4 (10a)

11.6.2021

mp4 (10b)

24

17.6.2021

mp4 (10c)

18.6.2021

mp4 (10d)

25

24.6.2021

mp4 (10e)

25.6.2021

mp4 (10f)

26

1.7.2021

mp4 (10g)

2.7.2021

mp4 (10h)

27

8.7.2021

mp4 (11)
mp4 (12a)

9.7.2021

mp4 (12b)

28

15.7.2021

mp4 (12c)

16.7.2021

mp4 (13)

29

22.7.2021

mp4 (14)

23.7.2021

mp4 (15)
mp4 (16)
mp4 (17)


Die Zahl hinter dem Link gibt an, auf welche Teilpräsentation sich das Video bezieht.

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:

  • 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 - 18:00 Uhr im AM 1 / online asynchron
  • Fr     12:15 - 13:45 Uhr im AM 1 / online asynchron

Beginn:
Donnerstag, den 04. April 2020

Ort und Zeit der Übungen:

  • Montags

Beginn:
Montag, den 19. April 2020

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