Studies

193
Compulsory

When a course instance has been created from a template, the course instance will be in this state

  • Data is usually still incomplete and everything can still be edited.
  • Lecturers or secretaries can move the state forward to Edited.

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/

The first class takes place on Tuesday, 18.10.2016.

Contents

  • Algorithms: linear programmimg, optimization, LP Rounding, satisfiability, routing, volume approximation, constructive local lemma, String search, randomized geometric algorithms (closest pair, minimum enclosing circle, ...), Johnson-Lindenstrauss, travels to cryptofantasia (differential privacy, homomorphic encryption, indistinguishability obfuscation)
  • data structures: Treaps, hash tables (universal, cuckoo, tabulation, two-Choice, Robin-Hood, ...), Bloom filter and Bloomier filter, nearest neighbor in high dimensions, range searching
  • Tools: concentration inequalities (Markov, Chebychev, Chernoff), Martingales, Markov-chains, coupling, hashing, fingerprinting, expander-graphs, Lovasz-local-lemma, Entropy, epsilon nets and VC dimension, backwards analysis, etc

Target Audience

M.S.-students in Computer Science, Mathematics or similar courses of study. Afterwards, you can obtain a topic for a Master thesis.

If desired, the class can be held in English.

Recommended Background

Basic knowledge in Mathematics and Theoretical Computer Science: discrete probability theory, discrete Mathematics, linear algebra, simple algebra and number theory, theory of algorithms, NP-completeness theory. More concretely: Contents of Mathematics for Computer Science, Theory of Computation, Algorithms and Data Structures, Advanced Algorithms

Website

http://www.inf.fu-berlin.de/lehre/WS16/RA/

Cross-language

193 154
Compulsory

Expectant Mother

Not dangerous
Partly dangerous
Alternative Course
Dangerous
Show questionnaire

Nursing Mother

Not dangerous
Partly dangerous
Alternative Course
Dangerous
Show questionnaire

AncillaryCourses

Übung zu Randomisierte Algorithmen

Expectant Mother

Not dangerous
Partly dangerous
Alternative Course
Dangerous
Show questionnaire

Nursing Mother

Not dangerous
Partly dangerous
Alternative Course
Dangerous
Show questionnaire