Efficient Algorithms - Interactive curriculae of TU Ilmenau

Bachelorstudium Informatik, insbesondere:

Algorithmen und Programmierung

Algorithmen und Datenstrukturen 1 und 2

Mathematik 1 und 2

Grundlagen und Diskrete Strukturen

Fach- und Methodenkompetenz: 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. 

In der Vorlesung konnten die notwendigen Kenntnisse und Methoden erworben werden; durch die Übungen sind die Studierenden darin geübt, die Methoden in neuen Aufgabenstellungen selbst anzuwenden und dabei eigene, selbständige, gut begründete Überlegungen anzustellen, im Rahmen der erlernten Methoden und des Standes der Technik. 

Sozialkompetenz: Die Studierenden haben in den Übungen die Gelegenheit genutzt, eigene Lösungen zu präsentieren und damit der Diskussion in der Gruppe auszusetzen. Wertschätzende Diskussion durch die Gruppe wurde angeleitet, beim Vortrag konnten die Studierenden wertvolle Erfahrung in der Rolle der Präsentierenden machen.

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.

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.

Bereitgestellt: Skript auf der Webseite

Tafelvortrag, Presenter-Projektion, Folien

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
  

Berkholz