19315401
Vorlesung
WiSe 16/17: Randomisierte Algorithmen
Wolfgang Mulzer, Paul Seiferth
Kommentar
Die erste Vorlesung findet statt am Dienstag, den 18.10.2016.
Inhalt
- Algorithmen: Lineares Programmieren, Optimierung, LP Rounding, Erfüllbarkeit, Routing, Volumenapproximation, konstruktives Lokal Lemma, Stringsuche, randomisierte geometrische Algorithmen (engstes Paar, kleinster umschließender Kreis, ...), Johnson-Lindenstrauss, Reisen nach Kryptofantasia (differential privacy, homomorphic encryption, indistinguishability obfuscation)
- Datenstrukturen: Treaps, Hashtabellen (universell, Kuckuck, Tabulation, Two-Choice, Robin-Hood, ...), Bloom Filter und Bloomier Filter, Nächste Nachbarn in hohen Dimensionen, Bereichssuche
- Werkzeuge: Konzentrationsungleichungen (Markov, Tschebyscheff, Chernoff), Martingale, Markov-Ketten, Coupling, Hashing, Fingerprinting, Expander-Graphen, Lovasz-Lokal-Lemma, Entropie, Epsilon Netze und VC Dimension, Rückwärtsanalyse, etc
Zielgruppe
M.S.-Studenten in Informatik, Mathematik o.ä., Die Vergabe von Masterarbeiten im Anschluss an die Vorlesung ist möglich.
Auf Wunsch kann die Vorlesung auch auf Englisch angeboten werden.
Empfohlene Vorkenntnisse
Grundkenntnisse in Mathematik und theoretischer Informatik: diskrete Wahrscheinlichkeitstheorie, diskrete Mathematik, lineare Algebra, einfache Algebra und Zahlentheorie, Algorithmik, NP-Vollständigkeitstheorie Konkreter: MafI I-III, Grundlagen der theoretischen Informatik, AlP III, Höhere Algorithmik
Website
http://www.inf.fu-berlin.de/lehre/WS16/RA/
SchließenLiteraturhinweise
- R. Motwani, P. Raghavan. Randomized Algorithms. Cambridge University Press, 1995.
- M. Mitzenmacher, E. Upfal. Probability and Computing: Randomized Algorithms and Probabilistic Analysis. Cambridge University Press, 2005.
32 Termine
Regelmäßige Termine der Lehrveranstaltung
Di, 18.10.2016 14:00 - 16:00
Di, 25.10.2016 14:00 - 16:00
Di, 01.11.2016 14:00 - 16:00
Di, 08.11.2016 14:00 - 16:00
Di, 15.11.2016 14:00 - 16:00
Di, 22.11.2016 14:00 - 16:00
Di, 29.11.2016 14:00 - 16:00
Di, 06.12.2016 14:00 - 16:00
Di, 13.12.2016 14:00 - 16:00
Di, 03.01.2017 14:00 - 16:00
Di, 10.01.2017 14:00 - 16:00
Di, 17.01.2017 14:00 - 16:00
Di, 24.01.2017 14:00 - 16:00
Di, 31.01.2017 14:00 - 16:00
Di, 07.02.2017 14:00 - 16:00
Di, 14.02.2017 14:00 - 16:00
Fr, 21.10.2016 10:00 - 12:00
Fr, 28.10.2016 10:00 - 12:00
Fr, 04.11.2016 10:00 - 12:00
Fr, 11.11.2016 10:00 - 12:00
Fr, 18.11.2016 10:00 - 12:00
Fr, 25.11.2016 10:00 - 12:00
Fr, 02.12.2016 10:00 - 12:00
Fr, 09.12.2016 10:00 - 12:00
Fr, 16.12.2016 10:00 - 12:00
Fr, 06.01.2017 10:00 - 12:00
Fr, 13.01.2017 10:00 - 12:00
Fr, 20.01.2017 10:00 - 12:00
Fr, 27.01.2017 10:00 - 12:00
Fr, 03.02.2017 10:00 - 12:00
Fr, 10.02.2017 10:00 - 12:00
Fr, 17.02.2017 10:00 - 12:00
Inhalt
Algorithmen: Lineares Programmieren, Optimierung, LP Rounding, Erfüllbarkeit, Routing, ... Lesen Sie weiter