ОСНОВЫ ДИСКРЕТНОЙ МАТЕМАТИКИ

Содержание учебной программы

МОДУЛЬ 1

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

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

2.1. Булевы функции. Табличное и геометрическое представления булевых функций. Формулы. Реализация булевых функций формулами. Булевы функции и логика высказываний.

2.2. Эквивалентность формул. Основные элементарные эквивалентности (логические тождества).

2.3. Дизъюнктивные и конъюнктивные нормальные формы. Совершенные ДНФ и КНФ. Сокращенные ДНФ и их построение методом Блэйка.

2.4. Многочлены Жегалкина. Единственность представления многочленом Жегалкина. Построение многочлена Жегалкина методом неопределенных коэффициентов.

2.5. Замкнутость и полнота классов булевых функций. Классы функций, сохраняющих ноль, единицу, монотонных, самодвойственных и линейных.

2.6. Теорема Поста о полноте.

2.7. Хорновские формулы и задача о получении продукции.

МОДУЛЬ 2

3. Графы

3.1. Определение графов. Ориентированные и неориентированные графы и их представления: графическое, матрицей смежности, матрицей инцидентности, списками смежности. Нагруженные графы. Примеры использования графов.

3.2. Достижимость и связность. Нахождение матрицы достижимости. Нахождение компонент сильной связности и базы графа.

3.3. Двудольные (бихроматические) графы. Критерий двудольности.

3.4. Ориентированные и неориентированные деревья. Эквивалентность разных определений.

3.5. Минимальное остовное дерево графа и алгоритм его построения.

3.6. Четные графы. Эйлеровы циклы и алгоритм их нахождения.

3.7. Задача о кратчайших путях в графе. Алгоритм Дейкстры для нахождения кратчайших путей из одного источника.

3.8. Задача о лабиринте. Алгоритмы обхода графа «в глубину» и «в ширину».

4. Логика предикатов.

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

2.6. Литература

1. Яблонский С.В. Введение в дискретную математику. М. Наука, 1979.

2. Гаврилов Г.П., Сапоженко А.А. Сборник задач по дискретной математике. М., Наука, 1977.

3. Кристофидес Н. Теория графов. Алгоритмический подход. М., Мир, 1978.

4. Дехтярь М.И. Предварительные сведения. (intro.pdf), 2003.

Булевы функции. (bool00.pdf), 2003.

Эквивалентность формул (bool01.pdf), 2003.

Хорновские формулы и задача о получении продукции (horn_formulas.pdf)

Логика предикатов (predikaty.pdf)

5. Тайцлин М.А. Замкнутые классы. (bool2.pdf), 2000.

Теорема Поста. (bool3.pdf), 2000.

Графы. (graphs.pdf), 2000.