Одним из главных принципов уникальной «системы Физтеха», заложенной в основу образования в МФТИ, является тщательный отбор одаренных и склонных к творческой работе представителей молодежи. Абитуриентами Физтеха становятся самые талантливые и высокообразованные выпускники школ всей России и десятков стран мира.

Студенческая жизнь в МФТИ насыщенна и разнообразна. Студенты активно совмещают учебную деятельность с занятиями спортом, участием в культурно-массовых мероприятиях, а также их организации. Администрация института всячески поддерживает инициативу и заботится о благополучии студентов. Так, ведется непрерывная работа по расширению студенческого городка и улучшению быта студентов.

Адрес e-mail:

Методический семинар кафедры Математических основ управления ФУПМ. Заседание 22 марта с 18.30 в 113 ГК.

опубликовано: 22.03.2011
Стохастический анализ в задачах
Занятия далее также будут проходить по вторникам в 18.30 в 113 ГК.
Приглашаются все желающие (в особенности студенты ФУПМ 3-го (874-876 группы) и 4-го курса).

Е.О. Ежова (60 мин.)
1) Коммуникационные протоколы. Алисе и Бобу сообщаются двоичные слова x, y длины n (каждому свое слово). В результате обмена информации они должны вычислить F(x,y). (Ответ в конце должны знать оба участника). Цель - сделать это оптимальным способом (передать как можно меньше бит информации).Все зависит от целевой функции F. Ясно, что для любой F, имеющей множество значений {0,1}, для вычисления протокола достаточно передать по каналу связи n+1 бит информации (Алиса передает Бобу свое слово x - n бит; Боб вычисляет F(x,y), результат передает Алисе - еще один бит). Для вычисления большинства коммуникационных протоколов оказывается необходимо передать O(n) бит информации. Однако если разрешить участникам протокола иногда ошибаться (с не большой вероятностью), то можно значительно сократить число передаваемых бит (например, до O(logn)). Такие протоколы назывются вероятностыми - каждый участник имеет доступ некоторому источнику случайности. 2) Криптографические протоколы. Задача обмена информации между участниками протокола усложняется, если при этом требуется обеспечить надежность передаваемой информации, гарантировать, чтобы информация не была "перехвачена противником". Более того, убедиться, что партнер именно тот, за кого себя выдает, а также гарантировать, что партнер не обманет (не откажется от своей подписи, или не откажется подписать контракт после того, как получит вашу подпись). Будут приведены некоторые криптографичесие протоколы (использующие "подбрасывание монетки"), решающие эти задачи, на примере организации электронной жеребьевки (можно обобщить на виртуальное казино), электронного голосования, протокола аутентификации, электронно-цифровой подписи.

Литература
1. http://reslib.com/book/Prikladnaya_kriptografiya__Protokoli__algoritmi_i_ishodnie_teksti_na_yazike_S

А.В. Гасников (30 мин.)
Парадоксы и контрпримеры в теории вероятностей
Много удивительных и неожиданных наблюдений можно сделать уже в простейшей схеме бросания монеты (схема Бернулли).
Например, в случайной последовательности нулей единиц (длины n) с вероятностью близкой к 1 найдется подпоследовательность из ~ log n подряд идущих единиц.
Другой пример (из книги А. Шеня). Давайте сыграем в такую игру: вы называете одну из восьми комбинаций
001, 010, 010, 011, 100, 101, 110, 111, я называю другую, потом мы бросаем
монету до тех пор, пока в последовательности нулей и единиц (результаты
бросаний) не появится одна из двух наших комбинаций. Тот, чья комбинация
появится, выиграл. (Заметим, что некоторые комбинации тре-
буют в среднем меньшего числа бросаний, чем другие, но первый игрок
может выбрать любую - так в чём же подвох?)
Тем не менее игра нечестная, и даже удивительно, насколько нечестная:
шансы второго игрока в ней по крайней мере вдвое выше. Дело в том, что
он выбирает свою комбинацию, уже зная комбинацию первого, и может вы-
брать её так, чтобы она появилась раньше с вероятностью по крайней мере
2/3. Например, если вы выберете 010, то я могу назвать 001 и выиграю с
вероятностью 2/3.

Литература
1. Стоянов Й. Контрпримеры в теории вероятностей. М.: Факториал, 1999.
2. Секей Г. Парадоксы в теории вероятностей и математической статистике. Москва – Ижевск, РХД, 2002.
3. Шень А. Вероятность: примеры и задачи. М.: МЦНМО, 2007. http://www.mccme.ru/free-books/shen/shen-probability.pdf
4. Феллер В. Введение в теорию вероятностей и ее приложения Т. 1, 2. М.: УРСС, 2010.
5. Задач из Колмогоровских студентческих олимпиад по теории вероятностей: http://mech.math.msu.su/probab/
Если вы заметили в тексте ошибку, выделите её и нажмите Ctrl+Enter.

© 2001-2016 Московский физико-технический институт
(государственный университет)

Техподдержка сайта

МФТИ в социальных сетях

soc-vk soc-fb soc-tw soc-li soc-li
Яндекс.Метрика