Die Informatik des Fachbereiches 3 der Universität Bremen Hier geht es zur Homepage der Verwaltung des Fachbereiches 3 der Universität Bremen Hier geht es zur Homepage der Informatik des Fachbereiches 3 der Universität Bremen Hier geht es zur Homepage der Mathematik des Fachbereiches 3 der Universität Bremen Hier geht es zur Homepage des Fachbereiches 3 der Universität Bremen Hier geht es zur Homepage der Universität Bremen


 




Zeige Digitale Medien-Format Pdf_icon Systems Engineering-Format Pdf_icon Wirtschaftsinformatik-Format Pdf_icon Informatik-Format Pdf_icon

System Engineering-Ansicht

Modultyp
Pflichtmodul Wahlbereich
Spezialisierungsbereich Anzahl Semesterwochenstunden CP Angeboten in jedem
V Ü S P Proj. ∑ Anzahl
Algorithmen auf Graphen
0 0 0 0 0 0 6 i. d. R. angeboten in jedem SoSe
Graph Algorithms         Berechnung des Workloads
Vorgesehenes Semester ab 1. Semester
Lernziele

  • Die Grundprinzipien der Analyse von Algorithmen verstehen und anwenden können.
  • Die Korrektheit und den Zeit- und Platzbedarf von Graphalgorithmen verstehen und erläutern können sowie die zugrunde liegenden Gesetzmäßigkeiten erkennen können.
  • Formale Konstruktionen auf Graphen und der Beweise von in diesem Zusammenhang interessierenden Eigenschaften nachvollziehen und durchführen können.

Lerninhalte

  1. Analyse konkreter Algorithmen auf Graphen (z.B. Eulersch-Test, kürzeste Wege, minimale aufspannende Bäume, maximale Flüsse u.ä.)
  2. Graphprobleme in der Klasse NP
  3. Reduktionsbegriff mit diversen Beispielen für Graphprobleme
  4. NP-Vollständigkeit des Erfüllbarkeitsproblems der Aussagenlogik und Bezug zu Graphalgorithmen
  5. Auswege aus der NP-Problematik
Prüfungsformen

i.d.R. Bearbeitung von Übungsaufgaben und Fachgespräch oder mündliche Prüfung
Dokumente (Skripte, Programme, Literatur, usw.)

  • Sabine Kuske: Algorithmen auf Graphen, Skript
  • Sven Oliver Krumke and Hartmut Noltemeier. Graphentheoretische Konzepte und Algorithmen. Leitfäden der Informatik. Vieweg+Teubner, 2012
  • Dieter Jungnickel: Graphs, Networks and Algorithms. Springer, 2008
  • Shimon Even, Graph Algorithms. Cambridge Univ. Press, 2011
  • Michael R. Garey, David S. Johnson: Computers and Intractability. Freeman & Company, 1979
  • Reinhard Diestel: Graphentheorie. Springer, 2010
Lehrende: Dr. S. Kuske Verantwortlich: Dr. S. Kuske
Zurück

Zeige Digitale Medien-Format Pdf_icon Systems Engineering-Format Pdf_icon Wirtschaftsinformatik-Format Pdf_icon Informatik-Format Pdf_icon