\documentclass[11pt]{article}

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

\parindent=0pt

\newcounter{question}
\setcounter{question}{0}
\newcommand{\question}{\stepcounter{question}\paragraph{\thequestion/}}
\newcommand{\ques}{\stepcounter{question}\textbf{\thequestion/} }

\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}

%%%% Sauts %%%%%%%%%%%%
\def\bs{\bigskip}
\def\ms{\medskip}
\def\ss{\smallskip}
%%%%%%%%%%%%%%%%%%%%%%

\begin{document}
{Institut Galilée \hfill L1PC -- Année 2011--2012}

\begin{center}
{\Large \hfill Programmation\hfill \textbf{Partiel III}\\ 
\hfill\small{(11.06.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}.

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

A) 1) Que représentent les courbes de \verb+Lissajous+  
\begin{equation}
\left\{ \
\begin{array}{rcl}
x(t) & = & sin(a.t)\\
y(t) & = & cos(c.t)\\
\end{array}
\right. \ ,
\end{equation}

2) a) Expliquer pourquoi, pour $(a,c)=(1,2)$, les coordonnées vérifient $y(t)=2x(t)^2-1$. 
Quelle est la portion de la courbe $y=2x^2-1$ qui est parcourue ? la représenter.\\
b) Reprendre la question pour $(a,c)=(2,1)$, expliquer pourquoi la courbe est $x=2y\sqrt{1-y^2}$. Indiquer la portion et la représenter. 

B) 1) a) Soit un r\'eel dont le d\'eveloppement en base $B=10$ est 
\begin{equation}\label{period}
X=(0,(a_{-1}a_{-2}\cdots a_{-p})^{\infty})_{10}
\end{equation}
donner la formule qui permet de retrouver la fraction $X$.\\
b) Soit maintenant un r\'eel dont le d\'eveloppement en base $B=10$ 
est 
\begin{equation}
X=(a_ma_{m-1}\cdots a_0,(a_{-1}a_{-2}\cdots a_{-p})^{\infty})_{10}
\end{equation}
utiliser la formule pr\'ec\'edente pour retrouver $X$.\\
c) Généraliser la formule pr\'ec\'edente pour retrouver pour $B$ quelconque.\\
d) Utiliser la formule \mref{period} pour trouver les fractions dont le DDI est 

\begin{center}
\begin{tabular}{ll}
a) $0,(1114)^\infty;\ b=10$ & 
b) $0,(047619)^\infty;\ b=10$
\end{tabular}
\end{center}

2) a) Quels sont les r\'eels qu'on peut repr\'esenter par une fraction 
continue (f.c.) ?\\
b) Donner le proc\'ed\'e de calcul des coefficients.\\
c) Quels sont les r\'eels dont la repr\'esentation est ultimement 
p\'eriodique ?\\
d) {\sc Application}\pointir Calculer les coefficients de la 
repr\'esentation en f.c. de $\sqrt{3}$. De $\sqrt{17}$.

\ss
C) 1) a) Qu'est-ce qu'un arbre binaire complet ?\\
b) Donner la grammaire qui permet de les définir/construire.\\
Soit $a_n$, le nombre d'arbres binaires complets à $n$ feuilles.\\
c) Dessiner les arbres binaires complets à $n$ feuilles pour $n\leq 4$ et donner les nombres 
$a_n$ correspondants.\\
d) 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}
   
2) a) Qu'est-ce qu'un arbre binaire incomplet ?\\
b) Donner la grammaire qui permet de les définir/construire.\\
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.\\
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}
      
\ss
{\bf II}) {\sc Exercices}\pointir
\\
1) Conversions Fraction $\leftarrow$ D\'eveloppements illimit\'es 
en base $b$ (les r\'esultats seront toujours donn\'es en base dix).\\

\begin{center}
\begin{tabular}{ll}
a) $13,(1114)^\infty;\ b=10$ & 
b) $10,(047619)^\infty;\ b=10$\\
c) $0,0(1311)^\infty;\ b=10$ & d) $0,(10111)^\infty;\ b=10$\\
\end{tabular}
\end{center}

2) Conversions Fraction $\rightarrow$ D\'eveloppements illimit\'es 
 (les r\'esultats seront donn\'es en base $10$).\\

\begin{center}
\begin{tabular}{llll}
a) $9/47$ & b) $11/101$ & c) $1/13$ & 
c) $3/8$
\end{tabular}
\end{center}

\ss
{\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}
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}

c) En déduire que $h_0(2n+1)=(2n+1)^2$.\\  
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)$.
b) Calculer $h_1(n)$ en général. 

\ss
B) (Fontaines de pièces)\pointir\\
Les fontaines de pièces sont des structures comme figuré ci-dessous
\begin{center}
\includegraphics[scale=0.2]{Coins.ps}
\\
\small{{\it\qquad Une fontaine de pi\`eces.}}
\end{center}
1) Montrer qu'une fontaine de pièces est 
\begin{enumerate}
	\item soit une ligne de pièces (et rien au dessus) 
	\item soit une ligne de pièces sur laquelle on pose une autre fontaine
\end{enumerate}

Soit $c_n$ le nombre de fontaines qui ont $n$ pièces ``\`a la base''. Pour vérification 
les premières valeurs de $c_n$ sont
\begin{center}
\begin{tabular}{c||c|c|c|c}
$n$ & 1 & 2 & 3 & 4\cr
\hline
$c_n$ & 1 & 2 & 5 & 13
\end{tabular}
\end{center}
 
2) Expliquez pourquoi $c_n$ vérifie la récurrence suivante 
\begin{equation}
	c_1=1\ ;\ c_n=1+\sum_{j=1}^{n-1}(n-j)\, c_j
\end{equation}
 
3) En déduire que $S=\sum_{n=1}^\infty c_n\, z^n$ vérifie 
\begin{equation}\label{rec1}
	S=\frac{z}{1-z}+\frac{z}{(1-z)^2}\, S
\end{equation}

4) Résoudre \mref{rec1} et montrer que 
\begin{equation}
	S=\frac{z(1-z)}{1-3z+z^2}
\end{equation}

\end{document}


