Войти
Логин:
Пароль:
Забыли пароль?
научная деятельность
структура институтаобразовательные проектыпериодические изданиясотрудники институтапресс-центрконтакты
русский | english
Образовательные проекты ИППИ >> Кафедра проблем передачи информации и ан... >> Первое знакомство с ИППИ РАН: задачи для...

Первое знакомство с ИППИ РАН: задачи для студентов

Данные задачи предназначены для тех студентов МФТИ или ВШЭ, кто думает о научной работе в ИППИ РАН и хотел бы найти себе научного руководителя и тему. Задачи рассчитаны в основном на уровень студентов бакалавриата, но многие из них могут быть интересны и магистрантам.

Каждая из задач — это только повод познакомиться с тем сотрудником, который ее предложил: совсем не планируется, что вы решите ее целиком прежде, чем первый раз встретитесь с предполагаемым научным руководителем. Подумайте о задаче, поищите в Сети или в литературе информацию об использованных при ее формулировке понятиях, о возможных подходах и методах ее решения, сделайте первые наметки решения и после этого свяжитесь с автором задачи (по электронным адресам, указанным на его или ее персональной странице) и расскажите о том, что вам удалось сделать. 

Задачи от Лаборатории зрительных систем

АФАНАСЬЕВ Валентин Борисович

  1. Выразить энтропию источника с экспоненциальным, биномиальным, нормальным и т.п.  распределениями вероятностей через параметры распределения.
  2. Запрограммировать алгоритмы сжатия Хаффмена и Шеннона, сравнить теоретические предсказания их эффективности с экспериментом.
  3. Запрограммировать и продемонстрировать арифметику конечного поля, запрограммировать алгоритм деления многочленов с остатком и без остатка над конечным полем. Построить таблицу логарифмов конечного поля.
  4. Построить реализацию случайного процесса с независимыми приращениями.
  5. Построить реализацию простой марковской цепи.

В документе, который можно скачать по следующей ссылке, даны некоторые задачи, который в том или ином виде часто возникают в анализе данных. Непосредственно каждой из задач предшествует введение, которое в крайне сжатой форме описывает, зачем эту задачу необходимо решать. Предполагается, что на собеседовании это введение будет воспроизведено в достаточном для понимания комиссией варианте и затем описан способ решения поставленной задачи. Вопросы составителю задач могут быть заданы по электронной почте.

БУРНАЕВ Евгений Владимирович

В документе, расположенном по ссылке, приведены некоторые задачи анализа данных и машинного обучения. Среди задач есть как практические задачи, в которых надо для конкретных данных применить тот или иной метод машинного обучения и интерпретировать полученные результаты расчетов, так и более теоретические задачи, в которых надо вывести формулу, доказать утверждение. Так как на втором курсе МФТИ студенты еще не имеют всех необходимых знаний, то в документе приведена литература, в которой можно найти всё необходимое для решения. Авторы отдают себе отчет в том, что задачи могут показаться трудными, однако, не надо пасовать - на самом деле это достаточно стандартные вопросы, на которые вы сможете легко отвечать после обучения на кафедре. Более того, от вас не ждут, что на собеседовании вы сможете рассказать решение полностью. Вопросы составителям можно присылать на почту: burnaevevgeny@gmail.com и likzet@gmail.com

ВЛАДИМИРОВ Александр Александрович

  1. Есть длинная нитка с нанизанными бусинками двух цветов, в случайном порядке. Нужно разложить ее на столе без пересечений (это важно!) так, чтобы некоторые пары бусинок соприкоснулись. Соприкасаться разрешается только бусинкам одного цвета. Какое максимальное число таких пар можно получить? Тот же вопрос для трех, четырех и т.д. цветов. Задача связана со вторичной структурой молекул РНК (см. А. А. Владимиров, «Паросочетания без пересечений», Пробл. передачи информ.49:1 (2013), 61–65).
  2. Есть сеть из нескольких «серверов». Извне приходят «клиенты», разные: у каждого свой маршрут. Возникают очереди на серверах, которые обслуживаются, например, в порядке поступления (или еще как-то). Есть две важных характеристики: пропускная способность сети (максимальная интенсивность внешнего потока, при которой сеть с ним еще справляется) и среднее время ожидания в очередях для клиентов. Что произойдет с этими величинами, если мы дублируем каждый сервер, а внешний поток тоже удвоим? (См., напр., А. А. Владимиров, А. Н. Рыбко, С. Б. Шлосман, «Свойство самоусреднения систем массового обслуживания», Пробл. передачи информ., 42:4 (2006), 91–103.) Предполагается как теоретический анализ, так и вычислительный эксперимент.

ВЬЮГИН Владимир Вячеславович

  1. Построить вероятностный аналог алгоритма WMA, вычислить его регрет. Сравнить предсказательные способности (регрет) алгоритма WMA и алгоритма оптимального распределения потерь (для случая 0/1-потерь).
  2. Оценить предсказательные способности агрегирующего алгоритма в случае 0/1 потерь. Сравнить оценку регрета этого алгоритма с оценкой Литлстоуна и Вармута для алгоритма WMA.
  3. Применить алгоритм следования за возмущенным лидером к задаче нахождения оптимального пути на графе (см. статью A. Kalai, S. Vempala).
  4. Применить алгоритмы предсказания с использованием экспертных стратегий для решения задачи оптимальной сортировки объектов (при различных предположениях).
  5. Реализовать агрегирующий алгоритм и его варианты для различных функций потерь и наборов экспертов. Оценить предсказательные способности агрегирующего алгоритма в случае абсолютной и др. функций потерь
  6. Алгоритмы построения оптимального портфеля в условиях стационарного процесса цен (Cover и др.).

Литература (все указанные источники можно получить у В.В. Вьюгина по электронной почте или найти в Сети):

  1. Вьюгин В.В. Математические основы машинного обучения и прогнозирования, Москва, Изд. МЦНМО, 2013. В этой книге имеется много простых и сложных задач, а также лабораторные работы, связанные с написанием программ и проведением численных экспериментов).
  2. N. Littlestone, M. Warmuth. The weighted majority algorithm // Information and Computation -- 1994 -- V. 108 -- P. 212--261.
  3. A. Kalai, S. Vempala. Efficient algorithms for online decisions. In Bernhard Scholkopf, Manfred K. Warmuth, editors, Proceedings of the 16th Annual Conference on Learning Theory COLT 2003, Lecture Notes in Computer Science 2777, pages 506--521, Springer-Verlag, Berlin, 2003. Extended version in Journal of Computer and System Sciences, 71:291--307, 2005.
  4. V. Vovk. Competitive on-line statistics. International Statistical Review -- 2001 -- V. 69. -- P. 213--248.
  5. V. Vovk, C. Watkins. Universal portfolio selection // Proceedings of the 11th Annual Conference on Computational Learning Theory -- New York: ACM Press, 1998. -- P. 12--23.
  6. V. Vovk. A game of prediction with expert advice // Journal of Computer and System Sciences -- 1998 -- V. 56. -- No. 2.  P. 153--173.
  7. Vladimir V"yugin, Universal Algorithm for Trading in Stock Market Based on the Method of Calibration // Lecture Notes in Artificial Intelligence V.8139, P.41--55, 2013.
  8. V. V’yugin, V. Trunov, Universal algorithmic trading // Journal of Investment Strategies Volume 2/Number 1, Winter 2012/13 P.63–88.
  9. Vladimir V. V"yugin. Online Learning in Case of Unbounded Losses Using Follow the Perturbed Leader Algorithm // Journal of Machine Learning Research, 12(Jan):241-266, 2011.

10. M. Hutter, J. Poland. Adaptive online prediction by following the perturbed leader // Journal of Machine Learning Research, 6:639--660, 2005.

11. T. Cover, E. Ordentlich. Universal portfolio with side information // IEEE Transaction on Information Theory -- 1996. --V. 42. -- P. 348--363.

12. M. Anthony M, P.L. Bartlett. Neural network learning: Theoretical foundations, Cambridge: Cambridge University Press, 1999.

ГАСНИКОВ Александр Владимирович

  1. Многорукие бандиты. Имеется два «одноруких бандита» (так называют игровые автоматы с ручкой, дергая за которую получаем случайный выигрыш). Вероятность выиграть 1 франк на первом автомате p1 > 0 (с вероятностью 1 -&nsbp;p1 выигрыш равен 0), а на втором — p2 > 0. Обе вероятности неизвестны. Игрок может в любом порядке раз дергать за ручки «одноруких бандитов». Стратегией игрока является выбор ручки на каждом шаге, в зависимости от результатов всех предыдущих шагов, так чтобы суммарный выигрыш был бы максимальным. Приведите стратегию игрока. Предложите свое обобщение задачи. (Литература: Bubeck S., Cesa-Bianchi N. Regret analysis of stochastic and nonstochastic multi-armed bandit problems, Foundation and Trends in Machine Learning, 5:1 (2012) 1–122; Lugosi G., Cesa-Bianchi N. Prediction, learning and games. New York: Cambridge University Press, 2006.)
  2. Оптимальная оценка в нерегулярном случае. В некотором вузе проходит экзамен. Количество экзаменационных билетов N > 1. Перед экзаменационной аудиторией выстроилась очередь из студентов, которые не знают чему равно N. Согласно этой очереди студенты вызываются на экзамен (второй студент заходит в аудиторию, после того как из нее выйдет первый, и т.д.). Каждый студент с равной вероятностью может выбрать любой из N билетов (вне зависимости от других студентов). Проэкзаменованные студенты, выходя из аудитории, сообщают оставшейся очереди номера своих билетов. Оцените сверху, сколько студентов должно быть проэкзаменовано, чтобы оставшаяся к этому моменту очередь смогла оценить число экзаменационных билетов с точностью 10% с вероятностью, не меньшей 0,95.

КАРАСЕВ Роман Николаевич

Пусть в R3 дана гауссова мера с плотностью, например, exp(-πx2). Известно (см. список литературы), что если мы рассматриваем три центрально-симметричные полоски (полоска – область, заключённая между парой параллельных плоскостей) с заданными ширинами abc, то их пересечение имеет минимальную гауссову меру тогда, когда они попарно перпендикулярны.

Вопрос   а когда объединение трёх центрально-симметричных полосок имеет максимальную гауссову меру? Когда они попарно перпендикулярны или когда они параллельны одной и той же прямой? Или в другом случае? Может быть ответ зависит от набора их ширин?

Литература

  1. Z. Sidák. Rectangular confidence regions for the means of multivariate normal distributions. Journal of the American Statistical Association, 62:318 (1967), 626--633.

В некоторых протоколах беспроводных сетей решение о том, являются ли два узда соседними или нет, принимается по последовательности принятых/потерянных сообщений. Следующие задачи навеяны как раз исследованием и оптимизацией таких протоколов.

1. У испытателя Глюка имеется несимметричная монета, при подбрасывании которой с вероятностью p выпадает "орел", а с вероятностью 1-p "решка". Глюк начинает подбрасывать монету до тех пор, пока впервые не выпадет "решка". Какое среднее число подбрасываний должен совершить испытатель Глюк?

2. Испытатель Глюк решил усложнить свой эксперимент. Теперь он подбрасывает монету до тех пор, пока "решка" не выпадет k раз подряд (k>1). Какое среднее число подбрасываний придется совершить Глюку на этот раз?

3. Так как эксперимент стал занимать много времени, испытатель Глюк решил изготовить еще одну точно такую же монету и подбрасывать монеты по-очереди, чтобы быстрее добиться успеха. Теперь он подбрасывает монеты поочередно до того момента, пока впервые на одной из монет k раз подряд не выпадет "решка". Какое среднее число подбрасываний совершит испытатель Глюк теперь?

4. Два узла беспроводной сети строго периодически 1 раз в секунду, но в разные моменты времени, выбранные независимо друг от друга, отправляют друг другу пакеты. Узел принимает решение, что соединение с другим узлом хорошее, и другой узел является соседним после того, как примет от него K пакетов подряд. Узел принимает решение о плохом соединении и перестает считать другой узел соседний после того, как L пакетов подряд будут потеряны. Какую долю времени оба узла будут одновременно считать друг друга соседями, и какова средняя продолжительность интервала, в течение которого узлы непрерывно считают друг друга соседями, если каждый пакет доставляется успешно с вероятностью p, а с вероятностью 1-p теряется?
 
КУРМУКОВ Анвар Илдарович
 
Метод к-средних - один из первых методов решения задачи кластеризации был предложен более 50 лет назад и до сих пор остается одним из самых популярных и часто используемых в самых разных областях науки. Несмотря на свою популярность метод к-средних имеет ряд недостатков: 1) Зависимость итогового решения от начальной инициализации 2) Отсутствие гарантий на сходимость к глобальному минимуму 3) Необходимость вручную задавать число кластеров.
В работе "k-means++:  The Advantages of Careful Seeding" by David Arthur and Sergei Vassilvitskii предлагается подход к инициализации начальных центров, позволяющий получить гарантии на качество итоговой кластеризации (2), и на практике улучшающий время сходимости алгоритма.
 
Задачи:
  1. Предлагается разобрать оригинальную работу и доказательство основной теоремы
  2. Предлагается реализовать алгоритм k-means и метод инициализации предложенный авторами, и сравнить время его работы и качество кластеризации в смысле суммарного квадратичного отклонения со случайной инициализацией

По данной ссылке представлены задачи по теории информации и теории кодирования

СОРОКИН Виктор Николаевич

  1. Колебания голосовых складок происходят в результате взаимодействия сил, создаваемых перепадом давления в легких и речевом тракте, сил упругих деформаций складок и аэродинамических сил воздушного потока в голосовой щели. Форма голосовых складок может быть описана через собственные функции упругих деформаций во всех трех измерениях, а скорость потока — одномерным нелинейным уравнением (Сорокин В.Н. Теория речеобразования, 1985, Радио и Связь). Написать систему уравнений, описывающих движения голосовых складок, определить условия стабильности автоколебаний. Написать программу для численного решения этой системы для симметричных и несимметричных геометрических и физиологических параметров голосовых складок.
  2. Резонансные частоты речевого тракта используются при распознавании речи и распознавании диктора. Задача определения этих частот по речевому сигналу некорректна, она не имеет ни единственного, ни устойчивого решения. Поэтому до сих пор не создано алгоритма, успешно решающего эту задачу. Известно несколько подходов к определению резонансных частот речевого тракта. Эти частоты могут отождествляться с частотами локальных пиков амплитудного спектра речевого сигнала, полюсами передаточной функции речевого тракта, мгновенной частотой пересечения нуля в различных частотных полосах. Предложите способ объединения результатов анализа различными методами, используя как мгновенные оценки резонансных частот, так и траектории их изменения на некотором интервале времени, а также статистику этих частот для данного диктора или множества дикторов.

ТАЛИС Вера Леонидовна

  1. Ходьба человека –циклическое движение нижних конечностей, взаимодействие которых в ряде статей принято описывать методом анализа главных компонент (Principal Component Analysis, PCA), разработанным для описания позы  (Alexandrov A., Frolov A., Massion J. Axial synergies during human upper trunk bending. Exp Brain Res 118:2 (1998) 210-220) и успешно переложенным для описания человеческой ходьбы (Borghese N.A., Bianchi L., Lacquaniti F. Kinematic determinants of human locomotion. J. Physiol. 494 (1996) 863-879). В некоторых специальных условиях утверждается возможность нарушения естественной синфазности движения суставов, обнаруживаемые методом РСА (Ivanenko Y.P., Grasso R., Lacquanity F. Influence of leg muscle vibration on human walking. J. Neurophysiol. 84:4 (2000) 1737-1747; Ivanenko Y.P., Grasso R., Macellari V., Lacquanity F. Control of foot trajectory in human locomotion: role of ground contact forces in simulated reduced gravity. J. Neurophysiol. 87:6 (2002) 3070-3089). Так ли это? Возможно ли до такой степени нарушить ходьбу? А если это возможно, может быть ходьба в этих специальных условиях уже не ходьба? И что считать ходьбой здорового человека?

ЯРОЦКИЙ Дмитрий Александрович

Рассмотрим квадратный лабиринт размера n × n, понимая под ним сетку из ячеек, у каждой из которых некоторые из 4 стенок открыты, а остальные закрыты. Нас будет интересовать такая задача: для заданных двух ячеек A и B определить, существует ли проход от A до B. Будем считать, что проход предъявлять не нужно, предполагается лишь ответ в форме «да/нет».

Такую задачу можно решить простым последовательным алгоритмом обхода всех ячеек, соединенных с данной, однако он может потребовать O(n2) шагов (если путь заполняет почти весь лабиринт). Вопрос: можно ли решить эту задачу быстрее, например за O(n) или даже o(n) шагов, с помощью клеточного автомата (т. е. параллельных вычислителей, локализованных в ячейках сетки и общающихся с ближайшими соседями)?

Решение с помощью клеточного автомата (КА) подразумевает три составные части:

  • инициализация КА: предварительное отображение ячеек лабиринта в начальные состояния вычислителей на основании информации о связях ячейки с ближайшими соседями и принадлежности к ячейкам A, B;
  • собственно правила итерации КА, т.е. закон изменения состояний вычислителей в зависимости от собственных состояний и состояний ближайших соседей (одновременное однократное изменение состояний всех вычислителей считается за один шаг алгоритма);
  • условия принятия окончательного решения о наличии/отсутствии прохода между A и B — можно считать, что решение принимается, когда либо все вычислители (конъюнктивный вариант), либо хотя бы один (дизъюнктивный вариант) переходят в некоторые выделенные состояния.
 
 
Дешифровка древнерусской тайнописи

В Государственной Третьяковской галерее под инвентарным номером 28747 хранится икона Николая Чудотворца с житием, происходящая из Введенской церкви в Ростове Великом и датируемая концом XIV – началом XV веков. Икона эта необычна тем, что ее средник (основная, средняя часть, где изображен святой) обрамлен светлой полосой, заполненной буквообразными знаками. Возможно, это просто орнамент, стилизованный под буквы. Но нельзя также исключить, что это – не расшифрованная до сих пор криптограмма. Известны случаи, когда древнерусские книжники прибегали к тайнописи – для обеспечения секретности, по религиозным соображениям и просто ради забавы. Предполагаемую шифровку с иконы Николая Чудотворца пытались разгадать несколько раз. Первым было высказано предположение, что знаки шифровки – это знаки зырянской азбуки. Согласно второй гипотезе, перед нами запись, предназначенная для пения – так называемая кондакарная. Однако обе гипотезы не вполне доказательны. Дешифровка, опирающаяся на методы частотного анализа, также удовлетворительного результата пока не дала. Так есть ли тут текст и можно ли его расшифровать?

Икона Николая Чудотворца

 

Таблица знаков криптограммы

 

Рассказ Алексея Алексеевича Гиппиуса о попытке расшифровать криптограмму с иконы Николы

 

Материалы Алексея Алексеевича Гиппиуса в помощь

 

Дополнительные материалы

Описание иконы и библиография вопроса 

«Кондакарная» гипотеза

Удачный опыт расшифровки тайнописи книжника Серапиона

 

НОВОСТИ И ОБЪЯВЛЕНИЯ
Собеседование на Кафедру проблем передачи информации и анализа данных (ИППИ РАН) для студентов второ...
ВНИМАНИЮ СТУДЕНТОВ! Обновлены программы курсов Кафедры проблем передачи информации и анализа данных ...
ВНИМАНИЮ СТУДЕНТОВ! Обновлено расписание занятий на весну 2015 в аудиториях ИППИ РАН в Большом Карет...
Вторая часть курса лекций "Введение в Квантовую теорию поля" проф. Александра Белавина в...
Изменения в расписании базовых кафедр...
Обновлено расписание занятий базовых кафедр МФТИ в ИППИ РАН, весенний...
15 марта в 17 часов в 115 кпм для студентов базовой кафедры состоится...
Все новости   
 

 

  © Федеральное государственное бюджетное учреждение науки
Институт проблем передачи информации им. А.А. Харкевича Российской академии наук, 2018
Об институте  |  Контакты  |  Старая версия сайта