• /
• Основы дискретной математики

Предварительные сведения.

• Множества, отношения, функции; метод математической индукции; элементы комбинаторики.

Булевы функции

• Табличное и геометрическое представления булевых функций. Формулы. Реализация булевых функций формулами. Булевы функции и логика высказываний.
• Эквивалентность формул. Основные элементарные эквивалентности (логические тождества).
• Дизъюнктивные и конъюнктивные нормальные формы. Совершенные ДНФ и КНФ. Сокращенные ДНФ и их построение методом Блейка.
• Многочлены Жегалкина. Единственность представления многочленом Жегалкина. Построение многочлена Жегалкина методом неопределенных коэффициентов
• Замкнутость и полнота классов булевых функций. Классы функций, сохраняющих ноль, единицу, монотонных, самодвойственных и линейных.
• Теорема Поста о полноте и ее применение.

Графы

• Определение графов. Ориентированные и неориентированные графы и их представления: графическое, матрицей смежности, матрицей инцидентности, списками смежности. Нагруженные графы. Примеры использования графов.
• Достижимость и связность. Нахождение матрицы достижимости. Нахождение компонент сильной связности и баз графа.
• Ориентированные и неориентированные деревья. Эквивалентность разных определений. Деревья и формулы. Обходы деревьев.
• Четные графы. Эйлеровы циклы и алгоритм их нахождения.
• Двудольные (бихроматические) графы. Критерий двудольности.
• Минимальное остовное дерево графа и алгоритм его построения.
• Задача о кратчайших путях в графе. Алгоритм Дейкстры для нахождения кратчайших путей из одного источника.
• Задача о лабиринте. Алгоритм обхода графа «в глубину» и его приложения.

Применение графов для представления булевых функций.

• Логические схемы (схемы из функциональных элементов). Определение схем и их сложность.
• Логические схемы и линейные программы.
• Построение схемы двоичного сумматора.
• Упорядоченные бинарные диаграммы решений (УБДР): определения и примеры.
• Сокращенные УБДР и преобразование произвольной УБДР в сокращенную.
• Построение сокращенной УБДР по формуле.

Конечные автоматы - 1

• Алфавиты, слова, языки. Операции над языками.
• Автоматы-преобразователи (с выходом) и автоматы-распознаватели.
• Недетерминированные и детерминированные конечные автоматы. Способы задания конечных автоматов: таблицы и диаграммы.
• Теорема о детерминизации недетерминированных конечных автоматов.

Конечные автоматы - 2

• Регулярные выражения и регулярные языки.
• Теорема о распознавании регулярных языков конечными автоматами.
• Свойства замкнутости класса автоматных языков.
• Алгоритмические проблемы для конечных автоматов.
• Теорема о разрастании. Примеры не конечно автоматных языков.

Алгоритмы -1: структурированные программы.

• Структурированные программы: синтаксис и семантика.
• Арифметические функции, вычислимые структурированными программами.

Алгоритмы - 2: частично рекурсивные функции.

• Рекурсивные функции. Операторы суперпозиции, примитивной рекурсии и минимизации.
• Рекурсивность функций, заданных с помощью ограниченного суммирования, сдвига, склейки и переименования переменных, разбора случаев. Нумерационные функции. Совместная рекурсия.
• Вычислимость рекурсивных функций программами.

Алгоритмы-2: машины Тьюринга

• Машины Тьюринга. «Тьюрингово» программирование: простейшие программы, реализация композиции, условного оператора и цикла.
• Вычислимость рекурсивных функций на машинах Тьюринга.
• Тезис Тьюринга-Черча. Алгоритмически неразрешимые проблемы.