Technische Universit├Ąt Ilmenau

Efficient Algorithms 2 - 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 2 in degree program Master Informatik 2009
ATTENTION: not offered anymore
module number8225
examination number2200230
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 points4
on-campus program (h)34
self-study (h)86
obligationobligatory module
examoral examination performance, 30 minutes
details of the certificate
alternative examination performance due to COVID-19 regulations incl. technical requirements
signup details for alternative examinations
maximum number of participants
previous knowledge and experience

Stoff des Bachelorstudiums zum Thema Algorithmen: Algorithmen und Datenstrukturen, Effiziente Algorithmen, Wahrscheinlichkeitsrechnung (Stochastik) für Informatiker, Mathematik für Informatiker.

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).

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, Potentialmethode.
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

Tafelvortrag, Ausarbeitungen als Text im Netz. Projektion. Übungsblätter auf der Vorlesungswebseite.

literature / references

Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein, Introduction to Algorithms, MIT Press, 2009

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

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

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

Ravindra K. Ahuja, Thomas L. Magnanti, James B. Orlin: Network Flows, Prentice Hall, 1993

evaluation of teaching

Pflichtevaluation:

WS 2012/13 (Fach)

Freiwillige Evaluation:

WS 2010/11 (Vorlesung, Übung)

WS 2011/12 (Vorlesung, Übung)

WS 2012/13 (Übung)

Hospitation:

WS 2012/13