Efficient Algorithms - Interactive curriculae of TU Ilmenau
The interactive curriculae 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 course catalogue.
Please note that this page is no longer updated. All modules and study plans from PO version 2021 onwards (Bachelor and Master study programs) are now available on the Campus Portal.
| module properties Efficient Algorithms in degree program Master Informatik 2013 | |
|---|---|
| module number | 100530 |
| examination number | 2200366 |
| department | Department of Computer Science and Automation |
| ID of group | 2242 (Algorithms) |
| module leader | Prof. Dr. Martin Dietzfelbinger |
| term | winter term only |
| language | Deutsch |
| credit points | 5 |
| on-campus program (h) | 45 |
| self-study (h) | 105 |
| obligation | obligatory module |
| exam | oral examination performance, 30 minutes |
| details of the certificate | |
| link to Moodle course | https://moodle.tu-ilmenau.de/course/view.php?id=3558 |
| teacher | |
| 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 and technical requirements for education and examination in case of online participation | 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 | |