Линейная комбинаторика
Название спецкурса на английском языке
Linear combinatorics
Пререквизиты
Отсутствуют
Целевая аудитория
3-6 курс, магистранты
Подразделение
[Кафедра МаТИС]
Семестр
Весна
Тип спецкурса
Спецкурс по выбору кафедры
Учебный год
2025/26
Список тем
Применение методов линейной алгебры в комбинаторике.
Элементы вероятностного подхода к комбинаторным проблемам.
Сложность обучения и размерность Вапника-Червоненкеса.
Пороговые функции и их свойства. Гармонический анализ на булевом кубе. Спектральные свойства пороговых функций. Проблема параметров Чжоу (Chow). PAC-обучающий алгоритм для класса пороговых функций. Шумоустойчивость и обучаемость класса линейных пороговых функций. Теорема Переса (Peres, 2004).
Граничные точки пороговых функций. Определяющая выборка и определяющее число для гипотезы из заданного класса. Оценки для определяющего числа гипотезы из класса пороговых функций.
Частично-упорядоченное множество конфигурации гиперплоскостей. Функция Мёбиуса и характеристический полином конфигурации гиперплоскостей. Теорема о поперечном сечении (The Cross-Cut Theorem). Теорема Уитни о характеристическом полиноме конфигурации гиперплоскостей. Функция Мёбиуса геометрической решетки. Теорема Т.Заславского (1975). Алгебро-топологическое описание функции Мёбиуса конфигурации гиперплоскостей.
Верхние и нижние оценки числа пороговых функций. Лемма Littlewood-Offord (1938) в
формулировке Erdős (1945). Верхняя оценка J.Komlós (1977) для числа вырожденных ±1-матриц. Теоремы А.А.Ирматова об асимптотике числа пороговых функций, асимптотике вероятности вырожденности ±1-матриц и о подпространствах, порожденных ±1-векторами.
Элементы вероятностного подхода к комбинаторным проблемам.
Сложность обучения и размерность Вапника-Червоненкеса.
Пороговые функции и их свойства. Гармонический анализ на булевом кубе. Спектральные свойства пороговых функций. Проблема параметров Чжоу (Chow). PAC-обучающий алгоритм для класса пороговых функций. Шумоустойчивость и обучаемость класса линейных пороговых функций. Теорема Переса (Peres, 2004).
Граничные точки пороговых функций. Определяющая выборка и определяющее число для гипотезы из заданного класса. Оценки для определяющего числа гипотезы из класса пороговых функций.
Частично-упорядоченное множество конфигурации гиперплоскостей. Функция Мёбиуса и характеристический полином конфигурации гиперплоскостей. Теорема о поперечном сечении (The Cross-Cut Theorem). Теорема Уитни о характеристическом полиноме конфигурации гиперплоскостей. Функция Мёбиуса геометрической решетки. Теорема Т.Заславского (1975). Алгебро-топологическое описание функции Мёбиуса конфигурации гиперплоскостей.
Верхние и нижние оценки числа пороговых функций. Лемма Littlewood-Offord (1938) в
формулировке Erdős (1945). Верхняя оценка J.Komlós (1977) для числа вырожденных ±1-матриц. Теоремы А.А.Ирматова об асимптотике числа пороговых функций, асимптотике вероятности вырожденности ±1-матриц и о подпространствах, порожденных ±1-векторами.
Список источников
L.Babai, P.Frankl. Linear Algebra Methods in Combinatorics. Version 2.1. 2020
Н.Алон, Дж.Спенсер. Вероятностный метод. Москва. Бином. Лаборатория знаний. 2007
Ryan O'Donnell. Analysis of Boolean Functions. https://doi.org/10.48550/arXiv.2105.10386
P. Erdős, On a lemma of Littlewood and Offord, Bull. Amer. Math. Soc. Volume 51, Number 12 (1945), 898-902
A. M. Odlyzko. On subspaces spanned by random selections of ±1 vectors, J. Combinatorial Theory A, 47 (1988), pp. 124-133
R.P.Stanley. An Introduction to Hyperplane Arrangements, IAS/Park City Mathematics Series, Volume 14, 2004
T.Zaslavsky. Facing Up to Arrangements: Face-Count Formulas for Partitions of Space by Hyperplanes, Memoirs of the American Mathematical Society, V. 154, Amer. Math. Soc., Providence RI, 1975
А.А. Ирматов. О числе пороговых функций, Дискрет. матем., 1993, том 5, выпуск 3, страницы 40–43
А. А. Ирматов, Ж. Д. Ковиянич. Об асимптотике логарифма числа пороговых функций K-значной логики, Дискрет. матем., 1998, том 10, выпуск 3, страницы 35–56
A.A.Irmatov. Arrangements of Hyperplanes and the Number of Threshold Functions, Acta Applicandae Mathematicae, 2001, Vol.68 (1), pp.211-226
A.A.Irmatov. Singularity of {±1}-matrices and asymptotics of the number of threshold functions. 2020 https://doi.org/10.48550/arXiv.2004.03400 (v.3)
A.A.Irmatov. On linear-combinatorial problems associated with subspaces spanned by {±1}-vectors. 2024 https://doi.org/10.48550/arXiv.2405.05082
Н.Алон, Дж.Спенсер. Вероятностный метод. Москва. Бином. Лаборатория знаний. 2007
Ryan O'Donnell. Analysis of Boolean Functions. https://doi.org/10.48550/arXiv.2105.10386
P. Erdős, On a lemma of Littlewood and Offord, Bull. Amer. Math. Soc. Volume 51, Number 12 (1945), 898-902
A. M. Odlyzko. On subspaces spanned by random selections of ±1 vectors, J. Combinatorial Theory A, 47 (1988), pp. 124-133
R.P.Stanley. An Introduction to Hyperplane Arrangements, IAS/Park City Mathematics Series, Volume 14, 2004
T.Zaslavsky. Facing Up to Arrangements: Face-Count Formulas for Partitions of Space by Hyperplanes, Memoirs of the American Mathematical Society, V. 154, Amer. Math. Soc., Providence RI, 1975
А.А. Ирматов. О числе пороговых функций, Дискрет. матем., 1993, том 5, выпуск 3, страницы 40–43
А. А. Ирматов, Ж. Д. Ковиянич. Об асимптотике логарифма числа пороговых функций K-значной логики, Дискрет. матем., 1998, том 10, выпуск 3, страницы 35–56
A.A.Irmatov. Arrangements of Hyperplanes and the Number of Threshold Functions, Acta Applicandae Mathematicae, 2001, Vol.68 (1), pp.211-226
A.A.Irmatov. Singularity of {±1}-matrices and asymptotics of the number of threshold functions. 2020 https://doi.org/10.48550/arXiv.2004.03400 (v.3)
A.A.Irmatov. On linear-combinatorial problems associated with subspaces spanned by {±1}-vectors. 2024 https://doi.org/10.48550/arXiv.2405.05082
Дополнительная информация
Спецкурс посвящен изучению свойств линейных объектов, возникающих в дискретной математике и математической кибернетики таких как, пороговые функции, конфигурации гиперплоскостей, случайные матрицы и других вероятностно-комбинаторными и алгебро-топологическими методами. Будут рассмотрены спектральные свойства пороговых функций; проблема параметров Чжоу; РАС-обучающие алгоритмы для класса пороговых функций. Предполагается изложить последние достижения в оценке числа пороговых функций и числа вырожденных ±1-матриц, полученные рядом авторов, за последние 80 лет, в том числе теоремы об асимптотике числа пороговых функций и асимптотике вероятности вырожденности ±1-матриц.
День недели
вторник
Время
18:30-20:05
Аудитория
1225
Дата первого занятия
Аудитория первого занятия
Ещё не назначена
Статус курса
Запись открыта
Форма записи на курс
Заполнение формы записи на курс доступно только студентам. Для записи на курс авторизуйтесь, пожалуйста, в студенческом аккаунте.
Введение в компьютерный интеллект. Современное компьютерное зрение
Название спецкурса на английском языке
Introduction to computer intelligence. Modern computer vision
Пререквизиты
Отсутствуют
Целевая аудитория
3-6 курс, магистранты
аспиранты
Подразделение
[Кафедра МаТИС]
Семестр
Весна
Тип спецкурса
Спецкурс по выбору студента
Учебный год
2025/26
Список тем
Задачи компьютерного зрения
Свёрточные слои
Несвёрточные слои
Обратное распространение ошибки
Введение в PyTorch
Классификацонные архитектуры
Методы сжатия и ускорения нейронных сетей
Методы обнаружения объектов
Методы семантической и объекто-чувствительной сегментации, мэттинг
Методы улучшения качества изображений
Введение в генеративные модели
Свёрточные слои
Несвёрточные слои
Обратное распространение ошибки
Введение в PyTorch
Классификацонные архитектуры
Методы сжатия и ускорения нейронных сетей
Методы обнаружения объектов
Методы семантической и объекто-чувствительной сегментации, мэттинг
Методы улучшения качества изображений
Введение в генеративные модели
Список источников
Ian Goodfellow and Yoshua Bengio and Aaron Courville. Deep Learning, 1st edition, MIT Press, 2016
http://neuralnetworksanddeeplearning.com/
Francois Chollet. Deep Learning with Python, 1st edition, Manning, 2017
http://neuralnetworksanddeeplearning.com/
Francois Chollet. Deep Learning with Python, 1st edition, Manning, 2017
Дополнительная информация
Ссылка на тг группу курса
День недели
вторник
Время
16:45-18:20
Аудитория
Ещё не назначена
Аудитория первого занятия
Ещё не назначена
Статус курса
Запись открыта
Форма записи на курс
Заполнение формы записи на курс доступно только студентам. Для записи на курс авторизуйтесь, пожалуйста, в студенческом аккаунте.
Математические основы машинного обучения и прогнозирования
Название спецкурса на английском языке
Artificial intelligence methods in data analysis and program verification
Пререквизиты
Отсутствуют
Целевая аудитория
1-2 курс
3-6 курс, магистранты
Подразделение
[Кафедра МаТИС]
Семестр
Весна
Тип спецкурса
Спецкурс по выбору студента
Учебный год
2025/26
Список тем
Задачи и модели машинного обучения.
Линейно разделимые выборки. Алгоритм обучения Розенблатта. Теорема Новикова.
Метод градиентного спуска. Метод стохастического градиента.
Метод обратного распространения ошибки для обучения нейронных сетей.
Метод опорных векторов. Теорема Каруша-Куна-Таккера.
Построение оптимальной разделяющей гиперплоскости по зашумленной выборке.
Ядерный метод машинного обучения.
Алгоритм вычисления калибруемых прогнозов.
Алгоритм взвешенного большинства. Алгоритм оптимального распределения потерь в
режиме онлайн.
Алгоритм экспоненциального взвешивания экспертных решений.
Агрегирующий алгоритм Вовка.
Игры и прогнозы. Антагонистические игры двух игроков. Достаточное условие
существования седловой точки. Смешанные расширения матричных игр.
Игры на универсальные прогнозы. Рандомизированные калибруемые прогнозы.
Теорема Блекуэлла о достижимости
Калибруемые прогнозы и коррелированное равновесие.
Линейно разделимые выборки. Алгоритм обучения Розенблатта. Теорема Новикова.
Метод градиентного спуска. Метод стохастического градиента.
Метод обратного распространения ошибки для обучения нейронных сетей.
Метод опорных векторов. Теорема Каруша-Куна-Таккера.
Построение оптимальной разделяющей гиперплоскости по зашумленной выборке.
Ядерный метод машинного обучения.
Алгоритм вычисления калибруемых прогнозов.
Алгоритм взвешенного большинства. Алгоритм оптимального распределения потерь в
режиме онлайн.
Алгоритм экспоненциального взвешивания экспертных решений.
Агрегирующий алгоритм Вовка.
Игры и прогнозы. Антагонистические игры двух игроков. Достаточное условие
существования седловой точки. Смешанные расширения матричных игр.
Игры на универсальные прогнозы. Рандомизированные калибруемые прогнозы.
Теорема Блекуэлла о достижимости
Калибруемые прогнозы и коррелированное равновесие.
Список источников
Миронов А.М., Машинное обучение, часть 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 с.
Вьюгин В.В. Математические основы машинного обучения и
прогнозирования. Москва, издательство МЦНМО, 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 с.
Дополнительная информация
Спецкурс включает знакомство с основными понятиями теории машинного обучения и прогнозирования. В первой части курса рассматривается формализация основных задач машинного обучения, излагаются алгоритмы обучения для линейно разделимых обучающих выборок, методы градиентного спуска и его разновидности, метод обучения нейронных сетей, метод опорных векторов, ядерные методы машинного обучения, регрессионный анализ, метрические и вероятностные модели машинного обучения, логические модели машинного обучения. Во второй части рассматриваются задачи адаптивного прогнозирования в нестохастических теоретико-игровой и сравнительной постановках: игры с прогнозами и прогнозы с использованием экспертных стратегий.
День недели
среда
Время
15:00-16:35
Аудитория
1624
Дата первого занятия
Аудитория первого занятия
1624
Статус курса
Запись открыта
Форма записи на курс
Заполнение формы записи на курс доступно только студентам. Для записи на курс авторизуйтесь, пожалуйста, в студенческом аккаунте.
Машинное обучение с подкреплением
Название спецкурса на английском языке
Reinforcement learning
Пререквизиты
математический анализ, линейная алгебра, теория вероятностей, базовый Python
Целевая аудитория
1-2 курс
3-6 курс, магистранты
аспиранты
Подразделение
[Кафедра МаТИС]
Семестр
Весна
Тип спецкурса
Спецкурс по выбору студента
Учебный год
2025/26
Список тем
Многорукие бандиты
Контекстуальные бандиты
MDP и основы RL
Уравнения Беллмана и динамическое программирование
Обучение по траекториям
Аппроксимация функций и Deep RL
Policy Gradient
Actor–Critic
Trust Region методы
Современная policy optimization: GRPO
Off-policy и Offline RL
Современные направления и ограничения
Контекстуальные бандиты
MDP и основы RL
Уравнения Беллмана и динамическое программирование
Обучение по траекториям
Аппроксимация функций и Deep RL
Policy Gradient
Actor–Critic
Trust Region методы
Современная policy optimization: GRPO
Off-policy и Offline RL
Современные направления и ограничения
Список источников
Sutton, Barto. Reinforcement Learning: An Introduction (2nd ed.).
Дополнительная информация
Курс посвящён современным методам обучения с подкреплением (Reinforcement Learning, RL) с акцентом на практическое применение.
В курсе излагаются модели многоруких и контекстуальных бандитов (regret, UCB, Thompson Sampling), затем излагаются марковскиие процессы принятия решений (MDP) и динамическое программирование, методы обучения по траекториям (MC/TD), глубокое обучение (DQN, источники нестабильности), policy gradient и actor–critic подходы, trust-region оптимизация (TRPO, PPO), а также современные направления: off-policy и offline RL, GRPO и связь RL с RLHF и обучение больших языковых моделей (LLM).
Занятия начинаются в 17-00.
День недели
четверг
Время
16:45-18:20
Аудитория
428
Дата первого занятия
Аудитория первого занятия
428
Статус курса
Запись открыта
Форма записи на курс
Заполнение формы записи на курс доступно только студентам. Для записи на курс авторизуйтесь, пожалуйста, в студенческом аккаунте.
Криптографические протоколы
Название спецкурса на английском языке
Cryptographic protocols
Пререквизиты
Отсутствуют
Целевая аудитория
3-6 курс, магистранты
Подразделение
[Кафедра МаТИС]
Семестр
Весна
Тип спецкурса
Спецкурс по выбору студента на английском языке
Учебный год
2025/26
Список тем
Протоколы аутентификации
Протоколы электронной подписи
Протоколы распределения криптографических ключей
Протоколы электронного голосования
Протоколы электронной коммерции
Примеры уязвимостей протоколов
Методы формального анализа протоколов
Протоколы электронной подписи
Протоколы распределения криптографических ключей
Протоколы электронного голосования
Протоколы электронной коммерции
Примеры уязвимостей протоколов
Методы формального анализа протоколов
Список источников
Миронов А.М. Криптографические протоколы, 120 стр., МаТИС, Механико-математический факультет МГУ им. М. В. Ломоносова
Дополнительная информация
Чат курса https://t.me/mathissuescompscience
День недели
пятница
Время
16:45-18:20
Аудитория
Ещё не назначена
Дата первого занятия
Аудитория первого занятия
Ещё не назначена
Статус курса
Курс не читается
Алгоритмическая алгебра
Название спецкурса на английском языке
Algorithmic algebra
Пререквизиты
Отсутствуют
Целевая аудитория
3-6 курс, магистранты
аспиранты
Подразделение
[Кафедра МаТИС]
Семестр
Весна
Тип спецкурса
Спецкурс по выбору студента
Учебный год
2025/26
Список тем
Элементы теории рекурсивных функций и алгоритмов
Частично рекурсивные функции как вариант формализации понятия алгоритма. Примитивно рекурсивные и общерекурсивные функции
Перечислимые, разрешимые, примитивно рекурсивные предикаты, отношения,
множества
Теорема Аккермана (о диагональной одноместной «быстрорастущей» общерекурсивной функции, не являющейся примитивно рекурсивной функцией)
Теоремы об устранимости кванторов в элементарных теориях (в теориях 1-го порядка) некоторых классов алгебраических систем и об алгоритмической разрешимости таких теорий
Теоремы об устранимости кванторов в монадических теориях 2-го порядка некоторых классов алгебраических систем и об алгоритмической разрешимости таких теорий.
Теорема Рабина о разрешимости монадической теории второго порядка бинарного дерева с двумя функциями следования (без доказательства). Теорема о разрешимости слабой монадической теории второго порядка бинарного дерева с двумя функциями следования
Применения теорем о разрешимости монадических теорий 2-го порядка к доказательству разрешимости некоторых теорий 1-го порядка
Частично рекурсивные функции как вариант формализации понятия алгоритма. Примитивно рекурсивные и общерекурсивные функции
Перечислимые, разрешимые, примитивно рекурсивные предикаты, отношения,
множества
Теорема Аккермана (о диагональной одноместной «быстрорастущей» общерекурсивной функции, не являющейся примитивно рекурсивной функцией)
Теоремы об устранимости кванторов в элементарных теориях (в теориях 1-го порядка) некоторых классов алгебраических систем и об алгоритмической разрешимости таких теорий
Теоремы об устранимости кванторов в монадических теориях 2-го порядка некоторых классов алгебраических систем и об алгоритмической разрешимости таких теорий.
Теорема Рабина о разрешимости монадической теории второго порядка бинарного дерева с двумя функциями следования (без доказательства). Теорема о разрешимости слабой монадической теории второго порядка бинарного дерева с двумя функциями следования
Применения теорем о разрешимости монадических теорий 2-го порядка к доказательству разрешимости некоторых теорий 1-го порядка
Список источников
Мальцев А.И. Алгоритмы и рекурсивные функции. – М.: Наука, 1965
Панкратьев Е.В. Элементы компьютерной алгебры – М.: Интернет-университет информационных технологий
Рабин М. Разрешимые теории. Справочная книга по математической логике. Часть 3 Теория рекурсии. – Москва: Наука, 1982
Ершов Ю.Л. Проблемы разрешимости и конструктивные модели. – М.: Наука, 1980
Панкратьев Е.В. Элементы компьютерной алгебры – М.: Интернет-университет информационных технологий
Рабин М. Разрешимые теории. Справочная книга по математической логике. Часть 3 Теория рекурсии. – Москва: Наука, 1982
Ершов Ю.Л. Проблемы разрешимости и конструктивные модели. – М.: Наука, 1980
Дополнительная информация
В курсе освещаются следующие вопросы:
1) начальные сведения по теории алгоритмов и теории конечных автоматов,
2) уравнения в словах в свободном моноиде,
3) метод устранения кванторов,
4) алгоритмическая разрешимость теорий некоторых классов алгебраических систем.
Нужные для понимания спецкурса сведения по математической логике и алгебре будут кратко напоминаться по ходу лекций.
День недели
четверг
Время
16:45-18:20
Аудитория
407
Дата первого занятия
Аудитория первого занятия
Ещё не назначена
Статус курса
Запись открыта
Форма записи на курс
Заполнение формы записи на курс доступно только студентам. Для записи на курс авторизуйтесь, пожалуйста, в студенческом аккаунте.