Теория информации

Энтропия и оптимальное кодирование. Информация по Хартли; префиксное кодирование и неравенство Крафта–Макмиллана; энтропия Шеннона как оценка средней длины кода; код Фано и арифметическое кодирование.
Информационные неравенства и их комбинаторные приложения. Условная энтропия и цепное правило; метод релятивизации; неравенства Шерера, Лумиса–Уитни и Ромащенко–Каседа; теорема Шеннона об идеальном шифре и неравенство Фано.
Передача информации. Теорема Шеннона о бесшумном канале; теорема Вольфа–Слепяна; каналы с шумом и их пропускная способность.
Предсказание и обучение. Игры предсказания битов и мартингалы; предсказание c экспертами: логарифмический штраф и предсказатель Соломонова, выпуклые штрафы и условие Блэквелла; PAC-обучение и размерность Вапника–Червоненкиса.