| Alex_Arahort | Дата: Понедельник, 14.05.2012, 01:06 | Сообщение # 1 |
 Admin
Группа: Администраторы
Сообщений: 91
Статус: Offline
| Вопросы по дисциплине
«Дискретная математика»
Теоретические.
1.Понятие высказывания. Основные логические операции.
2.Понятие формулы логики. Таблица истинности и методика ее построения. Тождественно-истинные формулы.
3.Понятие элементарной дизъюнкции, понятие конъюнктивной нормальной формы (КНФ). Методика построения таблицы истинности для КНФ.
4.Равносильные формулы. Законы логики.
5.Упрощение формул логики с помощью равносильных преобразований.
6.Понятие элементарной конъюнкции, понятие дизъюнктивной нормальной формы (ДНФ). Методика построения таблицы истинности для ДНФ.
7.Понятие булева вектора (двоичного вектора). Соседние векторы. Единичный N-мерный куб.
8.Понятие булевой функции (функции алгебры логики). Способы задания булевой функции. Представление булевой функции в виде формулы логики.
9.Понятие совершенной ДНФ. Правило получения СДНФ из формулы алгебры логики.
10. Понятие совершенной КНФ. Правило получения СКНФ из формулы алгебры логики. 11.Понятие минимальной ДНФ. Соответствие между гранями единичного N-мерного куба и элементарными произведениями. Представление булевой функции (N<3) в виде минимальной ДНФ графическим методом.
12.Операция двоичного сложения и ее свойства. Многочлен Жегалкина. Представление булевой функции в виде многочлена Жегалкина.
13.Понятие выражения одних булевых функций через другие. Проблема возможности выражения одних булевых функций через другие.
14.Полнота множества функций. Замыкание множества функций. Важнейшие замкнутые классы.
15.Теорема Поста. Шефферские функции (функция Шеффера и функция Пирса).
16.Построение логических схем по булевым функциям.
17.Построение релейно-контактных схем по булевым функциям.
18.Понятие множества. Подмножества. Теоретико-множественные диаграммы.
19.Операции над множествами и их свойства.
20.Формула количества элементов в объединении двух и трех конечных множеств.
21.Декартово произведение множеств, декартово степень множеств.
22.Соответствие между теоретико-множественными и логическими операциями.
23.Понятие предиката. Область определения и область истинности предиката.
24.Обычные логические и кванторные операции над предикатами.
25.Понятие предикатной формулы. Свободные и связанные переменные.
26.Построение отрицаний к предикатам, содержащим кванторные операции. Формализация предложений с помощью логики предикатов.
27.Понятие бинарного отношения. Способы задания.
28.Свойства бинарного отношения.
29.Отношение эквивалентности. Теорема о разбиении множества на классы эквивалентности.
30.Понятие отображения. Свойства функций.
31.Обратные функции и композиция функций.
32.Понятие подстановки. Формула количества подстановок. Циклическое разложение подстановки.
33.Чётные и нечётные подстановки. Свойства чётных и нечётных подстановок.
34.Произведение подстановок, обратная подстановка и степень подстановки.
35.Операция деления с остатком. Понятие вычета по модулю N.
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.Базовые множества для автомата. Таблица автомата и принципы его работы.
Практические.
1. Упростите формулу .
2. Доказать равносильность .
3. Привести к совершенной ДНФ следующую формулу
4. Привести к совершенной КНФ следующую формулу
5. Привести к совершенной КНФ следующую формулу
6. Привести к совершенной ДНФ следующую формулу
7. Минимизировать следующую функцию F( )= .
8. Минимизировать следующую логическую функцию графическим методом F( )= .
9. Получить из логической функции F( )= СПНФ.
10. Является ли функция F( )= базисом.
11. Является ли функция F( )= базисом.
12. Заданы два множества A={1,2,4,6}и B={2,3,4,8,9}. Найти .
13. Заданы два множества A={1,2,4,6} B={2,3,4,8,9}. Найти n( )?
14. Найти отрицание формулы .
15. На множестве М={1,2,3,…,20} заданы предикаты В(х): «х-четное число»; D(х):«х -кратно 3». Найти область истинности следующего предиката B(x) D(x).
16. Задано множество, и отношение R на A задано упорядоченными парами R={(1,1),(1,2),(1,3),(3,1),(2,3)}. Оно не рефлексивно, не симметрично и не транзитивно. Найдите соответствующие замыкания.
17. Покажите, что функция h :z→z ,(где z-целые числа) заданная формулой h(x)= и не инъективна, и не сюръективна.
18 . Покажите, что функция K:R→R (где R-действительные числа), заданная формулой К(х)= 4х +3, является биекцией .
19. Определите, какие из функций, изображенных на рисунке, инъективны, и какие сюръективны. Перечислите все биекции.
а 1 а 1 а а 1
2 1 2
б 2 б б
с с 3 2 б 3
3 с
20. Найдите композицию функций g•f , f•g, если f(x)= 2x + 1, g(x)= sin x.
21. Даны две подстановки δ1 =( ); δ2= ( ) . Перевести подстановки к канонической записи и найти их произведения.
22. Сравнимы ли два числа 36 и16 по модулю?
23. Произведите операции под вычетами
А=312; В=98; р=15, где р-модуль.
24. Укажите мосты и разделяющие вершины в графе
1 10
2 7 9
• 3 • 6 • 11
•8
• 4
5•
25. Найти расстояние между вершинами в графе
2 • •3
1 •
4 • • 5
26. Является ли граф двудольным
3 4
1
2 5
1 6
27. Изоморфи ли два графа. Пояснить.
A C• •B
E А•
B C D D• • E
28. Изобразить планарный граф для заданного
2 3
1 4
5
29.Есть ли в заданном графе Эйлеровы и Гамильтоновы циклы
30. Записать код Пруфера
6
5 7
4 3 8
1 2 9 10
31. Записать матрицу смежности для графа
2
1 3
5 4
32. Определить количество путей в орграфе
1 2
4 3
Я рождён на границе меж светом и тьмой, был распят за безумные игры с судьбой...
|
| |
| |
