Prof. Dr. Jochen Rethmann
Hochschule Niederrhein
Fachbereich Ingenieurwissenschaften 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: 26.03.2026
Wahlpflichtmodul 2: Spezielle Themen der Algorithmik (ALD2)
Master Informatik
3. Semester
Termine und Allgemeines für das SoSe 2026
| Form: |
seminaristische Lehrveranstaltung |
| Voraussetzungen: |
keine |
| Vorkenntnisse: |
Grundlegende Kenntnisse der theoretischen Informatik
Grundlagen über Algorithmen und Datenstrukturen |
| Präsenz: |
Mittwoch 8:15 Uhr bis 11:45 Uhr, Raum B E08
zweimal 90 Minuten Unterricht, dazwischen 30 Minuten Pause |
Arbeitsaufwand:
Das Modul WPM2 ist mit fünf 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
125 Stunden im Semester, bei der 25 Stunden für die Vorbereitung
auf die Klausur enthalten sind. Die restlichen 100 Stunden verteilen
sich bei 15 Wochen Vorlesungszeit im Semester auf sechseinhalb Stunden
pro Woche.
Inhalt
- Algorithmen für geometrische Probleme
Scan-Line-Prinzip,
Konvexe Hülle,
Voronoi-Diagramme
- Logik
Programmieren in Prolog,
Monadische Prädikatenlogik zweiter Ordnung (MSO) zum Lösen
von Graphproblemen
- Algorithmen für verteilte Systeme
Logische Ordnung,
Wechselseitiger Ausschluss,
Wahlalgorithmen,
Konsensalgorithmen
- Textsuche
Rabin-Karp,
Knuth-Morris-Pratt,
Boyer-Moore,
Suffix-Bäume
- Approximative Algorithmen
Güte,
Approximationsschemata,
Min Metric TSP,
Job Scheduling,
Max Knapsack
- Randomisierte Algorithmen
- Online-Algorithmen
- Exponentialzeit Algorithmen
Literatur
- Rolf Klein: Algorithmische Geometrie. Springer Verlag.
- M. de Berg, O. Cheong, M. van Kreveld, M. Overmars:
Computational Geometry. Springer Verlag.
- Ivan Bratko: PROLOG - Programming for Artificial Intelligence.
3rd edition, Addison-Wesley, 2000.
- L. Sterling, E. Shapiro: Prolog - Fortgeschrittene Programmiertechniken.
3rd edition, Addison-Wesley, 1988.
- Rolf Wanka: Approximationsalgorithmen. Teubner B.G
- Juraj Hromkovič: Randomisierte Algorithmen. Vieweg + Teubner
Verlag.
- F. Gurski, I. Rothe, J. Rothe, E. Wanke: Exakte Algorithmen für
schwere Graphenprobleme. Springer Verlag
- 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.
- Jon Kleinberg, Éva Tardos: Algorithm Design.
Pearson-Addison Wesley.
Folien
werden noch bereitgestellt ...
zurück zur Startseite