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

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

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

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

Синтез управляющих систем. Часть II

Название спецкурса на английском языке
Complexity of circuit computings. Part II
Авторы курса
Кочергин Вадим Васильевич
Пререквизиты
Отсутствуют
Целевая аудитория
3-6 курс, магистранты
аспиранты
Подразделение
[Кафедра дискретной математики]
Семестр
Весна
Тип спецкурса
Спецкурс по выбору кафедры
Учебный год
2025/26
Список тем
Трудности получения эффективных нижних оценок сложности для индивидуальных последовательностей функций. Теорема Яблонского о невозможности элиминации перебора при построении последовательности самых сложных функций. Нетривиальные линейные оценки в классе схем из функциональных элементов.
Контактные схемы. Физическая модель. Сложность контактных схем. Контактное дерево для системы конъюнкций. Минимальность контактного дерева в классе разделительных схем.
Метод каскадов. Наилучший по порядку метод синтеза схем на основе метода каскадов. Реализация линейной функции методом каскадов.
Разбиение наборов длины $2^m$ на непересекающиеся сферы. Асимптотически оптимальная реализация системы всех конъюнкций.
Мощностная нижняя оценка функции Шеннона сложности реализации булевых функций контактными схемами.
Асимптотически наилучший метод О. Б. Лупанова синтеза контактных схем. Корректирование одного замыкания или размыкания без асимптотического увеличения сложности.
Сложность формул как число символов переменных и как число функциональных символов. Мощностная нижняя оценка функции Шеннона сложности реализации булевых функций формулами (для двух определений сложности формулы).
Параллельно-последовательные контактные схемы, их связь с формулами в базисе $\{ \vee, \&, - \}$.Асимптотически наилучший метод О. Б. Лупанова синтеза параллельно-последовательных контактных схем.
Сложность реализации функции, принимающей единичное значение на наборах с одной единицей, контактными схемами. Теорема Кардо о сложности реализации линейной функции контактными схемами.
Метод Б. А. Субботовской получения нижних оценок сложности реализации булевых функций в классе параллельно-последовательных контактных схем. Нижняя оценка сложности линейных функций по методу Субботовской.
Метод В. М. Храпченко. Простые цепи и тупиковые сечения в параллельно-последовательных контактных схемах и их свойства. Теорема Храпченко о нижней оценке сложности реализации булевой функции в классе параллельно-последовательных контактных схем. Нижняя квадратичная оценка сложности реализации линейных функций.
Метод Э. И. Нечипорука получения нижних оценок сложности реализации булевых функций формулами в произвольном конечном базисе. Функция Нечипорука и нижняя оценка ее сложности при реализации формулами в произвольном конечном базисе.
Список источников
Лупанов О. Б. О синтезе некоторых классов управляющих систем // Проблемы кибернетики, вып. 10. --- М.: Физматгиз, 1963. --- C 63--97.
Лупанов О. Б. Об одном подходе к синтезу управляющих систем --- принципе локального кодирования // Проблемы кибернетики, вып. 14. --- М.: Наука, 1965.~--- C. 31--110.
Лупанов О. Б. Асимптотические оценки сложности управляющих
систем. --- М.: Изд-во Московского университета, 1984 (1-е издание); 2024 (2-е издание).
Яблонский С. В. Элементы математической кибернетики. --- М.: Высшая школа, 2007.
Нигматуллин Р. Г. Сложность булевых функций. --- М.: Наука, 1991.
Сэвидж Д. Е. Сложность вычислений. --- М.: Факториал, 1998.
День недели
вторник
Время
18:30-20:05
Аудитория
1213
Дата первого занятия
Аудитория первого занятия
1213
Статус курса
Запись открыта
Форма записи на курс
Заполнение формы записи на курс доступно только студентам. Для записи на курс авторизуйтесь, пожалуйста, в студенческом аккаунте.

Неявные формы выразимости в многозначных логиках

Название спецкурса на английском языке
Implicit types of expressibility in many-valued logics
Авторы курса
Старостин Михаил Васильевич
Пререквизиты
Курс ТДФ, а именно, знакомство со следующими понятиями: булева функция, суперпозиция, замкнутый класс, функция многозначной логики
Целевая аудитория
3-6 курс, магистранты
Подразделение
[Кафедра дискретной математики]
Семестр
Осень
Тип спецкурса
Спецкурс по выбору кафедры
Учебный год
2025/26
Список тем
Неявная выразимость. Параметрическая выразимость. Неэквивалентность неявной и
параметрической выразимости в P_k при k ⩾ 3.
Рефлексивность и монотонность оператора неявной выразимости. Цепочка вложений операторов выразимости.
Классы сохранения матриц и предикатов.
Централизаторы и бицентрализаторы. Централизатор как класс сохранения предиката.
Описание 25 параметрически замкнутых классов в P_2.
Эквивалентность неявной и параметрической выразимости в P_2.
Минимальные неявно полные классы без констант в P_3.
Критерий неявной полноты в P_k.
Список источников
Кузнецов А. В. О средствах для обнаружения невыводимости или невыразимости //Логический вывод. — М.:Наука, 1979. — С. 5–33
Касим-Заде О. М. О неявной выразимости булевых функций // Вестник МГУ. Серия 1. Математика. Механика. — 1995. — №2. — С. 44–49.
Марченков С. С. Основы теории булевых функций. М.: ФИЗМАТЛИТ, 2014, 136 с.
Орехова Е. А. Об одном критерии неявной полноты в трёхзначной логике // Математические вопросы кибернетики. — 2003. — Вып. 12 — С. 27-74.
Касим-Заде О. М. О неявной полноте в k-значной логике // Вестник МГУ. Серия 1. Математика. Механика. — 2007. — №3. — С. 9–13.
День недели
вторник
Время
16:45-18:20
Аудитория
Ещё не назначена
Дата первого занятия
Аудитория первого занятия
Ещё не назначена
Статус курса
Запись открыта
Форма записи на курс
Заполнение формы записи на курс доступно только студентам. Для записи на курс авторизуйтесь, пожалуйста, в студенческом аккаунте.

Сложность булевых функций

Название спецкурса на английском языке
Boolean complexity
Авторы курса
Чашкин Александр Викторович
Пререквизиты
Отсутствуют
Целевая аудитория
1-2 курс
3-6 курс, магистранты
аспиранты
Подразделение
[Кафедра дискретной математики]
Семестр
Осень
Тип спецкурса
Спецкурс по выбору кафедры
Учебный год
2025/26
Список тем
Реализация булевых функций формулами, схемами, автоматами и машинами Тьюринга. Сложность функции.
Сложность систем линейных булевых функций.
Оценки сложности и глубины вычисления префиксных сумм.
Оценки сложности и глубины арифметических операций над целыми числами.
Оценки сложности быстрого преобразования Фурье и умножения многочленов. Асимптотические методы реализации булевых функций схемами и формулами.
Оценки сложности вычисления монотонных булевых функций.
Вычисления с ограниченной памятью.
Схемы на плоскости и их сложность (площадь).
Схемы в 3-х мерном пространстве и их сложность (объем).
Самокорректирующиеся схемы.
Моделирование схем автоматами и машинами Тьюринга.
Теорема Кука. NP-полные задачи.
Список источников
Чашкин А. В. Дискретная математика. М.: Academia, 2012.
Блейхут Р. Быстрые алгоритмы цифровой обработки сигналов. М.: Мир, 1989.
Savage John E. Models of Computation: Exploring the Power of Computing. Addison-Wesley, 1997.
День недели
по согласованию
Время
по согласованию
Аудитория
Ещё не назначена
Аудитория первого занятия
Ещё не назначена
Статус курса
Запись открыта
Форма записи на курс
Заполнение формы записи на курс доступно только студентам. Для записи на курс авторизуйтесь, пожалуйста, в студенческом аккаунте.

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

Название спецкурса на английском языке
Analysis of boolean functions and related issues. 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., 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.
Дополнительная информация

Связь с лектором по эл. почте yutarann@gmail.com

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