\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 
%Corrigé : François Hache
\usepackage{multicol,diagbox}
\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\,}}
\newcommand{\barre}[1]{\overline{\,\vphantom{b}#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[french]{babel}
\DecimalMathComma
\usepackage[np]{numprint}
\newcommand{\e}{\,\text{e\,}}%%%               le e de l'exponentielle
\renewcommand{\d}{\,\text d}%%%              le d de l'intégration
\renewcommand{\i}{\,\text{i}\,}%%%           le i des complexes
\newcommand{\ds}{\displaystyle}
\setlength\parindent{0mm}
\setlength\parskip{5pt}

\begin{document}

\setlength\parindent{0mm}
\rhead{\textbf{A. P{}. M. E. P{}.}}
\lhead{\small BTS Métropole -- corrigé}
\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~Corrigé du BTS Métropole 12 mai 2016~\decofourright\\[5pt]Services informatiques aux organisations}}

\vspace{0,25cm}

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

\vspace{0,25cm}

\textbf{\large{}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 On détermine le niveau de chacun des sommets.

\begin{multicols}{2}%%% niveau 0
On part du tableau des prédécesseurs.\\
\\
On cherche les sommets qui n'ont pas de prédécesseur; il s'agit de A et de D.\\
\\
Les sommets A et D sont donc de niveau 0.

\columnbreak

\begin{center}
\psset{cancelType=s,linewidth=1pt,linecolor=blue}
\begin{tabular}{|*{2}{c|}}\hline
Tâche	& Prédécesseurs\\ \hline
A 	& --\\ \hline
B	&A\\ \hline
C	&A -- D\\ \hline
D	&--\\ \hline
E	&D\\ \hline
F  & C -- E\\ \hline
G 	&B -- F\\ \hline
\end{tabular}
\end{center}
\end{multicols}

\begin{multicols}{2}%%% niveau 1
On supprime dans le tableau les sommets de niveau 0, puis on cherche dans le nouveau  tableau les sommets qui n'ont pas de prédécesseur; il s'agit de B, C et E.\\
\\
Les sommets B, C et E sont donc de niveau 1.

\columnbreak

\begin{center}
\psset{cancelType=s,linewidth=1pt,linecolor=blue}
\begin{tabular}{|*{2}{c|}}\hline
Tâche	& Prédécesseurs\\ \hline
\psCancel A 	& --\\ \hline
B	& \psCancel A\\ \hline
C	& \psCancel A -- \psCancel D\\ \hline
\psCancel D	&--\\ \hline
E	& \psCancel D\\ \hline
F  & C -- E\\ \hline
G 	&B -- F\\ \hline
\end{tabular}
\end{center}
\end{multicols}

\newpage

\begin{multicols}{2}%%% niveau 2
On supprime dans le tableau les sommets de niveau 1, puis on cherche dans le nouveau  tableau les sommets qui n'ont pas de prédécesseur; il s'agit de F{}.\\
\\
Le sommet F est donc de niveau 2.

\columnbreak

\begin{center}
\psset{cancelType=s,linewidth=1pt,linecolor=blue}
\begin{tabular}{|*{2}{c|}}\hline
Tâche	& Prédécesseurs\\ \hline
\psCancel A 	& --\\ \hline
\psCancel B	& \psCancel A\\ \hline
\psCancel C	& \psCancel A -- \psCancel D\\ \hline
\psCancel D	&--\\ \hline
\psCancel E	& \psCancel D\\ \hline
F  & \psCancel C -- \psCancel E\\ \hline
G 	& \psCancel B -- F\\ \hline
\end{tabular}
\end{center}
\end{multicols}

\begin{multicols}{2}%%% niveau 3
On supprime dans le tableau les sommets de niveau 2, puis on cherche dans le nouveau  tableau les sommets qui n'ont pas de prédécesseur; il s'agit de G.\\
\\
Le sommet G est donc de niveau 3.

\columnbreak

\begin{center}
\psset{cancelType=s,linewidth=1pt,linecolor=blue}
\begin{tabular}{|*{2}{c|}}\hline
Tâche	& Prédécesseurs\\ \hline
\psCancel A 	& --\\ \hline
\psCancel B	& \psCancel A\\ \hline
\psCancel C	& \psCancel A -- \psCancel D\\ \hline
\psCancel D	&--\\ \hline
\psCancel E	& \psCancel D\\ \hline
\psCancel F  & \psCancel C -- \psCancel E\\ \hline
G 	& \psCancel B -- \psCancel F\\ \hline
\end{tabular}
\end{center}
\end{multicols}

On a donc:

\begin{center}
\begin{tabularx}{0.7\linewidth}{|c|*{4}{>{\centering \arraybackslash}X|}}
\hline
Niveaux & 0 & 1 & 2 & 3\\
\hline
Tâches & A -- D & B -- C -- E & F & G\\
\hline
\end{tabularx}
\end{center}


\item On donner le tableau des successeurs de chaque sommet.

\begin{center}
\psset{cancelType=s,linewidth=1pt,linecolor=blue}
\begin{tabular}{|*{3}{c|}}\hline
Tâche	& Prédécesseurs & Successeurs\\ \hline
A 	& -- & B -- C\\ \hline
B	&A & G\\ \hline
C	&A -- D & F\\ \hline
D	& -- & C -- E\\ \hline
E	&D & F\\ \hline
F  & C -- E & G\\ \hline
G 	&B -- F & --\\ \hline
\end{tabular}
\end{center}

\item On construit par étapes le graphe d'ordonnancement du projet (méthode M. P. M.); pour cela on construit le graphe par niveaux en rajoutant une tâche fictive \og fin \fg{}.

%%%%% 1
\begin{center}
\psset{xunit=0.6cm,yunit=0.6,arrowsize=3pt 2}
\begin{pspicture}(1,-0.5)(23,8.5)
\psset{linewidth=.75pt,nodesep=0.7cm}
%\psgrid[gridcolor=orange]
%%% boîte
\newcommand{\boxh}[3]{%%%
\psframe(-1,-1)(1,1)
\psline(-1,0)(1,0)
\psline(0,0)(0,1)
\rput(0,-0.5){#1}
\rput(-0.5,0.5){#2}
\rput(0.5,0.5){#3}}
%%% niveaux
%\multido{\i=0+1}{6}{
%\psline[linecolor=blue,linestyle=dashed](\i,-1.5)(\i,1.5)\uput[d](\i,-1.5){\blue \i}%{\blue $C_{\i}$}
%}
%\rput(-2,-2){\boxh{A}}
%\rput(0,2){\boxh{B}}
%%% sommets
\def\ray{5}
\cnodeput*(2,7){A}{\boxh{A}{}{}} 
\cnodeput*(2,1){D}{\boxh{D}{}{}}  
\cnodeput*(7,7){B}{\boxh{B}{}{}}  
\cnodeput*(7,4){C}{\boxh{C}{}{}}
\cnodeput*(7,1){E}{\boxh{E}{}{}} 
\cnodeput*(12,4){F}{\boxh{F}{}{}}  
\cnodeput*(17,7){G}{\boxh{G}{}{}}  
\cnodeput*(22,7){H}{\boxh{fin}{}{}}  
%%% arcs
\ncline{->}{A}{B} \ncput*{1}  
\ncline{->}{A}{C}  \ncput*{1}  
\ncline{->}{D}{C}  \ncput*{3}  
\ncline{->}{D}{E} \ncput*{3}   
\ncline{->}{B}{G}  \ncput*{5}  
\ncline{->}{C}{F}  \ncput*{1}  
\ncline{->}{E}{F}  \ncput*{1}  
\ncline{->}{F}{G}  \ncput*{4}  
\ncline{->}{G}{H}    \ncput*{1}   
\end{pspicture} 
\end{center}

Pour déterminer pour chaque tâche les \og dates au plus tôt \fg{}, on traite les sommets par niveaux en partant du début. Puis pour chaque sommet, on note la date qui est la longueur du plus \textbf{long} chemin depuis le début.

%%%%% 2
\begin{center}
\psset{xunit=0.6cm,yunit=0.6,arrowsize=3pt 2}
\begin{pspicture}(1,-0.5)(23,8.5)
\psset{linewidth=.75pt,nodesep=0.7cm}
%\psgrid[gridcolor=orange]
%%% boîte
\newcommand{\boxh}[3]{%%%
\psframe(-1,-1)(1,1)
\psline(-1,0)(1,0)
\psline(0,0)(0,1)
\rput(0,-0.5){#1}
\rput(-0.5,0.5){\blue #2}
\rput(0.5,0.5){\red #3}}
%%% niveaux
%\multido{\i=0+1}{6}{
%\psline[linecolor=blue,linestyle=dashed](\i,-1.5)(\i,1.5)\uput[d](\i,-1.5){\blue \i}%{\blue $C_{\i}$}
%}
%\rput(-2,-2){\boxh{A}}
%\rput(0,2){\boxh{B}}
%%% sommets
\def\ray{5}
\cnodeput*(2,7){A}{\boxh{A}{0}{}} 
\cnodeput*(2,1){D}{\boxh{D}{0}{}}  
\cnodeput*(7,7){B}{\boxh{B}{1}{}}  
\cnodeput*(7,4){C}{\boxh{C}{3}{}}
\cnodeput*(7,1){E}{\boxh{E}{3}{}} 
\cnodeput*(12,4){F}{\boxh{F}{4}{}}  
\cnodeput*(17,7){G}{\boxh{G}{8}{}}  
\cnodeput*(22,7){H}{\boxh{fin}{9}{}}  
%%% arcs
\ncline{->}{A}{B} \ncput*{1}  
\ncline{->}{A}{C}  \ncput*{1}  
\ncline{->}{D}{C}  \ncput*{3}  
\ncline{->}{D}{E} \ncput*{3}   
\ncline{->}{B}{G}  \ncput*{5}  
\ncline{->}{C}{F}  \ncput*{1}  
\ncline{->}{E}{F}  \ncput*{1}  
\ncline{->}{F}{G}  \ncput*{4}  
\ncline{->}{G}{H}    \ncput*{1}   
\end{pspicture} 
\end{center}

Ce graphe donne la durée minimale du projet qui est de 9 jours.

Pour déterminer pour chaque tâche les \og dates au plus tard \fg{}, on traite les sommets par niveaux en partant de la fin et en marquant 9 pour le sommet \og fin \fg{}.
La date \og au plus tard \fg{} d'une tâche s'obtient en retirant de la date au plus tard de la tâche qui lui succède sa propre durée.
S'il y a plusieurs successeurs, on garde la date la plus \textbf{petite}.

%%%%% 3
\begin{center}
\psset{xunit=0.6cm,yunit=0.6,arrowsize=3pt 2}
\begin{pspicture}(1,-0.5)(23,8.5)
\psset{linewidth=.75pt,nodesep=0.7cm}
%\psgrid[gridcolor=orange]
\newrgbcolor{rb}{0.804 0 0}
%%% boîte
\newcommand{\boxh}[3]{%%%
\psframe(-1,-1)(1,1)
\psline(-1,0)(1,0)
\psline(0,0)(0,1)
\rput(0,-0.5){#1}
\rput(-0.5,0.5){\blue #2}
\rput(0.5,0.5){\red #3}}
%%% niveaux
%\multido{\i=0+1}{6}{
%\psline[linecolor=blue,linestyle=dashed](\i,-1.5)(\i,1.5)\uput[d](\i,-1.5){\blue \i}%{\blue $C_{\i}$}
%}
%\rput(-2,-2){\boxh{A}}
%\rput(0,2){\boxh{B}}
%%% sommets
\def\ray{5}
\cnodeput*(2,7){A}{\boxh{A}{0}{2}} 
\cnodeput*(2,1){D}{\boxh{D}{0}{0}}  
\cnodeput*(7,7){B}{\boxh{B}{1}{3}}  
\cnodeput*(7,4){C}{\boxh{C}{3}{3}}
\cnodeput*(7,1){E}{\boxh{E}{3}{3}} 
\cnodeput*(12,4){F}{\boxh{F}{4}{4}}  
\cnodeput*(17,7){G}{\boxh{G}{8}{8}}  
\cnodeput*(22,7){H}{\boxh{fin}{9}{9}}  
%%% arcs
\ncline{->}{A}{B} \ncput*{1}  
\ncline{->}{A}{C}  \ncput*{1}  
\ncline{->}{D}{C}  \ncput*{3}  
\ncline{->}{D}{E} \ncput*{3}   
\ncline{->}{B}{G}  \ncput*{5}  
\ncline{->}{C}{F}  \ncput*{1}  
\ncline{->}{E}{F}  \ncput*{1}  
\ncline{->}{F}{G}  \ncput*{4}  
\ncline{->}{G}{H}    \ncput*{1}   
\end{pspicture} 
\end{center}


\item Il y a deux chemins critiques: D $\longrightarrow$ C $\longrightarrow$ F  $\longrightarrow$  G  $\longrightarrow$ \og fin \fg{} et  D $\longrightarrow$ E $\longrightarrow$ F  $\longrightarrow$  G  $\longrightarrow$ \og fin \fg{}.

La durée minimale du projet est de 9 jours.

\item %Calculer la marge libre et la marge totale de la tâche A.
\begin{list}{\textbullet}{}
\item La marge libre de A est obtenue par: \og plus petite date au plus tôt des successeurs de A \fg{} moins  \og date au plus tôt de A \fg{} moins \og durée de la tâche A \fg{} soit  $1-0-1=0$. 
\item La marge totale de A est obtenue par: \og date au plus tard de A \fg{} moins  \og date au plus tôt de A \fg{} soit $2-0=2$.
\end{list}

\item La tâche A commence avec un jour de retard.
	\begin{enumerate}
		\item La marge libre de A est égale à 0; le retard pour A de 1 jour est supérieur à la marge libre de A donc aura une incidence sur le début des tâches suivantes: plus précisément, la tâche B commencera avec 1 jour de retard.
		\item La marge totale de A est égale à 2; le retard pour A de 1 jour est inférieur à la marge totale de A donc n'aura pas d'incidence sur la date de fin du projet.
	\end{enumerate}
\end{enumerate}

\newpage

\textbf{\large{}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}. \\
On note $r$ cette raison.
	\begin{enumerate}
		\item% Donner une expression de son terme général.
Pour tout $n$, on a: $r_n=r_0+n\times r=\np{5000} + \np{1000}n$.	
		\item La résistance d'un bâtiment de niveau $20$ est
		$r_{20}=\np{5000} + \np{1000}\times 20 = \np{25000}$.
	\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$.\\
On note $q$ cette raison.
	\begin{enumerate}
		\item %Donner une expression du terme général $u_n$ de cette suite.
Pour tout $n$, on a: $u_n=u_0\times q^n = 450 \times 1,5^n$.		
		\item Le coût en pièce d'or pour améliorer un bâtiment du niveau 19 au niveau 20 est \\
$u_{19} = 450\times 1,5^{19}\approx \np{997577}$.
	\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é.

La suite $(u_n)$ est géométrique et on connaît la somme des premiers termes d'une suite géométrique qui est donnée par la formule
$S= \text{premier terme}\times \dfrac{1-\text{raison}^{\text{nombre de termes}}}{1-\text{raison}}$.

Donc
$u_0 + u_1 + \ldots + u_{19}=u_0 \times \dfrac{1-q^{20}}{1-q}
= 450 \times \dfrac{1-1,5^{20}}{1-1,5}\approx \np{2991831}$.

		\item On récolte \np{500000}~pièces d'or au cours de la partie.%, quel est le niveau atteint par le joueur ?
		
Le niveau  atteint est le plus grand entier $n$ tel que $u_0+u_1+ \ldots +u_n  \leqslant \np{500000}$.
		
%Justifier la réponse.

$u_0+u_1+ \ldots +u_n  \leqslant \np{500000}
\iff
u_0\times \dfrac{1-q^{n+1}}{1-q} \leqslant \np{500000}
\iff
450\times \dfrac{1-1,5^{n+1}}{1-1,5} \leqslant \np{500000}\\[5pt]
\phantom{u_0+u_1+ \ldots +u_n  \leqslant \np{500000}}
\iff
1-1,5^{n+1} \geqslant -0,5 \times \dfrac{\np{500000}}{450}
\iff
1+\dfrac{\np{250000}}{450} \geqslant 1,5^{n+1}\\[5pt]
\phantom{u_0+u_1+ \ldots +u_n  \leqslant \np{500000}}
\iff
\dfrac{\np{5009}}{9} \geqslant 1,5^{n+1}
\iff
\ln\left (\dfrac{\np{5009}}{9} \right )\geqslant \ln \left (1,5^{n+1}\right )\\[5pt]
\phantom{u_0+u_1+ \ldots +u_n  \leqslant \np{500000}}
\iff
\ln\left (\dfrac{\np{5009}}{9} \right )\geqslant \left (n+1\right ) \ln \left (1,5\right )
\iff
\dfrac{\ln\left (\frac{\np{5009}}{9} \right )}{\ln(1,5)} \geqslant n+1\\[5pt]
\phantom{u_0+u_1+ \ldots +u_n  \leqslant \np{500000}}
\iff
\dfrac{\ln\left (\frac{\np{5009}}{9} \right )}{\ln(1,5)}-1 \geqslant n$

$\dfrac{\ln\left (\frac{\np{5009}}{9} \right )}{\ln(1,5)}-1 \approx 14,6$ donc le joueur aura atteint le niveau 14.

	\end{enumerate}
\end{enumerate}

\newpage

\textbf{\large{}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.
$2\times 0+1=1$, $2\times 1+1=3$ et $2\times 2+1=5$ donc 	les 3 plus petits entiers naturels dont la réduction modulo 2 est égale à 1 sont 1, 3 et 5.	
		
		\item %Quelle est la réduction modulo 2 d'un entier pair ?
Un entier pair a pour reste 0 dans la division par 2, donc la réduction modulo 2 d'un entier pair est 0.		
		
			\end{enumerate}
			\end{enumerate}
			
\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

	\begin{enumerate}
\setcounter{enumi}{1}
\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 On calcule le code du mot $m = \begin{pmatrix}0 &1 &1 &0\end{pmatrix}$.

$m\times G =
\begin{pmatrix}0 &1 &1 &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 & 1 & 0 & 2 & 1 & 0 & 1
\end{pmatrix}$

et, après réduction modulo 2, on obtient: 
$\begin{pmatrix}
0 & 1 & 0 & 0 & 1 & 0 & 1
\end{pmatrix}$.
		
%\emph{On rappelle que les coefficients de la matrice obtenue doivent être réduits modulo }2.
		\item Parmi les réponses suivantes, la phrase encadrée traduit le fait que la fonction de codage $C$ est injective.
		
%\emph{Recopier sur la copie la seule bonne réponse.}

\begin{list}{\textbullet}{}
\item Le code d'un mot contient 7 bits différents.
\item Il existe un code de 7 bits.
\item \fbox{Deux mots différents ont des codes différents.}
\item Tout code de 7 bits est l'image d'un mot de 4 bits.
\end{list}
	\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}$.

C'est la matrice identité d'ordre 4 notée $I_4$.

Si  $c = m \times G$, alors $c \times H= m \times G  \times H$ donc $c \times H= m \times I_4$, et donc $c \times H = m$.

		\item On reçoit le code $c = \begin{pmatrix}1 &1 &0 &1 &1 &1 &0\end{pmatrix}$. 
		Il n'y a pas eu d'erreur de transmission.

$c\times H = \begin{pmatrix} 0 & 3 & 2 & 2 \end{pmatrix}$ donc le mot $m$ qui a été codé par l'émetteur est $\begin{pmatrix} 0 & 1 & 0 & 0 \end{pmatrix}$.

\emph{Remarque du correcteur}
\begin{quote}
Si, en utilisant la matrice $G$, on code le mot $m$ que l'on vient de trouver, on a:

$m*G=
\begin{pmatrix}
1 & 1 & 0 & 1 & 0 & 0 & 1
\end{pmatrix}$

qui n'est pas le code $c$ du départ. Contrairement à ce qui est écrit dans le sujet, il y a certainement une erreur dans la transmission. 
\end{quote}

	\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).
\begin{list}{\textbullet}{}
\item Soit $c_1= \begin{pmatrix}1 &1 &1 &0 &1 &1 &0\end{pmatrix}$ 

$c_1\times P = 
\begin{pmatrix} 2 &3 &3\end{pmatrix}$
soit après réduction modulo 2:
$\begin{pmatrix} 0 & 1 & 1\end{pmatrix}$

Il y a donc une erreur de transmission; $011_{2}=3$ donc l'erreur est sur le 3\ieme{} bit en partant de la gauche. Le bon code est donc
$c'_1= \begin{pmatrix}1 &1 &0 &0 &1 &1 &0\end{pmatrix}$.

\item Soit $c_2=  \begin{pmatrix}0 &0 &1 &0 &1 &1 &0\end{pmatrix}$

$c_2\times P = 
\begin{pmatrix} 2 &2 & 2\end{pmatrix}$
soit après réduction modulo 2:
$\begin{pmatrix} 0 & 0 & 0\end{pmatrix}$

Il n'y a pas eu d'erreur de transmission.
\end{list}

\emph{Remarque du correcteur -- retour sur la question 3.b.}

\begin{quote}
Si $c = \begin{pmatrix}1 &1 &0 &1 &1 &1 &0\end{pmatrix}$, on a:

$c \times P =  \begin{pmatrix} 3 & 2 & 2\end{pmatrix}$
soit après réduction modulo 2:
$\begin{pmatrix} 1 & 0 & 0\end{pmatrix}$.

Il y a bien eu une erreur de transmission sur le 4\ieme{} bit.
\end{quote}
\end{enumerate}

\end{document}
