ВУЗ: Томский государственный университет систем управления и радиоэлектроники
Категория: Учебное пособие
Дисциплина: Дискретная математика
Добавлен: 28.11.2018
Просмотров: 6249
Скачиваний: 13
96
массовой, так как угол, который требуется разделить на три
равные части, может быть любым. И для этой задачи существует
строгое доказательство ее алгоритмической неразрешимости.
3. Задача удвоения куба формулируется следующим обра-
зом. Дан куб A, длина ребра которого равна a. Требуется найти
длину ребра куба B, объем которого в два раза больше объёма
заданного куба A. При нахождении длины ребра куба B разре-
шается пользоваться только циркулем и линейкой, как и в зада-
че о квадратуре круга. Задача удвоения куба является массовой,
так как длина ребра заданного куба A может быть любой. Эта
задача также является алгоритмически неразрешимой.
Заметим, что эти задачи алгоритмически неразрешимы только
при заданных ограничениях относительно используемых опера-
ций. Если же снять ограничения, т.е. расширить набор разрешен-
ных операций, то некоторые неразрешимые задачи могут оказаться
разрешимыми. Например, Архимед дал решение задачи трисекции
угла, добавив в набор допустимых операций следующие две:
1) разрешается наносить на линейку пары точек, являю-
щихся копиями соответствующих точек на чертеже, и перено-
сить эти точки снова на бумагу;
2) линейку можно применять не только для проведения от-
резков. Разрешается так перемещать линейку, что одна из зара-
нее поставленных на ней точек скользит по окружности, а дру-
гая — по какой-либо прямой.
Если же требуется построить несуществующий объект, то
не помогут никакие расширения допустимых операций.
Завершим подраздел следующим замечанием. Теория алго-
ритмов призвана освещать не столько прикладные вопросы,
сколько общетеоретические. Для лиц, занимающихся решением
прикладных задач, вполне достаточно интуитивного представ-
ления об алгоритмах, и математическая теория алгоритмов
представляет для них интерес лишь с позиций кругозора. Но при
более глубоком её изучении, особенно вопросов, связанных со
сложностью алгоритмических задач, теория алгоритмов может
явиться хорошим подспорьем в становлении профессионального
программиста.
97
äéçíêéãúçõÖ Çéèêéëõ
Дискретная математика отличается большим разнообразием
тем и направлений развития и соответственно характеризуется
обширным понятийным аппаратом. Данный курс состоит только
из пяти тем, но так как в каждой теме насчитывается большое
число понятий, то и список контрольных материалов содержит
довольно много вопросов — 186. По содержанию все эти вопро-
сы отражают большинство понятий теоретической части, преду-
смотренной учебной программой по дискретной математике.
В нижеприведенном списке после формулировок вопросов
в круглых скобках указаны числа. Это номера страниц из учеб-
ного пособия «Основы дискретной математики» [3], где можно
найти все необходимые сведения для правильного ответа на ка-
ждый из 186 вопросов.
íÂÓðËfl ÏÌÓÊÂÒÚ‚
1. Как обозначаются множества? (12)
2. Записать с применением знака принадлежности элемента
множеству: «Элемент t принадлежит множеству P». (12)
3. Что такое синглетон? (12)
4. Как читается запись: a, t, m
∈ P? (12)
5. Как обозначается пустое множество? (12)
6. Как читается запись:
P = {x | 0
≤ x < 10 ∧ x — целое число}? (13)
7. Какие множества называются равными? Пример. (13)
8. Что такое мощность множества? Пример. (13)
9. Что такое кардинальное число множества? Поясните
примерами. (14)
10. Как формулируется интуитивный принцип объемности
в теории множеств? (13)
11. Какие множества называются эквивалентными? Пояс-
ните примерами. (14)
12. Чем по смыслу отличаются записи:
m
∈ P и m ⊂ P? (16)
13. Что такое булеан множества? Приведите пример. (14)
98
14. Что такое объединение множеств, пересечение мно-
жеств? Поясните примерами. (17, 18)
15. Какое множество называют универсальным? (18)
16. Что такое дополнение множества? Пример. (18)
17. Что такое разность множеств, симметрическая разность
множеств? (20)
18. Что такое диаграмма Венна? Приведите пример диа-
граммы. (21–22)
19. Что такое декартово произведение множеств? Поясните
примером. (26)
20.Что такое бинарное отношение? Пример. (27)
21. Что такое степень множества? Пример. (28)
22. Что такое кортеж в теории бинарных отношений? При-
ведите пример. (28)
23. Что такое квадрат множества? Пример. (28)
24. Что такое антисимметричность? Пример. (29)
25. Какое отношение называется транзитивным? Приведите
пример. (29)
26. Что такое рефлексивность в теории бинарных отноше-
ний? Поясните примером. (30)
27. Какое отношение называют отношением эквивалентно-
сти? Поясните примером. (30)
28. Чем отличается отношение строгого порядка от отно-
шения нестрогого порядка? Пример. (31)
29. Назовите четыре вида соответствий. (32, 33)
30. Какие отношения называются функциональными? При-
ведите пример. (33)
31. Что такое биекция, сюръекция? Примеры. (32, 34)
å‡ÚÂχÚ˘ÂÒ͇fl ÎÓ„Ë͇
1. Что такое формальная логика? (36)
2. В чем суть понятия «классическая логика»? (37)
3. Чем отличается классическая логика от неклассической?
(37)
4. Что такое понятие (40), суждение (41), умозаключение
(51)? Поясните примерами.
5. Что называется логическими действиями? (38)
99
6. Назовите основные приемы познавательной деятельно-
сти. (39, 40)
7. Что такое закон обратного отношения в традиционной
логике? (41)
8. Что такое категория в традиционной логике? (41)
9. Что такое дефиниция в традиционной логике? (40)
10. Назовите виды категорических суждений. (43, 44)
11. Что такое контрарность? (48)
12. Что такое контрадикторность? (49)
13. Что такое умозаключение? Пример. (51)
14. Назовите два основных вида умозаключений. (52)
15. Что такое категорический силлогизм? Пример. (53)
16. Что такое аксиома категорического силлогизма? Пояс-
ните на примере. (54)
17. Что такое меньший, больший и средний термины в кате-
горическом силлогизме? Пример. (54)
18. Что такое модус категорического силлогизма? Поясните
примером. (55)
19. Что такое фигура силлогизма? Пример. (56)
20. Перечислите логические законы и охарактеризуйте каж-
дый из них. (57, 58)
21. Что такое логическая константа? (61)
22. Перечислите аксиомы, определяющие дизъюнкцию,
конъюнкцию и инверсию. (62, 63)
23. Что такое терм? Пример. (64)
24. Что называется набором значений переменных? Пояс-
ните примером. (65)
25. Что такое тавтология? Пример. (65)
26. Какие формулы в алгебре логики называют общезначи-
мыми? Пример. (65)
27. В чем суть свойства двойственности в алгебре логики?
Поясните примером. (68)
28. Перечислите девять теорем одной переменной. (68)
29. Что такое ДНФ? Пример. (69)
30. Что такое КНФ? Пример. (69)
31. Как записываются теоремы поглощения и склеивания
для ДНФ и КНФ? (70)
32. Как формулируются теоремы де Моргана? (70)
100
33. Какая функция называется остаточной? (72)
34. Какую таблицу в булевой алгебре называют таблицей
истинности (соответствия)? Пример. (72)
35. Что такое минтерм? Пример. (74)
36. Что такое СДНФ? Пример. (74)
37. Какие булевы функции называют ортогональными? По-
яснить примером. (76)
38. По какому признаку определяется сложность булевой
формулы? Пояснить примером. (77)
39. В чем суть минимизации булевой формулы? Пояснить
примером. (77)
40. Какие аргументы булевой функции называют фиктив-
ными? (78)
41. Что такое импликанта булевой функции? Пояснить
примером. (78)
42. Что такое простая импликанта булевой функции? Пояс-
нить примером. (80)
43. Какая форма булевой функции называется сокращен-
ной? Пример. (80)
44. Что такое макстерм? Пример. (86)
45. Что такое СКНФ? Пример. (86)
46. Что такое конституента единицы? Пример. (75)
47. Что такое конституента нуля? Пример. (86)
48. Какие функции называют неполностью определенными?
Пример. (87)
49. Что значит доопределить функцию? Пример. (88)
50. Что такое симметрическая функция? Пример. (89)
51. Что такое а-число симметрической функции? (89)
52. В каких случаях симметрические функции поддаются
минимизации в классе ДНФ? Пример. (90)
53. Какие логические операции применяются в алгебре Же-
галкина? (90)
54. Приведите аксиомы операции «сумма по модулю 2» ал-
гебры Жегалкина. (91)
55. В чем главное отличие сильной дизъюнкции от слабой?
(63, 90)
56. Чем отличается операция «включающее ИЛИ» от опе-
рации « исключающее ИЛИ»? (63, 90)