Algo2Go

In dieser Folge stellen wir euch Auktionen als Algorithmen zum Finden von Preisen und Allokationen von Gütern vor. Je nach Auktionsformat unterscheiden sich optimale Bietstrategien und die zu erwartende Güte der Ergebnisse.

In dieser Folge stellen wir euch das Problem des Handlungsreisenden, ein Milleniumproblem, vor. Die Bestimmung der Route einer Stadtführung entlang aller Sehenswürdigkeiten mit möglichst kurzem Fußweg stellt unsere Computer vor große Herausforderungen. Deshalb erklären wir euch einen Algorithmus, der eine Route bestimmt, bei der ihr höchstens die doppelte Distanz zurücklegen müsst.

Viele praktische Probleme lassen sich als Flussprobleme in gerichteten Graphen formulieren. Wie viel Wasser gleichzeitig durch ein Netzwerk aus Rohren gepumpt werden kann, ist ein sehr naheliegendes Problem, aber auch die Chancen auf die Meisterschaft in Sportwettbewerben oder der Spielplan eines Round-Robin-Turniers kann mit Hilfe von Fluss-Algorithmen bestimmt werden. Wir stellen euch in dieser Folge den Ford-Fulkerson-Algorithmus zur Berechnung maximaler Flüsse vor.

Wir schauen uns erneut das Problem an kürzeste Wege in Graphen zu finden. Diesmal erlauben wir auch negative Kantenkosten und betrachten die Algorithmen von Bellman-Ford und Floyd-Warshall. Mit negativen Kantenkosten lässt sich auch ein "Infinite-Money-Algorithmus" formulieren.

Unser Gast Theresa von der TU Berlin stellt die Verkehrssimulationsoftware MATSim vor, die in der jüngeren Vergangenheit auch zur Prognostizierung der Ausbreitung des Coronavirus verwendet wurde. Untermauert eure Stammtischparolen mit wissenschaftlichen Fakten. Auf https://covid-sim.info/ findet ihr Simulationen und Plots für verschiedene Corona-Maßnahmen.

Die angesprochenen Plots zum Thema Masken findet ihr hier: https://covid-sim...

Probleme von 2019: Wie komme ich am schnellesten mit Fahrrad oder Bahn zu meinen Freunden? Wir beschreiben die Breitensuche und Dijkstras Algorithmus zum Finden von kürzesten Wegen von einem gegebenen Startknoten zu allen anderen Knoten in einem Graph.

Um Daten schnell im Speicher zu finden (oder Klausuren in einem Stapel) ist es sinnvoll die Datensätze zu sortieren. Sortieren ist ein Prozess, der in vielen anderen Algorithmen als Unterroutine vorkommt und oft sogar die Hauptarbeit eines Programms ausmacht. Umso wichtiger ist es, dass diese Aufgabe effizient ausgeführt wird. Wir stellen in dieser Folge drei Sortieralgorithmen vor.

Game Time! John Nash trifft Barney Stinson. Wir diskutieren Spieltheorie, Gleichgewichtskonzepte und algorithmische Anwendungen im Straßenverkehr.

Greed is good. Zumindest bei Schokolade, Pizza und Matroiden. Wir stellen euch das Konzept von Greedy-Algorithmen vor, die in jedem Schritt eine Entscheidung treffen, die zum aktuellen Zeitpunkt am besten aussieht. Auf manchen Problemen funktionieren diese Algorithmen optimal, auf anderen weniger gut oder sogar sehr schlecht.

Der Gale-Shapley-Algorithmus erzeugt für zwei Gruppen von Menschen oder Objekten eine stabile  1-zu-1-Beziehung. Stabil meint hier, dass es kein unzufriedenes Paar gibt, dass mit der vom Algorithmus bestimmten Aufteilung unzufrieden ist. Wir erklären den Algorithmus anhand eines Beispiels in einer Tanzschule und diskutieren grundlegende Eigenschaften der erhaltenen Lösungen und ein paar Erweiterungen des Modells.

Daraus leiten wir Lebensweisheiten ab.