Prof. Dr. Jochen Rethmann
Hochschule Niederrhein
Fachbereich Elektrotechnik und Informatik
Reinarzstraße 49
47805 Krefeld
Fon: 0 21 51 / 8 22 - 46 33
Fax: 0 21 51 / 8 22 - 46 66
E-Mail: jochen.rethmann(at)hsnr.de
Letzte Änderung: 21.01.2020
Effiziente Algorithmen (EAL)
Master Informatik
1. Semester
Termine und Allgemeines für das Wintersemester 2019/20
Form: |
seminaristische Lehrveranstaltung |
Voraussetzungen: |
keine |
Präsenz: |
Dienstag 8:15 Uhr bis 11:45 Uhr, Raum B 312
Mittwoch 14:00 Uhr bis 15:45 Uhr, Raum B 322 |
Vorbereitung:
Das Buch Goebbels, Rethmann: Mathematik für Informatiker. Springer
Vieweg. 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,
parametrisierte Probleme
- Entwurfsmethoden
divide & conquer,
dynamic programming,
greedy,
local search
- Sortieren
Shell-Sort,
Quick-Sort-Varianten,
Merge-Sort,
Heap-Sort,
untere Schranken,
Counting- / Radix-Sort
- Auswahlproblem (Median-Berechnung)
randomisiert,
worst-case
- Graphalgorithmen
Tiefen- und Breitensuche,
Zusammenhangsprobleme,
Minimale Spannbäume,
Kürzeste Wege,
Netzwerkfluss,
Matching-Probleme,
spezielle Graphklassen
- Vorrangwarteschlangen
Linksbäume,
Binomial-Queues,
Fibonacci-Heaps
- Textsuche
Rabin-Karp,
Knuth-Morris-Pratt,
Boyer-Moore,
Suffix-Bäume
- Suchbäume
AVL-Bäume,
Red-Black-Trees,
B-Bäume,
Splay-Bäume
- Amortisierte Laufzeitanalysen
Dynamic Tables,
Selbstanordnende Listen,
Fibonacci-Heaps,
Splay-Bäume
- Algorithmische Geometrie
Scan-Line-Prinzip,
Konvexe Hülle,
Voronoi-Diagramme,
Datenstrukturen
- Randomisierte Algorithmen
Literatur
- St.J. Goebbels, J. Rethmann: Mathematik für Informatiker.
Springer Vieweg, Heidelberg, 2014.
- 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
alle Folien
Praktikum / Projekt
Das Praktikum wird in Form eines Projektes durchgeführt.
Projektvorschläge
In der Veranstaltung erstellte Programme
zurück zur Startseite