Loading
     

Modulbeschreibung - Detailansicht

Wichtigste Meldungen anzeigenMeldungsfenster schließen
Moduldetails
Effiziente Algorithmen und Datenstrukturen II
Fakultät für Informatik
TUINFIN
8
1
6
IN2004
Zuordnungen zu SPO-Versionen
Lehrveranstaltungen und Prüfungsveranstaltungen
Beschreibungen
12S
Export
Allgemeine Daten (Modulhandbuch)
Bachelor/Master
Einsemestrig
Sommersemester
Englisch
Arbeitsaufwand (Work Load)
240
90
150
Studien- und Prüfungsleistungen
Die Prüfungsleistung wird in Form einer Klausur von 150 Minuten erbracht. In dieser weisen Studierende anhand der gestellten Aufgaben nach, dass sie über fundamentale und fortgeschrittene Kenntnisse der Algorithmenanalyse verfügen und diese erfolgreich bei der Lösung von Problemen anwenden können. Ferner demonstrieren Studierende beim Lösen der gestellten Aufgaben, dass sie die im Modul behandelten Datenstrukturen und fortgeschrittenen algorithmischen Methoden der kombinatorischen Optimierung beherrschen. Die Studierenden weisen nach, dass sie in begrenzter Zeit anspruchsvolle algorithmische Probleme erkennen und analysieren können sowie Wege zu einer effizienten Lösung finden können.
N
J
Beschreibung
IN0015 Diskrete Strukturen, IN0018 Diskrete Wahrscheinlichkeitstheorie, IN2003 Effiziente Algorithmen und Datenstrukturen
Nach dem Absolvieren des Moduls verfügen Studierende über umfangreiche Kenntnisse fortgeschrittener algorithmischer Methoden, insbesondere aus dem Bereich der Linearen Optimierung. Darüber hinaus wissen sie um die Bedeutung von Approximationsalgorithmen für die Lösung NP-vollständiger Probleme. Sie kennen verschiedene Techniken, um approximative Lösungen für Probleme aus dem Bereich der kombinatorischen Optimierung zu gewinnen und können diese Techniken selbstständig auf neue Probleme anwenden, die in einer wissenschaftlichen und/oder beruflichen Anwendung auftreten.
Lineare Optimierung
- Modellierung
- Simplex-Verfahren
- Seidels Algorithmus
- Ellipsoidmethode
- Karmarkar

Approximationsalgorithmen
- Greedy Methoden
- Lokale Suche
- Rundungsmethoden
- Primal/Dual-Verfahren
Das Modul besteht aus einer Vorlesung und einer begleitenden Übung. Die Inhalte der Vorlesung werden im Vortrag und durch Präsentation vermittelt. Studierende werden insbesondere durch die Lösung von Übungsblättern zur inhaltlichen Auseinandersetzung mit den Themen angeregt. Die Lösung der Übungsaufgaben wird in der Übungsveranstaltung besprochen. Zusätzlich erhalten die Studenten durch die Korrektur der Übungsblätter eine individuelle Rückmeldung über ihren Lernerfolg.
Folien, Tafelarbeit, Übungsblätter
Thomas H. Cormen, Charles E. Leiserson, Ron L. Rivest, Clifford Stein:
Introduction to Algorithms
McGraw-Hill, 1990

Jon Kleinberg, Eva Tardos:
Algorithm Design
Addison-Wesley, 2005

David P. Williamson, David B. Shmoys:
The Design of Approximation Algorithms
Cambridge University Press, 2011

Vijay Vazirani:
Approximation Algorithms
Springer, 2001

Christos H. Papadimitriou, Kenneth Steiglitz:
Combinatorial Optimization: Algorithms and Complexity,
Prentice Hall, 1982

Theory of Integer and Linear Programming
Alexander Schrijver
John Wiley & Sons, 1998
Modulverantwortliche*r
Susanne Albers, Prof. Dr. (susanne.albers@tum.de)