F07_KOGA < F07_Studium

Sie sind hier: Foswiki>F07_Studium Web>F07_KOGA (Revision 5) (Quelltext-Ansicht)
<!--
   * 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"}%
Topic-Revision: r5 - 06 Dec 2017, GeneratedContent
F07_Studium
Einloggen oder Registrieren
Webs
F07_Studium
System
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