Technische Universität Ilmenau

Efficient Algorithms - Modultafeln of TU Ilmenau

The Modultafeln have a pure informational character. The legally binding information can be found in the corresponding Studienplan and Modulhandbuch, which are served on the pages of the course offers. Please also pay attention to this legal advice (german only). Information on place and time of the actual lectures is served in the Vorlesungsverzeichnis.

subject properties Efficient Algorithms in major Master Mathematik und Wirtschaftsmathematik 2013 (WM)
subject number100530
examination number2200366
departmentDepartment of Computer Science and Automation
ID of group 2242 (Group for Complexity Theory and Efficient Algorithms)
subject leaderProf. Dr. Martin Dietzfelbinger
term Wintersemester
languageDeutsch
credit points4
on-campus program (h)45
self-study (h)75
Obligationobligatory elective
examoral examination performance, 30 minutes
details of the certificate
maximum number of participants
previous knowledge and experience

Bachelorstudium Informatik, insbesondere: Algorithmen und Programmierung, Algorithmen und Datenstrukturen, Mathematik 1 und 2, Grundlagen und diskrete Strukturen.

learning outcome

Fachkompetenz: Die Studierenden kennen einige wesentliche fortgeschrittene Algorithmen und die hierfür notwendigen Entwurfs- und Analysetechniken. Sie können mit den erlernten Techniken Algorithmen für abgewandelte Fragestellungen entwerfen und analysieren. Sie können Algorithmen auch auf nicht offensichtliche Anwendungsfragestellungen übertragen. Sie können eine amortisierte Laufzeitanalyse durchführen, wenn die wesentlichen Festlegungen angegeben sind. Die Studierenden kennen die vielfältige Anwendbarkeit von Flussalgorithmen. Sie kennen nichttriviale grundlegende Techniken für die Verarbeitung von Wörtern (Textsuche) und die relevanten Beweistechniken.   

content

Flussprobleme und –algorithmen: Ford-Fulkerson-Methode, Algorithmus von Edmonds/Karp, Sperrflussmethode (Algorithmus von Dinitz), Preflow-Push-Ansatz.

Matchingprobleme und ihre Algorithmen: Kardinalitätsmatching, Lösung über Flussalgorithmen, Algorithmus von Hopcroft/Karp; gewichtetes Matching: Auktionsalgorithmus, Ungarische Methode; Stabile Paarungen: Satz von Kuhn/Munkres, Algorithmus von Gale/Shapley.

Amortisierte Analyse von Datenstrukturen: Ad-Hoc-Analyse, Bankkontomethode, Potenzialmethode.

Implementierung von adressierbaren Priority Queues: Binomialheaps und Fibonacci-Heaps.

Textsuche: Randomisiertes Verfahren; Algorithmus von Knuth/Morris/Pratt, Algorithmus von Aho/Corasick, Algorithmus von Boyer/Moore, Vorverarbeitung für Boyer-Moore-Algorithmus.

media of instruction

Bereitgestellt: Skript auf der Webseite

Tafelvortrag, Presenter-Projektion, Folien

literature / references

Neben Vorlesungsskript:

- J. Kleinberg, E. Tardos, Algorithm Design, Pearson Education, 2005

- T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, Introduction to Algorithms, 2nd ed., MIT Press, 2001 (auch auf deutsch bei Oldenbourg)

- M. Dietzfelbinger, K. Mehlhorn, P. Sanders, Algorithmen und Datenstrukturen - Die Grundwerkzeuge, Springer, 2014

- S. Dasgupta, C. Papadimitriou, U. Vazirani, Algorithms, McGraw-Hill, 2007

- V. Heun, Grundlegende Algorithmen, 2. Auflage, Vieweg, 2003

evaluation of teaching

Pflichtevaluation:

SS 2010 (Fach)

WS 2012/13 (Fach)

Freiwillige Evaluation:

SS 2008 (Vorlesung)

WS 2009/10 (Übung)

SS 2010 (Übung)

WS 2010/11 (Vorlesung, Übung)

SS 2011 (Vorlesung, Übung)

WS 2011/12 (Vorlesung, Übung)

SS 2012 (Vorlesung, Übung)

WS 2012/13 (Übung

SS 2013 (Vorlesung, Übung)

WS 2013/2014 (Vorlesung, Übung)

SS 2014 (Vorlesung, Übung)

WS 2014/15 (Vorlesung, Übung)

WS 2015/16 (Vorlesung)

WS 2016/17 (Vorlesung, Übung)

WS 2017/18 (Vorlesung, Übung)

Hospitation: