|
Modulcode:
|
A5.3.5
|
|
Englische Bezeichnung:
|
Advanced Practical (Efficient Algorithms)
|
|
Modulverantwortliche(r):
|
Prof. Dr. Klaus Jansen
|
|
Turnus:
|
unregelmäßig
(WS09/10, SS10, WS10/11)
|
|
Präsenzzeiten:
|
4PÜ
|
|
ECTS:
|
8
|
|
Workload:
|
240 Std.
|
|
Dauer:
|
ein Semester
|
|
Modulkategorien:
|
A5 (alte Module)
|
|
Lehrsprache:
|
Deutsch
|
In diesem Praktikum sollen Algorithmen aus der theoretischen Forschung in Java implementiert
und ihre Qualität in Hinblick auf Laufzeit und Güte anhand konkreter Instanzen
geprüft werden.
Die Studenten erwerben oder vertiefen folgende Fertigkeiten:
- Design und Implementierung von Datenstrukturen für angewandte Probleme
- Umsetzung von nur auf abstrakter Ebene gegebenen Algorithmen in einer konkreten
Programmiersprache
- Evaluierung von Algorithmen in Hinblick auf Geschwindigkeit und Güte der erzeugten
Lösungen
Algorithmische Lösungen für praxisrelevante kombinatorische Optimierungsprobleme wie
z.B. Packungsprobleme und kürzeste-Wege-Probleme sind ein wichtiger Teil der Informatik.
Diese Algorithmen werden zugunsten einer besseren Verständlichkeit oft nur in
verknappter Form, z.B. als Pseudocode, angegeben, und ihre Laufzeit nur in O-Notation
betrachtet. Zwischen dieser akademischen Darstellung und einer konkreten lauffähigen
Implementierung liegt eine gewisse Lücke, die von den Studenten in diesem Praktikum
gefüllt wird.
Es werden also Algorithmen, die im üblichen Detailgrad der Forschung gegeben sind,
konkret implementiert. Dies beginnt beim Design der Datentypen, führt über die eigentliche
Umsetzung, mit Augenmerk auf Details wie Rundungsgenauigkeiten bei Gleitkommazahlen
etc. und endet mit einem Test anhand konkreter Beispielinstanzen.
Der Problemkreis, der behandelt wird, wechselt von Semester zu Semester.
Java-Kenntnisse; Besuch der Vorlesung "Effiziente Algorithmen" kann hilfreich sein, ist
aber nicht zwingend notwendig.
Prüfung am Ende der Veranstaltung.