\documentclass[12pt,a4paper]{article}
\usepackage[latin1]{inputenc}
\usepackage[francais]{babel}
\usepackage[T1]{fontenc}
\usepackage{kpfonts}
\usepackage[table]{xcolor}
\usepackage{tkz-euclide}
\usetikzlibrary{fadings,calc}
\usepackage[margin=2cm]{geometry}
\usepackage{titlesec}
\usepackage{fancyhdr}
\usepackage{eso-pic}
\usepackage{enumitem}
\usepackage{multicol}
\usepackage{mathtools}
\usepackage{tabularx}
\usepackage{cellspace}
	\setlength{\cellspacebottomlimit}{4pt}
	\setlength{\cellspacetoplimit}{4pt}
\frenchbsetup{StandardLists=true}
\graphicspath{{img/}}
\usepackage[urlcolor=purple,colorlinks=true]{hyperref}
\definecolor{violet}{cmyk}{0.28,0.89,0,0.28}
\definecolor{vert}{cmyk}{0.17,0,0.17,0.07}
%FONTES POUR ALGO
\DeclareFontFamily{T1}{lmtt}{} 
\DeclareFontShape{T1}{lmtt}{m}{n}{<-> ec-lmtl10}{} 
\DeclareFontShape{T1}{lmtt}{m}{\itdefault}{<-> ec-lmtlo10}{} 
\DeclareFontShape{T1}{lmtt}{\bfdefault}{n}{<-> ec-lmtk10}{} 
\DeclareFontShape{T1}{lmtt}{\bfdefault}{\itdefault}{<-> ec-lmtko10}{}
\renewcommand{\ttdefault}{lmtt}
% PACKAGES NECESSAIRES POUR ALGO
\usepackage{framed}
\usepackage{algorithm}
\usepackage{algpseudocode}
%ALGO
\definecolor{fond}{RGB}{136,136,136}
\definecolor{sicolor}{RGB}{128,0,128}
\definecolor{tantquecolor}{RGB}{221,111,6}
\definecolor{pourcolor}{RGB}{187,136,0}
\definecolor{bloccolor}{RGB}{128,0,0}
\newenvironment{cadrecode}{%
\def\FrameCommand{{\color{fond}\vrule width 5pt}\fcolorbox{fond}{white}}%
\MakeFramed {\hsize \linewidth \advance\hsize-\width \FrameRestore}\begin{footnotesize}}%
{\end{footnotesize}\endMakeFramed}
\makeatletter
\def\therule{\makebox[\algorithmicindent][l]{\hspace*{.5em}\color{fond} \vrule width 1pt height .75\baselineskip depth .25\baselineskip}}%
\newtoks\therules
\therules={}
\def\appendto#1#2{\expandafter#1\expandafter{\the#1#2}}
\def\gobblefirst#1{#1\expandafter\expandafter\expandafter{\expandafter\@gobble\the#1}}%
\def\Ligne{\State\unskip\the\therules}% 
\def\pushindent{\appendto\therules\therule}%
\def\popindent{\gobblefirst\therules}%
\def\printindent{\unskip\the\therules}%
\def\printandpush{\printindent\pushindent}%
\def\popandprint{\popindent\printindent}%
\def\Variables{\Ligne \textcolor{bloccolor}{\textbf{VARIABLES}}}
\def\Si#1{\Ligne \textcolor{sicolor}{\textbf{SI}} #1 \textcolor{sicolor}{\textbf{ALORS}}}%
\def\Sinon{\Ligne \textcolor{sicolor}{\textbf{SINON}}}%
\def\Pour#1#2#3{\Ligne \textcolor{pourcolor}{\textbf{POUR}} #1 \textcolor{pourcolor}{\textbf{ALLANT\_DE}} #2 \textcolor{pourcolor}{\textbf{A}} #3}%
\def\Tantque#1{\Ligne \textcolor{tantquecolor}{\textbf{TANT\_QUE}} #1 \textcolor{tantquecolor}{\textbf{FAIRE}}}%
\algdef{SE}[WHILE]{DebutTantQue}{FinTantQue}
  {\pushindent \printindent  \textcolor{tantquecolor}{\textbf{DEBUT\_TANT\_QUE}}}
  {\printindent \popindent  \textcolor{tantquecolor}{\textbf{FIN\_TANT\_QUE}}}%
\algdef{SE}[FOR]{DebutPour}{FinPour}
  {\pushindent \printindent \textcolor{pourcolor}{\textbf{DEBUT\_POUR}}}
  {\printindent \popindent  \textcolor{pourcolor}{\textbf{FIN\_POUR}}}%
\algdef{SE}[IF]{DebutSi}{FinSi}%
  {\pushindent \printindent \textcolor{sicolor}{\textbf{DEBUT\_SI}}}
  {\printindent \popindent \textcolor{sicolor}{\textbf{FIN\_SI}}}%
\algdef{SE}[IF]{DebutSinon}{FinSinon}
  {\pushindent \printindent \textcolor{sicolor}{\textbf{DEBUT\_SINON}}}
  {\printindent \popindent \textcolor{sicolor}{\textbf{FIN\_SINON}}}%
\algdef{SE}[PROCEDURE]{DebutAlgo}{FinAlgo}
   {\printandpush \textcolor{bloccolor}{\textbf{DEBUT\_ALGORITHME}}}%
   {\popandprint \textcolor{bloccolor}{\textbf{FIN\_ALGORITHME}}}%
\makeatother
\newenvironment{algobox}%
{%
\begin{ttfamily}
\begin{algorithmic}[1]
\begin{cadrecode}
\labelwidth 1.5em
\leftmargin\labelwidth \addtolength{\leftmargin}{\labelsep}
}
{%
\end{cadrecode}
\end{algorithmic}
\end{ttfamily}
}

\newcommand{\chapHead}[1]{% #1 = Titre
\begin{tikzpicture}
\fill[blue!20] (0,0) rectangle+(\textwidth,-1.5cm);
\fill[orange!5] (0,-1) rectangle +(\textwidth,-5cm);
\fill[violet] (12cm,0) rectangle +(4cm,-4.5cm);
\fill[violet!80] (12cm,-4.5cm) rectangle+(0.5cm,0.5cm);
\fill[violet!70] (12.5cm,-4.5cm) rectangle+(0.5cm,0.5cm);
\fill[violet!60] (13cm,-4.5cm) rectangle+(0.5cm,0.5cm);
\fill[violet!60] (12cm,-4cm) rectangle+(0.5cm,0.5cm);
\fill[violet!50] (12.5cm,-4cm) rectangle+(0.5cm,0.5cm);
\fill[violet!40] (12cm,-3.5cm) rectangle+(0.5cm,0.5cm);
\fill[violet!40] (13.5cm,-4.5cm) rectangle+(0.5cm,0.5cm);
\fill[vert] (12cm,-4.5cm) rectangle +(4cm,-1.5cm);
% "Article"
\node[below] at (14cm,-0.5cm) {%
\begin{minipage}{4cm}
\begin{center}
\color{white}\fontfamily{lmss}\fontseries{bx}\selectfont{\Large Article}

\bigskip

\emph{par\\{\small Stéphane PASQUET}}
\end{center}
\end{minipage}
};
% Titre
\node[below right] (titre) at (0.25cm,-1.5cm) {%
\begin{minipage}{11cm}
\fontfamily{lmss}\fontseries{bx}\selectfont \color{purple}\Huge #1
\end{minipage}
};
\node[below right,text=purple] at ($(titre.south west)+(0,-1em)$) {\fontfamily{lmss}\fontshape{it}\selectfont Disponible sur \url{http://www.mathweb.fr}};
% Date
\node at (14cm,-5.5cm) {%
\begin{minipage}{4cm}
\begin{center}
\fontfamily{lmss}\fontseries{bx}\selectfont\color{black}\today
\end{center}
\end{minipage}
};
\end{tikzpicture}
}
% Sections
\titleformat{\section}[block]
{\fontfamily{lmss}\fontseries{bx}\fontsize{16}{14}\selectfont\color{violet}}
{\thesection}
{1em}
{\fontfamily{lmss}\fontseries{bx}\selectfont}
\setlength{\parindent}{0pt}

% Subsections
\titleformat{\subsection}[block]
{\fontfamily{lmss}\fontseries{bx}\fontsize{12}{10}\selectfont\color{purple}}
{\thesubsection}
{1em}
{\fontfamily{lmss}\fontseries{bx}\selectfont}
\setlength{\parindent}{0pt}

% Paragraph

\titleformat{\paragraph}[runin]
{\fontfamily{lmss}\fontseries{b}\selectfont\color{purple}}{\theparagraph}{1em}{}

% Itemize, enumerate

\setlist[itemize,1]{label={\color{purple}\textbullet}}
\setlist[enumerate,1]{label={\color{purple}\arabic*.}}

% footpage

\cfoot{\fontfamily{lmss}\fontseries{bx}\selectfont\color{white}\fcolorbox{violet}{violet}{\thepage}}

\lhead{}
\rhead{}
\renewcommand{\headrulewidth}{0pt}


\begin{document}
\pagestyle{fancy}
\chapHead{Multiplier deux polynômes}

\section{Introduction}

Multiplier de deux polynômes peut être quelques fois tâche ardue, surtout si leur degré est supérieur à 2. Nous allons voir ici une méthode pour aller plus vite que d'appliquer la distributivité.

\section{Qu'est-ce qu'un polynôme ?}

Un polynôme $P$ est une somme de plusieurs termes de la forme $a_kx^k$.

On écrit alors : 
\[
P(x)=a_nx^n + a_{n-1}x^{x-1} + a_{n-2}x^{n-2} + \cdots + a_2x^2 + a_1x + a_0\;,
\]
que l'on peut aussi noter:
\[
P(x)=\sum_{k=0}^n a_kx^k \;.
\]
Si tous les $a_k$ sont des nombres réels, on dit que le polynôme $P$ appartient à l'ensemble $\mathbb{R}[x]$. Si les $a_k$ sont des nombres complexes, on dit que $P\in\mathbb{C}[x]$.

\medskip

On dit ici que le degré de $P$ est égal à $n$ et on note : $d^\circ(P)=n$.

Par exemple, le polynôme $3x^5 + 4x^4-5x^3 + 9x^2-8x+2$ est de degré 5.

\section{Produit de deux polynômes}


Posons $A(x)=3x^2-5x+2$ et $B(x)=4x^2+7x-6$, alors on définit le produit $AB$ en utilisant la distributivité :
\begin{align*}
AB(x) & = \big(3x^2-5x+2\big)\big(4x^2+7x-6\big)\\
			& = 3x^2\times4x^2 + 3x^2\times7x + 3x^2\times(-6)-5x\times4x^2-5x\times7x-5x\times(-6)+2\times4x^2+2\times7x+2\times(-6)\\& = 12x^4 + 21x^3 -18x^2 -20x^3 - 35x^2 + 30x + 8x^2 + 14x - 12
\intertext{On regroupe ensuite les termes de même degré :}
						& = 12x^4 + (21-20)x^3 + (-18-35+8)x^2 + (30+14)x - 12\\
\Aboxed{AB(x)	& = 12x^4 + x^3 - 45x^2 + 44x - 12}
\end{align*}

À l'aide du programme Xcas (gratuit), on peut vérifier le résultat avec les instructions suivantes :

\medskip

\begin{tabularx}{\linewidth}{|Sl@{~:~}>{\ttfamily\arraybackslash}S{X}|}
\hline
Ligne à taper par l'utilisateur & A(x):=3*x\verb+^+2-5*x+2;B(x):=4*x\verb+^+2+7*x-6\\
\hline
Ligne retournée par Xcas & \verb+//+Interprète A\\
& \verb+//+Succès lors de la compilation A\\
& \verb+//+Interprète B\\
& \verb+//+Succès lors de la compilation B\\
& \hfil (  x -> 3x\raisebox{0.5em}{\small 2}-5x+2 , x -> 4x\raisebox{0.5em}{\small 2}+7x-6 )\\
\hline
Ligne à taper par l'utilisateur & expand(A(x)*B(x))\\
\hline
Ligne retournée par Xcas & 12*x\raisebox{0.5em}{4}+x\raisebox{0.5em}{3}-45*x\raisebox{0.5em}{2}+44*x-12\\
\hline
\end{tabularx}

\medskip

Le produit de $A$ et $B$ est donc un polynôme de degré 4, c'est-à-dire que $d^\circ(AB)=d^\circ(A)+d^\circ(B)$.

Ainsi, si l'on veut déterminer le produit de deux polynômes de degrés respectifs 7 et 10, on aura un polynôme de degré $7+10=17$... Ce qui risque d'être très fastidieux !

\section{La méthode rapide}

En distribuant, on s'aperçoit que le coefficient de $x^k$ dans $AB(x)$ s'obtient en ajoutant les produits des coefficients de $x^p$ (dans $A(x)$) et $x^q$ (dans $B(x)$) tels que $p+q=k$, pour $k$ allant de 0 à 4.

Nous allons donc construire un tableau dans lequel seront tous les coefficients de $A$ et de $B$ selon le degré de $x^k$ :

\begin{center}
\begin{tabular}{|Sl|*3{Sc|}}
\hline
Exposants des $x^k$ & 2 & 1 & 0\\
\hline
Coefficients de $A$ & 3 & $-5$ & 2\\
\hline
Coefficients de $B$ & 4 & 7 & $-6$\\
\hline
\end{tabular}
\end{center}
Nous allons maintenant construire et compléter un tableau à 5 colonnes car le polynôme produit aura un degré égal à 4 (il y aura donc 5 coefficients en comptant la constante) :
\begin{center}
\begin{tabular}{|Sl|*5{Sc|}}
\hline
Exposants des $x^k$ & 4 & 3 & 2 & 1 & 0\\
\hline
Coefficients de $AB$ &  &  & & & \\
\hline
\end{tabular}
\end{center}
\begin{itemize}
\item Pour déterminer le coefficient de $x^4$ dans $AB$, on regarde la façon dont on peut obtenir 4 en ajoutant deux exposants de la liste : $(2,1,0)$ (qui sont les exposants de $A$ et $B$).

Il n'y a qu'une façon d'obtenir 4 : $2+2=4$. Par conséquent, on multiplie 3 et 4 : on obtient 12 donc le produit $AB$ commence par $12x^4$.
\begin{center}
\begin{tabular}{|Sl|*5{Sc|}}
\hline
Exposants des $x^k$ & 4 & 3 & 2 & 1 & 0\\
\hline
Coefficients de $AB$ & $3\times4=12$ &  & & & \\
\hline
\end{tabular}
\end{center}

\item Ensuite, on regarde comment obtenir 3 en ajoutant deux exposants. On peut faire $2+1$ ou $1+2$, ce qui revient à multiplier 3 par 7 et $-5$ par 4 ; on a alors 21 et $-20$. On ajoute ces nombres et on obtient 1 : 
\begin{center}
\begin{tabular}{|Sl|*5{Sc|}}
\hline
Exposants des $x^k$ & 4 & 3 & 2 & 1 & 0\\
\hline
Coefficients de $AB$ & 12 & $3\times7+(-5)\times4=1$ & & & \\
\hline
\end{tabular}
\end{center}

\item Ensuite, on voit que \og 2 \fg{} s'obtient en faisant $2+0$, $0+2$ ou $1+1$, ce qui revient à faire $3\times(-6)$, $2\times4$ et $-5\times7$. On obtient alors $-18$, 8 et $-35$ et en les ajoutant, on a le coefficient du terme $x^2$ de $AB(x)$ :
\begin{center}
\begin{tabular}{|Sl|*5{Sc|}}
\hline
Exposants des $x^k$ & 4 & 3 & 2 & 1 & 0\\
\hline
Coefficients de $AB$ & 12 & 1 & $3\times(-6)+2\times4+7\times(-5)=-45$ & & \\
\hline
\end{tabular}
\end{center}

\item Ensuite, on voit que \og 1 \fg{} s'obtient en faisant $0+1$ ou $1+0$, ce qui revient à faire $-5\times(-6)$ et $2\times7$ :
\begin{center}
\begin{tabular}{|Sl|*5{Sc|}}
\hline
Exposants des $x^k$ & 4 & 3 & 2 & 1 & 0\\
\hline
Coefficients de $AB$ & 12 & 1 & $-45$ & $-5\times(-6)+2\times7=44$ & \\
\hline
\end{tabular}
\end{center}

\item Il s'en suit alors :
\begin{center}
\begin{tabular}{|Sl|*5{Sc|}}
\hline
Exposants des $x^k$ & 4 & 3 & 2 & 1 & 0\\
\hline
Coefficients de $AB$ & 12 & 1 & $-45$ & $44$ & $2\times(-6)=-12$\\
\hline
\end{tabular}
\end{center}
\end{itemize}

Par cette méthode, on peut obtenir le produit de deux polynômes de degrés quelconques.

\section{Exemple supplémentaire}

Soient $A(x)=-2x^4+4x^3-x+2$ et $B(x)=x^3-3x^2+x-1$.

On construit le premier tableau :
\begin{center}
\begin{tabular}{|Sl|*5{Sc|}}
\hline
Exposants des $x^k$ & 4 & 3 & 2 & 1 & 0\\
\hline
Coefficients de $A$ & $-2$ & 4 & 0 & $-1$ & 2\\
\hline
Coefficients de $B$ & 0 & 1 & $-3$ & 1 & $-1$\\
\hline
\end{tabular}
\end{center}
$d^\circ(A)=4$ et $d^\circ(B)=3$ donc $d^\circ(AB)=4+3=7$ d'où:

\begin{multicols}{2}
Exposant 7 : $-2\times1=-2$

Exposant 6 : $-2\times(-3)+4\times1=10$

Exposant 5 : $-2\times1+4\times(-3)=-14$

Exposant 4 : $-2\times(-1)+4\times1+1\times(-1)=5$ 

Exposant 3 : $4\times(-1)+2\times1+(-1)\times(-3)=1$ 

Exposant 2 : $2\times(-3)+1\times(-1)=-7$ 

Exposant 1 : $-1\times(-1)+2\times1=3$

Exposant 0 : $2\times(-1)=-2$
\end{multicols}

Soit : 

\medskip

\begin{tabularx}{\linewidth}{|Sl|*8{S{>{\centering\arraybackslash}X}|}}
\hline
Exposants & 7 & 6 & 5 & 4 & 3 & 2 & 1 & 0\\
\hline
Coef. de $AB$ & 
$-2$ & % 7
$10$ &  % 6
$-14$ & %5
$5$ & % 4
$1$ & % 3 
$-7$ & % 2
$3$ & % 1
$-2$\\
\hline
\end{tabularx}

\newpage

\section{Un algorithme sous Algobox}

\begin{algobox}
\Variables
\Ligne n EST\_DU\_TYPE NOMBRE
\Ligne p EST\_DU\_TYPE NOMBRE
\Ligne A EST\_DU\_TYPE LISTE
\Ligne B EST\_DU\_TYPE LISTE
\Ligne i EST\_DU\_TYPE NOMBRE
\Ligne S EST\_DU\_TYPE NOMBRE
\Ligne j EST\_DU\_TYPE NOMBRE
\Ligne k EST\_DU\_TYPE NOMBRE
\Ligne AB EST\_DU\_TYPE LISTE
\DebutAlgo
\Ligne LIRE n
\Ligne LIRE p
\Ligne S PREND\_LA\_VALEUR n+p
\Pour{i}{0}{n}
\DebutPour
\Ligne LIRE A[i]
\FinPour
\Pour{i}{0}{p}
\DebutPour
\Ligne LIRE B[i]
\FinPour
\Pour{i}{0}{S}
\DebutPour
\Ligne AB[i] PREND\_LA\_VALEUR 0
\Pour{j}{0}{n}
\DebutPour
\Pour{k}{0}{p}
\DebutPour
\Si{(j+k==i)}
\DebutSi
\Ligne AB[i] PREND\_LA\_VALEUR AB[i]+A[j]*B[k]
\FinSi
\FinPour
\FinPour
\FinPour
\Pour{i}{0}{S}
\DebutPour
\Ligne AFFICHER "Coefficient de x exposant "
\Ligne AFFICHER i
\Ligne AFFICHER " : "
\Ligne AFFICHER AB[i]
\Ligne AFFICHER "."
\FinPour
\FinAlgo
\end{algobox}

\medskip

[Cet algorithme est fourni dans le fichier ZIP]

\medskip


Cet algorithme demande d'abord d'entre le degré de $A$ ($n$) et celui de $B$ ($p$). $S$ représente alors le degré de $AB$.

Ensuite, on entre les coefficients de $A$ selon les puissances de $x$ \underline{croissantes} (on entre $a_0$, puis $a_1$, etc.) ainsi que ceux de $B$.

Par exemple, pour $A(x)=3x^2-5x+2$ et $B(x)=4x^2+7x-6$, on entre d'abord : 2, $-5$ et 3 pour $A$, puis $-6$, 7 et 4 pour $B$.

En sortie, on a les coefficient de $AB$ selon les puissances de $x$ croissantes (on a d'abord la constante, puis le coefficient de $x$, puis celui de $x^2$).

\newpage

Dans notre exemple, on a donc en sortie :

\medskip

Coefficient de x exposant 0 : $-12$.\\
Coefficient de x exposant 1 : $44$.\\
Coefficient de x exposant 2 : $-45$.\\
Coefficient de x exposant 3 : $1$.\\
Coefficient de x exposant 4 : $12$.

\section{Pour aller plus loin...}

Considérons deux polynômes :
\[
A(x)=\displaystyle\sum_{k=0}^n a_kx^k=a_0+a_1x+a_2x^2+\cdots+a_{n-1}x^{n-1}a_nx^n
\] 
et 
\[
B(x)=\displaystyle\sum_{k=0}^p b_kx^k=b_0+b_1x+b_2x^2+\cdots+b_{p-1}x^{p-1}+b_px^p\;.
\]
Alors, le polynôme $AB(x)$ est égal à :
\begin{align*}
AB(x) & = \big(a_0+a_1x+a_2x^2+\cdots+a_{n-1}x^{n-1}a_nx^n\big)\big(b_0+b_1x+b_2x^2+\cdots+b_{p-1}x^{p-1}+b_px^p\big)\\
& = a_0b_0 + (a_0b_1+a_1b_0)x + (a_0b_2+a_1b_1+a_2b_0)x^2 + \cdots
\end{align*}

On constate que dans les sommes donnant chaque coefficient de $x^k$, les produits $a_ib_j$ sont tels que $i+j=k$. On écrit alors :
\[
AB(x) = \sum_{k=0}^n c_kx^k\qquad\text{, où }c_k=\sum_{\substack{i+j=k\\0\leqslant i\leqslant n\\0\leqslant j\leqslant p}}a_ib_j \;. 
\]
\end{document}