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

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

для студентов 1 курса

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. Теорема о пяти красках, гипотеза четырех красок.