Основы теории передачи информации

Теория информации возникла в основополагающей работе Шеннона (Shannon, 1948), которая попыталась формализовать и количественно оценить коммуникацию. Эта теория в основном игнорировалась теоретической информатикой до 1990-х годов, когда инструменты и концепции из теории информации начали играть центральную роль в мощных результатах в этой области. Примечательными примерами являются Теорема о параллельном повторении (1994), разработка меры информационной сложности как средства понимания коммуникативной сложности (2001). Сегодня информационно-теоретические меры и инструменты влияют на многие аспекты теории компьютерных наук, включая анализ потоковых алгоритмов, дифференциальную конфиденциальность и теорию игр. В этом курсе будут представлены основные понятия теории информации, а затем примеры тем, представляющих интерес для теории компьютерных наук, где инструменты теории информации играют центральную роль.