Аннотация:
В последние годы наблюдается резкий рост интереса к методам анализа больших данных. В основе многих популярных сейчас подходов к наиболее быстрому получению наиболее точной информации из данных лежат современные главы стохастического анализа. В частности, речь идет о неравенствах концентрации меры, стохастической оптимизации, рандомизированных алгоритмах, оракульных неравенствах и т.д.
К сожалению, доступно все это может быть хорошим студентам лишь где-то к четвертому году обучения. Однако, некоторые (основополагающие) идеи вполне могут быть восприняты и школьниками старших классов (если не вдаваться в технические детали). Это мы и попробуем сделать в настоящем курсе.
Явление концентрации меры
Многие знают, что почти весь объем многомерного арбуза сосредоточен у его границы. Гораздо менее известно, что почти вся площадь поверхности оказывается в малой окрестности экватора – как бы мы не выбирали полюса! Более того, рядом с этим «законом больших чисел» есть и «центральная предельная теорема»: если арбуз n-мерный, а его радиус $\sim \sqrt n$, то первая координата случайно (равномерно) выбранной в этом арбузе точки с хорошей точностью будет (стандартной) нормальной случайной величиной – той же самой, которая стоит в правой части обычной центральной предельной теоремы. Более того, оказывается, что отмеченные выше наблюдения можно перенести на арбузы не обязательно правильной формы (сохраняя при этом строгую выпуклость формы арбуза).
Все это при правильной интерпретации порождает множество всевозможных нелинейных законов больших чисел на самых разнообразных объектах (группы перестановок, хэминговский куб, случайные матрицы, случайные графы, диаграммы Юнга и многое многое другое).
Вероятностные основы теории информации и кодирования
Теоремы Шеннона с точки зрения концентрации меры (схема испытаний Бернулли). Вероятностный метод (случайные коды) и концентрация меры на примере задачи получения граница Эдгара Гилберта. Неравенство Крафта-Макмиллана. Коды Шеннона-Фано и Хаффмана. Коды Хэмминга и их приложения.
Вероятностные методы в Computer Science
Вероятностный анализ алгоритмов. Рандомизированные алгоритмы.
