Тип: курс по выбору кафедры

Лектор: Калачев Глеб Вячеславович, Шуткин Юрий Сергеевич, Ефимов Алексей Андреевич

Для: студентов 5 курса

Время: чт 15.00 - 16.35

Начиная с: 12.09.2025

Общее понятие сложности управляющих систем. Задача синтеза. Функция Шеннона.
Схемы из функциональных элементов. Простейшие методы синтеза.
Метод синтеза Шеннона для СФЭ. Нижняя оценка функции Шеннона для СФЭ.
Метод синтеза Лупанова для СФЭ.
Контактные схемы. Простейшие методы синтеза.
Метод синтеза Шеннона для контактных схем. Нижняя оценка функции Шеннона для контактных схем.
Метод синтеза Лупанова для контактных схем. Метод каскадов.
Укладка СФЭ на граф. Модели схем. Сложность функции в данной модели. Универсальная нижняя оценка для “однослойных схем”.
Плоские схемы. Порядок роста функции Шеннона сложности плоских схем (теорема Кравцова).
Связь между различными моделями схем.
Квадратичная нижняя оценка сложности реализации умножения на случайные разреженные матрицы плоскими схемами. Следствие о переходе от СФЭ к плоским схемам.
Асимптотика площади дешифратора в специальном базисе в классе прямоугольных схем (теорема Зизова).
Активность плоских схем. Метод синтеза плоских схем с активностью \( O(2^{n/2}) \).

Материалы:

1. Яблонский С.В. Введение в дискретную математику: Учеб. пособие. М.: Наука. 1986. (1-4)
2. Лупанов О. Б. О синтезе некоторых классов управляющих систем // Проблемы кибернетики, вып. 10. – М.: Физматгиз, 1963. – C 63-97. (3-7)
3. Ложкин С. А. Лекции по основам кибернетики. 2009. Глава 3. (1-7)
4. Шуткин Ю. С. О реализации булевых функций информационными графами // Дискретная математика. – 2008. – Т. 20, № 4. – С. 31 – 41 (8-9)
5. Жуков Д.А. О вычислении частичных булевых функций клеточными схемами. // Дискретный анализ и исследование операций. Апрель -- июнь 2004. Серия 1. Том 11, № 2, С. 32 – 40 (10)
6. Т. Р. Сытдыков, Сложность синтеза многомерных прямоугольных схем, Интеллектуальные системы. Теория и приложения, 2019, том 23, выпуск 3, 61–8. (12)
7. С. А. Ложкин, В. С. Зизов, “Уточненные оценки сложности дешифратора в модели клеточных схем из функциональных и коммутационных элементов” // Учен. зап. Казан. ун-та. Сер. Физ.-матем. науки, 2020, том 162, книга 3, 322–334 (14)
8. Г. В. Калачев. Порядок мощности плоских схем, реализующих булевы функции. Дискретная математика, 26(1):49–74, 2014. (15)