Die algorithmische diskrete Mathematik ist ein recht junges Gebiet mit Wurzeln in der Algebra, Graphentheorie, Kombinatorik, Informatik (Algorithmik) und Optimierung. Sie behandelt diskrete Strukturen wie Mengen, Graphen, Permutationen, Partitionen und diskrete Optimierungsprobleme.

Diese Veranstaltung gibt eine Einführung in die algorithmische diskrete Mathematik. Es werden strukturelle und algorithmische Grundlagen der Graphentheorie und kombinatorischen Optimierung vermittelt. Im Vordergrund steht die Entwicklung und mathematische Analyse von Algorithmen zum exakten Lösen von kombinatorischen Optimierungsproblemen. Es werden u.a. folgende Themen behandelt:

* Einführung in Graphentheorie, kombinatorische und lineare Optimierung
* Graphentheorie: Grundbegriffe, Wege in Graphen, Euler- und Hamiltonkreise, Bäume
* Algorithmische Grundlagen (Kodierungslänge, Laufzeit, Polynomialzeitalgorithmen)
* Spannbäume, Matchings, Netzwerkflüsse und -schnitte (kombinatorische Algorithmen)
* Matroide
* Einblick in lineare Optimierung: Modellierung, Polyedertheorie, Optimalitätskriterien, Dualität
* Elemente der Komplexitätstheorie

Die Veranstaltung richtet sich an fortgeschrittene Bachelorstudierende.

Findet zusammen mit der Veranstaltung 03-M-SP-42 Approximation Theory statt.

Die Funktionalanalysis untersucht unendlichdimensionale Räume und die darauf definierten Operatoren.

Einblicke in die Industriemathematik: mathematische Modellierung, Analyse und numerische Simulationen zu wöchentlich wechselnden Anwendungsproblemen.

Fortsetzung von Numerik~1: Entwicklung und Analyse von Algorithmen zur approximativen Lösung mathematischer Probleme, die insbesondere in industriellen Anwendungen auftreten.
Die Veranstaltung findet im NEOS Gebäude, Raum 3410, statt.

https://lvb.informatik.uni-bremen.de/igs/03-ibfw-hto.pdf
A large number of problems arising in practical scenarios like communication, transportation, planning, logistics etc. can be formulated as discrete linear optimization problems. This course briefly introduces the theory of such problems. We develop a toolkit to model real-world problems as (discrete) linear programs. We also explore several ways to find integer solutions such as cutting planes, branch & bound, and column generation.

Throughout the course, we learn these skills by modeling and solving, for example, scheduling, packing, matching, routing, and network-design problems. We focus on translating practical examples into mixed-integer linear programs. We learn how to use solvers (such as CPLEX, Gurobi, Xpress and free ones) and tailor the solution process to certain properties of the problem.

This course consists of two phases:

• One week Mon-Fri (full day, 9-5) of lectures and practical labs: July 14-18, in MZH.
• A subsequent project period: One problem has to be modeled, implemented, and solved individually or in a group of at most three students. The topic will be provided by the lecturers and will be discussed on the last day of the block course. The project including the implementation has to be presented in the beginning of the winter semester.

There are no prerequisites except some basic programming skills to participate.

3 SWS Seminar
Raum im KKSB Linz 4
Homepage des KKSB und Uni-Lageplan