Примерный Экзаменационный билет

Вопросы для подготовки к промежуточной аттестации

 

1. Понятие множества, элемента множества. Пустое множество, счетное множество

2. Мощность множества. Истинное подмножество. Включение, строгое включение подмножества

3. Универсальное множество. Диаграммы Венна.

4. Тождества алгебры множеств

5. Основные операции над множествами

6. Объединение множеств

7. Отношение, операции над отношениями. Свойства отношений.

8. Специальные виды бинарных отношений.

9. Теоретико-множественная форма бинарных отношений

10. Общие свойства бинарных отношений

11. Высказывание. Логические операции: отрицание, конъюнкция, дизъюнкция, импликация, эквивале́нция.

12. Законы алгебры логики.

13. Формулы алгебры логики. Функции алгебры логики.

14. Таблица истинности для всевозможных функций двух переменных

15. Дизъюнктивная нормальная форма. Конъюнктивная нормальная форма

16. Совершенная дизъюнктивная нормальная форма

17. Совершенная конъюнктивная нормальная форма

18. Дистрибутивные законы Инволюционный закон

19. Операции “штрих Шеффера” и “стрелка Пирса”

20. Общие свойства алгебры логики и алгебры множеств

21. Получение совершенной дизъюнктивной нормальной формы и совершенной конъюнктивной нормальной формы с помощью таблицы истинности

22. Получение совершенной дизъюнктивной нормальной формы и совершенной конъюнктивной нормальной формы с помощью равносильных преобразований

23. Логика высказываний и логика предикатов. Одноместный и n-местный предикаты

24. Кванторы всеобщности, существования, квантификация предиката.

25. Превращение предиката в высказывание c помощью кванторов

26. Способы формализации ситуаций

27. Способы построения логических выводов

28. Модуль логического вывода в интеллектуальных системах

29. Понятие адекватности логических выводов¶

30. Представление графов. Псевдографы, мультиграфы, планарные графы

31. Пути и маршруты графа. Степень вершин графа.

32. Изоморфизм графов. Нагруженные графы

33. Маршрут, цепь, замкнутый маршрут, замкнутая цепь, цикл, простой цикл.

34. Длина маршрута, расстояние между вершинами, диаметр графа

35. Матрица смежности для ориентированного и неориентированного графа.

36. Алгоритм выделения компонентов связности

37. Поиск кратчайшего маршрута между вершинами ориентированного графа с помощью матрицы длин дуг

38. Поиск кратчайшего маршрута между вершинами неориентированного графа с помощью матрицы длин дуг

39. Эйлеровы графы. Гамильтоновы графы.

40. Способы построения остовного дерева

41. Алгоритм для поиска минимального пути (маршрута) в нагруженном орграфе (графе) через последовательные матрицы смежности (бинарная степень матриц)

42. Алгоритм Форда – Беллмана для нахождения минимального пути в нагруженном орграфе между вершинами.

43. Алгоритм нахождения кратчайшего контура, соединяющего все узлы ориентированной сети (алгоритм ветвей и границ Литтла

44. Алгоритм Дейкстры для нахождения минимального пути (маршрута) в нагруженном орграфе (графе)

45. Эйлеров граф в решении задачи коммивояжера. Алгоритм решения задачи коммивояжера

46. Применение Гамильтоновых графов и циклов

47. Применение остовного дерева в задачах оптимизации

48. Практическая реализация алгоритма Форда – Беллмана для нахождения минимального пути между вершинами в нагруженном ориентированном орграфе, не включающем ребра с отрицательным весом

49. Практическая реализация алгоритма Форда – Беллмана для нахождения минимального пути между вершинами в нагруженном ориентированном орграфе, включающем ребра с отрицательным весом

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

51. Основные понятия комбинаторики: перестановки, правило сложения, правило умножения, размещения, сочетания

52. Биномиальная формула в общем виде и в виде разложения

53. Треугольник Паскаля

54. Свойства биномиальных коэффициентов.

55. Полиномиальная формула в общем виде и в виде разложения.

56.  Сетевые модели: основные понятия, требования, предъявляемые к сетевым моделям.

57. Нахождение критического пути в сетевой модели. Определение резерва в сететвой модели.

58. Алгоритм для нахождения матрицы достижимости.

Примерный Экзаменационный билет

                      по дисциплине  Дискретная математика                       

 

Направление подготовки________________        Группа___________________

Ф.И.О. студента______________________        № билета_________________

1. (1) Разностью между множествами С и В называется множество, состоящее из тех и только тех элементов, которые

     1) Принадлежат множеству С и не принадлежат множеству В.

     2) Принадлежат хотя бы одному из множеств С и В.

     3) Принадлежат и множеству С и множеству В.

     4) Принадлежат множеству В и не принадлежат множеству С.

2.(3) Согласны ли Вы с высказываниями

 

ü Даны два множества Х= {0; 1; 3; 5; 7} и У= {0; 1; 3; 5}. Верно ли, что множество У есть подмножество Х. ___________________

ü Бинарное отношение R на множестве Х называется транзитивным, еслидля любых элементов х и у из множества Х из того, что х находится в отношении R с элементом у и элемент у находится в отношении R с элементом х следует, что элементы х и у совпадают. ________________

ü На сетевом графике работа должна отображаться одной стрелкой __________________

3. (2) Допишите:

Ø Число размещений из n элементов по k без повторов вычисляется по формуле ____________________.

Ø Отношение R в Х называют отношением ____________________________, если оно рефлексивно, симметрично и транзитивно.

4. (1) Дана таблица истинности. Какой логической операции она соответствует?

X	Y	?
0	0	1
0	1	0
1	0	0
1	1	1

А)Дизъюнкция.

Б) Отрицание.

В) Конъюнкция.

Г) Эквивалентность.

Д) импликация

 

5 . (3)Выбрать верные утверждения:

а) Граф, имеющий всего две нечетные вершины, можно начертить, не отрывая карандаша от бумаги.

б)  - двухместный предикат от переменных х и у, истинный при всех значениях х и у.

в)  Алгоритм Фалкерсона позволяет упорядочивать вершины графа.

6. (2) а) Формулой логического высказывания

«Если на улице не будет солнечно и будет дождь, то я буду писать сочинение, а не пойду на прогулку» является:

a) ;                          b)

c)                          d)

7. (3) Вычислите:

Ответ:_________________

8. (3) Найдите декартово произведение множеств В×А, если А= {2; 4} , В= {0;2}

Ответ:_________________________

9. (6) В отделе НИИ работают несколько сотрудников, знающих хотя бы один иностранный язык. Из них 10 человек знают английский, 8 – немецкий, 7 – французский, 5 – английский и немецкий, 4 – французский и немецкий, 2 – французский и английский, 1 человек все три языка. Сколько человек знают только один язык?

Ответ:_________________________

10. (7) Сколькими способами можно составить трехцветный полосатый флаг (три горизонтальных полосы), если имеется материя 5 различных цветов?

Ответ:_________________________

 

11. (7) Представить граф в виде точек и отрезков, если известна его матрица смежности по вершинам

                             Ответ: ____________________

12 (8) СКНФ формулы  является…

Ответ:_________________

13.(14) Определите, кто из четырех студентов сдал экзамен, ecли известно:

1. Если первый сдал, то и второй сдал.

2. Если второй сдал, то третий сдал или первый не сдал.

3. Если четвертый не сдал, то первый сдал, а третий не сдал.

4. Если четвертый сдал, то и первый сдал.