\documentclass[10pt,a4paper]{article}
\usepackage{ifxetex}
\usepackage[T1]{fontenc}
\usepackage[mathletters]{ucs}
\usepackage[utf8x]{inputenc}
\usepackage[french]{babel}
\usepackage{geometry}
\usepackage[enonce]{exam}
%\usepackage[correction]{exam}

\usepackage{epsf,amsmath,amssymb,graphicx,realboxes}
\newcommand\scr{}
\usepackage[boldsans]{ccfonts}
\usepackage[mathcal,mathbf]{euler}
%\usepackage{preambuleTrm}


\usepackage{tikz}
\usetikzlibrary{automata,fit,trees,matrix,arrows,decorations.pathmorphing,shapes.arrows,chains,positioning,intersections,backgrounds,calc,through,mindmap}

\usepackage{tkz-graph,tikz-uml}
\input{patch-tkz-graph}
\usepackage{tikz-qtree}
%\usepackage{circuitikz}
%\usepackage{Karnaugh}
%\usepackage[autolanguage]{numprint}

\newcommand{\ve}[1]{\overrightarrow{#1}}

\usepackage{algo}

\renewcommand{\algocommentfont}{\small\ttfamily\itshape}


\usepackage{minted}
\newminted{python}{linenos,breaklines,breakindent=1cm,frame=lines,framesep=2mm,fontsize=\small,fontfamily=txtt}


\newcommand\nor{\downarrow}
\newcommand\nand{\uparrow}


\graphicspath{{/home/moi/IUT/Figures/}{/home/moi/VISA_III/figures_visa/}{/home/moi/Lycee/TDmaple/2006_7/}{/home/moi/Figures/Arbres_Graphes/}{/home/moi/Figures/FigSTI/}{/home/moi/Figures/FigMaple/}{/home/moi/Photos/Maths/}{/home/moi/Photos/Tehessin/}{/home/moi/Figures/FigSTI/}{/home/moi/Figures/FigSeconde/}{/home/moi/Lycee/Informatique/XCAS/2008_9/}{/home/moi/Lycee/TDmaple/2008_9/}{/home/moi/IUT/Thierry/Conversions/}{/home/moi/Photos/informathix/}{/home/moi/Lycee/Informatique/PafAlgo/}{/home/moi/Figures/figuresAlice/}{/home/moi/Figures/FigSeconde/}{/home/moi/Biocam/robot/}{/home/moi/Biocam/CoursIni3d/}{/home/moi/Biocam/central/figures/}{/home/moi/Biocam/central/}{/home/moi/IUT/INFO2/Images/}{/home/moi/IUT/INFO2/2011_12/graphes/}{/home/moi/IUT/INFO1/CM1/}{/home/moi/Figures/figuresTS/}{/home/moi/Photos/Tehessin/}{/home/moi/Figures/FigSTI/}{/home/moi/Alice/figures3/}{/home/moi/Alice/figures3/newcourbes/}{/home/moi/Alice/figures/}{/home/moi/Figures/figuresAlice/}{/home/moi/Photos/Maths/}{/home/moi/Lycee/TS/}{/home/moi/Lycee/TS/2009_10/}{/home/moi/Figures/FigMaple/}{/home/moi/Figures/figuresTS/newcourbes/}{/home/moi/Figures/FigEspace/}{/home/moi/PROG/HASKELL/FLOAT/}} 


\newcommand{\Fonc}[5]{#1~\colon~\begin{array}{rll} #2 &\to &#3\\ #4& \mapsto &#5 \end{array}} % fonction d'une autre variable
\newcommand{\illt}[4]{\begin{minipage}[t]{#3\linewidth}\vspace{0cm}#1\end{minipage}\hspace{0.5cm}\begin{minipage}[t]{#4\linewidth}\vspace{-0.25cm}
\hspace{5.5cm} \begin{flushright}\includegraphics[width=\linewidth]{#2}\end{flushright}\end{minipage}}

\newcommand{\ch}{\operatorname{ch}}
\newcommand{\sh}{\operatorname{sh}}
\newcommand{\E}{{\operatorname e}}

\usepackage{listing}

\lstset{
 language=python,
        escapeinside={(*@}{@*)},
        %numbers=left,
        basicstyle={\bfseries\ttfamily\color{black!60!blue}},
        commentstyle={\small\itshape\color{pink!60!black}},
        keywordstyle={\ttfamily\bfseries\fontfamily{ul9}\selectfont\color{black!30!blue}},
        stringstyle={\small\ttfamily\color{gray!50!black}\itshape},
        breaklines=true,
        breakatwhitespace=true,
        showtabs=False,
        showspaces=False,
        showstringspaces=False,
        extendedchars=true,
        %aboveskip=1em,
        %belowskip=1em,
        rulecolor=\color{gray},
        %rulesepcolor=\color{gray},
        %frame=trBL,
        frame=single,
        frameround=tttt,
        framerule=0.3pt,
        framesep=4pt,
       % belowcaptionskip=2.1pt,
%title={{\setlength{\fboxsep}{1pt}\fcolorbox{gray}{gray!10}{\sffamily\scriptsize
 %     \textcolor{gray!10}{\_}Haskell \textcolor{gray!10}{\_}}}}
}

% %%% Fraction en oblique
\newcommand{\ofr}[2]{%
	\raisebox{0ex}{$#1$}\negthinspace\slash
	\raisebox{-.5ex}{$#2$}}


\newcommand{\RR}{\mathcal{R}}



%transposee
\usepackage{fouridx}
\newcommand*{\transp}[1]{\fourIdx{{\rm t}}{}{}{}{#1}}
\newcommand\tr{\vphantom{}^{\rm t}}

\newcommand{\dd}{\text{ d}}


\paper{DS-M41} % <- do not include FC, FT etc
%\version{0}                     % <- for multiple choice exams
\title{Devoir Surveillé - Compléments de mathématiques}
\time{quatre-vingts  minutes / cent sept en cas de tiers temps} % <- number of hours: default is three
\semester{Quatrième semestre}
\annee{2015-2016} % <- default is the current year

% %\campus{City}
% \note{\small \bfseries Vous justifierez vos réponses
%     avec le plus grand soin. % N'oubliez pas qu'il serait maladroit de
%    %  copier sur  votre voisin(e) qui  a, de toute façon,  écrit n'importe
%    %  quoi. Toute enfreinte à  cette règle entraîne l'obtention d'une note
%    % plutôt faible.
%    Aucune calculatrice ni tout autre engin relié
%     à un  quelconque réseau ou   pouvant faire office  de téléphone n'est
%     autorisée.}
%     %N'oubliez pas que c'est compilator qui corrigera votre script...}
\begin{document} 

%{\small




\begin{exercice}[Étude d'un algorithme]
On appelle racine carrée entière d'un entier naturel $n$ l'unique entier $r$
vérifiant:

$$r^2 \leqslant n < (r+1)^2$$

\begin{enumerate}
\item Quelles sont les racines carrées entières des entiers de 5 à 15?
\item Voici un joli algorithme:

  \begin{algo}
\COMMENT{Pre : n >= 0}
\FUNC{Rac}{\pfarg{n}{Entier naturel}}{Entier naturel}
\STATE{r = 0}
\COMMENT{P0 : r$^2$ <= n}
\WHILE{(r + 1)*(r + 1) <= n}
\COMMENT{P1 : P0 ET x}
\STATE{r = r + 1}
\ENDWHILE
\COMMENT{P2 : P0 ET y}
\RETURN{z}
\COMMENT{Post : Rac(n)$^2$ <= n $∧$ n < (Rac(n) + 1)$^2$}
  \end{algo}

  \begin{enumerate}
  \item Déterminez les conditions x et y et l'expression z.
  \item Démontrez la terminaison et la correction de cet algorithme.
  \item Déterminez sa complexité temporelle.
  \end{enumerate}

\item  Proposez une  fonction qui  détermine la  racine carrée  entière avec  une
  complexité logarithmique.

\end{enumerate}

\end{exercice}

\newpage

\begin{exercice}[Fang Tcheng]

Voici pour mémoire une fonction étudiée en cours:

\begin{pythoncode}
def triangle(self) :
        [r,c] = self.D
        m     = min(r,c)
        S     = self
        T     = zeros(r,c)
        while m > 0:
            NoLigne = 0
            while S[NoLigne, 0] == 0 and (NoLigne < m - 1):
                    NoLigne += 1
            S = S.swap(NoLigne,0)
            if S[0, 0] != 0:
                pivot = S[0,0]
                for k in range(1,m):
                    if S[k,0] != 0:
                        S = S.comb_lignes(pivot, -S[k,0],k,0)
            T = T.remplace_ligned(r - m,S.F)
            S = S.decoupe()
            m -= 1
        return T
\end{pythoncode}

\begin{enumerate}

\item Comment modifier ce code pour obtenir une méthode \mintinline{python}{det(self)}
qui calcule le déterminant de la matrice \mintinline{python}{self}?

Vous indiquerez pourquoi \mintinline{python}{triangle} ne permet pas de calculer
le  déterminant  directement  puis  vous  préciserez les  lignes  à  changer  et
proposerez des solutions.

\item  Utilisez   \mintinline{python}{triangle}  pour  déterminer   une  méthode
  \mintinline{python}{rang(self)} qui détermine le  rang d'une matrice (3 lignes
  grand maximum).



\end{enumerate}


\end{exercice}





\begin{exercice}[Géométrie?]
  Une  matrice est  dite \textbf{orthogonale}  si, et  seulement  si, sa
  transposée est égale à son inverse.

  \begin{enumerate}
  \item La matrice $I_n$  est-elle orthogonale (Pour que M. ....  ait au moins 1
    point )?
\item La matrice $A=
  \begin{pmatrix}
    \cos(t)&\sin(t)\\-\sin(t)&\cos(t)
  \end{pmatrix}
$ est-elle orthogonale pour tout $t\in\bbr$?

\item On  considère deux  réels $t$  et $t'$.  Calculez la  partie réelle  et la
  partie imaginaire de  ${\rm e}^{{\rm i}t}×{\rm e}^{{\rm  i}t'}$ et déduisez-en
  que:

$$\cos(t+t') = \cos t\cos t' - \sin t\sin t'$$


Déterminez une formule similaire pour $\sin(t+t')$.

\item Déterminez une  formule simple donnant $A^k$ pour tout  entier naturel $k$
  et démontrez votre résultat.

Comment interpréter géométriquement le résultat obtenu?

  \end{enumerate}
\end{exercice}


\begin{exercice}[It's more fun to compute]
Inversez, si possible, la matrice suivante par la méthode de Gau\ss:

$$
H=\begin{pmatrix}
i&2&-3\\0&i&2\\0&0&i
\end{pmatrix}
$$

On rappelle que i est le nombre vérifiant ${\rm i}^2=-1$


\end{exercice}


\begin{exercice}[Sagesse]

Comment interpréter les résultats qui suivent? Il peut y avoir plusieurs
interprétations  possibles selon  les cas.  Votre  esprit de  synthèse sera  
évalué.


\begin{enumerate}
\item 
\begin{pythoncode}
sage: var('a,b,c')
(a, b, c)
sage: M = matrix([[0,1,1,a],[1,0,1,b],[1,1,0,c]])
sage: M.echelon_form()
[ 1   0   0  -1/2*a + 1/2*b + 1/2*c]
[ 0   1   0   1/2*a - 1/2*b + 1/2*c]
[ 0   0   1   1/2*a + 1/2*b - 1/2*c]  
\end{pythoncode}

\item 

\begin{pythoncode}
sage: M = matrix(QQ,[[0,1,1,1,0,0],[1,0,1,0,1,0],[1,1,0,0,0,1]])
sage: M.echelon_form()
[   1    0    0 -1/2  1/2  1/2]
[   0    1    0  1/2 -1/2  1/2]
[   0    0    1  1/2  1/2 -1/2]  
\end{pythoncode}



\item 
\begin{pythoncode}
  sage: M = matrix([[1,2,3,a],[4,5,6,b],[7,8,9,c]])
sage: M.echelon_form()
[ 1  0 -1  0]
[ 0  1  2  0]
[ 0  0  0  1]
\end{pythoncode}

\item 

\begin{pythoncode}
sage: M = matrix(QQ,[[1,2,3,1,0,0],[4,5,6,0,1,0],[7,8,9,0,0,1]])
sage: M.echelon_form()
[   1    0   -1    0 -8/3  5/3]
[   0    1    2    0  7/3 -4/3]
[   0    0    0    1   -2    1]  
\end{pythoncode}


\item 

\begin{pythoncode}
sage: B = matrix(QQ,[[1,1,1,1],[1,-1,-2,3],[2,3,5,0],[4,3,4,4]])
sage: B.echelon_form()
[   1    0    0  5/3]
[   0    1    0    0]
[   0    0    1 -2/3]
[   0    0    0    0]  
\end{pythoncode}

\item 

\begin{pythoncode}
sage: B = matrix(QQ,[[1,1,1,1],[1,-1,-2,3],[2,3,5,0],[4,3,4,3]])
sage: B.echelon_form()
[1 0 0 0]
[0 1 0 0]
[0 0 1 0]
[0 0 0 1]  
\end{pythoncode}


\item 

\begin{pythoncode}
sage: B = matrix(QQ,[[1,2,3,4,1],[4,5,6,2,2],[7,8,9,-1,4]])
sage: B.echelon_form()
[    1     0    -1     0 -17/3]
[    0     1     2     0  16/3]
[    0     0     0     1    -1]  
\end{pythoncode}


\newpage

\item 

\begin{pythoncode}
 sage: B = matrix(CC,[[1j, 2, -3,1,0,0],[0,1j,2,0,1,0],[0,0,1j,0,0,1]])
sage: B.echelon_form()
[ 1  0  0  -1*I      2   -3 + 4*I]
[ 0  1  0     0   -1*I          2]
[ 0  0  1     0      0       -1*I] 
\end{pythoncode}



  \end{enumerate}
\end{exercice}


\begin{exercice}[Loop]
  Quelle est la complexité de cet algorithme:


%\begin{figure}
\begin{center}
  \includegraphics[height=7.5cm]{loop}
\end{center}
%\end{figure}

\end{exercice}


\begin{exercice}[Bonus]

Remplir ce Sudoku (pour M. .... non, je ne citerai personne.)
  

%\begin{figure}
\begin{center}
  \includegraphics[height=3cm]{sudoku}
\end{center}
%\end{figure}


\end{exercice}


Bon stage  et que la  force et la  programmation fonctionnelle soient  avec vous
pour la suite de vos études!


%\begin{figure}
\begin{center}
  \includegraphics[height=4.5cm]{vador}
\end{center}
%\end{figure}

\end{document}

%%% Local Variables:
%%% mode: latex
%%% TeX-master: t
%%% End:
