\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}
\newcommand{\intervalle}[2]{\mathopen\llbracket#1,#2\mathclose\rrbracket}
\newcommand{\vabs}[1]{\left | #1 \right |}
\usepackage{listings}
\lstset{language=python}

\lstset{moredelim=[is][\ttfamily]{(*}{*)},morecomment=[il]{\#}}
% \lstdefinestyle{Maple}{language=Maple,style=numbers,firstline=1}
\lstdefinestyle{numbers}
{numbers=left, stepnumber=0, numberstyle=small, numbersep=10pt}
%\lstdefinestyle{nonumbers}
%{numbers=none}
%:
\lstset{morekeywords={proc,return,end,local, global,
for,from,to,if,then,elif,else,integer,
nops,convert,printf,list_length,vect_length,int_of_char,do,od,while,
and, array, fi, or,
one,two,three,four,five,six,seven,eight,
nine,ten,eleven,twelve,o,clock,rock,around,the,tonight,mod,quo,rem},
morecomment=[s][\color{red}]{(*+}{*)},
morecomment=[s][\color{red}]{/*-}{*/}}
\lstset{% general command to set parameter(s)
basicstyle=\small, % print whole listing small
keywordstyle=\color{black}\bfseries,%\underbar,
% underlined bold black keywords
identifierstyle=, % nothing happens
commentstyle=\color{white}, % white comments
stringstyle=\ttfamily, % typewriter type for strings
showstringspaces=false} % no special string spaces

\lstset{numbers=left, numberstyle=\tiny, stepnumber=1, numbersep=10pt}
\lstset{extendedchars=true} 
\lstset{escapeinside={(*@}{@*)}}
%%% 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{\LeTitrec}[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}%
\fbox{Correction}%
   \end{center}%
%\\\bigskip%
\inter_exo%
\vspace{1cm}}%
% 1 = numero du sujet
% 2 = date

 \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}
\LeTitrec{\NomChapitre}{Jeudi 15 mai 2014}                                     

% TODO : inclure via listing

\begin{exo}[E3A 2013]
\begin{enumerate}
\item Deux fonctions possibles en $O(N^2)$ :
\begin{lstlisting}[numbers=left]
def listeSommesPartielles1(L):
    return [sum(L[:k+1]) for k in range(len(L))]
\end{lstlisting}

ou en $O(N)$ (donc mieux) :
\begin{lstlisting}[numbers=left]
def listeSommesPartielles2(L):
    if len(L)==0:
        return []
    resultat=[L[0]]
    for k in range(1,len(L)):
        resultat.append(resultat[k-1]+L[k])
    return resultat
\end{lstlisting}
\item On utilise la fonction \texttt{max} :
\begin{lstlisting}[numbers=left]
def listeSommesPartielles1(L):
    return [sum(L[:k+1]) for k in range(len(L))]
\end{lstlisting}

ou on la recode (attention, \texttt{max} est un mot réservé du langage, ne pas l'utiliser comme nom de variable) :
\begin{lstlisting}[numbers=left]
def maxSommesPartiellesMain(L):
    if len(L)==0:
        return 'Erreur'
    SP=listeSommesPartielles2(L)
    maximum=SP[0]
    for element in SP[1:]:
        if element > maximum:
            maximum = element
    return maximum
\end{lstlisting}
\item Cet algorithme ne prétend pas être optimal.

On considère les listes de la forme \texttt{L[k1:N]} lorsque $k_1\in \llbracket 1,N \rrbracket$. 
Pour chacune de ces listes, on cherche la somme partielle maximale (donc $\displaystyle \sum_{i=k_1}^k \ell_i$ maximale lorsque $k$ bouge).
Puis on stocke les $N$ résultats dans une liste, dont on prend le maximum.
\newpage
~\\
\begin{lstlisting}[numbers=left]
def maxSommes(L):
    if len(L)==0:
        return 'Erreur'
    return max([maxSommesPartielles(L[k1:]) for k1 in range(len(L))])
\end{lstlisting}
\end{enumerate}
\end{exo}

\begin{exo}[Poteaux t\'el\'egraphiques -- corrigé UPS]%X 2013
\end{exo}
{\bf\Large Partie I. Planter le paysage}

%: Question 1
\textbf{Question 1.} Pour créer et remplir le tableau \texttt{hauteurs}, on 
utilise la propri\'et\'e $h_{0}=0$ ce qui se traduit par
\verb|hauteurs = [0.]| en ligne \ref{pg1lg3} et la propri\'et\'e $h_{i} = h_{i-1} + 
\mathtt{deniveles}[i]$ pour $i \in \intervalle{1}{n}$ qui se traduit 
par la boucle des lignes \ref{pg1lg4} \`a \ref{pg1lg5}. 
\begin{lstlisting}[numbers=left]
def calculHauteurs(n):
    hauteurs = [0.] (*@\label{pg1lg3}@*)
    for i in range(1,n+1): (*@\label{pg1lg4}@*)
        hauteurs.append(hauteurs[i-1] + deniveles[i]) (*@\label{pg1lg5}@*)
    return hauteurs
\end{lstlisting}

On pouvait aussi utiliser la fonction de l'exercice 1.

\smallbreak
\noindent
\textbf{Question 2.} On suppose le tableau \texttt{hauteurs} rempli 
par l'appel de la fonction \texttt{calculHauteurs}. On balaye le 
tableau des hauteurs pour trouver les hauteurs minimales et maximales 
ainsi que leurs indices. On commence par supposer que ces points 
sont en position 0 et donc que les altitudes correspondantes sont 
nulles (lignes 3 \`a 6).
Dans la boucle des lignes \ref{pg2lg7} \`a \ref{pg2lg12}, on parcourt le tableau des 
hauteurs. Si on trouve un point strictement plus bas que les pr\'ec\'edents, on 
enregistre sa hauteur et sa position dans les variables globales 
\texttt{hMin} et \texttt{iMin} (ligne \ref{pg2lg10}) et si on trouve un point 
strictement plus haut que les pr\'ec\'edents,  on 
enregistre sa hauteur et sa position dans les variables globales 
\texttt{hMax} et \texttt{iMax} (ligne \ref{pg2lg12}).
\begin{lstlisting}[numbers=left]
def calculFenetre(n):
    global hauteurs
    hMin = hauteurs[0]
    hMax = hauteurs[0]
    iMin = 0
    iMax = 0
    for i in range(1,n+1): (*@\label{pg2lg7}@*)
        hauteur = hauteurs[i]
        if hauteur < hMin:
            hMin = hauteur; iMin = i (*@\label{pg2lg10}@*)
        if hauteur > hMax:
            hMax = hauteur; iMax = i (*@\label{pg2lg12}@*)
    return (hMin, hMax, iMin, iMax)
\end{lstlisting}

%\eject
%: Question 3
\quad\smallbreak

\noindent
\textbf{Question 3} : La fonction \texttt{distanceAuSol} calcule la 
longueur de la ligne bris\'ee du point $P_{i}$ au point $P_{j}$. On 
applique le th\'eor\`eme de Pythagore pour calculer la distance
du point $P_{k-1}$ au 
point $P_{k}$, cette distance \'etant \'egale \`a
$\sqrt{1^{2}+ \mathtt{denivele}[k]^{2}}$. Les~lignes \ref{pg3lg4} \`a 
\ref{pg3lg7} permettent 
d'initialiser les variables $I$ et $J$ pour parcourir les points du
paysage en ordre croissant dans la boucle des lignes \ref{pg3lg8} \`a \ref{pg3lg9}.
\begin{lstlisting}[numbers=left]
def distanceAuSol(i,j):
    global deniveles
    dist = 0
    if i <= j : (*@\label{pg3lg4}@*)
        I = i; J = j
    else :
        I = j; J = i (*@\label{pg3lg7}@*)
    for k in range(I+1,J+1) : (*@\label{pg3lg8}@*)
       dist = dist + (1**2+deniveles[k]**2)**(1/2.) (*@\label{pg3lg9}@*)
    return dist 
\end{lstlisting}

%: Question 4
\smallbreak
\noindent
\textbf{Question 4.1} : Dans la proc\'edure \texttt{pointRemarquable}($i,n$) (où l'on avait besoin de $n$...), 
on commence par tester si on est au bord (ligne  \ref{pg4.1lg4}). 
Sinon, on teste ligne \ref{pg4.1lg6} si les deux points $P_{i-1}$ et $P_{i+1}$ qui entourent $P_i$ sont plus bas que $P_i$.
\begin{lstlisting}[numbers=left]
def pointRemarquable(i,n):
    global hauteurs
    res = False
    if (i == 0) or (i == n): (*@\label{pg4.1lg4}@*)
        res = True
    elif hauteurs[i]>max(hauteurs[i-1],hauteurs[i+1]): (*@\label{pg4.1lg6}@*)
        res = True
    return res
\end{lstlisting}
On pouvait aussi tout tester d'une seule phrase logique, grace à l'évaluation paresseuse :
\begin{lstlisting}[numbers=left]
def pointRemarquable2(i,n):
    global hauteurs
    return (i == 0) or (i == n) or (hauteurs[i] > max(hauteurs[i-1],hauteurs[i+1]))
\end{lstlisting}
Si $i=0$ ou $i=n$, python ne va pas plus loin (à cause du \texttt{or}), donc la formule appelant \texttt{i-1} et \texttt{i+1} ne provoque pas une erreur.

\smallbreak
\noindent
\textbf{Question 4.2} : Dans la proc\'edure 
\texttt{longueurDuPlusLongBassin}, on parcourt le tableau gr\^ace \`a la boucle des 
lignes \ref{pg4lg5} \`a \ref{pg4lg9}.
\`A la ligne \ref{pg4lg6}, on regarde si le point $P_{i}$ est un 
pic. Si~c'est le cas, on calcule la distance au sol entre $P_{i}$ et 
le dernier point remarquable. Si~cette distance est sup\'erieure \`a la 
plus longue distance de bassin de la partie \'etudi\'ee, on actualise la 
variable \texttt{longueurBassinMax} (ligne \ref{pg4lg8}).
Dans tous les cas, on 
modifie la variable \texttt{debut} qui rep\`ere le premier point du 
bassin \`a l'\'etude (ligne \ref{pg4lg9}).  Les lignes \ref{pg4lg10}
\`a \ref{pg4lg11} permettent 
d'\'etudier le dernier bassin situ\'e, entre le dernier pic et le 
point remarquable de droite.
\begin{lstlisting}[numbers=left]
def longueurDuPlusLongBassin(n):
  global hauteurs
  debut = 0
  longueurBassinMax = 0
  for i in range(1,n-1): (*@\label{pg4lg5}@*)
      if hauteurs[i] > max(hauteurs[i-1], hauteurs[i+1]): (*@\label{pg4lg6}@*)
           longueur = distanceAuSol(debut,i)
           if longueur > longueurBassinMax:
               longueurBassinMax = longueur (*@\label{pg4lg8}@*)
           debut = i (*@\label{pg4lg9}@*)
  longueur = distanceAuSol(debut,n)
  if longueur > longueurBassinMax: (*@\label{pg4lg10}@*)
      longueurBassinMax = longueur (*@\label{pg4lg11}@*)
  return longueurBassinMax
\end{lstlisting}

{\bf \Large Partie II. Planter les poteaux}

% Question 5
\smallbreak
\noindent
\textbf{Question 5} :   On initialise \texttt{beta} avec la valeur 
$\beta_{i,j}$ de l'\'enonc\'e (on a simplifi\'e les \og$\ell$\fg{ }dans 
l'expression de l'\'enonc\'e). Puis, gr\^ace \`a la boucle des lignes
\ref{pg5lg6} \`a \ref{pg5lg8}
(ou la boucle des lignes \ref{pg5lg10} \`a \ref{pg5lg12}), 
on parcourt le tableau des hauteurs. Pour chaque $k$ de 
l'intervalle $\intervalle{i+1}{j-1}$, on calcule 
$\alpha_{i,k}$ que l'on met dans la variable \texttt{alpha}.
Le branchement conditionnel de la ligne \ref{pg5lg5} permet de diff\'erencier
les cas $i\leqslant j$ et $i>j$.
En 
sortie de boucle, la variable \texttt{res} vaut \texttt{true} si et 
seulement si $i=j$ ou bien
$\beta_{i,j} \geqslant \max\limits_{i < k < j} \alpha_{i,k},\text{ lorsque }
j > i;\text{ ou bien }\beta_{i,j} \leqslant \min\limits_{j < k < i} 
\alpha_{i,k},\text{ lorsque }j < i$.
\begin{lstlisting}[numbers=left]
def estDeltaAuDessusDuSol(i,j,l,delta):
   global hauteurs
   res = True
   beta = (hauteurs[j]-hauteurs[i])/(j-i) (*@\label{pg5lg4}@*)
   if j>i : (*@\label{pg5lg5}@*)
       for k in range(i+1,j): (*@\label{pg5lg6}@*)
           alpha = (hauteurs[k]+delta-hauteurs[i]-l)/float(k-i);
           res = res and (beta >= alpha) (*@\label{pg5lg8}@*)
   else:
       for k in range(j+1,i): (*@\label{pg5lg10}@*)
           alpha = (hauteurs[k]+delta-hauteurs[i]-l)/float(k-i);
           res = res and (beta <= alpha) (*@\label{pg5lg12}@*)
   return res (*@\label{pg5lg13}@*)
\end{lstlisting}

% Question 6
\noindent
\textbf{Question 6} : \`A la ligne \ref{pg6lg4}, on \og plante\fg{} un premier 
poteau en $P_{0}$. La variable \texttt{DernierPoteauPlante} garde en m\'emoire la 
position du dernier poteau \og plant\'e\fg{}. La~boucle des lignes 
\ref{pg6lg6} \`a 
\ref{pg6lg10} permet de parcourir tous les points diff\'erents des extr\'emit\'es. Si 
le segment de droite reliant le dernier poteau plant\'e au poteau en $P_{k}$ ne 
respecte pas
la l\'egislation, c'est que le point $P_{k-1}$ est le dernier 
point pour lequel la l\'egislation est satisfaite.
On \og plante\fg{} un poteau au point $P_{k-1}$  
en modifiant en cons\'equence le tableau \texttt{poteaux}
(ligne \ref{pg6lg10}) et on actualise la variable \texttt{DernierPoteauPlante} 
(ligne \ref{pg6lg9}) et la 
variable \texttt{nb\_poteaux} qui compte le nombre de poteaux 
plant\'es (ligne \ref{pg6lg8}). Les~lignes \ref{pg6lg11} \`a \ref{pg6lg13}, 
traite le cas du poteau plant\'e au point~$P_{n}$.%\eject
\begin{lstlisting}[numbers=left]
def placementGloutonEnAvant(n,l,delta):
   global poteaux
   nb_poteaux = 1
   poteaux[1]= 0 (*@\label{pg6lg4}@*)
   DernierPoteauPlante = 0
   for k in range(1,n+1): (*@\label{pg6lg6}@*)
       if not(estDeltaAuDessusDuSol(DernierPoteauPlante,k,l,delta)):
           nb_poteaux = nb_poteaux+1 (*@\label{pg6lg8}@*)
           DernierPoteauPlante = k - 1 (*@\label{pg6lg9}@*)
           poteaux[nb_poteaux] = DernierPoteauPlante (*@\label{pg6lg10}@*)
   nb_poteaux = nb_poteaux + 1 (*@\label{pg6lg11}@*)
   poteaux[0] = nb_poteaux
   poteaux[nb_poteaux] = n (*@\label{pg6lg13}@*)
   return None
\end{lstlisting}

(On pouvait aussi écrire une fonction qui retourne une liste (locale) \texttt{poteaux}).

%\eject
% Question 7
\smallbreak
\noindent
\textbf{Question 7} : La complexit\'e de 
\verb|estDeltaAuDessusDuSol(pos,k,l,delta)| est en $O(k-pos+1)$ donc 
au maximal en $O(k)$. La complexit\'e de la boucle des lignes
\ref{pg6lg6} \`a \ref{pg6lg10}
est donc en $O(\sum_{k=1}^{n-1} k)= O(n^{2})$. Les autres op\'erations 
se faisant \`a co\^ut constant, \begin{center}
\fbox{la complexit\'e de la fonction 
\texttt{placementGloutonEnAvant} est quadratique (en $O(n^{2})$)}
\end{center}

La complexit\'e quadratique vient de l'appel de la fonction 
\texttt{estDeltaAuDessusDuSol} dans la boucle des lignes \ref{pg6lg6}
\`a \ref{pg6lg10}. 
Pour am\'eliorer l'algorithme, on peut se contenter de ne calculer 
qu'une seule fois les pentes que l'on peut stocker dans un tableau ou 
que l'on calcule une seule fois \`a chaque passage dans la boucle.
Il suffit de  garder en m\'emoire le maximum 
des pentes entre les points $P_{DernierPoteauPlante}$ et $P_{k}$.
Il~faudrait donc 
modifier la boucle des lignes \ref{pg6lg6} \`a \ref{pg6lg10} en supprimant l'appel de 
la fonction \texttt{estDeltaAuDessusDuSol} et introduire une variable 
\texttt{MaxPente} qui m\'emorise la pente maximale entre le dernier 
poteau plant\'e et la position courante \'etudi\'ee (d'indice 
$k$).

\end{document}
