====== Graphen und Algorithmen ======

^ Info                                                                                                        ||
| Modultafel            | https://www.tu-ilmenau.de/modultafeln/Informatik/Master/2021/fach/20712/             |
| Website               | https://moodle.tu-ilmenau.de/course/view.php?id=49                                   |
| Regelstudiensemester  | {{tagpage>semester:ma01}} |

===== Vorlesung =====

Die Vorlesung beschäftigt sich mit diversen Problemen aus der Graphentheorie und Algorithmen zur Lösung dieser, u.A.:

  * Bäume
    * Suchbäume
    * Bäume kleinsten Gewichtes
    * Das Traveling-Salesman-Problem
  * Matchings
    * Matchingins in bipartiten Graphen
    * Faktorsätze
  * Flüsse
  * Färbungen
    * Greedy-Färbungen
    * Komplexität von Färbungsproblemen

Teilweise überschneiden sich die Inhalte der Vorlesungen mit denen aus [[..:effiziente-algorithmen:]].
Damit können die Inhalte der jeweils anderen Vorlesung gut als Ergänzung bzw. genauere/andere Erklärung zum besseren Verständnis genutzt werden.

===== Übung =====

Die meisten Übungsaufgaben beginnen mit den Worten „Man zeige“.
Zu den Übungsterminen wird erwartet, dass die Aufgaben bereits zuhause vorbereitet und gelöst wurden
und dass Lösungen nur noch vorgestellt werden.
Zudem gibt es die Möglichkeiten, Fragen und Verständnisprobleme zu klären.

===== Material =====

  * [[.:ws2324:start]]

===== Prüfung =====

Die Prüfung ist mündlich.
Vor dem Prüfungstermin werden ein paar Prüfungsaufgaben herausgegeben,
die zuhause selbstständig zu lösen sind.
Diese müssen zur Prüfung vollständig gelöst mitgebracht und abgegeben werden.
Mindestens eine dieser Aufgaben wird dann während der Prüfung vorgestellt und Fragen dazu werden beantwortet.

===== Zusatzmaterial =====

  * [[https://page.mi.fu-berlin.de/block/htw-lehre/wise2015_2016/bel_und_rend/skripte/GraphentheorieII.pdf|Reinhard Diestel, Graphentheorie]]
  * [[https://num.math.uni-goettingen.de/werner/angmat03-graph.pdf|Skript Angewandte Mathematik, Universität Göttingen, Kapitel 3, Graphentheorie]]
  * [[https://page.math.tu-berlin.de/~felsner/Lehre/GrTh05/Graphentheorie.pdf|Graphentheorie, TU Berlin]]


{{tag>semester:ma01}}