|
Effiziente kombinatorische Algorithmen (EffAlg)7.5 ECTS (englische Bezeichnung: Efficient Combinatorial Algorithms)
(Prüfungsordnungsmodul: Effiziente kombinatorische Algorithmen)
Modulverantwortliche/r: Rolf Wanka Lehrende:
Rolf Wanka
Startsemester: |
WS 2021/2022 | Dauer: |
1 Semester | Turnus: |
jährlich (WS) |
Präsenzzeit: |
60 Std. | Eigenstudium: |
165 Std. | Sprache: |
Deutsch oder Englisch |
Lehrveranstaltungen:
Empfohlene Voraussetzungen:
Es wird empfohlen, folgende Module zu absolvieren, bevor dieses Modul belegt wird:
Berechenbarkeit und Formale Sprachen (WS 2020/2021)
Inhalt:
In diesem Modul werden effiziente exakte Algorithmen für diskrete Probleme vorgestellt. Zuerst werden nichttriviale tiefensuchbasierte Linearzeitverfahren für die Berechnung zweifacher Zusammenhangskomponenten auf ungerichteten Graphen und starker Zusammenhangskomponenten auf gerichteten Graphen untersucht. Danach werden Polynomialzeit-Verfahren zur Berechnung maximaler Flüsse präsentiert. Eine Einführung in den Entwurf und die Analyse parametrisierter Algorithmen an Hand des Vertex-Cover-Problems und eine Einführung in den Bereich der sog. mild-exponentiellen Algorithmen für das Erfüllbarkeitsproblem und weiterer NP-vollständiger Probleme runden das Modul ab.
Lernziele und Kompetenzen:
- Wissen
- Lernende können Wissen abrufen und wiedergeben. Sie kennen konkrete Einzelheiten wie Begriffe, Definitionen, Fakten, Regeln, Gesetzmäßigkeiten, Theorien.
- Verstehen
- Lernende können Beispiele anführen, Aufgabenstellungen interpretieren oder ein Problem in eigenen Worten wiedergeben.
- Anwenden
- Lernende können ein neues Problem durch Transfer des Wissens lösen.
- Analysieren
- Lernende können ein Problem in einzelne Teile zerlegen und so die Struktur des Problems verstehen; sie können Zusammenhänge erkennen und Folgerungen ableiten.
Literatur:
- A. V. Aho, J. E. Hopcroft, J. D. Ullman. The Design and Analysis of Computer Algorithms. Addison-Wesley, 1975.
Venkatesh Raman, Saket Saurabh, Somnath Sikdar. Efficient Exact Algorithms through Enumerating Maximal Independent Sets and Other Techniques. Theory of Computing Systems 41 (2007) 563-587.
Frank Gurski, Irene Rothe, Jörg Rothe, Egon Wanke. Exakte Algorithmen für schwere Graphenprobleme. Springer 2010.
Sven Oliver Krumke, Hartmut Noltemeier. Graphentheoretische Konzepte und Algorithmen. Vieweg+Teubner, 2. Auflage 2009.
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein. Introduction to Algorithms (2nd Edition). MIT Press, 2001.
Fedor V. Fomin, Dieter Kratsch. Exact Exponential Algorithms. Springer, 2010.
Volker Heun. Grundlegende Algorithmen. Vieweg, 2. Auflage 2003.
Juraj Hromkovic. Algorithmics for Hard Problems. Springer, 2001.
Stephan Hußmann, Brigitte Lutz-Westphal (Hrsg.). Kombinatorische Optimierung erleben. Vieweg, 2007.
Jon Kleinberg, Eva Tardos. Algorithm Design. Pearson / Addison Wesley, 2006.
Sven Oliver Krumke, Hartmut Noltemeier. Graphentheoretische Konzepte und Algorithmen. Vieweg+Teubner, 2. Auflage 2009.
Christos H. Papadimitriou, Kenneth Steiglitz. Combinatorial Optimization: Algorithms and Complexity. Dover Publications, 1998.
Volker Turau. Algorithmische Graphentheorie. Oldenbourg, 3. Auflage 2009.
Vöcking et al. (Hrsg.) Taschenbuch der Algorithmen. Springer 2008.
Verwendbarkeit des Moduls / Einpassung in den Musterstudienplan:
- Informatik (Master of Science)
(Po-Vers. 2010 | TechFak | Informatik (Master of Science) | Gesamtkonto | Wahlpflichtbereich | Säule der theoretisch orientierten Vertiefungsrichtungen | Vertiefungsrichtung Theoretische Informatik | Effiziente kombinatorische Algorithmen)
Dieses Modul ist daneben auch in den Studienfächern "Computational Engineering (Master of Science)", "Computational Engineering (Rechnergestütztes Ingenieurwesen) (Master of Science)", "Informatik (Bachelor of Arts (2 Fächer))", "Informatik (Bachelor of Science)", "Mathematik (Bachelor of Science)", "Wirtschaftsinformatik (Bachelor of Science)" verwendbar. Details
Studien-/Prüfungsleistungen:
Effiziente kombinatorische Algorithmen (Vorlesung mit Übung) (Prüfungsnummer: 843472)
- Prüfungsleistung, mündliche Prüfung, Dauer (in Minuten): 30, benotet
- Anteil an der Berechnung der Modulnote: 100.0 %
- weitere Erläuterungen:
- Prüfungssprache: Deutsch oder Englisch. Die Unterrichts- und Prüfungssprache hängt von den Sprachkenntnissen und Präferenzen der Teilnehmerinnen und Teilnehmer ab und wird dementsprechend innerhalb der ersten zwei Wochen nach Vorlesungsbeginn festgelegt.
- Erstablegung: WS 2021/2022, 1. Wdh.: SS 2022
|
![](/img/anew/void.gif) |
![](/img/anew/void.gif) |
|
UnivIS ist ein Produkt der Config eG, Buckenhof |
|
|