- •Элементы вариационного исчисления. Задачи, приводящие к вариационному исчислению.
- •Элементы вариационного исчисления. Основные понятия (функционал, вариация функционала)
- •Простейшая вариационная задача с закрепленными границами. Понятие об экстремуме функционала.
- •Вариационная задача с подвижными границами. Задача с подвижными концами.
- •Вариационная задача с подвижными границами. Задача с подвижными границами.
- •Вариационные задачи на условный экстремум.
- •Постановка задачи оптимального управления.
- •Линейная стационарная задача оптимального быстродействия.
- •О возможности решения задач оптимального управления с помощью вариационного исчисления.
- •Принцип максимума Понтрягина в линейной стационарной задаче оптимального управления.
- •Множества. Операции над множествами.
- •Высказывания. Предикаты. Виды предикатов.
- •Операции над высказываниями (отрицание, конъюнкция, дизъюнкция, импликация, эквиваленция, штрих Шеффера, сумма по модулю два).
- •Конъюнктивная и дизъюнктивная нормальные формы. Их свойства. Приведение формул логики к кнф, днф.
- •Булевы функции. Булева алгебра.
- •Многочлен Жегалкина.
- •Предполные классы.
- •Теорема Поста (критерий полноты системы булевых функций).
- •Основные понятия теории графов.
- •Обход графа (алгоритмы «оптимиста» и «пессимиста»).
- •Нахождение кратчайшего пути (алгоритмы Флойда и Дийкстра).
- •Деревья. Построение сети дорог минимальной стоимости.
- •Построение максимального потока грузов по транспортной сети.
- •Автоматы.
- •Элементы комбинаторики.
- •События. Виды событий. Операции над ними.
- •Классическое определение вероятности события
- •Теоремы сложения и умножения вероятностей.
- •Формула полной вероятности. Формула Байеса.
- •Формула Бернулли
- •Локальная и интегральная теоремы Муавра- Лапласа.
- •Дискретные случайные величины. Закон распределения дсв. Законы биномиальный и Пуассона.
- •Числовые характеристики дсв.
- •Непрерывные случайные величины. Плотность распределения непрерывной случайной величины.
- •Числовые характеристики непрерывные случайных величин.
- •Функция случайного аргумента.
- •Закон распределения двумерной случайной величины.
- •Выборочный метод. Статистическое распределение выборки.
- •Выборочный метод. Эмпирическая функция распределения.
- •Выборочный метод. Полигон и гистограмма
- •Статистические оценки параметров распределения. Точечные оценки.
- •Статистические оценки параметров распределения. Интервальные оценки.
- •Методы расчета сводных характеристик выборки. Метод произведений вычисления выборочной средней и дисперсии.
- •Методы расчета сводных характеристик выборки. Метод сумм вычисления выборочной средней и дисперсии.
- •Элементы теории корреляции.
- •Статистическая проверка статистических гипотез.
- •Проверка гипотезы о нормальном распределении генеральной совокупности по критерию Пирсона в случае эмпирического распределения, заданного в виде последовательности равноотстоящих вариант.
Обход графа (алгоритмы «оптимиста» и «пессимиста»).
Алгоритм «оптимиста» состоит из 2-х правил. Правило А. Двигаться по непройденным рёбрам, нумеруя пройденные. Правило Б. Если таких рёбер нет, то двигаться в обратном направлении по последнему пройденному 1 раз ребру.
Алгоритм «пессимиста». Шаг 1. Пройти из вершины а0 к вершинам, отстоящим от него на 1 ребро. Шаг к+1. Из вершины а0 двигаться по незакрытым отмеченным рёбрам до вершин смежных с неотмеченными, и каждое такое ребро отметить меткой к+1 и закрыть его, если оно ведёт в вершину уже отмеченную или являющуюся кольцевой.
Замечание: алгоритм «пессимиста» в отличие от «оптимиста» позволяет сделать обход «бесконечного» графа.
Нахождение кратчайшего пути (алгоритмы Флойда и Дийкстра).
Алгоритм Флойда предназначен для поиска кратчайших путей между всеми парами вершин взвешенного графа. Пусть граф задан матрицей по следующему правилу: A равно
1. 0, если i равно j;
2. бесконечности, если из i в j нет ребра;
3. весу ребра между вершинами i и j в остальных случаях.
Алгоритм Дейкстры предназначен для нахождения кратчайших путей от одной вершины взвешенного графа до всех остальных вершин. Пусть граф представлен в виде матрицы (определенной как в алгоритме Флойда) и необходимо найти кратчайшие пути из вершины с номером N. Алгоритм использует тот факт, что любая часть кратчайшего пути сама является кратчайшим путем между соотвествующими вершинами.
Деревья. Построение сети дорог минимальной стоимости.
Дерево- связанный неориентированный граф без цикла. Теорема: в дереве между любыми 2-мя вершинами А и В существует единственная цепь(маршрут, в кот. Каждая вершина встречается 1 раз). Вершина, локальная степень кот. равна 1 называется концевой. Ребро, смежное с концевой вершиной называется концевым. Остовым деревом графа G называется дерево, являющееся подграфом графа G и содерж. все его вершины.
Построение сети дорог миним. стоимости. Имеется n городов, известна стоимость строит-ва дорог м/у парами городов. Надо построить сеть дорог миним. стоимости, так чтобы от любого города можно было добраться до любого другого.
Замечание: видно, что минимальная сеть дорог должна быть деревом, т.к. при наличии цикла из него можно выбросить ребро, сохранив связанность и уменьшив стоимость сети.
«Жадный алгоритм».
Выбрать минимальное ребро.
Среди оставшихся рёбер, добавление которых к построенной части не приводит к образованию цикла, выбрать ребро минимальной длины а присоединить его к строящемуся дереву.
Правило 2 применять пока возможно.
Построение максимального потока грузов по транспортной сети.
Шаг 1. Полагаем i = 0. Пусть j0 - любой допустимый поток в транспортной сети D. (например, полный; можно начинать с нулевого потока: j0 (x), x О X).
Шаг 2. По сети D и потоку ji строим граф I(D, ji).
Шаг 3. Находим простую цепь hi, являющуюся минимальным путем из v1 в нагруженном графе I(D, ji). Если длина этой цепи равна Ґ, то поток ji максимален, и работа алгоритма закончена. В противном случае увеличиваем поток вдоль цепи hi на максимально допустимую величину ai > 0, где ai О Z (прибавляя ее для каждой дуги x О X, через которую проходит цепь hi, к уже имеющейся величине потока по дуге x, если направления x и hi совпадают, и, вычитая, если направления x и hi противоположны).