Финансовая математика и машинное обучение в финансах

Название спецкурса на английском языке
Financial mathematics and machine learning in finance
Авторы курса
Кирнасов Александр Евгеньевич
Пререквизиты
Отсутствуют
Целевая аудитория
3-6 курс, магистранты
аспиранты
Подразделение
[Кафедра МаТИС]
Семестр
Весна
Тип спецкурса
Спецкурс по выбору студента
Учебный год
2025/26
Список тем
Виды деривативных контрактов – Форварды, Фьючерсы, Опционы
Модели биномиального риска
Случайные процессы, Интеграл Ито, Формула Ито
Модель Блэка-Шоулза, Вывод формулы Блэка Шоулза
Греки и Хеджирование, Численные методы прайсинга
Локальная и статистическая волатильность
Высокочастотный трейдинг, микроструктура рынка
Высокочастотный Market Making и оптимальное стохастическое управление
Модель Авеланеды-Стоикова
Обобщения модели Авеланеды-Стоикова, модель Гуанта-Легаля-Фернандеса-Тапии, модель
Картеа
Статистический арбитраж
Машинное обучение в финансах, предсказания временных рядов
Метрики точности предсказательных моделей – R squared, ROC AUC
Модели ARCH и GARCH
Линейная и логистическая регрессия, регрессия Ridge, LASSO
Сравнение нейросетей для временных рядов – линейные, вероятностные, LSTM, Transformers
Применение Reinforcement Learning в финансах
Сравнение алгоритмов DQN и PPO
Список источников
Ширяев А.Н. Основы стохастической финансовой математики – М.: Московский центр
непрерывного математического образования, 2016
Наумов В.Н. Методы прогнозирования временных рядов – М.: Издательство Лань, 2024
Лапань М. В. Глубокое Обучение с подкреплением, AlphaGo и другие технологии – М.:
Издательство Питер, 2020
Бенджио Иошуа, Курвиль Аарон, Глубокое обучение - М. Издательство ДМК Пресс, 2018
Дополнительная информация

В курсе освещаются следующие вопросы:

1) начальные сведения по теории финансовой математики

2) интеграл Ито и модель Блэка Шоулза прайсина опционов

3) модели стохастического оптимального управления для высоко частотного Market Making

4) машинное обучения в задачах прогнозирования временных рядов

5) глубокое обучение и глубокое обучение с подкреплением для финансовых задач

Нужные для понимания спецкурса сведения из статистики, теории вероятностей и случайных

процессов, финансовой математки и машинного обучения будут напоминаться по ходу лекций.

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

Дополнительные главы теоретической информатики

Название спецкурса на английском языке
Additional chapters of computer science
Авторы курса
Гасанов Эльяр Эльдарович, Алексеев Дмитрий Владимирович, Шуткин Юрий Сергеевич, Калачев Глеб Вячеславович
Пререквизиты
Отсутствуют
Целевая аудитория
аспиранты
Подразделение
[Кафедра МаТИС]
Семестр
Весна
Тип спецкурса
Спецкурс по выбору студента
Учебный год
2025/26
Список тем
Понятие алгоритма и вычислимой функции, перечислимого и разрешимого множества.
Универсальная вычислимая функция. Существование перечислимого неразрешимого множества. Алгоритмические проблемы.
Определение вычислимости в теоретико-множественных терминах (например, вычислимость по Тьюрингу). Тезис Тьюринга-Чёрча.
Сложность вычисления. Классы P и NP. Полиномиальная сводимость и NP-полные задачи. Теорема об NP-полноте задачи выполнимости булевых формул (3-выполнимость)
Понятие алгоритма и вычислимой функции, перечислимого и разрешимого множества.
Универсальная вычислимая функция. Существование перечислимого неразрешимого множества. Алгоритмические проблемы.
Определение вычислимости в теоретико-множественных терминах (например, вычислимость по Тьюрингу). Тезис Тьюринга-Чёрча.
Сложность вычисления. Классы P и NP. Полиномиальная сводимость и NP-полные задачи. Теорема об NP-полноте задачи выполнимости булевых формул (3-выполнимость)
Линейное программирование. Симплекс-метод. Двойственные задачи линейного программирования, теоремы о сильной/слабой двойственности.
Задачи целочисленного линейного программирования (ЦЛП). Метод ветвей и границ, метод Гомори. Примеры и решение Задачи ЦЛП: Транспортная задача. Задача о назначениях, венгерский алгоритм. Задача коммивояжера.
Задача распределения ресурсов. Принцип выравнивания Гермейера.
Метод динамического программирования. Принцип Беллмана. Примеры задач. Алгоритмы Нидлмана-Вунша и Смита-Ватермана
Потоки в сетях. Теорема Форда-Фалкерсона. Алгоритм нахождения максимального потока. Теорема о целочисленности. Теорема Кенига-Эгервари. Теорема Холла. Теорема Дилуорса.
Модель межотраслевого баланса В. В. Леонтьева. Продуктивные матрицы. Критерии продуктивности. Теорема Фробениуса—Перрона. Свойства числа Фробениуса—Перрона. Теорема об устойчивости примитивных матриц.
Динамическая модель Леонтьева. Теорема о магистрали Моришимы. Экономическая интерпретация вектора Фробениуса — Перрона.
Теоремы о неподвижных точках (Брауэра, Какутани). Модель Вальраса. Модель Эрроу—Дебре. Конкурентное равновесие.
Список источников
Верещагин Н. К., Шень А. Лекции по математической логике и теории алгоритмов. Часть 3. Вычислимые функции. — 4-е изд., исправленное. — М.: МЦНМО, 2012. — 160 c.
Мальцев А. И. Алгоритмы и рекурсивные функции. 2-е изд. - М.: Наука. Гл. ред. физ.-мат. лит., 1986. — 368 с.
Гери М., Джонсон Д., Вычислительные машины и трудно решаемые задачи. М.: Мир, 1982, 416с.
Кострикин А.И. Введение в алгебру, ч. 3, Основные структуры , 3 изд., М:ФИЗМАТЛИТ, 2004
Галочкин А.И., Нестеренко Ю.В., Шидловский А.Б. Введение в теорию чисел, Изд-во Моск. ун-та, 1984, 152 стр.
Коблиц Н., Курс теории чисел и криптографии, М.: Науч. изд-во ТВП, 2001, 254 с.
Ван-дер-Варден Б.Л., Алгебра, М.: Мир, 1976. - 648 с.
Винберг Э.Б., Курс алгебры, М.: Изд-во «Факториал Пресс», 2001. 544c.
Бунина Е.И., Лекции по алгебре, 3 сем., 2016–2017 уч. год. Лекция 17 (электронное издание)
http://halgebra.math.msu.su/wiki/lib/exe/fetch.php/staff:lecture17.pdf
Виноградов И.М. Основы теории чисел, М.-Л., Гостехиздат, 1952. 180 с.
Нестеренко Ю.В., Теория чисел, – М.: Академия, 2008. 272с.
Дополнительная информация

Литература курса доступна для скачивания с Гугл-диска

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

Введение в сжатие медиа

Название спецкурса на английском языке
Introduction to media compression
Авторы курса
Бабин Дмитрий Николаевич, Пархоменко Денис Владимирович
Пререквизиты
Отсутствуют
Целевая аудитория
3-6 курс, магистранты
аспиранты
Подразделение
[Кафедра МаТИС]
Семестр
Весна
Тип спецкурса
Спецкурс по выбору студента
Учебный год
2025/26
Список тем
Необходимый минимум по цифровой обработке сигналов
Кодеки для изображений и видео
Не нейросетевые аудио кодеки
Задача генерации образов. Авторегрессионная генерация: рекуррентные нейросети, LLM
Неавторегрессионная генерация: трансформеры, основы генеративно-состязательного
обучения, диффузионные модели
Токенизаторы аудио для генеративного ИИ
Токенизаторы изображений и видео для генеративного ИИ
Список источников
Хайкин С. «Нейронные сети: полный курс», Вильямс 2006
Половников В.С. «Об оптимизации структурной реализации нейронных сетей» диссертация на соискание степени кандидата наук, 2007
William Merrill, Sequential Neural Networks as Automata, 2021
Calvin Luo, Understanding Diffusion Models: A Unified Perspective, 2022
Patrick Esser et al, A Disentangling Invertible Interpretation Network for Explaining Latent Representations, 2020
Jacob Devlin, BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding , 2019
День недели
вторник
Время
18:30-20:05
Аудитория
Ещё не назначена
Аудитория первого занятия
Ещё не назначена
Статус курса
Запись открыта
Форма записи на курс
Заполнение формы записи на курс доступно только студентам. Для записи на курс авторизуйтесь, пожалуйста, в студенческом аккаунте.

Дополнительные главы теории автоматов в лабиринтах

Название спецкурса на английском языке
Additional chapters of automata in labyrinths
Авторы курса
Волков Николай Юрьевич
Пререквизиты
Отсутствуют
Целевая аудитория
3-6 курс, магистранты
Подразделение
[Кафедра МаТИС]
Семестр
Весна
Тип спецкурса
Спецкурс по выбору студента
Учебный год
2025/26
Список тем
Лабиринты: прямоугольные, мозаичные, шахматные.
Перемещение независимых систем автоматов в лабиринтах.
Возможность обхода конечных мозаичных лабиринтов конечными автоматами.
Теорема Будаха-Подколзина (невозможность обхода конечным автоматом всех мозаичных лабиринтов).
Обход автоматом конечных односвязных шахматных лабиринтов.
Обход конечным автоматом конечных лабиринтов с ограниченными внутренними дырами.
Перемещение в лабиринтах коллективов автоматов.
Периодичность поведения системы автоматов в конечных лабиринтах.
Пример непериодического поведения коллектива автоматов.
Автоматы со счётчиками.
Обход произвольных конечных шахматных лабиринтов автоматом со счётчиком.
Обход произвольных конечных шахматных лабиринтов коллективом автоматов.
Обход коллективом автоматов лабиринтов с одной дырой.
Постановка задачи преследования в шахматных лабиринтах.
Поведение конечного автомата в L0.
Задача преследования независимой системой хищников независимой системы жертв в L0.
Поведение конечного автомата в L1.
Задача преследования независимой системой хищников независимой системы жертв в L1.
Поведение конечного автомата в L2(l).
Задача преследования независимой системой хищников независимой системы жертв в L2(l).
Поведение конечного автомата в L3(l) и L4.
Задача преследования независимой системой хищников независимой системы жертв в L3(l) и L4.
Поимка данной жертвы в L0 коллективом хищников.
Существование универсального коллектива хищников в L0.
Существование универсального коллектива хищников в L1, L2(l), L3(l) и L4.
Задача преследования коллективом хищников независимой системы жертв в L5(l).
Нерешённые лабиринтные задачи.
Список источников
http://intsys.msu.ru/magazine/archive/v12(1-4)/volkov-137-158.pdf
http://intsys.msu.ru/magazine/archive/v11(1-4)/volkov-361-402.pdf
Дополнительная информация

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

День недели
пятница
Время
15:00-16:35
Аудитория
407
Дата первого занятия
Аудитория первого занятия
Ещё не назначена
Статус курса
Запись открыта
Форма записи на курс
Заполнение формы записи на курс доступно только студентам. Для записи на курс авторизуйтесь, пожалуйста, в студенческом аккаунте.

Свойства автоматных базисов

Название спецкурса на английском языке
Properties of automata bases
Авторы курса
Бабин Дмитрий Николаевич
Пререквизиты
Отсутствуют
Целевая аудитория
3-6 курс, магистранты
аспиранты
Подразделение
[Кафедра МаТИС]
Семестр
Весна
Тип спецкурса
Спецкурс по выбору студента
Учебный год
2025/26
Список тем
Автоматы, операции суперпозиции и комозициция
Свойства решётки Поста
Замкнутый класс, порядок замкнутого класса
Теорема о числе входов полной системы автоматов
Замкнутые классы автоматов
Автоматы с функциями переходов и выходов из классов Поста
Арность классов автоматов с операциями суперпозиции и композиции
Классы автоматов бесконечной арности
Суперпозиция автоматов и её связь с теоретико-групповыми операциями
Линейные автоматы, свойства замкнутых классов линейных автоматов
Кодировка состояний автоматов
Список источников
Кудрявцев В.Б., Гаврилов Г.П., Яблонский С.В., Функции алгебры логики и классы Поста, Наука, М., 1966.
Кудрявцев В.Б., Алешин С.В., Подколзин А.С. Введение в теорию автоматов
Дополнительная информация

Доп дискуссии и отработки в Zoom Meeting Meeting ID: 452 832 0761 Passcode: 8gdJck

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

Введение в искусственный интеллект и машинное обучение

Название спецкурса на английском языке
Introduction to artificial intelligence and machine learning
Авторы курса
Боков Григорий Владимирович, Хусаенов Артем Азатович
Пререквизиты
Отсутствуют
Целевая аудитория
3-6 курс, магистранты
Подразделение
[Кафедра МаТИС]
Семестр
Весна
Тип спецкурса
Спецкурс по выбору студента
Учебный год
2025/26
Список тем
Введение в математику и философию ИИ. От естественного интеллекта к искусственному
Представление знаний и автоматизация рассуждений
Введение в машинное обучение. Процесс принятия решения в терминах обучаемой модели (упрощенно). Нечеткая функция принадлежности и представление естественных признаков в виде нечеткого множества.
Базовое представление о проблеме переобучения моделей. Дилемма смещения-разброса как пояснение в терминах аппроксимации и статистики (упрощенно).
Основы Python. Базовые аспекты и основные объекты
Классическое машинное обучение. Краткий обзор базовых методов машинного обучения (с упрощенным пояснением). Примеры задач: как простейшие алгоритмы решают сложные задачи.
Логическое представление естественно-биологической модели связи из нескольких нейронов. Многослойная нейронная сеть прямого распространения. Проблемы переобучения нейронной сети.
Автоассоциативные нейронные сети. Оценка важности признаков и главная нелинейная компонента множества. Смещение рода ошибки (упрощенно: больной-здоровый, здоровый-больной). Пример: рекомендательная система для врачей - оценка вероятности неблагоприятного клинического исхода у пациента.
Рекуррентные нейронные сети. Задачи прогнозирования и обработки временных рядов, основы обработки естественного языка. Примеры: распознавание речи, оценка тональности текста.
Глубокие сверточные нейронные сети. Основы компьютерного зрения. Примеры карт признаков. Аугментация данных окклюзия признаков. Технология transfer-learning и дообучение нейронных сетей. Примеры кода: как обучить модель в 15 строк кода.
Список источников
Брик Х., Феверолф М., Ричардс Д., Машинное обучение, Библиотека программиста: Питер, 2017. – 336 с.
Заде Л., Понятие лингвистической переменной и его применение к принятию приближенных решений: Мир, 1976. — 166 с.
Мак-Каллок, У. С., Питтс, В. Логическое исчисление идей, относящихся к нервной активности = A logical calculus of the ideas immanent in nervous activity: Автоматы, 1956. - 363 – 384 с.
Минский М., Пейперт С., Персептроны = Perceptrons: Мир, 1971. — 261 с.
Розенблатт Ф., Принципы нейродинамики: Перцептроны и теория механизмов мозга = Principles of Neurodynamic: Perceptrons and the Theory of Brain Mechanisms: Мир, 1965. — 480 с.
Николенко С., Архангельская Е., Кадурин А, Глубокое обучение, покружение в мир нейронных сетей, Библиотека программиста: Питер, 2020. – 480 с.
Бенджио И., Курвилль А., Гудфеллоу Я., Глубокое обучение: ДМК-Пресс, 2018. – 652 с.
Liou C., Cheng C., Liou J.-W., Liou D., Autoencoder for Words: Neurocomputing, 2014. - v.139, 84-96 p.
Lesk, A. M.. Introduction to bioinformatics, 2012.
Murphy, K. P. Machine Learning: A Probabilistic Perspective. 2012. Cambridge, Mass: The MIT Press
Дополнительная информация

Курс является обязательным для студентов магистратуры философского факультета и факультета психологии. Ссылка на Telegram канал https://t.me/+Y6cohsegopE2NzA6

В ауд г309 Шуваловского корпуса

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

Кодирование и защита информации

Название спецкурса на английском языке
Coding and information security
Авторы курса
Носов Валентин Александрович, Панкратьев Антон Евгеньевич
Пререквизиты
Отсутствуют
Целевая аудитория
3-6 курс, магистранты
Подразделение
[Кафедра МаТИС]
Семестр
Весна
Тип спецкурса
Спецкурс по выбору студента
Учебный год
2025/26
Список тем
Кодирование, криптография, стеганография. Исторический очерк развития.
Введение в теорию кодирования. Алфавитное кодирование. Префиксные коды. Теорема Маркова. Неравенство МакМиллана.
Коды с минимальной избыточностью (коды Хаффмана).
Самокорректирующиеся коды (коды Хэмминга). Геометрические приложения.
Математическая модель шифра замены. Классификация шифров замены.
Шифры перестановки. Элементы анализа.
Анализ шифра Виженера: нахождение длины ключа с использованием индекса совпадения; нахождение ключа с использованием взаимного индекса совпадения.
Статистические характеристики открытых текстов. Пример вскрытия шифра простой замены.
Блочные шифры. Стандарты шифрования данных. Режимы использования блочных шифров.
Введение в теорию сложности вычислений. Скорость роста функций. Сложностные классы. Труднорешаемые задачи и их применение в криптографии.
Шифрование с открытым ключом: принципы и примеры протоколов.
Задача о рюкзаке и рюкзачные системы.
Задача дискретного логарифмирования. Алгоритм Сильвера-Полига-Хеллмана, индексный алгоритм.
Проверка чисел на простоту. Вероятностные тесты на простоту. Тест Соловея-Штрассена. Тест Миллера-Рабина.
Факторизация больших составных чисел. Алгоритм Полларда. Факторизация Ферма. Алгоритм факторных баз.
Эллиптические кривые и их применение в криптографии. Обобщение известных криптосистем на эллиптические кривые.
Совершенные шифры. Латинские квадраты и их свойства. Построение параметрических классов латинских квадратов.
Клеточные автоматы и их использование в криптографии.
Системы шифрования, основанные на сложностных задачах комбинаторной теории групп.
Список источников
А.П. Алферов, А.Ю. Зубов, А.С. Кузьмин, А.В. Черемушкин, «Основы криптографии», Москва: Гелиос АРВ, 2001.
Н. Коблиц, «Курс теории чисел и криптографии», Москва: ТВП, 2001.
К. Шеннон, «Теория связи в секретных системах», в сб. «Работы по теории информации и кибернетике», Москва: Иностранная Литература, 1963, сс. 333-369.
J. Denes and A.D. Keedwell, «Latin squares and their applications», New York: Academic Press, 1974
Т. Кормен, Ч. Лейзерсон, Р. Ривест, «Алгоритмы: построение и анализ», Москва: МЦНМО, 2000.
В.А. Носов, «основы теории алгоритмов и анализа их сложности», Москва: 1992.
А. Саломаа, «Криптография с открытым ключом», Москва: Мир, 1995.
В.Б. Кудрявцев, А.С. Подколзин, А.А. Болотов, «Основы теории однородных структур», Москва: Наука, 1990.
A. Myasnikov, V. Shpilrain, A. Ushakov, «Group-based cryptography» Basel: Birkhauser, 2008.
Е.В. Панкратьев, «Элементы компьютерной алгебры», Москва: Бином, 2007.
Дополнительная информация

В курсе освещаются следующие вопросы:
1) начальные сведения по теории кодирования и шифрования;
2) основные понятия теории сложности вычислений;
3) круг задач, решаемых с помощью криптографии;
4) симметричное и асимметричное шифрование;
5) криптографические протоколы, основанные на сложностных проблемах из различных областей алгебры и дискретной математики.

Нужные для понимания спецкурса сведения будут кратко напоминаться по ходу лекций.

День недели
пятница
Время
16:45-18:20
Аудитория
405
Дата первого занятия
Аудитория первого занятия
Ещё не назначена
Статус курса
Запись открыта
Форма записи на курс
Заполнение формы записи на курс доступно только студентам. Для записи на курс авторизуйтесь, пожалуйста, в студенческом аккаунте.

Группы и полугруппы автоматов

Название спецкурса на английском языке
Automata groups and semigroups
Авторы курса
Алешин Станислав Владимирович
Пререквизиты
Отсутствуют
Целевая аудитория
3-6 курс, магистранты
Подразделение
[Кафедра МаТИС]
Семестр
Весна
Тип спецкурса
Спецкурс по выбору студента
Учебный год
2025/26
Список тем
Декомпозиция автоматов
Группа кос
Проблема Бернсайда
Список источников
В.Б.Кудрявцев, С.В.Алешин, А.С.Подколзин, Элементы теории автоматов, М., Изд-во МГУ, 1978 г
С.В.Алешин Об отсутствии базисов в некоторых классах инициальных автоматов. Проблемы кибернетики, вып.22, 1970 г.
С.В.Алешин Конечные автоматы и проблема Бернсайда о периодических группах.Мат.
заметки, вып3, 1972.
Дополнительная информация

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

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

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

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

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

Название спецкурса на английском языке
Combinatorial methods of discrete mathematics
Авторы курса
Носов Валентин Александрович
Пререквизиты
Отсутствуют
Целевая аудитория
3-6 курс, магистранты
Подразделение
[Кафедра МаТИС]
Семестр
Весна
Тип спецкурса
Спецкурс по выбору студента
Учебный год
2025/26
Список тем
Модели вычислений, используемые для оценки сложности алгоритмов и вычислений
Меры сложности алгоритмов
Труднорешаемость задач
Классы P и NP и их свойства
NP-полные задачи
Теорема Кука о NP-полноте проблемы выполнимости формул алгебры высказываний
Полиномиальная сводимость задач
Рекурсивные алгоритмы для задач сортировки массивов чисел, умножения чисел, умножения матриц, преобразования формул алгебры логики
Доказательства не существования приближенных алгоритмов с некоторыми мерами уклонения
Оптимизация алгоритмов перебора
Политика жадности
Приближенные алгоритмы для задач об упаковке, о коммивояжере, о вершинном покрытии
Матроиды
Характеризация случаев оптимальности жадных алгоритмов
Теорема Радо- Эдмонса.
Список источников
Носов В.А. Основы теории алгоритмов и анализа их сложности. Курс лекций. Москва, 1992. 140 стр.
Дополнительная информация

Для 5го курса МаТИС

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

День недели
среда
Время
16:45-18:20
Аудитория
405
Дата первого занятия
Аудитория первого занятия
405
Статус курса
Запись открыта
Форма записи на курс
Заполнение формы записи на курс доступно только студентам. Для записи на курс авторизуйтесь, пожалуйста, в студенческом аккаунте.