Předmět Randomness and Communication (IA170)

Na serveru studentino.cz naleznete nejrůznější studijní materiály: zápisky z přednášek nebo cvičení, vzorové testy, seminární práce, domácí úkoly a další z předmětu IA170 - Randomness and Communication, Fakulta informatiky, Masarykova univerzita (MU).

Materiál	Typ	Datum	Počet stažení

Cíl

At the end of the course student should have a broad knowledge and an ability to independent study and solve problems in the areas of: randomness generation, randomness post processing, using real world randomness efficiently in information processing, efficient communication both with and without noise in the channel, efficient distributed function computation. He should acquire necessary knowledge of information theory as well. Should be able to learn independently new problems requiring knowledge of information theory, randomness and communication complexity.

Osnova

- Operational meaning of information and entropy. Shannon entropy, relative entropy, mutual information. Renyi entropy. Min- and Max- entropy.- Shannon (asymptotic) channel capacity. Assisted channel capacity, channels with memory. Shannon’s forward and reverse channel capacity theorem. Shannon’s zero-error capacity, Lovasz‘s theta function.- Perfect and weak randomness, applications. Measuring randomness. Randomness extraction, extractors, seeded extractors, independent-source extractors. Pseudorandom structures: k-wise independent random variables, expanders.- Communication complexity. Communication-efficient distributed computation. Randomness and communication complexity.

Literatura

doporučená literaturaInformation theory :coding theorems for discrete memoryless cystems. ISBN 9780521196819. info- KUSHILEVITZ, Eyal a Noam NISAN. Communication complexity. Cambridge: Cambridge University Press, c1997, xiii, 189 s. ISBN 0521560675STINSON, Douglas Robert. Cryptography :theory and practice. 3rd ed. Boca Raton: CRC Press, 2006. 593 p. ISBN 1-58488-508-4. infoElements of information theory. Edited by T. M. Cover - Joy A. Thomas. 2nd ed. Hoboken, N.J.: Wiley-Interscience, 2006. xxiii, 748. ISBN 9780471241959. infoMITZENMACHER, Michael a Eli UPFAL. Probability and computing :an introduction to randomized algorithms and probabilistic analysis. New York: Cambridge University Press, 2005. xvi, 352 s. ISBN 0-521-83540-2. info

Požadavky

Knowledge of basic discrete mathematics (e.g. as presented in the course IB000), basic knowledge of probability theory (e.g. IV111).

Garant

prof. RNDr. Mojmír Křetínský, CSc.

Vyučující

RNDr. Jan Bouda, Ph.D.Frédéric Dupont Dupuis, Ph.D.