Navigation Zur Modulseite
Anzeigesprache

Diskrete Optimierung (ADM II)

10

Deutsch

#20088 / #1

Seit SS 2014

Fakultät II

MA 5-2

Institut für Mathematik

Keine Angabe

Skutella, Martin

Keine Angabe

skutella@math.tu-berlin.de

Keine Angabe

POS-Nummer PORD-Nummer Modultitel
36600 30483 Diskrete Optimierung (ADM II)

Lernergebnisse

In der Veranstaltung werden algorithmische und strukturelle Methoden der linearen, kombinatorischen und ganzzahligen Optimierung vermittelt und vertieft. Dazu gehort insbesondere die Komplexität linearer Programme, die Behandlung NP-schwerer Optimierungsprobleme sowie Theorie und Praxis der Lösung ganzzahliger Optimierungsprobleme. Fachkompetenz: 55% Methodenkompetenz: 30% Systemkompetenz: 10% Sozialkompetenz: 5%

Lehrinhalte

Simplex-Verfahren: revidierter Simplex-Algorithmus, dualer Simplexalgorithmus Pivotregeln, exponentielle Beispiele Polyedertheorie, Geometrie des Simplex-Verfahrens Primal-duale Algorithmen mit Anwendungen bei Graphen und Netzwerken Polynomiale Verfahren: Ellipsoid-Methode, innere-Punkte-Verfahren Ganzzahlige lineare Optimierung: Branch und Bound, Lagrange Relaxation, Schnittebenenverfahren Zuordnungsprobleme,Matchings, Matroide Polynomiale Techniken zur Behandlung NP-schwerer Probleme: Approximationsalgorithmen, Gutegarantien. Klassikation der Approximierbarkeit, stark- und schwach NP-vollstandig, MAX-SNP schwer.

Modulbestandteile

Pflichtteil:

Die folgenden Veranstaltungen sind für das Modul obligatorisch:

Lehrveranstaltungen Art Nummer Turnus Sprache SWS
Diskrete Optimierung (ADM II) VL 3236 L 236 SS Deutsch 4
Diskrete Optimierung (ADM II) TUT SS Deutsch 2
Diskrete Optimierung (ADM II) UE SS Deutsch 2

Arbeitsaufwand und Leistungspunkte

Diskrete Optimierung (ADM II) (VL):

Aufwandbeschreibung Multiplikator Stunden Gesamt
Präsenzzeit 15.0 4.0h 60.0h
Vor-/Nachbereitung 15.0 8.0h 120.0h
180.0h(~6 LP)

Diskrete Optimierung (ADM II) (TUT):

Aufwandbeschreibung Multiplikator Stunden Gesamt
Präsenzzeit 15.0 2.0h 30.0h
30.0h(~1 LP)

Diskrete Optimierung (ADM II) (UE):

Aufwandbeschreibung Multiplikator Stunden Gesamt
Präsenzzeit 15.0 2.0h 30.0h
30.0h(~1 LP)

Lehrveranstaltungsunabhängiger Aufwand:

Aufwandbeschreibung Multiplikator Stunden Gesamt
Prüfungsvorbereitung 1.0 60.0h 60.0h
60.0h(~2 LP)
Der Aufwand des Moduls summiert sich zu 300.0 Stunden. Damit umfasst das Modul 10 Leistungspunkte.

Beschreibung der Lehr- und Lernformen

Vorlesungen, Übungen, Programmierubungen, Übungen in Kleingruppen

Voraussetzungen für die Teilnahme / Prüfung

Wünschenswerte Voraussetzungen für die Teilnahme an den Lehrveranstaltungen:

Analysis, Lineare Algebra, Kenntnisse in einer hoheren Programmiersprache, Einführung in die lineare und kombinatorische Optimierung (ADM I)

Verpflichtende Voraussetzungen für die Modulprüfungsanmeldung:

Keine Angabe

Abschluss des Moduls

Benotung

benotet

Prüfungsform

Mündliche Prüfung

Sprache

Deutsch

Dauer/Umfang

Keine Angabe

Dauer des Moduls

Für Belegung und Abschluss des Moduls ist folgende Semesteranzahl veranschlagt:
1 Semester.

Dieses Modul kann in folgenden Semestern begonnen werden:
Sommersemester.

Maximale teilnehmende Personen

Dieses Modul ist nicht auf eine Anzahl Studierender begrenzt.

Anmeldeformalitäten

Werden in der Vorlesung angegeben.

Literaturhinweise, Skripte

Skript in Papierform

Verfügbarkeit:  nicht verfügbar

Skript in elektronischer Form

Verfügbarkeit:  nicht verfügbar

Literatur

Empfohlene Literatur
Wird in der Vorlesung bekannt gegeben.

Zugeordnete Studiengänge

Diese Modulversion wird in folgenden Studiengängen verwendet:

Sonstiges

Literatur wird in der Vorlesung angegeben.