Синтез управляющих систем. Часть I
Название спецкурса на английском языке
Complexity of circuit computings. Part 1
Пререквизиты
Для слушателей требуются знания курсов ТДФ и матанализа за первый курс
Целевая аудитория
3-6 курс, магистранты
аспиранты
Подразделение
[Кафедра дискретной математики]
Семестр
Осень
Тип спецкурса
Спецкурс по выбору кафедры
Учебный год
2025/26
Список тем
Управляющие системы. Основные модельные классы. Задача синтеза. Асимптотическая постановка задачи оптимального синтеза. Примеры.
Схемы конкатенации. Сложность схем конкатенации. Функция Шеннона. Асимптотически оптимальный метод синтеза схем конкатенации. Мощностная нижняя оценка. Эффект Шеннона. Последовательность де Брейна. Конструктивная нижняя оценка функции Шеннона сложности для схем конкатенации. Асимптотика сложности слова, состоящего только из нулей. Двойственность двух способов доказательства верхней оценки. Сложность класса слов с фиксированным числом единиц.
Вентильные схемы (различные постановки). Асимптотически оптимальный метод синтеза вентильных схем глубины 2. Мощностная нижняя оценка для вентильных схем глубины 2.
Вентильные схемы произвольной глубины. Мощностная нижняя оценка. Асимптотически оптимальный метод синтеза вентильных схем произвольной глубины для квадратных матриц.
Использование аппарата вентильных схем для получения верхних оценок сложности в задачах Р. Беллмана и Д. Кнута. Порядок функции Шеннона реализации вентильными схемами класса булевых матриц с заданной площадью информационной части (<<ступенчатых матриц>>).
Вентильные схемы с кратным числом путей. Асимптотика роста сложности в случае схем с одним входом и одним выходом. Доказательство двойственности задачи о сложности вычисления систем одночленов от многих переменных.
Схемы из функциональных элементов (эквивалентность трех определений), их сложность. Существование правильной нумерации элементов. Эквивалентность базисов. Примеры точных линейных оценок сложности. Реализация системы всех конъюнкций. Реализации системы всех функций от заданных переменных.
Функция Шеннона. Метод Шеннона. Метод каскадов. Реализация симметрических функций.
Асимптотически наилучший метод синтеза О. Б. Лупанова для схем в базисе $\{ \vee, \&, - \}$. Асимптотически наилучший метод, использующий заданное соотношение дизъюнкторов и конъюнкторов.
Лемма о числе неприводимых схем. Мощностная нижняя оценка (с оценкой второго слагаемого в асимптотическом разложении функции Шеннона).
Мощностные нижние оценки для схем в произвольном базисе, для вектор-функций,
для классов функций.
Понятие о методе локального кодирования. Сложность класса самодвойственных функций. Реализация функций на фиксированном числе последовательных наборов.
Инвариантные классы С. В. Яблонского, их свойства. Сложность инвариантных классов. Теорема Яблонского о невозможности элиминации перебора при построении последовательности асимптотически самых сложных функций.
Инверсионная сложность. Теорема Маркова о точном значении инверсионной сложности произвольной системы булевых функций.
Схемы конкатенации. Сложность схем конкатенации. Функция Шеннона. Асимптотически оптимальный метод синтеза схем конкатенации. Мощностная нижняя оценка. Эффект Шеннона. Последовательность де Брейна. Конструктивная нижняя оценка функции Шеннона сложности для схем конкатенации. Асимптотика сложности слова, состоящего только из нулей. Двойственность двух способов доказательства верхней оценки. Сложность класса слов с фиксированным числом единиц.
Вентильные схемы (различные постановки). Асимптотически оптимальный метод синтеза вентильных схем глубины 2. Мощностная нижняя оценка для вентильных схем глубины 2.
Вентильные схемы произвольной глубины. Мощностная нижняя оценка. Асимптотически оптимальный метод синтеза вентильных схем произвольной глубины для квадратных матриц.
Использование аппарата вентильных схем для получения верхних оценок сложности в задачах Р. Беллмана и Д. Кнута. Порядок функции Шеннона реализации вентильными схемами класса булевых матриц с заданной площадью информационной части (<<ступенчатых матриц>>).
Вентильные схемы с кратным числом путей. Асимптотика роста сложности в случае схем с одним входом и одним выходом. Доказательство двойственности задачи о сложности вычисления систем одночленов от многих переменных.
Схемы из функциональных элементов (эквивалентность трех определений), их сложность. Существование правильной нумерации элементов. Эквивалентность базисов. Примеры точных линейных оценок сложности. Реализация системы всех конъюнкций. Реализации системы всех функций от заданных переменных.
Функция Шеннона. Метод Шеннона. Метод каскадов. Реализация симметрических функций.
Асимптотически наилучший метод синтеза О. Б. Лупанова для схем в базисе $\{ \vee, \&, - \}$. Асимптотически наилучший метод, использующий заданное соотношение дизъюнкторов и конъюнкторов.
Лемма о числе неприводимых схем. Мощностная нижняя оценка (с оценкой второго слагаемого в асимптотическом разложении функции Шеннона).
Мощностные нижние оценки для схем в произвольном базисе, для вектор-функций,
для классов функций.
Понятие о методе локального кодирования. Сложность класса самодвойственных функций. Реализация функций на фиксированном числе последовательных наборов.
Инвариантные классы С. В. Яблонского, их свойства. Сложность инвариантных классов. Теорема Яблонского о невозможности элиминации перебора при построении последовательности асимптотически самых сложных функций.
Инверсионная сложность. Теорема Маркова о точном значении инверсионной сложности произвольной системы булевых функций.
Список источников
1. Лупанов О. Б. О синтезе некоторых классов управляющих систем //
Проблемы кибернетики, вып. 10. --- М.: Физматгиз, 1963. ---
C 63--97.
2. Лупанов О. Б. Асимптотические оценки сложности управляющих систем. --- М.: Изд-во Московского университета, 1984 (1-е издание); 2024 (2-е издание).
3. Яблонский С. В. Элементы математической кибернетики. --- М.: Высшая школа, 2007.
4. Кочергин В. В. Лекции по дискретной математике. --- М.: Изд-во Московского университета, 2024.
5. Лупанов О. Б. О вентильных и контактно-вентильных схемах //
Доклады АН СССР. --- 1956. --- Т. 111, N 6. --- С. 1171--1174.
6. Кочергин В. В. О сложности вычислений в конечных абелевых группах // Математические вопросы кибернетики, вып. 4.~--- М.: Наука, 1992. --- С. 178--217.
7. Гашков С. Б., Кочергин В. В. Об аддитивных цепочках векторов, вентильных схемах и сложности вычисления степеней // Методы дискретного анализа в теории графов и сложности.--- Новосибирск, 1992. --- Вып. 52.. --- С. 22--40.
Проблемы кибернетики, вып. 10. --- М.: Физматгиз, 1963. ---
C 63--97.
2. Лупанов О. Б. Асимптотические оценки сложности управляющих систем. --- М.: Изд-во Московского университета, 1984 (1-е издание); 2024 (2-е издание).
3. Яблонский С. В. Элементы математической кибернетики. --- М.: Высшая школа, 2007.
4. Кочергин В. В. Лекции по дискретной математике. --- М.: Изд-во Московского университета, 2024.
5. Лупанов О. Б. О вентильных и контактно-вентильных схемах //
Доклады АН СССР. --- 1956. --- Т. 111, N 6. --- С. 1171--1174.
6. Кочергин В. В. О сложности вычислений в конечных абелевых группах // Математические вопросы кибернетики, вып. 4.~--- М.: Наука, 1992. --- С. 178--217.
7. Гашков С. Б., Кочергин В. В. Об аддитивных цепочках векторов, вентильных схемах и сложности вычисления степеней // Методы дискретного анализа в теории графов и сложности.--- Новосибирск, 1992. --- Вып. 52.. --- С. 22--40.
День недели
вторник
Время
18:30-20:05
Аудитория
1213
Дата первого занятия
Аудитория первого занятия
1213
Статус курса
Запись открыта
Форма записи на курс
Заполнение формы записи на курс доступно только студентам. Для записи на курс авторизуйтесь, пожалуйста, в студенческом аккаунте.