Moses - Einführung in die Lineare und Kombinatorische Optimierung (ADM I)

Zur Modulseite PDF generieren

Modul / Version
#20087 / #1

Gültigkeit
Seit SS 2014

Verfügbare Sprache(n)
Deutsch

Titel des Moduls
Einführung in die Lineare und Kombinatorische Optimierung (ADM I)

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 werden algorithmische und strukturelle Grundlagen der Linearen und Kombinatorischen Optimierung vermittelt. Dazu gehören Grundlagen der Graphen- und Polyedertheorie und das Erlernen algorithmischer Denk- und Arbeitsweisen wie Komplexität von Problemklassen, Effizienz von Algorithmen und Approximation am Beispiel von Optimierungsaufgaben in Netzwerken. Fachkompetenz: 55% Methodenkompetenz: 30% Systemkompetenz: 10% Sozialkompetenz: 5%

Lehrinhalte

Graphen und Digraphen: bipartite Graphen, Netzwerke, Zusammenhang, Bäume, Graphensuche. Lineare Programme: Struktur, Modellierung, Transformation auf Standardform, Basen primale und duale Zulässigkeit, ökonomische Interpretation (Schattenpreise) Simplex-Verfahren: Grundversion/Tableaux und geometrische Interpretation Dualitätstheorie, komplementärer Schlupf Polynomiale Algorithmen für Basisprobleme in Netzwerken: aufspannende Bäume, kürzeste Wege, maximale Flüsse, Minimalkostenflüsse Komplexitätstheorie: Die Klassen P und NP, NP-Vollständigkeit. NP-schwere Probleme: Cliquen-, Travelling Salesman-, Maximalschnitt- und Färbungsprobleme.

Modulbestandteile

Pflichtbereich

Die folgenden Veranstaltungen sind für das Modul obligatorisch:

Lehrveranstaltungen	Art	Nummer	Turnus	Sprache	SWS
Einführung in die Lineare und Kombinatorische Optimierung (ADM I)	VL	3236 L 148	WiSe	de	4
Einführung in die Lineare und Kombinatorische Optimierung (ADM I)	TUT		WiSe	de	2
Einführung in die Lineare und Kombinatorische Optimierung (ADM I)	UE		WiSe	de	2

ISIS-Kurssuche nach Veranstaltungen des Moduls

Arbeitsaufwand und Leistungspunkte

Einführung in die Lineare und Kombinatorische Optimierung (ADM I) (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)

Einführung in die Lineare und Kombinatorische Optimierung (ADM I) (TUT):

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

Einführung in die Lineare und Kombinatorische Optimierung (ADM I) (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, Programmierübungen, Übungen in Kleingrupen

Voraussetzungen für die Teilnahme / Prüfung

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

Analysis, Lineare Algebra, Kenntnisse in einer höheren Programmiersprache

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:
Wintersemester.

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
Mathematik (B. Sc.)	1	36	WS 2014/15	SoSe 2025
Mathematik (M. Sc.)	1	21	WS 2014/15	SoSe 2025
Naturwissenschaften in der Informationsgesellschaft (B. Sc.)	3	45	WS 2015/16	SoSe 2025
Scientific Computing (M. Sc.)	2	26	WS 2014/15	SoSe 2025
Technomathematik (B. Sc.)	1	21	WS 2014/15	SoSe 2025
Technomathematik (M. Sc.)	1	22	WS 2014/15	SoSe 2025
Wirtschaftsmathematik (B. Sc.)	1	22	WS 2014/15	SoSe 2025
Wirtschaftsmathematik (M. Sc.)	2	24	WS 2014/15	SoSe 2025

Sonstiges

Keine Angabe