\documentclass[11pt]{article}

\usepackage[french]{babel}
\usepackage{fullpage}
\usepackage[latin1]{inputenc}
\usepackage{amsmath,amsthm,amssymb}
\usepackage{multicol}
\usepackage[usenames]{color}

\parindent=0pt

\newcounter{question}
\setcounter{question}{0}
\newcommand{\question}{\stepcounter{question}\paragraph{\thequestion/}}
\newcommand{\ques}{\stepcounter{question}\textbf{\thequestion/} }
\def\tcbr#1{{\color{BrickRed} #1}}


\def\N{\mathbb{N}}
\def\Z{\mathbb{Z}}
\def\ss{\smallskip}
\def\bu{{$\bullet$}}
\def\pointir{\unskip . --- \ignorespaces}
\def\mref#1{(\ref{#1})}

%%% Flèches %%%%%%%%%%%

\def\dra{{$\rightarrow$}}
\def\dla{{$\leftarrow$}}
\def\dua{{$\uparrow$}}
\def\dda{{$\downarrow$}}
\def\ra{\rightarrow}
\def\ra{\rightarrow}
\def\da{\downarrow}
\def\sw{\swarrow}
\def\se{\searrow}
\def\ne{\nearrow}
\def\lra{\leftrightarrow}
\def\Lra{\Longrightarrow}
\def\ul#1{\underline #1}

%%%% Sauts %%%%%%%%%%%%
\def\bs{\bigskip}
\def\ms{\medskip}
\def\ss{\smallskip}
%%%%%%%%%%%%%%%%%%%%%%
\def\2#1{\ifnum#1<10 0\fi\the#1}
\xdef\isodayandtime{
%\centerline
{\2\day-\2\month-\the\year\space\2{\count0}:%
\2{\count2}}}
%\endgroup

%%%%%%%%%%%%%%%%%%%%%%
\begin{document}
{Institut Galilée \hfill L1PC -- Année 2013}

\begin{center}
{\Large \hfill Programmation\hfill 
\textbf{Partiel I Corrigé\setcounter{footnote}{-1}\footnote{Version du \isodayandtime}}\\ 
\hfill\small{(28.02.2012)}}\\
\end{center}

\bs
{\footnotesize Seules les notes manuscrites, le support de cours 
et la calculette sont autoris\'es. Le 
candidat s'efforcera de r\'ediger lisiblement et avec soin sa copie. En particulier, les 
r\'eponses doivent \^etre justifi\'ees.\\
Le sujet est (en principe) trop long pour le temps imparti, il est donc 
conseill\'e de traiter en priorit\'e les questions que l'on sait faire 
en en indiquant clairement la r\'ef\'erence\\
\tcbr{Les réponses et explications sont indiquées dans le texte en rouge brique.}}.

\bs
{\bf I}) {\sc Question de Cours}:

A) 1) Quels objets définissent la grammaire suivante ? 

\ss
\begin{center}
\begin{tabular}{llllll}
				&		&	&$\bullet$  &		&\\
${\cal A}\ =\ \Box\ + $	&		&$\sw$	&	    &$\se$	&\\
				&${\cal A}$	&	&	    &		&${\cal A}$\\
\end{tabular}
\end{center}
\tcbr{Les arbres binaires complets.}

2) a) Donner les arbres qui ont entre 2 et 4 feuilles ($2\leq n\leq 4$, 8 arbres en tout).\\
\tcbr{Les dessins ont été faits plusieurs fois en cours (je peux insérer l'image sur demande). Bien respecter la grammaire ! Pour vérification, il y a un arbre à $2$ feuilles, $2$ arbres à $3$ feuilles, et $5$ arbres à $4$ feuilles.}
\\
b) Préciser à chaque fois (dans les dessins) les sous-arbres gauche et droit.\\
\tcbr{Comme le dit la grammaire, chaque arbre qui a plus de $2$ feuilles se présente sous la forme
\begin{center}
\begin{tabular}{llllll}
				&		&				&$\bullet$  &				&\\
       	&		&$\sw$	&	    			&$\se$	&\\
				&$t_1$	&	&	    &				&$t_2$\\
\end{tabular}
\end{center}
$t_1$ est le sous-arbre gauche et $t_2$ est le sous-arbre droit. Dans la suite, on va le noter $(t_1,t_2)$.
}

Soit $a_n$, le nombre d'arbres binaires complets à $n$ feuilles.\\
c) Expliquer pourquoi $a_n$ vérifie la récurrence : 
\begin{equation}
	a_1=1\ ;\ a_n=\sum_{k=1}^{n-1}a_ka_{n-k}
\end{equation}
\tcbr{Le seul arbre à une feuille est $\Box$, donc $a_1=1$. Quand $n\geq 2$, les arbres à $n$ feuilles sont du type $(t_1,t_2)$ avec $t_1$ (sous-arbre gauche) à $k$ feuilles et $t_2$ (sous-arbre droit) à $n-k$ feuilles. On a $1\leq k\leq n-1$, leur nombre, pour $k$ fixé, est $a_ka_{n-k}$, il faut ensuite faire la somme sur tous les $k$ possibles.}\\
d) Donner les premières valeurs de $a_n$ sous forme d'un tableau (on complètera pour $n\leq 7$)

\begin{center}
\begin{tabular}{|l||l|l|l|l|}
\hline
$n$  & $1$ & $2$ & $3$ & $\cdots$ \\
\hline
$a_n$ & $1$ &$1$ & $2$ & $\cdots$ \\
\hline
\end{tabular}
\end{center}
%  
\tcbr{
\begin{center}
\begin{tabular}{|c||c|c|c|c|c|c|c|}
\hline
$n$  & $1$ & $2$ & $3$ & $4$ & $5$ & $6$ & $7$\\
\hline
$a_n$ & $1$ &$1$ & $2$ & $5$ & $14$ & $42$ & $132$\\
\hline
\end{tabular}
\end{center}
}
3) a) Qu'est-ce qu'un arbre binaire incomplet ?\\
\tcbr{C'est un arbre
\begin{enumerate}
	\item Soit réduit à une feuille $\Box$ 
	\item Soit du type un sommet avec un fils gauche, un fils droit ou deux fils
\end{enumerate}
}
b) Donner la grammaire qui permet de les définir/construire.\\
\tcbr{
\ss
\begin{center}
\begin{tabular}{llllllll}
			   	&$\bullet$	&	&$\bullet$	&   &		&$\bullet$  &\\
${\cal A}\ =\ \Box\ + $	& $\sw$  	&$+$  & $\se$   	&$+$& $\sw$	&	    &$\se$	\\
				&${\cal A}$	&     &${\cal A}$ 	&   &${\cal A}$&        &${\cal A}$\\
\end{tabular}
\end{center}
}
Soit $b_n$, le nombre d'arbres binaires incomplets à $n$ n\oe uds.\\
c) Dessiner les arbres binaires incomplets à $n$ n\oe uds pour $n\leq 4$ et donner les nombres 
$b_n$ correspondants.\\
\tcbr{Les dessins ont été faits plusieurs fois en cours (je peux insérer l'image sur demande). Bien respecter la grammaire ! Pour vérification, il y a un arbre à $1$ n\oe ud (c'est $\Box$), $2$ arbres à $2$ n\oe uds, $5$ arbres à $3$ n\oe uds, $14$ arbres à $4$ n\oe uds.}\\
d) Expliquer pourquoi $b_n$ vérifie la récurrence : 
\begin{equation}
	b_1=1\ ;\ b_n=2b_{n-1}+\sum_{k=1}^{n-2}b_kb_{n-1-k}
\end{equation}
\tcbr{Le seul arbre à un n\oe ud est $\Box$, donc $b_1=1$. Quand $n\geq 2$, les arbres à $n$ n\oe ud sont 
\begin{enumerate}
	\item soit type $(t_1,-)$ (un sommet avec un fils gauche) avec $t_1$ (sous-arbre gauche) à $n-1$ n\oe uds 
	\item soit type $(-,t_2)$ (un sommet avec un fils droit) avec $t_2$ (sous-arbre droit) à 
$n-1$ n\oe uds
	\item soit type $(t_1,t_2)$ (un sommet avec un fils gauche {\bf et} un fils droit ) avec $t_1$ (sous-arbre gauche) à $k$ n\oe uds et avec $t_2$ (sous-arbre droit) à $n-1-k$ n\oe uds. On a $1\leq k\leq n-2$, leur nombre, pour $k$ fixé, est $b_kb_{n-1-k}$, il faut ensuite faire la somme sur tous les $k$ possibles. 
\end{enumerate}
(1) et (2) donnent $2b_{n-1}$ et (3) donne $\sum_{k=1}^{n-2}b_kb_{n-1-k}$.}\\
d) Donner les premières valeurs de $b_n$ sous forme d'un tableau comme ci-dessus 
(on complètera pour $n\leq 7$).
\tcbr{
\begin{center}
\begin{tabular}{|c||c|c|c|c|c|c|c|}
\hline
$n$  & $1$ & $2$ & $3$ & $4$ & $5$ & $6$ & $7$\\
\hline
$b_n$ & $1$ & $2$ & $5$ & $14$ & $42$ & $132$ & $429$\\
\hline
\end{tabular}
\end{center}
}

\ss
B) (Commandes Maple) \\
1) Donner le sens et la construction des commandes suivantes :
\begin{center}
\begin{tabular}{llllll}
\verb+for+&\verb+if+ &\verb+op+&\verb+nops+&\verb+random+& \verb+whattype+
\end{tabular}
\end{center}

\newpage
\tcbr{Voir l'aide de Maple. Par exemple, pour\\
$>${\tt ? for}\\
on obtient la construction
\begin{eqnarray}
&&| for <name> | | from <expr> | | by <expr> | | to <expr>\cr
&&| | while <expr> | do <statement sequence> end do;
\end{eqnarray}
les explications suivent.
}

\bs
{\bf II}) {\sc Exercices}:\\
%
1) Mettre les nombres binaires suivants sous forme d\'ecimale\\
a) $(101101)_2$\qquad b)$(101101101)_2$\qquad
c) $(\underbrace{101\cdots 101}_{3n\;{\rm chiffres}})_2$ (pour le (c), on
montrera que la r\'eponse d\'epend de la conversion d'un nombre plus simple)
\\
\tcbr{a) $45$, b) $365$, c) Soit $c_n$ ce chiffre, on a $c_{n+1}=8c_n+5$ avec $c_1=5$. Si l'on veut ``pousser'' (mais ce n'était pas exigé), on peut résoudre et avoir $c_n=5/7(8^n-1)$.}
\\
2) Mettre les fractions suivantes sous forme d\'ecimale\par
a) $(0,615)_8$  b) $(12,321)_5$
c) $(0,\underbrace{7777777777}_{10\;{\rm  chiffres}})_8$
\\
\tcbr{a) $\frac{397}{512}$, b) $\frac{961}{125}$, c) $\frac{1073741823}{1073741824}$}
\\
3) Calculer\par
a) $a_n=(0,\underbrace{5\cdots 5}_{n\;{\rm chiffres}})_8$\qquad
b) $b_n=(12,\underbrace{1212\cdots 12}_{2n\;{\rm chiffres}})_8$\qquad
c) $c_n=(12,\underbrace{2112\cdots 2112\cdots}_{
n\;{\rm chiffres}})_8$ \par
d) $f_1=(0,(54321)^{\infty})_8$\par
e) le d\'eveloppement d\'ecimal illimit\'e de\par
i) $23/7$\qquad  ii) $7/22$\qquad iii) $1/99999$ \bigskip
\\
\tcbr{(a) $a_n=5.\Big(\frac{1-8^{-n}}{7}\Big)$, (b) $b_n=10+10.\Big(\frac{1-8^{-2n}}{63}\Big)$,
(c) $c_n=10+1098.\Big(\frac{1-8^{-4n}}{4095}\Big)$, (d) $\frac{22737}{32767}$\\
(e) i) $\frac{23}{7}=3,(285714)^\infty$ ii) $\frac{7}{22}=0,3(18)^\infty$ iii) 
$\frac{1}{99999}=0,(00001)^\infty$
}\\
4) Conversions Fraction $\leftrightarrow$ D\'eveloppements illimit\'es
en base $b$ (les r\'esultats seront toujours donn\'es en base dix
sauf pour les points c,e).\\
\begin{tabular}{lll}
a) $12,(345)^\infty;\ b=10$ & b) $12,(345)^\infty;\ b=8$\\
c) $BA/CA;\ b=16$ & d) $22/132;\ b=10$ & e) $BA,(CA)^\infty;\ b=16$ \\
\end{tabular}
\\
\tcbr{
(a) $\frac{4111}{333}$ (b) $\frac{5339}{511}$ (c) $(BA/CA)_{16}=\frac{93}{101}=0,(9207)^\infty$ 
(d) $0,1(6)^\infty$ (e) $\frac{23917}{255}$}

\bs
{\bf III}) {\sc Probl\`eme}\pointir
\\
%
A) On définit une suite de points (c'est à dire une application $\N\ra \N^2$) par 
le diagramme suivant :
%
\begin{center}
\begin{tabular}{ccccccc}
     	&$\cdots$&\bu    	&\dla   	& \bu   	&\dla  	&\bu   	\\ 
    	&       	&       	&       	&       	&       	& \dua  \\ 
\bu     	& \dra  	& \bu   	& \dra  	& \bu   	&   	& \bu	\\ 
\dua   	&       	&          &       	& \dda  & 	&\dua \\
\bu        &  \dla	&\bu    	&       	& \bu    &          & \bu  	\\
        	&       	&\dua   &       	& \dda 	&       	& \dua \\
$\circ$ &\dra  	&\bu    	&       	& \bu  	& \dra  	& \bu   	\\
\end{tabular}
\end{center}
c'est une suite de couples ($c_n$), le point de d\'epart ($\circ$) \'etant 
l'origine ($c_0=(0,0)$).\\
%
1) Soit $h_0(n)$, l'indice du (n+1)\up{\`eme} passage de $c_n$ sur l'``axe des abcisses''  
(d'équation $y=0$), on a $h_0(0)=0$.\\
a) Vérifier que les premières valeurs de $h_0$ sont
%
\begin{center}
\begin{tabular}{c||c|c|c|c|c|c|}
$n$			&0	&1	&2 	&3	&4	&5\\
\hline
$h_0(n)$&0	&1	&8	&9  &24 &25\\
\end{tabular}
\end{center}
\tcbr{Il s'agit juste d'une vérification. Si l'on veut détailler, on peut donner les points qui correspondent soit dire\\ 
En effet
$$
c_0=(0,0),\ c_1=(1,0),\ c_8=(2,0),\ c_9=(3,0),\ c_{24}=(4,0),\ c_{25}=(5,0)
$$
d'une manière générale $c_{n^2-1}=(n-1,0),\ c_{n^2}=(n,0)$. 
}

b) \'Evaluer la longueur du ``serpent'' qui 
\begin{enumerate}
	\item part verticalement du point $(2n+1,0)$)
	\item pour aller à la diagonale en $(2n+1,2n+1)$ 
	\item puis vers l'``axe des ordonnées'' en $(0,2n+1)$
	\item s'élève d'un pas en $(0,2n+2)$
	\item revient vers la diagonale en $(2n+2,2n+2)$
	\item puis vers l'``axe des abcisses'' en $(2n+2,0)$
	\item refait un pas en $(0,2n+3)$
\end{enumerate}

\tcbr{
\begin{itemize}
	\item (1-2) a pour longueur $2n+1$
	\item (3) a pour longueur $2n+1$
	\item (4) a pour longueur $1$ 
	\item (5) a pour longueur $2n+2$
	\item (6) a pour longueur $2n+2$
	\item (7) a pour longueur $1$
\end{itemize}
au total, on a une longueur de $8n+8$.}

c) En déduire que $h_0(2n+1)=(2n+1)^2$.\\
\tcbr{En effet, pour $n=0$, on a bien $h_0(1)=1$. D'autre part $h_0(2n+3)=h_0(2n+1)+8n+8$, si on 
fait l'hypoth\`ese de récurrence que $h_0(2n+1)=(2n+1)^2$, on a 
$$
h_0(2n+3)=(2n+1)^2+8n+8=4n^2+4n+1+8n+8=4n^2+12n+9=(2n+3)^2=(2(n+1)+1)^2
$$
ce qui montre le résultat.}\\
2) Soit $h_1(n)$, l'indice du n\up{\`eme} passage de $c_n$ sur la 
premi\`ere demi-diagonale $x=y;\ x> 0$.\\
a) Donner les premières valeurs de $h_1(n)$.\\
\tcbr{
\begin{center}
\begin{tabular}{c||c|c|c|c|c|}
$n$			&1	&2	&3 	&4	&5	\\
\hline
$h_1(n)$&0	&2	&6	&12  &20 \\
\end{tabular}
\end{center}
}
b) Calculer $h_1(n)$ en général. 
\tcbr{\`A cause de l'étape (1-2) de (b), on a $h_1(2n+2)=h_0(2n+1)+2n+1=(2n+1)(2n+2)$, à partir de là, on peut déduire $h_1(2n+1)$, donc $h_1$ en général.}

\ss
B) On construit une suite de $\Z^2$ par le proc\'ed\'e suivant\\
\tcbr{Cette partie n'a pas été abordée.} 
\end{document}


