Winter 2022/23

Algorithmentheorie

Wintersemester 2020/21, 4SWS, 6CP
03-BB-602.02

Algorithmen bilden eine der wichtigsten Grundlagen der
Informatik. Anschaulich beschreibt ein Algorithmus eine Vorgehensweise
um ein Problem zu lösen. Somit bilden Algorithmen eine Grundlage der
Programmierung, sind aber unabhängig von der konkreten
Programmiersprache und Umsetzung. Algorithmen sind so vielfältig wie
ihre Anwendungen, darum ist es umso wichtiger die fundamentalen
Prinzipien des effizienten Algorithmenentwurfs und in den wichtigsten
Problembereichen die grundlegenden Lösungsverfahren zu kennen.

Die Vorlesung hat zum Ziel diese fundamentalen Prinzipien des
Algorithmenentwurfs zu vermitteln. Die Prinzipien werden anhand
klassischer Algorithmen für wichtige Probleme illustriert und
eingeübt. Auf der theoretischen Seite werden die Grundlagen
abstrakter Maschinenmodelle, formale Korrektheitsbeweise und
Laufzeitanalyse vermittelt. Das erworbene Wissen ermöglicht es den
Studierenden für ein gegebenes algorithmisches Problem verschiedene
Lösungsansätze bezüglich ihrer Effizienz zu beurteilen, den am besten
geeigneten Ansatz zur Lösung auszuwählen und seine Korrektheit zu
beweisen.

• Algorithmenparadigmen: Greedy, Divide-and-Conquer, Dynamische Programmierung
• Sortierverfahren
• Grundlegende Begriffe der Graphentheorie
• Graphenprobleme: Kürzeste-Wege, minimale aufspannende Bäume, maximale Netzwerkflüsse

Dozenten:  Prof. Dr. Nicole Megow
Prof. Dr. Sebastian Siebertz

Die Veranstaltung findet online asynchron statt. Der online
Einführungstermin in der ersten Veranstaltungswoche steht noch nicht fest.