Алгебраическая сложность, Разборов А.А., 2019.
Брошюра написана по материалам курса, прочитанного автором в 2010 г. в Летней школе «Современная математика». В ней рассказывается об основных понятиях теории алгебраической сложности и приводятся её начальные утверждения. Рассматриваются задачи эффективного вычисления полиномов и билинейных форм, матричного умножения и алгебраической теории NP-полноты.
Книга представляет интерес для широкого круга сравнительно подготовленных читателей, интересующихся математикой.
Первое издание книги вышло в 2016 г.
Вычисление полиномов от одной переменной.
Начнем мы с некоторых примеров. Пусть мы хотим вычислить значение полинома х2010, проще говоря, возвести число х в 2010-ю степень. Можно действовать так: заведем переменную, которую сначала положим равной х, а затем 2009 раз умножим ее на х.
Чему равно время работы такого алгоритма? Имеется следующая простая универсальная формула:
время работы алгоритма = число элементарных операций х время выполнения одной операции.
Интуитивно понятно, что разные арифметические операции (сложение, умножение и деление) имеют, вообще говоря, разную трудоемкость, поэтому в эту формулу часто вводят неотрицательные веса, приписываемые операциям разного типа. Для простоты мы ограничимся случаем, когда часть весов равны 0 (т. е. операция допускается бесплатно), а остальные равны 1. Помимо этого мы абстрагируемся от такой величины, как время выполнения одной элементарной операции. Эта величина зависит от скорости процессора и от других параметров, не связанных с математикой. Кроме того, в алгебраической сложности нас не будет интересовать конкретное значение числа х. Ясно, что на практике намного проще в 2010-ю степень возвести двойку, чем число из тысячи знаков. Но для нас «х умножить на у» — это одна операция, вне зависимости от того, чему равны хиу. Операции сложения и вычитания мы будем считать бесплатными. Более того, операции с фиксированными числами мы тоже будем считать бесплатными, например, вычисление 1000х или даже √2х (конечно, с некоторой погрешностью).
ОГЛАВЛЕНИЕ.
1. Вычисление полиномов от одной переменной.
2. Полиномы от многих переменных.
3. Перемножение полиномов и вычисление билинейных форм.
4. Умножение матриц.
5. Перманент и VNP-полнота.
Приложение. Необходимые сведения.
Список литературы.
Купить .
Дата публикации:
Теги: учебник по алгебре :: алгебра :: Разборов
Смотрите также учебники, книги и учебные материалы:
Следующие учебники и книги:
Предыдущие статьи:
