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

Informatik-Ansicht

Algorithmen auf Graphen


Graph Algorithms 		Modulnummer
BB-602.01
Bachelor
Pflicht/Wahl
Wahl Basis Ergänzung
Sonderfall
Zugeordnet zu Masterprofil
Sicherheit und Qualität
KI, Kognition, Robotik
Digitale Medien und Interaktion
Modulbereich : Mathematik und Theoretische Informatik
Modulteilbereich : 602 Algorithmen- und Komplexitätstheorie
Anzahl der SWS
V UE K S Prak. Proj. ∑
0 0 4 0 0 0 4
Kreditpunkte : 6 Turnus

i. d. R. angeboten in jedem SoSe

Formale Voraussetzungen : -
Inhaltliche Voraussetzungen : Theoretische Informatik 1, Theoretische Informatik 2
Vorgesehenes Semester : ab 4. Semester
Sprache : Deutsch
Ziele :
  • 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.
Inhalte :
  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
Unterlagen (Skripte, Literatur, Programme 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
Form der Prüfung : i.d.R. Bearbeitung von Übungsaufgaben und Fachgespräch oder mündliche Prüfung
Arbeitsaufwand
Präsenz 56
Übungsbetrieb/Prüfungsvorbereitung 124
Summe 180 h
Lehrende: Dr. S. Kuske Verantwortlich Dr. S. Kuske
Zurück

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