Stud.IP Uni Oldenburg
University of Oldenburg
07.02.2023 08:30:49
inf405 - Algorithmic Graph Theory (Complete module description)
 Module label Algorithmic Graph Theory Modulkürzel inf405 Credit points 6.0 KP Workload 180 h Institute directory Department of Computing Science Verwendbarkeit des Moduls Dual-Subject Bachelor's Programme Computing Science (Bachelor) > Wahlpflicht Theoretische Informatik (30 KP) Master of Education Programme (Gymnasium) Computing Science (Master of Education) > Wahlpflichtmodule (Theoretische Informatik) Zuständige Personen Lehrenden, Die im Modul (Prüfungsberechtigt) Lehrenden, Die im Modul (Module responsibility) Prerequisites Skills to be acquired in this module Graphs are the most frequently used abstraction in computer science. Every system which consists of discrete states or objects and relations between these can be modelled as a graph. Most applications require efficient algorithms to process such graphs (Turau, 1996). This module provides typical graph theory problems and algorithmic solutions. They are discussed with regard to their efficiency and applicability and many of the algorithms will be implemented. An important aspect of this module is to consider different approaches to problems and learn different solution strategies.Professional competenceThe students:identify basic terms of graph theory and optimization and illustrate them with examplesname typical graph theory problems and algorithmic solutionsidentify situations where graph algorithms can be applieddiscuss typical graph theory problems and algorithmic solutions with regard to their efficiency and applicability.implement graph algorithmsknow proof strategies and are able to apply themMethodological competenceThe students:extend their knowledge about algorithms and their complexitydevelop their programming skillsexpand their range of methods of mathematical modellingSocial competenceThe students:use the language of mathematics to discuss problems in groups with different knowledge levelspresent their ideas in a comprehensible wayExpand and improve their own ideas through the comments of their fellow studentsSelf-competenceThe students:reflect their knowledge about algorithms and their complexitydevelop appropriate solutions for given problemschallenge methods of resolution Module contents A) TreesB) Search AlgorithmsC) Graph ColoringD) Flows in NetworksE) Applications of Network AlgorithmsF) Shortest PathsG) Approximation AlgorithmsG) Approximation Algorithms Literaturempfehlungen Jungnickel, Dieter: Graphs, Networks and Algorithms. Springer, Berlin,Heidelberg, 4th edition, 2013. Available as an E-Book in BIS.A detailed bibliography is contained in the lecture notes of this module. Links Language of instruction German Duration (semesters) 1 Semester Module frequency jährlich Module capacity unlimited Modullevel / module level AS (Akzentsetzung / Accentuation) Modulart / typ of module je nach Studiengang Pflicht oder Wahlpflicht Lehr-/Lernform / Teaching/Learning method V+Ü Vorkenntnisse / Previous knowledge Grundveranstaltungen Mathematik und Informatik
Form of instruction Comment SWS Frequency Workload of compulsory attendance
Lecture 3 SoSe 42
Exercises 1 SoSe 14
Präsenzzeit Modul insgesamt 56 h
Examination Prüfungszeiten Type of examination
Final exam of module
At the end of the lecture period
Written exam