Technische Universität Ilmenau

Algorithmen und Datenstrukturen 2 - Modultafeln der TU Ilmenau

Die Modultafeln sind ein Informationsangebot zu den Studiengängen der TU Ilmenau.

Die rechtsverbindlichen Studienpläne entnehmen Sie bitte den jeweiligen Studien- und Prüfungsordnungen (Anlage Studienplan).

Alle Angaben zu geplanten Lehrveranstaltungen finden Sie im elektronischen Vorlesungsverzeichnis.

Informationen und Handreichungen zur Pflege von Modulbeschreibungen durch die Modulverantwortlichen finden Sie unter Modulpflege.

Hinweise zu fehlenden oder fehlerhaften Modulbeschreibungen senden Sie bitte direkt an modulkatalog@tu-ilmenau.de.

Modulinformationen zu Modulnummer 200064 - allgemeine Informationen
Modulnummer200064
FakultätFakultät für Informatik und Automatisierung
Fachgebietsnummer2242 (Komplexitätstheorie und Effiziente Algorithmen)
Modulverantwortliche(r)Prof. Dr. Martin Dietzfelbinger
SpracheDeutsch
TurnusWintersemester
Vorkenntnisse

Algorithmen und Datenstrukturen 1

Mathematik 1 und 2

Lernergebnisse und erworbene Kompetenzen

Fachkompetenz: Die Studierenden kennen Entwurfsprinzipien für Algorithmen (Divide-and-Conquer, Greedy, Dynamische Programmierung) und die zugehörigen Analyseverfahren und können sie in einfachen Fällen zum Algorithmenentwurf einsetzen. Sie kennen spezielle Divide-and -Conquer-Algorithmen und können das "Master-Theorem" zur Analyse einsetzen. Sie kennen die Verfahren "Breitensuche" und "Tiefensuche", und können die Situationen identifizieren, in denen diese Verfahren benutzt werden müssen. Sie kennen weitere Anwendungen der Tiefensuche (Kantenklassifizierung, Kreisfreiheit, topologische Sortierung, starke Zusammenhangskomponenten) mit Korrektheits­beweisen. Die Studierenden kennen Algorithmen für die Berechnung kürzester Wege (Dijkstra, Bellman/Ford) mit ihren Anwendbarkeitsbereichen und den Korrektheitsbeweisen. Sie kennen die Datenstruktur "adressierbare Priority Queue" mit Implementierungs- und Anwendungsmöglichkeiten. Sie kennen weitere Algorithmen für die Berechnung eines minimalen Spannbaums (mit Korrektheitsbeweisen) und der dafür nötigen Union-Find-Datenstruktur. Sie kennen Algorithmen für das "All-pairs-Shortest-Paths"-Problem auf der Basis des Prinzips "Dynamische Programmierung", sowie weitere Beispiele für die Anwendung dieses Prinzips.

Methodenkompetenz: Die Studierenden kennen und verstehen fortgeschrittenere Korrektheitsbeweise und beherrschen wesentliche Techniken für solche Beweise. Sie überblicken die Zusammenhänge zwischen der Bereitstellung von (grundlegenden und fortgeschrittenen) Datenstrukturen und effizienten Algorithmen. Sie kennen Rechenzeitaussagen und ihre Herleitung. Auf dieser Basis können sie in verschiedenen Anwendungsfeldern die für kkonkrete Aufgaben geeigneten Algorithmen auswählen und diese Auswahl sachgerecht begründen. 

Sozialkompetenz: Die Studierenden haben die Erfahrung gemacht, dass zur Erreichung des Ziels der Vorlesung die Herstellung einer gemeinsamen konzentrierten Arbeitsatmosphäre wesentlich ist. Diskussionsbeiträge und Fragen werden von den Lehrenden und den Studierenden immer begrüßt. Die Studierenden können sich aktiv und interagierend an der Diskussion der Lösung der Übungsaufgaben in der Übung beteiligen. Sie erkennen, dass unterschiedliche Herangehensweisen zum Ziel führen können, im Rahmen der mathematischen Regeln und des Standes der Kunst.

Inhalt

Divide-and-Conquer: Multiplikation ganzer Zahlen    Matrixmultiplikation, Master-Theorem.

Quickselect, Schnelle Fourier-Transformation.

Durchmustern von Graphen: Tiefensuche, Zusammenhangskomponenten, Entdecken von Kreisen, topologische Sortierung, starke Zusammenhangskomponenten.

Greedy-Strategie: Teilbares Rucksackproblem.

Schedulingprobleme, Huffman-Kodierung, Kürzeste Wege 1: Algorithmus von Dijkstra, Minimale Spannbäume (Algorithmus von Kruskal, Union-Find), Algorithmus von Jarnik-Prim, randomisierter Algorithmus für minimale Schnitte.

Dynamische Programmierung: Editierdistanz.

Ganzzahliges Rucksackproblem (mit/ohne Wiederholungen).

Kürzeste Wege 2: Algorithmus von Floyd-Warshall, Kürzeste Wege 3: Algorithmus von Bellman-Ford, das Problem des Handlungsreisenden.

Medienformen und technische Anforderungen bei Lehr- und Abschlussleistungen in elektronischer Form

Folien, Folienprojektion, Folien auf der Webseite, Details im Tafelvortrag

Literatur
  • T. Ottmann, P. Widmayer, Algorithmen und Datenstrukturen, Spektrum Akademischer Verlag, 2002
  • R. Sedgewick, Algorithms, Addison-Wesley, 2002 (auch C-, C++, Java-Versionen, auch auf deutsch bei Pearson)
  • R. Sedgewick, Algorithms, Part 5: Graph Algorithms, Addison-Wesley, 2003
  • K. Mehlhorn, P. Sanders, Algorithms and Data Structures - The Basic Toolbox, Springer, 2008
  • S. Dasgupta, C. Papadimitriou, U. Vazirani, Algorithms, McGraw-Hill, 2007
  • T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, Introduction to Algorithms, 2nd ed., MIT Press, 2001 (auch auf deutsch bei Oldenbourg)
  • V. Heun, Grundlegende Algorithmen, 2. Auflage, Vieweg, 2003
  • J. Kleinberg, E. Tardos, Algorithm Design, Pearson Education, 2005
  • U. Schöning, Algorithmik, Spektrum Akademischer Verlag, 2001
Lehrevaluation
Spezifik Referenzmodul
ModulnameAlgorithmen und Datenstrukturen 2
Prüfungsnummer2200713
Leistungspunkte5
SWS4 (2 V, 2 Ü, 0 P)
Präsenzstudium (h)45
Selbststudium (h)105
VerpflichtungPflichtmodul
Abschlussschriftliche Prüfungsleistung, 90 Minuten
Details zum Abschluss
Alternative Abschlussform aufgrund verordneter Corona-Maßnahmen inkl. technischer Voraussetzungen
Anmeldemodalitäten für alternative PL oder SL
max. Teilnehmerzahl
Spezifik im Studiengang Bachelor Wirtschaftsinformatik 2021
ModulnameAlgorithmen und Datenstrukturen 2
Prüfungsnummer2200713
Leistungspunkte5
Präsenzstudium (h)90
Selbststudium (h)60
VerpflichtungWahlmodul
Abschlussschriftliche Prüfungsleistung, 90 Minuten
Details zum Abschluss
Alternative Abschlussform aufgrund verordneter Corona-Maßnahmen inkl. technischer Voraussetzungen
Anmeldemodalitäten für alternative PL oder SL
max. Teilnehmerzahl
Spezifik im Studiengang Bachelor Informatik 2021
ModulnameAlgorithmen und Datenstrukturen 2
Prüfungsnummer2200713
Leistungspunkte5
Präsenzstudium (h)45
Selbststudium (h)105
VerpflichtungPflichtmodul
Abschlussschriftliche Prüfungsleistung, 90 Minuten
Details zum Abschluss
Alternative Abschlussform aufgrund verordneter Corona-Maßnahmen inkl. technischer Voraussetzungen
Anmeldemodalitäten für alternative PL oder SL
max. Teilnehmerzahl