Список вопросов:
1.Множества и действия над ними. Свойства множеств. Законы алгебры множеств.
2.Отношения и функции. Композиция бинарных отношений. Инъективные, сюрьективные и биективные функции.
3.Отношения эквивалентности. Рефлексивность, симметричность, антисимметричность, транзитивность. Вид матриц, выражающих эти свойства.
4.Отношения порядка. Частичный порядок элементов множеств. Диаграммы Хассе.
5.Эквивалентные, конечные и бесконечные множества. Теорема Кантора — Бернштейна.
6.Аксиомы теории множеств. Аксиома выбора и аксиома детерминированности.
7.Отбор подмножеств. Число перестановок с повторениями и без повторений. Число сочетаний с повторениями и без повторений.
8.Бином Ньютона и свойства биномиальных коэффициентов.
9.Полиномиальная теорема.
10.Метод рекуррентных соотношений. Вывод формулы.
11.Производящая функция. Операции в классе производящих функций. Производящие функции последовательностей.
12.Производящая функция последовательности чисел Фибоначчи.
13.Метод включений и исключений. Подсчет числа элементов объединения n множеств.
14.Формула включений и исключений для множества элементов с k совместимыми свойствами.
15.Учет весов в формуле включений и исключений.
16.3адача о числе беспорядков. Функция Эйлера.
17.Графы, виды графов, способы их задания. Операции над графами. Маршруты, цепи, циклы.
18.Способы задания графов. Матрицы связности, достижимости и контрдостижимости графа.
19.Метрические характеристики графа.
20.Упорядочивание дуг и вершин орграфа.
21.Выявление маршрутов с заданным количеством ребер. Метод Шимбелла.
22.Алгоритм Дейкстры.
23.Алгоритм Беллмана — Мура.
24.Алгоритм нахождения максимального пути.
25.Деревья. Построение экстремального остова.
26.Эйлеровы графы. Признак эйлеровости графа. Алгоритм Флери.
27.Гамильтоновы графы. Теорема Оре.
28.Фундаментальные циклы, матрица фундаментальных циклов.
29.Независимые множества графа. Доминирование. Оценки числа вершинной независимости и числа доминирования.
30.Клики графа. Алгоритм выделения клик в графе. Матрица клик.
31.Планарность графов. Свойство гомеоморфизма. Теорема Понтрягина-Куратовского. Число планарности.
32.Алгоритм укладки графа на плоскость.
33.Хроматические графы. Гипотеза четырех красок. Оценки хроматического числа. Алгоритм последовательной раскраски графа.
34.Потоки в сетях. Теорема Форда — Фалкерсона.
35.Модификации сети для расчета потока минимальной стоимости.
З6.Элементы сетевого планирования. Критические пути и сроки. Ранние и поздние сроки свершения событий и работ. Резервы времени.
37.Линейные графики. Планирование ресурсов в сети.
Скачать Шпору: