Основы теории погрешности. Прямая и обратная задачи теории погрешностей. Оценка погрешности.

Понятие погрешности и ее виды. Абсолютная и относительная погрешность, оценка погрешности. Прямая и обратная задачи теории погрешности. Пример вычисления погрешностей суммы, разности, произведения, частного.

Численные методы решения нелинейных уравнений с одним неизвестным.

Методы решения нелинейных уравнений. Отделение корней нелинейного уравнения. Уточнение корней. Метод дихотомии (деления отрезка пополам). Конечные и итерационные методы. Метод простой итерации. Сходимость метода. Метод Ньютона. Сравнение методов.

Решение систем линейных уравнений: конечные и итерационные методы.

Численные методы решения СЛАУ. Метод Гаусса. Приведение матрицы системы к треугольному виду с помощью исключений. Прямой и обратный ход метода. Выбор главного элемента. Метод полного исключения Жордана. Сравнение методов. Итерационные методы решения СЛАУ. Метод простой итерации. Норма матрицы. Метод Зейделя. Невязка.

Численная интерполяция: методы Лагранжа и Ньютона.

Понятие аппроксимации и интерполяции. Интерполяционные полиномы. Полином Лагранжа. Оценка погрешности интерполяции. Полином Ньютона. Разделенные разности. Сравнение полиномов Лагранжа и Ньютона.

Численное интегрирование и дифференцирование. Формулы численного дифференцирования. Метод Ньютона-Котеса.

Метод аппроксимация как основа построения формул численного дифференцирования и интегрирования. Формулы разностных производных. Использование интерполяционных полиномов Лагранжа для построения формул численного интегрирования. Формула Ньютона-Котеса. Коэффициенты Котеса и их свойства. Однократный и многократный метод вычисления. Формулы прямоугольников, трапеций и Симпсона.

Основные виды задач оптимизации и методы их решения. Линейное программирование. Основные этапы решения задачи симплекс-методом.

Классификация задач оптимизации (линейное программирование, нелинейное программирование, условная и безусловная оптимизация, динамическое программирование). Постановка задачи линейного программирования, приведение к стандартному виду, получение начального допустимого решения. Алгоритм Симплекс-метода. Реализации симплекс-метода.

Основные понятия теории игр. Чистые и смешанные стратегии игры. Седловая точка игры и ее поиск.

Классификация задач теории игр (игры с чистой и смешанной стратегией). Постановка задачи теории игр, матрица игры, исследование матрицы – проверка на наличие седловой точки. Решение задачи в смешанных стратегиях.

43 Транспортная задача: постановка задачи, поиск опорного плана, оптимизация решения.

Понятие и постановка транспортной задачи. Табличное представление задачи. Опорный план задачи. Методы получения опорного плана (северо-западного угла и предварительной оптимизации). Условие баланса. Решение транспортной задачи методом потенциалов Канторовича.

Понятие графа, методы описания графа, виды графов. Эйлеровы и гамильтоновы графы.

Понятие графа, 3 метода описания графов. Матрицы смежности и инцидентности. Основные характеристики и виды графов (степень вершин, связность, наличие циклов). Остовное дерево графа. Эйлеровы и гамильтоновы графы и их свойства. Уникурсальная линия.

Комбинаторные объекты дискретной математики. Алгоритмические задачи комбинаторики. Задача коммивояжера.

Перестановки, размещения, сочетания. Понятие разбиения, числа Стирлинга. Бином Ньютона, биномиальные коэффициенты, треугольник Паскаля. Решение задачи коммивояжера жадным и деревянным алгоритмом. Метод ветвей и границ.

Алгоритмические задачи поиска в графах: задачи Прима-Краскала, Дейкстры, Форда-Фалкерсона.

Классификация алгоритмических задач на графах (задачи поиска, сетевого планирования, распределения потоков). Постановка задачи Прима-Краскала, методы ее решения и возможные приложения. Постановка задачи Дейкстры, методы ее решения и возможные приложения. Алгоритм Уоршелла. Пропускная способность, поток и сечение в сети. Постановка задачи на максимальный поток (Форда-Фалкерсона), методы ее решения и возможные приложения.

Рекурсивные функции.

Понятие рекурсивной функции. Базовые рекурсивные функции. Оператор суперпозиции. Оператор примитивной рекурсии. Оператор минимизации. Тезис Черча. Тезис Клини. Доказательство рекурсивности функций.