Вопросы к зачету по «Дискретной математике»

Вопросы к зачету по «Дискретной математике»

для студентов 2 курса спец. ИС, ИД.

1. Множества и операции над ними. Подмножество. Булеан непустого множества. Законы алгебры множеств(доказать дистрибутивность объединения относительно пересечения).

2. Декартово произведение n множеств. Геометрическая интерпретация декартова произведения двух множеств.

3. Формула включений и исключений. Частные случаи (n = 2, n = 3).

4. Комбинаторика. Размещения из n элементов по k элементов с повторениями и без повторений. Перестановки n из элементов с повторениями и без повторений. Их число (вывод формул).

5. Комбинаторика. Сочетания из n элементов по k элементов с повторениями и без повторений. Их число (вывод формул).

6. Бином Ньютона. Свойства биномиальных коэффициентов. Треугольник Паскаля.

7. Бинарные отношения. Определения. Способы заданий. Свойства.

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

9. Отношение эквивалентности. Примеры. Прямая (доказательство) и обратная теоремы.

10. Отношение порядка. Диаграммы Хассе.

11. Отображения и их виды.

12. Равномощные множества. Счетные и несчетные множества (доказать, что множество действительных чисел несчетно). Примеры. Свойства счетных и бесконечных множеств.

13. Графы. Основные понятия. Способы задания графов. Изоморфные графы.

14. Подграф. Операции над графами.

15. Маршруты, цепи, циклы. Связность. Нахождение сильных компонент графа.

16. Метрические характеристики графов.

17. Нахождение кратчайших путей. Алгоритмы Дейкстры.

18. Деревья, лес. Задача об остове экстремального веса.

19. Гамильтоновы цепи и циклы. Задача коммивояжера.

20. Эйлеровы цепи и циклы. Необходимое и достаточное условие эйлеровости графа.

21. Планарные графы. Толщина и искаженность непланарного графа.

22. Раскраска графов. Хроматические графы. Задача о четырех красках.