Вопросы для подготовки к экзамену по курсу
«Дискретная математика»
1. Понятия множество, мультимножество, нечеткое множество, элемент, универсум, подмножество, кортеж.
2. Операции над множествами
3. Декартово произведение. п -арное соответствие. Алгебраическая п -арная операция.
4. Понятия отображения и функции. Сюръекция, инъекция и биекция
5. Обратное отображение, композиция отображений и их свойства
6. Алгебраическая система.
7. Чёткие и нечёткие соответствия.
8. Понятие мощность множества. Способы задания множеств, мультимножеств, нечетких множеств.
9. Наглядное представление задаваемых множеств. Диаграмма Эйлера-Венна. Индикаторы множества.
10. Классификация множеств. Числовые характеристики.
11. Кардинальные и трансфинитные числа.
12. Аксиоматика содержательно (интуитивно) построенных множеств.
13. Парадоксы Рассела и Кантора.
14. Операции, выполняемые над множествами и мультимножествами
15. Операции, выполняемые над нечеткими множествами
16. Аксиоматика формально построенных теорий множеств.
17. Определение комбинаторного анализа. Классификация комбинаторных задач.
18. Упорядоченные множества. Элементы комбинаторики
19. Треугольник Паскаля. Число Белла. Число Стирлинга.
20. Метод включений и исключений.
21. Задачи решаемые в комбинаторном анализе, их примеры.
22. Определение соответствий. Бинарные соответствия. Чёткие и нечёткие соответствия.
23. Классификация бинарных соответствий. Примеры интерпретации и способы задания.
24. Таблица Кэли. Операции над соответствиями.
25. Определение бинарного отношения.
26. Специальные бинарные отношения: порядок, эквивалентность.
27. Свойства бинарных отношений.
28. Представление бинарных отношений порядка с помощью диаграмм Хассе.
29. Отношение, нечеткое отношение: понятия, способы задания и операции, выполняемые над ними
30. Основные алгебраические системы
31. Булева алгебра логики. Язык алгебры логики.
32. Задача Венна. Логические (булевы) функции как n-арные операции.
33. Способы задания логических функций. Табличные задания булевых функций.
34. Эквивалентные преобразования логических функций.
35. Происхождение теории графов. Задача о Кенигсбергских мостах
36. Основные понятия теории графов: вершины, ребра, инцидентность.
37. Типы графов: гиперграф, псевдограф, мультиграф, элементарный граф. Способы представления графов.
38. Изоморфизм графов.
39. Понятие подграфа, надграфа, остовного подграфа.
40. Маршруты (цепь, простая цепь, цикл, простой цикл) и связность.
41. Степень графа. Однородный граф, полный граф, нуль-граф, регулярный граф.
42. Дополнение графа, самодополнительный граф.
43. Двудольный граф. Условие разнообразия.
44. Связные и несвязные графы. Блоки. Точка сочленения. Мост. Неразделимый граф.
45. Независимые и доминирующие множества. Число независимости, число доминирования.
46. Деревья. Правило экономичности.
47. Операции на графах.
48. Объединение G1ÈG2 и дизъюнктивное объединение графов.
49. Соединение G1+G2 графов.
50. Произведение G1´G2 графов.
51. Композиция G1[G2] графов.
52. Удаление вершин.
53. Удаление и добавление ребра (дуги).
54. Отождествление вершин.
55. Стягивание ребра (дуги).
56. Расщепление вершины.
57. Гомоморфизм.
58. Обходы графов: эйлеровы и гамильтоновы графы.
59. Планарность. Плоский граф. Укладка графа. Максимальный планарный граф.
60. Раскраска графов. Правильная раскраска. Хроматическое число графа. Гипотеза 4-х красок.
61. Матрицы, ассоциированные с графами: матрица инцидентности, матрица смежностей, матрица циклов.
62. Понятие алгоритма. Характерные черты. Численные и логические алгоритмы.
63. Алгоритмы анализа графов: поиск кратчайших путей в графе;
64. Алгоритмы анализа графов: нахождение самого длинного (критического) пути в ориентированном ациклическом графе;
65. Алгоритмы анализа графов: задача поиска гамильтонова цикла; задача о коммивояжере.
66. Потоки в сетях. Максимальный поток. Пропускные способности.
67. Теорема о спросе и предложении. Размещение центров.
68. Условие разнообразия. Правило экономичности.
69. Задача о наименьшем покрытии.
70. Задачи сетевого планирования.
71. Задача о коммивояжере.
72. Задача о наименьшем покрытии.
73. Связные и несвязные графы. Компоненты связности
74. Задачи сетевого планирования.
75. Максимальная пропускная способность сети.
76. Оптимизационные задачи теории графов.
77. Алгоритм поиска маршрута в графе (алгоритм Тэрри).
78. Графы бинарных отношений.
79. Алгоритм раскраски вершин.
80. Поиск маршрутов в ориентированном графе (алгоритм фронта волны).
81. Алгоритм поиска минимального разреза.
82. Алгоритм Дейкстры.
83. Алгоритм поиска максимального пути на графе.
84. Эквивалентные преобразования логических функций.
85. Правило экономичности в теории графов.
Примеры практических заданий
1. Решить задачу поиска кратчайшего пути в графе при помощи алгоритма Дейкстры
2. Решить задачу нахождения критического пути в ориентированном ациклическом графе
3. Решить задачу поиска гамильтонова цикла
4. Решить задачу о коммивояжере
5. Решить задачу о Кенигсбергских мостах
6. Найти максимальный поток в сети
7. Найти наибольший поток в сети
8. Решить задачу о наименьшем покрытии.
9. Решить задачу сетевого планирования.
10. Найти компоненты связности графа
11. Найти маршрут в графе при помощи алгоритма Тэрри.
12. Раскрасить вершины графа.
13. Найти маршрут в ориентированном графе (алгоритм фронта волны).
14. Найти минимальный разрез графа.
15. Найти экономическое дерево графа
16. Алгоритм поиска максимального пути на графе.
17. Эквивалентные преобразования логических функций.
18. Правило экономичности в теории графов.
19. Упростить формулу 
20. Упростите формулу 
.
21. Какое наибольшее количество ребер можно удалить из полного графа с n вершинами, чтобы он остался связным?
22. Докажите, что любое дерево, имеющее не менее двух вершин, содержит, как минимум, две висячие вершины.
23. Докажите справедливость тождеств: (AÈB)\B=A\B
24. Можно ли нарисовать 11 отрезков так, чтобы каждый пересекался ровно с тремя другими?
25. Докажите, что подграф полного двудольного графа является полным двудольным графом.
26. Докажите, что полный граф является надграфом любого полного двудольного графа с тем же количеством вершин.
27. Докажите, что любой незамкнутый маршрут, соединяющий вершины А и В, содержит в себе простую цепь, соединяющую эти вершины.
28. Докажите, что связный граф остается связным тогда и только тогда, когда это ребро содержится в некотором цикле.
29. Докажите, что элементарный граф с n вершинами, степень каждой из которых не меньше (n-1)/2, является связным.
30. Докажите, что связный граф с n вершинами содержит не менее n-1 ребр.
31. Можно ли так ориентировать ребра полного графа, чтобы в нем не появилось ни одного контура?
32. По матрице смежности построить наглядное изображение и охарактеризовать граф
Формы текущего контроля
· Оценка работы студента в аудитории (оценка за текущую успеваемость): по каждой теме за работу на интерактивных занятиях выставляется в рабочую ведомость оценка 0 или 1 балл.
Интегральная оценка текущей работы студента (Оаудиторная) рассчитывается как процент оценок «зачтено» за выполненные на интерактивных занятиях работы, приведенная к 10-балльной оценке
· Оценка выполнения заданий для самостоятельной работы (решение практических задач и выполнение расчетно-графических работ) студентов (Осам. работа=∑ Осам. работа. i): максимальная оценка выполнения каждого задания 5 баллов
Интегральная оценка самостоятельной работы студента (Осам. работа) рассчитывается как сумма оценок за выполненные работы:
Осам. работа = ∑ ОПр.задача. i + ∑ ОРГР. j
Форма промежуточной аттестации (по семестрам)
· экзамен (Оэкзамен): максимальная оценка 20 баллов
Методика формирования накопительной оценки текущего контроля знаний и умений
Накопительная оценка текущего контроля знаний и умений студентов рассчитывается как взвешенная интегральная оценка: 10-балльной оценки работы студента в аудитории и средней арифметической тридцати 5-балльных оценок выполнения заданий для самостоятельной работы (решение 30-и практических задач).
Методика формирования результирующей оценки промежуточной аттестации (по-семестровой) знаний и умений
Изучение дисциплины заканчивается экзаменом, который (с учетом ответов студента на заданные преподавателем дополнительные вопросы по тематике изучаемой дисциплины) оценивается 20-балльной оценкой.
Итоговая оценка (Оитоговая) рассчитывается по формуле:
Оитоговая = (k1· Оэкзамен + k2 Оаудиторная+ Осам. работа /30)/3
Рекомендуемая литература
1. Судоплатов С.В., Овчинникова Е.В. Дискретная математика.– Москва-Новосибирск, 2007.
2. Морозоа В.Д. Введение в анализ.– М.: Изд. МГТУ им. И.Э. Баумана, 1996.
3. Белоусов А.И., Ткачев С.Б. Дискретная математика.– М.: Изд. МГТУ им. И.Э. Баумана, 2006.
4. Алеев Ю.А., Тюрин С.Ф. Дискретная математика и математическая логика.– Москва, 2006.
5. Шапорев С.Д. Дискретная математика.– СПб, 2007.
6. Новиков Ф.А. Дискретная математика для программистов.– СПб.: Изд. «Питер», 2001.
7. Иванов Б. Н. Дискретная математика. Алгоритмы и программы. – М.: Лаборатория базовых знаний, 2002.
8. Акимов О. Е. Дискретная математика: логика, группы, графы. – М.: Лаборатория базовых знаний, 2001.
9. Абатуров В.А. Дискретная математика. Модули 0-3. Введение в дискретную математику.– М.: МПСУ, 2011.
10. Абатуров В.А. Дискретная математика./ Основные структуры. Элементы математической логики и теории алгоритмов.// Методические указания по практическим (семинарским) занятиям.– М.: МПСУ, 2011.
Интернет-ресурсы:
11. https://mirea.boom.ru/diskret.html
12. https://rk-cmb.chat.ru/algo/ln_dm_01.htm
13. https://www.isu.ru/~slava/do/disc/curshome.htm
14. "Введение в анализ, синтез и моделирование систем" (https://www.intuit.ru/)
15. https://kurs.ido.tpu.ru/courses/disk_math/