Вопросы
Элементы теории множеств.
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. Алгоритмически неразрешимые проблемы.
Задачи.
Элементы теории множеств, комбинаторики
и логики предикатов
| Задача 1.Перечислить все подмножества множества А: 0) А= {2,7,9, 11}; 1) A= {x,y,z,t}; 2) A = {a,b,c,d}; 3) A = {X,Y,Z,T}; 4) А = {+,-,×,/}; 5) А = {!,#,%,+}; 6) А = {α,β,λ,δ} 7) А= {←,↑,→,↓}; 8) А= {Вася, Петя, Маша, Рая}; 9) A = {Q,W,E,R}. | Задача 2.Найти пересечение, объединение и разность следующих множеств: 0) А= {1,3,5,7, 8}, В = {2,4,6,8,10}, С = {а,Ь,с}; 1) A={a,b,d}, B = {l,5,d}, C={2,a,8}. 2) A = {x,y,z,t}, B = {l,5,d}, C = {a,b,z,1, 5}; 3) A = {a,b,z,t}, B = {l,5,d}, C = {x,y,z,1, 5}; 4) A={a,b,d}, B = {l,5,d}, C = {2,a,8}; 5) A ={a, b, c, d}, В = {1,5, d}, С = {2, a, x, 8}; 6) A={a,b,d,e,f}, B = {l,5,d}, C = {2,a,8}; 7) A = {x, y, a, b}, В = {1, 5, d}, С = {a, b, z, 1, 5}; 8) A = {l,2,3,7,8,10}, B = {2,4,6,8,10}, C = {x,y,z}; 9) A ={a, b, c, d,4}, В = {1,а, 5, d}, С = {2, a, b, 8}; |
| Задача 3. Сколько трехзначных чисел, меньших заданного числа А можно образовать, используя цифры 2,3,4,5,6,8,9, если: 0) А=450; 1) А=350; 2) А=250; 3) А=420; 4) А=410; 5) А=380; 6) А=370; 7) А=430; 8) А=390; 9) А=460. | Задача 4. Сколькими способами N пар, пришедших в кино, могут занять места, если все пять пар сидят подряд и: 0) N=4; 1) N=5; 2) N=7; 3) N=6; 4) N=8; 5) N=9; 6) N=3; 7) N=10; 8) N=12; 9) N=11. |
| Задача 5.В соревнованиях участвуют N спортсменов. Сколько существует вариантов распределения трех призовых мест, если: 0) N=8; 1) N=7; 2) N=6; 3) N=9; 4) N=10; 5) N=5; 6) N=11; 7) N=12; 8) N=15; 9) N=13; | Задача 6. Сколько существует N- битовых строк, содержащих А нулей и К единиц, если: 0) N=8; А=3, К=5; 1) N=8; А=2, К=6; 2) N=8; А=4, К=4; 3) N=9; А=2, К=7; 4) N=9; А=3, К=6; 5) N=9; А=4, К=5; 6) N=10; А=3, К=7; 7) N=10; А=4, К=6; 8) N=10; А=2, К=8; 9) N=10; А=5, К=5. |
| Задача 7. Постройте матрицу одноместного предиката Q(x), если: 0) Q (x)=”2x2 кратно 5”, при xÎ (-8, 13); 1) Q (x)=”3x2 кратно 2”, при xÎ [-5, 17); 2) Q (x)=”4x2 кратно 5”, при xÎ (-10, 11); 3) Q (x)=”3x3 кратно 2”, при xÎ [-9, 12); 4) Q (x)=”5x2 кратно 3”, при xÎ (-5, 13]; 5) Q (x)=”3x3 кратно 4”, при xÎ (-7, 12); 6) Q (x)=”5x3 кратно 4”, при xÎ [-6, 15]; 7) Q (x)=”x4 кратно 2”, при xÎ (-11, 10); 8) Q (x)=”x3 кратно 5”, при xÎ (-9, 10); 9) Q (x)=”x2 кратно 3”, при xÎ (-7, 15); | Задача 8. Изобразите геометрически множество истинности одноместного предиката G(x), если: 0) G(x)=”8 ³ -2x > 4/3”; 1) G(x)=”12 >1/5x > -5”; 2) G(x)=”-9 < 3x £ 3/2”; 3) G(x)=”11 > 3/4x > -3”; 4) G(x)=”0 ³ x >-28/4”; 5) G(x)=”–14 £ 7x £ 1/4”; 6) G(x)=”1/8 < -3x £ 9”; 7) G(x)=”1 ³ -1/6x > -1/2”; 8) G(x)=”-1/3 > 6x >-36”; 9) G(x)=”5 ³ 1/2x ³ -1/4”; |
Элементы теории графов
Задача 9.Дана матрица смежностиориентированного графа. Построить его матрицу инцидентности и нарисовать диаграмму графа.
0) 
| 1) 
| 2) 
| 3) 
| 4) 
|
5) 
| 6) 
| 7) 
| 8) 
| 9) 
|