Коммуникационная сложность

Название спецкурса на английском языке
Communication complexity
Авторы курса
Верещагин Николай Константинович
Пререквизиты
Знакомство с линейной алгеброй в объеме одного семестра и с началами
теории вероятностей
Целевая аудитория
3-6 курс, магистранты
аспиранты
Подразделение
[Кафедра математической логики и теории алгоритмов]
Семестр
Весна
Тип спецкурса
Спецкурс по выбору кафедры
Учебный год
2025/26
Список тем
Логарифмические верхние оценки коммуникационной сложности функций MED и CIS.
Вероятностный протокол с логарифмической и константной коммуникацией для предиката равенства.
Связь детерминированной сложности с разбиением на одноцветные прямоугольники.
Методы доказательства нижних оценок для разбиений и покрытий прямоугольниками.
Теорема о квадратичной верхней оценке детерминированной сложности через недетерминированную
Теорема Разборова о квадратичном разрыве между недетерминированной и детерминированной сложностями.
Вероятностный протокол логарифмической сложности для GT
Сравнение вероятностных сложностей с общими и приватными битами (теорема Ньюмана).
Безошибочная вероятностная сложность предиката DISJ (теорема Хостада-Вигдерсона).
Пестрота. Линейная нижняя оценка вероятностной сложности предиката IP.
Информационная сложность протоколов, теорема о прямой сумме
Коммуникационная сложность отношений. Связь между формулами в базисе И, ИЛИ, НЕ и коммуникационной сложностью (Карчмер-Вигдерсон).
Отношение FORK и нижняя оценка глубины коммуникационного протокола для него. Сверх-логарифмическая нижняя оценка глубины монотонных формул для булевой функции
Применение коммуникационной сложности для оценки размера схем из пороговых элементов
Применение коммуникационной сложности для оценки высоты деревьев решений
Экспоненциальная нижняя оценка веса пороговых элементов для схем глубины 2, вычисляющих предикат IP.
Список источников
Anup Rao and Amir Yehudayoff, Communication Complexity: and Applications, Cambridge University Press; 1st edition (March 26, 2020)
E. Kushilevitz, N. Nisan. Communication Complexity. Cambridge UP. 1st edition 1997
Дополнительная информация

Чат в Телеграм: https://t.me/+9G993a4ym640ZTVi

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

Современные методы обработки данных, II

Название спецкурса на английском языке
Modern data processing methods, II
Авторы курса
Любецкий Василий Александрович
Пререквизиты
Отсутствуют
Целевая аудитория
1-2 курс
3-6 курс, магистранты
аспиранты
Подразделение
[Кафедра математической логики и теории алгоритмов]
Семестр
Весна
Тип спецкурса
Спецкурс по выбору кафедры
Учебный год
2025/26
Список тем
Постановки алгоритмических задач построения и эволюции синтеничных структур.
Алгоритм построения синтении.
Алгоритм эволюции синтении.
Список источников
В.А. Любецкий, К.Ю. Горбунов, С.А. Пирогов, Г.А. Хазиев, А.И. Агламазова. Кластеризация точек многомерного пространства на основе идеологии Seurat // Проблемы передачи информации, принята в печать в 1-й номер 2026 года.
В.А. Любецкий, К.Ю. Горбунов, Л.И. Рубанов. Построения и эволюции синтеничных структур. // 2026 год. Рукопись.
Дополнительная информация

Дан набор буквенных последовательностей. Синтенией называется набор их коротких  подпоследовательностей, которые подобны по взаиморасположению букв и по их гомологии (которая возникает из того, что каждая буква обозначает сложный объект, например, ген). Изложение не использует материал 1-го семестра (https://scs.math.msu.ru/ru/node/8581) и не требует предварительных знаний. Сейчас этот материал доступен в рукописи. Курс может сдаваться как «годовой» (объединение материала 1-го и 2-го семестров), так и как «полугодовой» (материал весеннего семестра). Эта тема нуждается в компьютерной программе, и широко востребована в мировой практике.

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

Метод резолюций

Название спецкурса на английском языке
The resolution method
Авторы курса
Плиско Валерий Егорович
Пререквизиты
Отсутствуют
Целевая аудитория
3-6 курс, магистранты
аспиранты
Подразделение
[Кафедра математической логики и теории алгоритмов]
Семестр
Осень
Тип спецкурса
Спецкурс по выбору кафедры
Учебный год
2025/26
Список тем
Логика первого порядка
Теорема Эрбрана
Метод резолюций для логики высказываний
Алгоритм унификации
Метод резолюций для логики предикатов
Уточнения исчисления резолюций
Применения метода резолюций в математической логике
Список источников
В.Н.Крупский, В.Е.Плиско. Математическая логика и теория алгоритмов. М.: Академия, 2013. Глава 14.
Ч.Чень, Р.Ли. Математическая логика и автоматическое доказательство теорем. М.: Наука, 1983.
A.Leitsch. The Resolution Calculus. Springer, 1997.
Дополнительная информация

В спецкурсе детально излагается так называемый метод резолюций, используемый при построении систем автоматического доказательства теорем.

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

Математическая логика, часть 2

Название спецкурса на английском языке
Mathematical logic, part 2
Авторы курса
Яворская Татьяна Леонидовна
Пререквизиты
Отсутствуют
Целевая аудитория
1-2 курс
3-6 курс, магистранты
аспиранты
Подразделение
[Кафедра математической логики и теории алгоритмов]
Семестр
Весна
Тип спецкурса
Спецкурс по выбору кафедры
Учебный год
2025/26
Список тем
Рекурсивные функции.
Теоремы Геделя о неполноте.
Аксиоматическая теория множеств.
Теорема Цермело.
Список источников
T. Jech. Set theory, The Third Millenium Edition. Springer, 2006.
G. Boolos. The logic of provability. Cambridge University Press, 1993.
Дополнительная информация

Спецкурс является обязательным для студентов 3 курса кафедры математической логики и теории алгоритмов.

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

Математическая логика, часть 1

Название спецкурса на английском языке
Mathematical logic, part 1
Авторы курса
Яворская Татьяна Леонидовна
Пререквизиты
Отсутствуют
Целевая аудитория
1-2 курс
3-6 курс, магистранты
аспиранты
Подразделение
[Кафедра математической логики и теории алгоритмов]
Семестр
Осень
Тип спецкурса
Спецкурс по выбору кафедры
Учебный год
2025/26
Список тем
Классическая логика высказываний.
Интуиционистская логика высказываний.
Логика предикатов.
Теорема Геделя о полноте.
Список источников
W. Rautenberg. A concise introduction to mathematical logic. Springer, 2010.
В. Е. Плиско, В. Х. Хаханян. Интуиционистская логика. — М.: Изд-во при мех.-мат. ф-те МГУ, 2009.
Дополнительная информация

Спецкурс является обязательным для студентов 3 курса кафедры математической логики и теории алгоритмов.

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

Математические методы анализа данных, II

Название спецкурса на английском языке
Mathematical methods of data analysis, II
Авторы курса
Любецкий Василий Александрович
Пререквизиты
Отсутствуют
Целевая аудитория
1-2 курс
3-6 курс, магистранты
аспиранты
Подразделение
[Кафедра математической логики и теории алгоритмов]
Семестр
Осень
Тип спецкурса
Спецкурс по выбору кафедры
Учебный год
2025/26
Список тем
Постановка задачи об оптимальном преобразовании одного ориентированного нагруженного графа в другой наперёд заданными операциями над графами. Каждая операция имеет свою цену и минимизируется суммарная цена последовательности операций, которая преобразуем один данный граф в другой.
Постановка задачи об оптимальной эволюции вдоль дерева (ациклической сети): даны данные в листьях дерева и ищутся данные в нелистовых вершинах. Один из подходов основан на марковской (или близкой к ней) эволюции.
Постановка задачи о классификации данного множества точек в многомерном вещественном пространстве (иными словами, столбцов неотрицательной числовой матрицы данных). Минимизируется функционал, который накладывает условие на искомую кластеризацию: для каждого её кластера, «близость» точек внутри него значимо больше, чем близость точек кластера к точкам вне кластера. Оставшаяся часть курса обсуждает эту задачу кластеризации.
Удаление скрытых параметров в данных. Преобразование данных, приводящее к минимальной зависимости дисперсии строки данной матрицы от среднего строки.
Выбор характерных для кластеризации строк матрицы.
Переход к оптимальным и наиболее информативным координатам исходных точек, т.е. к новым координатам столбцов.
Переход к графу: вершины – исходные точки, рёбра соединяют вершины, у которых окрестности вершин пересекаются, и рёбрам приписаны ранговые веса.
Максимизация функции модулярности, аргумент которой – переменная кластеризация вершин (=точек) графа.
Алгоритм такой максимизации.
Выбор индивидуальных признаков каждого кластера в оптимальной кластеризации.
Понижение размерности исходных данных (матрица типично имеет более 30 тысяч строк 50 тысяч столбцов; возможно понижение размерности пространства до значения 2).
Список источников
Butler A, Hoffman P, Smibert P, Papalexi E, Satija R. Integrating data across different conditions, technologies, and species. Nat Biotechnol. 2018 Jun;36(5):411-420. doi:10.1038/nbt.4096. Epub 2018 Apr 2 PMID: 29608179; PMCID: PMC6700744.
Дополнительная информация

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

Страница спецкурса: http://logic.math.msu.ru/staff/lyubetsky/mmdp/. 

Cлушатели должны зарегистрироваться по адресу gorbunov@iitp.ru, сообщив о себе: ФИО полностью, факультет, группу, свой email и мобильный.

Компьютерная обработка больших данных — универсальное направление исследований буквально во всех областях естественных и гуманитарных наук. В тоже время такая обработка опирается на методы современной математики, от алгоритмов до геометрии. Используемые здесь методы/алгоритмы в основном эвристические, интуитивно построенные, для которых почти неизвестны доказательства их правильности. Более того, обычно не существует даже математической постановки задачи, решаемой таким эвристическим алгоритмом; сама эта задача понимается интуитивно, на основе компьютерных экспериментов и опыта применения в данной прикладной области. Будет рассказан, так называемый, метод Seurat, широко применяемый в разных прикладных задачах и особенно в биоинформатике. Будут обсуждаться проблемы его обоснования, далёкие от математического решения. Будут предложены компьютерные вычислительные программистские математические задачи, как и реально прикладные, для курсовых и дипломных работ; для аспирантских тем. Никакие предварительные знания не предполагаются; все необходимые сообщаются на лекциях. После каждой лекции предполагается факультативный семинар и обсуждение задач.

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

Односторонние функции и их применения

Название спецкурса на английском языке
One-way functions and their applications
Авторы курса
Верещагин Николай Константинович
Пререквизиты
Отсутствуют
Целевая аудитория
3-6 курс, магистранты
аспиранты
Подразделение
[Кафедра математической логики и теории алгоритмов]
Семестр
Осень
Тип спецкурса
Спецкурс по выбору кафедры
Учебный год
2025/26
Список тем
Односторонние функции (сильно и слабо). Теорема Левина - Гольдрайха о преобразовании слабо односторонней функции в сильно одностороннюю. Обобщение понятия односторонней функции --- частичные односторонние функции (с равномерным распределением). Односторонние перестановки. Функция Рабина, функция RSA, дискретная экспонента.
Статистически и вычислительно неотличимые случайные величины. Свойства вычислительно неотличимых случайных величин. Полиномиально генерируемые и доступные последовательности случайных величин. Генераторы псевдослучайных чисел (ПСЧ). Слабая необратимость генераторов ПСЧ.
Понятие трудного бита для данной функции. Лемма о трудном бите (конкатенация значения функции и трудного бита неотличима от конкатенации значения функции и случайного бита).
Построение генератора ПСЧ, исходя из односторонней перестановки с трудным битом.
Теорема о вероятностном декодировании списком кода Адамара.
Теорема Левина-Гольдрайха о трудном бите для односторонних функций (доказательство по модулю теоремы о вероятностном декодировании списком кода Адамара).
Семейства псевдослучайных функций (ПСФ). Сильный и слабый варианты определения. Построение псевдослучайных функций исходя из генератора ПСЧ.
Односторонние перестановки с секретом (trapdoor permutations). Примеры. Трудный бит для необратимой перестановки с секретом.
Одноразовые схемы шифрования с закрытым ключом (СШЗК, симметричные схемы). Построение СШЗК на основе генератора ПСЧ.
Многоразовые схемы шифрования с закрытым ключом. Построение многоразовой СШЗК на основе семейства ПСФ и одноразовой СШЗК.
Схемы шифрования с открытым ключом (ШОК, асимметричные схемы). Конструкция ШОК на основе необратимой перестановки с секретом. Неинтерактивные протоколы привязки к биту (НПБ). Построение НПБ на основе односторонней перестановки.
Интерактивные алгоритмы. Интерактивные протоколы привязки к биту (ИПБ). Построение ИПБ на основе генератора ПСЧ. Протоколы бросания монетки. Построение таких протоколов на основе протокола привязки к биту.
Список источников
Введение в криптографию. Под общей редакцией В.В.Ященко. ---
3-е изд. доп. --- М.: МЦНМО: "ЧеРо", 2000. --- 288 с.


М.И. Анохин, Н.П.Варновский, В.М.Сидельников, В.В. Ященко.
Криптография в банковском деле. М.: МИФИ, 1997.


O. Goldreich.
Foundations of cryptography. Basic tools.
Cambridge Univ. Press. 2001. 400 p.


O. Goldreich.
Foundations of cryptography. Basic applications.
Cambridge Univ. Press. 2004
День недели
вторник
Время
16:45-18:20
Аудитория
1408
Дата первого занятия
Аудитория первого занятия
Ещё не назначена
Статус курса
Запись открыта
Форма записи на курс
Заполнение формы записи на курс доступно только студентам. Для записи на курс авторизуйтесь, пожалуйста, в студенческом аккаунте.

Коды с исправлением ошибок

Название спецкурса на английском языке
Error correcting codes
Авторы курса
Верещагин Николай Константинович
Пререквизиты
Отсутствуют
Целевая аудитория
3-6 курс, магистранты
аспиранты
Подразделение
[Кафедра математической логики и теории алгоритмов]
Семестр
Осень
Тип спецкурса
Спецкурс по выбору студента на английском языке
Учебный год
2025/26
Список тем
Кодовые слова, размерность, минимальное расстояние кодов.
Количество исправленных ошибок и стираний. Код Хэмминга [n-1,n,2].
Граница Хэмминга. Граница Гилберта.
Формула для объема шара Хэмминга. Функция Шеннона.
Линейные коды.
Граница Варшамова-Гилберта.
Коды Возенкрафта.
Коды Хэмминга.
Граница Синглтона. Коды Рида-Соломона.
Каскадные коды. Коды Форни. Коды Форни-Юстесена-Возенкрафта
Границы Плоткина и улучшение границы Синглтона.
Коды Адамара.
Код Рида — Маллера.
Коды БЧХ.
Декодирование списком с исправлением ошибок. Общие границы.
Декодирование списком и минимальное расстояние.
Декодирование списком с исправлением n-sqrt{n(n-d)} ошибок для кода Рида-Соломона.
Декодирование списка с (1-eps)/2 ошибками для кода Адамара
Теорема Голдрайха-Левина
Список источников
А. Ромащенко, А. Румянцев и А. Шень, Заметки по теории кодирования, МЦНМО, 2011.
Дополнительная информация

Страничка курса в Телеграме https://t.me/+7w1cLI5fA9Q1ZmYy 

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

Конструктивная логика

Название спецкурса на английском языке
Constructive logic
Авторы курса
Плиско Валерий Егорович
Пререквизиты
Отсутствуют
Целевая аудитория
1-2 курс
3-6 курс, магистранты
аспиранты
Подразделение
[Кафедра математической логики и теории алгоритмов]
Семестр
Полгода (весна)
Тип курса
Спецкурс по выбору кафедры
Учебный год
2024/25
Список тем
Интуиционистская логика
Теория алгоритмов
Конструктивные интерпретации логических и логико-математических языков
Список источников
В.Е.Плиско, В.Х.Хаханян, Интуиционистская логика. М.: Мехмат МГУ, 2009.
В.Е.Плиско, Лекции по конструктивной логике. М.: Луч, 2021.
День недели
пятница
Время
18:30-20:05
Аудитория
425
Дата первого занятия
Аудитория первого занятия
Ещё не назначена

Сложность вычислений

Название спецкурса на английском языке
Computational complexity
Авторы курса
Верещагин Николай Константинович
Пререквизиты
Отсутствуют
Целевая аудитория
3-6 курс, магистранты
аспиранты
Подразделение
[Кафедра математической логики и теории алгоритмов]
Семестр
Полгода (весна)
Тип курса
Спецкурс по выбору кафедры
Учебный год
2024/25
Список тем
Теорема Фишера–Рабина об экспоненциальной нижней оценки времени разрешения элементарной теории поля действительных чисел.
Класс NP. NP полные и NP трудные задачи. Теорема Кука — Левина об NP-полноте проблемы выполнимости.
Вероятностные полиномиальные алгоритмы. Класс BPP. Уменьшение вероятности ошибки и вложение класса BPP в класс P/poly.
Список источников
M. Гэри, Д. Джонсон. Вычислительные машины и труднорешаемые задачи. М.: Мир, 1982.
A. Китаев, А. Шень, М. Вялый. Классические и квантовые вычисления. М.: МЦНМО, ЧеРо, 1999.
Т. Кормен, Ч. Лейзерсон, Р. Ривест. Алгоритмы: построение и анализ. М.: МЦНМО, 2001.
День недели
вторник
Время
18:30-20:05
Аудитория
424
Аудитория первого занятия
424
Подписаться на [Кафедра математической логики и теории алгоритмов]