Technische Universität Ilmenau

Effiziente Algorithmen 2 - 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 Effiziente Algorithmen 2 im Studiengang Master Informatik 2009
ACHTUNG: wird nicht mehr angeboten!
Modulnummer8225
Prüfungsnummer2200230
FakultätFakultät für Informatik und Automatisierung
Fachgebietsnummer 2242 (Komplexitätstheorie und Effiziente Algorithmen)
Modulverantwortliche(r)Prof. Dr. Martin Dietzfelbinger
TurnusWintersemester
SpracheDeutsch
Leistungspunkte4
Präsenzstudium (h)34
Selbststudium (h)86
VerpflichtungPflichtmodul
Abschlussmündliche Prüfungsleistung, 30 Minuten
Details zum Abschluss
Alternative Abschlussform aufgrund verordneter Corona-Maßnahmen inkl. technischer Voraussetzungen
Anmeldemodalitäten für alternative PL oder SL
max. Teilnehmerzahl
Vorkenntnisse

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

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

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.

Medienformen und technische Anforderungen bei Lehr- und Abschlussleistungen in elektronischer Form

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

Literatur

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

Lehrevaluation

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