Shows
Algo2GoEpisode 20 - Branch and BoundWir 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.2021-06-2026 minAlgo2GoEpisode 19 - P und NPDas 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.2021-06-1323 minAlgo2GoEpisode 18 - VerschlüsselungWie 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.2021-05-3039 minAlgo2GoEpisode 17 - IDEs in dynamischen FlüssenWir 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.2021-05-2340 minAlgo2GoEpisode 16 - Maximale MatchingsIn 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.2021-05-1629 minAlgo2GoEpisode 15 - Der Simplex-AlgorithmusViele 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.2021-05-0934 minAlgo2GoEpisode 14 - SchedulingWie 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.2021-05-0220 minAlgo2GoEpisode 13 - FairnessWie kann man etwas gemeinsam Erarbeitetes fair verteilen? Wir stellen euch dafür die drei Aufteilungskonzepte Shapley-Wert, Core und Nucleolus vor.2021-04-2528 minAlgo2GoEpisode 12 - Online-AlgorithmenBisher 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.2021-04-1824 minAlgo2GoEpisode 11 - WahlenIn 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.2021-04-1128 minAlgo2GoEpisode 10 - AuktionenIn 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.2021-03-2836 minAlgo2GoEpisode 9 - RundreiseproblemIn 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.2021-03-2131 minAlgo2GoEpisode 8 - Maximale FlüsseViele 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.2021-03-1424 minAlgo2GoEpisode 7 - Kürzeste Wege IIWir 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.2021-03-0731 minAlgo2GoEpisode 6 - MATSim und EpiSimUnser 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.
2021-02-2844 minAlgo2GoEpisode 5 - Kürzeste WegeProbleme 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.2021-02-2128 minAlgo2GoEpisode 4 - SortieralgorithmenUm 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.2021-02-1434 minAlgo2GoEpisode 3 - Nash-GleichgewichteGame Time! John Nash trifft Barney Stinson. Wir diskutieren Spieltheorie, Gleichgewichtskonzepte und algorithmische Anwendungen im Straßenverkehr.2021-02-0729 minAlgo2GoEpisode 2 - Greedy-AlgorithmenGreed 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.2021-01-3132 minAlgo2GoEpisode 1 - Der Gale-Shapley-AlgorithmusDer 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.2021-01-2428 minAlgo2GoNullnummer - 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.2021-01-1726 min