Skip to main content
Algo2Go

Algo2Go

By Niklas Rieken, Laura Vargas Koch, Björn Tauer
In jeder Folge stellen wir euch einen Algorithmus vor. Dabei orientieren wir uns am Anfang an einer Algorithmen-Vorlesung unseres Lehrstuhls, mal sehen was später noch daraus wird.
Listen on
Where to listen
Apple Podcasts Logo

Apple Podcasts

Breaker Logo

Breaker

Google Podcasts Logo

Google Podcasts

Pocket Casts Logo

Pocket Casts

RadioPublic Logo

RadioPublic

Spotify Logo

Spotify

Currently playing episode

Episode 12 - Online-Algorithmen

Algo2Go

1x
Episode 19 - P und NP
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.
23:34
June 13, 2021
Episode 18 - Verschlüsselung
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.
39:00
May 30, 2021
Episode 17 - IDEs in dynamischen Flüssen
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.
40:21
May 23, 2021
Episode 16 - Maximale Matchings
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.
29:43
May 16, 2021
Episode 15 - Der Simplex-Algorithmus
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.
34:26
May 9, 2021
Episode 14 - Scheduling
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.
20:28
May 2, 2021
Episode 13 - Fairness
Wie kann man etwas gemeinsam Erarbeitetes fair verteilen? Wir stellen euch dafür die drei Aufteilungskonzepte Shapley-Wert, Core und Nucleolus vor.
28:50
April 25, 2021
Episode 12 - Online-Algorithmen
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.
24:07
April 18, 2021
Episode 11 - Wahlen
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.
28:25
April 11, 2021
Episode 10 - Auktionen
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.
36:36
March 28, 2021
Episode 9 - Rundreiseproblem
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.
31:33
March 21, 2021
Episode 8 - Maximale Flüsse
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.
24:31
March 14, 2021
Episode 7 - Kürzeste Wege II
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.
31:23
March 7, 2021
Episode 6 - MATSim und EpiSim
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.
44:22
February 28, 2021
Episode 5 - Kürzeste Wege
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.
28:19
February 21, 2021
Episode 4 - Sortieralgorithmen
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.
34:30
February 14, 2021
Episode 3 - Nash-Gleichgewichte
Game Time! John Nash trifft Barney Stinson. Wir diskutieren Spieltheorie, Gleichgewichtskonzepte und algorithmische Anwendungen im Straßenverkehr.
29:52
February 7, 2021
Episode 2 - Greedy-Algorithmen
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.
32:46
January 31, 2021
Episode 1 - Der Gale-Shapley-Algorithmus
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.
28:30
January 24, 2021
Nullnummer - Was ist ein Algorithmus?
In dieser Epsiode stellen wir uns und das Konzept des Podcasts vor. Außerdem erklären wir euch, was ein Algorithmus ist.
26:02
January 17, 2021