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

Название спецкурса на английском языке
Error correcting codes
Авторы курса
Верещагин Николай Константинович
Пререквизиты
Отсутствуют
Целевая аудитория
3-6 курс, магистранты
Подразделение
[Кафедра математической логики и теории алгоритмов]
Семестр
Осень
Тип спецкурса
Спецкурс по выбору студента на английском языке
Учебный год
2026/27
Список тем
Постановка задачи и основные границы. Канал с ошибками и стираниями Код: алфавит, размерность, длина блока, минимальное кодовое расстояние. Связь расстояния с числом исправляемых ошибок. Скорость и относительное расстояние. Граница Синглтона. Граница Хэмминга. Объём шара Хэмминга, функция Шеннона, асимптотический вид границ для двоичного и произвольного алфавита. Граница Гилберта; граница Варшамова—Гилберта и жадный алгоритм.
Линейные коды и классические конструкции. Линейные коды. Коды Рида—Соломона и их декодирование от ошибок. Коды Хэмминга $[2^m-1,2^m-m-1,3]_2$ и $[2^m,2^m-m-1,4]_2$, кодирование и декодирование. Случайные линейные коды. Коды Возенкрафта. Коды Рида—Маллера и их кодовое расстояние. Коды БЧХ; связь БЧХ с кодами Хэмминга.
Каскадные коды и явные асимптотически хорошие коды. Каскадное кодирование. Полиномиальное декодирование каскадных кодов от $(d-1)/2$ ошибок. Теорема Форни. Коды Форни—Возенкрафта—Юстесена. Коды с малой плотностью проверок на чётность (LDPC) и их связь с экспандерами.
Верхние границы параметров кода. Геометрические леммы для границ Плоткина. Первая граница Плоткина. Вторая граница Плоткина для двоичного и для произвольного алфавита. Улучшенная граница Синглтона. Граница Джонсона. Граница Элайеса—Бассалыго.
Декодирование списком и локальные алгоритмы. Коды Адамара и расширенные коды Адамара; рандомизированное декодирование за время $\mathrm{poly}(\log n)$. Декодирование списком: определение, объёмная граница, теорема Элайеса как достаточное условие. Кодовое расстояние и декодирование списком. Декодирование списком кодов Адамара со списком постоянного размера; теорема Голдрайха—Левина. Декодирование списком кодов Рида—Соломона. Композиция Рида—Соломона с Адамаром и её декодирование списком.
Список источников
А. Е. Ромащенко, А. Ю. Румянцев, А. Шень. Заметки по теории кодирования. МЦНМО, Москва, 2011; 2-е изд., испр. и доп., 2017. — Основа конспекта курса; написана по материалам лекций М. Судана в MIT.
Н. К. Верещагин. Конспект лекций «Коды с исправлением ошибок». Рукопись
V. Guruswami, A. Rudra, M. Sudan. Essential Coding Theory. Книга, черновик доступен онлайн. — Ближе всего к программе курса: границы Плоткина, Элайеса—Бассалыго, Джонсона, каскадные коды, декодирование списком, экспандерные коды.
F. J. MacWilliams, N. J. A. Sloane. The Theory of Error-Correcting Codes. North-Holland, 1977.
R. M. Roth. Introduction to Coding Theory. Cambridge University Press, 2006.
V. Guruswami. List Decoding of Error-Correcting Codes. Lecture Notes in Computer Science, vol. 3282, Springer, 2004.
Дополнительная информация

Страничка курса в Телеграме t.me/+7w1cLI5fA.... с полной информацией о курсе

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

Теория информации

Название спецкурса на английском языке
Information theory
Авторы курса
Верещагин Николай Константинович
Пререквизиты
Отсутствуют
Целевая аудитория
3-6 курс, магистранты
аспиранты
Подразделение
[Кафедра математической логики и теории алгоритмов]
Семестр
Осень
Тип спецкурса
Спецкурс по выбору кафедры
Учебный год
2026/27
Список тем
Энтропия и оптимальное кодирование. Информация по Хартли; префиксное кодирование и неравенство Крафта–Макмиллана; энтропия Шеннона как оценка средней длины кода; код Фано и арифметическое кодирование.
Информационные неравенства и их комбинаторные приложения. Условная энтропия и цепное правило; метод релятивизации; неравенства Шерера, Лумиса–Уитни и Ромащенко–Каседа; теорема Шеннона об идеальном шифре и неравенство Фано.
Передача информации. Теорема Шеннона о бесшумном канале; теорема Вольфа–Слепяна; каналы с шумом и их пропускная способность.
Предсказание и обучение. Игры предсказания битов и мартингалы; предсказание c экспертами: логарифмический штраф и предсказатель Соломонова, выпуклые штрафы и условие Блэквелла; PAC-обучение и размерность Вапника–Червоненкиса.
Список источников
Н. К. Верещагин, Е. В. Щепин. Информация, кодирование и предсказание. М.:
МЦНМО, 2012.
А. М. Яглом, И. М. Яглом. Вероятность и информация. М.: Наука.
Дополнительная информация

Чат в Телеграмме с полной информацией о курсе https://t.me/+bIR53NvrzrM2NTYy

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

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

Название спецкурса на английском языке
Advanced data processing techniques, II
Авторы курса
Любецкий Василий Александрович
Пререквизиты
Отсутствуют
Целевая аудитория
1-2 курс
3-6 курс, магистранты
аспиранты
Подразделение
[Кафедра математической логики и теории алгоритмов]
Семестр
Весна
Тип спецкурса
Спецкурс по выбору кафедры
Учебный год
2026/27
Список тем
Эволюция как цепь Маркова в наблюдаемом множестве точек многомерного вещественного пространства.
Определение kNN-графа для таких точек.
Построение близости состояний цепи с помощью гауссова ядра.
Понижения размерности с помощью собственных векторов и переход к диффузионному расстоянию.
Построение переходной матрицы цепи Маркова.
Псевдовремя в множестве состояний цепи.
Метастабильные состояния эволюции.
Макросостояния эволюции для обратимой и необратимой цепей Маркова.
Терминальные макросостояния в эволюции.
Матрица судьбы состояний цепи.
Характерные признаки данного макросостояния.
Драйверные признаки макросостояния.
Связь кластеров и макросостояний.
Список источников
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.
Fackeldey, K., Sikorski, A. & Weber, M. Spectral clustering for non-reversible Markov chains. Comp. Appl. Math. 37, 6376–6391 (2018). https://doi.org/10.1007/s40314-018-0697-0
Дополнительная информация

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

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

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

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

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

Название спецкурса на английском языке
Advanced data processing techniques, I
Авторы курса
Любецкий Василий Александрович
Пререквизиты
Отсутствуют
Целевая аудитория
1-2 курс
3-6 курс, магистранты
аспиранты
Подразделение
[Кафедра математической логики и теории алгоритмов]
Семестр
Осень
Тип спецкурса
Спецкурс по выбору кафедры
Учебный год
2026/27
Список тем
Концепция сжатия данных. Задача об оптимальном преобразовании одного ориентированного нагруженного графа в другой наперёд заданными операциями над графами. Каждая операция имеет заданную цену. При этом минимизируется суммарная цена последовательности операций, которые преобразуют данные графы, один в другой.
Задача об оптимальной эволюции вдоль дерева (ациклической сети): данные в листьях дерева реконстрируются в нелистовых вершинах.
Дискретная эволюция как марковская (или близкая к ней) цепь.
Задача о классификации данного множества точек в многомерном вещественном пространстве (иными словами, столбцов неотрицательной числовой матрицы данных). Минимизируется функционал, который выражает, что для каждого кластера «близость» точек внутри него значимо больше, чем близость точек из кластера к точкам вне кластера.
В данных удаление скрытых параметров. Преобразование данных, приводящее к минимальной зависимости для строки её дисперсии от её среднего.
Выбор характерных признаков для кластеризации.
Переход к оптимальным и информативным координатам исходных точек.
Переход к графу kNN: вершины – исходные точки, рёбра соединяют вершины, у которых окрестности вершин пересекаются, а рёбрам приписаны ранговые веса.
Максимизация функции модулярности, аргумент которой – текущая кластеризация вершин графа.
Алгоритм такой максимизации.
Характерные признаки кластера в оптимальной кластеризации.
Понижение размерности исходных данных до плоскости (матрица типично имеет более 30 тысяч строк и более 50 тысяч столбцов).
Список источников
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.
Fackeldey, K., Sikorski, A. & Weber, M. Spectral clustering for non-reversible Markov chains. Comp. Appl. Math. 37, 6376–6391 (2018). https://doi.org/10.1007/s40314-018-0697-0
Дополнительная информация

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

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

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

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

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

Название спецкурса на английском языке
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-го семестров), так и как «полугодовой» (материал весеннего семестра). Эта тема нуждается в компьютерной программе, и широко востребована в мировой практике.

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

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

Название спецкурса на английском языке
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
Аудитория
Ещё не назначена
Дата первого занятия
Аудитория первого занятия
Ещё не назначена
Статус курса
Запись открыта
Форма записи на курс
Заполнение формы записи на курс доступно только студентам. Для записи на курс авторизуйтесь, пожалуйста, в студенческом аккаунте.
Подписаться на [Кафедра математической логики и теории алгоритмов]