Специальность Прикладная математика
дисциплина Дискретная математика
Ответы на билеты + шпаргалка. формат docx 

Список вопросов (есть 26 из 39):

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. Построение МДНФ. Карты Карно.