Тематический план и содержание дисциплины ( с распределением общего бюджета времени в часах)

КУРС

СЕМЕСТР

Раздел

дисциплины,

содержание

ВСЕГО

АУДИТОРНЫЕ

Самостоятельная

работа студентов

Лекции

Аудиторный

практикум

Лабораторный

практикум

2

3

Раздел I. Элементы теории множеств

15

5

4

6

Тема 1. Множества и операции над ними

Множество. Равенство множеств. Подмножество. Пустое множество, универсум. Диаграммы Эйлера-Венна. Булеан. Способы задания множеств. Основные операции над множествами. Алгебра множеств, её основные формулы. Конституенты.

6

2

2

2

Тема 2. Отношения и функции

Декартовы произведения множеств. Бинарные отношения. Отображения множеств. Образы, прообразы, обратные отображения, виды отображений. Функции, их свойства. Бинарные отношения специального вида. Отношения порядка.

5

2

1

2

Тема 3. Мощность множеств. Кардинальные числа

Эквивалентность и мощность множеств. Кардинальные числа, шкала кардинальных чисел. Конечные, бесконечные, счётные, бессчётные, континуальные множества, их свойства. Арифметика кардинальных чисел.

4

1

1

2

Раздел II. Комбинаторика

30

8

12

10

Тема 4. Основные формулы комбинаторики

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

9

2

4

3

Тема 5. Принцип включений и исключений

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

9

2

4

3

Тема 6. Производящие функции

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

12

4

4

4

Раздел III. Основы теории графов

29

8

8

13

Тема 7. Основные понятия теории графов

Граф (орграф), его элементы. Виды графов (орграфов). Отношения между элементами графа (орграфа). Способы задания. Степень вершины. Изоморфизм. Связность.

6

2

2

2

Тема 8. Маршруты, пути, циклы

Маршруты в графах, их виды. Цепь, цикл. Пути в орграфах, их виды. Контур. Теоремы о маршрутах и циклах.

8

2

2

4

Тема 9. Деревья

Дерево (ордерево). Корневые, бинарные деревья. Теоремы о деревьях.

7

2

2

3

Тема 10. Сети, потоки в сетях

Определения двухполюсной направленной сети, потока. Задача о максимальном потоке. Разрез. Теорема Форда-Фалкерсона.

8

2

2

4

Раздел IV. Теория булевых функций

45

13

10

22

Тема 11. Алгебра высказываний

Высказывание как первичное понятие алгебры логики. Основные операции над высказываниями. Пропозициональные связки. Истинностные функции. Формулы алгебры высказываний, их виды. Метод истинностных таблиц.

4

1

1

2

Тема 12. Основные понятия теории булевых функций

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

4

1

1

2

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

Нормальные формы. Алгоритмы приведения к совершенным дизъюнктивной и конъюнктивной нормальным формам. Полиномы Жегалкина.

8

3

1

4

Тема 14. Приложения алгебры логики

Релейно-контактные схемы, их математическое описание и методы построения.

8

2

2

4

Тема 15. Двойственность

Двойственная функция. Принцип двойственности.

4

1

1

2

Тема 16. Полнота и замкнутые классы

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

9

3

2

4

Тема 17. Минимизация булевых функций

Задача минимизации булевых функций. Структура n-мерного куба. Сокращённая дизъюнктивная форма (ДНФ). Методы Блейка, Нельсона, Квайна их построения, карты Карно. Тупиковая, минимальная, кратчайшая ДНФ, методы их построения.

8

2

2

4

Итого за 3 семестр:

119

34

34

51