Algorithmen und Datenstrukturen (CS1001)


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

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

  • Einführung (pdfpptx)
    Algorithmen, Summenbildung, Entwurfsmuster: schrittweises Abarbeiten, Ein-Schritt-Berechnung, Verkleinerungsprinzip
  • Sortierung durch Vergleichen (pdfpptx)
    Sortieren durch Einfügen, Entwurfsmuster: Teile-und-Herrsche, Problemkomplexität, Algorithmenanalyse: asymptotische Komplexität eines Algorithmus (O-Notation), Sortieren durch Auswählen, Problemklassen, Quicksort, Heaps als Datenstrukturen, Heapsort
  • Sortierung durch Verteilen (pdfpptx)
    Counting Sort, Stabiles Sortieren, Radix-Sort, Wiederholung: Listen, Keller, Schlangen, Bucket-Sort
  • Prioritätswarteschlangen (pdfpptx)
    Binomial-Heaps, Fibonacci-Heaps, amortisierte Analyse
  • Selektion (pdfpptx)
    K-Kleinstes Element
  • Mengen, selbstorganisierende Datenstrukturen, binäre Suchbäume, Iteratoren und Navigationsstrukturen, Ausgeglichenheit, Splay-Bäume, Rot-Schwarz-Bäume, AVL-Bäume (pdfpptx)
  • Mengen von Zeichenketten (pdfpptx)
    Tries, PATRICIA Tries
  • Disjunkte Mengen (pdfpptx)
    Union-Find-Datenstrukturen
  • Assoziation von Objekten (pdfpptx)
    Hash-Tabellen, Dynamisches Hashing (Kollisionslisten, Lineare Sondierung, Quadratische Sondierung, Doppeltes Hashing), Statisches Hashing, Universelles Hashing
  • Graphen (pdfpptx)
    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 (pdfpptx)
    Minimax-Suche, Suchraumaufbau, Alpha-Beta-Pruning zur Suchraumbeschneidung
  • Pruning und Subgraph-Isomorphie (pdfpptx)
    Ullmanns Algorithmus, Anwendungen zur Zeichenerkennung, Erkennung von Proteinstrukturen, usw.
  • Dynamische Programmierung, Gierige Verfahren (pdfpptx)
    Optimierungsprobleme, Sequenz-Alignment (Longest-Common-Subsequence, LCS), Rucksackproblem, Planungs- und Anordnungsprobleme, Wechselgeldbestimmung, Vollständigkeit von Algorithmen
  • Zeichenkettenabgleich (pdfpptx)
    Exakte Algorithmen (Knuth-Morris-Pratt, Boyer-Moore, Rabin-Karp, Suffix-Bäume und Felder), Approximativer Zeichenkettenabgleich durch dynamische Programmierung
  • Schwierige Probleme (pdfpptx)
    Erfüllbarkeitsproblem 3-SAT, P=NP, Clique-Problem, Problemreduktion, NP-schwere und NP-vollständige Probleme, Algorithmische Entwurfsmuster zur Behandlung NP-schwerer Probleme (DPLL, Dependenzgesteuertes 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)
  • Approximation (pdf, pptx)
    Was tun, wenn Heuristiken nicht greifen und ein Algorithmus sich in kombinatorischer Suche verirrt? Aufgabe der optimalen Lösung und Verwendung von Näherungsverfahren? Approximationsgüte gieriger Verfahren, Beispiel: Lastbalancierung, Was tun, wenn Approximationsgüte zu schlecht? Nicht jedes formal sauber definierte Problem kann sinnvoll mit Computern behandelt werden.

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
    Achtung: am 07.06.2018 findet die Vorlesung in der Zeit von 16:00 Uhr - 17:30 Uhr statt !
  • Fr     12:15 - 13:45 Uhr im AM 1 / Audimaxgebäude

Beginn:
Donnerstag, den 12. April 2018

Ort und Zeit der Übungen:

  • Montags

Beginn:
Montag, den 16. April 2018

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