Website
Modulhandbuch ab WS 2016/17

Modul CS1001-KP08, CS1001

Algorithmen und Datenstrukturen (AuD)

Dauer:
1 Semester
Angebotsturnus:
Jedes Sommersemester
Leistungspunkte:
8
Studiengang, Fachgebiet und Fachsemester:
  • Bachelor Informatik ab 2016 (Pflicht: fachliche Eignungsfeststellung), Grundlagen der Informatik, 2. Fachsemester
  • Bachelor MML ab 2016 (Pflicht), Grundlagen der Informatik, 2. Fachsemester
  • Bachelor Robotik und Autonome Systeme (Pflicht), Informatik, 2. Fachsemester
  • Bachelor IT-Sicherheit (Pflicht: fachliche Eignungsfeststellung), Informatik, 2. Fachsemester
  • Bachelor Medizinische Informatik ab 2014 (Pflicht), Informatik, 2. Fachsemester
  • Bachelor MIW ab 2014 (Wahlpflicht), Informatik/Elektrotechnik, 4. oder 6. Fachsemester
  • Bachelor Medieninformatik (Pflicht), Grundlagen der Informatik, 2. Fachsemester
  • Bachelor Informatik 2014 und 2015 (Pflicht: fachliche Eignungsfeststellung), Grundlagen der Informatik, 2. Fachsemester
  • Bachelor Medizinische Informatik vor 2014 (Pflicht), Informatik, 2. Fachsemester
  • Bachelor MIW vor 2014 (Pflicht), Grundlagen der Informatik, 4. Fachsemester
  • Bachelor MML (Pflicht), Grundlagen der Informatik, 2. Fachsemester
  • Bachelor Informatik vor 2014 (Pflicht: fachliche Eignungsfeststellung), Grundlagen der Informatik, 2. Fachsemester
Lehrveranstaltungen:
  • Algorithmen und Datenstrukturen (Übung, 2 SWS)
  • 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)
Qualifikationsziele/Kompetenzen:
  • Verständnis und Anwendungserfahrung grundlegender Algorithmen
  • Verständnis und Anwendungserfahrung über elementare Datenstrukturen
  • Beherrschen grundlegender Prinzipien und Methoden für Entwurf, Implementierung und Analyse von Algorithmen
Vergabe von Leistungspunkten und Benotung durch:
  • Übungsaufgaben
  • 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
Letzte Änderung:
4.7.2018

Modulhandbuch online

Zur Liste aller Module

Modulhandbuch als PDF