Algorithmen und Datenstrukturen (CS1001-KP08)
Dozent:
Prof. Dr. rer. nat. Ralf Möller
Inhalt (für pptx sollte der Font Myriad Pro installiert sein):
Aufzeichnungspasswort für Videos: MjA6M3Qc
- Einführung (pdf, pptx, mp4 streaming, mp4 download) 9.4.2020
Algorithmen, Summenbildung, Entwurfsmuster: schrittweises Abarbeiten (linearer Aufwand), Berechnung mit konstantem Aufwand, Verkleinerungsprinzip: Sortieren durch Einfügen - Sortierung durch Vergleichen, Algorithmenanalyse Teil a: (pdf, pptx, mp4 streaming, mp4 download), Teil b: (pdf, pptx, mp4 streaming, mp4 download), Teil c: (pdf, pptx, mp4 streaming, mp4 download) 16.-17.4.2020
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 - Sortierung durch Verteilen Teil a: (pdf, pptx, mp4 streaming, mp4 download), Teil b: (pdf, pptx, mp4 streaming, mp4 download), Teil c: (pdf, pptx, mp4 streaming, mp4 download) 23.-24.4.2020
Counting Sort, Mehrkriteriensortierung durch stabile Sortierverfahren, Radix-Sort, Bucket-Sort, Wiederholung: Listen, Keller, Schlangen - Prioritätswarteschlangen Teil a: (pdf, pptx, mp4 streaming, mp4 download), Teil b: ( pdf, pptx, mp4 streaming, mp4 download), Teil c: (pdf, pptx, mp4 streaming, mp4 download), Teil d: (pdf, pptx, mp4 streaming, mp4 download) 30.4.2020, 7.5.2020
Realisierung mit binären Heaps, Binomial-Heaps und Fibonacci-Heaps, amortisierte Analyse - Selektion (pdf, pptx, mp4 streaming, mp4 download) 7.5.2020
K-Kleinstes Element - 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 mp4 streaming, mp4 download), Teil b: (pdf, pptx mp4 streaming, mp4 download), Teil c: (pdf, pptx, mp4 streaming, mp4 download), Teil d: (pdf, pptx, mp4 streaming, mp4 download), Teil e: (pdf, pptx, mp4 streaming, mp4 download) 8.5.-15.5.2020
- Mengen von Zeichenketten (pdf, pptx, mp4 streaming, mp4 download) 22.5.2020
Tries, PATRICIA Tries - Disjunkte Mengen (pdf, pptx, mp4 streaming, mp4 download) 28.5.2020
Union-Find-Datenstrukturen - Assoziation von Objekten Teil a: (pdf, pptx, mp4 streaming, mp4 download), Teil b: (pdf, pptx, mp4 streaming, mp4 download) 28.5.-29.5.2020
Hash-Tabellen, Dynamisches Hashing (Kollisionslisten, Lineare Sondierung, Quadratische Sondierung, Doppeltes Hashing), Statisches Hashing, Familie universeller Hashfunktionen - Graphen Teil a: (pdf, pptx, mp4 streaming, mp4 download), Teil b: (pdf, pptx, mp4 streaming, mp4 download), Teil c: (pdf, pptx, mp4 streaming, mp4 download), Teil d: (pdf, pptx, mp4 streaming, mp4 download), Teil e: (pdf, pptx, mp4 streaming, mp4 download), Teil f: (pdf, pptx, mp4 streaming, mp4 download), Teil g: (pdf, pptx, mp4 streaming, mp4 download), Teil h: (pdf, pptx, mp4 streaming, mp4 download) 4.6.-12.6.2020
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 - Suchgraphen für Spiele (pdf, pptx, mp4 streaming, mp4 download) 18.6.2020
Minimax-Suche, Suchraumaufbau, Alpha-Beta-Pruning zur Suchraumbeschneidung - Dynamische Programmierung, Gierige Verfahren Teil a: (pdf, pptx, mp4 streaming, mp4 download), Teil b: (pdf, pptx, mp4 streaming, mp4 download), Teil c: (pdf, pptx, mp4 streaming, mp4 download) 19.6.-26-6-2020
Optimierungsprobleme, Sequenz-Alignment (Longest-Common-Subsequence, LCS), Rucksackproblem, Planungs- und Anordnungsprobleme, Wechselgeldbestimmung, Vollständigkeit von Algorithmen - Zeichenkettenabgleich (pdf, pptx, mp4 streaming, mp4 download) 2.7.2020
Exakte Algorithmen (Knuth-Morris-Pratt, Boyer-Moore, Rabin-Karp, Suffix-Bäume und Felder), Approximativer Zeichenkettenabgleich durch dynamische Programmierung - Schwere Probleme (pdf, pptx, mp4 streaming, mp4 download) 3.7.-9-7.2020
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 - Pruning und Subgraph-Isomorphie (pdf, pptx, mp4 streaming, mp4 download) 10.7.2020
Ullmanns Algorithmus, Anwendungen zur Zeichenerkennung, Erkennung von Proteinstrukturen, usw. - Approximation (pdf, pptx, mp4 streaming, mp4 download) 10.7.2020
Aufgabe der optimalen Lösung und Verwendung von Näherungsverfahren? Approximationsgüte gieriger Verfahren, Beispiel: Lastbalancierung - Abspann (mp4 streaming, mp4 download) 10.7.2020
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 / Audimaxgebäude
- Fr 12:15 - 13:45 Uhr im AM 1 / Audimaxgebäude
Beginn:
Donnerstag, den 09. April 2020
Ort und Zeit der Übungen:
- Montags
Beginn:
Montag, den 20. April 2020
Weitere Informationen (Skripte, Einteilung der Übungsgruppen, Übungsmaterial, etc.) zur Vorlesung erhalten Sie im Moodle der Universität zu Lübeck.