\documentclass[a4paper,twocolumn]{article}
\usepackage{amstex,french,tp}
\advance\topmargin -1cm
\advance\textheight 1cm

\begin{document}

\begin{header}
\Huge Onzième TP
\bigskip
\end{header}

\section{Triangle de Pascal}
On définit les nombres $C_n^p$ par les
formules suivantes :
\begin{itemize}
\item[$\bullet$] $\forall n>0, C_n^1 = 1$
\item[$\bullet$] $\forall n>0, C_n^n = 1$
\item[$\bullet$] $\forall n<p, C_n^p = 0$
\item[$\bullet$] $\forall n>p>0, C_{n+1}^{p+1} = C_n^{p+1} + C_n^p$
\end{itemize}

Les premières lignes du tableau ressemblent donc à
\[
\begin{array}{c|c|c|c|c|c|}
\multicolumn{1}{c}{C_n^p}
  & \multicolumn{5}{c}{p} \cr\cline{2-6}
  & 1 & 0 & 0 & 0 & 0 \cr \cline{2-6}
  & 1 & 1 & 0 & 0 & 0 \cr \cline{2-6}
n & 1 & 2 & 1 & 0 & 0 \cr \cline{2-6}
  & 1 & 3 & 3 & 1 & 0 \cr \cline{2-6}
  & 1 & 4 & 6 & 4 & 1 \cr \cline{2-6}
\end{array}
\]

\subsection*{Tableau à deux dimensions}
\begin{itemize}
\item
Déclarer une variable tableau à deux dimensions
qui servira à stocker tous les $C_n^p$ pour
$1\leq n,p\leq 10$.
\item
Écrire une procédure qui remplit le tableau.
\item
Écrire une procédure qui affiche le tableau.
\item
Modifier la procédure précédente pour afficher
le caractère \verb|*| si l'élément correspondant
est impair, et un espace s'il est pair.
\end{itemize}

\subsection*{Sans tableau}
\begin{itemize}
\item
Faire une fonction qui a pour arguments \verb|n| et \verb|p|
et qui calcule $C_n^p$.
\item
Faire une procédure qui a pour argument un entier \verb|n|
et qui affiche les \verb|n| premières lignes du triangle
de Pascal.
\end{itemize}

\hrule

\section{Résolution par dichotomie}
On définit une fonction réelle d'une variable réelle,
par exemple :
\begin{verbatim}
FUNCTION F(x : REAL) : REAL;
VAR a, b, c : REAL;
BEGIN
  a := sin(x) + x * x;
  b := sin(x + a);
  c := cos(x) * cos(x/2) + a * b;
  IF a < x THEN F := a - 3
  ELSE IF b < c THEN F := b + a
  ELSE F := c;
END;
\end{verbatim}

On sait que cette fonction a au moins une solution
dans l'intervalle $[0,3]$.

Faire une fonction \verb|Dichotomie|
qui a deux arguments \verb|mini| et \verb|maxi|
et dont le résultat est la position d'une racine
de \verb|F|, avec une précision au moins $10^{-4}$.

\newpage

\section{Jeu de la vie}
On utilise un quadrillage. Chaque case a huit cases
voisines : quatre ayant un côté commun et quatre ayant
un sommet commun.

On place un certain nombre de cellules (cases pleines),
les autres cases sont vides.
Le but du jeu de la vie est de regarder comment évolue
cette population de cellules.

À chaque instant, il y a des cellules qui naissent et des
cellules qui meurent. Les naissances et les morts sont simultanées.
\begin{itemize}
\item[$\bullet$]
Une cellule meurt étouffée si elle a plus de trois voisines.
\item[$\bullet$]
Une cellule meurt isolée si elle a zéro ou une voisine.
\item[$\bullet$]
Une cellule nait dans une case de laquelle exactement trois
cellules sont voisines.
\end{itemize}

Exemple :
\bgroup\divide\tabcolsep3
\begin{tabular}{|p{.8em}|p{.8em}|p{.8em}|}\hline
X&X&\cr\hline &X&\cr\hline &X&\cr\hline
\end{tabular}
devient
\begin{tabular}{|p{.8em}|p{.8em}|p{.8em}|}\hline
X&X&\cr\hline &X&X\cr\hline &&\cr\hline
\end{tabular}
puis
\begin{tabular}{|p{.8em}|p{.8em}|p{.8em}|}\hline
X&X&X\cr\hline X&X&X\cr\hline &&\cr\hline
\end{tabular}
\egroup

\subsection*{Sur un tableau borné}
\begin{itemize}
\item
On définit un type \verb|Univers|
qui est un \\\verb|ARRAY[1..10,1..10] OF BOOLEAN|.
\item
Faire une procédure \verb|Affiche|
qui affiche la position des cellules.
\item
Faire une procédure \verb|Evolution|
qui modifie une variable de type \verb|Univers|
pour faire naître et mourir les cellules.
\item
Utiliser les procédures précédentes
pour montrer l'évolution d'un univers
aléatoire.
\end{itemize}

On pourra aussi regarder le comportement
particulier du motif ci-dessous :
\begin{center}\divide\tabcolsep3
\begin{tabular}{|p{.8em}|p{.8em}|p{.8em}|}\hline
&&X\cr\hline X&&X\cr\hline &X&X\cr\hline
\end{tabular}
\end{center}

\subsection*{Sur un terrain infini (difficile)}
Pour ne pas être limité par la taille du terrain,
on remplace le type \verb|Univers| précédemment
défini par \\\verb|ARRAY[1..1000] OF RECORD x,y:INTEGER; END|.

Ceci permet de représenter l'évolution d'au plus
1000 cellules, sur un terrain vituellement infini.

Réfléchir à la façon de faire le calcul de
l'évolution de l'univers et à la façon de faire
l'affichage.

\end{document}
