Задачи для подготовки к экзамену

1. Доказать или опровергнуть равенство, используя метод характеристических функций:

2. Доказать или опровергнуть равенство, используя метод эквивалентных преобразований:

3. Доказать или опровергнуть равенство, используя диаграммы Эйлера-Венна:

4. Изобразить на диаграмме Эйлера-Венна следующее множество:

5. Построить транзитивное замыкание отношения, заданного матрицей:

6. Выяснить, является ли отношение, заданное следующей матрицей, транзитивным:

7. Для множества привести примеры:

· рефлексивного отношения;

· симметричного отношения;

· транзитивного отношения;

· отношения порядка;

· отношения частичного порядка;

· отношения линейного порядка;

· отношения эквивалентности.

8. Выписать все коды Грэя длины 5.

9. Построить таблицу истинности для высказывания: .

10. Найти совершенную ДНФ для булевой функции .

11. Найти минимальную ДНФ для булевой функции , используя единичный куб.

12. Найти минимальную ДНФ для булевой функции , используя карту Карно.

13. Найти минимальную ДНФ для булевой функции , используя алгоритм Куэйна-Маккласки.

14. В номере автомобиля записываются подряд буква, три цифры и ещё две буквы. Сколько таких номеров можно составить, если использовать только буквы А,В,Е,К,М,Н,О,Р,С,Т,У,Х?

15. Какой номер автомобиля из предыдущей задачи будет первым, если выписывать все номера в лексикографическом порядке? Какой номер будет последним? Какой номер следует за номером «У 899 ХХ»? Какой номер ему предшествует?

16. В автомобиле 5 мест. Сколькими способами пять человек могут занять места для путешествия, если водить машину могут только трое из них?

17. После хоккейного матча каждый игрок одной команды пожал руку каждому игроку другой. Сколько всего игроков присутствовало на площадке, если было совершено 323 рукопожатия?

18. Сколькими способами можно выбрать на шахматной доске две клетки так, чтобы из одной в другую можно было попасть ходом ладьи? Ходом коня?

19. Сколькими способами 5 человек могут встать в очередь к билетной кассе? Как называется каждая такая комбинация в комбинаторике?

20. В чемпионате по футболу участвует 16 команд. Сколькими способами могут распределиться 3 призовых места? Как называется каждая такая комбинация в комбинаторике?

21. Сколько различных четырёхзначных чисел можно составить из четырёх карточек, на которых написаны цифры: а) 1,2,3,4; б) 1,2,3,3; в) 1,1,2,2.

22. Сколькими способами можно выбрать двух дежурных из класса, в котором 25 учеников. Как называется каждая такая комбинация в комбинаторике?

23. Сколькими способами в карточке лотереи «Спортлото» можно зачеркнуть 5 номеров из 36? Как называется каждая такая комбинация в комбинаторике?

24. Группу из 20 туристов нужно распределить по 3 маршрутам так, чтобы по первому маршруту шли 8 человек, по втором – 7, по третьему – 5. Сколькими способами это можно сделать?

25. Определить, сколько решений в неотрицательных целых числах имеет уравнение при условии, что .

26. Определить, сколько решений в натуральных числах имеет уравнение при условии, что .

27. Решить рекуррентное соотношение второго порядка с начальными условиями .

28. В таблице приведены запросы и количество страниц, которые нашел поисковый сервер по этим запросам в некотором сегменте Интернета:

Запрос	Количество страниц (тыс.)
(Суворов & Альпы) | (Суворов & Варшава)
Суворов & Варшава
Суворов & Варшава & Альпы

Сколько страниц (в тысячах) будет найдено по запросу

Суворов & Альпы

29. По заданной весовой матрице ориентированного графа найти кратчайший путь между двумя заданными вершинами и его длину, используя алгоритм Дейкстры:

30. По заданной весовой матрице ориентированного графа найти длины кратчайших путей между всеми парами вершин, используя алгоритм Флойда-Уоршалла:

31. По заданной весовой матрице неориентированного графа найти минимальный каркас и его вес, используя алгоритм Краскала:

32. По заданной весовой матрице неориентированного графа найти минимальный каркас и его вес, используя алгоритм Прима:

33. Найти все с точностью до изоморфизма деревья, содержащие 5 вершин.

34. Найти для заданного дерева его код Прюфера:

3 6 5 ―― 12

| | |

8 ―― 7 ―― 1 ―― 2 ――9 ―― 4

| |

11 10

35. Построить дерево по его коду Прюфера: 7,9,1,7,2,2,7,1,2,5,12.

36. Найдите НОД(126, 180) и его линейное представление.

37. Найдите количество нулей, на которые заканчивается число 100!

38. Разложите 2560000 на простые множители.

39. Построить таблицу умножения в Z₅.

40. Найти все классы вычетов в Z₁₀, которые имеют обратные.

41. Решите уравнение в Z₉.

42. Вычислите функцию Эйлера j(2560).

43. Для простой «задачи о рюкзаке» (3, 4, 9, 20, 40, 77, 155, 311) и чисел D=623, x=13, y=48 построить сложную задачу и зашифровать с её помощью сообщение 10101110.

44. С помощью простой «задачи о рюкзаке» (3, 4, 9, 20, 40, 77, 155, 311) и чисел D=623, x=13, y=48 расшифровать сообщение 835.

45. Для заданных простых чисел p=3557, q=2579 и открытой экспоненты e=3 построить секретный ключ (n,d) с помощью алгоритма RSA.

46. С помощью секретного ключа (n=9173503, d=6111579) расшифровать сообщение 4051753, зашифрованное по алгоритму RSA.