Effiziente Algorithmen (EAL)

Master Informatik
1. Semester

Termine und Allgemeines für das WiSe 2024/25

Vorbereitung: Das Buch Goebbels, Rethmann: Eine Einführung in die Mathematik an Beispielen aus der Informatik. Springer Spektrum. eignet sich gut zum Auffrischen der Mathematikkenntnisse zwischen Bachelor- und Master-Studium. Das Besondere an dem Buch sind die vielen Querbezüge zur Informatik und die ausführlichen Herleitungen mit vielen Zwischenschritten.

Arbeitsaufwand: Das Modul EAL ist mit sechs Leistungspunkten (CP) in der Prüfungsordnung angegeben. Laut der Verordnung zur Regelung des Näheren der Studienakkreditierung in Nordrhein-Westfalen (Studienakkreditierungsverordnung - StudakVO) vom 25.01.2018, Paragraph 8 Leistungspunktesystem, Satz (1) entspricht ein Leistungspunkt einer Gesamtarbeitsleistung von 25 bis höchstens 30 Zeitstunden. Insgesamt ergibt sich also ein Arbeitsaufwand von 150 Stunden im Semester, bei der 30 Stunden für die Vorbereitung auf die Klausur enthalten sind. Die 120 Stunden verteilen sich bei 15 Wochen Vorlesungszeit im Semester auf acht Stunden pro Woche.

Inhalt

• Einführung Bewertung von Algorithmen, Berechenbarkeitstheorie, Komplexitätstheorie
• Algorithmen für schwere Probleme 3-KNF-SAT, Vertex-Cover, Independent-Set
• Entwurfsmethoden divide & conquer, greedy, dynamic programming, local search
• Graphalgorithmen Tiefen- und Breitensuche, Zusammenhangsprobleme, Netzwerkfluss, Matching
• spezielle Graphklassen Bäume und Co-Graphen, chordale Graphen, Vergleichbarkeitsgraphen, planare Graphen
• Vorrangwarteschlangen Linksbäume, Binomial-Heap, Fibonacci-Heap
• Amortisierte Laufzeitanalyse Dynamic Tables, Selbstanordnende Listen, Fibonacci-Heaps, Splay-Bäume, Union-Find-Datenstruktur
• Algorithmen für moderne Hardware Lokalität der Daten, externe Datenstrukturen
• Algorithmen für geometrische Probleme Scan-Line-Prinzip, Konvexe Hülle

Literatur

• St.J. Goebbels, J. Rethmann: Eine Einführung in die Mathematik an Beispielen aus der Informatik. Springer Spektrum, Berlin, Heidelberg, 2023.
• T. Ottmann, P. Widmayer: Algorithmen und Datenstrukturen. Spektrum Akademischer Verlag.
• Uwe Schöning: Algorithmen - kurz gefasst. Spektrum Akademischer Verlag.
• T.H. Cormen, C.E. Leiserson, R.L. Rivest: Introduction to Algorithms. MIT Press.
• Robert Sedgewick: Algorithms. Addison-Wesley.
• A.V. Aho, J.E. Hopcroft, J.D. Ullman: Datastructures and Algorithms. Addison-Wesley.
• Jon Kleinberg, Éva Tardos: Algorithm Design. Pearson-Addison Wesley.
• Rolf Klein: Algorithmische Geometrie. Springer Verlag.
• M. de Berg, O. Cheong, M. van Kreveld, M. Overmars: Computational Geometry. Springer Verlag.
• S.O. Krumke, H. Noltemeier: Graphentheoretische Konzepte und Algorithmen. Springer Vieweg.
• Juraj Hromkovič: Randomisierte Algorithmen. Vieweg + Teubner Verlag.

Folien

In der Veranstaltung erstellte Programme

zurück zur Startseite