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

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

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

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

АКОПЯН Арсений Владимирович

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

Литература

  1. Brehm U. Extensions of distance reducing mappings to piecewise congruent mappings on Rm. Journal of Geometry, 16:1 (1981) 187-193.
  2. Акопян А. В., Тарасов А. С. Конструктивное доказательство теоремы Киршбрауна. Математические заметки 84:5 (2008) 781-784.

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

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

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

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

Приглашаем студентов, интересующихся научной работой сектора, на сайт компании DATADVANCE (www.datadvance.net), на котором можно найти много примеров прикладных задач из различных отраслей промышленности, при решении которых использованы методы и разработки сектора. Те, кто придет к нам в сектор и компанию будут:

  • создавать процедуры анализа данных и оптимизации;
  • реализовывать их в программном обеспечении;
  • решать реальные инженерные задачи, с примерами которых можно познакомиться на сайте DATADVANCE.

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

  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.

КАБАТЯНСКИЙ Григорий Анатольевич

  1. Как найти фальшивые монеты на точных весах за минимальное число взвешиваний? Известно, что вес фальшивой монеты 9 гр., а настоящей 10 гр. Пусть N — число монет, а взешивания мы планируем заранее («без обучения») — это важно. Легко видеть, что нужно как минимум N/log2 N взвешиваний. Можно доказать, что нужно асимптотически как минимум вдвое больше взвешиваний (это непросто, но попробуйте доказать сами). Удивительно, но есть красивая конструкция взвешиваний, которая в асимптотике это же и дает — т. е. мы знаем ответ хотя бы для асимптотики (для дискретных задач — это большой успех!). Попробуйте придумать этот план взвешиваний сами — это хорошая олимпиадная задача.
  2. Жесткость пространства Хэмминга. Пусть X — некоторое метрическое пространство. Будем называть его подмножество B базой, если любая точка X однозначно определяется ее расстояниями до точек B. Например, X — обычная плоскость, а B — любые три точки, не лежащие на одной прямой. Минимальную мощность базы назовем жесткостью X. По определению N-мерное q-ичное пространство Хэмминга — это множество всех слов длины N в алфавите из q элементов. Расстояние — это число позиций, где два слова различаются. Убедитесь (несложно), что жесткость N-мерного двоичного пространства Хэмминга — это минимальное число взвешиваний (с точностью до ±1). Вопрос — чему равна асимптотика жесткости q-ичного пространства Хэмминга? Гипотеза: 2N/logq N. Умеем доказывать только для q = 3 и q = 4.
  3. Коды для суммирующего канала множественного доступа. Запишем базу B пространства Хэмминга в виде матрицы, где строки — это векторы-точки B. А вот столбцы этой матрицы — это код для суммирующего канала. Почему? Смотри Chang S. C., Wolf J. K., Coding for T-user multiple-access channels, IEEE Trans. Inform. Theory, 25:6 (1979) 684-691. Или пиши kaba@iitp.ru.
  4. Разделяй и …? Будем называть M × n матрицу из элементов -1, 0, +1 3-разделяющей, если для любых трех строк матрицы найдется хотя бы одна из n координат такая, такая что эти три строки в этой координате равны -1, 0, +1 (в любом порядке). Обозначим через M(n) максимально возможное число строк в такой матрице. Как ведет себя M(n): как nd или как dn? Это решить несложно (попробуйте найти ответ сами), а вот значение константы d неизвестно, есть только оценки на нее сверху и снизу. Как это, на первый взгляд, ни странно, но эти две задачи «из одной корзины».

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

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

 

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