ВОПРОСЫНА ЭКЗАМЕН ПО ДИСКРЕТНОЙ МАТЕМАТИКЕ
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. Алгоритм ПГ (поиск в глубину) построения остовного дерева связного графа.
33. Алгоритмы Краскала и Прима нахождения остова минимального веса во взвешенном связном графе. Обоснование алгоритма.
34. Алгоритм нахождения кратчайшего пути между парой вершин в связном графе. Понятие дерева кратчайших путей.
35. Плоские и планарные графы. Укладка графа на плоскость. Алгоритм.
36. Теорема о непланарности графа К5. Критерий планарности графа.
37. Теорема об укладке графа в трёхмерное пространство и на сферу.
38. Грани плоского графа. Формула Эйлера.
39. Следствия из теоремы Эйлера и доказательство непланарности графа К3,3.
40. Определение Эйлерового графа. Критерий Эйлеровости графа. Задача о Кенигсбергских мостах и её решение.
41. Определение Гамильтонова графа. Некоторые теоремы о гамильтоновости графа. Задача коммивояжера.
42. Вершинная и рёберная независимость. Задача о ферзях. Паросочетания.
43. Паросочетания в двудольном графе. Задача о назначениях. Критерий существования в двудольном графе совершенного паросочетания.
44. Алгоритм построения наибольшего совершенного паросочетания в
двудольном графе.
45. Правильная раскраска графа. Хроматическое число. Теорема о раскраске плоского графа.
46. Проблема четырёх красок и её решение.
47. Элементы математической логики. Высказывания. Предикаты. Высказывания, содержащие кванторы. Примеры.
48. Операции над высказываниями и их свойства. Построение отрицания высказывания, содержащего кванторы. Примеры.
49. Законы алгебры логики и их применение.
50. Теоремы. Виды теорем. Примеры.