Лекции – 70 часов

1 Семестр (34 часа)

Введение. История развития дискретной математики и ее становление как науки. Место ДМ в математическом образовании. Направления ДМ в широком смысле, в узком смысле. Проблемы, которые ставит перед кибернетикой практика. ДМ – фундамент математической кибернетики. Перечень разделов ДМ, которые выносятся на рассмотрение. Роль знаний ДМ в системе создания высоких технологий.

1. Элементы комбинаторики (4 часа). Перестановки, размещения, сочетания, сочетания с повторениями, их число. Биномиальные коэффициенты, их свойства. Биномиальная теорема. Полиномиальная теорема. Формула включения и исключения. Формула решета. Производящие функции.

2. Функции алгебры логики (ФАЛ) (14 часов). Существенные и фиктивные переменные. Формулы. Реализация функций формулами. Эквивалентность формул. Свойства элементарных функций. Разложение функций алгебры логики по переменным. СДНФ, СКНФ. Принцип двойственности. Единственность представления функций алгебры логики полиномами Жегалкина. Методы построения полиномов. Полнота и замкнутость. Примеры полных систем. Важнейшие замкнутые классы. Критерий полноты для ФАЛ. Возможность выделить из любой полной системы полную подсистему, состоящую из не более чем 4-х функций. Предполные классы. Базисы. Примеры базисов. Представления о результатах Э. Поста.

3. Синтез управляющих систем (8 часов). Схемы из функциональных элементов (СФЭ) в стандартном базисе. Реализация любой ФАЛ некоторой СФЭ. Сложность СФЭ, функция Шеннона, основная задача синтеза. Порядок функции Шеннона. Метод синтеза, основанный на моделировании СДНФ ФАЛ. Метод синтеза, основанный на совместной реализации всевозможных конъюнкций длины n. Метод Шеннона. Специальное представление ФАЛ в асимптотически наилучшем методе синтеза. Метод О.Б. Лупанова.

4. Элементы теории графов (8 часов). Основные понятия теории графов. Типы и способы задания графов. Изоморфизм, связность. Оценки числа неизоморфных графов. Геометрическая реализация графов. Формула Эйлера. Следствия, вытекающие из формулы Эйлера. Операция подразделения ребра. Гомеоморфность графов. Теорема Понтрягина-Куратовского. Деревья и их свойства. Корневые деревья и оценка их числа.

2 Семестр (36 часов)

5. Элементы математической логики (8 часов). Исчисление высказываний (ИВ). Язык ИВ. Аксиомы и правила вывода в ИВ. Непротиворечивость и полнота ИВ. Исчисление предикатов (ИП). Формулы ИП. Аксиомы ИП. Правила образования выводимых формул в ИП. Понятие интерпретации. Выполнимость и общезначимость формулы 1-го порядка.

6. Ограниченно-детерминированные (о.-д.) функции (9 часов). Детерминированные функции. Задание детерминированных функций деревьями. Вес дерева. О.-д. функции. Способы задания о.-д. функций. Канонические уравнения. Диаграммы переходов. Операции над о.-д. функциями. Примеры полных систем. Пример универсальной о.-д. функции. Проблема распознавания полноты систем о.-д. функций.

7. Вычислимые функции (9 часов). Машины Тьюринга. Методы построения машин Тьюринга. Описание технологии программирования для машин Тьюринга. Машинные коды и их преобразования. Вычислимые функции. Операции суперпозиции, примитивной рекурсии и минимизации. Рекурсивные функции, их связь с классом вычислимых функций. Тезис Черча. Тезис Тьюринга.

8. Элементы теории кодирования (10 часов). Коды. Задачи теории кодирования. Алфавитное кодирование. Критерий однозначности декодирования. Теорема А.А. Маркова. Алгоритм распознавания однозначности декодирования. Помехоустойчивое кодирование. Самокорректирующиеся коды. Коды Хэмминга. Представление о кодах с минимальной избыточностью. Применение кодирования для защиты информации. Криптография.