Delimost_mnogochlenov
4.3 Ускоренные версии алгоритма.
Одним из методов ускорения целочисленного алгоритма Евклида является использование симметричного остатка:
где
Одна из наиболее многообещающих версий ускоренного алгоритма Евклида для полиномов основывается на том, что промежуточные значения алгоритма в основном зависят от высоких степеней. Применение стратегии Разделяй и Властвуй позволяет уменьшить асимптотическую сложность алгоритма.
8
Содержание
- Аннотация
- Оглавление
- Введение
- Основная часть
- 1. Общее понятие.
- 1.1 Одночлен.
- 1.2 Многочлен.
- 1.3 Стандартный вид многочлена.
- 2. Действия с многочленами.
- 2.1 Сложение (вычитание) многочленов.
- 2.2 Умножение многочленов.
- 2.3 Деление многочленов
- 3. Делимость многочленов
- 4. Алгоритм Евклида.
- 4.1 Исторические сведения.
- 4.2 Обобщённый алгоритм Евклида для многочленов.
- 4.3 Ускоренные версии алгоритма.
- 5. Применение теории делимости.
- 5.1 Разложение на множители.
- 5.2 Сокращение дробей.
- 5.3 Решение уравнений.
- 5.4 Теорема Безу