Образовательная программа 6B06102 «Информационные системы»

Дисциплина DM 3209 − «Дискретная математика»

Модуль OPD 05 − «Общепрофессиональных дисциплин»

Образовательная программа 6B06102 – «Информационные системы»

Факультет инновационных технологий

Кафедра информационно-вычислительные системы

Разработаны: старшим преподавателем Олейниковой А.В.

Обсуждены на заседании кафедры «Информационно-вычислительные системы»

Зав. кафедрой ___________ Калинин А.А. «___»________2023 г.

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. 
    Записать со знаком факториала:1•2•3•4•4•5•6.
    
73. 
    Записать с использованием знака факториала: 1•2•3•4•5•7•8•9•10.
    
74. 
    Записать с использованием знака факториала: 1•2•3•7•8•9.
    
75. 
    Записать со знаком факториала: 1•2•4•6•7•8. Здесь пропущены два числа: 3 и 5.
    
76. 
    Записать со знаком факториала:1•2•3•4•4•5.
    
77. 
    Записать со знаком факториала: 1•3•5•6•7•8. Здесь пропущены два числа: 2 и 4.
    
78. 
    На окружности расположены n точек. Каждая пара точек соединена прямой линией так, что в любой точке пересекаются не более двух прямых. Сколько точек пересечения имеется внутри круга? Точки пересечения линий с окружностью не учитывать.
    
79. 
    В урне пять шаров с номерами 1, 2, 3, 4, 5. Вынимают один шар и записывают его номер. Шар возвращают в урну и наугад снова выбирают один шар и номер его записывают справа от первой цифры. Получится двухразрядное число. Сколько возможно таких чисел?
    
80. 
    В урне пять шаров с номерами 1, 2, 3, 4, 5. Вынимают один шар и записывают его номер. Шар возвращают в урну и наугад снова выбирают один шар и номер его записывают справа от первой цифры. Получится двухразрядное число. Пусть шары извлекают три раза. Сколько получится трехзначных чисел?
    
81. 
    Сколько существует трехразрядных шестеричных чисел?
    
82. 
    Сколько существует трехразрядных десятичных чисел, не содержащих повторяющихся цифр, если используются только цифры 3, 5, 9?
    
83. 
    Сколько существует трехразрядных десятичных чисел, не содержащих повторяющихся цифр, если используются только цифры 2, 4, 8?
    
84. 
    Сколько существует трехразрядных десятичных чисел, не содержащих повторяющихся цифр, если используются только цифры 1, 3, 7?
    
85. 
    Сколько существует трехразрядных десятичных чисел, не содержащих повторяющихся цифр, если используются только цифры 2, 4, 6?
    
86. 
    Сколько различных слов можно составить из букв слова «километр», если под словом понимать всякую последовательность из восьми букв?
    
87. 
    Сколько существует четырехбуквенных слов, в которых три буквы «а» и одна буква «в»?
    
88. 
    Сколько различных слов можно составить, переставляя буквы слова «ротор»? В слове «ротор» 5 букв. Из них две буквы «р», две буквы «о», одна буква «т».
    
89. 
    Сколько различных слов можно составить, переставляя буквы слова «мотор»? В слове «ротор» 5 букв. Из них одна буквы «м», две буквы «о», одна буква «т».
    
90. 
    Сколько существует четырехзначных десятичных чисел, если в каждом из них все цифры разные?
    
91. 
    Сколько существует трехразрядных десятичных чисел, не содержащих четных цифр и не содержащих одинаковых цифр?
    
92. 
    Имеется 12 ролей. Четыре артиста могут играть любую роль, и всем им предлагается выбор. Сколькими способами можно распределить роли между ними?
    
93. 
    Сколько можно образовать четырехразрядных чисел, используя только цифры 3, 7, 8, 9, если повторения возможны?
    
94. 
    Сколько всего существует трехразрядных десятичных чисел, которые могут быть составлены из цифр 1, 2, 4, 5, 6, 8?
    
95. 
    Дано множество букв: А = {а, б, в, г, д, е}. Сколько двух- и трехбуквенных слов можно составить из этих букв?
    
96. 
    Сколько существует пятиразрядных чисел шестеричной системы счисления?
    
97. 
    Сколько существует шестиразрядных двоичных чисел, содержащих три единицы?
    
98. 
    Упростить:
    
99. 
    Дано А= (1,3,5,6), В = (2,3,4,5,7), С = (1,4,5), I = (1,2,3,4,5,6,7). Найти: .
    
100. 
     Дано А= (1,3,5,6), В = (2,3,4,5,7), С = (1,4,5), I = (1,2,3,4,5,6,7). Найти:
     
101. 
     Дано А= (1,3,5), В = (2,3,4,7), С = (1,4,5), I = (1,2,3,4,5,6,7). Найти: .
     
102. 
     Дано А= (1,3,5,6), В = (2,3,4,5,7), С = (1,4,5), I = (1,2,3,4,5,6,7). Найти: .
     
103. 
     Найти значение выражения: =
     
104. 
     Найти значение выражения: =
     
105. 
     Найти значение выражения: =
     
106. 
     Записать СДНФ функции, заданной следующей картой Вейча:
     
107. 
     Задана функция: f = (0, 1, 3, 6, 7, 8, 12, 13, 14, 15). Нанесём её на карту Вейча и записать в СДНФ.
     
108. 
     Задана функция: f = (0, 1, 6, 7, 8, 12, 1). Нанесём её на карту Вейча и записать в СДНФ.
     
109. 
     Задана функция: f = (2, 4, 6, 8). Нанесём её на карту Вейча и записать в СДНФ.
     
110. 
     Задана функция: f = (0, 1, 3, 14, 15). Нанесём её на карту Вейча и записать в СДНФ и упростить.
     
111. 
     Упростить по методу Квайна f = (1, 4, 8, 12).
     
112. 
     Упростить по методу Квайна f = (1, 2, 3, 6, 8, 11,15).
     
113. 
     Упростить по методу Квайна f = (1, 3, 5, 8 11).
     
114. 
     Задана функция: f = (0, 1, 6, 7, 8, 12, 13). Нанесём её на карту Вейча и записать в СДНФ.
     
115. 
     Задана функция: f = (2, 4, 7, 15). Нанесём её на карту Вейча и записать в СДНФ.
     
116. 
     Задана функция: f = (1,3, 8, 9). Нанесём её на карту Вейча и записать в СДНФ.
     
117. 
     Задана функция: f = (0, 1, 3, 14, 15). Нанесём её на карту Вейча и записать в СДНФ и упростить.
     
118. 
     Упростить по методу Квайна f = (1, 2, 3, 6, 8, 11,15).
     
119. 
     Упростить по методу Квайна f = (1, 3, 5, 8 11).
     
120. 
     Упростить по методу Квайна f = (1, 3, 6, 15).
     
121. 
     Упростить по методу Квайна f = (2, 4, 6, 11).
     
122. 
     Упростить по методу Квайна f = (1, 3, 8, 10).
     
123. 
     Упростить по методу Квайна f = (0, 2, 4, 8).
     
124. 
     Дано А= (1,3,5,6), В = (2,3,4,5,7), С= (1,4,5), I= (1,2,3,4,5,6,7). Найти: .
     
125. 
     Дана . Упростить.
     
126. 
     Дана . Упростить.
     
127. 
     Дана . Упростить.
     
128. 
     Дана . Упростить.
     
129. 
     Дана . Упростить.
     
130. 
     Дана . Упростить.
     
131. 
     Даны множества . Найти элементы множества .
     
132. 
     Даны множества . Найти элементы множества .
     
133. 
     Найти значение выражения:
     
134. 
     Найти элементы нечеткого множества , если , .
     
135. 
     Найти значение выражения: .
     
136. 
     Найти значение выражения:
     
137. 
     Найти значение выражения: .
     
138. 
     Найти значение выражения: .
     
139. 
     Найти значение выражения: .
     
140. 
     Найти значение выражения:
     
141. 
     Найти значение выражения:
     
142. 
     Найти значение выражения:
     
143. 
     Найти значение выражения:
     
144. 
     Найти значение выражения:
     
145. 
     Найти значение выражения:
     
146. 
     Найти значение выражения:
     
147. 
     Найти значение выражения:
     
148. 
     Пусть даны нечеткие множества , , . Запишите результат операции .
     
149. 
     Пусть дана диаграмма Найти: .
     
150. 
     Записать СДНФ функции, заданной следующей картой Вейча:
     

Список рекомендуемой литературы

1. Лелонд О. В., Тренина М. А. Дискретная математика. Издательство: Тольятти: Тольяттинский государственный университет, 2018.