\documentclass[12pt,french]{article}
\usepackage[french]{babel}
\usepackage[utf8]{inputenc}

\usepackage{amssymb,fancybox,fancyhdr,lastpage,a4,mdwlist,graphicx}
\usepackage{pstricks,pst-node,pst-tree,pst-coil,amsmath}

\topmargin-0.5cm
\headheight20pt
\textheight23cm
\textwidth17.5cm
\oddsidemargin-1cm
\evensidemargin0cm
\parindent0pt

\def\[{[\![}
\def\]{]\!]}

\begin{document}

\renewcommand{\labelenumi}{\arabic{enumi})}
\renewcommand{\labelenumii}{\alph{enumii})}
\renewcommand{\labelenumiii}{\roman{enumiii})}

\pagestyle{fancy}
\lhead{{\bf MPSI option info}}
\chead{}
\rhead{TP 4~: impératif}
\lfoot{\sl Lyc\'ee Chateaubriand}
\cfoot{}
\rfoot{\thepage/\pageref{LastPage}}

\renewcommand{\footrulewidth}{0.4pt}


\section{Exercice du cours}
\label{sec:orga9c9783}

\subsection*{Liste chaînée}
\label{sec:orgbfcb093}
Définir à la main une chaîne contenant \texttt{[0;1;2;3;4]} où chaque élément sera
\begin{itemize}
\item un couple \texttt{(u, p)} où \texttt{u} est la valeur stockée et \texttt{p} un pointeur vers l'élément suivant
\item sauf si il s'agit du dernier élément auquel cas ce sera \texttt{u}.
\end{itemize}

Quel est le type de l'objet ainsi construit ?

\section{Le crible d'Ératosthène}
\label{sec:org5be89b6}
Soit \(n\) un entier fixé. Le crible d'Ératosthène\footnote{Ératosthène est un astronome, géographe, philosophe et mathématicien grec du IIIe siècle av. J.-C. (Cyrène, v. -276 – Alexandrie, Égypte, v. -194).} est un algorithme qui permet de déterminer de manière efficace les entiers premiers strictement inférieurs à \(n\). On construit pour cela un tableau \(t\) de booléens de taille \(n\) dont toutes les cases sont initialisées à \texttt{true}, sauf les cases 0 et 1 qui contiennent initialement \texttt{false}.
Pour \(i\) variant de 2 à la partie entière de \(\sqrt{n}\), on itère alors le procédé suivant : si \texttt{t.(i)} contient \texttt{true} alors on met \texttt{false} dans toutes les cases du tableau dont l'indice est un multiple strict de \(i\). À la fin de l'algorithme, \texttt{t.(i)} contient \texttt{true} si
et seulement si l'entier \(i\) est premier.

\begin{description}
\item[{Question 1}] Écrivez une fonction \texttt{eratosthene} qui implémente cet algorithme.
\begin{verbatim}
val eratosthene : int -> bool array
\end{verbatim}
\item[{Question 2}] Écrivez une fonction \texttt{decompose\_somme} telle que \texttt{decompose\_somme t s} retourne un booléen indiquant si l'entier \texttt{s} se décompose comme la somme de deux entiers premiers. (\texttt{t} est un tableau de booléens de taille supérieure à \texttt{s} tel que \texttt{t.(x)} indique si \texttt{x} est premier.)
\begin{verbatim}
val decompose_somme : bool array -> int -> bool
\end{verbatim}
\end{description}

\section{Polynômes}
\label{sec:orgb98943a}

L'objet est d'étudier une implémentation des polynômes à une variable et des opérations élémentaires sur les polynômes. Un polynôme :
$$P = a_0 + a_1 X + a_2 X^2 + \cdots + a_n X^n$$
sera représenté en machine par le tableau Ocaml :
\begin{verbatim}
p = [|a0 ; a1 ; a2 ; ... ; an |]
\end{verbatim}
On se contentera de manipuler des polynômes à coefficients entiers donc \(a_0 , \cdots , a_n\) seront de type \texttt{int} et \texttt{p} de type \texttt{int array}.

\subsection*{1) Addition, soustraction, multiplication}
\label{sec:org49210ac}
Si
$$
P = \sum_{i = 0}^{d_P} a_i X^i
\quad\text{ et }\quad
Q = \sum_{i = 0}^{d_Q} b_i X^i
$$
alors
$$
P \pm Q = \sum_{i = 0}^{\max(d_P,d_Q)} (a_i \pm b_i) X^i
$$
en convenant que les \(a_i,b_i\) manquants valent zéro. Pour implémenter ceci en Ocaml une méthode consiste à définir un tableau résultat, \texttt{r}, suffisamment long initialisé à zéro, à y recopier \texttt{p} puis à lui ajouter ou retrancher \texttt{q}.

Voici le code d'une fonction \texttt{(++)} additionnant deux polynômes :
\begin{verbatim}
(* addition *)
let (++) p q =
  let lp = Array.length p
  and lq = Array.length q
  in
  let r = Array.make (max lp lq) 0 in
  for i=0 to lp-1 do
    r.(i) <- p.(i)
  done;
  for i=0 to lq-1 do
    r.(i) <- r.(i) + q.(i)
  done;
  r;;
\end{verbatim}

Recopier ce code, définir de même la soustraction et la multiplication des polynômes qui seront notées \texttt{(-{}-)} et \texttt{( ** )} (attention aux espaces entre les parenthèses et les étoiles, sinon c'est considéré comme un commentaire vide).

Tester vos fonctions avec les polynômes \texttt{p} et \texttt{q} définis ci-dessous ou avec d'autres.
\begin{verbatim}
let p = [| 1; 2; 3 |]     (* 1 + 2x + 3x^2 *)
and q = [| 4; 5; 6; 7|]   (* 4 + 5x + 6x^2 + 7x^3 *)
;;

p ++ q;;
\end{verbatim}


\subsection*{2) Les polynômes de Tchebychev}
\label{sec:org0b64ef0}
Il s'agit d'une suite de polynômes définis par les relations :
\begin{align*}
T_0 &= 1, \\
T_1 &= X, \\
T_n &= 2X T_{n-1} - T_{n-2} & \text{ si } n > 2.
\end{align*}

Programmer itérativement le calcul du \(n\)ème polynôme de Tchebychev à l'aide des opérations \texttt{++}, \texttt{-{}-} et \texttt{**} définies précédemment.

Vous pouvez au choix utiliser une matrice \texttt{t} avec \texttt{t.(i)} = \(T_i\) les \texttt{t.(i)} étant calculés de proche en proche ou, mais c'est plus compliqué à implémenter, n'utiliser que deux polynômes variables (donc en fait des références sur des polynômes) contenant les deux derniers polynômes calculés et faire \emph{évoluer} ces variables pour calculer les \(T_i\) de proche en proche. Quelque soit votre choix, votre fonction \texttt{tchebychev : int -> int array} ne devra retourner que le polynôme dont l'indice est fourni en argument et sa complexité devra être linéaire en $i$.

Vérifier que
$
T_{7}=64X^{7}-112X^{5}+56X^{3}-7X
$.

\begin{verbatim}
# tchebychev 7;;
- : int array = [|0; -7; 0; 56; 0; -112; 0; 64; 0; 0; 0; 0; 0; 0|]
(* Selon votre implémentation, il y a plus ou moins de zéros inutiles à la fin du tableau *)
\end{verbatim}

\subsection*{3) Composition}
\label{sec:org9b4b455}
Si
$
P = \sum_{i = 0}^{d_P} a_i X^i
$
et $Q$ est un polynôme quelconque alors
$
P \circ Q = \sum_{i = 0}^{d_P} a_i Q^i
$.
En particulier si $a$ est un entier, $P(a) = P \circ a$ où le deuxième $a$ désigne le polynôme constant $aX^0$. La composition des polynômes est une opération de même nature que l'évaluation en un point et les algorithmes d'évaluation peuvent être utilisés pour calculer une composée. En particulier, on peut utiliser l'algorithme de Hörner qui va consister \`a calculer $P \circ Q$ sous la forme
$
a_0 + Q \left( a_1 + Q \left (a_2 + \cdots + Q a_n \right)\cdots \right)
$.

Programmer cette opération de composition en Caml, elle sera notée \texttt{compose}. L'utiliser pour calculer :
\begin{verbatim}
compose [|0; 0; 0; 0; 0; 0; 1|] [|1; 1|]
\end{verbatim}
et expliquer quel est le résultat obtenu.

\subsection*{4) Division euclidienne}
\label{sec:orgd99ee27}
On considère l'algorithme suivant
\begin{quote}
\begin{description}
\item[{Entrée}] $A = \sum_i^n a_i X^i$ et $B = \sum_{i = 0}^m b_i X^i \in \mathbb R[X]$ avec $b_m \neq 0$
\item[{Sortie}] Le couple $(Q, R) \in \mathbb R[X]$ tel que $A = BQ + R$ et $\deg R < m$
\item[{1.}] Si $n < m$, renvoyer $Q = 0$ et $R = A$
\item[{2.}] $R \leftarrow A$, $u \leftarrow b_m^{-1}$
\item[{3.}] pour $i = n - m, n - m - 1, \cdots , 0$, faire
\begin{itemize}
\item si $\deg R = m + i$ alors
\begin{itemize}
\item $q_i \leftarrow \text{cd}(R)u$,
\item $R \leftarrow R - q_i X^i B$
\end{itemize}
\item sinon
\begin{itemize}
\item $q_i \leftarrow 0$
\end{itemize}
\end{itemize}
\item[{4.}] Renvoyer $Q = \sum_{i=0}^{n - m} q_i X^i$ et $R$
\end{description}
\end{quote}
où cd$(R)$ désigne le coefficient dominant d'un polynôme.


\begin{enumerate}
\item Que fait cet algorithme ?
\item Quelle est sa complexité en fonction de $n$ et $m$ ?
\item Est-ce que l'algorithme fonctionne avec des polynômes à coefficients entiers ?
\item Implémenter l'algorithme.
\end{enumerate}


\section{Jeu de Hex}
\label{sec:orga006daa}

Le jeu de Hex co-inventé par le mathématicien John Nash\footnote{John Forbes Nash, Jr. est un mathématicien et économiste américain du XXème siècle, très connu pour ses travaux en théorie des jeux et en économie. Il est le seul mathématicien et économiste à être lauréat à la fois du prix Nobel d'économie en 1994 et du prix Abel pour les mathématiques en 2015.} est un jeu de stratégie sur plateau à deux joueurs. Il se joue sur un plateau en forme de losange divisé en $14 \times 14$ (ou $11 \times 11$) cases hexagonales.

Les deux joueurs \texttt{O} et \texttt{X} jouent en posant une pièce à tour de rôle ; le but pour chacun des joueurs est de connecter un bord du plateau à son bord opposé par une chaîne connexe de pièces lui appartenant.


\begin{center}
\includegraphics[width=.5\textwidth]{Hex.png}
\end{center}

Sur cette image le joueur \texttt{O} a gagné. Une des particularités de ce jeu est que si l'on ne peut plus jouer, alors il y a toujours un et un seul joueur victorieux.


On codera le tableau hexagonal sous forme de matrice en faisant correspondre les lignes et en associant à une diagonale la colonne correspondante de la matrice (sur le dessin \texttt{A}, \texttt{B} et \texttt{H} sont envoyées respectivement sur les colonnes 0, 1 et 7 de la matrice).

\begin{enumerate}
\item Quelles sont les cases voisines de la case $(i,j)$ sur un plateau de taille $n$ ? Écrire une fonction \texttt{voisins : int -> int -> int -> (int * int) list} qui prend en paramètre $i,j$ et $n$. On fera attention aux cas limites.

\item Écrire une fonction qui étant donné un plateau de jeu sous forme d'une matrice $n \times n$ de \texttt{char} (\texttt{'O'}, \texttt{'X'} ou \texttt{' '} pour les cases vides) détermine si un joueur a gagné et si oui lequel.

\item S'il vous reste du temps, démontrer rigoureusement qu'il ne peut pas y avoir de match nul et qu'il existe toujours un gagnant.
\end{enumerate}
\end{document}