Практические занятия

№

Содержание

1. 1

Множества и бинарные отношения. Операции над множествами. Подсчет элементов конечных множеств с помощью правила суммы, формулы включений и выключений. Определение свойств бинарных отношения на множестве. Построение разбиений множеств на классы эквивалентности.

Л-4: № 1.1. 1.9, 1.10, 1.28, 1.29.

Выдача БДЗ № 1

2. 2

Элементы комбинаторики. Подсчет числа элементов конечных множеств с использованием правила суммы, правила произведения и основных комбинаторных формул. Доказательство комбинаторных тождеств.

Л-4: №.1.5, 1.6, 1.7, 1.8. 1.21 - 1.24.

3. 3

Булевы функции и способы их задания. Задание булевой функции таблицей истинности и вектором значений. Задание булевых функций формулами. Построение функций, существенно зависящих от всех своих переменных.

Л-4: №. 2.1, 2.2, 2.4 – 2.6, 2.10, 2.8, 2.9, 2.11, 2.12

4. 4

Равносильность формул и дизъюнктивные и конъюнктивные нормальные формы. Упрощение формул с помощью равносильных преобразований. Построение двойственных функций по определению и с помощью принципа двойственности. Задание булевых функций в виде СДНФ и СКНФ.

Л-4: №. 2.13 – 17, 2.20 – 2.23, 2.27, 2.29 – 33.

Контрольная работа № 1

5. 5

Минимизация дизъюнктивных нормальных форм. Построение для булевой функции сокращенных, тупиковых, минимальных ДНФ.

Л-4: № 2.38 – 41, 2.44, 2.43, 2.45.

Прием БДЗ № 1. Выдача БДЗ № 2.

6. 6

Классы Поста и замыкание. Построение полинома Жегалкина методом равносильных преобразований и неопределенных коэффициентов. Определение принадлежности функций классам Поста.

Л-4: № 2.46 - 49, 2.51, 2.52, 2.56, 2.57, 2.59, 2.61. 2.65, 2.70, 2.77, 2.78, 2.81.

7. 7

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

Л-4: № 2.85, 2.86, 2.87, 2.88.

8. 8

Контрольная работа № 2 (базовый и повышенный уровень).

Занятие 9

Первичные понятия теории графов. Компоненты связности. Циклы и мосты. Классификация элементов графа; задание графа диаграммой и матрицами. Изоморфные графы, виды графов. Пути и циклы на графе. Выделение компонент связности графа.

Л-4: №.3.1, 3.55, 3.2, 3.3 -3.8, 3.12, 3.13. 3.11, 3.16. 3.15, 3.62, 3.56.

Прием БДЗ № 2

9. 10

Коллоквиум по модулю 1

10. 11

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

Л-4: № 3.46, 3.47, 3.68, 3.69, 3.71, 3.48 - 3. 50, 3.52, 3.53.

Выдача БДЗ № 3

11. 12

Планарность. Обсуждение проблемы укладки графа в пространстве и на плоскости. Доказательство планарности (непланарности) графа с использованием формулы Эйлера для плоских графов и критериев планарности.

Л-4: № 3.20, 3.78, 3.83. 3.84, 3.85, 3.89.

12. 13

Обходы графов. Применение критерия Эйлера к решению вопроса о существовании эйлерова цикла (цепи) на графе. Построение Эйлерова цикла (цепи) на графе.

Раскраска графов. Раскраска графа, определение хроматического числа, обсуждение критерия бихроматичности.

Фундаментальная система циклов графа. Линейное пространство циклов. Алгоритм построения фундаментальной системы циклов.

Л-4: №.3.37 - 3.42, 3.72 - 3.74, 3.76, 3.64 - 3.67.

13. 14

Ориентированные графы. Классификация элементов орграфов, задание орграфа диаграммой и матрицами, изоморфные орграфы, слабая и сильная связность орграфа. Ориентированные деревья.

Оптимизационные задачи на орграфах. Отыскание кратчайших путей в сети (алгоритм Дейкстры). Построение максимального потока и минимального разреза в сети (алгоритм Форда-Фалкерсона).

Л-4: №. 3.9, 3.10, 3.90, 3.91. Разработка кафедры.

14. 15

Построение схем функциональных элементов .

Упорядоченная бинарная диаграмма решений. Понятие об УБДР. Минимальные УБДР. Сокращенные УБДР, их построение для функции, заданной таблицей и формулой.

Разработка кафедры.

Занятие 16

Контрольная работа № 3 (базовый и повышенный уровень).

Прием БДЗ № 3