%!TEX encoding = UTF-8 Unicode
\documentclass[10pt]{article}
\usepackage[T1]{fontenc}
\usepackage[utf8]{inputenc}%ATTENTION codage en utf8 ! 
\usepackage{fourier} 
\usepackage[scaled=0.875]{helvet}
\renewcommand{\ttdefault}{lmtt}
\usepackage{amsmath,amssymb,makeidx}
\usepackage{fancybox}
\usepackage{graphicx}
\usepackage{tabularx}
\usepackage[normalem]{ulem}
\usepackage{pifont}
\usepackage{textcomp} 
\newcommand{\euro}{\eurologo}
%Tapuscrit : Denis Vergès 
\usepackage{pst-plot,pst-text,pst-tree,pstricks-add}
\newcommand{\R}{\mathbb{R}}
\newcommand{\N}{\mathbb{N}}
\newcommand{\D}{\mathbb{D}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\Q}{\mathbb{Q}}
\newcommand{\C}{\mathbb{C}}
\usepackage[left=3.5cm, right=3.5cm, top=3cm, bottom=3cm]{geometry}
\newcommand{\vect}[1]{\overrightarrow{\,\mathstrut#1\,}}
\renewcommand{\theenumi}{\textbf{\arabic{enumi}}}
\renewcommand{\labelenumi}{\textbf{\theenumi.}}
\renewcommand{\theenumii}{\textbf{\alph{enumii}}}
\renewcommand{\labelenumii}{\textbf{\theenumii.}}
\def\Oij{$\left(\text{O}~;~\vect{\imath},~\vect{\jmath}\right)$}
\def\Oijk{$\left(\text{O}~;~\vect{\imath},~\vect{\jmath},~\vect{k}\right)$}
\def\Ouv{$\left(\text{O}~;~\vect{u},~\vect{v}\right)$}
\usepackage{fancyhdr}
\usepackage{hyperref}
\hypersetup{%
pdfauthor = {APMEP},
pdfsubject = {BTS},
pdftitle = {Métropole 12 mai 2016},
allbordercolors = white,
pdfstartview=FitH}  
\usepackage[frenchb]{babel}
\usepackage[np]{numprint}
\begin{document}
\setlength\parindent{0mm}
\rhead{\textbf{A. P{}. M. E. P{}.}}
\lhead{\small Brevet de technicien supérieur Métropole}
\lfoot{\small{Services informatiques aux organisations\\ épreuve obligatoire}}
\rfoot{\small{12 mai  2016}}
\pagestyle{fancy}
\thispagestyle{empty}
\marginpar{\rotatebox{90}{\textbf{A. P{}. M. E. P{}.}}}

\begin{center} {\Large \textbf{\decofourleft~BTS Métropole 12 mai 2016~\decofourright\\[5pt]Services informatiques aux organisations}}

\vspace{0,25cm}

\textbf{Épreuve obligatoire}
  
\end{center}

\vspace{0,25cm}

\textbf{Exercice 1 \hfill 9 points}

\medskip

La planification d'un projet de création d'un robot requiert les sept tâches listées ci-dessous.

\begin{center}
\begin{tabularx}{\linewidth}{|m{4cm}|*{3}{>{\centering \arraybackslash}X|}}\hline
\textbf{Description de la tâche}&\textbf{Tâche}	&\textbf{Durée (en jour)}&\textbf{Prédécesseurs}\\ \hline
Achat de la structure 				&A 	&1 		&-\\ \hline
Modélisation numérique				&B	&5		&A\\ \hline
Montage de la maquette				&C	&1		&A, D\\ \hline
Achat des capteurs					&D	&3		&-\\ \hline
Développement du programme			&E	&1		&D\\ \hline
Test du programme sur la maquette et ajustements&F &4 &C,E\\ \hline
Négociation des frais de fabrication&G 	&1 		&B,F\\ \hline
\end{tabularx}
\end{center}

\begin{enumerate}
\item Déterminer le niveau de chacun des sommets.
\item Donner le tableau des successeurs de chaque sommet.
\item Construire le graphe d'ordonnancement du projet (méthode M. P. M. ou P. E. R. T.) en incluant les
dates au plus tôt et au plus tard.
\item Donner un chemin critique et la durée minimale du projet.
\item Calculer la marge libre et la marge totale de la tâche A.
\item La tâche A commence avec un jour de retard.
	\begin{enumerate}
		\item Ce retard aura-t-il une incidence sur le début des tâches suivantes ? Justifier.
		\item Ce retard aura-t-il une incidence sur la date de fin du projet ? Justifier.
	\end{enumerate}
\end{enumerate}

\vspace{0,5cm}

\textbf{Exercice 2 \hfill 5 points}

\medskip

Dans un jeu vidéo de stratégie, le but est de franchir des niveaux successifs pour augmenter la
résistance d'un bâtiment. Au début du jeu, le joueur commence au niveau 0 avec un bâtiment de
résistance \np{5000}. Au cours de la partie, le joueur gagne des pièces d'or qui lui permettent de passer
des niveaux tout en augmentant la résistance du bâtiment. Par exemple, il en coûte $450$ pièces d'or
pour passer au niveau 1.

L'entier naturel $n$ désigne le niveau du jeu atteint. On note $r_n$ la résistance du bâtiment au niveau $n$ et $u_n$ le coût en pièce d'or pour passer du niveau $n$ au niveau $n + 1$.

On a donc $r_0 = \np{5000}$ et $u_0 = 450$.

\medskip

\begin{enumerate}
\item Dans la programmation du jeu, la suite $\left(r_n\right)$ est une suite arithmétique de raison \np{1000}.
	\begin{enumerate}
		\item Donner une expression de son terme général.
		\item Calculer la résistance d'un bâtiment de niveau $20$.
	\end{enumerate}
\item Le jeu est programmé pour que la suite $\left(u_n\right)$ soit une suite géométrique de raison 1,5.
	\begin{enumerate}
		\item Donner une expression du terme général $u_n$ de cette suite.
		\item Calculer le coût en pièce d'or pour améliorer un bâtiment du niveau 19 au niveau 20. Le
résultat sera arrondi à l'unité.
	\end{enumerate}
\item On s'intéresse à plusieurs améliorations successives d'un bâtiment.
	\begin{enumerate}
		\item Le coût total en pièce d'or pour améliorer successivement un bâtiment du niveau 0 au niveau
20 est égal à la somme des 20 premiers termes de la suite $\left(u_n\right)$, c'est-à-dire la somme
$u_0 + u_1 + \ldots + u_{19}$.
		
Calculer ce coût total en pièce d'or, arrondi à l'unité.
		\item En récoltant \np{500000}~pièces d'or au cours de la partie, quel est le niveau atteint par le joueur ?
Justifier la réponse.
	\end{enumerate}
\end{enumerate}

\vspace{0,5cm}

\textbf{Exercice 3 \hfill 6 points}

\medskip

Lors de la transmission d'un message entre un émetteur et un récepteur, il est possible que le
message soit altéré par des erreurs. On utilisera le vocabulaire suivant :

\setlength\parindent{8mm}
\begin{itemize}
\item un \emph{mot} est une suite de 4 bits;
\item le \emph{code initial} est le code envoyé par l'émetteur, il est constitué de 7 bits;
\item le \emph{code reçu} est le code reçu par le récepteur, il est constitué de 7 bits.
\end{itemize}
\setlength\parindent{0mm}

On s'intéresse dans cet exercice à un code correcteur dit code de Hamming dont l'intérêt est de
permettre de retrouver le code initial si une erreur intervient dans la transmission du code.

\medskip

\begin{enumerate}
\item Travail préliminaire.

On appelle \og réduction d'un entier modulo 2 \fg{} le reste de la division euclidienne de cet entier par
2. Par exemple $11 =  2 \times 5 + 1$ donc la réduction de 11 modulo 2 est égale à 1.
	\begin{enumerate}
		\item Donner les 3 plus petits entiers naturels dont la réduction modulo 2 est égale à 1.
		\item Quelle est la réduction modulo 2 d'un entier pair ?
		
\textbf{Dans la suite de cet exercice, tous les produits de matrices seront calculés de façon
habituelle, puis on donnera la réduction modulo 2 de tous les coefficients.}
		
\smallskip
	\end{enumerate}
\item Codage d'un mot
	
On veut transmettre un mot de 4 bits. On le représente par une matrice à 1 ligne et 4 colonnes, par
exemple le mot 0100 est représenté par la matrice :
	
\[m = \begin{pmatrix}0 &1 &0 &0\end{pmatrix}.\]

Pour calculer son codage, on définit la matrice $G$ suivante :

\[G = \begin{pmatrix}
1&1	&1	&0	& 0	&0	&0\\
1&1 &0 	&1 	&0 	&0	&1\\
1&0 &0 	&1 	&1	&0	&0\\
0&1 &0 	&1 	&0 	&1	&0\end{pmatrix}.\]

La fonction de codage $C$, qui donne le code $c$, est la fonction injective définie pour tout mot $m$ de
longueur 4 par le produit de matrices:

\[c = C(m) = m \times G.\]

Par exemple pour le mot $m = \begin{pmatrix}1 &1 &0 &0\end{pmatrix}$, on a le code $c = 
\begin{pmatrix}0 &0 &1 &1 &0 &0 &1\end{pmatrix}$ car :


\[\begin{pmatrix}1 &1 &0 &0\end{pmatrix}\times  \begin{pmatrix}
1	&1	&1	&0	&0	&0	&0\\
1	&1 	&0 	&1 	&0 	&0	&1\\
1 	&0 	&0 	&1	&1	&0	&0\\
0	&1 	&0 	&1 	&0 	&1	&0\end{pmatrix} = \begin{pmatrix}2&2&1&1&0&0&1\end{pmatrix}\]

et, après réduction modulo 2, on obtient bien : 
$c = C(m) = \begin{pmatrix}0 &0 &1 &1 &0 &0 &1\end{pmatrix}$.

	\begin{enumerate}
		\item Calculer le code du mot $m = \begin{pmatrix}0 &1 &1 &0\end{pmatrix}$.
		
\emph{On rappelle que les coefficients de la matrice obtenue doivent être réduits modulo }2.
		\item Parmi les réponses suivantes, laquelle traduit le fait que la fonction de codage $C$ est injective ?
		
\emph{Recopier sur la copie la seule bonne réponse.}

\setlength\parindent{8mm}
\begin{itemize}
\item[$\bullet~~$] Le code d'un mot contient 7 bits différents.
\item[$\bullet~~$] Il existe un code de 7 bits.
\item[$\bullet~~$] Deux mots différents ont des codes différents.
\item[$\bullet~~$] Tout code de 7 bits est l'image d'un mot de 4 bits.
\end{itemize}
\setlength\parindent{0mm} 
	\end{enumerate}
\item Décodage
	
La fonction de décodage $D$ est la fonction surjective qui associe à tout code $c$ le mot $m = D(c)$
tel que $c = C(m)$. 
	
Le processus de codage-décodage permet donc de coder un mot avant sa
transmission et de retrouver ce mot après sa transmission.

%010 1
%o 1 1 0
%101 1
	\begin{enumerate}
		\item Soit $H$ la matrice à 7 lignes et 4 colonnes définie par : $H = \begin{pmatrix}
0 	&1	&0	&1\\
0	&1	&1	&0\\
1	&0	&1	&1\\
0	&1	&1	&1\\
0	&0	&0	&0\\
0	&0	&0	&0\\
0	&0	&0	&0\\
\end{pmatrix}$.

On remarque que l'on a $G \times H = \begin{pmatrix}1&0&0&0\\
0&1&0&0\\
0 &0&1&0\\
0 &0&0&1\end{pmatrix}$.

Montrer que l'égalité $c = m \times G$ implique l'égalité $m = c \times H$.
		\item On reçoit le code $c = \begin{pmatrix}1 &1 &0 &1 &1 &1 &0\end{pmatrix}$. II n'y a pas eu d'erreur de transmission.

Retrouver le mot $m$ qui a été codé par l'émetteur.
	\end{enumerate}
\item Vérification de la présence d'une erreur et correction
	
Dans la suite, on appelle erreur le remplacement d'un seul bit du code initial (0 au lieu de 1, ou 1
au lieu de 0). Pour vérifier l'apparition d'une telle erreur dans le code reçu $c$ et la corriger, on
utilise une matrice dite de parité $P$ définie par :
	
\[P = \begin{pmatrix} 0 &0&1\\
0 &1 &0\\
0 &1 &1\\
1 &0 &0\\
1 &0 &1\\
1 &1 &0\\
1 &1 &1
\end{pmatrix}.\]

On calcule le produit matriciel $c \times P$. Les coefficients résultants sont réduits modulo 2.

Si le résultat est $\begin{pmatrix}0 &0 &0\end{pmatrix}$ alors il n'y a pas eu d'erreur au sens défini ci-dessus.

Par exemple, si le code reçu est $c = \begin{pmatrix}1 &1 &0 &1 &0 &0 &1\end{pmatrix}$ alors $c \times P = \begin{pmatrix}0 &0 &0\end{pmatrix}$, il n'y a pas eu d'erreur au sens défini ci-dessus.

Sinon, le résultat obtenu correspond à la décomposition binaire de la position de l'erreur.

Par exemple, si le code reçu est $c = \begin{pmatrix}1 &1 &0 &0 &0 &0 &1\end{pmatrix}$ on a  
$c \times P = \begin{pmatrix}1 &0 &0\end{pmatrix}$, donc il y a eu une erreur. Comme $100_2 = 4$, l'erreur porte sur le 4\up{e} bit en partant de la gauche, on en déduit que le code initial était 

$\begin{pmatrix}1 &1 &0 &1 &0 &0 &1\end{pmatrix}$.

Parmi les deux codes suivants, déterminer celui qui contient une erreur puis la corriger. Justifier
(on ne demande pas le mot $m$ correspondant à ce code).

\[\bullet~~ \begin{pmatrix}1 &1 &1 &0 &1 &1 &0\end{pmatrix} \quad ;\quad \bullet~~ \begin{pmatrix}0 &0 &1 &0 &1 &1 &0\end{pmatrix}.\]
\end{enumerate}
\end{document}