Moses - Approximationsalgorithmen (ADM III)

Zur Modulseite PDF generieren

Modul / Version
#20091 / #1

Gültigkeit
Seit SS 2014

Verfügbare Sprache(n)
Deutsch

Titel des Moduls
Approximationsalgorithmen (ADM III)

Leistungspunkte
10

Modulverantwortliche*r
Skutella, Martin

Benotung
Benotet

Prüfungsform
Mündliche Prüfung

Lehrsprache(n)
Deutsch

Zugehörigkeit

Fakultät
Fakultät II

Institut
Institut für Mathematik

Fachgebiet
Keine Angabe

Prüfungsausschuss
Mathe

Kontakt

Sekretariat
MA 5-2

Ansprechpartner*in
Keine Angabe

E-Mail-Adresse
skutella@math.tu-berlin.de

Webseite
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:

Lehrveranstaltungen	Art	Nummer	Turnus	Sprache	SWS	ISIS	VVZ
ADM III	VL	3236 L 233	WiSe/SoSe	de	4

ISIS-Kurssuche nach Veranstaltungen des Moduls

Arbeitsaufwand und Leistungspunkte

ADM III (VL):

Aufwandbeschreibung	Multiplikator	Stunden	Gesamt
Präsenzzeit	15.0	4.0h	60.0h
Vor- und Nachbereitung	15.0	12.0h	180.0h
			240.0h(~8 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

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

Semester:

Zeige auch ausgelaufene Studiengänge und StuPOs

Diese Modulversion wird in folgenden Studiengängen verwendet:

Studiengang / StuPO	StuPOs	Verwendungen	Erste Verwendung	Letzte Verwendung
Computer Engineering (M. Sc.)	1	17	SS 2017	SoSe 2025
Computer Science (Informatik) (M. Sc.)	1	29	SS 2017	SoSe 2025
Elektrotechnik (M. Sc.)	1	17	SS 2017	SoSe 2025
Mathematik (B. Sc.)	1	22	WS 2014/15	SoSe 2025
Mathematik (M. Sc.)	2	22	WS 2014/15	SoSe 2025
Naturwissenschaften in der Informationsgesellschaft (B. Sc.)	4	49	WS 2015/16	WiSe 2025/26
Technomathematik (B. Sc.)	1	21	WS 2014/15	SoSe 2025
Technomathematik (M. Sc.)	1	22	WS 2014/15	SoSe 2025
Wirtschaftsmathematik (B. Sc.)	2	23	WS 2014/15	SoSe 2025
Wirtschaftsmathematik (M. Sc.)	2	24	WS 2014/15	SoSe 2025

Sonstiges

Keine Angabe