Zur Seitennavigation oder mit Tastenkombination für den accesskey-Taste und Taste 1 
Zum Seiteninhalt oder mit Tastenkombination für den accesskey und Taste 2 
Startseite    Anmelden     
Winter 2021/22    Hilfe  Trennstrich  Sitemap  Trennstrich  Impressum  Trennstrich  Datenschutz  Trennstrich  node1  Trennstrich  Switch to english language

Veranstaltung

Effiziente Graphenalgorithmen

  • Funktionen:

Grunddaten

Veranstaltungsart Vorlesung SWS 3.00
Veranstaltungsnummer 23163 Semester WS 2021/22
Sprache Deutsch Studienjahr
Hyperlink Stud.IP Link zu dieser Lehrveranstaltung in Stud.IP

Belegung über StudIP

Status Link
offene Belegung (kein Anmeldeverfahren)    Link

Module

1100760 Vertiefung Informatik 1
1100770 Vertiefung Informatik 2
1100790 Vertiefung Theoretische Informatik
1101160 Effiziente Graphenalgorithmen

Termine Gruppe: [unbenannt] iCalendar Export für Outlook

  Tag Zeit Rhythmus Dauer Raum Raum-
plan
Lehrperson Status Bemerkung fällt aus am Max. Teilnehmer/-innen
Einzeltermine anzeigen
iCalendar Export für Outlook
Mi. 17:00 bis 19:00 ungerWoch 13.10.2021 bis 19.01.2022  A.-Einstein-Str. 22 - HS 037, A.-Einstein-Str. 22 Raumplan Le findet statt    
Einzeltermine anzeigen
iCalendar Export für Outlook
Mi. 09:00 bis 11:00 woch 13.10.2021 bis 26.01.2022  A.-Einstein-Str. 22 - SR 110, A.-Einstein-Str. 22 Raumplan Le findet statt    
Gruppe [unbenannt]:
 

Verantwortliche Person

Verantwortliche Person Zuständigkeit
apl. Prof. Dr. rer. nat. habil. Van Bang Le

Studiengänge

Studiengang/Abschluss/Prüfungsversion Semester Teilnahmeart
Informatik, Bachelor (2016) 4. - 6. Semester wahlobligatorisch
Informationstechnik/Technische Informatik, Bachelor (2012) 5. Semester wahlobligatorisch
Informationstechnik/Technische Informatik, Bachelor (2018) 5. Semester wahlobligatorisch
Mathematik, Bachelor (2020) 4. - 6. Semester wahlobligatorisch
Wirtschaftsinformatik, Bachelor (2013) 4. - 6. Semester wahlobligatorisch
Wirtschaftsinformatik, Bachelor (2018) 4. - 6. Semester wahlobligatorisch
Wirtschaftsinformatik, Bachelor (2021) 5. Semester wahlobligatorisch

Zuordnung zu Einrichtungen

Fakultät für Informatik und Elektrotechnik (IEF)

Inhalt

Kommentar

Kenntnis der wichtigsten Grundlagen effizienter Graphenalgorithmen, die für
das Informatikstudium relevant sind.

Literatur

• T.H. Cormen, C.E. Leiserson, R. Rivest, C. Stein, Algorithmen-Eine
Einführung, Oldenbourg 2004, ISBN 3-486-27515-1.
• A. Brandstädt, Graphen und Algorithmen, Teubner Verlag 1994,
ISBN 3-519-02131-5.
• K. Mehlhorn, Graph Algorithms and NP-Completeness, Springer,
1984, ISBN 3-540-13641-x.
Ergänzende Empfehlungen:
• S. Even, Graph Algorithms, Computer Science Press 1979, ISBN 0-
914894-21-8.
• M. Golumbic, Algorithmic Graph Theory and Perfect Graphs, Annals
of Discrete Mathematics 57, Elsevier 2004, 2nd edition, ISBN 0-444-
51530-5.

Lerninhalte

Das Modul führt in die Grundlagen effizienter Graphenalgorithmen für Informatiker
ein, behandelt grundlegende Probleme undMethoden wie vollständiges
Durchsuchen von Graphen, kürzesteWege in Graphen, minimum spanning
trees, Maximalfluß in Netzwerken, das Matchingproblem, Färbungsprobleme
sowie Baumstrukturen in Graphen und Dekomposition sowie
Weitebegriffe. Außerdem werden einige spezielle Klassen behandelt wie
z.B. chordale Graphen, Intervallgraphen, perfekte Graphen sowie planare
Graphen.
Inhalte
• Graphen und ihre Darstellung
• Tiefensuche (DFS) und Breitensuche (BFS) sowie Varianten
• Mimimalgerüste (minimum spanning tree) und greedy-Algorithmus
• die Algorithmen von Kruskal, Dijkstra und Sollin
• das Steinerbaumproblem und Varianten
• Maximalfluß in Netzwerken und Anwendungen
• Algorithmus von Dinitz; Komplexität
• das maximum matching Problem und Varianten
• Knoten- und Kantenf¨arbungen in Graphen mit Anwendungsbeispielen
• chordale Graphen und Intervallgraphen; perfekte Graphen
• Baumstruktur in Graphen, modulare Dekomposition, treewidth, cliquewidth
• planare Graphen, graph drawing und Anwendungen sowie Komplexitätsfragen



Zugehörige weitere Veranstaltung
Nr. Veranstaltungsart Beschreibung SWS
23163 Übung Effiziente Graphenalgorithmen 1.00

Strukturbaum

Die Veranstaltung wurde 3 mal im Vorlesungsverzeichnis Winter 2021/22 gefunden:
Bachelor Informatik · · · · [+]