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

Inhalt:

• Einführung (pdf, ppt, pptx)
  Algorithmen, Summenbildung, Entwurfsmuster: schrittweises Abarbeiten, Ein-Schritt-Berechnung 
• Sortierung durch Vergleichen (pdf, ppt, pptx)
  Entwurfsmuster: Verkleinerungsprinzip, Teile-und-Herrsche, Problemkomplexität, Algorithmenanalyse: asymptotische Komplexität eines Algorithmus (O-Notation), Problemklassen, Heaps 
• Sortierung durch Verteilen (pdf, ppt, pptx)
  Counting Sort, Stabiles Sortieren, Radix-Sort, Bucket-Sort
• Prioritätswarteschlangen (pdf, ppt, pptx)
  Binomial-Heaps, Fibonacci-Heaps, amortisierte Analyse 
• Selektion (pdf, ppt, pptx)
  K-Kleinstes Element
• Mengen (pdf, ppt, pptx)
  Selbstorganisierende Datenstrukturen, binäre Suchbäume, Iteratoren (u.a. für Bereiche) und Navigationsstrukturen, Ausgeglichenheit, Splay-Bäume (Ausgleich beim Suchen), Rot-Schwarz-Bäume und AVL-Bäume (Ausgleich beim Einfügen) 
• Mengen von Zeichenketten (pdf, ppt, pptx)
  Tries, PATRICIA Tries 
• Disjunkte Mengen, Partitionen (pdf, ppt, pptx)
  Union-Find-Datenstrukturen
• Assoziation von Objekten (pdf, ppt, pptx)
  Hash-Tabellen, Dynamisches Hashing (Kollisionslisten, Lineare Sondierung, Quadratische Sondierung, Doppeltes Hashing), Statisches Hashing, Universelles Hashing 
• Graphen (pdf, ppt, 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), [nicht in SoSe 15: Minimax-Suche, Alpha-Beta-Pruning], Netzwerkflüsse (Ford-Fulkerson-Algorithmus, Edmonds-Karp-Algorithmus), Bipartites Matching, Eulerkreis, Eulerweg, Hamilton-Kreis
• Entwurfsmuster: Dynamische Programmierung, Gierige Verfahren (pdf, ppt, pptx)
  Optimierungsprobleme, Sequenz-Alignment (Longest-Common-Subsequence, LCS), Rucksackproblem(e), Planungs- und Anordnungsprobleme, Wechselgeldbestimmung, Vollständigkeit von Algorithmen
• Schwierige Probleme (pdf, ppt, pptx)
  Erfüllbarkeitsproblem 3-KNF-SAT, P=NP, Clique-Problem, Problemreduktion, Algorithmische Entwurfsmuster zur Behandlung schwieriger Probleme am Beispiel von SAT, 2-KNF-SAT, Abbildung von Sudoku auf SAT
• Approximation (pdf, ppt, pptx)
  Approximationsgüte gieriger Verfahren, Lastbalancierung

Herzlichen Dank an Christian Scheideler, Sven Groppe, Michael Bergau und Martin Wirsing für die Bereitstellung von Präsentationsmaterialien, die ich in teils modifizierter Form verwendet habe.

Zielgruppe:

• Bachelor Medizinische Informatik SJ14 (Pflicht), Informatik, 2. Fachsemester

• Bachelor MIW SJ14 (Wahlpflicht), Informatik/Elektrotechnik, 4. oder 6. Fachsemester

• Bachelor Medieninformatik SJ14 (Pflicht), Grundlagen der Informatik, 2. Fachsemester

• Bachelor Informatik SJ14 (Pflicht: fachliche Eignungsfeststellung), Grundlagen der Informatik, 2. Fachsemester

• Bachelor Medizinische Informatik (Pflicht), Informatik, 2. Fachsemester

• Bachelor MIW (Pflicht), Grundlagen der Informatik, 4. Fachsemester

• Bachelor MML (Pflicht), Grundlagen der Informatik, 2. Fachsemester

• Bachelor Informatik (Pflicht: fachliche Eignungsfeststellung), Grundlagen der 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 08. April 2015

Achtung: Die Vorlesung am 23.04.2015 entfällt wegen der Uni-Jahresfeier und wird am Freitag, den 24.04.2015 in der Zeit von 14:00-16:00 Uhr nachgeholt.

Ort und Zeit der Übungen:

• Montags

Beginn:
Montag, den 20. April 2015

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