Randomisierter Min-Cut-Algorithmus für Streaming-Graph-Analyse
Übersicht
Worum es bei diesem Projekt geht.
Implementieren Sie Karger's einfachen Min-Cut-Algorithmus und die rekursive Variante Karger-Stein. Implementieren Sie zusätzlich Stoer-Wagner als deterministische Referenz. Benchmarken Sie auf 5 Graph-Klassen (zufällige G(n,p), Power-Law, geclusterte Communities, Path-Strukturen, reale anonymisierte Social-Graphen mit n = 500 bis 50.000). Messen Sie für Karger-Stein die empirische Erfolgswahrscheinlichkeit pro Lauf und leiten Sie die nötige Wiederholungszahl für 99 % Konfidenz ab. Liefern Sie die Implementierung, ein Benchmark-Notebook und einen 5-seitigen Bericht mit konkreter Produkt-Empfehlung.
Das Briefing
Was Du tust und was Du zeigst.
Wie viele Wiederholungen von Karger-Stein sind nötig, um auf realen Social-Graphen mit 99-%-Konfidenz den Min-Cut zu finden, und wie schlägt sich das Verfahren gegen Stoer-Wagner in Praxislaufzeit?
Earning criteria — what you'll demonstrate
- Randomisierte Graphalgorithmen korrekt und effizient implementieren
- Erfolgswahrscheinlichkeiten randomisierter Verfahren empirisch messen
- Verstärkungs-Argumente (Repetition Boost) konkret quantifizieren
- Algorithmen-Auswahl für ein Produkt-Team mit Daten begründen
Studienpassung
Wo dies in Dein Studium passt.
Schärft dieselben Fähigkeiten, die Dein Studium von Dir erwartet.
Fähigkeiten
Fähigkeiten, die Du unter Beweis stellst.
Jede taucht auf Deinem verifizierten Zertifikat auf.
Karrieren
Berufe, auf die dies Dich vorbereitet.
Echte Berufsbezeichnungen. Echte Skill-Brücken. Wähle die, die Deinem Werdegang am nächsten kommt.
Karrierewege, die das aufbaut
Kanonische RollenSoftwareentwickler:in
Ein konkreter Vergleich randomisiert vs. deterministisch für einen Graphalgorithmus ist eine seltene Code-Probe, die in Algorithmus-zentrierten Senior-Interviews positiv auffällt.
Dieses Projekt schärft
- randomized-algorithms
- graph-algorithms
- python
Data Engineer:in
Graph-Analytics-Pipelines profitieren massiv von randomisierten Vorfiltern — wer die Methodik beherrscht, kann Pipeline-Architektur sichtbar verbessern.
Dieses Projekt schärft
- graph-algorithms
- performance-benchmarking
- python
Noch eine Sache