\documentclass[documents]{monexamen}
%\documentclass[documents]{monexamen}
%\setlength{\parindent}{0pt}

\usepackage{graphicx}
\usepackage{a4wide,amssymb,frenchle}
\usepackage[latin1]{inputenc} %% entr\'ee 8 bits iso-latin1
\usepackage[T1]{fontenc}      %% encodage 8 bits des fontes utilis\'ees

\newcommand{\f}{\ensuremath{\uparrow}}


\begin{document}

\entete{\'{E}cole Sup\'{e}rieure en Sciences
Informatiques}
{ }{04}{05}{Math\'{e}matiques  Discr\`{e}tes\\ du 13 Janvier 2005}{Dur\'{e}e : 1 heure}% \
%{Probabilit\'{e}s}{02}{03}{du 1er Avril  2003 }
\\
\addtolength{\evensidemargin}{-1cm}
\addtolength{\oddsidemargin}{-1cm}
\reversemarginpar{ 

\begin{tabular}{l|l}
1 &  \ \  \\\hline
2 &   \\\hline
3 &   \\\hline
4 &   \\\hline
5  &   \\

\end{tabular}
}
\\





\section {}
Que signifie la notation $f(n)= O(n)$ ?

Que signifie la notation $ f(n)= \Theta (n)$ ?

\begin{copie}
\lignes{8}
\end{copie}
\section{}

\begin{copie}
Quelles sont toutes les solutions de l'équation $u_n=5u_{n-1 }-6u_{n-2}$ ?
\lignes{16}
\end{copie}

\section {}
\begin {itemize}

\item Question 1 : Montrer par induction que la méthode sum suivante retourne $\sum_{i=min}^{i=max} A [i]$ .
\item Question 2 : Déterminer la complexité de cette méthode.
\end{itemize}
\begin{verbatim}

//On suppose que  0  <= min  <= max < A.length
public static int sum(int[] A, int min, int max){
	int mid;
	if(min == max) {
		return A[min]; 
	}
	if (max-min == 1) {
		return A[min] + A[max];
	}
 	// dans les autres cas
	mid = (min + max)/2; 
	return sum(A,min,mid) + sum(A,mid+1,max); 
	
}
\end{verbatim}



\begin{copie}

\lignes{22}
\end{copie}

\section {}
Donner l'ordre de grandeur des solutions des équations suivantes:

$u_n=5u_{n-1 }-6u_{n-2}+3^n, u_0=0$

$v_n=5v_{n-1 }-6_{n-2}+5^n, u_0=0$
\begin{copie}
\lignes{20}
\end{copie}

\section{}
On considère une variante des tours de Hanoï avec trois piquets A,B,C et n disques.
\begin{itemize}
\item
	les n disques sont de tailles différentes
\item initialement les n disques sont rangés sur le piquet A, du plus grand en bas, au plus petit en haut
\item on désire amener les n disques dans le même ordre sur le piquet C
\item on ne peut déplacer qu'un seul disque à la fois
\item on ne peut pas poser un disque sur un disque de taille inférieure
\item	tous les mouvements de disques doivent se faire via le piquet central (un déplacement direct de A vers C ou de C vers A est interdit)
\end{itemize}
Déterminer et prouver l'équation de récurrence correspondant au nombre minimum de déplacements de disques.

\begin{copie}
\lignes{20}
\end{copie}

\end{document}