\documentclass[a4paper,11pt]{article}
\usepackage{fullpage,lastpage,ifthen}
\usepackage[on]{auto-pst-pdf}  % [off] si pas de modification des pspictures
\usepackage[francais]{babel}
\usepackage{amssymb,amsmath,pstricks-add}
% \usepackage{subfigure}
\usepackage[applemac]{inputenc}
\usepackage{ifpdf}
 \ifpdf
   \usepackage[pdftex]{hyperref}
  \hypersetup{pdftitle={\'Epreuve d'informatique de Polytechnique},colorlinks=true,pdfauthor={d'apr\`es UPS},%
 pdfmenubar=true}
 \else
  \usepackage[T1]{fontenc}
  \usepackage[applemac]{inputenc}
  \usepackage[dvips]{graphicx}
  \def\href#1#2{#2}
 \fi
\ifpdf
\hypersetup{pdfauthor={d'apr\`es l'UPS},pdftitle={d'apr\`es l'\'Epreuve de 
L'\'ecole Polytechnique PSI/PT 2013},pdfkeywords={informatique, polytechnique, 
concours, maple, algorithmique, classes pr\'eparatoires},
pdfsubject={Poteaux t\'el\'egraphiques},
pdftoolbar=true,pdfmenubar=true,bookmarks=true,
colorlinks=true}
\fi

\pagestyle{plain}

%%% Moi
\usepackage{fancyhdr}           % pied et tete de page                          
\usepackage{theorem,graphicx} %??                                               
\theoremstyle{break}\theorembodyfont{\rm}                                       
\newtheorem{exo}{\Large Exercice}                                               
\def\inter_exo{\rule[0.5ex]{\linewidth}{0.3mm}}                                 
\usepackage{stmaryrd}           % \rr et \llbracket
 \def\cad{c'est-\`a-dire}
 \newenvironment{itemiz}{\renewcommand \labelitemi{$\bullet$}\begin{itemize}}{\end{itemize}}

%%%%%% pied et tete de page : reglage %%%%%%                                    
\pagestyle{fancy}                                                               
%\lhead[\thepage]{\footnotesize\Titre}                                          
%\chead[]{}                                                                     
%\rhead[\footnotesize\Titre]{\thepage}                                          
\lhead[]{\Type}                                                                 
\chead[]{}                                                                      
\rhead[]{\NomChapitre}                                                          
\lfoot[]{\thepage}                                                              
\cfoot[]{}                                                                      
\rfoot[]{}                                                                      
%\usepackage[a4paper]{geometry}  % papier a4                                     


%%% /Moi

\setlength{\parindent}{0mm}

\makeatletter
\renewcommand%
{\section}{\@startsection{section}{2}{0mm}
{-\baselineskip}{0.25\baselineskip}%
{\normalfont\bf\Large\centering}}%
\makeatother 

% \parindent=0pt

%Macros
% \renewcommand{\leq}{\leqslant}
% \renewcommand{\geq}{\geqslant}
% \newcommand{\grandO}[1]{\mathop{O{}}\left(#1\right)}
% \newcommand{\tq}{\mid}
% \newcommand{\set}[1]{\left \{ #1 \right \}}
% \newcommand{\R}{\ensuremath{\mathbb{R}}}

 \newcommand{\LeTitre}[2]{%                                                   
 \title{}\date{}\author{}                                                       
 \maketitle                                                                     
 \vspace{-4.5cm}                                                                
Lycée La Prat's \hfill #2\\                                                    
Classe de PTSI\bigskip%                                                         
   \begin{center}%                                                              
     {\bfseries %                                                               
       \Large%                                                                  
       \'Epreuve d'Informatique #1%                                             
     }%                                                                         
   \end{center}\bigskip%                                                        
   \begin{center}%                                                              
Durée 1 h%                                                                      
   \end{center}%                                                                
%\\\bigskip%                                                                    
\inter_exo%                                                                     
\bigskip%\\%                                                                    
   \begin{center}%                                                              
     {\bfseries %                                                               
    L'utilisation des calculatrices \textbf{n'est pas autoris\'ee} pour %
    cette \'epreuve.\\% 
Nous attacherons la plus grande importance \`a la lisibilit\'e du code %
produit par les candidats; %
aussi, nous encourageons les candidats \`a introduire des proc\'edures ou %
fonctions interm\'ediaires %
lorsque cela en simplifie l '\'ecriture.    %
     }%                                                                         
   \end{center}                                                                 
\vspace{1cm}}%                                                                  

\begin{document}
\baselineskip=15pt
\def\NomChapitre{4}
\def\Type{DST}
\LeTitre{\NomChapitre}{Jeudi 15 mai 2014}                                     

{\em Une copie par exercice. Ne passez pas trop de temps sur la question 3 de
  l'exercice 1, vous pourrez y revenir après au besoin. L'énoncé est long car
  la présentation de l'exercice 2 est très détaillée.}

\begin{exo}%[\Large E3A 2013]
Soit $L$ une liste d'entiers relatifs, de taille $N$. 
\begin{enumerate}
\item \'Ecrire une fonction qui prend en argument une liste \texttt{L}
  d'entiers et retourne un liste \texttt{resultat} des sommes partielle
  $\displaystyle \sum_{i=0}^k \ell_i$ : la $k$-ème case de \texttt{resultat} contiendra la somme
\texttt{L[0]+$\dots$+L[k]}. On essayera (sans y passer trop de temps non plus) d'être le plus efficace (en terme de complexité) possible.
\item \'Ecrire une fonction qui prend en argument une liste \texttt{L}
  d'entiers et retourne la sous-somme $\displaystyle \sum_{i=0}^k \ell_i$
  maximale. %Déterminer la complexité dans le pire cas.
\item \'Ecrire une fonction qui prend en argument une liste \texttt{L}
  d'entiers et retourne la sous-somme $\displaystyle \sum_{i=k_1}^{k_2} \ell_i$
  maximale (on commence à $k_1$ quelconque désormais). %Déterminer la complexité dans le pire cas.
\end{enumerate}
\end{exo}

\newpage~\\
\begin{exo}[\Large Poteaux t\'el\'egraphiques]%X 2013
\end{exo}

Cette exercice a pour objectif de choisir o\`u placer des poteaux 
t\'el\'egraphiques pour relier le
point le plus \`a gauche d'un paysage unidimensionnel au point le plus 
\`a droite en fonction de 
crit\`eres de co\^ut. Nous ferons les simplifications suivantes : les fils 
sont sans poids et tendus; ils 
relient donc en ligne droite les sommets de deux poteaux cons\'ecutifs. 
Les normes de s\'ecurit\'e 
imposent que les fils soient en tout point \`a une distance d'au moins 
$\Delta$ (mesur\'ee verticalement) 
au-dessus du sol. Les poteaux sont tous de longueur identique $\ell 
\geqslant \Delta$. 
Voici par exemple une 
proposition valide de placement de poteaux pour le paysage ci-dessous 
avec $\Delta = 0.5$ et $\ell = 2.0$. 

	\begin{figure}[!h]
		\centering
	\begin{pspicture}(11,3.3)(0.5,0.5)
	\psset{levelsep=2cm,nodesep=0mm,unit=7mm}
		\psaxes[labels=none](18,0)
		\rput[t](0,-.3){0}
		\rput[t](11,-.3){$i$}
		\rput[b](18,.3){$n$}
		% ligne de cr\^ete
		\psline[linewidth=1.5pt](0,0)(1,-1)(2,1)(3,1.5)(4,2.8)(5,2.5)
		(6,1.5)(7,2.5)(8,2.5)(9,2)(10,3)(11,2.3)(12,2.0)(13,2.3)
		(14,1.5)(15,1.8)(16,1)(17,-0.1)(18,-2)
		% ligne de s\'ecurit\'e en pointill\'e
		\psline[linestyle=dotted](0,0.4)(1,-0.6)(2,1.4)(3,1.9)(4,3.2)
		(5,2.9)(6,1.9)(7,2.9)
		(8,2.9)(9,2.4)(10,3.4)(11,2.7)(12,2.4)(13,2.7)(14,1.9)(15,2.2)
		(16,1.4)(17,0.3)(18,-1.6)
		% les poteaux
		\psline[linewidth=2pt](0,0)(0,1.8)
		\psline[linewidth=2pt](7,2.5)(7,4.3)
		\psline[linewidth=2pt](16,1)(16,2.8)
		\psline[linewidth=2pt](18,-2)(18,-.2)
		% la ligne \'electrique
		\psline(0,1.8)(7,4.3)(16,2.8)(18,-.2)
		% pour h_{i}
		\psline[arrows=<->](11,0)(11,2.3)
		\rput[l](11.1,1.1){$h_{i}$}
		% pour Delta
		\psline[arrows=<->](7.5,2.5)(7.5,2.9)
		\rput[l](7.7,2.8){$\Delta$}
		% pour \ell
		\psline[arrows=<->](6.8,2.5)(6.8,4.3)
		\rput[r](6.6,3.5){$\ell$}
		\psline(6.6,2.5)(7,2.5)
		\psline(6.6,4.3)(7,4.3)
		
	\end{pspicture}
	\caption{Un exemple de poteaux o\`u le fil est en tout point au 
	moins $\Delta$ au-dessus du sol.}
	\label{fig1}
	\end{figure}

% z   
% 11/4, '\'\\ , - A'_\__'\og O'I/ '__'-_ kxx'
% o 1' a
% FIGURE 1 - Un exemple de poteaux o\`u le fil est en tout point au moins 
% $\Delta$ au-dessus du sol.

Tous les tableaux d\'efinis dans ce probl\`eme 
seront consid\'er\'es comme des 
variables globales, accessibles et modifiables directement par toutes 
les proc\'edures et fonctions sans avoir à les passer comme arguments. 

\begin{center}
    {\bf\Large Partie I. Planter le paysage}
\end{center}

Nous d\'efinissons le paysage \`a partir d'une suite de relev\'es de 
d\'enivel\'es stock\'es dans un 
tableau \texttt{deniveles} de nombres flottants (c'est-\`a-dire des nombres \`a
virgule) de taille $n + 1$. 
Le tableau \texttt{deniveles} est suppos\'e \^etre une variable globale : il
n'est pas nécessaire de le passer en paramètre, il accessible depuis toutes
les fonctions.

Le paysage est alors d\'ecrit par une ligne bris\'ee de $n + 1$ points, 
dont le $i$-\`eme point $P_{i}$ est
de coordonn\'ees $(i,h_{i})$ o\`u :
\[
h_{0} = 0.0\text{ et }h_{i} = h_{i-1} + \mathtt{deniveles}[i]\text{ 
pour }i \in \{1, ...,n\}.
\]
Ainsi, la hauteur du $i$-ème point est la hauteur du $(i-1)$-ème point plus la dénivelée stoquée en \texttt{deniveles[i]}.

%: Question 1
\smallbreak\noindent\textbf{Question 1} \'Ecrire une fonction
\texttt{calculHauteurs}($n$) 
qui retourne un tableau  de taille $n + 1$ contenant les hauteurs $h_i$ des
points. 
On suppose désormais que ce résultat est stocké dans une
variable globale \texttt{hauteurs}.

%: Question 2
\smallbreak\noindent\textbf{Question 2} \'Ecrire une fonction
\texttt{calculFenetre}($n$)
qui calcule les hauteurs minimale et maximale
que peut atteindre un point du paysage. Elle calculera également les indices
des points les plus \`a 
gauche de hauteur minimale et maximale. 

On supposera que les résultats sont désormais
stockés dans des variables
globales  
\texttt{hMin} et \texttt{hMax} (pour les hauteurs) et
\texttt{iMin} et 
\texttt{iMax} (pour les indices).

On appelle \textit{distance} au sol de $i$ \`a $j$, la longueur de la 
ligne bris\'ee allant du point $P_{i}$ au 
point~$P_{j}$.

%: Question 3
\smallbreak\noindent\textbf{Question 3} \'Ecrire une fonction \texttt{distanceAuSol}($i, 
j$) qui calcule et renvoie la distance au sol de $P_{i}$
\`a $P_{j}$. On pourra commencer par calculer la distance au sol entre $P_i$
et $P_{i+1}$, à l'aide du théorème de Pythagore. On suppose que $h_i$ est donnée en mètres, de même que les
abscisses $i$ (horizontalement, chaque point est distant %de cents mètres
d'un mètre 
du suivant).

On appelle un \textit{pic} un point $P_{i}$ d'indice $1 \leqslant i < 
n$ tel que $h_{i} > \max(h_{i-1},h_{i+1})$. On appelle
\textit{point remarquable}, les pics et les points des bords gauche
(point $P_{0}$) et droit (point $P_{n}$). On
appelle \textit{bassin} toute partie du paysage allant d'un point 
remarquable au suivant. 

\smallbreak\noindent\textbf{Question 4.1} \'Ecrire une fonction 
\texttt{pointRemarquable}($i,n$) qui détermine si le point $P_i$ est
remarquable, et renvoie un booléen.

%: Question 4
\smallbreak\noindent\textbf{Question 4.2} \'Ecrire une fonction 
\texttt{longueurDuPlusLongBassin}($n$) qui calcule et renvoie la longueur
au sol maximale d'un bassin dans le paysage.

% 2

\begin{center}
    {\bf\Large Partie II. Planter les poteaux}
\end{center}
On souhaite relier le point le plus \`a gauche au point le plus \`a droite
par un fil
t\'el\'egraphique. Pour cela, nous devons choisir \`a quels points parmi les
$(P_{i})_{0\leqslant i\leqslant n}$ planter les
poteaux t\'el\'egraphiques interm\'ediaires. Rappelons que le fil est 
suppos\'e sans poids et tendu et 
qu'il relie donc les sommets de chacun des poteaux en ligne droite. 
Les poteaux sont plant\'es 
verticalement et ont tous une longueur identique $\ell \geqslant 
\Delta$ ($\ell$ et $\Delta$ sont 
des nombres flottants).

La l\'egislation impose que le fil doit rester \`a une distance 
sup\'erieure ou \'egale \`a $\Delta$ (mesur\'ee 
verticalement) au-dessus du sol. Pour tester si un fil tir\'e entre un 
poteau plac\'e au point $P_{i}$ et 
un poteau plac\'e au point $P_{j}$ (avec $j > i$ ou $j < i$)
respecte la l\'egislation, notons

\[ \alpha_{i,k} = \frac{(h_{k}+\Delta)-(h_{i}+\ell)}{k-i}\text{ pour 
}k\neq i,\text{ et }\beta_{i,j} = 
\frac{(h_{j}+\ell)-(h_{i}+\ell)}{j-i}, \]

les pentes des fils tir\'es depuis le poteau en $P_{i}$ jusqu'\`a une 
hauteur $\Delta$ au-dessus du point $P_{k}$
d'une part et jusqu'\`a une hauteur $\ell$ au-dessus du point $P_{j}$
d'autre part (voir la Figure 2).

On admet que le fil tir\'e d'un poteau en $P_{i}$ \`a un poteau en $P_j$
respecte la l\'egislation si et seulement~si :
\[
\beta_{i,j} \geqslant \max\limits_{i < k < j} \alpha_{i,k},\text{ lorsque }
j > i;\text{ et }\beta_{i,j} \leqslant \min\limits_{j < k < i} 
\alpha_{i,k},\text{ lorsque }j < i.
\]
\cad{},
\begin{itemiz}
\item lorsque $j>i$, $\beta_{i,j}$ est plus grand que tous les $\alpha_{i,k}$ lorsque $k$
parcourt $\llbracket i+1,j-1\rrbracket$ 
\item ou bien, lorsque $j<i$, $\beta_{i,j}$ est plus petit que tous les $\alpha_{i,k}$ lorsque $k$
parcourt $\llbracket i+1,j-1\rrbracket$.

\end{itemiz}
	\begin{figure}[!h]
		\centering
	\begin{pspicture}(11,3.3)(0.5,0.5)
	\psset{levelsep=2cm,nodesep=0mm,unit=1cm}
		\psaxes[labels=none,Dx=0.5,Ox=-0.2](5.5,0)
		\rput[t](1,-.3){$i$}
		\rput[t](3,-.3){$k$}
		\rput[t](5,-.3){$j$}
		% ligne de cr\^ete
		\psline[linewidth=1.1pt](0,2.2)(0.5,1.5)(1,2)(1.5,1.6)(2,0.8)(2.5,0.7)
		(3,1)(3.5,0.7)(4,1.1)(4.5,0.3)(5,0.5)(5.5,0.4)
		% ligne de s\'ecurit\'e en pointill\'e
 		\psline[linestyle=dotted](0,2.5)(0.5,1.8)(1,2.3)(1.5,1.9)
		(2,1.1)(2.5,1)(3,1.3)(3.5,1)(4,1.4)(4.5,0.6)(5,0.8)(5.5,0.7)
		% les poteaux
		\psline[linewidth=2pt](1,2)(1,3)
		\psline[linewidth=2pt](5,0.5)(5,1.5)
		% pour Delta
		\psline[arrows=<->](2.5,0.7)(2.5,1)
		\rput[r](2.4,1){$\Delta$}
		% pour les lignes inclin\'ees
		\pcline(1,3)(3,1.3)
		\uput[30]{-30}(2.1,1.8){\footnotesize$\alpha_{i,k}$}
		\pcline[arrows<->](1,3)(4,1.4)
		\uput[30]{-25}(2.9,1.8){\footnotesize$\max\alpha_{i,k}$}
		\uput[30]{-25}(2.8,1.5){\tiny$1\!<\!k\!<\!j$}
		\pcline(1,3)(5,1.5)
		\uput[30]{-20}(3.7,1.9){\footnotesize$\beta_{i,j}$}
		\qdisk(3,1.3){1pt}
		\qdisk(4,1.4){1pt}
		
	\end{pspicture}
	\caption{Condition sur les pentes ($\beta_{i,j}$, les $\alpha_{i,k}$) pour pouvoir tirer un fil.}
	\label{fig2}
	\end{figure}

% i k j
% FIGURE 2 - Condition sur les pentes pour pouvoir tirer un fil.


%: Question 5
\smallbreak\noindent\textbf{Question 5} En utilisant cette m\'ethode, \'ecrire une fonction 
\texttt{estDeltaAuDessusDuSol}($i,j,\ell,delta$) qui 
renvoie \texttt{True} si un fil tir\'e entre les sommets d'un poteau
plac\'e au point $P_{i}$ et d'un poteau plac\'e
au point $P_{j}$ respecte la l\'egislation, et renvoie \texttt{False}
dans le cas contraire.

Consid\'erons une premi\`ere strat\'egie, dite \textit{algorithme glouton}
en avant. Le premier poteau est
plant\'e en $P_{0}$. Pour calculer l'emplacement du prochain poteau,
on part du dernier poteau plant\'e
et on avance (\`a droite) avec le fil tendu tant que la l\'egislation est 
respect\'ee (et que $P_{n}$ n'est pas 
atteint). Un nouveau poteau est alors plant\'e, et on recommence 
jusqu'\`a ce que $P_{n}$ soit atteint. 

La figure 3 illustre la solution produite par cet algorithme.
% 3

% ._'--'-"""j,f"' o W ' l'
	\begin{figure}[!h]
		\centering
	\begin{pspicture}(11,3.3)(0.5,0.5)
	\psset{levelsep=2cm,nodesep=0mm,unit=7mm}
		\psaxes[labels=none](18,0)
		\rput[t](0,-.3){0}
		\rput[b](18,.3){$n$}
		% ligne de cr\^ete
		\psline[linewidth=1.5pt](0,0)(1,1)(2,-1.4)(3,-.3)(4,2.1)(5,3)
		(6,1.3)(7,1.3)(8,0.6)(9,2.7)(10,3.5)(11,2.3)(12,2.0)(13,1.6)
		(14,3)(15,1)(16,0.7)(17,-0.1)(18,-2)
		% ligne de s\'ecurit\'e en pointill\'e
		\psline[linestyle=dotted](0,0.4)(1,1.4)(2,-1)(3,0.1)(4,2.5)
		(5,3.4)(6,1.7)(7,1.7)(8,1)(9,3.1)(10,3.9)(11,2.7)(12,2.4)
		(13,2)(14,3.4)(15,1.4)(16,1.1)(17,0.3)(18,-1.6)
		% les poteaux
		\psline[linewidth=2pt](0,0)(0,1.8)
		\psline[linewidth=2pt](1,1)(1,2.8)
		\psline[linewidth=2pt](5,3)(5,4.7)
		\psline[linewidth=2pt](14,3)(14,4.7)
		\psline[linewidth=2pt](18,-2)(18,-.2)
		\psline[linewidth=2pt,linestyle=dashed](2,-1.4)(2,.4)
		\psline[linestyle=dashed,dash=1pt 3pt 5pt 3pt](0,1.8)(2,.4)
		\psline[linewidth=2pt,linestyle=dashed](6,1.3)(6,3.1)
		\psline[linestyle=dashed,dash=1pt 3pt 5pt 3pt](1,2.8)(6,3.3)
		\psline[linewidth=2pt,linestyle=dashed](15,1)(15,2.8)
		\psline[linestyle=dashed,dash=1pt 3pt 5pt 
		3pt](5,4.7)(15,2.8)
		% la ligne \'electrique
		\psline(0,1.8)(1,2.8)(5,4.7)(14,4.7)(18,-.2)
		% pour Delta
		\psline[arrows=<->](11,2.3)(11,2.7)
		\rput[l](11.2,2.5){$\Delta$}
		
	\end{pspicture}
	\caption{Solution produite par l'algorithme glouton en avant.
	Les poteaux et les fils en pointill\'es sont ceux violant la l\'egislation.}
	\label{fig3}
	\end{figure}
% FIGURE 3 - Solution produite par l'algorithme glouton en avant. Les 
% poteaux et les fils en 
% pointill\'es sont ceux violant la l\'egislation.

%: Question 6
\smallbreak\noindent\textbf{Question 6} \'Ecrire une fonction
\texttt{placementGloutonEnAvant}($n,\ell,delta)$ qui calcule la disposition
des poteaux selon l'algorithme ci-dessus. La solution sera stock\'ee 
dans un tableau \texttt{poteaux} de la fa\c{c}on suivante :
\begin{itemize}
    \item  la case \texttt{poteaux}[0] contiendra le nombre de poteaux utilis\'es;

    \item  la case \texttt{poteaux}[$t$], pour $t \geqslant 1$, 
    contiendra l'indice $i$ indiquant que le $t$-\`eme poteau, s'il 
    existe, est plant\'e en $P_{i}$
\end{itemize}
La figure 3 correspond au tableau \texttt{poteaux} suivant :
\texttt{[5,1,5,14,18]}.

Le nombre de poteaux est stocké dans \texttt{poteaux[0]}, qui vaut donc ici
$5$. Le premier poteau est toujours en $0$ : il n'est pas noté.

%: Question 7
\smallbreak\noindent\textbf{Question 7} Donner une majoration de la complexit\'e du temps 
de calcul de votre algorithme 
en fonction de $n$. Justifier qu'on peut se contenter du calcul de 
$O(n)$ pentes pour impl\'ementer 
l'algorithme glouton en avant. Expliquer succinctement comment 
modifier votre fonction (si 
n\'ecessaire) pour obtenir une complexit\'e en $O(n)$. \textit{Aucune 
impl\'ementation n'est demand\'ee dans 
cette question.}

% L'algorithme glouton en avant a tendance \`a placer beaucoup trop de 
% poteaux, en particulier dans les vall\'ees alors qu'il suffirait de 
% relier les deux extr\'emit\'es par un unique fil. Nous 
% consid\'erons donc une alternative, dite glouton au plus loin, qui 
% consiste \`a planter le prochain 
% poteau le plus \`a droite possible de la position courante. Le premier 
% poteau est toujours plant\'e 
% en $P_{0}$.

% La figure \ref{fig4} illustre la solution produite par cet algorithme sur le 
% m\^eme paysage que celui de la figure \ref{fig3}.

% 	\begin{figure}[!h]
% 		\centering
% 	\begin{pspicture}(11,3.3)(0.5,0.5)
% 	\psset{levelsep=2cm,nodesep=0mm,unit=7mm}
% 		\psaxes[labels=none](18,0)
% 		\rput[t](0,-.3){0}
% 		\rput[b](18,.3){$n$}
% 		% ligne de cr\^ete
% 		\psline[linewidth=1.5pt](0,0)(1,1)(2,-1.4)(3,-.3)(4,2.1)(5,3)
% 		(6,1.3)(7,1.3)(8,0.6)(9,2.7)(10,3.5)(11,2.3)(12,2.0)(13,1.6)
% 		(14,3)(15,1)(16,0.7)(17,-0.1)(18,-2)
% 		% ligne de s\'ecurit\'e en pointill\'e
% 		\psline[linestyle=dotted](0,0.4)(1,1.4)(2,-1)(3,0.1)(4,2.5)
% 		(5,3.4)(6,1.7)(7,1.7)(8,1)(9,3.1)(10,3.9)(11,2.7)(12,2.4)
% 		(13,2)(14,3.4)(15,1.4)(16,1.1)(17,0.3)(18,-1.6)
% 		% les poteaux
% 		\psline[linewidth=2pt](0,0)(0,1.8)
% 		\psline[linewidth=2pt](10,3.5)(10,5.3)
% 		\psline[linewidth=2pt](16,0.7)(16,2.5)
% 		\psline[linewidth=2pt](18,-2)(18,-.2)
% 		\psline[linewidth=2pt,linestyle=dashed](2,-1.4)(2,.4)
% 		\psline[linestyle=dashed,dash=1pt 3pt 5pt 3pt](0,1.8)(2,.4)
% 		\psline[linewidth=1.5pt,linestyle=dashed](11,2.3)(11,4.1)
% 		\psline[linestyle=dashed,dash=1pt 3pt 5pt 
% 		3pt](0,1.8)(11,4.1)\psline[linewidth=1.5pt,linestyle=dashed](17,-0.1)(17,1.7)
% 		\psline[linestyle=dashed,dash=1pt 3pt 5pt 3pt](10,5.3)(17,1.7)
% 		% la ligne \'electrique
% 		\psline(0,1.8)(10,5.3)(16,2.5)(18,-.2)
% 		% pour Delta
% 		\psline[arrows=<->](11,2.3)(11,2.7)
% 		\rput[l](11.2,2.5){$\Delta$}
		
% 	\end{pspicture}
% 	\caption{Solution produite par l'algorithme glouton au plus loin. 
% Les poteaux et fils en pointill\'es sont ceux violant la l\'egislation.}
% 	\label{fig4}
% 	\end{figure}
% % ,\fg \fg '.'I""\"I\"I\"A/  0  
% % FIGURE 4 - Solution produite par Palgorithme glouton au plus loin. 
% % Les poteaux et fils en pointill\'es sont ceux violant la l\'egislation.
% % 4


% %: Question 8
% \smallbreak\noindent\textbf{Question 8} \'Ecrire une fonction
% \texttt{placementGloutonAuPlusLoin}($n,\ell,\Delta$) qui calcule la disposition
% des poteaux selon l'algorithme ci-dessus. La solution sera stock\'ee 
% dans un tableau global \texttt{poteaux} de la fa\c{c}on suivante :
% \begin{itemize}
% \item la case \texttt{poteaux}[0] contiendra le nombre de poteaux utilis\'es;
% \item la case \texttt{poteaux}[$t$], pour $t \geqslant 1$, contiendra
% l'indice $i$ indiquant que le $t$-\`eme poteau, s'il
% existe, est plant\'e en $P_{i}$. 
% \end{itemize}

% \begin{center}
%     {\bf\Large Partie III. Minimiser la longueur du fil}
% \end{center}

% L'objectif est maintenant de calculer un placement optimal des 
% poteaux \textbf{en terme de longueur totale du fil} (le nombre de poteaux 
% pouvant \^etre maintenant arbitraire). Un tableau  
% \texttt{optL} peut \^etre calcul\'e de proche en proche tel que 
% \texttt{optL}[$i$] d\'esigne la longueur minimale de fil \`a
% utiliser si l'on souhaitait relier le point $P_{0}$ au point $P_{i}$.

% %: Question 9
% \smallbreak\noindent\textbf{Question 9} Soit $L_{i,j}$ la longueur du segment d'extr\'emit\'es
% $P_{i}$ et $P_{j}$.

% Montrer que le tableau \texttt{optL} v\'erifie : \texttt{optL}$[0] = 0$,
% et pour $1 \leqslant i \leqslant n$,
% \[
% \mathtt{optL}[i] = \min\{L_{i,j} + \mathtt{optL}[j],\text{ o\`u }
% 0 \leqslant  j < i\text{ et il est possible de tirer un fil de 
% }P_{j}\text{ \`a }P_{i}\}.
% \]
% La case \texttt{optL}[$n$] contient alors la longueur minimale
% de fil pour relier le bord gauche au bord droit.

% %: Question 10
% \smallbreak\noindent\textbf{Question 10} \'Ecrire une fonction 
% \texttt{longueurMinimale}($n,\ell,\Delta)$ qui renvoie la longueur minimale de
% fil pour relier le bord gauche au bord droit, en respectant la l\'egislation.

% %: Question 11
% \smallbreak\noindent\textbf{Question 11} Modifier votre fonction
% \texttt{longueurMinimale}($n,\ell,\Delta)$ pour qu'elle remplisse
% \'ega\-le\-ment un tableau \texttt{precOptL} de taille $n + 1$, o\`u 
% \texttt{precOptL}[$i$] contient l'indice du poteau
% pr\'ec\'edant le poteau plac\'e en $P_{i}$ dans une solution de longueur 
% minimale reliant $P_{0}$ \`a $P_{i}$. (Par convention, 
% \texttt{precOptL}[0] = -1.) 

% %: Question 12
% \smallbreak\noindent\textbf{Question 12} \'Ecrire une fonction qui produit un placement 
% des poteaux minimisant la longueur du fil de $P_{0}$ \`a $P_{n}$ \`a 
% partir du tableau \texttt{precOptL}. La solution sera stock\'ee dans un 
% tableau global \texttt{poteaux} de la fa\c{c}on suivante :
% \begin{itemize}
% \item la case \texttt{poteaux}[0] contiendra le nombre de poteaux utilis\'es;
% \item la case \texttt{poteaux}[t], pour $t \geqslant 1$, contiendra
% l'indice $i$ indiquant que le $t$-\`eme poteau, s'il existe, est plant\'e 
% en $P_{i}$.
% \end{itemize}
% Quelle est la complexit\'e de votre fonction en fonction de $n$?
% % >l< >|<
% % *
% % 5



% \vskip 1cm
% \begin{center}
%     *\quad *
    
%     *
% \end{center}


\end{document}
