F07_GRT < F07_Studium

<!--
   * Set USERSTYLEURL = %PUBURLPATH%/%WEB%/DokumentFormat/fonts.css
-->
---+!! %FORMFIELD{"TopicClassification"}% %FORMFIELD{"Bezeichnung"}%

*Verantwortlich:* Prof. Dr. Randerath


%TOC{depth="3"}%
%STARTSECTION{"no_toc"}%
---
---++ Lehrveranstaltung
---+++ Befriedigt MID
   * aktuelle
      * [[BaTIN2012_GRT]]
   * auslaufende
      * [[]]

---+++ 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>2012-04-23</td>
          </tr>
          <tr>
            <td>VID</td>
            <td>1</td>
          </tr>
          <tr>
            <td>gültig ab</td>
            <td>SS 2013</td>
          </tr>
          <tr>
            <td>gültig bis</td>
            <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>LVID</td>
            <td>F07_GRT</td>
          </tr>
          <tr>
            <td>LVPID (Prüfungsnummer)</td>
            <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
   * Mathematisches Grundlagenwissen
   * Grundlagenwissen der Praktischen Informatik
   * Grundlagenwissen über Algorithmen und Datenstrukturen

---++++ Literatur
   * Diskrete Mathematik, M. Aigner, Vieweg-Verlag
   * Graphentheorie, R. Diestel, Springer Verlag
   * Graphentheorie, P. Tittman, Fachbuchverlag Leipzig
   * Graphen an allen Eckern und Kanten, L. Volkmann,  RWTH Aachen

---++++ Dozenten



---++++ Wissenschaftliche Mitarbeiter
   * Dipl.-Math. Katharina Hammersen

---++++ Zeugnistext
Graphentheorie

---+++ Kompetenznachweis
<sticky>
  <table border="1" cellpadding="2" cellspacing="0">
    <th colspan="2">Form</th>
    <tr>
      <td>sMP</td>
      <td>Regelfall (bei großer Prüfungszahl: sK)</td>
    </tr>
  </table>
</sticky>

<sticky>
  <table border="1" cellpadding="2" cellspacing="0">
    <th colspan="2">Aufwand [h]</th>
    <tr>
      <td>sMP</td>
      <td>10</td>
    </tr>
  </table>
</sticky>

*Intervall:* 3/Jahr

-----
---++ Lehrveranstaltungselemente

%STARTSECTION{"Vorlesung / Übung"}%
---+++ Vorlesung / Übung

---++++ Lernziele 
---+++++ Lerninhalte (Kenntnisse)
   * Grundlagen der Kombinatorik und Asymptotische Analyse: KombinatorischeGrundprinzipien, Elementare Zählprinzpien, Permutationen, Variationen undKombinationen, Prinzip der Inklusion und Exklusion, Wachstum von Funktionen,Laufzeit von Algorithmen, Komplexitätsklassen.
   * Grundlagen der Graphentheorie: Definition Graph, vollständige und bipartite Graphen,Isomorphie von Graphen, Adjazenz- und Inzidenzmatrix, Wege und Kreise, Zusammenhangvon Graphen, gerichtete Graphen; Wälder, Bäume, Elementare Graphenparameter. 
   * Traversierung in Graphen und das kürzeste Wege Problem:Breitensuche, Tiefensuche, Topologische Sortierung, Eulertouren,Hamiltonkreise, Dijkstra-Algorithmus, Bellman-Ford-Algorithmus.
   * Matchings und Flüsse: Matchings, Ungarische Methode, Edmonds-Algorithmus, Netzwerke, Flüsse, zuässige Flüsse, Max-Flow-Min-Cut, Ford-Fulkersen-Algorithmus, Edmonds-Karp-Algorithmus..
   * Färbungen:  Knotenfärbungen, Kantenfärbungen, Listenfärbungen,Turniere und Spielpläne, Planare Graphen, Vier-Farben-Satz, PerfekteGraphen, Färbungsalgorithmen. 

---+++++ Fertigkeiten
   * Die Studierenden beherrschen grundlegende Kenntnisse über Graphen und Algorithmen
   * Sie sind in der Lage Verfahren und Konzepte der Graphentheoriezur Beschreibung und algorithmischen Lösung von Problemstellungender Informatik, der Technik und des täglichen Lebens anzuwenden. 


---++++ Begleitmaterial 
   * elektronische Vortragsfolien zur Vorlesung
   * elektronische Übungsaufgabensammlung


---++++ Besondere Voraussetzungen 


---++++ Besondere Literatur 


---++++ 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"}%



%STARTSECTION{"Praktikum"}%
---+++ Praktikum

---++++ Lernziele 
---+++++ Lerninhalte (Kenntnisse)
   * Grundlagen: Graphentheorie mit Maple
   * Ausgewählte Graphenalgorithmen mit Maple

---+++++ Fertigkeiten
   * Die Studierende sind in der Lage einfachegraphentheoretische Probleme mit Maple zu lösen


---++++ Begleitmaterial 
   * elektronisches Entwicklungswerkzeug: MAPLE
   * elektronisches Tutorial: praktikumsspezifische Einführung in Maple


---++++ Besondere Voraussetzungen 


---++++ Besondere Literatur 
   * Exploring Discrete Mathematics with Maple, Kenneth Rosen (McGraw-Hill Verlag)


---++++ Besonderer Kompetenznachweis 
<sticky>
  <table border="1" cellpadding="2" cellspacing="0">
    <th colspan="2">Form</th>
    <tr>
      <td>bSZ</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>bSZ</td>
      <td>unbenotet; Voraussetzung für die mündliche Prüfung</td>
    </tr>
  </table>
</sticky>

*Intervall:* 1/Jahr

%ENDSECTION{"Praktikum"}%




%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