Экзаменационные вопросы по дискретной математике

Экзаменационные вопросы по дискретной математике

1.  Основные понятия теории множеств. Способы задания множеств. Определения и свойства пустого множества, универсума, булеана. Парадоксы теории множеств.

2.  Определения операций над множествами. Правила построения диаграмм Эйлера-Венна. Разбиения и покрытия множеств.

3.  Свойства операций над множествами. Способы доказательств равенства множеств. Метод 2-х включений.

4.  Индуктивное определение формулы в теории множеств. Суперпозиция формул. Алгоритм приведения формул к стандартному базису.

5.  Определение равномощных множеств. Мощность как отношение эквивалентности и отношение порядка на множестве всех множеств. Теоремы о счетных множествах. Доказательства счётности рациональных и алгебраических чисел, множества слов. Существование несчетных множеств: теорема Кантора, гипотеза континуума.

6.  Определение упорядоченных и неупорядоченных наборов элементов. Декартово произведение множеств. Свойства декартова произведения. Примеры декартовых произведений.

7.  Определение n-местного отношения между множествами. Способы задания отношений. Унарное и бинарное отношения. Полное и пустое отношения, алгебра отношений.

8.  Определения и свойства композиции бинарных отношений и обратного отношения. Образы и прообразы элементов и отношений.

9.  Свойства бинарных отношений: сюръективность, инъективность, биективность. Функциональность. Свойства композиций функций.

10. Свойства бинарных отношений: рефлексивность, иррефлексивность; симметричность, антисимметричность; транзитивность. Примеры.

11. Отношение эквивалентности. Свойства классов эквивалентности. Фактор-множество. Способы задания отношения эквивалентности. Примеры.

12. Отношение порядка. Двойственный порядок, индуцированный порядок. Способы задания отношений порядка. Примеры.

13. Упорядоченные множества. Диаграммы Хассе. Мажоранта, миноранта, инфинум, супремум, Свойства min(a, b) и max(a, b). Решетки.

14. Определение операции. Связь операций и отношений. Свойства бинарных операций. Существование и свойства нейтральных и нулевых элементов. «Нули» и «единицы» в теории множеств.

15. Абстрактные алгебры и алгебраические системы. Определение гомоморфизма алгебр. Классификация алгебр с одной операцией. Аксиомы группы. Циклические группы. Примеры.

16. Аксиомы группы. Определение и свойства подгруппы. Симметрические группы. Группы вращений. Примеры.

17. Алгебры с двумя операциями. Аксиомы кольца. Примеры колец, решеток и полей. Поля Галуа.

18. Векторные пространства над произвольным полем. Примеры. Размерность векторного пространства. Теоремы о базисе.

19. Свойства n-мерного булева куба. Понятие булевой функции. Число булевых функций. Равенство булевых функций. Таблицы истинности.

20. Элементарные булевы функции. Законы алгебры Буля.

21. Представление конечных множеств в ЭВМ. Логические операции. Связь алгебры Буля с алгеброй подмножеств.

22. Нормальные формы булевых функций. Алгоритм приведения произвольной формулы к нормальной дизъюнктивной форме. Формулы разложения произвольной функции в СДНФ и СКНФ.

23. Индуктивное определение формулы. Теорема двойственности. Связь формул и функций. Равносильность формул как отношение эквивалентности.

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

25. Классы функций Поста и критерий полноты системы функций. Примеры полных систем элементарных булевых функций.

26. Полиномы Жегалкина. Метод неопределённых коэффициентов.

27. Минимизация булевых функций. Алгоритмы Квайна – Мак-Клоски, Карно. Геометрический смысл минимизации.

28. Определение графа как алгебраической системы. Характеристики графов. Изоморфизм. Разновидности графов. Свойства деревьев.

29. Укладка графа. Планарность. Формула Эйлера для многогранников. Виды непланарных графов.

30. Способы аналитического задания графов и их сложность.

31. Обходы графа – маршруты, цепи, циклы. Метрические характеристики графов.

32. Эйлеровы графы. Теорема Эйлера. Алгоритм построения эйлерова цикла (цепи) в графе.

33. Алгоритмы поиска в глубину и ширину. Остовные деревья и фундаментальные циклы.

34. Связность. Пространства разрезов и фундаментальных циклов.

35. Нахождение кратчайшего расстояния между вершинами во взвешенном графе.

36. «Жадный» алгоритм. Нахождение минимального остова графа.

37. Сети. Теорема Форда–Фалкерсона. Алгоритм нахождения максимального потока.

38. Паросочетания. Теорема Холла о трансверсалях.

39. Задачи кодирования. Равномерное и алфавитное кодирования. Условие разделимости кодов. Минимизация кодов методом Фано и Хаффмана.

40. Принцип помехоустойчивого кодирования. Проверка по чётности. Расстояние Хэмминга. Теоремы о возможности обнаружения и исправления ошибок. Пример матричного кода, исправляющего однократную ошибку.