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

Название спецкурса на английском языке
Combinatorial designs
Авторы курса
Таранников Юрий Валерьевич
Пререквизиты
Знание основных свойств конечных полей.
Целевая аудитория
1-2 курс
3-6 курс, магистранты
аспиранты
Подразделение
[Кафедра дискретной математики]
Семестр
Весна
Тип спецкурса
Спецкурс по выбору студента
Учебный год
2025/26
Список тем
Блок-дизайны и t-дизайны.
Конечные геометрии.
Матрицы Адамара.
Латинские квадраты.
Трансверсальные дизайны.
Ортогональные массивы.
Связь с линейными кодами.
Разностные множества.
Корреляционно-иммунные и бент-функции.
Вист-турниры.
Список источников
Таранников Ю. В. Комбинаторные свойства дискретных структур и приложения к
криптологии. М.: МЦНМО, 2011.
Hedayat A. S., Sloane N. J. A., Stufken , J. Orthogonal arrays. Theory and applications. Springer-Verlag, 1999.
Handbook of Combinatorial Designs. 2nd Edition by Colbourn C. J., Dinitz J. H (Eds). Chapman and Hall/CRC, 2007.
День недели
по согласованию
Время
по согласованию
Аудитория
Ещё не назначена
Аудитория первого занятия
Ещё не назначена
Статус курса
Запись открыта
Форма записи на курс
Заполнение формы записи на курс доступно только студентам. Для записи на курс авторизуйтесь, пожалуйста, в студенческом аккаунте.

Анализ булевых функций и приложения. II

Название спецкурса на английском языке
Analysis of boolean functions and related issues. II
Авторы курса
Таранников Юрий Валерьевич
Пререквизиты
Спецкурс "Анализ булевых функций и приложения. I"
Целевая аудитория
1-2 курс
3-6 курс, магистранты
аспиранты
Подразделение
[Кафедра дискретной математики]
Семестр
Весна
Тип спецкурса
Спецкурс по выбору студента
Учебный год
2025/26
Список тем
Преобразование Уолша булевой функции и его свойства.
Полиномиальные представления булевой функции, их свойства и следствия.
Теорема Нисана-Сегеди о максимальном числе существенных переменных и ее усиления.
Теорема Симона-Вегенера и следствия из нее.
Регулярные булевы функции и их свойства.
Сложностные характеристики булевой функции и их взаимосвязь.
Деревья решений.
Приложения анализа булевых функций в теории сложности.
Нелинейность булевых функций.
Корреляционно-иммунные и устойчивые булевы функции.
Приложения анализа булевых функций в криптологии.
Список источников
O’Donnell R. Analysis of boolean functions. Cambridge University Press, 2014.
Wegener I., The complexity of boolean functions, Wiley-Teubner Series in Computer Science, Teubner, Stuttgart, 1987.
Carlet C. Boolean functions for cryptography and coding theory. Cambridge University Press, 2021.
Таранников Ю. В. О корреляционно-иммунных и устойчивых булевых функциях. Математические вопросы кибернетики, 2002, вып. 11, с. 91-148.
Nisan N., Szegedy M. On the degree of boolean functions as real polynomials, Computational Complexity 4 (1994), p. 301-313.
Chiarelli J., Hatami P., Saks M., An asymptotically tight bound on the number of relevant variables in a bounded degree boolean function, Combinatorica 40 (2020), p. 237-244.
Wellens J., Relationships between the number of inputs and other complexity measures of boolean functions, arXiv:2005.00566v2, 2022.
Huang H. Induced subgraphs of hypercubes and a proof of the sensitivity conjecture, arXiv:1907.00847v2, 2019.
Nisan N., CREW PRAMs and decision trees, SIAM J. Comput. 20 (6) (1991), p. 999 -1007.
Rubinstein D., Sensitivity vs. block sensitivity of Boolean functions, Combinatorica 15 (2) (1995), p. 297-299.
Buhrman H., de Wolf R. Complexity measures and decision tree complexity: a survey, Theoretical Computer Science 288 (2002), p. 21-43.
День недели
по согласованию
Время
по согласованию
Аудитория
Ещё не назначена
Аудитория первого занятия
Ещё не назначена
Статус курса
Запись открыта
Форма записи на курс
Заполнение формы записи на курс доступно только студентам. Для записи на курс авторизуйтесь, пожалуйста, в студенческом аккаунте.

Избранные вопросы анализа булевых функций

Название спецкурса на английском языке
Selected problems of the analysis of Boolean functions
Авторы курса
Таранников Юрий Валерьевич
Пререквизиты
Базовые знания математического анализа, линейной и высшей алгебры.
Целевая аудитория
1-2 курс
3-6 курс, магистранты
аспиранты
Подразделение
[Кафедра дискретной математики]
Семестр
Весна
Тип спецкурса
Спецкурс по выбору кафедры
Учебный год
2025/26
Список тем
Преобразование Уолша булевой функции и его свойства.
Полиномиальные представления булевой функции, их свойства и следствия.
Теорема Нисана-Сегеди о максимальном числе существенных переменных и ее усиления.
Теорема Симона-Вегенера и следствия из нее.
Регулярные булевы функции и их свойства.
Сложностные характеристики булевой функции и их взаимосвязь.
Список источников
O’Donnell R. Analysis of boolean functions. Cambridge University Press, 2014.
Wegener I., The complexity of boolean functions, Wiley-Teubner Series in Computer Science, Teubner, Stuttgart, 1987.
Carlet C. Boolean functions for cryptography and coding theory. Cambridge University Press, 2021.
Таранников Ю. В. О корреляционно-иммунных и устойчивых булевых функциях. Математические вопросы кибернетики, 2002, вып. 11, с. 91-148.
Nisan N., Szegedy M. On the degree of boolean functions as real polynomials, Computational Complexity 4 (1994), p. 301-313.
Chiarelli J., Hatami P., Saks M., An asymptotically tight bound on the number of relevant variables in a bounded degree boolean function, Combinatorica 40 (2020), p. 237-244.
Wellens J., Relationships between the number of inputs and other complexity measures of boolean functions, arXiv:2005.00566v2, 2022.
Huang H. Induced subgraphs of hypercubes and a proof of the sensitivity conjecture, arXiv:1907.00847v2, 2019.
Nisan N., CREW PRAMs and decision trees, SIAM J. Comput. 20 (6) (1991), p. 999 -1007.
Rubinstein D., Sensitivity vs. block sensitivity of Boolean functions, Combinatorica 15 (2) (1995), p. 297-299.
Buhrman H., de Wolf R. Complexity measures and decision tree complexity: a survey, Theoretical Computer Science 288 (2002), p. 21-43.
День недели
по согласованию
Время
по согласованию
Аудитория
Ещё не назначена
Аудитория первого занятия
Ещё не назначена
Статус курса
Запись открыта
Форма записи на курс
Заполнение формы записи на курс доступно только студентам. Для записи на курс авторизуйтесь, пожалуйста, в студенческом аккаунте.

Геометрия и механика стержневых и многогранных структур

Название спецкурса на английском языке
Geometry and mechanics of rode and polyhedral structures
Авторы курса
Ковалёв Михаил Дмитриевич
Пререквизиты
Дисциплины, изучаемые на первом и втором курсах механико-математического факультета.
Целевая аудитория
3-6 курс, магистранты
аспиранты
Подразделение
[Кафедра дискретной математики]
Семестр
Весна
Тип спецкурса
Спецкурс по выбору студента
Учебный год
2025/26
Список тем
Изгибаемость и жёсткость идеальных структур трёхмерного евклидова пространства.
Теорема Лежандра- Коши об определённости выпуклых многогранников их гранями.
Теорема Максвелла о внутреннем напряжении в рёберном скелете проекции многогранника.
Проективная инвариантность статических свойств.
Геометрическая теория шарнирных механизмов и ферм.
Теория напряжённосвязанных конструкций (tensegrity frameworks).
Список источников
Учебник: Ковалёв М. Д. "Геометрические вопросы кинематики и статики", Ленанд, 2019.
Переработанное издание Ковалёв М. Д. "Геометрические вопросы кинематики и статики", Издательство МГУ, 2025
Дополнительная информация

Материал курса с одной стороны нагляден и важен для механики, в частности строительной механики, с другой стороны интересен с математической стороны тем, что в этой классической области возникают новые  содержательные вопросы.  Приводимых сведений достаточно для начала самостоятельного исследования, поднимаемых в курсе вопросов. 

Связь с лектором по электронной почте mkov@rambler.ru

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

Геометрические вопросы кинематики и статики

Название спецкурса на английском языке
Geometric questions of kinematics and statics
Авторы курса
Ковалёв Михаил Дмитриевич
Пререквизиты
Аналитическая геометрия и линейная алгебра, математический анализ, алгебра, теория графов, элементы топологии.
Целевая аудитория
3-6 курс, магистранты
аспиранты
Подразделение
[Кафедра дискретной математики]
Семестр
Весна
Тип спецкурса
Спецкурс по выбору студента
Учебный год
2025/26
Список тем
Основы кинематики и статики твёрдых тел.
Математические основы робототехники, теории механизмов и строительной механики.
Кинематика и статика совокупностей твёрдых тел в проективном изложении.
Введение в вещественную алгебраическую геометрию.
Список источников
Учебник: Ковалёв М. Д. "Геометрические вопросы кинематики и статики", Ленанд, 2019
Переработанное издание Ковалёв М. Д. "Геометрические вопросы кинематики и статики", Издательство МГУ, 2025
Дополнительная информация

Материал курса с одной стороны нагляден и важен для механики, с другой стороны интересен с математической стороны тем, что в этой классической области возникают новые  содержательные вопросы.  Приводимых сведений достаточно для начала самостоятельного исследования, поднимаемых в курсе вопросов. 

Связь с лектором по электронной почте mkov@rambler.ru

 

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

Введение в дискретную геометрию

Название спецкурса на английском языке
Introduction to discrete geometry
Авторы курса
Ковалёв Михаил Дмитриевич
Пререквизиты
Отсутствуют
Целевая аудитория
1-2 курс
3-6 курс, магистранты
Подразделение
[Кафедра дискретной математики]
Семестр
Весна
Тип спецкурса
Спецкурс по выбору студента
Учебный год
2025/26
Список тем
Равномерно дискретные точечные системы в евклидовой плоскости.
Разбиения Делоне и Вороного.
Решётки в евклидовой плоскости.
Параллелоэдры.
Задачи плотнейшей упаковки и редчайшего покрытия евклидовой плоскости равными кругами.
Список источников
Книга С.С.Рышков, Р.Г.Барыкинский, Я.В.Кучериненко Решения основных задач дискретной геометрии в случае плоскости, МГУ, 2000.
День недели
четверг
Время
15:00-16:35
Аудитория
469
Дата первого занятия
Аудитория первого занятия
469
Статус курса
Запись открыта
Форма записи на курс
Заполнение формы записи на курс доступно только студентам. Для записи на курс авторизуйтесь, пожалуйста, в студенческом аккаунте.

Основы теории точечных решёток

Название спецкурса на английском языке
Basics of point lattice theory
Авторы курса
Ковалёв Михаил Дмитриевич
Пререквизиты
Курс линейной алгебры, некоторые сведения из матанализа
Целевая аудитория
3-6 курс, магистранты
аспиранты
Подразделение
[Кафедра дискретной математики]
Семестр
Весна
Тип спецкурса
Спецкурс по выбору кафедры
Учебный год
2025/26
Список тем
Задание точечных решёток в евклидовом пространстве. Решётки и квадратичные формы. Реперы.
Свойства решёток. Леммы Блихфельдта и Минковского.
Подрешётки и центрировки, сечения и проекции решёток.
Минимальные векторы решётки и задача плотнейшей решётчатой упаковки шаров.
Список источников
Книга С.С.Рышков Основы теории точечных решёток и систем Делоне, МГУ, 2014.
День недели
четверг
Время
16:45-18:20
Аудитория
469
Дата первого занятия
Аудитория первого занятия
469
Статус курса
Запись открыта
Форма записи на курс
Заполнение формы записи на курс доступно только студентам. Для записи на курс авторизуйтесь, пожалуйста, в студенческом аккаунте.

Структуры данных для комбинаторного анализа на словах

Название спецкурса на английском языке
Data structures for combinatorial analysis of words
Авторы курса
Колпаков Роман Максимович
Пререквизиты
Отсутствуют
Целевая аудитория
3-6 курс, магистранты
аспиранты
Подразделение
[Кафедра дискретной математики]
Семестр
Весна
Тип спецкурса
Спецкурс по выбору студента
Учебный год
2025/26
Список тем
Эффективные структуры данных (суффиксные деревья, суффиксные массивы и суффиксные автоматы) для комбинаторных алгоритмов на формальных словах и алгоритмы их построения.
Поиск образцов в формальных словах посредством различных структур данных.
Эффективные алгоритмы поиска палиндромов, повторов и периодичностей в формальных словах.
Список источников
M. Crochemore, W. Rytter. Text algorithms / Oxford University Press, 1994.
D. Gusfield. Algorithms on Strings, Trees and Sequences / Cambridge University Press, 1997.
G. Navarro, M. Raffinot. Flexible Pattern Matching in Strings / Cambridge University Press, 2002.
B. Smyth. Computing Patterns in Strings / Pearson Education, 2003.
3rd M.Lothaire volume "Applied Combinatorics on Words", Cambridge University Press, 2005.
День недели
по согласованию
Время
по согласованию
Аудитория
Ещё не назначена
Аудитория первого занятия
Ещё не назначена
Статус курса
Запись открыта
Форма записи на курс
Заполнение формы записи на курс доступно только студентам. Для записи на курс авторизуйтесь, пожалуйста, в студенческом аккаунте.

Введение в математическую кибернетику

Название спецкурса на английском языке
Introduction to mathematical cybernetics
Авторы курса
Колпаков Роман Максимович
Пререквизиты
Отсутствуют
Целевая аудитория
3-6 курс, магистранты
Подразделение
[Кафедра дискретной математики]
Семестр
Весна
Тип спецкурса
Спецкурс по выбору кафедры
Учебный год
2025/26
Список тем
Схемная и формульная сложность реализации булевых функций
Теория автоматов
Алгоритмы сортировки и умножения
Алгоритмы на графах
Список источников
М. Свами, К. Тхуласираман. Графы, сети и алгоритмы / Москва: Мир, 1984.
О.Б. Лупанов. Асимптотические оценки сложности управляющих систем / Москва: Изд-во МГУ, 1984.
Р.Г. Нигматуллин. Сложность булевых функций / Москва: Наука, 1991.
Дж.Э. Сэвидж. Сложность вычислений / Москва: Изд-во "Факториал", 1998.
В.Б. Кудрявцев, С.В. Алешин, А.С. Подколзин. Введение в теорию автоматов / Москва: Наука, 1985.
Г.М. Адельсон-Вельский, Е.М. Ландис. Один алгоритм организации информации / Доклады АН СССР, 1962. Том 146, N 2, с. 263-266.
А. Ахо, Д. Хопкрофт, Д. Ульман. Построение и анализ вычислительных алгоритмов / Москва: Мир, 1979.
Э. Рейнгольд, Ю. Нивергельт, Н. Део. Комбинаторные алгоритмы. Теория и практика. / Москва: Мир, 1980.
День недели
по согласованию
Время
по согласованию
Аудитория
Ещё не назначена
Аудитория первого занятия
Ещё не назначена
Статус курса
Запись открыта
Форма записи на курс
Заполнение формы записи на курс доступно только студентам. Для записи на курс авторизуйтесь, пожалуйста, в студенческом аккаунте.

Алгебраические задачи в теории сложности

Название спецкурса на английском языке
Algebraic problems in complexity theory
Авторы курса
Кочергин Вадим Васильевич
Пререквизиты
Отсутствуют
Целевая аудитория
1-2 курс
3-6 курс, магистранты
Подразделение
[Кафедра дискретной математики]
Семестр
Весна
Тип спецкурса
Спецкурс по выбору кафедры
Учебный год
2025/26
Список тем
Битовая сложность умножения чисел. Быстрые алгоритмы умножения, их особенности.
Задача об эффективном возведении в степень и задача об аддитивных цепочках.
Векторные аддитивные цепочки. Задача Р. Беллмана. Задача Д. Кнута. Двойственность.
Сборка слов схемами конкатенации. Конструктивная нижняя оценка сложности сборки асимптотически самого сложного слова заданной длины.
Задача О. Б. Лупанова о сложности реализации элементов конечных абелевых групп.
Асимптотически точное решение.
Сложность вычисления элементов конечных нильпотентных и разрешимых групп.
Задача Н. Пиппенджера о сложности вычисления систем одночленов от нескольких переменных. Унивесальная нижняя оценка. Простые случаи: два одночлена или две переменные.
Сравнение задачи Пиппенджера и задачи о сложности вычисления систем элементов конечных абелевых групп.
Сложность аддитивных вычислений целочисленных линейных форм.
Задача о сложности вычисления элементов свободных абелевых групп.
Схемы из делений.
Сложность классических и обобщенных вентильных схем.
Список источников
Ахо А., Хопкрофт Д., Ульман Д. Построение и анализ вычислительных алгоритмов. --- Мир, 1979.
Сэвидж Д. Е. Сложность вычислений. --- М.: Факториал, 1998.
Кнут Д. Е. Искусство программирования. Т. 2. 3-е издание. --- М.: Издательский дом <Вильямс>>, 2000 (раздел 4.6.3).
Кочергин В. В. Задачи Беллмана, Кнута, Лупанова, Пиппенджера и их вариации как обобщения задачи об аддитивных цепочках // Математические вопросы кибернетики. Вып. 20. --- М.: ФИЗМАТЛИТ, 2022. --- С. 119–256.
https://keldysh.ru/papers/2022/mvk/mvk2022_119.pdf
Кочергин В. В. О сложности вычислений в конечных абелевых, нильпотентных и разрешимых группах// Дискретная математика. --- Т. 5, вып. 1. --- 1993. --- С. 91--111.
Кочергин В. В. О сложности вычислений в конечных нильпотентных группах // Дискретный анализ и исследование операций. --- 1996. --- Т. 3, No 1. --- С. 43--51.
Кочергин В. В. О максимальной сложности совместного вычисления систем элементов свободной абелевой группы // Вестник Московского университета. Сер. 1. Математика. Механика. --- 2007, No 3. --- С. 14--19.
Кочергин В. В. Сравнение сложности вычисления одночленов и элементов конечных абелевых групп // Вестник Московского университета. Сер. 1. Математика. Механика. --- 2022, No 3. --- С. 6--11.
Кочергин В. В. О сложности вычисления систем элементов конечных абелевых групп // Вестник Московского университета. Сер. 1. Математика. Механика. --- 2023, No 4. --- С. 22--29.
Дополнительная информация

https://keldysh.ru/papers/2022/mvk/mvk2022_119.pdf

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