Теория автоматов

Название спецкурса на английском языке
Automata theory
Авторы курса
Алешин Станислав Владимирович, Подколзин Александр Сергеевич
Пререквизиты
Отсутствуют
Целевая аудитория
3-6 курс, магистранты
Подразделение
[Кафедра МаТИС]
Семестр
Полгода (весна)
Тип курса
Спецкурс по выбору кафедры
Учебный год
2024/25
Список тем
Абстрактные автоматы
Структурные автоматы
Сложность управляющих систем
Список источников
Теория автоматов : учебник для вузов / В. Б. Кудрявцев, С. В. Алешин, А. С. Подколзин. — 2-е изд., испр. и доп. — Москва : Издательство Юрайт, 2024. — 320 с
Дополнительная информация

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

 

Обязательный для 4 курса кафедры МаТИС.

Ауд 1404

День недели
среда
Время
12:30-14:05
Аудитория
Ещё не назначена
Дата первого занятия
Аудитория первого занятия
Ещё не назначена
Статус курса
Запись открыта
Форма записи на курс
Заполнение формы записи на курс доступно только студентам. Для записи на курс авторизуйтесь, пожалуйста, в студенческом аккаунте.

Физико-математические основы прочности и пластичности

Название спецкурса на английском языке
Physical and mathematical fundamentals of strength and plasticity
Авторы курса
Хвостунков Кирилл Анатольевич
Пререквизиты
Отсутствуют
Целевая аудитория
3-6 курс, магистранты
Подразделение
[Кафедра теории пластичности]
Семестр
Полгода (весна)
Тип курса
Спецкурс по выбору кафедры
Учебный год
2024/25
Список тем
Линейная упругость. Изотропия. Вывод закона Гука на основе одномерного
макроэксперимента
Ковариантность. Соотношение Гамильтона-Кэли. Физически нелинейная изотропная
упругость. Тензорная нелинейность. Девиаторная связь (деформационная теория)
Базовые тензоры. Их линейная независимость. Пример связи трех тензоров.
Однонаправленный композит. Эталонные эксперименты. Полный набор упругих
постоянных
Особенности нелинейной упругости. Отделимость девиаторных составляющих. Потеря
изотропии для соотношения в приращениях
Термодинамика однородных процессов при малых деформациях. Функции и
функционалы внутренних параметров. Законы термодинамики
Неравенство диссипации. Примеры его применения. Упругость. Нелинейная вязкость
КПД тепловой машины. Классические условия на КПД. Следствие для работы
внутренних сил на замкнутом цикле
Содержательность неравенства диссипации для больших деформаций. Проблема выбора обобщенных деформаций и напряжений. Возможность использования тензоров типа Лагранжа. Пара: градиент перемещений и тензор Пиола. Упругий потенциал
Формулировка задачи для больших деформаций в лагранжевых переменных. Уравнение движения с тензором Пиолы. Потенциал связи тензора Пиолы и градиент перемещения для упругости. Краевая задача
Общий энергетический критерий хрупкого разрушения. Его формулировка через
коэффициент интенсивности для трех типов разрушений
Атомная структура. Перемещение атомных стенок. Силы Ван-дер-Ваальса. Модули Юнга и сдвига. Теоретическая и реальная прочность
Энергия разрушения. Трещина и критическое усилие при растяжении. Общий случай
нагружения. Идея о критическом значении коэффициента интенсивности. Основы
линейной механики разрушения
Дефекты кристаллической решетки. Дислокации. Краевые и винтовые дислокации.
Напряженно-деформированное состояние и энергия дислокаций
Взаимодействие дислокаций с полем внешних сил. Общий случай и случай сдвига
Две краевые дислокации. Кольцевая дислокация. Стенка дислокаций. Полоса
скольжения. как источник зарождения микротрещин
Оценка числа дислокаций. Воспроизведение дислокаций. Механизм Франка-Рида. Ширина дислокации. Формула Пауэрса. Интегральные свойства скольжения в монокристалле. Системы скольжения. Предельные напряжения. Гранецентрированная
кубическая решетка
Поликристаллическое тело. Теория скольжения Батдорфа-Будянского. Феноменологические варианты теории скольжения. Сопоставление качественных особенностей теории течения и теории скольжения. Сингулярная пластичность
Геометрическое представление процессов нагружения и деформирования частицы среды. Гипотезы геометрического порядка. Физический смысл постулата изотроnии. Примеры использования геометрических гипотез. Пятичленная формула
Макроэксперимент как основа формирования разрешающей системы уравнений в
континуальной механике. Возможности и ограничения. Принцип макродетерминизма.
Соответствующее ограничение на форму определяющих соотношений в пластичности.
Примеры невыполнения этого принципа и последствия
Список источников
Клюшников В. Д. Физико-математические основы прочности и пластичности. М.: Изд-во МГУ, 1994. 189 с.
День недели
среда
Время
12:30-14:05
Аудитория
450
Аудитория первого занятия
Ещё не назначена
Статус курса
Запись открыта
Форма записи на курс
Заполнение формы записи на курс доступно только студентам. Для записи на курс авторизуйтесь, пожалуйста, в студенческом аккаунте.

Избранные главы теории вероятностей и случайных процессов

Название спецкурса на английском языке
Selected topics of probability theory and theory of stochastic processes
Авторы курса
Козлов Михаил Васильевич, Шкляев Александр Викторович
Пререквизиты
Базовые курсы теории вероятностей, математической статистики, теории случайных процессов, дополнительные главы теории вероятностей.
Целевая аудитория
3-6 курс, магистранты
аспиранты
Подразделение
[Кафедра математической статистики и случайных процессов]
Семестр
Полгода (весна)
Тип курса
Спецкурс по выбору кафедры
Учебный год
2024/25
Список тем
Усиленный закон больших чисел Колмогорова.
Теорема Пуассона. Теорема Ле Кама.
Закон повторного логарифма.
Список источников
Ширяев А. Н. Вероятность. – МЦНМО, 2007.
Боровков А. А. Теория вероятностей. – 1986.
Феллер В. Введение в теорию вероятн
День недели
среда
Время
18:30-20:05
Аудитория
405
Аудитория первого занятия
405

Параметрическая статистика (на английском языке)

Название спецкурса на английском языке
Parametric statistics
Авторы курса
Хиль Елена Викторовна
Пререквизиты
Базовые курсы теории вероятностей и математической статистики
Целевая аудитория
3-6 курс, магистранты
аспиранты
Подразделение
[Кафедра математической статистики и случайных процессов]
Семестр
Полгода (весна)
Тип курса
Спецкурс на английском языке
Учебный год
2024/25
Список тем
Байесовский подход
Последовательный байесовский критерий
Байесовский классификатор
Предельное распределение статистик критерия множителей Лагранжа и критерия Вальда
Список источников
Wasserman L. All of statistics. Springer-Verlag New York, 2004.
Williams D. Weighting the Odds: a Course in Probability and Statistics. Cambridge University
Press, 2001
Berger, James O. Statistical decision theory. Time Series and Statistics. London: Palgrave Macmillan UK, 1990. 277-284
День недели
среда
Время
10:45-12:20
Аудитория
453
Дата первого занятия
Аудитория первого занятия
453

Структурная теория алгебр Ли

Название спецкурса на английском языке
Structural theory of Lie algebras
Авторы курса
Жеглов Александр Борисович
Пререквизиты
Это вторая часть годового курса по группам и алгебрам Ли.
Курс будет доступен студентам, освоившим стандартные предметы на 1-2 курсе, а также первый семестр спецкурса - теорию Ли.
Целевая аудитория
3-6 курс, магистранты
аспиранты
Подразделение
[Кафедра дифференциальной геометрии и приложений]
Семестр
Полгода (весна)
Тип курса
Спецкурс по выбору кафедры
Учебный год
2024/25
Список тем
Нильпотентные и разрешимые алгебры Ли. Теоремы Энгеля и Ли.
Полупростые алгебры Ли. Критерии Картана разрешимости и полупростоты
Теорема Вейля о представлениях полупростых алгебр. Теорема Леви.
Подалгебры Картана.
Список источников
1. Записки лекций первого семестра (по запросу)
2. Винберг, Э.Б., Онищик, А.Л., "Семинар по группам Ли и алгебраическим группам." Наука, М. 1988
3. Ж.-П. Серр, "Алгебры Ли и группы Ли." Мир, Москва, 1969
4. Н. Бурбаки, "Группы и алгебры Ли." Мир, Москва (1978).
День недели
среда
Время
16:45-18:20
Аудитория
407
Дата первого занятия
Аудитория первого занятия
407

Математические основы машинного обучения и прогнозирования

Название спецкурса на английском языке
Artificial intelligence methods in data analysis and program verification
Авторы курса
Миронов Андрей Михайлович
Пререквизиты
Отсутствуют
Целевая аудитория
1-2 курс
3-6 курс, магистранты
Подразделение
[Кафедра МаТИС]
Семестр
Полгода (весна)
Тип курса
Спецкурс по выбору студента
Учебный год
2024/25
Список тем
Задачи и модели машинного обучения.
Линейно разделимые выборки. Алгоритм обучения Розенблатта. Теорема Новикова.
Метод градиентного спуска. Метод стохастического градиента.
Метод обратного распространения ошибки для обучения нейронных сетей.
Метод опорных векторов. Теорема Каруша-Куна-Таккера.
Построение оптимальной разделяющей гиперплоскости по зашумленной выборке.
Ядерный метод машинного обучения.
Алгоритм вычисления калибруемых прогнозов.
Алгоритм взвешенного большинства. Алгоритм оптимального распределения потерь в
режиме онлайн.
Алгоритм экспоненциального взвешивания экспертных решений.
Агрегирующий алгоритм Вовка.
Игры и прогнозы. Антагонистические игры двух игроков. Достаточное условие
существования седловой точки. Смешанные расширения матричных игр.
Игры на универсальные прогнозы. Рандомизированные калибруемые прогнозы.
Теорема Блекуэлла о достижимости
Калибруемые прогнозы и коррелированное равновесие.
Список источников
Миронов А.М., Машинное обучение, часть 1 Москва, МАКС-пресс, 2018, 88 с.
Вьюгин В.В. Математические основы машинного обучения и
прогнозирования. Москва, издательство МЦНМО, 2018 384 с.
Ветров Д.П., Кропотов Д.А. Алгоритмы выбора моделей и построения
коллективных решений в задачах классификации,
основанные на принципе устойчивости. Москва, URSS, 2006 112 с
В. Н. Вапник, А. Я. Червоненкис. Теория распознавания образов.
Статистические проблемы обучения. М., Наука. (1974)
Bishop C. M. Pattern Recognition and Machine Learning. - Springer, Series:
Information Science and Statistics, 2006 - 740 pp.
Murphy Kevin P. Machine Learning: A Probabilistic Perspective. The MIT Press,
2012, 1104 с.
Дополнительная информация

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

 

Ауд 16-10. Первое занятие - 12 февраля.

День недели
среда
Время
15:00-16:35
Аудитория
Ещё не назначена
Дата первого занятия
Аудитория первого занятия
Ещё не назначена

Комбинаторные методы дискретной математики

Название спецкурса на английском языке
Combinatorial methods of discrete mathematics
Авторы курса
Носов Валентин Александрович
Пререквизиты
Отсутствуют
Целевая аудитория
3-6 курс, магистранты
Подразделение
[Кафедра МаТИС]
Семестр
Полгода (весна)
Тип курса
Курс научно-естественного содержания
Учебный год
2024/25
Список тем
Постановка основных математических задач в теории сложности алгоритмов и их значение для обработки экономической информации.
Роль оптимизации и сложности алгоритмов в разработке программных продуктов искусственного интеллекта.
Машины произвольного доступа к памяти, машины Тьюринга и их модификации.
Взаимное моделирование моделей вычислений.
Функции сложности алгоритмов и их свойства.
Существование сложных задач.
Теорема Блюма об ускорении.
Труднорешаемость задач.
Классы P и NP и их свойства.
Полиномиальная сводимость задач.
NP-полные задачи. Теорема Кука о NP-полноте проблемы выполнимости формул алгебры высказываний.
Основные NP-полные задачи.
Задачи с числовыми параметрами. Задача о рюкзаке. Сильная NP-полнота.
Бесконечная серия NP-полных задач Шиффера.
Методы построения быстрых алгоритмов.
Структуры данных.
Рекурсия. Типы полиномиальных оценок сложности рекурсивных алгоритмов.
Рекурсивные алгоритмы для задач сортировки массивов чисел, умножения чисел, умножения матриц, преобразования формул алгебры логики.
Быстрое преобразование Фурье и его применения. Сложность умножения многочленов.
Быстрые алгоритмы на графах. Поиск в глубину и в ширину. Кратчайшие пути. Минимальные остовные деревья. Алгоритмы для задачи о паросочетании.
Потоки в сетях и алгоритмы нахождения максимального потока.
Методы решения труднорешаемых задач.
Метод ограничения параметров.
Метод приближенных алгоритмов. Существование приближенных алгоритмов с различными мерами уклонений от точных алгоритмов.
Доказательства не существования приближенных алгоритмов с некоторыми мерами уклонения.
Политика жадности. Примеры оптимальности жадных алгоритмов. Приближенные алгоритмы для задач об упаковке, о коммивояжере, о вершинном покрытии. Матроиды. Характеризация случаев оптимальности жадных алгоритмов. Теорема Радо- Эдмонса.
Оптимизация алгоритмов перебора.
Минимизация среднего числа опробований с учетом вероятности истинного варианта и сложности его опробования.
Метод согласования координат при переборе.
Методы получения нижних оценок сложности
Нижние оценки сложности в наследственных алгоритмах, использующих отношение частичной упорядоченности. Теорема Дилуорса. Лемма Анселя для единичного куба..
Сложность оптимального алгоритма выделения монотонной функции.
Нижние оценки вычисления на машине Тьюринга. Проблема симметрии слов. Теорема Барздинь и доказательство оптимальности.
Заключение. Основные направления исследований в области оценок сложности алгоритмов. Приложения к проблемам защиты банковской информации и электронной коммерции.
Список источников
Алгоритмы. Построение и анализ: Кормен, Лейзерсон, Ривест, Диалектика, 2020
Дополнительная информация

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

День недели
среда
Время
16:45-18:20
Аудитория
406
Дата первого занятия
Аудитория первого занятия
406

Математические основы термоупругости

Название спецкурса на английском языке
Mathematical foundations of thermoelasticity
Авторы курса
Беднова Вероника Борисовна
Пререквизиты
Отсутствуют
Целевая аудитория
3-6 курс, магистранты
аспиранты
Подразделение
[Кафедра механики композитов]
Семестр
Полгода (весна)
Тип курса
Спецкурс по выбору студента
Учебный год
2024/25
Список тем
Общие замечания и обозначения. Деформации. Напряжения. Уравнения движения. Основные понятия и законы термодинамики. Термодинамические функции. Закон теплопроводности Фурье. Соотношения Дюгамеля-Неймана. Уравнение теплопроводности.
Постановка и классификация связанных задач термоупругости. Случай температурных напряжений. Уравнения термоупругости в цилиндрических и сферических координатах. Материальные константы. Принцип виртуальных работ. Принцип Гамильтона.
Статические задачи, связь между напряженным и деформированным состояниями. Квазистатическая постановка. Теплопроводность, нестационарные задачи теплопроводности. Преобразование Лапласа для решения нестационарных задач теплопроводности.
Теорема о представлении решения связанной задачи для композита через решение такой же задачи для однородного тела.
Список источников
Коваленко А.Д. Основы термоупругости. Киев, Наукова думка, 1970.
Коренев Б.Г. Задачи теории теплопроводности и термоупругости. М., Наука, 1980.
Лыков А.В. Тепломасообмен. Справочник. Энергия, 1978.
Новацкий В. Теория упругости. М., Мир, 1975.
День недели
среда
Время
18:30-20:05
Аудитория
Ещё не назначена
Дата первого занятия
Аудитория первого занятия
Ещё не назначена

Расстояние Громова-Хаусдорфа и алгебраическая топология

Название спецкурса на английском языке
Gromov-Hausdorff distance and algebraic topology
Авторы курса
Иванов Александр Олегович, Тужилин Алексей Августинович
Пререквизиты
Отсутствуют
Целевая аудитория
1-2 курс
3-6 курс, магистранты
аспиранты
Подразделение
[Кафедра дифференциальной геометрии и приложений]
Семестр
Полгода (весна)
Тип курса
Спецкурс по выбору кафедры
Учебный год
2024/25
Список тем
Расстояния Хаусдорфа и Громова–Хаусдорфа
Расстояния до симплексов
Ультраметризация
Фундаментальные группы и расстояния Громова–Хаусдорфа
Симплициальные комплексы и их гомологии
Комплексы Чеха, Вьеториса–Рипса и расстояния Громова–Хаусдорфа
Теоремы типа Борсука–Улама
Расстояния Громова–Хаусдорфа между сферами
Расстояние Громова–Хаусдорфа между окружностью и отрезком

Список источников
[1] Gromov M. Structures m´etriques pour les vari´et´es riemanniennes, edited by Lafontaine and Pierre Pansu, 1981.
[2] Gromov M. Metric structures for Riemannian and non-Riemannian spaces, Birkhдuser (1999). ISBN 0-8176-
3898-9 (translation with additional content).
[3] Бураго Д.Ю., Бураго Ю.Д., Иванов С.В. Курс метрической геометрии. Москва-Ижевск, Институт компьютерных исследований, 2004.
[4] https://en.wikipedia.org/wiki/Von_Neumann\T2A\textendashBernays\T2A\textendashG\T2A\cyrcdel_
set_theory
[5] Ivanov A.O., Tsvetnikov R.A., Tuzhilin A.A. Path Connectivity of Spheres in the Gromov-Hausdorff Class, 2021,
ArXiv e-prints, arXiv:2111.06709 [math.MG].
[6] Ihttp://dfgm.math.msu.su/files/ivanov-tuzhilin/2021-2022/GromovHausdorff.pdf
[7] Tuzhilin A.A. Calculation of Minimum Spanning Tree Edges Lengths using Gromov–Hausdorff Distance, 2016,
ArXiv e-prints, arXiv:1605.01566v1 [math.MG].
[8] Ivanov A.O., Tuzhilin A.A. Geometry of Compact Metric Space in Terms of Gromov-Hausdorff Distances to
Regular Simplexes, 2016, ArXiv e-prints, arXiv:1607.06655v1 [math.MG].
[9] Grigor’ev D.S., Ivanov A.O., Tuzhilin A.A. Gromov–Hausdorff Distance to Simplexes, 2019, ArXiv e-prints,
arXiv:1906.09644v1 [math.MG].
[10] Ivanov A.O., Lychagina E.S., Tuzhilin A.A. Metric Space Recognition by Gromov–Hausdorff Distances to
Simplexes, 2024, ArXiv e-prints, arXiv:2412.18949v1 [math.MG].
[11] Ivanov A.O., Tuzhilin A.A. Geometry of Compact Metric Space in Terms of Gromov–Hausdorff Distances to
Regular Simplexes, 2016, ArXiv e-prints, arXiv:1607.06655v1 [math.MG].
[12] Ivanov A.O., Tuzhilin A.A. The Gromov-Hausdorff Distances between Simplexes and Ultrametric Spaces, 2019,
ArXiv e-prints, arXiv:1907.03828v1 [math.MG].
[13] Ivanov A.O., Tuzhilin A.A. Solution to Generalized Borsuk Problem in Terms of the Gromov-Hausdorff Distances
to Simplexes, 2019, ArXiv e-prints, arXiv:1906.10574v1 [math.MG].
[14] Ivanov A.O., Tuzhilin A.A. The Gromov–Hausdorff Distance between Simplexes and Two-Distance Spaces, 2019,
ArXiv e-prints, arXiv:1907.09942v1 [math.MG].
[15] Лекции по геометрии расстояния Громова–Хаусдорфа, 2021.
[16] Ivanov A.O., Tuzhilin A.A. Gromov–Hausdorff Distance, Irreducible Correspondences, Steiner Problem, and
Minimal Fillings, 2016, ArXiv e-prints, arXiv:1604.06116v1 [math.MG].
[17] Емеличев В.А., Мельников О.И., Сарванов В.И., Тышкевич Р.И., Л екции по теории графов, М.: УРСС,
2019.
[18] Hadwiger H. Uberdeckung einer Menge durch Mengen kleineren Durchmessers ¨ . Commentarii Mathematici
Helvetici, 1945, v. 18, N 1, pp. 73–75.
[19] Hadwiger H. Mitteilung betreffend meine Note: Uberdeckung einer Menge durch Mengen kleineren Durchmessers ¨ .
Commentarii Mathematici Helvetici, 1946, v. 19.
[20] Kahn J., Kalai G. A counterexample to Borsuk’s conjecture. Bull. Amer. Math. Soc., 1993, v. 29, N 1, 60–62.
[21] Райгородский А.М. Вокруг гипотезы Борсука. Геометрия и механика, СМФН, 23, РУДН, М., 2007, 147–164;
Journal of Mathematical Sciences, 2008, v. 154, N 4, 604–623.
[22] Mikhailov I.N. Ultrametric spaces and clouds, ArXiv e-prints, arXiv:2501.19346v1 [math.MG].
[23] Talipov T. Gromov-Hausdorff distance between vertex sets of regular polygons inscribed in a given circle, 2022,
ArXiv e-prints, arXiv:2210.09971v1 [math.MG].
[24] Ivanov A.O., Mikhailov I.N., Tuzhilin A.A. Gromov-Hausdorff Geometry of Metric Trees, 2024, ArXiv e-prints,
arXiv:2412.18888v1 [math.MG].
[25] Adams H., Majhi S., Manin F., Virk Z., Zava N. Lower-bounding the Gromov–Hausdorff distance in metric graphs,
2024, ArXiv e-prints, arXiv:2411.09182.
[26] Adams H., Frick F., Majhi S., McBride N. Hausdorff vs Gromov–Hausdorff distances, 2024, ArXiv e-prints,
arXiv:2309.16648 [math.MG].
[27] Hausmann J.-C.. On the Vietoris–Rips complexes and a cohomology theory for metric spaces. Annals of
Mathematics Studies, 1995, v. 138, pp. 175–188.
[28] Virk Z. Rips complexes as nerves and a functorial Dowker-nerve diagram. Mediterranean Journal of Mathematics,
2021, v. 18, N 2, pp. 1–24.
[29] Munkres J.R. Elements of Algebraic Topology, Westview Press, 1996.
[30] Alexandroff P.S. Uber den allgemeinen Dimensionsbegriff und seine Beziehungen zur elementaren geometrischen ¨
Anschauung. Mathematische Annalen, 1928, v. 98, N 1, pp. 617–635.
[31] Borsuk K. On the imbedding of systems of compacta in simplicial complexes. Fundamenta Mathematicae, 1948,
v. 35, N 1, pp. 217–234.
[32] Hatcher A. Algebraic Topology. Cambridge University Press, Cambridge, 2002.
[33] Hausmann J.C. Mod Two Homology and Cohomology. Universitext. Springer International Publishing, 2015.
[34] Lim S., Memoli F., Smith Z. The Gromov–Hausdorff distance between spheres. Geometry & Topology, 2023, v.
27, N 9, pp. 3733–3800.
[35] Bollobas B. The art of mathematics: Coffee time in Memphis, Cambridge University Press, 2006.
[36] Chowdhury S., Memoli F. Explicit geodesics in Gromov-Hausdorff space, Electronic Research Announcements,
2018, vol. 25, pp. 48–59.
[37] Ivanov A.O., Tuzhilin A.A. Solution to Generalized Borsuk Problem in Terms of the Gromov–Hausdorff Distances
to Simplexes. 2019, ArXiv e-prints, arXiv:1906.10574 [math.MG].
[38] Chazal F., de Silva V., Oudot S. Persistence stability for geometric complexes. Geometriae Dedicata, 2014, v.
174, pp. 193–214.
[39] Люстерник Л.А., Шнирельман Л.Г. Топологические методы в вариационных задачах. М.: Исследовательский институт математики и механики при I МГУ, 1930.
[40] Matou˘sek J. Using the Borsuk-Ulam theorem: lectures on topological methods in combinatorics and geometry,
Springer Science & Business Media, 2003.
[41] Munkholm H.J. A Borsuk-Ulam theorem for maps from a sphere to a compact topological manifold, Illinois Journal
of Mathematics, 1969, vol.13, N 1, pp. 116–124.
[42] Dubins L., Schwarz G. Equidiscontinuity of Borsuk-Ulam functions, Pacific Journal of Mathematics, 1981, vol.
95, N 1, pp. 51–59.
[43] https://math.stackexchange.com/questions/2869360/the-lusternik-schnirelmann-theorem-for-ope
n-and-closed-sets
[44] Freund R.M., Todd M.J. A constructive proof of Tucker’s combinatorial lemma. J. Combinatorial Theory, Ser.
A, 1981, v. 30, pp. 321–325.
[45] Harrison M., Jeffs R.A. Quantitative upper bounds on the Gromov–Hausdorff distance between spheres, 2024,
ArXiv e-prints, arXiv:2309.11237v3 [math.MG].
[46] Martin S.R. Some novel constructions of Gromov-Hausdorff-optimal correspondences between spheres, 2025,
ArXiv e-prints, arXiv:2409.02248v2 [math.MG].
[47] Martin S.R. Gromov-Hausdorff distances from simply connected geodesic spaces to the circle, 2024, ArXiv e-prints,
arXiv:2404.05153v2 [math.MG].
[48] Carlsson G.E., Memoli F. Characterization, stability and convergence of hierarchical clustering methods, J. Mach.
Learn. Res., 2010, vol. 11, pp. 1425–1470.
[49] Ji Y., Tuzhilin A.A. Gromov-Hausdorff Distance Between Segment and Circle, 2021, ArXiv e-prints,
arXiv:2101.05762 [math.MG].
[50] Dunford N., Schwartz J.T. Linear operators, v. 1, Wiley-Interscience (1958).
[51] https://en.wikipedia.org/wiki/Arzel\T2A\cyra\T2A\textendashAscoli_theorem
Дополнительная информация

Желающие присоединиться с слушателям спецкурса, пожалуйста, напишите сначала или 
Александру Олеговичу Иванову, или Алексею Августиновичу Тужилину

----------------------------

Ссылка на наш сайт: http://dfgm.math.msu.su/courses.php?comments=19

----------------------------

Аннотация курса

Знаменитое расстояние Громова-Хаусдорфа измеряет степень неизометричности метрических пространств: у изометричных пространств расстояние равно нулю, и чем более пространства "не похожи" друг на друга, тем это расстояние больше. Задача вычисления расстояния Громова-Хаусдорфа между конечными метрическими пространствами является NP-трудной, и к настоящему времени известно лишь небольшое число конкретных значений. Наиболее хорошо изучен случай пространств с одним ненулевым расстоянием (мы называем такие пространства метрическими симплексами), и здесь хватает геометрических и комбинаторных методов. Однако уже для вычисления расстояния между стандартными сферами разных размерностей такой подход к успеху не приводит. В последние годы были разработаны методы, позволяющие находить расстояния Громова-Хаусдорфа с использованием традиционных инвариантов алгебраической топологии, а именно фундаментальных групп и гомологий. Впрочем, для стягиваемых пространств был предложен оригинальный метод ультраметризации: данное метрическое пространство каноническим образом заменяется на ультраметрическое, а расстояние Громова-Хаусдорфа между исходной парой пространств оценивается снизу расстоянием между полученными ультраметрическими пространствами (верхние оценки обычно получаются из геометрических соображений). Преимущество этого метода состоит в том, что стягиваемое пространство превращается в точку, а, скажем, вершины правильного многоугольника, правильного многогранника или точки кубической решетки – в метрический симплекс.

В наших лекциях мы приведем все определения и предварительные результаты, необходимые для понимания основной части курса. Мы начнем с краткого обзора геометрической теории расстояния Громова-Хаусдорфа, в частности, обсудим известные результаты о расстояниях до симплексов и некоторые приложения этой теории, например, к изучению минимальных остовных деревьев, вычислению хроматических чисел и чисел покрытия графов, решению проблемы Борсука о разбиении ограниченного метрического пространства на части меньшего диаметра.  Затем мы сформулируем и докажем теорему об ультраметризации, а также приведем многочисленные следствия из нее. Далее мы определим фундаментальную группу пунктированного топологического пространства и обсудим, как можно использовать эти группы для вычисления расстояния между окружностью и другими пространствами. Следующим шагом будет изложение основ симплициальной теории гомологий и ее связи с сингулярными гомологиями. Мы покажем, как по подмножеству метрического пространства можно построить классические симплициальные комплексы Чеха и Вьеториса-Рипса, сформулируем и докажем теоремы, которые позволяют оценить снизу расстояние Громова-Хаусдорфа через известные группы гомологий многообразия (поверхности) с использованием этих комплексов. Дальнейшие лекции основаны на теоремах типа Борсука-Улама, которые описывают свойства непрерывных отображений сфер, а также шаров в сферы. Мы расскажем о разных вариантах этих теорем, приведем их подробные доказательства, и применим полученные результаты для оценки и вычисления расстояния Громова-Хаусдорфа. В конце курса мы расскажем о вычислении расстояния Громова-Хаусдорфа между отрезком и окружностью, которое основано на нетривиальных оценках, не использующих методы алгебраической топологии.
 

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

Первая лекция в весеннем семестре 2024–2025 учебного года состоится 19 февраля 2025.

День недели
среда
Время
18:30-20:05
Аудитория
Ещё не назначена
Аудитория первого занятия
Ещё не назначена

Теория алгоритмов

Название спецкурса на английском языке
Theory of algorithms
Авторы курса
Носов Михаил Васильевич
Пререквизиты
Отсутствуют
Целевая аудитория
3-6 курс, магистранты
Подразделение
[Кафедра МаТИС]
Семестр
Полгода (весна)
Тип курса
Спецкурс по выбору студента
Учебный год
2024/25
Список тем
Машины Тьюринга. Основные понятия. Тезис Тьюринга. Вычислимые (по Тьюрингу) функции. Примеры машин Тьюринга.
Проблема самоприменимости. Проблема применимости.
Универсальные машины Тьюринга.
Классы вычислимых и рекурсивных функций. Операции суперпозиции,
примитивной рекурсии, минимизации. Тезис Чёрча. Примеры.
Некоторые теоремы теории рекурсивных функций. Функция Аккермана.
Теорема о совпадении класса вычислимых по Тьюрингу функций и класса
частично рекурсивных функций (Кв=Кчр).
Нормальные алгоритмы Маркова. Теорема о совпадении класса нормально
вычислимых функций с классами Кв, Кчр.
Разрешимость и перечислимость множеств. Теорема Райса.
О теореме Гёделя о неполноте.
Список источников
Мальцев А.И. Алгоритмы и рекурсивные функции.
Мендельсон Э. Введение в математическую логику.
Яблонский С.В. Введение в дискретную математику.
Гаврила Г.П., Сапоженко А.А. Задачи и упражнения по курсу дискретной математики.
День недели
среда
Время
16:45-18:20
Аудитория
409
Дата первого занятия
Аудитория первого занятия
409