Вопросы к экзамену по дискретной математике
1. Понятие множества, подмножества. Мощность множества.
2. Операции над множествами: объединение, пересечение, разность, дополнение, симметрическая разность и их свойства.
3. Алгебра множеств. Тождества алгебры множеств. Диаграммы Эйлера – Венна. Мультимножества.
4. Булеан. Число k -элементных подмножеств n -элементного множества. Число сочетаний и его свойства.
5. Декартово произведение. Правила равенства, суммы и произведения при перечислении элементов множеств. Покрытия и разбиения множеств.
6. Отношения. Общие свойства отношений. Способы представления отношений.
7. Отношения эквивалентности и порядка. Их свойства.
8. Булевы наборы. булев куб. Изображение булева куба при n = 2, 3, 4.
9. Функции алгебры логики. Основные функции алгебры логики одной и двух переменных.
10.Аналитическое и табличное представление функций алгебры логики. Существенные и фиктивные переменные. Равенство функций алгебры логики.
11.Свойства элементарных булевых функций.
12.Разложение булевых функций по переменным. Совершенная ДНФ.
13.Перевод функций алгебры логики, заданных таблично и аналитически в совершенную ДНФ.
14.Разложение булевых функций по переменным. Совершенная КНФ.
15.Перевод функций алгебры логики, заданных таблично и аналитически в совершенную КНФ.
16.ДНФ и КНФ. Минимизация ДНФ и КНФ.
17.Минимизация ДНФ методом минимизирующих карт (карт Карно).
18.Минимизация КНФ методом минимизирующих карт (карт Карно).
19.Высказывания. Операции над высказываниями.
20.Формулы алгебры высказываний. Таблицы истинности.
21.Предикаты. Кванторы. Связанные и свободные переменные.
22.Формулы алгебры предикатов. Связь кванторов и логических операций.
23.Равносильности алгебры предикатов. Способы их доказательства.
24.Графы и орграфы. Основные понятия теории графов.
25.Простейшие типы графов.
26.Матрицы смежности и инцидентности графов. Их свойства.
27.Матрицы смежности и инцидентности орграфов. Их свойства.
28.Изоморфизм графов. Теорема о вложении псевдографа в R 3.
29.Подграфы. Операции над подграфами и графами.
30.Маршруты, цепи, циклы. Пути в орграфах.
31.Связность и компоненты графа.
32.Цикломатическое число и его свойства.
33.Эйлеровы цепи и циклы. Существование эйлерова цикла.
34.Гамильтоновы цепи (циклы). Существование гамильтонова цикла.
35.Деревья и их свойства.
36.Планарность графа. Формула Эйлера.
37.Матричный метод нахождения числа маршрутов в орграфах.
38.Поиск в глубину (DFS) и поиск в ширину (BFS).
39.Жадные алгоритмы. Построение кратчайшего остова (SST). Алгоритмы Краскала и Прима.
40.Нахождение кратчайшего пути в графе. Алгоритм Дейкстры.
Основная литература
Парфенова М.Я. Дискретная математика: учебное пособие. - М.: изд. «МУ им. С.Ю. Витте», 2015.
Сапронов И. Математика. Элементы дискретной математики. Учебное пособие. - Воронеж: Воронежская государственная лесотехническая академия, 2013. - 118 с.
https://online.muiv.ru/lib/books/45333/
3. Ковалева Л.Ф. Дискретная математика в задачах. Учебное пособие. – М.: Евразийский открытый институт, 2011. - 142 с. https://online.muiv.ru/lib/books/359/
Тюрин С.Ф., Аляев Ю.А. Дискретная математика: Практическая дискретная математика и математическая логика: учебное пособие. –М.: Финансы и статистика, 2010. - 385 с.
https://online.muiv.ru/lib/books/39279/
Балюкевич Э.Л., Ковалева Л.Ф., Романников А.Н. Дискретная математика. Учебно-практическое пособие. –М.: Изд. центр ЕАОИ, 2012. - 173 с.
https://online.muiv.ru/lib/books/358/
Дополнительная литература
6. Хаггарти Р. Дискретная математика для программистов. Издание 2-е, исправленное. Издательство: РИЦ "Техносфера", 2012.
https://online.muiv.ru/lib/books/41361/
Редькин Н.П. Дискретная математика. Учебник. –М.: Издательство: Физматлит, 2009 г.
https://online.muiv.ru/lib/books/100504/
Макоха А. и др. Дискретная математика: учебное пособие. - М.: Физматлит, 2005. - 368 с.
https://online.muiv.ru/lib/books/100370/
9. Сачков В.Н.Введение в комбинаторные методы дискретной математики (2-е издание, исправленное и дополненное). – М.: МЦНМО, 2004. - 424 с.
https://online.muiv.ru/lib/books/408/
Сигал И.Х., Иванова А.П. Введение в прикладное дискретное программирование: модели и вычислительные алгоритмы. – М.: Издательство: Физматлит, 2007.
https://online.muiv.ru/lib/books/100878/
Яблонский С.В. Введение в дискретную математику. – М.: Высшая школа, 2008. – 384 с.
Гаврилов Г.П., Сапоженко А.А. Задачи и упражнения по дискретной математике. – М.: Высшая школа, 2008. – 416 с..
Интернет-ресурсы
1. https://www.matburo.ru/ Учебники, лекции, методические пособия по дискретной математике
2. https://www.ph4s.ru/book_pc_diskretka.html/ Студентам и школьникам книги по дискретной математике
3. https://litevv.narod.ru/lekcii/diskret.html/ Лекции по дискретной математике
4. www.exponenta.ru/ Оразовательный математический сайт. Теоретический материал по высшей математике, информация по работе с математическими пакетами, тесты по математике для самопроверки.
5. https://www.i-exam.ru/ Обучающая система on-line тестирования
6. https://www.edulib.ru/ – центральная библиотека образовательных ресурсов.
7. https://www.auditorium.ru/ – библиотека образовательного портала «AUDITORIUM».
8. https://www.public.ru/ – публичная интернет-библиотека.