Ruprecht-Karls-Universität Heidelberg




Prüfungsstoff für die Vorlesung
"Effiziente Algorithmen II"

Komplexität

  • Klassifikation von Entscheidungsproblemen
  • Klassifikation von Optimierungsproblemen
  • Gütegarantien
  • Approximation und NP-Vollständigkeit
Approximative Algorithmen
  • Maschinenbelegung mit unabhängigen Aufgaben
  • Maschinenbelegung mit abhängigen Aufgaben
  • Knoten-Überdeckungs-Problem
  • Bin-Packing-Problem
  • Subset-Sum-Problem
  • Knapsack-Problem
  • Traveling-Salesman-Problem
  • Set-Covering-Problem
Relaxierungen
  • Kombinatorische Relaxierungen
  • LP-Relaxierungen
  • Lagrange-Relaxierungen
Bestimmung von Optimallösungen
  • Dynamische Programmierung
  • Allgemeine Schnittebenenverfahren
  • Branch-and-Bound
  • Branch-and-Cut
  • Simulated Annealing
Polyedrische Kombinatorik
  • Berechnung linearer Beschreibungen
  • Allgemeine Resultate und Liftungssätze
Das Max-Cut-Problem
  • Anwendung: Via-Minimierung
  • Heuristiken für das Max-Cut-Problem
  • Das Cut-Polytop
  • Separierung für das Cut-Polytop


Erstellt am Feb 2, 2011
comopt{at}informatik.uni-heidelberg.de

optWay
Links