Technische Universität Ilmenau

Effiziente Algorithmen - Modultafeln der TU Ilmenau

Die Modultafeln sind ein Informationsangebot zu den Studiengängen der TU Ilmenau.

Die rechtsverbindlichen Studienpläne entnehmen Sie bitte den jeweiligen Studien- und Prüfungsordnungen (Anlage Studienplan).

Alle Angaben zu geplanten Lehrveranstaltungen finden Sie im elektronischen Vorlesungsverzeichnis.

Informationen und Handreichungen zur Pflege von Modulbeschreibungen durch die Modulverantwortlichen finden Sie unter Modulpflege.

Hinweise zu fehlenden oder fehlerhaften Modulbeschreibungen senden Sie bitte direkt an modulkatalog@tu-ilmenau.de.

Modulinformationen zu Modulnummer 100530 - allgemeine Informationen
Modulnummer100530
FakultätFakultät für Informatik und Automatisierung
Fachgebietsnummer2242 (Komplexitätstheorie und Effiziente Algorithmen)
Modulverantwortliche(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 und erworbene Kompetenzen

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 und technische Anforderungen bei Lehr- und Abschlussleistungen in elektronischer Form

zum Moodle-Kurs

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)

WS 2018/19 (Vorlesung, Übung)

Hospitation:

Spezifik Referenzmodul
ModulnameEffiziente Algorithmen
Prüfungsnummer2200366
Leistungspunkte5
SWS4
Präsenzstudium (h)45
Selbststudium (h)105
VerpflichtungPflichtmodul
Abschlussmündliche Prüfungsleistung, 30 Minuten
Details zum Abschluss
Alternative Abschlussform aufgrund verordneter Corona-Maßnahmen inkl. technischer Voraussetzungen

Prüfungsgespräch (mündliche Abschlussleistung) in Distanz nach §6a PStO-AB

Dauer: 30 Minuten

Technische Voraussetzung: Webex https://intranet.tu-ilmenau.de/site/vpsl-pand/SitePages/Handreichungen_Arbeitshilfen.aspx

Anmeldemodalitäten für alternative PL oder SL
max. Teilnehmerzahl
Spezifik im Studiengang Master Wirtschaftsinformatik 2014, Master Wirtschaftsinformatik 2015, Master Wirtschaftsinformatik 2018
ModulnameEffiziente Algorithmen
Prüfungsnummer2200366
Leistungspunkte5
Präsenzstudium (h)45
Selbststudium (h)105
VerpflichtungWahlmodul
Abschlussmündliche Prüfungsleistung, 30 Minuten
Details zum Abschluss
Alternative Abschlussform aufgrund verordneter Corona-Maßnahmen inkl. technischer Voraussetzungen

Prüfungsgespräch (mündliche Abschlussleistung) in Distanz nach §6a PStO-AB

Dauer: 30 Minuten

Technische Voraussetzung: Webex https://intranet.tu-ilmenau.de/site/vpsl-pand/SitePages/Handreichungen_Arbeitshilfen.aspx

Anmeldemodalitäten für alternative PL oder SL
max. Teilnehmerzahl
Spezifik im Studiengang Master Mathematik und Wirtschaftsmathematik 2013 (WM), Master Mathematik und Wirtschaftsmathematik 2013 (AM)
ModulnameEffiziente Algorithmen
Prüfungsnummer2200366
Leistungspunkte4
Präsenzstudium (h)45
Selbststudium (h)75
VerpflichtungWahlmodul
Abschlussmündliche Prüfungsleistung, 30 Minuten
Details zum Abschluss
Alternative Abschlussform aufgrund verordneter Corona-Maßnahmen inkl. technischer Voraussetzungen

Prüfungsgespräch (mündliche Abschlussleistung) in Distanz nach §6a PStO-AB

Dauer: 30 Minuten

Technische Voraussetzung: Webex https://intranet.tu-ilmenau.de/site/vpsl-pand/SitePages/Handreichungen_Arbeitshilfen.aspx

Anmeldemodalitäten für alternative PL oder SL
max. Teilnehmerzahl
Spezifik im Studiengang Master Informatik 2013
ModulnameEffiziente Algorithmen
Prüfungsnummer2200366
Leistungspunkte5
Präsenzstudium (h)45
Selbststudium (h)105
VerpflichtungPflichtmodul
Abschlussmündliche Prüfungsleistung, 30 Minuten
Details zum Abschluss
Alternative Abschlussform aufgrund verordneter Corona-Maßnahmen inkl. technischer Voraussetzungen

Prüfungsgespräch (mündliche Abschlussleistung) in Distanz nach §6a PStO-AB

Dauer: 30 Minuten

Technische Voraussetzung: Webex https://intranet.tu-ilmenau.de/site/vpsl-pand/SitePages/Handreichungen_Arbeitshilfen.aspx

Anmeldemodalitäten für alternative PL oder SL
max. Teilnehmerzahl