<!-- * Set USERSTYLEURL = %PUBURLPATH%/%WEB%/DokumentFormat/fonts.css --> ---+!! %FORMFIELD{"TopicClassification"}% %FORMFIELD{"Bezeichnung"}% %TOC{depth="3"}% %STARTSECTION{"no_toc"}% --- *Verantwortlich:* Prof. Dr. Hubert Randerath ---++ Lehrveranstaltung ---+++ Befriedigt Modul (MID) * aktuelle * [[MaTIN2012_KOGA]] ---+++ Organisation <sticky> <table border="0"> <tr valign="top"> <td> <table border="1" cellpadding="2" cellspacing="0"> <th colspan="2">Version</th> <tr> <td>erstellt</td> <td>2013-04-29</td> </tr> <tr> <td>VID</td> <td>2</td> </tr> <tr> <td>gültig ab</td> <td>WS 2013/14</td> </tr> <tr> <td>gültig bis</td> <td/> </tr> </table> </td> <td> </td> <td> <table border="1" cellpadding="2" cellspacing="0"> <th colspan="2">Bezeichnung</th> <tr> <td>Lang</td> <td>%FORMFIELD{"Bezeichnung"}%</td> </tr> <tr> <td>Englisch</td> <td>Combinatorial Optimization and Graph Algorithms</td> </tr> <tr> <td>LVID</td> <td>F07_KOGA</td> </tr> <tr> <td>LVPID (Prüfungsnummer)</td> <td/> </tr> </table> </td> </tr> </table> </sticky><sticky> <table border="0"> <tr valign="top"> <td> <table border="1" cellpadding="2" cellspacing="0"> <th colspan="2">Semesterplan (SWS)</th> <tr> <td>Vorlesung</td> <td>%FORMFIELD{"VorlesungSWS"}%</td> </tr> <tr> <td>Übung (ganzer Kurs)</td> <td>%FORMFIELD{"UebungGanzSWS"}%</td> </tr> <tr> <td>Übung (geteilter Kurs)</td> <td>%FORMFIELD{"UebungHalbSWS"}%</td> </tr> <tr> <td>Praktikum</td> <td>%FORMFIELD{"PraktikumSWS"}%</td> </tr> <tr> <td>Projekt</td> <td>%FORMFIELD{"ProjektSWS"}%</td> </tr> <tr> <td>Seminar</td> <td>%FORMFIELD{"SeminarSWS"}%</td> </tr> <tr> <td>Tutorium (freiwillig)</td> <td>%FORMFIELD{"TutoriumSWS"}%</td> </tr> </table> </td> <td> </td> <td> <table border="1" cellpadding="2" cellspacing="0"> <th colspan="2">Präsenzzeiten</th> <tr> <td>Vorlesung</td> <td>%FORMFIELD{"VorlesungPZ"}%</td> </tr> <tr> <td>Übung (ganzer Kurs)</td> <td>%FORMFIELD{"UebungGanzPZ"}%</td> </tr> <tr> <td>Übung (geteilter Kurs)</td> <td>%FORMFIELD{"UebungHalbPZ"}%</td> </tr> <tr> <td>Praktikum</td> <td>%FORMFIELD{"PraktikumPZ"}%</td> </tr> <tr> <td>Projekt</td> <td>%FORMFIELD{"ProjektPZ"}%</td> </tr> <tr> <td>Seminar</td> <td>%FORMFIELD{"SeminarPZ"}%</td> </tr> <tr> <td>Tutorium (freiwillig)</td> <td>%FORMFIELD{"TutoriumPZ"}%</td> </tr> </table> </td> <td> </td> <td> <table border="1" cellpadding="2" cellspacing="0"> <th colspan="2">max. Teilnehmerzahl</th> <tr> <td>Übung (ganzer Kurs)</td> <td>%FORMFIELD{"UebungGanzTeilnehmer"}%</td> </tr> <tr> <td>Übung (geteilter Kurs)</td> <td>%FORMFIELD{"UebungHalbTeilnehmer"}%</td> </tr> <tr> <td>Praktikum</td> <td>%FORMFIELD{"PraktikumTeilnehmer"}%</td> </tr> <tr> <td>Projekt</td> <td>%FORMFIELD{"ProjektTeilnehmer"}%</td> </tr> <tr> <td>Seminar</td> <td>%FORMFIELD{"SeminarTeilnehmer"}%</td> </tr> </table> </td> </tr> </table> </sticky> *Gesamtaufwand:* %FORMFIELD{"Gesamtaufwand"}% ---++++ Unterrichtssprache * Deutsch ---++++ Niveau * %FORMFIELD{"Niveau"}% ---++++ Notwendige Voraussetzungen * Grundlagenwissen Graphentheorie * Grundlagenwissen Algorithmik ---++++ Literatur * Lineare und Netzwerk-Optimierung, H.W. Hamacher, Vieweg-Verlag * CATBOX - An Interactive Course in Combinatorial Optimization, W. Hochstättler, A. Schliep, Springer-Verlag * Graphentheoretische Konzepte und Algorithmen, S. O. Krumke, H. Noltemeier, Teubner-Verlag * Combinatorial Optimization - Polyhedra and Efficiency, A. Schrijver, Springer-Verlag ---++++ Dozenten * Prof. Dr. Hubert Randerath ---++++ Wissenschaftliche Mitarbeiter * tba ---++++ Zeugnistext Kombinatorische Optimierung und Graphenalgorithmen ---+++ Kompetenznachweis <sticky> <table border="1" cellpadding="2" cellspacing="0"> <th colspan="2">Form</th> <tr> <td>sK</td> <td>Regelfall (bei geringer Prüfungsanzahl: sMP)</td> </tr> </table> </sticky> <sticky> <table border="1" cellpadding="2" cellspacing="0"> <th colspan="2">Aufwand [h]</th> <tr> <td>sK</td> <td>10</td> </tr> </table> </sticky> *Intervall:* 3/Jahr ----- ---++ Lehrveranstaltungselemente %STARTSECTION{"Vorlesung / Übung"}% ---+++ <u>Vorlesung / Übung</u> ---++++ Lernziele ---+++++ Lerninhalte(Kenntnisse) * KOGA-Grundlagen: Grundbegriffe der Graphentheorie und der Kombinatorischen Optimierung * Minimale aufspannende Bäume: Algorithmen von Kruskal, Prim und Tarjan, Greedy-Algorithmen, Matroide, Steinerbäume, Netzwerk-Design * Lineare Programme: Struktur, Modellierung, Transformation in die Standardform, Simplex-Verfahren, Dualitätstheorie * Gewichtete Matchings und das Chinesische Briefträger Problem: Gewichtete Matchings in bipartiten Graphen, Gewichtete Matchings in nicht-bipartiten Graphen, Algorithmus von Floyd-Warshall, Algorithmus von Fleury, Effizienter Algorithmus für das Chinesische Briefträger Problem * Flüsse in Netzwerken: Grundlagen der Netzwerktheorie, Algorithmus von Dinic, Kostenminimale Flüsse * Spezielle Diskrete und Kombinatorische Optimierungsprobleme: Travelling Salesman Problem, das Frequenzzuweisungsproblem, Scheduling-Probleme, Routing-Probleme ---+++++ Fertigkeiten * Die Studierenden sind in der Lage Verfahren und Konzepte der Graphentheorie und der Kombinatorischen Optimierung zur Beschreibung und algorithmischen Lösung von Problemstellungen der Informatik, der Technik und des täglichen Lebens anzuwenden. * Sie haben die Fertigkeit Verfahren und Konzepte der Graphentheorie und der Kombinatorischen Optimierung zur Beschreibung und algorithmischen Lösung von Problemstellungen der Informatik, der Technik und des täglichen Lebens anzupassen. * Sie können algorithmische Denk- und Arbeitweisen wie Komplexität von Problemklassen, Effizienz von Algorithmen und Approximation, die sie induktiv an Optimierungsaufgaben in Netzwerken und gewichteten Graphen erlernt haben, anwenden. ---++++ Begleitmaterial * elektronische Vortragsfolien zur Vorlesung * elektronische Übungsaufgabensammlung ---++++ Besondere Voraussetzungen * keine ---++++ Besondere Literatur * keine ---++++ Besonderer Kompetenznachweis <sticky> <table border="1" cellpadding="2" cellspacing="0"> <th colspan="2">Form</th> <tr> <td>bÜA</td> <td>Präsenzübung</td> </tr> </table> </sticky> <sticky> <table border="1" cellpadding="2" cellspacing="0"> <th colspan="2">Beitrag zum LV-Ergebnis</th> <tr> <td>bÜA</td> <td>unbenotet</td> </tr> </table> </sticky> *Intervall:* 1/Jahr %ENDSECTION{"Vorlesung / Übung"}% %ENDSECTION{"no_toc"}%
Das Urheberrecht © liegt bei den mitwirkenden Autoren. Alle Inhalte dieser Kollaborations-Plattform sind Eigentum der Autoren.
Ideen, Anfragen oder Probleme bezüglich Foswiki?
Feedback senden