- Institute of Operating Systems and Computer Networks
- News
- About us
- Connected and Mobile Systems
- Distributed Systems
- Algorithms
- Microprocessor Lab
- Education
- Services
- Spin-Offs
- Research Cooperations
Algorithm Engineering
Semester | Summer 2009 | ||||||||||||||
Module # | INF-ALG-05 | ||||||||||||||
Event # | INF-ALG-009, INF-ALG-010 | ||||||||||||||
Programmes | Computer Science Master, Computer and Communication Systems Engineering Master, Business Information Systems Master | ||||||||||||||
IBR Group | ALG (Prof. Fekete) | ||||||||||||||
Type | Lecture & Exercise | ||||||||||||||
Lecturer | Dr. Alexander Kröller Ehemaliger Juniorprofessor | ||||||||||||||
Credits | 4 | ||||||||||||||
Hours | 2+1 | ||||||||||||||
Time & Place | Vorlesung: Mittwoch, 14:15 - 14:45, IZ 251. | ||||||||||||||
Prerequisites | keine | ||||||||||||||
Certificates | Erfolgreiche Bearbeitung der Hausaufgaben und erfolgreiche Teilnahme an der mündlichen Prüfung. | ||||||||||||||
Content | Algorithm Engineering hat sich in jüngster Zeit als eigenständiges Teilgebiet der Algorithmik etabliert. Die klassische Algorithmik konzentriert sich hauptsächlich auf theoretische Analysen unter oft stark vereinfachenden, unrealistischen Voraussetzungen. Im Algorithm Engineering versucht man dagegen praxisrelevante Aspekte soweit wie möglich bei dem Entwurf, der Implementierung und der Analyse von Algorithmen zu berücksichtigen. Im Mittelpunkt steht dabei ein von falsifizierbaren Hypothesen getriebener Kreislauf aus Entwurf, Analyse, Implementierung, und experimenteller Bewertung von praktikablen Algorithmen. Realistische Modelle, für Maschinen und Anwendungen, sowie Algorithmenbibliotheken und Sammlungen realer Eingabeinstanzen erlauben eine zusätzliche Kopplung an Anwendungen. ÜbungstermineDie Übung findet offiziell "14-tägig" statt. Das ist leider aufgrund von Feier- und Abwesenheitstagen meinerseits so nicht umsetzbar. Daher hier die genauen Daten: 20.4., 11.5., 25.5. 15.6., 29.6., 6.7. Materialen
Hinweise zu Linearer ProgrammierungIhr könnt euch hier einen IBR-Account anlegen. Damit könnt ihr euch auf
Die ZIB Optimization Suite ist freie Software und kann hier bezogen werden. CPLEX ist kommerziell. Insbesondere die Dokumentation von ZIMPL könnte hilfreich sein. Die wichtigsten Befehle an der CPLEX/SCIP-Kommandozeile lauten:
Das CPLEX LP-Format ist im Wesentlichen selbsterklärend. Die Dateiendung muss Hier ist ein erklärendes Beispiel: Maximize \ hier kann auch "Minimize" stehen, \ Der "\" ist das Kommentarzeichen und dient auch \ dazu, Zeilen umzubrechen 2x + 4 hallo - 0.8172 x_99 Subject To \ Hier kommen die Nebenbedingungen: 2x + 4y >= 1 99z - 99a = 4 2a + 2b <= 99 Integers \ Hier werden die Variablen gelistet, für die eine \ ganzzahlige Zuweisung gefordert ist: z1 z2 z3 Binary \ Hier werden Binärvariablen gelistet (die dann \ in der Integers-Section oben nicht mehr aufgeführt \ werden müssen. b1 b2 b3 Bounds \ Hier wird der zulässige Zahlenbereich der \ Variablen definiert: x1 >= 0 0 <= x2 <= 999 End \ muss am Ende stehen! |