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 Wirtschaftsinformatik-Format Pdf_icon Informatik-Format Pdf_icon Digitale Medien-Format Pdf_icon Systems Engineering-Format Pdf_icon

Digitale Medien-Ansicht

Modulnummer
Modulbezeichnung
Algorithmen auf Graphen
Titel (englisch)
Graph Algorithms
Pflicht/Wahl
Pflicht
Erklärung
CP
6
Berechnung des Workloads
Turnus
i. d. R. angeboten in jedem SoSe
Dauer
ein Semester
Form
4 SWS K
Prüfung
i.d.R. Bearbeitung von Übungsaufgaben und Fachgespräch oder mündliche Prüfung
Anforderungen
Theoretische Informatik 1, Theoretische Informatik 2
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
Quellen
  • 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
Sprache
Deutsch
Bemerkung
Zuletzt geändert
2018-05-02 12:57:32 UTC
Zurück

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