Вычисления в нелинейной алгебре

2019/2020

Статус: Дисциплина общефакультетского пула

Кто читает: Департамент больших данных и информационного поиска

Где читается: Факультет компьютерных наук

Когда читается: 1, 2 модуль

Преподаватели: Погудин Глеб Александрович

Язык: русский

Кредиты: 2

Контактные часы: 38

Полная версия программы учебной дисциплины

Аннотация

Огромное количество вычислений так или иначе сводятся в линейной алгебре. Дело в том, что линейная алгебра прекрасно изучена, придуманы и качественно реализованы алгоритмы для большей части её задач. Однако, многие процессы по своей природе нелинейны, а значит для их анализа нам нужны нелинейные методы. Основные вопросы для данного факультатива: - какие важные вопросы могут быть сведены к задачами из нелинейной алгебры, - какие алгоритмы и методы имеются в нашем распоряжении для решения этих задач. В рамках курса будут рассмотрены задачи нелинейной алгебры, возникающие в теории вероятностей, дискретной математике, моделировании, экономике, и т.д. Темы из нелинейной алгебры, которые планируется в той или иной степень затронуть: базисы Грёбнера, исключение кванторов, цилиндрическое разложение, тропическая геометрия.

Цель освоения дисциплины

Формирование у студентов навыков сведения практических задач к задачам на языке нелинейной алгебры
Ознакомление студентов с основными алгоритмами нелинейной алгебры
Формирование у студентов навыков настройки и адаптации алгоритмов с учетом специфики и структуры конкретной задачи
Ознакомление с общими принципами работы обсуждаемых алгоритмов и соответствующими разделами математики
Ознакомление студентов с языком Julia

Планируемые результаты обучения

Сводить задачи к решению системы нелинейных уравнений
Решать системы уравнений методом гомотопического продолжения
Применять базисов Грёбнера для исключения переменных
Использовать исключение переменных для обнаружения зависимостей
Решать SDP-задачи на языке Julia
Сводить комбинаторые задачи к задачам SDP
Вычислять SOS-сертификаты
Транслировать задачи в формулы первого порядка
Применять алгоритмы исключения кванторов

Содержание учебной дисциплины

Решение систем нелинейных уравнений методом гомотопического продолжения
Метод гомотопического продолжения. Типы стартовых систем: система полной степени, мультиоднородная система. Метод монодромии. Примеры: разделение нормальных распределений методом моментов, реконструкция изображений по проекциям.
Методы исключения переменных из нелинейных систем
Понятие об исключении. Геометрический смысл исключения. Основные алгоритмы: базисы Грёбнера и треугольные множества. Зависимость эффективности алгоритма от выбора упорядоченья. Примеры: определение формул для параметров, метод моментов.
Неотрицательное программирование
Базовые сведения о неотрицательном программировании (SDP). Пример применения для приближенного решения NP-полных задач. Сертификаты суммы квадратов (SOS-certificates) и их вычисление
Исключение кванторов
Теорема Тарского об исключении кванторов и её применения. Алгоритмы для исключения кванторов и их использование. Применения для автоматических доказательств, верификации гибридных систем.

Элементы контроля

Домашнее задание 1
Домашнее задание 2
Экзамен

Промежуточная аттестация

Промежуточная аттестация (2 модуль)
0.35 * Домашнее задание 1 + 0.35 * Домашнее задание 2 + 0.3 * Экзамен

Программа дисциплины