Technische Universität Ilmenau

Efficient Algorithms - Modultafeln of TU Ilmenau

The module lists provide information on the degree programmes offered by the TU Ilmenau.

Please refer to the respective study and examination rules and regulations for the legally binding curricula (Annex Curriculum).

You can find all details on planned lectures and classes in the electronic university catalogue.

Information and guidance on the maintenance of module descriptions by the module officers are provided at Module maintenance.

Please send information on missing or incorrect module descriptions directly to modulkatalog@tu-ilmenau.de.

module properties Efficient Algorithms in degree program Master Informatik 2013
module number100530
examination number2200366
departmentDepartment of Computer Science and Automation
ID of group 2242 (Complexity Theory and Efficient Algorithms)
module leaderProf. Dr. Martin Dietzfelbinger
term winter term only
languageDeutsch
credit points5
on-campus program (h)45
self-study (h)105
obligationobligatory module
examoral examination performance, 30 minutes
details of the certificate
signup details for alternative examinations
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

zum Moodle-Kurs

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)

WS 2018/19 (Vorlesung, Übung)

Hospitation: