Мини-курс Александра Шеня "Случайность и псевдо-случайность".
Мероприятие завершено
С 27 по 29 ноября 2017 года Александр Шень прочтет мини-курс "Случайность и псевдо-случайность".
Место проведения: Факультет компьютерных наук, Кочновский проезд, 3.
Язык мини-курса: русский
Расписание мини-курса:
27 ноября, 12:10-13:30, ауд. 301
29 ноября, 18:10-21:00, ауд. 503
Приглашаются все желающие.
Заказ пропуска: evavilova@hse.ru
Аннотация
В классической теории вероятности понятия индивидуального случайного объекта не существует - скажем, все последовательности нулей и единиц длины $n$, будь то последовательность из одних нулей или любая иная, "одинаково случайны" с точки зрения гипотезы честной монеты. Алгоритмическая теория вероятностей предлагает считать случайными объекты максимальной сложности (несжимаемые, не имеющие более короткого описания). Это имеет смысл, но делает невозможным алгоритмы - "генераторы случайных чисел" (построенная таким алгоритмом последовательность сжимаема по определению). После появления теории сложности была предложена (Яо, Блюм, Микэли) математическая модель таких генераторов в терминах теории сложности вычислений, ныне общепринятая. Мы разберём это определение и его простейшие свойства и применения (эквивалентность непредсказуемости и неотличимости, построение на основе необратимой перестановки по Левину-Голдрайху, применение для дерандомизации и пр.)
Изложение предполагает минимальное знакомство с теорией алгоритмов и сложности вычислений (классы P, NP)
Дата
27 ноября
12:10
Адрес
Кочновский пр-д., д.3
В статье упомянуты