diskrete

Теоретический минимум ДМ

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. Алгоритм построения СДНФ по таблице истинности

37. Сокращенная ДНФ

38. Минимальная ДНФ

39. Тупиковая ДНФ

40. Определение карты Карно или диаграммы Вейча

41. Алгоритм упрощения высказываний картами

42. Определение макстерма

43. Определение СКНФ

44. Алгоритм построения СКНФ по таблице истинности

45. Теорема о разложении КНФ

46. Что такое арность функции?

47. Суперпозиция функций: подстановка и отождествление

48. Замкнутое множество функций

49. Замыкание множества функций

50. Полная система функций. Безызбыточная полная система функций

51. Перечислите известные классы эквивалентности функций

52. Определение самодвойственной функции

53. Определение линейной функции

54. Определение  монотонной функции

55. Формулировка критерия Поста

56. Полином Жегалкина

57. Принцип математической индукции

58. Принцип умножения и сложения в комбинаторике

59. Принцип включения-исключения

60. Перестановка с повторениями и без

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. Матрица смежности

86. Матрица инцидентности (ориентированный и неориентированный граф)

87. Пограф. Надграф. Частичный граф.

88. Собственный и несобственный подграф

89. Регулярный граф, полный граф.

90. Объединение и пересечение графов. Дополнение графа.

91. Путь. Цепь. Простая цепь. Цикл и простой цикл.

92. Определение связности в неориентированном графе. Компоненты связности

93. Слабая связность. Сильная связность

94. Реберная двусвязность

95. Мост (какие-то 2 определения на выбор)

96. Вершинная двусвязность

97. Точка сочленения (2 определения). Блок (1 определение)

98. Дерево. Лес

99. Определение графа блоков и точек сочленения

100. Определение графа компонент реберной двусвязности

101. Остов графа. Цикломатическое число. Фундаментальная система циклов

102. Минимальное остовное дерево

103. Определение безопасного ребра

104. Лемма о безопасном ребре

105. Диаметр графа, центр и радиус

106. Теорема о поиске числа путей заданной длины с помощью матрицы смежности орграфа

107. Лемма о белых путях

108. Эйлеров путь, цикл, граф. Критерий эйлеровости

109. Произвольно вычерчиваемый граф

110. Гамильтонов путь, цикл, граф.

111. Формулировка теоремы Оре

112. Формулировки теорем Дирака и Гуйя-Ури

Тема		Вопрос
Теория множеств	1	Основные определения. Способы задания. Операции над множествами.
	2	Свойства операций над множествами. Диаграммы Эйлера-Венна. Декартово произведение множеств.
Бинарные отношения	3	Основные определения. Способы задания отношений. Композиция отношений. Свойства бинарных отношений.
	4	Отношения эквивалентности. Разбиение. Отношения строгого\нестрогого порядка. Упорядоченные множества. Отношения соответствия. Функциональные отношения.
Математическая индукция	5	Принцип математической индукции
Математическая логика	6	Высказывание. Булева алгебра. Аксиомы булевой алгебры. Теоремы одной переменной. Свойства дизъюнкции и конъюнкции.
	7	Теорема единственности дополнения. Теорема поглощения. Теоремы склеивания, де Моргана.
Булевы функции	8	Понятие булевой функции. Способы задания булевой функции. Минтермы. СДНФ. Алгоритм построения СДНФ.
	9	Дизъюнктивные и конъюнктивные формы. Разложение Шеннона. Теорема о единственности представления функции в СДНФ.
	10	Карты Вейча. Упрощение высказываний картами. Поиск сокращенных, минимальных и тупиковых форм картами.
	11	Макстермы. СКНФ. Построение СКНФ. Нахождение через СДНФ. Методы посроения сокращенных форм.
Функциональная полнота	12	Унарные и бинарные булевы функции. Суперпозиции. Полные системы функций. Классы эквивалентности.
	13	Теорема Поста с доказательством.
	14	Алгебра Жегалкина. Единственность представления полиномом. Построение методом треугольника и Паскаля.
Комбинаторика	15	Основные комбинаторные объекты. Принципы умножения и сложения (принцип включения исключений).
	16	Перестановки. Размещения. Сочетания. Биномиальная теорема. Получение коэффициентов через треугольник Паскаля. Теорема Вандермонда.
	17	Лексикографический порядок. Генерация следующего в лексикографическом порядке объекта (сочетания и перестановки).
Теория вероятности	18	Определения: выборочное про-во, событие, вероятность. Свойства вероятности. Вероятность объединения событий.
	19	Независимые и несовместные события. Независимость попарная и в совокупности. Схема Бернулли. Теорема об осуществлении k успехов в n испытаниях.
	20	Условная вероятность. Формула полной вероятности. Формула Байеса.
	21	Случайная величина, распределение и функция распределения. Математическое ожидание. Дисперсия.
Теория графов	22	Основные определения. Изоморфизм графов. Ориентированные графы. Лемма о рукопожатиях. Дополнение графа. Объединение и пересечение графов.
	23	Матрица смежности со свойствами. Матрица инцидентности со свойствами.
	24	Путь и цепи. Реберно и вершинно простые пути. Лемма о существовании простой цепи при существовании пути в графе. Связность и компоненты связности. Слабая и сильная связность. Компоненты сильной связности.
	25	Отношение реберной двусвязности. Мосты. Эквивалентные определения. Лемма и числе компонент после удаления моста. Лемма о цикле и мосте.
	26	Отношение вершинной двусвязности. Блоки и точки сочленения. Эквивалентные определения. Леммы про точку сочленения: о простых цепях и о единственности общей точки для двух блоков
	27	Леммы про точку сочленения: о принадлежности общему циклу любых двух вершин или любых вершины и ребра. Теорема эквивалентных определений блока.
	28	Дерево. Эквивалентные определения. Граф блоков-точек сочленения. Док-во что он дерево. Граф компонент реберной двусвязности. Док-во что он дерево.
	29	Остов графа. Цикломатическое число. Фундаментальная система циклов. Минимальное остовное дерево (MST). Лемма о безопасном ребре. Алгоритмы поиска MST: Прима и Краскала.
	30	Поиск кратчайших путей во взвешенном графе: Дейкстра. Расстояния в графе. Диаметр. Центр.Радиус. Поиск числа путей определенной длины с помощью матрицы смежности.
	31	Обход в глубину: алгоритм. Лемма о белых путях. Основные области применения обхода в глубину.
	32	Обход в ширину: алгоритм. Теорема нахождении кратчайших путей с помощью BFS. Поиск центра и диаметра дерева.
	33	Эйлеровы циклы. Теорема об эквивалентности определений. Теорема о покрытии ребер графа путями. Критерий эйлеровости. Поиск эйлерова пути или цикла.
	34	Произвольно вычерчиваемые графы.
	35	Гамильтоновы графы. Теорема Оре. Теорема Дирака. Гуйя-Ури (без док-ва). Поиск гамильтонова цикла.