1. Наименование тем, их содержание

Тема 1. Введение. Основы теории множеств.

Предмет и задачи дисциплины “Дискретная математика”, ее связь с другими дисциплинами. Области применения методов дискретной математики, особая роль решения задач оптимизации.

Р.Л.: [1]; [2]; [3];[4]; [11].

Раздел 1. Теория множеств

Тема 2. Множества и подмножества

Понятие множества. Элементы множества. Принадлежность/ не принадлежность множеству. Определение класса (семейства) множеств. Универсальное множество. Пустое множество. Конечное/бесконечное множество. Собственное подмножество. Собственное надмножество. Способы задания множеств.

Р.Л.: [1]; [2];[3];[4]; [6];[11]; [14]; [16]; [19]

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

Сравнение множеств. Равенство множеств. Мощность множеств. Равномощные множества. Свойства равных множеств. Операции над множествами: объединение, пересечение, разность, симметрическая разность, дополнение, разбиение. Свойства операций над множествами. Примеры доказательств тождеств с множествами. Понятие булеана.

Р.Л.: [1]; [2]; [3]; [4]; [6];[14]; [16]; [19].

Тема 4. Упорядоченные множества

Понятие упорядоченной пары. Равенство пар. Понятие кортежа. Длина кортежа. Проекция кортежа. Одноименные компоненты. Пустой кортеж. Утверждения для кортежей. Операция проекции кортежей. Проекция множества. Операции над кортежами: композиция и инверсия. Декартово произведение множеств. Свойства декартово произведения множеств. Понятие графика. Область определения графика. Область значения графика. Операции над графиками: инверсия, композиция. Симметричность графика. Понятие диагонали. Компонирование графиков. Свойства графиков.

Р.Л.: [1]; [2]; [3]; [4]; [6];[11]; [14]; [16]; [19].

Тема 5. Отношения на множествах

Понятие отношения.

Р.Л.: [[1]; [2]; [3]; [4]; [6];[11]; [14]; [16]; [19].

Тема 6. Соответствие и функции

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

Р.Л.: [1]; [2]; [3]; [4]; [6];[11]; [14]; [16]; [19].

Тема 7. Мультимножества

Понятие мультимножества. Компонента мультимножества. Функция кратности. Порождающее множество (домен). Мощность мультимножества. Высота (пиковое значение) мультимножества. Подмультимножество. Надмультимножество. Операции над мультимножествами.

Р.Л.: [1]; [2]; [3]; [4]; [6];[11]; [14]; [16]; [19].

Раздел 2. Теория графов

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

Понятие графа. Ориентированный, неориентированный граф. Пустой граф. Нуль-граф. Понятие инцидентности. Смежность вершин и ребер. Висячая вершина. Изолированная вершина. Способы задания графа.

Р.Л.: [1]; [3]; [5]; [7]; [19].

Тема 9. Графы

Типы графов. Полный граф. Симметрический, антисимметрический граф. Полный граф. Связный граф. Ориентированное дерево. Планарный/непланарный граф. Ориентированный/неориентированный граф. Двудольный граф. Подграфы. Остов подграф. Собственный подграф. Правильный подграф. Виды подграфов. Порожденный подграф. Сильно связанные графы и компоненты графа. Маршрут в графе. Открытый маршрут. Замкнутый маршрут. Цепь. Открытая цепь. Замкнутая цепь. Длина пути. Длина цикла. Свойства путей и циклов. Связность и компоненты графа. Операции над графами. Матрица смежности и инцидентности.

Р.Л.: [1]; [3]; [5]; [7]; [12]; [13]; [15]; [17]; [18],[19].

Тема 10. Орграфы

Понятие орграфа. Основание орграфа. Вершина орграфа. Изоморфные орграфы. Матрица смежности орграфа. Ориентированный маршрут в орграфе. Орцепь. Орциклы. Сильный орграф. Слабый орграф. Односторонний орграф. Несвязный орграф. Порожденный орграф. Матрицы орграфов. Ориентированные эйлеровы графы.

Р.Л.: [1]; [3]; [5]; [7]; [12]; [13]; [15]; [17]; [18],[19].

Тема 11. Ориентированные ациклические графы и деревья

Понятие ациклических графов. Понятие ориентированных ациклических графов. Понятие дерева. Лес. Остово дерево. Коциклический ранг графа. Остов лес. Фундаментальная система циклов.

Р.Л.: [1]; [3]; [5]; [7]; [12]; [13]; [15]; [17]; [18],[19].

Тема 12. Планарность и двойственность

Понятие планарного графа. Графы Куратовского. Точки сочленения, мосты, блоки. Двойственные графы. Лемма. Абстрактно двойственные графы.

Р.Л.: [1]; [3]; [5]; [7]; [12]; [13]; [15]; [17]; [18],[19].

Тема 13. ОрганизПоиск на графах

Исследование лабиринта. Поиск в глубину. Поиск в ширину. Нахождение кратчайшего пути (алгоритм Дейкстры).

Р.Л.: [1]; [3]; [5]; [7]; [12]; [13]; [15]; [17]; [18],[19].

2. Контрольные работы, их характеристика

3. ЛИТЕРАТУРА

ОСНОВНАЯ

1. Горбатов В.А. Фундаментальные основы дискретной математики. Информационная математика. – М.: Наука. Физматлит, 2000. – 544 с.

2. Новиков Ф.А. Дискретная математика для программистов: учебник для вузов. 3-е изд. СПб.: Питер, 2009. – 384 с.: ил.

3. Кузнецов О. П. Дискретная математика для инженеров. — СПб.: Лань, 2004.

4. Гладков Л.А., Курейчик В.В., Курейчик В.М. Дискретная математика. Часть 1. Теория множеств. – Таганрог, 2005. – 160 с.

5. 9. Гладков Л.А., Курейчик В.В., Курейчик В.М. Дискретная математика. Часть 2. Теория графов. – Таганрог, 2010. – 162 с.

ДОПОЛНИТЕЛЬНАЯ

6. Белоусов А.И., Ткачев С.Б. Дискретная математика. – М.: Изд-во МГТУ им. Н.Э. Баумана, 2004. – 744 с.

7. Берж К. Теория графов и ее применение. М.: Иностранная литература, 1962.8.

10. Информация в понятиях и терминах / Под ред. В.А. Извозчикова. М.: Просвещение, 1991.

11. Липский В. Комбинаторика для программистов. М.: Мир, 1988.

12. Мелихов А.Н. Ориентированные графы и конечные автоматы. М.:Наука, 1971.

13. Оре О. Теория графов. – М.: Наука, 1980. – 336 с.

14. Соболева Т.С., Чечкин А.В. Дискретная математика. – М.: Издательский центр «Академия», 2006. — 256 с.

15. Татт У. Теория графов. – М.: Мир, 1988. - 424 с.

16. Тишин В.В. Дискретная математика в примерах и задачах. – СПб.: БХВ-Петербург, 2008. — 352 с.

17. Уилсон Р. Введение в теорию графов. – М.: Мир, 1977. – 208 с.

18. Харари Ф. Теория графов / Пер. с англ. и предисл. В. П. Козырева. — М.: Едиториал УРСС, 2003. — 296 с.

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