close

Anmelden

Neues Passwort anfordern?

Anmeldung mit OpenID

Einführung - KIT

EinbettenHerunterladen
Algorithmen für schwierige Optimierungsprobleme
Vorlesung für den Bereich Bachelor Informatik
Dozent: Juniorprof. Dr. Henning Meyerhenke
PARALLELES RECHNEN
INSTITUT FÜR THEORETISCHE INFORMATIK, FAKULTÄT FÜR INFORMATIK
KIT – Universität des Landes Baden-Württemberg und
nationales Forschungszentrum in der Helmholtz-Gemeinschaft
www.kit.edu
21. Oktober 2014
VORLESUNG 1
Einführung
2
H. Meyerhenke: Kombinatorische Optimierung
Paralleles Rechnen, Institut für Theoretische
Informatik, Fakultät für Informatik
Begriffserklärungen
!  Algorithmische Methoden
!   Welche?
für
!  schwere Optimierungsprobleme
!   Was?
!   Welche?
3
H. Meyerhenke: Kombinatorische Optimierung
Paralleles Rechnen, Institut für Theoretische
Informatik, Fakultät für Informatik
Behandelte Probleme (was und welche)
!   Klassische NP-schwere kombinatorische
Optimierungsprobleme mit hohem Praxisbezug
!   Typische Problemstellung: Finde aus einer (meist großen)
Menge von diskreten Elementen eine optimale Teilmenge
!   Optimierung anhand einer Zielfunktion, die von einer großen
Zahl von Variablen abhängt
!   Berücksichtigung von Nebenbedingungen
!   Welche Beispiele kennen Sie bereits?
4
H. Meyerhenke: Kombinatorische Optimierung
Paralleles Rechnen, Institut für Theoretische
Informatik, Fakultät für Informatik
Beispielprobleme
!   Bohrpunktproblem:
!   Finde kostenminimale Tour für
Bohrer
http://www.dj5am.de/cw-geber/leiterplatte.gif
!   Job-Zuordnungsproblem:
!   Weise Arbeiter an Jobs zu
(Rechenzentrum)
Universität Paderborn, PC2
5
H. Meyerhenke: Kombinatorische Optimierung
Paralleles Rechnen, Institut für Theoretische
Informatik, Fakultät für Informatik
Motivation
!   Hoher Bedarf an Optimierern in der Wirtschaft:
!
!
!
!
!
 
 
 
 
 
Beratung
Logistik
Energie
Produktionsplanung
...
[http://blog.121watt.de/blog/5-regeln-fur-erfolgreiche-landingpages]
!   Verbindung von
!   Theorie (Komplexität, Approximationsalgorithmen) und
!   Praxis (Anwendungsproblem, Heuristiken, Metaheuristiken)
6
H. Meyerhenke: Kombinatorische Optimierung
Paralleles Rechnen, Institut für Theoretische
Informatik, Fakultät für Informatik
Vorlesungsübersicht
Problemstellungen
!
!
!
!
!
!
7
  Bin-Packing
  TSP
  SAT
Graphclustering
Grapheinbettung
  Graphpartitionierung
H. Meyerhenke: Kombinatorische Optimierung
Anwendungen
!
!
!
!
!
!
Verschnittprobleme
  Routing (Warenhaus, Schulbus)
  Konfiguration von Autos
  Community Detection
  Parallele Prozesse
  Numerische Simulationen
Paralleles Rechnen, Institut für Theoretische
Informatik, Fakultät für Informatik
Vorlesungsübersicht (welche Methoden)
!   Typische Abarbeitung der einzelnen Themen:
!   Motivation durch Anwendungsfall
!   Komplexität
!   Approximationsergebnisse
„Es gibt nichts
Praktischeres als eine
gute Theorie.“
! Heuristiken
! Metaheuristiken
!   Problemvarianten und/oder
weitere Anwendungsfälle
In der Theorie gibt es
keinen Unterschied
zwischen Theorie und
Praxis; in der Praxis
hingegen gibt es einen
großen Unterschied.“
(Kurt Lewin)
(Al Roth)
8
H. Meyerhenke: Kombinatorische Optimierung
Paralleles Rechnen, Institut für Theoretische
Informatik, Fakultät für Informatik
Formale Anforderungen
Lernziele
Kurzversion
Kurzvortrag
!   Algorithmische Probleme formal formulieren
Seminararbeit
können
Hauptvortrag
!   Berechnungskomplexität algorithmischer
Aktive Teilnahme
Probleme analysieren und einschätzen
können
!   Algorithmen exemplarisch ausführen und ihre
Eigenschaften erklären können
!   Geeignete algorithmische Lösungstechniken
erkennen, entwerfen und auf unbekannte
Probleme anwenden können
[http://www.floridaipblog.com/uploads/image/trademar_checklist.jpg]
Image source: http://www.floridaipblog.com/uploads/image/trademar_chec
!   Algorithmen implementieren und hinsichtlich
ihrer Qualität, AnwendbarkeitHenning
und Meyerhenke,
Laufzeit
Roland Glantz:
10
Seminar
Algorithmentechnik
bewerten können
9
H. Meyerhenke: Kombinatorische Optimierung
Paralleles Rechnen, Institut für Theoretische
Informatik, Fakultät für Informatik
MEINE ARBEITSGRUPPE
10
H. Meyerhenke: Kombinatorische Optimierung
Paralleles Rechnen, Institut für Theoretische
Informatik, Fakultät für Informatik
Meine Stationen
!   Studium in Paderborn, Jena, Ottawa
!   2008: Promotion in Informatik an der
Uni Paderborn
!   Nach der Promotion zwei Jahre
Postdoc in Deutschland
!   Dann ein Jahr Postdoc im HPC Lab
des Georgia Institute of Technology
in Atlanta (Georgia, USA)
!   Seit Oktober 2011: JP für
Theoretische Informatik und
Paralleles Rechnen am ITI
11
H. Meyerhenke: Algorithmische Methoden zur Netzwerkanalyse
Paralleles Rechnen, Institut für Theoretische
Informatik, Fakultät für Informatik
Wiss. Mitarbeiter der Gruppe
Promovierter Wissenschaftler:
!   Dr.-Ing. Roland Glantz
Doktoranden:
!   Elisabetta Bergamini
!   Moritz von Looz
!   Christian Staudt
12
H. Meyerhenke: Kombinatorische Optimierung
Paralleles Rechnen, Institut für Theoretische
Informatik, Fakultät für Informatik
Beschleunigung von Simulationen
!   Effiziente Verteilung von
numerischen Simulationen auf
Parallelrechner, üblicherweise
modelliert als
Graphpartitionierungsproblem
!   Diffusionsbasierte Methoden
mit hoher Lösungsqualität bei
!   statischen und
!   dynamischen
Simulationen
13
H. Meyerhenke: Kombinatorische Optimierung
Paralleles Rechnen, Institut für Theoretische
Informatik, Fakultät für Informatik
Netzwerkanalyse
!   Parallele Analyse von Netzwerken:
!   BIG Data, unstrukturiert
!   Schwerpunkte:
!   Große Datenmengen
!   Dynamische Graphen
!   Benchmarking für neue parallele
Architekturen
!   Entwicklung neuer Analysealgorithmen
!   Beschleunigung durch Parallelisierung
Six degrees of Kevin Bacon
[Seok-Hee Hong]
!   Sonstiges:
!   Parallele Algorithmen aus
verschiedenen Bereichen (Graphen,
Strings, Geometrie)
14
H. Meyerhenke: Kombinatorische Optimierung
Paralleles Rechnen, Institut für Theoretische
Informatik, Fakultät für Informatik
Bachelor-/Masterarbeiten
!   Insbesondere in den vorher
genannten Themengebieten
!   Beschreibungen liegen aus und
sind auf Gruppenwebseite zu
Studium und Lehre:
[http://www.uni-rostock.de/weiterbildung/fernstudien/medien-bildung/masterabschluss/]
! http://parco.iti.kit.edu/lehre.shtml
!   Weitere Themen auf Anfrage
!   Bei Interesse einfach
ansprechen!
15
H. Meyerhenke: Kombinatorische Optimierung
[http://www.oc.tu-bs.de/dickschat/masterarbeiten_de.html]
Paralleles Rechnen, Institut für Theoretische
Informatik, Fakultät für Informatik
Organisatorisches
!   Termine:
!   Dienstags 11:30-13:00 Uhr im SR -118
!   Donnerstags 14:00-15:30 Uhr im SR 236
!   Übersicht auf
Vorlesungswebseite
!   SWS: 2+1
! LVNr: 2400013
!   Sprechstunde: Nach Vereinbarung (E-Mail)
[http://igd-r.fraunhofer.de/awf_organisatorisches/?L=1]
!   Webseite zur Vorlesung: http://parco.iti.kit.edu/henningm/lehre.shtml
16
H. Meyerhenke: Kombinatorische Optimierung
Paralleles Rechnen, Institut für Theoretische
Informatik, Fakultät für Informatik
Literatur
!   E. Talbi: Metaheuristics. From Design to
Implementation. John Wiley & Sons, 2009.
!   S. Luke:
Essentials of Metaheuristics. Lulu, 2009.
!   J. Hromkovic:
Algorithmics for Hard Problems.
Introduction to Combinatorial Optimization,
Randomization, Approximation, and
Heuristics. 2nd edition. Springer-Verlag,
2003.
!   R. Wanka: Approximationsalgorithmen.
Eine Einführung. Teubner, 2006.
!   T. Gonzalez (ed.): Handbook of
Approximation Algorithms and
Metaheuristics. Chapman & Hall, 2007.
!   B. Korte, J. Vygen: Kombinatorische
Optimierung. Theorie und Algorithmen. 2.
Auflage. Springer-Verlag, 2012.
17
H. Meyerhenke: Kombinatorische Optimierung
Paralleles Rechnen, Institut für Theoretische
Informatik, Fakultät für Informatik
Abschnitt 1:
EINLEITUNG UND MOTIVATION
18
H. Meyerhenke: Kombinatorische Optimierung
Paralleles Rechnen, Institut für Theoretische
Informatik, Fakultät für Informatik
Kombinatorisches Optimierungsproblem
!   Instanz eines komb. Optimierungsproblems ist Paar (L, f):
!   L ist abzählbare Menge aller möglicher Lösungen
!   Zielfunktion f weist jedem Element aus L einen Wert zu
!   Beispiel: Bohrpunktproblem
!   Instanz:
!   Aufgabe:
Eine Menge von Punkten p1, ..., pn 2 R2
Bestimmen Sie eine Permutation ¼, so dass
Σi=1n-1 d(p¼(i), p¼(i+1)) minimal ist.
!   Aufgabe: Lösen Sie die folgende Instanz:
!   a = (2,3), b = (5, 1), c = (4, 7), d = (3, 6)
!   Quadratische Distanzen: a zu b: 13, a zu c: 20, a zu d: 13; b zu c:
37, b zu d: 29; c zu d: 2
19
H. Meyerhenke: Kombinatorische Optimierung
Paralleles Rechnen, Institut für Theoretische
Informatik, Fakultät für Informatik
Vorgehensweise
!   Bei kleinen Instanzen:
c
!   „Ausprobieren“
!   Aufzählen aller Lösungen, Wahl
der besten
!   Anzahl möglicher Lösungen?
d
a
b
!   Was würden Sie bei großen
Instanzen tun?
20
H. Meyerhenke: Kombinatorische Optimierung
Paralleles Rechnen, Institut für Theoretische
Informatik, Fakultät für Informatik
Document
Kategorie
Bildung
Seitenansichten
13
Dateigröße
5 119 KB
Tags
1/--Seiten
melden