Technische Universität Ilmenau

Effiziente Algorithmen - Modultafeln der TU Ilmenau

Die Modultafeln sind ein Informationsangebot zu unseren Studiengängen. Rechtlich verbindliche Angaben zum Verlauf des Studiums entnehmen Sie bitte dem jeweiligen Studienplan (Anlage zur Studienordnung). Bitte beachten Sie diesen rechtlichen Hinweis. Angaben zum Raum und Zeitpunkt der einzelnen Lehrveranstaltungen entnehmen Sie bitte dem aktuellen Vorlesungsverzeichnis.

Fachinformationen zu Effiziente Algorithmen im Studiengang Master Informatik 2013
Fachnummer100530
Prüfungsnummer2200366
FakultätFakultät für Informatik und Automatisierung
Fachgebietsnummer 2242 (Komplexitätstheorie und Effiziente Algorithmen)
Fachverantwortliche(r)Prof. Dr. Martin Dietzfelbinger
TurnusWintersemester
SpracheDeutsch
Leistungspunkte5
Präsenzstudium (h)45
Selbststudium (h)105
VerpflichtungPflicht
Abschlussmündliche Prüfungsleistung, 30 Minuten
Details zum Abschluss
max. Teilnehmerzahl
Vorkenntnisse

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

Lernergebnisse

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.   

Inhalt

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.

Medienformen

Bereitgestellt: Skript auf der Webseite

Tafelvortrag, Presenter-Projektion, Folien

Literatur

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

Lehrevaluation

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:

Informationen und Handreichungen zur Pflege von Modul- und Fachbeschreibungen durch den Modul- oder Fachverantwortlichen finden Sie auf den Infoseiten zum Modulkatalog.