1. Modulverzeichnis (MTS)
  2. Module
  3. Modulbeschreibung anzeigen

Approximationsalgorithmen (ADM III)

Zur Modulseite PDF generieren

#20091 / #1

Seit SS 2014

Deutsch

Approximationsalgorithmen (ADM III)

10

Skutella, Martin

Benotet

Mündliche Prüfung

Deutsch

Zugehörigkeit


Fakultät II

Institut für Mathematik

Keine Angabe

Mathe

Kontakt


MA 5-2

Keine Angabe

skutella@math.tu-berlin.de

Keine Angabe

Lernergebnisse

In der Veranstaltung sollen algorithmische und strukturelle Grundlagen der approximativen Lösung kombinatorischer Optimierungsprobleme vermittelt werden. Einen Schwerpunkt bilden Algorithmen und algorithmische Techniken, die (oder deren Analyse) auf linearer Optimierung beruhen. Dazu gehören insbesondere das Primal-Duale Schema und LP-Runden. Fachkompetenz: 55% Methodenkompetenz: 30% Systemkompetenz: 10% Sozialkompetenz: 5%

Lehrinhalte

Approximierbarkeit und Nichtapproximierbarkeit Polynomiale Approximationsschemata LP-Runden: randomisiert, deterministisch, iteriert Dual Fitting am Beispiel von Set Cover Primal-duales Schema und Local Ratio Methode Anwendungen bei Netzwerkdesign-Problemen Schranken aus semideniten Relaxationen am Beispiel von MAX CUT PCP Theorem (ohne Beweis), luckenerzeugende Reduktionen Klasse MAX-SNP, lüuckenbewahrende Reduktionen

Modulbestandteile

Pflichtbereich

Die folgenden Veranstaltungen sind für das Modul obligatorisch:

LehrveranstaltungenArtNummerTurnusSpracheSWS ISIS VVZ
ADM IIIVL3236 L 233WiSe/SoSede4
ISIS-Kurssuche nach Veranstaltungen des Moduls

Arbeitsaufwand und Leistungspunkte

ADM III (VL):

AufwandbeschreibungMultiplikatorStundenGesamt
Präsenzzeit15.04.0h60.0h
Vor- und Nachbereitung15.012.0h180.0h
240.0h(~8 LP)

Lehrveranstaltungsunabhängiger Aufwand:

AufwandbeschreibungMultiplikatorStundenGesamt
Prüfungsvorbereitung1.060.0h60.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

Voraussetzungen für die Teilnahme / Prüfung

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

Graphen- und Netzwerkalgorithmen (ADM I), Lineare Optimierung (ADM II)

Verpflichtende Voraussetzungen für die Modulprüfungsanmeldung:

Dieses Modul hat keine Prüfungsvoraussetzungen.

Abschluss des Moduls

Benotung

Benotet

Prüfungsform

Mündliche Prüfung

Sprache(n)

Deutsch

Dauer/Umfang

ca. 30 min.

Dauer des Moduls

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

Dieses Modul kann in folgenden Semestern begonnen werden:
Winter- und Sommersemester.

Maximale teilnehmende Personen

Dieses Modul ist nicht auf eine Anzahl Studierender begrenzt.

Anmeldeformalitäten

Standard.

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:

Studiengang / StuPOStuPOsVerwendungenErste VerwendungLetzte Verwendung
Computer Engineering (M. Sc.)119SS 2017SoSe 2026
Computer Science (Informatik) (M. Sc.)133SS 2017SoSe 2026
Elektrotechnik (M. Sc.)119SS 2017SoSe 2026
Mathematik (B. Sc.)124WS 2014/15SoSe 2026
Mathematik (M. Sc.)124WS 2014/15SoSe 2026
Naturwissenschaften in der Informationsgesellschaft (B. Sc.)254WS 2015/16SoSe 2026
Technomathematik (B. Sc.)123WS 2014/15SoSe 2026
Technomathematik (M. Sc.)124WS 2014/15SoSe 2026
Wirtschaftsmathematik (B. Sc.)125WS 2014/15SoSe 2026
Wirtschaftsmathematik (M. Sc.)126WS 2014/15SoSe 2026

Sonstiges

Keine Angabe