====== Randomisierte Algorithmik ====== **Betreuung:** [[people:thomasblaesius|]], [[people:maximiliankatzmann|]], [[https://algo2.iti.kit.edu/lehmann.php|Hans-Peter Lehmann]], [[https://algo2.iti.kit.edu/sanders.php|Peter Sanders]], [[https://algo2.iti.kit.edu/4650.php|Stefan Walzer]] \\ In der Vorlesung geht es darum, zu verstehen, wann und warum Randomisierung zur Lösung eines algorithmischen Problems nützlich oder notwendig ist. Dabei werden zentrale Entwurfsmethoden und Analysewerkzeuge der randomisierten Algorithmik erklärt und trainiert wie randomisierte Algorithmen und Datenstrukturen zur Lösung eines Problems entworfen werden können und welche Werkzeuge sich für die Analyse der Ansätze eignen. \\ [[https://ilias.studium.kit.edu/goto.php?target=crs_2244855&client_id=produktiv|Ilias-Kurs]] für Abgabe der Übungsblätter, Discord-Link, etc. Teile der Vorlesung werden auch im {{ :teaching:2023ws:randalg:worsch-skript.pdf |Skript der Vorgängerveranstaltung}} behandelt, aber nicht alle. ===== Ablauf ===== Es gibt zwei wiederkehrende Termine: * wöchentlich Donnerstags 11:30 - 13:00, Raum 236 (typischerweise Vorlesung) * zwei-wöchentlich Dienstags 08:00 - 09:30, Raum 236 (typischerweise Übung) Die erste Woche bildet hierbei eine Ausnahme! \\ \\ ^ Woche ^ Dienstag ^ Donnerstag ^ | 1 | 2023-10-24: Vorlesung 1 | 2023-10-26: Übung 1 | | 2 | | 2023-11-02: Vorlesung 2 | | 3 | 2023-11-07: Übung 2 | 2023-11-09: Vorlesung 3 | | 4 | | 2023-11-16: Vorlesung 4 | | 5 | 2023-11-21: Übung 3 | 2023-11-23: Vorlesung 5 | | 6 | | 2023-11-30: Vorlesung 6 | | 7 | 2023-12-05: Übung 4 | 2023-12-07: Vorlesung 7 | | 8 | | 2023-12-14: Vorlesung 8 | | 9 | 2023-12-19: Übung 5 | 2023-12-21: Vorlesung 9 | | 10 | | 2024-01-11: Vorlesung 10 | | 11 | 2024-01-16: Übung 6 | 2024-01-18: Vorlesung 11 | | 12 | | 2024-01-25: Vorlesung 12 | | 13 | 2024-01-30: Übung 7 | 2024-02-01: Gemischte Session | | 14 | | 2024-02-08: Inverted-Classroom Session | | 15 | 2024-02-13: Inverted Classroom Session | 2024-02-15: Zusammenfassung + Fragen | ===== Vorlesung ===== Hier erscheinen die Foliensätze der Vorlesungen - Overview & The Power of Randomness: {{ :teaching:2023ws:randalg:introduction.pdf |mit Klicks}}, {{ :teaching:2023ws:randalg:introduction-print.pdf |ohne Klicks}} - Probability Amplification: {{ :teaching:2023ws:randalg:probability-amplification.pdf |mit Klicks}}, {{ :teaching:2023ws:randalg:probability-amplification-print.pdf |ohne Klicks}} - Coupling & Erdős-Rényi Random Graphs: {{ :teaching:2023ws:randalg:er-coupling.pdf |mit Klicks}}, {{ :teaching:2023ws:randalg:er-coupling-print.pdf |ohne Klicks}} (Update 09.11. - 15:15 - Herleitung der Coupling Inequality korrigiert) - Concentration: {{ :teaching:2023ws:randalg:concentration.pdf |mit Klicks}}, {{ :teaching:2023ws:randalg:concentration-print.pdf |ohne Klicks}} (Update 08.02. - 16:30 - Fehlende Folien in "ohne Klicks" ergänzt) - Nachtrag zum Coupling im Konzentrationsbeweis: {{ :teaching:2023ws:randalg:proof-coupling-extension.pdf | ohne Klicks}} - Probabilistic Method: {{ :teaching:2023ws:randalg:probabilistic-method.pdf |mit Klicks}}, {{ :teaching:2023ws:randalg:probabilistic-method-print.pdf |ohne Klicks}} (Update 23.11. 14:30 -- Beispiel mit Abhängigkeiten und Ungleichheitszeichen korrigiert) - Continuous Probability Spaces & Random Geometric Graphs: {{ :teaching:2023ws:randalg:continuous.pdf |mit Klicks}}, {{ :teaching:2023ws:randalg:continuous-print.pdf |ohne Klicks}} (Update 05.12. 16:00: Integration durch Substitution, Kettenregel für bedingte Dichtefunktionen und Torus-Distanz korrigiert) - Bounded Differences & Geometric Inhomogeneous Random Graphs: {{ :teaching:2023ws:randalg:bounded-differences.pdf |mit Klicks}}, {{ :teaching:2023ws:randalg:bounded-differences-print.pdf |ohne Klicks}} (Update 07.12. 13:30 -- Doppelte Quantifizierung in Lipschitzbedingungen korrigiert) - {{ :teaching:2023ws:randalg:complexity-classes.pdf |Complexity Classes}} ({{ :teaching:2023ws:randalg:complexity-classes-handout.pdf | ohne Klicks}}) - {{ :teaching:2023ws:randalg:game-theory-yao.pdf |Lower bounds using Yao's Principle}} ({{ :teaching:2023ws:randalg:game-theory-yao-handout.pdf | ohne Klicks}}) - {{ :teaching:2023ws:randalg:approximation.pdf |Approximation Algorithms}} ({{ :teaching:2023ws:randalg:approximation-handout.pdf | ohne Klicks}}) - {{ :teaching:2023ws:randalg:streaming.pdf |Streaming Algorithms}} ({{ :teaching:2023ws:randalg:streaming-handout.pdf | ohne Klicks}}) - {{ :teaching:2023ws:randalg:hashing1.pdf |Classic Hash Tables}} ({{ :teaching:2023ws:randalg:hashing1-handout.pdf | ohne Klicks}}) - {{ :teaching:2023ws:randalg:bloom.pdf |Bloom Filter}} ({{ :teaching:2023ws:randalg:bloom-handout.pdf | ohne Klicks}}) - {{ :teaching:2023ws:randalg:cuckoo.pdf |Cuckoo Hashing}} ({{ :teaching:2023ws:randalg:cuckoo-handout.pdf | ohne Klicks}}) [[https://www.youtube.com/watch?v=2mUI-gAqvRA|VORLESUNGSVIDEO]] - {{ :teaching:2023ws:randalg:peeling.pdf |Peeling}} ({{ :teaching:2023ws:randalg:peeling-handout.pdf |ohne Klicks}}) [[https://www.youtube.com/watch?v=pH3nJPfvRpY|VORLESUNGSVIDEO]] - {{ :teaching:2023ws:randalg:retrieval-and-ph.pdf | Retrieval and Perfect Hashing}} ({{ :teaching:2023ws:randalg:retrieval-and-ph-handout.pdf | ohne Klicks}}) [[https://www.youtube.com/watch?v=Z7a9-AGp-Do|VORLESUNGSVIDEO]] - {{ :teaching:2023ws:randalg:conclusion-print.pdf |Conclusion}} == Vollständiger Foliensatz == {{ :teaching:2023ws:randalg:probcomp-ws2324-handout.pdf | Ohne Klicks}} (50 MB). ===== Übungen ===== Hier erscheint das Material zu den Übungen * {{ :teaching:2023ws:randalg:00-blatt-notizen.pdf | Notizen zu Blatt 00}} * {{ :teaching:2023ws:randalg:01-blatt-notizen.pdf | Notizen zu Blatt 01}} * {{ :teaching:2023ws:randalg:02-blatt-notizen.pdf | Notizen zu Blatt 02}} * {{ :teaching:2023ws:randalg:03-blatt-notizen.pdf | Notizen zu Blatt 03}}, {{ :teaching:2023ws:randalg:03-blatt-notizen-bonus.pdf | Studentischer Vorschlag zur Bonusaufgabe}} * {{ :teaching:2023ws:randalg:04-blatt-notizen.pdf | Notizen zu Blatt 04}} * {{ :teaching:2023ws:randalg:05-blatt-notizen.pdf | Notizen zu Blatt 05}} * {{ :teaching:2023ws:randalg:06-blatt-notizen.pdf | Notizen zu Blatt 06}} * {{ :teaching:2023ws:randalg:07-blatt-notizen.pdf | Notizen zu Blatt 07}} * {{ :teaching:2023ws:randalg:08-blatt-solution.pdf | Lösungsvorschlag zu Blatt 08}} * {{ :teaching:2023ws:randalg:09-blatt-solution.pdf | Lösungsvorschlag zu Blatt 09}} * {{ :teaching:2023ws:randalg:10-blatt-solution.pdf | Lösungsvorschlag zu Blatt 10}} * {{ :teaching:2023ws:randalg:11-blatt-solution.pdf | Lösungsvorschlag zu Blatt 11}} * {{ :teaching:2023ws:randalg:12-blatt-sol.pdf | Lösungsvorschlag zu Blatt 12}} * {{ :teaching:2023ws:randalg:13-blatt-aktiv-sol.pdf | Lösungsvorschlag zu Blatt 13}} * {{ :teaching:2023ws:randalg:14-blatt-aktiv-sol.pdf | Lösungsvorschlag zu Blatt 14}} * {{ :teaching:2023ws:randalg:15-blatt-aktiv-sol.pdf | Lösungsvorschlag zu Blatt 15}} ===== Übungsblätter ===== Übungsblätter können jeweils bis zum Donnerstag vor der nächsten Übung über den [[https://ilias.studium.kit.edu/goto.php?target=crs_2244855&client_id=produktiv|Ilias-Kurs]] abgeben werden. * {{ :teaching:2023ws:randalg:00-blatt.pdf | Blatt 00}} * {{ :teaching:2023ws:randalg:01-blatt.pdf | Blatt 01}} * {{ :teaching:2023ws:randalg:02-blatt.pdf | Blatt 02}} * {{ :teaching:2023ws:randalg:03-blatt.pdf | Blatt 03}} * {{ :teaching:2023ws:randalg:04-blatt.pdf | Blatt 04}} (Update 16.11. - 18:30: Bessere Variablennamen) * {{ :teaching:2023ws:randalg:05-blatt.pdf | Blatt 05}} * {{ :teaching:2023ws:randalg:06-blatt.pdf | Blatt 06}} * {{ :teaching:2023ws:randalg:07-blatt.pdf | Blatt 07}} (Update 08.12. - 11:30: Fehlende Definition von X ergänzt) * {{ :teaching:2023ws:randalg:08-blatt.pdf | Blatt 08}} * {{ :teaching:2023ws:randalg:09-blatt.pdf | Blatt 09}} * {{ :teaching:2023ws:randalg:10-blatt.pdf | Blatt 10}} * {{ :teaching:2023ws:randalg:11-blatt.pdf | Blatt 11}} * {{ :teaching:2023ws:randalg:12-blatt.pdf | Blatt 12}} * {{ :teaching:2023ws:randalg:13-blatt-aktiv.pdf | Blatt 13}} * {{ :teaching:2023ws:randalg:14-blatt-aktiv.pdf | Blatt 14}} * {{ :teaching:2023ws:randalg:15-blatt-aktiv.pdf | Blatt 15}} ===== Evaluation ===== {{ :teaching:2023ws:randalg:ws23_24-evaluation-randomisierte_algorithmik.pdf | Evaluation der Vorlesung}}