ДИСКРЕТНАЯ МАТЕМАТИКА (вопросы к экзамену)

теоретические

практические
Множества и операции над ними. Законы алгебры множеств. Декартово произведение множеств. Отношения и способы их задания. Свойства отношений. Проверка свойств с помощью различных способов задания множеств. Операции над отношениями. Отношения эквивалентности. Отношения порядка. Наибольший (наименьший), максимальные (минимальные) элементы. Функции и способы их задания. Композиция функций. Виды функций – сюръекция, инъекция, биекция. Размещения, перестановки, сочетания. Бином Ньютона. Размещения и сочетания с повторениями. Линейные однородные рекуррентные соотношения второго порядка с постоянными коэффициентами. Линейные неоднородные рекуррентные соотношения второго порядка с постоянными коэффициентами. Высказывания. Логические операции над ними. Законы алгебры высказываний. Нахождение высказывания по таблице истинности. Дизъюнктивная и совершенная дизъюнктивная нормальные формы (алгоритм построения). Карты Карно (для 2, 3, 4 переменных). Этапы работы с картой Карно. Логические структурные схемы и их связь с логическими выражениями. Графы, виды графов, способы их задания. Маршруты, пути, циклы в графе. Эйлеровы и Гамильтоновы графы. Остов графа. Алгоритмы построения остова поиском в ширину и глубину. Минимальный остов графа. Прима алгоритм и алгоритм Краскала. Кратчайший путь между вершинами взвешанного графа, алгоритм Декстра. Сети планирования. Задача о минимальной сети планирования. Построить диаграмму Эйлера-Венна для заданного множества. Задать отношение графом или бинарной матрицей. Проверить выполнение свойств для данного отношения. Проверить, является ли данное отношение отношением эквивалентности. Определить класс эквивалентности для данного элемента. Проверить, является ли данное отношение отношением частичного порядка. Найти наибольший (наименьший), максимальные (минимальные) элементы. Построить диаграмму Хассе по данному отношению или восстановить отношение по его диаграмме Хассе. Доказать утверждение методом математической индукции. Решить текстовую задачу с применением комбинаторных формул. Найти общее или частное решение рекуррентного соотношения. Построить таблицу истинности для логического выражения. Минимизировать логическое выражение с использованием карты Карно. Построить и упростить логическую структурную схему. Построить остовы графа поиском в ширину или глубину. Построить минимальный остов графа. Найти кратчайший путь между вершинами графа. Найти минимальную сеть планирования.