Kombinatorische Optimierung 1
WS 2010-2011, 3 VO/1 UE
(502.636 / 502.637)
E. Dragoti-Cela
Institut für Optimierung und Diskrete Mathematik
Diese Lehrveranstaltung befasst sich mit grundlegenden kombinatorischen
Optimierungsproblemen. In der Regel sind das polynomial lösbare Optimierungsprobleme
für die sowohl strukturelle Eigenschaften als auch Lösungsansätze besprochen werden.
Das Ziel ist, einerseits die Studierenden mit prominenten, sowohl theoretisch als auch
praktisch relevanten Problemen der Kombinatorischen Optimierung vertraut zu
machen, und anderseits eine Handvoll an Lösungsansätzen und
algorithmischen Paradigmen als praktisch relevantes Wissen zu
vermitteln.
Die Kapitelüberschriften und Stichwörter sind:
Die Hauptliteraturquelle ist
B. Korte und J. Vygen, Kombinatorische Optimierung: Theorie und Algorithmen, Springer, 2008.
Weitere Titel sind:
Die Vorlesung wird anhand einer mündlichen Prüfung benotet. Die Prüfungstermine werden je nach Bedarf mit der Vortragenden vereinbart.
Die einstündige Übung hat einen immanenten Charakter und wird anhand von zwei Klausuren und der Mitarbeit der Studierenden in den Übungsstunden mit Hilfe
eines Punktesystems benotet.
Klausurtermine:
Aufgrund des immanenten Charakters der Lehrveranstaltung gibt es genau eine Nachklausur
(Ende Februar/Anfang März 2011). Beim Antreten zur Nachklausur ist zu entscheiden,
ob die erste oder die zweite Klausur wiederholt werden soll. Durch den Antritt werden die Punkte aus der wiederholten Klausur gelöscht.
Die Klausuren werden (rechtzeitig) im Prüfungssystem des TUGonline erfasst;
die Anmeldung zu den Klausuren erfolgt via TUGonline.
Bei den Übungsklausuren sind alle schriftliche Unterlagen sowie Taschenrechner erlaubt. Dennoch sind alle Zwischenschritte anzugeben. Die Verwendung von Notebooks, PDAs, Handhelds etc. ist nicht gestattet.
Mitarbeit im Rahmen der Übungseinheiten:
Vor jeder Übung müssen Sie online ankreuzen (Ankreuzschluss ist 30 Minuten vor
Beginn der Übung), welche Beispiele Sie gelöst haben und vorführen können.
Anhand dieser Kreuze werden per Zufallsgenerator Studierende ausgewählt, um das jeweilige
Beispiel an der Tafel vorzuführen.
Für ein Tafelbeispiel gibt es höchstens
einen Punkt.
Bei der Vorführung von Beispielen wird neben der mathematischen Korrektheit auch auf die
Qualität der Präsentation Wert gelegt. Falls die Präsentation darauf
schließen lässt, dass das Beispiel zu Unrecht angekreuzt wurde
(insbesondere bei Abwesenheit), werden sämtliche Beispiele der letzten 2n
Übungseinheiten gestrichen, wobei n für die Anzahl der bereits
erfolgten Streichungen steht.
Studierende, die ausnahmsweise nicht an der Übung teilnehmen können, dürfen
höchstens ein Mal im Semester die vorzubereitenden Beispiele abgeben. In diesem Fall
müssen die Kreuze im Onlinesystem als "Ersatzkreuze" angekreuzt werden.
Die Beispiele müssen vor Beginn der Übung abgegeben werden und müssen
selbstständig erarbeitet worden sein. Die Übungsleiterin kann Studierende
jederzeit zur Präsentation der abgegebenen Beispiele außerhalb der
Übungseinheit auffordern!
In besonders berücksichtigungswürdigen Fällen kann bei entsprechendem
Nachweis und vorheriger Vereinbarung eine höhere Anzahl von Abgaben erfolgen.
Achtung: Die Übungen werden
Der nächste Übungstermin wird von der Vortragenden
begleitend zum aktuellen Übungsblatt rechtzeitig bekanntgegeben.
Benotung:
Die Gesamtpunktezahl ergibt sich durch
| k -- | Anzahl der angekreuzten Beispiele, |
| e -- | Ersatzkreuze durch Abgabe von Beispielen, |
| k_Sigma -- | Anzahl der ankreuzbaren Beispiele, |
| t -- | Summe Punkte auf Tafelleistungen, |
| t_anzahl -- | Anzahl der vorgerechneten Beispiele an der Tafel, |
| p_1 -- | Punkte Punkte der ersten Klausur (zwischen 0 und 10), |
| p_2 -- | Punkte Punkte der zweiten Klausur (zwischen 0 und 10), |
Notenschlüssel für die Bewertung der Übung:
| 0.00 <= P < 0.50 | Nicht genügend |
| 0.50 <= P < 0.65 | Genügend |
| 0.65 <= P < 0.80 | Befriedigend |
| 0.80 <= P < 0.90 | Gut |
| 0.90 <= P | Sehr Gut. |
Zusätzliche Voraussetzung: Um ein positives Übungszeugnis zu erhalten, müssen auf beide Klausuren zusammen mindestens 8 Punkte erzielt werden.
Bei der ersten Anmeldung bitte Matrikelnummer und ein leeres Passwort eingeben, daraufhin wird ein Passwort per Email zugestellt. Beachten Sie, dass eine Anmeldung erst nach der Anmeldung zur LV im TUGonline möglich ist und dass zwischen der Anmeldung im TUGonline und der Einspielung der Daten in das Ankreuzsystem einige Zeit vergehen kann.
Die Aufbereitung des Stoffes wird in vielen Abschnitten mit dem Skriptum nach der Vorlesung von Dr. Johannes Hatzl im WS 2009/2010 übereinstimmen.
cela@opt.math.tu-graz.ac.at.
Letzte Änderung: März 2011