Контрольные по математике | Вопросы к экзамену по дискретной математике | Matematiku5
Вузы по математике Готовые работы по математике Как писать работы по математике Примеры решения задач по математике Решить задачу по математике online

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


1.  Основные понятия теории множеств (множество, подмножество, принадлежность, булеан, мощность множества, пустое множество). Операции с множествами и их свойства, иллюстрация с помощью диаграмм Эйлера-Венна.

2.  Декартово произведение множеств. Мощность декартово произведения. Примеры.

3.  Отношения на множествах. Способы задания отношений. Свойства бинарных отношений. Примеры.

4.  Графы. Основные понятия. Способы задания графов. Матрицы смежности и инцидентности.

5.  Путь и расстояние в графе. Таблица расстояний. Радиус и центр графа.

6.  Транспортная задача. Области возникновения, основные понятия. Теорема Форда-Фалкерсона.

7.  Алгоритм Форда-Фалкерсона построения максимального потока. Пример.

8.  Задача поиска кратчайшего пути. Алгоритм поиска. Сложность задач на графах, NP-полнота, примеры.

9.  Изоморфизм графов. Понятия плоского и планарного графов. Теорема Эйлера о плоском графе. Следствие из этой теоремы. Kn полные графы.

10. Эйлеровы графы. Задача о кёнигсбергских мостах.

11. Алгебра логики. Логические переменные, формулы и функции. Основные логические переменные. Таблица истинности. Законы алгебры логики (10 пп). Основные логические эквивалентности.

12. Нормальные формы. СДНФ и СКНФ, их построение.

13. Релейно-контактные схемы. Основные задачи теории релейно-контактных схем. Пример — машина для голосования.

14. Полином Жегалкина. Два способа построения. Степень полинома Жегалкина.

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

16. Комбинаторика, ее основные задачи (4пп). Основные понятия и правила комбинаторики.

17. Сочетания, размещения, перестановки, перестановки в мультимножествах.

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

19. Формула включения и исключения. Пример.

20. Задача о беспорядках.

21. Метод рекуррентных соотношений. Линейные рекуррентные соотношения с постоянными коэффициентами.

22. Алгоритмы. Основные свойства алгоритма (6пп). Схема определения алгоритма. Классы алгоритмов. Оценка сложности. Классификация алгоритмов.

23. Элементарные и примитивно-рекурсивные функции.

24. Математическая логика. Формальные теории.

25. Исчисление высказываний. Понятие высказываний, тавтологий, формулы. Построение вывода формул логики высказываний. Метод резолюций, общий алгоритм метода.

26. Исчисление предикатов. Понятие предиката, местности предиката, множества истинности. Кванторы. Изменение порядка кванторов.

27. Предваренная и приведенная предикатные формы. Примеры.

Наташа

Автор

Наташа — контент-маркетолог и блогер, но все это не мешает ей оставаться адекватным человеком. Верит во все цвета радуги и не верит в теорию всемирного заговора. Увлекается «нефрохиромантией» и тайно мечтает воссоздать дома Александрийскую библиотеку.

Распродажа дипломных

 Скидка 30% по промокоду Diplom2020

А ты боишься COVID-19?

 Пройди опрос и получи промокод