Algo2Go

Wir schauen uns in dieser Folge IPs (Interger Programme) an. Aus Episode 15 kennen wir bereits LPs (Lineare Programme), die sich mit dem Simplex-Algorithmus lösen lassen. IPs fordern nun noch zusätzlich, dass die Lösungen alle ganzzahlig sein sollen. Im Allgemeinen findet der SImplex-Algorithmus keine solchen Lösungen, aber wenn wir noch das Branch-and-Bound-Verfahren draufwerfen, dann erhalten wir ganzzahlige Lösungen.

Das P-vs-NP-Problem ist eines der größten offenen Probleme der Informatik. Wir schauen uns in dieser Folge die beiden Klassen einmal an und beschreiben Zusammenhänge und Implikationen der möglichen Ergebnisse.

Wie werden Mails und andere Informationen, die man im Internet austauscht verschlüsselt? In dieser Folge erklären wir euch den RSA-Algorithmus, der in ähnlicher Form überall im Internet Anwendung findet, sowie den Diffie-Hellman-Handshake.

Wir haben mit Lukas von der Universität Augsburg einen weiteren Gast im Podcast. Er stellt uns seine Arbeit an Instanteneous Dynamic Equilibria vor, die Verkehrsflüsse beschreiben mit Autos die mithilfe von GPS navigiert werden.

In vielen praktischen Anwendungen ist es notwendig 1:1-Zuordnungen zwischen Menschen oder Objekten zu finden, die in irendeinerweise kompatibel zueinander sind. Ein medizinisches Beispiel sind Überkreuz-Nierenspenden, bei denen Spender/Empfänger-Paare passend ausgewählt werden müssen um kompatible Organspender zu finden. Solche Probleme lassen sich als Matchingproblem in ungerichteten Graphen modellieren und können mithilfe von Edmonds' Blossom-Shrink-Algorithmus gelöst werden.

Viele Optimierungsprobleme aus der Praxis lassen sich als lineares Programm (ein System aus einer linearen Zielfunktion und linearen Ungleichungen) formulieren. Solche Programme lassen sich mit Hilfe des Simplex-Algorithmus in der Regel schnell lösen. Um eine optimale Lösung zu finden, bewegt sich der Algorithmus von Ecke zu Ecke eines belieibig hochdimensionalen Polyeders, sodass in jedem Schritt sich der Zielfunktionswert verbessert.

Wie plant man optimal seine Woche oder Aufträge auf der Arbeit? Solche Scheduling-Probleme besprechen wir in dieser Folge und stellen euch zwei Algorithmen vor.

Wie kann man etwas gemeinsam Erarbeitetes fair verteilen? Wir stellen euch dafür die drei Aufteilungskonzepte Shapley-Wert, Core und Nucleolus vor.

Bisher haben wir uns Probleme angeguckt, bei denen die gesamte Eingabe bereits zu Beginn eines Algorithmus bekannt war. Heute schauen wir uns Online-Probleme an, bei denen die Eingabe erst nach und nach über die Zeit eintrifft und der Algorithmus sofort eine Entscheidung über diesen Teil der Eingabe fällen muss.

In dieser Folge untersuchen wir Wahlen von ihren algorithmischen und strategischen Seiten. Wir stellen außerdem den Satz von Arrow vor, der die Unmöglichkeit einer perfekten sozialen Wohlfahrtsfunktion (und damit von fairen Wahlen) zeigt.

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.info/v8/masks, die aktuellsten Plots sind hier zu finden: https://covid-sim.info/2021-02-20.

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.

In dieser Epsiode stellen wir uns und das Konzept des Podcasts vor. Außerdem erklären wir euch, was ein Algorithmus ist.