\input{../.headers/cours.tex}

\section{Partie théorique}

\subsection{}

\begin{align*}
	& \begin{cases}
	P &= a_0 + a_1 X + \cdots + a_n X^n \\
	Q &= b_0 + b_1 X + \cdots + b_n X^n \\
	\end{cases} \\
	P+Q &= (a_0 + b_0) + \cdots + (a_n + b_n) X^n \\
\end{align*}

Pour $k \in \llbracket 0, n \rrbracket$, on calcule $a_k + b_k$ 
On a ainsi $\Theta(n)$ additions. \fbox{C'est optimal} car il y a $n+1$ coefficients.	

\subsection{}

\begin{align*}
	& \begin{cases}
	P &= a_0 + a_1 X + \cdots + a_n X^n \\
	Q &= b_0 + b_1 X + \cdots + b_n X^n \\
	\end{cases} \\
	P \times Q &= c_0 + c_1 X + \cdots + c_{2n} X^{2n} \\
\end{align*}

où \[
	c_n = \sum_{k=0}^{n} a_k b_{n-k}
\] 

Pour $k\in \llbracket 0, 2n \rrbracket$ on calcule $c_k$ (à l'aide d'une boucle \ocaml{for} par exemple)

\paragraph{Complexité}
\begin{align*}
	\sum_{k=0}^{2n} \underbrace{\Theta(k)}_{\text{$k+1$ produits, $k$ sommes}} &= \Theta((2n)^2) \\
										   &= \Theta(n^2) \\
\end{align*}

On va améliorer: on utilise la stratégie romaine, \emph{diviser pour régner} .

\subsection{}


\begin{align*}
	P &= a_0 + a_1 X + \cdots + a_{\left\lceil \frac{n}{2} \right\rceil -1} X^{\left\lceil \frac{n}{2} \right\rceil -1} + a_{\left\lceil \frac{n}{2} \right\rceil }X^{\left\lceil \frac{n}{2} \right\rceil } + \cdots + a_n X^n \\
	Q &= b_0 + b_1 X + \cdots + b_{\left\lceil \frac{n}{2} \right\rceil -1} X^{\left\lceil \frac{n}{2} \right\rceil -1} + b_{\left\lceil \frac{n}{2} \right\rceil }X^{\left\lceil \frac{n}{2} \right\rceil } + \cdots + b_n X^n \\
	P &= AX^{\left\lceil \frac{n}{2} \right\rceil } + B \\
	Q &= CX^{\left\lceil \frac{n}{2} \right\rceil } + D \\
	PQ &= ACX^{2 \left\lceil \frac{n}{2} \right\rceil } + (AD + BC)X^{\left\lceil \frac{n}{2} \right\rceil } + BD \\
\end{align*}

\paragraph{Cas d'arrêt}

\fbox{$n=0$ }
\paragraph{Relation de récurrence}
\begin{align*}
	c_n &= \underbrace{4c_{\left\lceil \frac{n}{2} \right\rceil }}_{\text{appels récursifs}} + \underbrace{\Theta(n)}_{\text{sommes}} + \underbrace{\Theta(n)}_{\text{décalages (multiplication par  $X^{\ldots}$)}}\\
\end{align*}

\paragraph{Complexité}
\begin{align*}
	c_n &= a c_{\left\lceil \frac{n}{2} \right\rceil } + \Theta(n^\beta) \\
	\alpha = \lg a &\iff a = 2^{\alpha} \\
\end{align*}

Ici, $\alpha = \lg 4 = 2 \lg 2 = 2 > \beta = 1$ 

\[
	c_n = \Theta(n^{\alpha}) = \Theta(n^2)
\] 


\paragraph{Bi\sout{h}lan}


On retrouve la complexité quadratique de la méthode naïve :/

\subsection{}

\begin{align*}
	(AD+BC) &= (A+B)(C+D) - AC - BD \\
\end{align*}

\begin{align*}
	P \times Q &= \underbrace{AC}_{\text{1er produit}} X^{2\left\lceil \frac{n}{2} \right\rceil } + \left( \underbrace{(A+B)(C+D)}_{\text{2e produit}} - \underbrace{AC}_{\text{1er produit}} - \underbrace{BD}_{\text{3e produit}} \right) X^{\left\lceil \frac{n}{2} \right\rceil } + \underbrace{BD}_{\text{3e produit}} \\
\end{align*}

\paragraph{Relation de récurrence}


\[
	c_n = \underbrace{3 c_{\left\lceil \frac{n}{2} \right\rceil }}_{\text{appels récursifs}} + \Theta(n^1)
\] 

\paragraph{Complexité}

\begin{align*}
	c_n = \Theta(n^{\alpha}) = \Theta(n^{\lg 3}) \\
\end{align*}

\subsection{}

\begin{align*}
	p &= \overline{a_n a_{n-1} \ldots a_0}^2 = \overline{a_n \ldots a_{\left\lceil \frac{n}{2} \right\rceil } 0 \ldots 0}^2 + \overline{0 \ldots 0 a_{\left\lceil \frac{n}{2} \right\rceil -1}\ldots a_0}^2 \\
	q &= \overline{b_n b_{n-1} \ldots b_0}^2 = \overline{b_n \ldots b_{\left\lceil \frac{n}{2} \right\rceil } 0 \ldots 0}^2 + \overline{0 \ldots 0 b_{\left\lceil \frac{n}{2} \right\rceil -1}\ldots b_0}^2 \\
\end{align*}

\begin{align*}
	B &= \overline{a_{\left\lceil \frac{n}{2} \right\rceil -1}\ldots a_0}^2 \qquad A = \overline{a_n \ldots a_{\left\lceil \frac{n}{2} \right\rceil }}^2 \\
	D &= \overline{b_{\left\lceil \frac{n}{2} \right\rceil -1}\ldots b_0}^2 \qquad C = \overline{b_n \ldots b_{\left\lceil \frac{n}{2} \right\rceil }}^2 \\
\end{align*}
\newpage
\inputminted{ocaml}{./tp_4.ml}

\end{document}