Вопросы к экзамену по дискретной математике

Вопросы к экзамену по дискретной математике

1.Понятие множества и кортежа. Элементы кортежа.

2.Способы задания множеств. Парадокс Рассела.

3.Понятие подмножества и надмножества. Разбиения и покрытия множества.

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

5.Соответствие алгебры множеств логическим выражениям.

6.Принцип "исключённого третьего" и закон противоречия.

7.Средневзвешенное по элементам множества.

8.Понятие выпуклого и невыпуклого множества. Ограниченные множества, открытые и замкнутые множества.

9.Теорема о пересечении выпуклых множеств и её доказательство.

10.Отношения эквивалентности, строгого и нестрогого порядка. Класс эквивалентности.

11.Понятие доминирования. Необходимое и достаточное условия доминирования.

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

13.Кортежи и прямое произведение множеств.

14.Теорема о принципе включений и исключений и её применение.

15.Следствие из теоремы о принципе включений и исключений.

16.Взаимосвязь отношений, соответствий и отображений.

17.Инъективная, сюръективная и биективная функции.

18.Понятие о неразрешимых вычислительных проблемах. Однонаправленные функции.

19.Целочисленное умножение и задача факторизации.

20.Основные понятия теории графов. Диаграммы графов.

21.Типы графов, ориентированные и неориентированные графы.

22.Элементы графов. Понятие валентности в теории графов.

23.Маршруты и циклы в графах.

24.Понятие связности графа. Тривиальные, полные и двудольные графы.

25.Понятие эйлерова графа. Задача о кенигсбергских мостах.

26.Теорема Эйлера о сумме степеней вершин графа и её доказательство.

27.Эйлеровы и гамильтоновы циклы. Понятие гамильтонова графа.

28.Операции над графами.

29.Понятие планарного графа. Применение планарных графов.

30.Внутренняя и внешняя устойчивость множества вершин графа.

31.Хроматическое и цикломатическое числа графа.

32.Сопоставительный анализ различных способов представления графа в ЭВМ.

33.Дерево как частный случай графа.

34.Обходы деревьев и задача коммивояжера.

35.Алгоритм. Дейкстры поиска кратчайшего пути в графе.

36.Решение задачи коммивояжера методом ветвей и границ.

37.Метод динамического программирования.

38.Транспортные сети. Максимальный поток и минимальный разрез в сети.

39.Теорема Форда-Фалкерсона и её доказательство. Алгоритм Форда-Фалкерсона.

40.Код Грея и его применение.