Мы используем файлы cookies для улучшения работы сайта НИУ ВШЭ и большего удобства его использования. Более подробную информацию об использовании файлов cookies можно найти здесь, наши правила обработки персональных данных – здесь. Продолжая пользоваться сайтом, вы подтверждаете, что были проинформированы об использовании файлов cookies сайтом НИУ ВШЭ и согласны с нашими правилами обработки персональных данных. Вы можете отключить файлы cookies в настройках Вашего браузера.
Кафедра технологий моделирования сложных систем создана в 2011 г. на базе Института проблем передачи информации им. А.А. Харкевича РАН — признанного мирового центра исследований по фундаментальным основам информационных технологий.
Направлением специализации кафедры являются методы метамоделирования и предсказательного моделирования, опирающиеся на такие области математики, как теория аппроксимации, машинное обучение, теория оптимизации, математическая статистика и теория информации.
Шишкин С. В., Шейман И. М., Власов В. В. и др.
М.: Национальный исследовательский университет "Высшая школа экономики", 2022.
Rostislav Berezovskiy, Урусов А. М., Yanovich Y.
Blockchain: Research and Applications. 2024.
Mangold P., Samsonov S., Labbi S. et al.
In bk.: 38th Conference on Neural Information Processing Systems (NeurIPS 2024). 2024. Ch. 37. P. 13927-13981.
Sheshukova M., Belomestny D., Durmus A. et al.
math. arXiv. Cornell University, 2024
На этой странице в качестве справочной информации приведены темы курсовых и дипломных работ, выполнявшихся под руководством сотрудников ИППИ РАН в предыдущие годы. Темы текущего учебного года представлены по ссылке.
Темы курсовых и дипломных работ существенно меняются и пересматриваются в начале каждого учебного года. Приведенные ниже темы мы предлагали студентам магистерской программы “Науки о данных” в 2016-2017 учебном году. В большинстве случаев похожие темы существовали и для студентов бакалавриата, разница заключалась в конкретной постановке задачи и ожидаемой глубине ее проработки.
Кроме того, студенты кафедры выполняют курсовые и дипломные работы под руководством сотрудников ИППИ РАН, формально не связанных с кафедрой. В этом случае, по правилам Вышки, назначается научный консультант из числа сотрудников НИУ ВШЭ.
Темы, которые мы предлагали для курсовых и дипломных работ в предыдущие годы, можно посмотреть по ссылке.
Нерастягивающие отображения — это отображения, которые не увеличивают расстояния между точками. Теорема Киршбрауна утверждает, что любое нерастягивающее отображение подмножества из евклидового пространства в себя может быть продолжено на всё евклидово пространство. Если же изначально отображение задано на конечном числе точек, то существует очень простой и наглядый алгоритм построения такого продолжения, и результатом работы алгоритма будет всего лишь разбиение пространства на многогранники. В случае плоскости — это будет разбиение на многоугольники, которое можно воспринимать, как узор оригами. Предлагается написать программу, реализующую этот алгоритм и визуализирующую его результат.
Литература:
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. Построить программную реализацию простой марковской цепи.
Поток машин на однополосном шоссе можно представить как коллективное случайное блуждание набора частиц с условием отсутствия обгонов. В теории случайных процессов этому соответствует так называемый «totally asymmetric exclusion process», рассматриваемый как в непрерывном, так и в дискретном времени. В настоящее время ряд результатов в этой области получен аналитически (т. е. с точными математическими доказательствами), однако большинство наблюдений связано с численным моделированием. Имеется целый ряд важных открытых вопросов, нуждающихся как в численном моделировании, так и в аналитическом решении. Перечислю лишь несколько из них:
Литература:
1. Liggett T.M. Interacting Particle Systems. Springer, 2005.
2. Введение в математическое моделирование транспортных потоков: учеб. пособие / Гасников А.В., Кленов С.Л., Нурминский Е.А., Холодов Я.А., Шамрай Н.Б; Приложения: Бланк М.Л., Гасникова Е.В., Замятин А.А., Малышев В.А., Колесников А.В., Райгородский А.М; Под ред. А.В. Гасникова - М.: МФТИ, 2010. - 385 с.
3. Blank M. Metric properties of discrete time exclusion type processes in continuum. J. Stat. Phys. 140:1 (2010) 170-197. (arXiv:0904.4585).
4. Blank M. Exclusion type spatially heterogeneous processes in continuum. J. Stat. Mech. (2011) P06016 (arXiv:1105.4232v1).
Мы рассматриваем модели систем обслуживания, в которых несколько потоков заявок поступают на серверы (приборы), каждая заявка обслуживается одним из серверов и покидает систему. В математической модели задается характер входных потоков (распределение длин интервалов времени между приходами заявок), характер обслуживания (распределение длин обслуживания заявки), правила рассылки заявок на приборы. Предполагается, что система не перегружена, т. е. заявки обслуживаются за конечное время (математическое ожидание времени обслуживания конечно). Задачи, которые мы рассматриваем тесно связаны с теорией очередей. (Английские термины — network, queueing theory, dynamic routing).
Нас интересуют модели систем, в которых прибор, на который направляется заявка, выбирается с учетом того в каком состоянии находится система.
Пусть система состоит из k серверов, на которую поступает l независимых пуассоновских потоков. Сообщения из каждого потока направляются на один из m серверов, причем каждое сообщение направляется на тот из серверов, где в момент его прихода меньше нагрузка. Каждый сервер может обслуживать несколько потоков. Вопрос: какова вероятность того, что некоторые серверы оказываются очень сильно нагружены (перегружены)? Оказывается, что в такой системе конфигурация перегруженных серверов зависит от интенсивности входных потоков: при условии перегруженности m серверов и при небольшой интенсивности входных потоков остальные серверы вероятнее всего не перегружаются, а при интенсивности входных потоков близкой к критической вероятнее всего все серверы оказываются перегруженными.
Интересно проследить, какова вероятность «небольших» перегрузок. На этот счет есть некоторые предположения. Предлагается получить распределение величин таких перегрузок с помощью моделирования (симулирования) работы системы.
Литература:
1. Введенская Н.Д., Печерский Е.А. Кольцо взаимодействующих серверов: спонтанное возникновение коллективного поведения при больших флуктуациях. Пробл. передачи информ. 44:4 (2008) 101-117.
2. Введенская Н.Д. Конфигурация перегруженных серверов при динамической маршрутизации. Пробл. передачи информ. 47:3 (2011) 80-95.
Есть сеть из нескольких «серверов». Извне приходят «клиенты», разные: у каждого свой маршрут. Возникают очереди на серверах, которые обслуживаются, например, в порядке поступления (или еще как-то). Есть две важных характеристики: пропускная способность сети (максимальная интенсивность внешнего потока, при которой сеть с ним еще справляется) и среднее время ожидания в очередях для клиентов. Что произойдет с этими величинами, если мы дублируем каждый сервер, а внешний поток тоже удвоим? Предполагается как теоретический анализ, так и вычислительный эксперимент.
Литература:
1. А. А. Владимиров, А. Н. Рыбко, С. Б. Шлосман, «Свойство самоусреднения систем массового обслуживания», Пробл. передачи информ., 42:4 (2006), 91–103.
Есть длинная нитка с нанизанными бусинками двух цветов, в случайном порядке. Нужно разложить ее на столе без пересечений (это важно!) так, чтобы некоторые пары бусинок соприкоснулись. Соприкасаться разрешается только бусинкам одного цвета. Какое максимальное число таких пар можно получить? Тот же вопрос для трех, четырех и т.д. цветов. Задача связана со вторичной структурой молекул РНК.
Литература:
1. А. А. Владимиров, Паросочетания без пересечений, Пробл. передачи информ., 49:1 (2013), 61–65).
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 J. Computer System Sci., 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 // J. Computer and System Sci. -- 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 // J. 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 // J. Machine Learning Res., 12(Jan):241-266, 2011.
10. M. Hutter, J. Poland. Adaptive online prediction by following the perturbed leader // J. Machine Learning Res., 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, 2] для полностью автоматического решения некоторых задач обработки изображений, связанных с выделением и детекцией объектов определенной формы. В основе алгоритма лежит глауберова динамика рождения-гибели в непрерывной среде, а также более общие стохастические динамики маркированных точечных полей.
Литература:
1. Descombes X., Zhizhina E., The Gibbs fields approach and relateddynamics in image processing. Condensed Matter Physics 11:2 (2008) 1-20.
2. Descombes X., Minlos R.A., Zhizhina E., Object extraction usingstochastic birth-and-death dynamics in continuum. J. Math. Imaging Vision 33:3 (2009) 347.
Представим себе, что мы наблюдаем неизвестную нам последовательность символов (из некоторого конечного алфавита) через «окошко» размера k, а окошко это мутновато – т. е. часть символов мы не видим совсем, или, что еще хуже, воспринимаем их ошибочно. Нам разрешается двигать этим «окошком» вдоль последовательности как нам захочется. Сколько минимально понадобится наблюдений, чтобы восстановить последовательность?
Литература:
1. V.I. Levenshtein, Efficient reconstruction of sequences. IEEE Trans. Inform. Theory 47:1 (2001) 2-22.
2. V.I. Levenshtein, Efficient reconstruction of sequences from their subsequences or supersequences. J. Combin. Theory. Ser. A 93:2 (2001) 310-332.
Описание формы объекта является фундаментальной задачей в теории обработки изображений. В [1] построена математическая модель, в которой вводится дескриптор формы, основанный на изучении объема границы объекта. Кроме того, в этой работе получено соответствие между формой и функциями на отрезке, работать с которыми значительно удобнее.
При некоторых ограничениях на класс множеств (форм) введена метрика на пространстве форм, которая позволяет решать проблему нахождения «близких» форм в некотором массиве данных. Релевантность модели подтверждается численными результатами.
Возможными задачами для дальнейшего изучения в рамках данной модели являются:
Литература:
1. Xavier Descombes, Sergey Komech. Shape Descriptor Based on the Volume of Transformed Image Boundary. PReMI'2011, Springer-Verlag LNCS series, pp. 142-147
Если пикселы заданного цветного изображения представить в координатах HSL (тон, насыщенность, светлота) и отбросить информацию о насыщенности и светлоте пикселов, останется колорит — распределение пикселов по точкам цветового круга, отвечающего параметру L. В работе предлагается разработать алгоритм коррекции колорита изображения по заданному образцу, оптимальной в смысле метрики Вассерштейна. Этот метод применяется, в частности, при цифровом восстановлении цветных фильмов.
Литература:
1. J. Delon, J. Salomon, and A. Sobolevski. Fast transport optimization for monge costs on the circle. SIAM J. Appl. Math., 70(7):2239–2258, 2010. (arXiv:0902.3527).
Литература:
1. Frisch U., Matarrese S., Mohayaee R., Sobolevski A. A reconstruction of the initial conditions of the Universe by optimal mass transportation. Nature 417 (2002) 260-262 (arXiv:astro-ph/0109483)
2. Brenier Y., Frisch U., Hénon M., Loeper G., Matarrese S., Mohayaee R., Sobolevski A. Reconstruction of the early Universe as a convex optimization problem. Mon. Not. R. Astron. Soc. 346:2 (2003) 501-524 (arXiv:astro-ph/0304214)
Литература:
1. Brenier Y. A combinatorial algorithm for the Euler equations of incompressible flows. Computer Methods in Applied Mechanics and Engineering, 75:1-3 (1989) 325-332.
Ходьба человека –циклическое движение нижних конечностей, взаимодействие которых в ряде статей принято описывать методом анализа главных компонент (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). Так ли это? Возможно ли до такой степени нарушить ходьбу? А если это возможно, может быть ходьба в этих специальных условиях уже не ходьба? И что считать ходьбой здорового человека?
В работе необходимо применить итерационные оптимизационные схемы, основанные на методах сжимающих отображений, для оптимизации ("выравнивания") векторных полей на многообразиях. Данная задача является вспомогательной задачей задачи снижения размерности.
В работе необходимо применить градиентные оптимизационные схемы для оптимизации ("выравнивания") векторных полей на многообразиях. Данная задача является вспомогательной задачей задачи снижения размерности.
Многие реальные данные в машинном обучении лежат на или вблизи многообразии меньшей размерности, чем размерность исходных данных. В работе необходимо определить размерности для популярных реальных задач.
В популярных статьях по снижению размерности и оцениванию многообразий неявно используется, но авторами не требуется, свойство геодезической выпуклости рассматриваемых многообразий. В работе необходимо показать, что данное свойство не следует из стандартных предположений авторов и модифицировать результаты на случай геодезически невыпуклых многообразий.