Technische Universität Ilmenau

Effiziente Algorithmen 2 - 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 2 im Studiengang Master Informatik 2009
ACHTUNG: wird nicht mehr angeboten!
Fachnummer8225
Prüfungsnummer2200230
FakultätFakultät für Informatik und Automatisierung
Fachgebietsnummer 2242 (Komplexitätstheorie und Effiziente Algorithmen)
Fachverantwortliche(r)Prof. Dr. Martin Dietzfelbinger
TurnusWintersemester
SpracheDeutsch
Leistungspunkte4
Präsenzstudium (h)34
Selbststudium (h)86
VerpflichtungPflicht
Abschlussmündliche Prüfungsleistung, 30 Minuten
Details zum Abschluss
max. Teilnehmerzahl
Vorkenntnisse

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

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

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

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

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