Условия и решения задач к экзамену по Наимову - файл n1.doc

приобрести
Условия и решения задач к экзамену по Наимову
скачать (19904 kb.)
Доступные файлы (5):
n1.doc522kb.24.05.2009 20:19скачать
n2.txt1kb.16.01.2011 15:09скачать
n3.doc75kb.19.06.2010 01:02скачать
n4.doc19842kb.19.06.2010 01:04скачать
n5.pdf196kb.13.06.2009 15:16скачать

n1.doc

Сто десять задач по дискретной математике
1. Множества, бинарные отношения, отображения,

эквивалентность, группа, кольцо, поле
1. Доказать, что для любых подмножеств , . . . , любого множества справедливы формулы де Моргана

,

.
2. Доказать, что множество вещественных чисел эквивалентно множеству точек плоскости.
3. Доказать, что множество рациональных чисел счетно.
4. Найти инфимум, супремум, максимум и минимум множества

.
5. Доказать, что на множестве натуральных чисел бинарное отношение



является отношением эквивалентности. Найти классы эквивалентности.
6. Пусть - множество всех подмножеств множества . Найти и доказать, что частично упорядочено относительно бинарного отношения включения подмножеств. Построить диаграмму Хассе.
7. Для бинарного отношения

найти , .
8. Привести пример бинарного отношения, которое

а) рефлексивно, симметрично, нетранзитивно;

б) рефлексивно, несимметрично, транзитивно.
9. Привести пример бинарного отношения, которое

а) рефлексивно, антисимметрично, нетранзитивно;

б) нерефлексивно, симметрично, транзитивно.
10. На множестве определить отношение строгого порядка.
11. На множестве построить неассоциативную бинарную операцию.
12. На множестве построить ассоциативную, некоммутативную бинарную операцию.
13. На множестве построить ассоциативную, коммутативную бинарную операцию.

14. На множестве четных натуральных чисел определена бинарная операция . Найти решение уравнения .
15. При каком натуральном верно равенство , если бинарная операция * определена формулой .
16. Построить пример отображения которое

а) биективно;

б) инъективно, несюръективно.
17. Построить пример отображения которое

а) неинъективно, сюръективно;

б) неинъективно, несюръективно.
18. Привести пример двух таблиц, к которым применимы все операции реляционной алгебры.
19. На множестве определить бинарную операцию, относительно которой будет полугруппой, но не группой.
20. Привести пример неабелевой группы из шести элементов.
21. Доказать, что группа подстановок четвертого порядка неабелева.
22. Привести пример циклической группы порядка 4.
23. Привести пример группы и ее собственной подгруппы . Найти левые и правые смежные классы по подгруппе .
24. На множестве определить групповую операцию и привести пример фактор-группы.
25. Доказать, что множество является полем относительно операций сложения и умножения по модулю 7.
2. Комбинаторика
26. Доказать формулу бинома Ньютона

.
27. Найти число целых неотрицательных решений уравнения .
28. Сколькими способами можно распределять 30 студентов на производственную практику в три города, так чтобы два определенных студента оказались в одном городе, если в первый город необходимо отправить 15 выпускников, во второй – 8, в третий – 7.
29. Десять книг сколькими способами можно расставить в один ряд, так чтобы три определенные книги оказались рядом.
30. Сколькими способами можно составить букет из семи цветов, используя четыре сорта цветов.
31. В группе из 25 студентов любящих математику – 15, физику – 10, нелюбящих ни математику, ни физику – 8. Сколько студентов любят и математику, и физику.
32. Из 100 студентов знают английский – 28, немецкий – 30, французский – 42, английский и немецкий – 8, английский и французский -10, немецкий и французский – 5, все языки – 3. Сколько студентов не знают ни одного из этих языков.
33. писем сколькими способами можно вложить в конвертов с адресами, так чтобы

а) хотя бы одно письмо попало в свой конверт;

б) ни одно письмо не попало в свой конверт.
34. Найти решение рекуррентного соотношения , , .
35. Найти решение рекуррентного соотношения , , .
36. Вывести общую формулу для чисел Фибоначчи.
37. Найти последовательность чисел по производящей функции .
38. Составить рекурсивный алгоритм вычисления суммы



39. Найти производящую функцию последовательности чисел , .
40. Доказать формулу для числа сочетаний с повторениями .

3. Графы
41. Построить геометрическую реализацию ориентированного графа с множеством вершин и множеством дуг . Найти матрицу смежности графа.
42. Найти граф по его геометрической реализации



43. Найти граф по матрицу смежности

.

44. Найти орграф, если известна его матрица смежности

.
45. Найти граф, если известна его матрица инцидентности

.
46. Найти орграф, если известна его матрица инцидентности

.
47. Найти число всевозможных графов с двадцатью вершинами.

48. Доказать, что если в графе степени всех вершин не меньше двух, то в таком графе существует цикл.

49. Найти число всевозможных графов с двадцатью вершинами, связные компоненты которых регулярны.

50. На множестве натуральных чисел от 1917 до 1991 задать множество ребер так, чтобы получился 7-дольный граф.

51. Для числа ребер связного графа доказать оценку ,

где - число вершин графа.

52. Построить двоичный гиперкуб в случае , и найти его диаметр.

53. Найти число остовных деревьев графа с множеством вершин и множеством ребер .

54. Найти число всевозможных маршрутов длины 4, соединяющих первую и третью вершины графа.

55. Доказать, что связный граф эйлеров тогда и только тогда, когда все вершины графа имеют четную степень.

56. Составить коды де Брейна в случае .

57. Составить коды Грея в случае .

58. Построить пример негамильтонового графа без точек сочленения.

59. Построить пример графа, который

а) эйлеровый, гамильтоновый;

б) неэйлеровый, гамильтоновый;

в) эйлеровый, негамильтоновый.

60. Доказать, что граф задачи о трех колодцах непланарный

61. Доказать, что полный граф с пятью вершинами непланарный

62. Доказать, что для любого связного планарного графа справедлива формула Эйлера , где - число вершин, - число ребер, - число граней графа.

63. Доказать, что в любом планарном графе существует вершина, степень которой не больше пяти.

64. Доказать, что любой граф укладывается в пространстве.

65. Доказать теорему о пяти раскрасках.

66. Найти в данном графе гамильтонову цепь.

67. Найти остов, имеющий наименьшую сумму весов ребер.

68. Найти кратчайший путь между вершинами 1 и 6.

69. Найти максимальный поток для транспортной сети.

70. Докажите, что в группе из шести человек всегда найдутся три человека, знакомые между собой, или три человека, не знакомые между собой (раскраска графа).

71. Каждый из семи мальчиков имеет трех братьев. Докажите, что все мальчики – братья (связные графы).
72. В некоторой компании любые два знакомых не имеют общих знакомых, а любые два незнакомых имеют ровно двух общих знакомых. Докажите, что в этой компании все имеют одинаковое число знакомых.(регулярные графы)
73. Может ли в государстве, в котором из каждого города выходит ровно три дороги, быть ровно 100 дорог между городами? (лемма о рукопожатий)
74. Из какого минимального числа кусков проволоки можно спаять каркас куба? (Толщина всех ребер каркаса должна быть одинаковой). (полуэйлеровы циклы)
75. В информационной сети каждый центр соединен каналами связи с четным числом центров. Докажите, что после уничтожения любого канала сеть не выйдет из строя. (существование цикла в графе)

4. Булевы функции
76. Для булевой функции заданной таблицей найти

а) СДНФ, СКНФ;

б) многочлен Жегалкина;

в) минимальную ДНФ.

x1

0

1

0

1

0

1

0

1

x2

0

0

1

1

0

0

1

1

x3

0

0

0

0

1

1

1

1

f

1

0

1

0

1

0

1

0

77. Для булевой функции заданной таблицей найти

а) СДНФ, СКНФ;

б) многочлен Жегалкина;

в) минимальную ДНФ.

x1

0

1

0

1

0

1

0

1

x2

0

0

1

1

0

0

1

1

x3

0

0

0

0

1

1

1

1

f

0

1

0

1

0

1

0

1

78. Для булевой функции заданной таблицей найти

а) СДНФ, СКНФ;

б) многочлен Жегалкина;

в) минимальную ДНФ.

x1

0

1

0

1

0

1

0

1

x2

0

0

1

1

0

0

1

1

x3

0

0

0

0

1

1

1

1

f

1

1

0

1

0

1

1

1

79. Для булевой функции заданной таблицей найти

а) СДНФ, СКНФ;

б) многочлен Жегалкина;

в) минимальную ДНФ.

x1

0

1

0

1

0

1

0

1

x2

0

0

1

1

0

0

1

1

x3

0

0

0

0

1

1

1

1

f

0

1

0

1

1

0

0

1

80. Для булевой функции заданной таблицей найти

а) СДНФ, СКНФ;

б) многочлен Жегалкина;

в) минимальную ДНФ.

x1

0

1

0

1

0

1

0

1

x2

0

0

1

1

0

0

1

1

x3

0

0

0

0

1

1

1

1

f

1

1

1

1

0

1

0

0

81. Для булевой функции заданной таблицей найти двойственную функцию. Определить принадлежность функции классам Поста. Построить комбинаторную схему.

x1

0

1

0

1

0

1

0

1

x2

0

0

1

1

0

0

1

1

x3

0

0

0

0

1

1

1

1

f

0

0

1

0

1

1

0

0


82. Для булевой функции заданной таблицей найти двойственную функцию. Определить принадлежность функции классам Поста. Построить комбинаторную схему.

x1

0

1

0

1

0

1

0

1

x2

0

0

1

1

0

0

1

1

x3

0

0

0

0

1

1

1

1

f

1

1

0

1

0

0

0

1

83. Для булевой функции заданной таблицей найти двойственную функцию. Определить принадлежность функции классам Поста. Построить комбинаторную схему.

x1

0

1

0

1

0

1

0

1

x2

0

0

1

1

0

0

1

1

x3

0

0

0

0

1

1

1

1

f

0

1

0

0

1

1

0

1


84. Для булевой функции заданной таблицей найти двойственную функцию. Определить принадлежность функции классам Поста. Построить комбинаторную схему.

x1

0

1

0

1

0

1

0

1

x2

0

0

1

1

0

0

1

1

x3

0

0

0

0

1

1

1

1

f

1

0

1

0

1

0

1

0


85. Для булевой функции заданной таблицей найти двойственную функцию. Определить принадлежность функции классам Поста. Построить комбинаторную схему.

x1

0

1

0

1

0

1

0

1

x2

0

0

1

1

0

0

1

1

x3

0

0

0

0

1

1

1

1

f

0

1

0

1

0

1

0

1


86. Доказать замкнутость классов Поста.
87. Найти число булевых функций зависящих от переменных и сохраняющих .

88. Найти число булевых функций зависящих от переменных и сохраняющих .

89. Найти число самодвойственных булевых функций зависящих от переменных.

90. Найти число линейных булевых функций зависящих от переменных.
91. Доказать, что булеву функцию отрицания можно выразить суперпозициями любой немонотонной булевой функции и функций 0 и 1.

92. Пусть и . Доказать, что суперпозициями функций , можно выразить либо функцию отрицания, либо функции 0 и 1. (рассмотреть функцию )

93. Пусть . Доказать, что суперпозициями функции и функции отрицания можно выразить 0 и 1. (рассмотреть функцию , где - точка, где нарушается условие самодвойственности)

94. Пусть , , . Доказать, что суперпозициями функций , , , можно выразить функцию отрицания и функции 0, 1. (вывести из решений задач 91-93)

95. Пусть . Доказать, что функцию конъюнкции можно выразить суперпозициями функции , функции отрицания и функций 0, 1. (Примечание: функция представима в виде , где функции , , , не зависят от переменных , и на каком-то наборе , поэтому для функции имеем )
96. Доказать теорему Поста о полноте. (вывести из решений задач 94, 95)

5. Кодирование
97. Для заданного алфавита построить разделимую схему, которая не является префиксной или постфиксной.
98. Для заданного алфавита построить разделимую схему с заданными длинами элементарных кодов , , , , .
99. Для заданного алфавита построить постфиксную схему с заданными длинами элементарных кодов , , , , , .
100. По заданным вероятностям , , , , построить коды Хаффмана и оценить меру избыточности.
101. По заданным вероятностям , , , , , построить коды Хаффмана и оценить меру избыточности.
102. По заданным вероятностям , , , , построить коды Хаффмана и оценить меру избыточности.
103. По заданным вероятностям , , , , , построить коды Фано-Шеннона и оценить меру избыточности.
104. По заданным вероятностям , , , , построить коды Фано-Шеннона и оценить меру избыточности.
105. По заданным вероятностям , , , , , построить коды Фано-Шеннона и оценить меру избыточности.
106. Над заданным алфавитом привести пример неразделимой схемы с попарно различными кодами.
107. Для двоичного сообщения построить код Хемминга, исправляющий одну ошибку.
108. Для двоичного сообщения построить код Хемминга, исправляющий одну ошибку.
109. Для двоичного сообщения , разбивая его на две части, построить коды Хемминга, в совокупности исправляющих две ошибки.
110. Для двоичного сообщения , разбивая его на две части, построить коды Хемминга, в совокупности исправляющих две ошибки.






Сто десять задач по дискретной математике
Учебный материал
© nashaucheba.ru
При копировании укажите ссылку.
обратиться к администрации