ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 26.10.2023
Просмотров: 19
Скачиваний: 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. Построение сетевого графика по заданной упорядоченности работ.