Курс состоит из следующих глав: 

"Функции алгебры логики"

"Основы теории графов"

"Основы теории кодирования"

"Основы теории конечных автоматов"

"Основы теории управляющих систем"

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

Лекция 1. Функции алгебры логики.
Введение Функции алгебры логики (булевы функции) Функции от двух переменных Лемма (о числе слов) Существенные и фиктивные переменные Равные функции Определение формулы Эквивалентные формулы Основные эквивалентности Теорема о разложении по переменным

Лекция 2. Элементарная конъюнкция. Элементарная дизъюнкция.
(разложение по одной переменной) (теорема о совершенной дизъюнктивной нормальной форме) Теорема о совершенной конъюнктивной нормальной форме Определение литерала Элементарная конъюнкция (элементарная дизъюнкция) (определение) Определение дизъюнктивной нормальной формы Элементарная конъюнкция Теорема 1 Определение простой импликанты функции Утверждение (любая импликанта функции F содержит хотя бы одну простую импликанту) Определение сокращённой дизъюнктивной нормальной формы Теорема 2 Метод построения сокращённой дизъюнктивной нормальной формы

Лекция 3. Сокращённая дизъюнктивная форма. Полные системы.
Сокращенная дизъюнктивная форма Метод Нельсона построения сокращённой дизъюнктивной формы Теорема о сокращённой дизъюнктивной форме Лемма 1 Лемма 2 Лемма 3 Лемма 4 Утверждение теоремы о сокращённой дизъюнктивной форме Лемма 5 Метод Нельсона (итог) Полные системы Лемма 1 Теорема о полных системах Полиномы Жегалкина Теорема (построение полинома Жегалкина)

Лекция 4. Полиномы Жегалкина. Замкнутые классы.
Всякая функция алгебры логики представляется полиномом Жегалкина единственным способом Быстрый алгоритм построения полинома Жегалкина Лемма Замкнутые классы Класс Т0 Класс Т1 Класс L

Лекция 5. Замкнутые классы.
Замкнутые классы Класс S Теорема (принцип двойственности) Самодвойственная функция Теорема (класс S является замкнутым) Класс М Монотонная функция Теорема (класс М является замкнутым) Теорема Поста Лемма о несамодвойственной функции Лемма о немонотонной функции

Лекция 6. Теорема Поста о полноте.
Лемма о немонотонной функции Лемма о нелинейной функции Теорема Поста по полноте Базис равно 4) Предполный класс множеств функций алгебры логики предполных классов

Лекция 7. Обобщение алгебры логики. k-значная логика.
предполных классов k-значная логика Теорема (в k-значной логике тоже есть конечные полные системы) Операции сложения и умножения по модулю k Отрицание Поста Отрицание Лукашевича форма) Утверждение

Лекция 8. Вычисления по модулю k. Теория графов.
Вычисления по модулю k Теорема Лемма (малая теорема Ферма) Особенности k-значной логики Теория графов Определение графа Определение мультиграфа Определение смежных вершин в графе Определение инцидентных вершин Определение степени вершины

Лекция 9. Графы.
Утверждение (о равенстве суммы степеней всех вершин в любом графе (псевдографе)) Способы задания графов Определение подграфа Изоморфные и неизоморфные графы Путь в графе Простая цепь Утверждение (о простой цепи) Определение связного графа Определение замкнутого пути Лемма 2 Лемма 3

Лекция 10. Деревья.
Теорема об эквивалентных определениях дерева Задача оптимизации (кратчайшее остовное дерево) Теорема (описанный алгоритм корректно строит кратчайшее остовное дерево) Корневые деревья Упорядоченное корневое дерево

Лекция 11. Геометрическая реализация графов. Планарные графы.
Упорядоченное корневое дерево Теорема о числе корневых деревьев Изоморфизм корневых деревьев Геометрическая реализация графов Теорема (для любого графа существует геометрическая реализация в трёхмерном евклидовом пространстве) Планарные графы Формула Эйлера для планарных графов Непланарные графы

Лекция 12. Раскраски графов.
Критерии планарности Теорема Понтрягина - Куратовского Раскраски графов красках

Лекция 13. Теория кодирования.
Теорема Кёнига Лемма 1 Замкнутый подпуть нечётной длины Лемма 2 Теория кодирования Определение кодирования Алфавитное кодирование Префиксный код Утверждение - любой префиксный код является взаимнооднозначным Суффиксный код Задача о распознавании по заданному кодированию Теорема о взаимной однозначности кодирования

Лекция 14. Теорема о взаимной однозначности кодирования. Теорема Маркова.
Теорема о взаимной однозначности кодирования Теорема Маркова Неравенство Макмиллана

Лекция 15. Неравенство Макмиллана.
Неравенство Макмиллана Обратная теорема Следствие из двух теорем Определение оптимального кодирования для заданных частот Теорема об оптимальном кодировании заданных частот Утверждение (об оптимальном префиксном коде) Свойства оптимального кода

Лекция 16. Теорема редукции.
Свойства оптимального кода Теорема редукции Смысл теоремы редукции Коды, исправляющие ошибки Определение (шар радиуса r) Определение (кодовое расстояние) Утверждение о кодах, исправляющих ошибки

Лекция 17. Коды Хэмминга.
Коды, исправляющие ошибки Коды Хэмминга Определение кода Хэмминга Теорема о коде Хэмминга Теорема (оценка в случае одной ошибки) Теорема (о линейных кодах)

Лекция 18. Автоматы. Часть 1.
Автоматы (инициальные) Определение инициального автомата Функционирование автомата Отображение Определение (отображение как автоматная функция) Пример (автомат задержка) Диаграмма Мура для автомата Схемы из функциональных элементов Ациклический ориентированный граф Утверждение (в любом ациклическом ориентированном графе есть хотя бы один исток) Схема из функциональных элементов Определение схемы из функциональных элементов Пример Функционирование схемы Глубина вершины в ацикличном ориентированном графе Утверждение о глубине вершины Определение функционирования схемы Схема из функциональных элементов с задержками Функционирование схемы из функциональных элементов с задержками

Лекция 19. Автоматы. Часть 2.
Теорема Обратная теорема Теорема Мура

Лекция 20. Теорема Мура.
Теорема Мура Лемма Теорема (существует автомат с тремя состояниями, в котором каждая пара состояний отлична, но не существует эксперимента, который бы однозначно определял начальное значение автомата) Схемный сумматор порядка N Теорема (существует схема из функциональных элементов в стандартном базисе, которая является сумматором и имеет сложность ...)

Лекция 21. Умножитель порядка N.
Построение сумматора Вычитатель порядка N Теорема о вычитаеле порядка N Построение вычитателя Умножитель порядка N Алгоритм умножения в столбик Теорема (Карацуба А.А.) Лемма 1 Лемма 1.1 Доказательство оценки из теоремы Лемма 2