From 0be2be0a92f992bf8ee9eff701cb19658a1e7544 Mon Sep 17 00:00:00 2001
From: Andrew Guschin <guschin.drew@gmail.com>
Date: Thu, 29 Dec 2022 15:20:32 +0400
Subject: =?UTF-8?q?=D0=94=D0=BE=D0=B1=D0=B0=D0=B2=D0=BB=D0=B5=D0=BD=D1=8B?=
 =?UTF-8?q?=20=D0=BB=D0=B0=D0=B1=D1=8B=208-15?=
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: 8bit

---
 report/lab15/lab15.tex | 104 +++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 104 insertions(+)
 create mode 100644 report/lab15/lab15.tex

(limited to 'report/lab15/lab15.tex')

diff --git a/report/lab15/lab15.tex b/report/lab15/lab15.tex
new file mode 100644
index 0000000..077ba29
--- /dev/null
+++ b/report/lab15/lab15.tex
@@ -0,0 +1,104 @@
+\documentclass[a4paper,oneside]{article}
+
+\usepackage[utf8]{inputenc}
+\usepackage[T2A]{fontenc}
+\usepackage[english,russian]{babel}
+
+\usepackage{amsmath}
+\usepackage{mathtools}
+\usepackage{amsfonts}
+\usepackage{enumitem}
+\usepackage{amsthm}
+\usepackage{minted}
+\setminted{fontsize=\small, breaklines=true, style=emacs, linenos}
+\usepackage{graphicx}
+\graphicspath{ {./images/} }
+\usepackage{float}
+
+\newtheorem{theorem}{Теорема}[subsection]
+\newtheorem*{theorem*}{Теорема}
+
+% --- Определение --- %
+\theoremstyle{definition}
+\newtheorem{definition}{Определение}[subsection]
+\newtheorem*{definition*}{Определение}
+% ------------------- %
+
+\title{{Алгоритмы алгебры и теории чисел}\\{Лабораторная работа №15}}
+\author{Гущин Андрей, 431 группа, 1 подгруппа}
+\date{\the\year{} г.}
+
+\begin{document}
+
+\maketitle
+
+\section{Задача}
+
+Вычисление значений и корней полиномов
+
+
+\section{Алгоритм}
+
+
+\subsection{Значение многочлена}
+
+При вычислении значений многочленов очень широкое применение получило правило
+Горнера. Метод назван в честь британского математика Уильяма Джорджа Горнера.
+
+В соответствии с этим правилом многочлен $n$-й степени:
+\begin{equation*}
+    P_n(x)=a_0 x^n + a_1 x^{n-1} + \dots + a_{n-1} x + a_n
+\end{equation*}
+представляется в виде
+\begin{equation*}
+    P_n(x) =(\dots((a_0 x + a_1) x + a_2) x + \dots + a_{n-1}) x + a_n
+\end{equation*}
+
+Вычисление значения многочлена производится в порядке, определяемом скобками.
+
+\subsection{Корни многочлена}
+
+Схема Горнера - способ деления многочлена
+$$P_n(x) = \sum_{i=0}^{n} a_i x^{n - i} = a_0 x^n + a_1 x^{n - 1} + \cdots +
+a_n$$ на бином $x - a$. Работать придётся с таблицей, первая строка которой
+содержит коэффициенты заданного многочлена.  Первым элементом второй строки
+будет число $a$, взятое из бинома $x - a$.
+
+Вторая строка таблицы заполняется постепенно. Второй элемент этой строки
+(обозначим его $b_0$) равен $a_0$, т.е., по сути, мы просто переносим вниз число
+$a_0$.
+
+Следующий элемент второй строки, который мы обозначим как $b_1$, получается по
+такой формуле: $b_1 = a \cdot b_0 + a_1$.  Далее находим элемент $b_2$ по
+формуле $b_2 = a \cdot b_1 + a_2$ и т.д.
+
+В конечном итоге, мы вычислим последний элемент $b_n = a \cdot b_{n - 1} + a_n$.
+
+После деления исходного многочлена $n$-й степени $P_n(x)$ на бином $x - a$,
+получим многочлен, степень которого на единицу меньше исходного, т.е. равна $n -
+1$.
+
+Последнее число второй строки, т.е. $b_n$, есть остаток от деления $P_n ( x )$
+на $x - a$:
+\begin{equation*}
+    \sum_{i=0}^{n} a_i x^{n - i} = a_0 x^n + a_1 x^{n - 1} + \dots + a_n = (x - a) \cdot (b_0 x^{n - 1} + b_1 x^{n - 2} + \dots + b_{n - 1}) + b_n
+\end{equation*}
+
+Таким образом, по теореме Безу это означает, что число $b_n$ равно значению
+многочлена $P_n ( x )$ при $x = a$, т.е. $b_n = P_n ( a )$.
+
+Если $b_n = 0$, то исходный многочлен делится на бином $x - a$ нацело, т.е.
+число $a$ является корнем этого многочлена.
+
+
+\section{Реализация}
+\inputminted{python}{../../lab15/lab15.py}
+
+
+\section{Тестирование}
+\begin{figure}[H]
+    \centering
+    \includegraphics[width=0.8\textwidth]{test15.png}
+\end{figure}
+
+\end{document}
-- 
cgit v1.2.3

