Перечень вопросов
Введение
Элементы теории множеств
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. Задача Штейнера в построении кратчайшего дерева.
40. Гиперграф и способы его представления. Понятия цепи, цикла, дерева и раскраски гиперграфа.
41. Кенигово представление гиперграфа.
Элементы теории алгоритмов
42. Понятие алгоритма, виды алгоритмов.
43. Общая, прикладная и структурная теория алгоритмов.
44. Понятия алфавита, алфавитного оператора.
45. Способы задания алфавитных операторов.
46. Кодирующие отображения, коды, кодирование и его обратимость.
47. Основные свойства алгоритмов, машина Тьюринга.
48. Полиноминальные, экспоненциальные, детерминированные и недетермини-
рованные алгоритмы.
49. Методы оценки алгоритмов: сложность и временная сложность алгоритма.
50. Задачи на допустимость и оптимальность. N, NP и NPC – задачи.
51. Операторные алгоритмы Ван Хао.
52. Операторные алгоритмы Ляпунова, логические схемы алгоритмов.
53. Алгоритм Маркова.
54. Блок-схемный метод алгоритмизации.
55. Алгоритмические языки и требования, предъявляемые к ним.
Математическое программирование
56. Линейное программирование. Математическая формулировка задачи линейного программирования.
57. Транспортная задача. Задача о назначениях.
58. Методы решения задач линейного программирования. Симплекс метод. Венгерский метод.
59. Нелинейное программирование. Математическая формулировка задачи нелинейного программирования.
60. Методы решения задач нелинейного программирования. Методы дихотомического деления, штрафных функций, чисел Фибоначчи, полиномиальной аппроксимации.
61. Методы безусловной оптимизации: Розенброка, деформирующего многогранника.
62. Дискретное программирование. Математическая формулировка задачи дискретного программирования.
63. Методы решения задач дискретного программирования: комбинаторные, отсечения, приближённые, специальные. Задача о кратчайшем пути (о коммивояжёре). Задачи о покрытии и укладке.
64. Стохастическое программирование. Методы случайного поиска и случайного поиска с локальной оптимизацией.
65. Динамическое программирование. Принцип Беллмана. Примеры алгоритмов и задач, использующих принцип Беллмана.