Modulbeschreibung Algorithmik
Master-Wahlpflichtmodul: Algorithmik
1. Modulkennung
WPM4
2. Studiengang
Bachelorstudiengang Informatik, Masterstudiengang Informatik, Masterstudiengang Bioinformatik
3. Modulbezeichnung
Algorithmik (ALG), engl.: Algorithmics (ALG)
4. Modul-Verantwortliche/r
Rarey
5. VeranstalterIn/DozentIn
Jantzen, Rarey
6. Sprache
Deutsch mit deutsch- und englischsprachigem Lehrmaterial
7. Motivation, Bedeutung für / Stellung im Gesamtprogramm
Die Entwicklung von Algorithmen zur Lösung von Problemen mit dem Computer sind zentraler Bestandteil der Informatik. Unabhängig von einer späteren Ausrichtung in theoretischer, praktischer und anwendungsbezogener Informatik sind fundamentale Kenntnisse in dem Prozess des Algorithmenentwurfs unabdingbar. Jeder Informatiker sollte zudem eine Reihe von grundlegenden Algorithmen und Datenstrukturen kennen, um diese als Teillösungen für komplexe Fragestellungen gewinnbringend einsetzen zu können. Aufbauend auf AD1 und FGI werden weiterführende Algorithmen und die zugrundeliegenden Analysen präsentiert. Dabei werden Schwerpunkte in den Bereichen Graphalgorithmen, algorithmische Geometrie und Lösung komplexer Optimierungsprobleme gelegt.
8. Lernziele/Kompetenzen
8.1 Passung Leitbild
- Vermittlung von Problemlösungskompetenz (Konzeptionalisierung und Realisierung) zur Lösung formalisierbarerer, schwieriger Probleme meist kombinatorischer Struktur
8.2 Grundlagen-/Faktenwissen
- Entwurfsmethoden für effiziente Datenstrukturen und Algorithmen
- Effiziente Datenstrukturen und Algorithmen für ausgewählte Probleme
- Methoden zur Effizienzanalyse von Algorithmen und Datenstrukturen
8.3 Methodenwissen
- Selbständiges, kreatives Entwickeln von Algorithmen und Datenstrukturen („Wie gestalte ich den kreativen Prozess vom algorithmischen Problem zum effizienten Algorithmus?“)
- Einsetzen mathematischer Methoden zur Effizienzanalyse
- Einschätzen der Qualität von Algorithmen und algorithmischen Ansätzen unter Effizienzaspekten
- Selbständiges Aneignen von neuen Algorithmen, Datenstrukturen und algorithmischen Ideen und Analysen
8.4 Transferkompetenz
- Fähigkeit zum selbständigen Aneignen von neuen Algorithmen, Datenstrukturen, sowie algorithmischen Ideen und Analysen
- Übertragen bekannter Algorithmen auf neue Problemstellungen
- Modifikation von Algorithmen im Hinblick auf veränderte Anforderungen
- Entwicklung neuer Algorithmen für anwendungsbezogene Problemstellungen
- Einsetzen mathematischer Methoden zum Korrektheitsbeweis und zur Effizienzanalyse
8.5 Normativ-bewertende Kompetenz
- Beurteilen der Qualität von Algorithmen und algorithmischen Ansätzen im Hinblick auf Problemadäquatheit, Effizienz, Korrektheit, Vollständigkeit und praktische Verwertbarkeit
- Erkennen grundlegender Beschränkungen von gegebenen Algorithmen
- Einschätzen von Informationsverarbeitungsproblemen in Hinblick auf ihre algorithmische Komplexität
8.6 ABK/BOK/Schlüsselqualifikationen
- Kooperations- und Teamfähigkeit in den Präsenzübungen
- Strategien des Wissenserwerbs: Kombination aus Vorlesung, Vor- und Nachbereitung am Vorlesungsmaterial, Präsenzübungen mit betreuter Gruppenarbeit, Hausaufgaben und Zentralübung
- Kreatives Problemlösen am Beispiel der Entwicklung effizienter Algorithmen
- 4 SWS Vorlesung Algorithmik
- 2 SWS Übungen (Präsenzübungen, Kleingruppen)
10. Inhalt
- Weiterführende Graphalgorithmen: All-Pairs / algebraische kürzeste Wege, Minimale Spannbäume, Netzwerk-Flussalgorithmen, Matching
- Einführung in Algorithmische Geometrie: Schnittprobleme, Algorithmen und Datenstrukturen zur Raumanfrage, Konvexe Hüllen, Voronoi-Diagramme und Delauney-Triangulierung, kleinste umschließende Kreise, Lineare Programmierung
- Analyse und Lösung NP-schwerer Optimierungsprobleme: Reduktionsbeweise, Approx-imationsalgorithmen (Set Cover und geometrisches TSP), polynomielle Approx-imationsschemata, Branch&Bound mit Relaxation, heuristische Techniken
11. Bezüge zu anderen Modulen
- Innerhalb des Studienganges: Das Modul bietet die Möglichkeit zur Vertiefung im Themenbereich Algorithmen und Datenstrukturen. Ein inhaltlicher Bezug besteht u.a. zu dem Wahlpflichtmodul Grundlagen der Wissensverarbeitung.
- Im konsekutiven Masterstudiengang: Ein inhaltlicher Bezug besteht u.a. zu dem Wahlpflichtmodul Interaktives Visuelles Computing.
Vertiefungsmodule des Master-Studiengangs Informatik bauen auf diesem Modul inhaltlich auf. - In anderen Studiengängen: Das Modul eignet sich als Bestandteil von Wirtschafts- und Bioinformatik-Studiengängen. Darüber hinaus ist ein Einbringen als Wahlmodul im Rahmen naturwissenschaftlicher Studiengänge bedingt denkbar.
12. Modulvoraussetzungen
Im Bachelor-Studiengang Informatik:- Verbindlich: 72 Leistungspunkte, Algorithmen und Datenstrukturen
- Empfohlen: Softwareentwicklung I, Softwareentwicklung II, Diskrete Mathematik, Formale Grundlagen der Informatik I und II
- Verbindlich: keine
- Empfohlen: keine
13. Semester, Studienjahr /-phase
Im Bachelor-Studiengang Informatik:- Studienabschnitt: 2
- Referenzsemester: keins
- Empfohlenes Semester: 5
Studiensemester: Empfohlenes Semester: 1 oder 3 (bei Zulassung im Wintersemester), 2 (bei Zulassung im Sommersemester)
14. Prüfungsleistungen
Die Zulassung zur Modulprüfung setzt die regelmäßige und erfolgreiche Teilnahme
an Übungen/Seminar/Praktikum voraus; die Teilnahme an Übungen/Praktikum gilt
grundsätzlich als erfolgreich, wenn alle Aufgaben bearbeitet und mindestens 50%
richtig gelöst wurden; die Teilnahme an einem Seminar gilt grundsätzlich als
erfolgreich, wenn das zugeordnete Themenfeld verstanden, angemessen präsentiert
und ggf. angemessen schriftlich aufgearbeitet wurde; im Falle abweichender
Kriterien müssen diese zu Beginn der Veranstaltung bekannt gemacht werden.
Gemeinsame Modulprüfung für alle Lehrveranstaltungen des Moduls; mündlich und
in der Unterrichtssprache.
15. Bewertung
Gesamt: 9 Leistungspunkte
(Vorlesung Algorithmik: 5 Leistungspunkte, Übungen/Seminar/Praktikum zu Algorithmik: 4 Leistungspunkte)
16. Periodizität
Wintersemester, jährlich, Dauer: 1 Semester
17. Methodische Aufbereitung und Medienformen
- Vorlesung mit Beamer, Overhead und Tafel
- Übungen in Kleingruppen
- Erwartete Aktivitäten der Studierenden: Mitarbeit bei Präsenzübungen, Hausaufgaben (Bearbeitung von Übungsblättern)
18. Literatur
- T.H. Corman, C.E. Leiserson, R.L. Rivest & C. Stein: Introductions to Algorithms, MIT-Press (2003)
- M. de Berg, M. van Kreveld, M. Overmars, O. Schwarzkopf: Computational Geometry Algorithms and Applications, Springer Verlag (2000)
- K. Mehlhorn, S. Näher: Leda: A Platform for Combinatorial and Geometric Computing, Cambridge University Press (2000)
- G. Ausiello et .al.: Complexity and Approximation, Springer (2003)
- J. Hromkovič: Algorithms for Hard Problems, Springer (2003)
- I. Gerdes, F. Klawonn, R. Kruse: Evolutionäre Algorithmen, Vieweg (2004)
