Website
Modulhandbuch

Modul CS1001-KP08, CS1001

Algorithmen und Datenstrukturen (AuD)

Dauer:


1 Semester
Angebotsturnus:


Jedes Sommersemester
Leistungspunkte:


8
Studiengang, Fachgebiet und Fachsemester:
  • Bachelor Medizinische Ingenieurwissenschaft 2020 (Wahlpflicht), Informatik/Elektrotechnik, ab 3. Fachsemester
  • Bachelor Medieninformatik 2020 (Pflicht), Informatik, 2. Fachsemester
  • Bachelor Informatik 2019 (Pflicht: fachliche Eignungsfeststellung), Grundlagen der Informatik, 2. Fachsemester
  • Bachelor Robotik und Autonome Systeme 2020 (Pflicht), Informatik, 2. Fachsemester
  • Bachelor Medizinische Informatik 2019 (Pflicht), Informatik, 2. Fachsemester
  • Bachelor Informatik 2016 (Pflicht: fachliche Eignungsfeststellung), Grundlagen der Informatik, 2. Fachsemester
  • Bachelor Mathematik in Medizin und Lebenswissenschaften 2016 (Pflicht), Grundlagen der Informatik, 2. Fachsemester
  • Bachelor Robotik und Autonome Systeme 2016 (Pflicht), Informatik, 2. Fachsemester
  • Bachelor IT-Sicherheit 2016 (Pflicht: fachliche Eignungsfeststellung), Informatik, 2. Fachsemester
  • Bachelor Medizinische Informatik 2014 (Pflicht), Informatik, 2. Fachsemester
  • Bachelor Medizinische Ingenieurwissenschaft 2014 (Wahlpflicht), Informatik/Elektrotechnik, 4. oder 6. Fachsemester
  • Bachelor Medieninformatik 2014 (Pflicht), Grundlagen der Informatik, 2. Fachsemester
  • Bachelor Informatik 2014 (Pflicht: fachliche Eignungsfeststellung), Grundlagen der Informatik, 2. Fachsemester
  • Bachelor Medizinische Informatik 2011 (Pflicht), Informatik, 2. Fachsemester
  • Bachelor Medizinische Ingenieurwissenschaft 2011 (Pflicht), Grundlagen der Informatik, 4. Fachsemester
  • Bachelor Mathematik in Medizin und Lebenswissenschaften 2010 (Pflicht), Grundlagen der Informatik, 2. Fachsemester
  • Bachelor Informatik 2012 (Pflicht: fachliche Eignungsfeststellung), Grundlagen der Informatik, 2. Fachsemester
Lehrveranstaltungen:
  • CS1001-Ü: Algorithmen und Datenstrukturen (Übung, 2 SWS)
  • CS1001-V: Algorithmen und Datenstrukturen (Vorlesung, 4 SWS)
Workload:
  • 25 Stunden Prüfungsvorbereitung
  • 125 Stunden Selbststudium
  • 90 Stunden Präsenzstudium
Lehrinhalte:
  • Einführung, Algorithmen, Entwurfsmuster: Schrittweises Abarbeiten, Ein-Schritt-Berechnung
  • Sortierung durch Vergleichen, Entwurfsmuster: Verkleinerungsprinzip, Teile-und-Herrsche, Problemkomplexität, Algorithmenanalyse: asymptotische Komplexität eines Algorithmus (O-Notation), Problemklassen, Heaps als Datenstrukturen
  • Sortierung durch Verteilen, Sortieren durch Zählen, Stabiles Sortieren, Radix-Sortieren, Bucket-Sortierung
  • Prioritätswarteschlangen, Binomial-Heaps, Fibonacci-Heaps, amortisierte Analyse
  • Selektion, K-Kleinstes Element
  • Mengen, selbstorganisierende Datenstrukturen, binäre Suchbäume, Iteratoren und Navigationsstrukturen, Ausgeglichenheit, Splay-Bäume, Rot-Schwarz-Bäume, AVL-Bäume
  • Mengen von Zeichenketten, Tries, PATRICIA-Tries
  • Disjunkte Mengen, Union-Find-Datenstrukturen
  • Assoziation von Objekten, Hash-Tabellen, Dynamisches Hashing (Kollisionslisten, Lineare Sondierung, Quadratische Sondierung, Doppeltes Hashing), Statisches Hashing, Universelles Hashing
  • Graphen, 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
  • Suchgraphen für Spiele, Minimax-Suche, Suchraumaufbau, Alpha-Beta-Pruning zur Suchraumbeschneidung, Anwendung im Schach, Pruning und Subgraph-Isomorphie
  • Ullmanns Algorithmus, Anwendungen zur Zeichenerkennung, Erkennung von Proteinstrukturen
  • Dynamische Programmierung, Gierige Verfahren, Optimierungsprobleme, Sequenz-Alignment (Longest-Common-Subsequence, LCS), Rucksackproblem, Planungs- und Anordnungsprobleme, Wechselgeldbestimmung, Vollständigkeit von Algorithmen
  • Zeichenkettenabgleich, Exakte Algorithmen (Knuth-Morris-Pratt, Boyer-Moore, Rabin-Karp, Suffix-Bäume und Felder), Approximativer Zeichenkettenabgleich durch dynamische Programmierung
  • Schwierige Probleme, 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, Beschränkungs-Erfüllungsprobleme, Reduktion des Rücksetzens durch Heuristiken (am Beispiel der Probleme Chromatische Zahl und n-Damen)
  • Pruning und Subgraph-Isomorphie, Ullmanns Algorithmus, Anwendungen zur Zeichenerkennung, Erkennung von Proteinstrukturen, usw.
  • Approximation, Aufgabe der optimalen Lösung und Verwendung von Näherungsverfahren? Approximationsgüte gieriger Verfahren, Beispiel: Lastbalancierung
Qualifikationsziele/Kompetenzen:
  • Für alle in den Lehrinhalten unter der Spiegelstrichen genannten Themen können die Studierenden die zentralen Ideen benennen, die jeweils relevanten Begriffe definieren und die Funktionsweise von Algorithmen anhand von Anwendungsbeispielen erläutern.
Vergabe von Leistungspunkten und Benotung durch:
  • Klausur
Voraussetzung für:
Setzt voraus:
Modulverantwortlicher:
Lehrende:
Literatur:
  • T. Ottmann, P. Widmayer: Algorithmen und Datenstrukturen - Spektrum, 2002
  • R. Sedgewick: Algorithmen in Java Teil 1 - 4 - Pearson Studium, 2003
  • S. Baase und A. Van Gelder: Computer Algorithms - 3. Auflage, Addison-Wesley, 2000
Sprache:
  • Wird nur auf Deutsch angeboten
Bemerkungen:

Zulassungsvoraussetzungen zum Modul:
- Keine (Die Kompetenzen der vorausgesetzten Module werden für dieses Modul benötigt, die Module stellen aber keine Zulassungsvoraussetzung dar.)

Zulassungsvoraussetzungen zur Prüfung:
- Erfolgreiche Bearbeitung von Übungsaufgaben während des Semesters

Letzte Änderung:
11.11.2019