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

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