Курс «Основы кибернетики» (ранее «Элементы кибернетики»), создателем и основным лектором которого был чл.-корр. РАН С.В. Яблонский, читается на факультете ВМК с первых лет его существования. Он является продолжением курса «Дискретная математика» и посвящён изложению основных моделей, методов и результатов математической кибернетики, связанных с теорией дискретных управляющих систем (УС), с задачей схемной или структурной реализации дискретных функций и алгоритмов.

В нём рассматриваются различные классы УС (классы схем), представляющие собой дискретные математические модели различных типов электронных схем, систем обработки информации и управления, алгоритмов и программ. Для базовых классов УС (схем из функциональных элементов, формул, контактных схем, автоматных схем), а также некоторых других типов УС, ставятся и изучаются основные задачи теории УС: задача минимизации дизъюнктивных нормальных форм (ДНФ), задача эквивалентных преобразований и структурного моделирования УС, задача синтеза УС, задача повышения надёжности и контроля УС из ненадёжных элементов и др. В программу курса входят классические результаты К. Шеннона, С.В. Яблонского, Ю.И. Журавлева и О.Б. Лупанова, а также некоторые результаты последних лет. Показывается возможность практического применения этих результатов на примере задачи проектирования СБИС, которые составляют основу программно-аппаратной реализации алгоритмов. Продолжением курсов «Дискретная математика» и «Основы кибернетики» является читаемый для бакалавров данного профиля в 7 семестре курс «Дополнительные главы дискретной математики и кибернетики».

Список всех тем лекций

Лекция 1. ДНФ функции алгебры логики.
Организационные вопросы Введение: о кибернетике, системах управления, курсе, его разделах и сферах применения Булевы множества Вес набора Геометрическая интерпретация: рёбра, слои, грани (их представления, мощность и количество в кубе) Важные понятия Множества ФАЛ Примеры со стандартными ФАЛ Представление ФАЛ дизъюнктивными нормальными формами (ДНФ) Утверждение о единственности СДНФ

Лекция 2. Сокращённая ДНФ.
Повторение материала прошлой лекции Совершенная КНФ (СКНФ) Сравнение с СДНФ Некоторые тождества алгебры логики, необходимые в дальнейшем Простая импликанта "Геометрическая" интерпретация сокращённой ДНФ Пример Утверждение о построении сокращённой ДНФ и его следствие Расширение и строгое расширение ДНФ Метод Блейка построения сокращённой ДНФ и его следствие

Лекция 3. Особенности сокращённых ДНФ.
Повторение материала прошлой лекции Окрестность грани, степень локальности Локальность критериев вхождения простой импликанты Линейные ФАЛ и их свойства Функции, монотонно зависящие от переменной и их свойство Имонотонность ФАЛ Особенности сокращённых ДНФ монотонных ФАЛ Покрытие, задача покрытия, функция покрытия и её свойства Построение всех тупиковых ДНФ

Лекция 4. Задача минимизации ДНФ.
Примеры Пси-сложность, пси-оптимальность Пример Разложение Шеннона Отображение набора k-мерного единичного куба на набор независимых случайных величин

Лекция 5. Сложность задачи минимизации ДНФ.
Повторение материала прошлой лекции Эффект Шеннона Параметры трудоёмкости задачи минимизации ДНФ Утверждение о числе тупиковых (минимальных) ДНФ и его следствие Симметрическая ФАЛ, примеры Цепная ФАЛ, примеры

Лекция 6. Формула алгебры логики.
Базис, функциональный элемент, входной и выходной алфавиты Индуктивное (по глубине) определение формулы Пример Функционалы сложности формул Утверждение о связи функционалов сложности Принцип эквивалентной замены Преобразования подобия Формула с поднятыми отрицаниями Альтернирование

Лекция 7. Схема из функциональных элементов.
Схема: изоморфность, эквивалентность, классы, сложность Переход от СФЭ к системе формул (квазидеревьев) Функционалы сложности СФЭ (Аналогично случаю формулы) Квазиизоморфоность формул Оценка количества попарно неэквивалентных СФЭ

Лекция 8. Эквивалентные преобразования СФЭ.
Пример эквивалентных СФЭ Модификация тождества Полнота системы тождеств Примеры Утверждение о получении полной системы тождеств для ЭП СФЭ

Лекция 9. Контактная схема.
Типы проводящих контактов, их соответствие с МОП-транзисторами Примеры Примеры ФАЛ отделимости Последовательное и параллельное соединения Сопоставление пи-схеме формулы с поднятыми отрицаниями Контактное дерево Оценка числа попарно неэквивалентных пи-схем Утверждение об оценке числа попарно неэквивалентных КС

Лекция 10. Нижние оценки сложности ФАЛ.
Простейшие верхние оценки Нижние оценки сложности системы ФАЛ Нижние оценки сложности отдельной ФАЛ Пример Пример Верхние оценки некоторых ФАЛ

Лекция 11. Суперпозиции различных схем.
Суперпозиция схем Частные случаи суперпозиции Правильная и корректная суперпозиции Примеры Пример Пример Пример Утверждение о существовании ККС, реализующей систему из отрицаний ФАЛ

Лекция 12. Каскадная СФЭ.
Повторение прошлой лекции Частный случай Утверждение о существовании ККС, реализующей систему из отрицаний ФАЛ Пример с конъюнктивным и дизъюнктивным контактными деревьями Примеры Пример Оценки сложности некоторых каскадных схем Метод Шеннона

Лекция 13. Асимптотически наилучший метод синтеза СФЭ.
Нижние мощностные оценки функций Шеннона Мощностные оценки в таких задач Метод Лупанова для синтеза СФЭ Асимптотически наилучшая верхняя оценка сложности для СФЭ

Лекция 14. Асимптотически наилучший метод синтеза формул.
Повторение прошлой лекции Пример Продолжение примера Асимптотически наилучшая верхняя оценка сложности для формул Асимптотически наилучшая верхняя оценка сложности для КС

Лекция 15. Асимптотически наилучший метод синтеза КС.
Повторение прошлой лекции Необходимые разложения для формулы Построение КС по разложению и её сложность Замечание о верхней оценке разбиения данной КС Примеры Несколько слов про следующую тему

Лекция 16. Самокорректирующаяся КС.
Каскадная пи-схема Верхние оценки сложности для некоторых мультиплексоров Обрыв и замыкание контакта Тривиальное решение задачи повышения надёжности схемы Коррекция с помощью разбиения Асимптотика функции Шеннона для самокорректирующихся КС Случай схемы Кардо

Лекция 17. Задача контроля схем.
Область определённости Цель контроля: проверка, диагностика Тупиковый, минимальный, проверяющий и диагностический тесты Способы построения тестов Продолжение примера Оценки длин тестов

Лекция 18. Эквивалентные преобразования КС.
КС с неразделёнными полюсами Примеры Примеры Понятие подсхемы, выполняющее принцип эквивалентной замены Примеры эквивалентных преобразований КС Вывод вспомогательных тождеств Обобщённые тождества

Лекция 19. Полнота системы основных тождеств.
Продолжение вывода обобщённых тождеств Переход к канонической форме через ЭП ЭП эквивалентных КС

Лекция 20. Цикломатическое число КС.
Небольшое повторение прошлой лекции Пример Пример Доказательство отсутствия конечной полной системы тождеств в классе КС Примеры задач на синтез схем ФАЛ из специальных классов

Лекция 21. Модификации классов схем.
Команды ввода, вычисляющие команды, вывод Пример Двоичная решающая диаграмма (BDD) Пример Элементы задержки Реализация элементов задержки через схемы с "мгновенными" обратными связями