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 Fachnummer 100530 - allgemeine Informationen
Fachnummer100530
FakultätFakultät für Informatik und Automatisierung
Fachgebietsnummer2242 (Komplexitätstheorie und Effiziente Algorithmen)
Fachverantwortliche(r)Prof. Dr. Martin Dietzfelbinger
SpracheDeutsch
TurnusWintersemester
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:

Spezifik im Studiengang Master Wirtschaftsinformatik 2013, Master Wirtschaftsinformatik 2014, Master Wirtschaftsinformatik 2015, Master Wirtschaftsinformatik 2018
FachnameEffiziente Algorithmen
Prüfungsnummer2200366
Leistungspunkte5
Präsenzstudium (h)45
Selbststudium (h)105
VerpflichtungWahlpflicht
Abschlussmündliche Prüfungsleistung, 30 Minuten
Details zum Abschluss
max. Teilnehmerzahl
Spezifik im Studiengang Master Mathematik und Wirtschaftsmathematik 2013 (AM), Master Mathematik und Wirtschaftsmathematik 2013 (WM)
FachnameEffiziente Algorithmen
Prüfungsnummer2200366
Leistungspunkte4
Präsenzstudium (h)45
Selbststudium (h)75
VerpflichtungWahlpflicht
Abschlussmündliche Prüfungsleistung, 30 Minuten
Details zum Abschluss
max. Teilnehmerzahl
Spezifik im Studiengang Master Informatik 2013
FachnameEffiziente Algorithmen
Prüfungsnummer2200366
Leistungspunkte5
Präsenzstudium (h)45
Selbststudium (h)105
VerpflichtungPflicht
Abschlussmündliche Prüfungsleistung, 30 Minuten
Details zum Abschluss
max. Teilnehmerzahl

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