Файл: Вопросы к экзамену по учебной дисциплине дискретная математика.docx
ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 11.01.2024
Просмотров: 32
Скачиваний: 1
ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.
ВОПРОСЫ К ЭКЗАМЕНУ
ПО УЧЕБНОЙ ДИСЦИПЛИНЕ «ДИСКРЕТНАЯ МАТЕМАТИКА»
1. Комбинаторный признак умножения. Количество битовых строк длины k.
2. Количество всех подмножеств k - элементного множества.
3. Комбинаторный признак сложения.
4. Перестановки, размещения, сочетания без повторения.
5. Бином Ньютона. Треугольник Паскаля. Свойства биномиальных коэффициентов.
6. Перестановки, размещения, сочетания с повторениями.
7. Признак клеток (Дирихле).
8. Признак математической индукции.
9. Высказывания. Отрицание, конъюнкция, дизъюнкция, их таблицы истинности.
10. Импликация и эквиваленция, их таблицы истинности.
11. Эквивалентные высказывания. Теорема о свойствах логических эквивалентностей.
12. Тавтологии и противоречия, их свойства.
13. Умозаключения и правила вывода, доказательство от противного.
14. Полнота в логике высказываний. Штрих Шеффера и стрелка Пирса.
15. Понятие множества. Подмножества. Равенство множеств. Универсум. Пустое множество. Операции над множествами.
16. Операции над множествами.
17. Основные свойства операций над множествами.
18. Булеан множеств. Количество элементов булеана конечного множества (с доказательством).
19. Декартово произведение двух и нескольких множеств. Кортежи. Арифметическое n-мерное точечное пространство.
20. Диаграммы Эйлера - Венна основных операций над множествами.
21. Теорема об основных свойствах операций над множествами.
22. Булева алгебра.
23. Основные законы и свойства операций Булевой алгебры.
24. Отношения множеств. Область определения и множество значений отношения. Обратное отношение.
25. Специальные свойства отношений на А.
26. Граф. Ориентируемый граф.
27. Отношение эквивалентности. Классы эквивалентности. Разбиение множеств.
28. Сравнения. Вычеты. Множество классов вычетов по модулю n. Сложение и умножение классов вычетов по модулю n.
29. Функция. Область определения и область значений функции. Образ и прообраз подмножества. Композиция функций.
30. Биекция и перестановка. Обратная функция.
31. Числовые матрицы. Операции над матрицами.
32. Матричное представление отношения. Булева матрица. Булевы операции над Булевыми матрицами.
33. Мощность. Счетные множества.
34. Несчетные множества. Несчетность множества действительных чисел R (с доказательством).
35. Мажоранты для функций.
36. Оценка числа операций, необходимых для сложения и умножения двух матриц, для вычисления значения многочлена.
37. Алгоритм сортировки выбором (СВ). Пример. Оценка числа операций.
38. Граф и подграф. Основные понятия.
39. Орграф, мультиграф, размеченный граф. Основные понятия. Пути, связность.
40. Деревья, ориентированные деревья.
41. Корневые деревья. Остовное дерево графа.
42. Две задачи о Кенигсбергских мостах. Пути и циклы Эйлера.
43. Матрица инцидентности и матрица смежности. Теоремы о к-путях.
44. Алгоритм Уоршолла.
45. Гиперкубы. Построение кода Грея для к+1.
46. Построение (m×n) – сетки с помощью кода Грея.
47. Гомоморфизм, изоморфизм и гомеоморфизм графа.
48. Объединение, пересечение, дополнение графов.
49. Разрезающее множество, разрезающее ребро и разрезающая вершина графа.
50. Теоремы о компонентах двусвязности графа.
51. Планарные графы. Грани. Формула Эйлера.
52. Теоремы о планарных и непланарных графах.
53. Непланарность графа Петерсона.
54. Гамильтонов путь и Гамильтонов цикл. Теоремы о Гамильтоновых циклах.
55. Замыкание графа. Примеры.
56. Взвешенные графы. Алгоритм Дейкстры.
57. Первый алгоритм Флойда-Уоршолла.
58. Условия для графа быть деревом.
59. Условия для графа быть корневым ориентированным деревом.
60. Теоремы о m-арных ориентированных деревьях.