\documentclass[11pt]{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{enumitem}
\usepackage{pifont}
\usepackage{textcomp} 
\newcommand{\euro}{\eurologo}
\usepackage{multicol,diagbox}
%Tapuscrit : Denis Vergès
%Corrigé : François Hache
\usepackage{pst-plot,pst-text,pst-node,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{\,\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 mai 2021},
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}
\rhead{\textbf{A. P{}. M. E. P{}.}}
\lhead{\small Corrigé du BTS Métropole}
\lfoot{\small{Services informatiques aux organisations\\ épreuve obligatoire}}
\rfoot{\small{mai 2021}}
\pagestyle{fancy}
\thispagestyle{empty}
\marginpar{\rotatebox{90}{\textbf{A. P{}. M. E. P{}.}}}

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

\medskip

\textbf{Épreuve obligatoire}

%\vspace{0,25cm}
%
%\textbf{L'usage de calculatrice avec mode examen actif est autorisé} 
%
%\textbf{L'usage de calculatrice sans mémoire \og type collège \fg{} est autorisé}

\end{center}

\smallskip

\textbf{\large Exercice 1 : un problème de routage \hfill 5 points}

\medskip

%\textbf{Les parties A et B sont indépendantes}

\medskip

\textbf{Partie A}

\medskip

On considère un réseau de commutation de paquets constitués de 6 routeurs A, B, C, D, E et F. 
Chaque paquet reçu par l'un des routeurs doit être acheminé vers un autre routeur, jusqu'à atteindre sa destination finale.
Dans le tableau ci-dessous, on a résumé les règles de routage d'un routeur à un autre routeur.

\begin{center}
\begin{tabularx}{\linewidth}{|c|*{6}{>{\centering \arraybackslash}X|}}\hline
Peut transmettre à&A &B &C &D &E &F\\ \hline
A&&&$\blacksquare$&$\blacksquare$&$\blacksquare$&\\ \hline
B&$\blacksquare$&&$\blacksquare$&&$\blacksquare$&$\blacksquare$\\ \hline
C&&&&&$\blacksquare$&\\ \hline
D&&&&&&\\ \hline
E&&&&$\blacksquare$&&$\blacksquare$\\ \hline
F&&&&$\blacksquare$&&\\ \hline
\end{tabularx}
\end{center}

On considère le graphe simple orienté \textbf{G} constitué des sommets A, B, C, D, E et F. Les sommets représentent les routeurs. Si un sommet X peut transmettre un paquet vers un sommet Y alors on a l'arc: X $\longrightarrow$ Y.


On peut représenter ce graphe:

\begin{center}
\psset{unit=1.5cm,arrowsize=3pt 2}
\begin{pspicture*}(-2.5,-2.2)(2.5,2.2)
\psset{linewidth=.75pt}
%\psgrid[gridcolor=orange]
%%% 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}$}
%}
%%% sommets
\def\ray{2}
\cnodeput*(\ray;90){A}{\bf A} 
\cnodeput*(\ray;150){B}{\bf B}  
\cnodeput*(\ray;210){C}{\bf C}  
\cnodeput*(\ray;-90){D}{\bf D}
\cnodeput*(\ray;-30){E}{\bf E} 
\cnodeput*(\ray;30){F}{\bf F}  

%%% arcs
\ncline{->}{A}{C}  \ncline{->}{A}{D} \ncline{->}{A}{E}
\ncline{->}{B}{A} \ncline{->}{B}{C} \ncline{->}{B}{E} \ncline{->}{B}{F} 
\ncline{->}{C}{E}
\ncline{->}{E}{D} \ncline{->}{E}{F} 
\ncline{->}{F}{D}    
\end{pspicture*} 
\end{center}

%\medskip

\begin{enumerate}
\item
	\begin{enumerate}
		\item On complète le tableau des successeurs et des prédécesseurs du graphe \textbf{G} :

\begin{center}
\begin{tabularx}{0.7\linewidth}{|*{3}{>{\centering \arraybackslash}X|}}\hline
Sommets&Prédécesseurs&Successeurs\\ \hline
A& B & C - D - E\\ \hline
B& -- & A - C - E - F \\ \hline
C& A - B & E\\ \hline
D& A - E - F & --\\ \hline
E& A - B - C & D - F\\ \hline
F& B - E & D \\ \hline
\end{tabularx}
\end{center}

	\item La matrice d'adjacence $M$ du graphe \textbf{G}, les sommets étant rangés par ordre alphabétique est:
		
\begin{center}
$M=\quad
\bordermatrix
{
~\rotatebox{45}{$\blue\curvearrowright$}&\blue  \text A & \blue \text B &\blue  \text  C &\blue  \text D & \blue \text E & \blue \text  F\cr
\blue \text  A & 0 & 0 & 1 & 1 & 1 & 0 \cr
\blue \text  B &  1 & 0 & 1 & 0 & 1 & 1\cr
\blue \text  C &  0 & 0 & 0 & 0 & 1 & 0\cr
\blue \text  D &  0 & 0 & 0 & 0 & 0 & 0\cr
\blue \text  E &  0 & 0 & 0 & 1 & 0 & 1\cr
\blue \text  F &  0 & 0 & 0 & 1 & 0 & 0\cr
}$
\end{center}
		
	\end{enumerate}
\item
	\begin{enumerate}
		\item La calculatrice donne:
		
\begin{center}
$M^3=\quad
\bordermatrix
{
~\rotatebox{45}{$\blue\curvearrowright$}&\blue  \text A & \blue \text B &\blue  \text  C &\blue  \text D & \blue \text E & \blue \text  F\cr
\blue \text  A & 0 & 0 & 0 & 2 & 0 & 1 \cr
\blue \text  B &  0 & 0 & 0 & 3 & 1 & 2\cr
\blue \text  C &  0 & 0 & 0 & 1 & 0 & 0\cr
\blue \text  D &  0 & 0 & 0 & 0 & 0 & 0\cr
\blue \text  E &  0 & 0 & 0 & 0 & 0 & 0\cr
\blue \text  F &  0 & 0 & 0 & 0 & 0 & 0\cr
}$
\end{center}		
		
		\item Le nombre de chemins de longueur 3 allant du sommet B (sommet \no 2) au sommet D (sommet \no 4) est le nombre de la matrice $M^3$ situé à l'intersection de la 2\ieme{} ligne  et de la 4\ieme{} colonne; il s'agit du nombre 3 donc il y a 3 chemins de longueur 3 allant du sommet B au sommet D.
		
Ce sont: B $\rightarrow$ A $\rightarrow$ E $\rightarrow$ D,
B $\rightarrow$ C $\rightarrow$ E $\rightarrow$ D et
B $\rightarrow$ E $\rightarrow$ F $\rightarrow$ D.
		
	\end{enumerate}
\item 
	\begin{enumerate}
		\item %Déterminer la matrice $\widearc{M}$ de la fermeture transitive du graphe \textbf{G}.
La matrice de fermeture transitive de ce graphe est une matrice carrée d'ordre 6;  on met un 1 à l'intersection de la ligne correspondant au sommet X et de la colonne correspondant au sommet Y s'il existe  au moins un chemin allant du sommet X au sommet Y. Sinon on met un 0.

Le graphe \textbf{G} contient 6 sommets donc la matrice de fermeture transitive est\\ 
$\widearc M =M\vee M^{[2]} \vee M^{[3]}\vee M^{[4]}\vee M^{[5]} \vee M^{[6]}$ où $\vee$ désigne la somme booléenne, et $M^{[n]}$ la matrice booléenne de $M^n$, c'est-à-dire la matrice $M^n$ dans laquelle on a remplacé chaque nombre non nul par un 1.

Pour obtenir  $\widearc{M}$, il suffit de calculer $N= M+M^2+M^3+M^4+ M^5+M^6$ et de remplacer dans la matrice $N$ chaque nombre non nul par le nombre 1.

\newpage

La calculatrice donne:

\begin{center}
$N= M+M^2+M^3+M^4+ M^5+M^6=\quad
\bordermatrix
{
~\rotatebox{45}{$\blue\curvearrowright$}&\blue  \text A & \blue \text B &\blue  \text  C &\blue  \text D & \blue \text E & \blue \text  F\cr
\blue \text  A & 0 & 0 & 1 & 5 & 2 & 2 \cr
\blue \text  B &  1 & 0 & 2 & 10 & 4 & 5\cr
\blue \text  C &  0 & 0 & 0 & 2 & 1 & 1\cr
\blue \text  D &  0 & 0 & 0 & 0 & 0 & 0\cr
\blue \text  E &  0 & 0 & 0 & 2 & 0 & 1\cr
\blue \text  F &  0 & 0 & 0 & 1 & 0 & 0\cr
}$
\end{center}

On obtient donc:

\begin{center}
$\widearc{M}=\quad
\bordermatrix
{
~\rotatebox{45}{$\blue\curvearrowright$}&\blue  \text A & \blue \text B &\blue  \text  C &\blue  \text D & \blue \text E & \blue \text  F\cr
\blue \text  A & 0 & 0 & 1 & 1 & 1 & 1 \cr
\blue \text  B &  1 & 0 & 1 & 1 & 1 & 1\cr
\blue \text  C &  0 & 0 & 0 & 1 & 1 & 1\cr
\blue \text  D &  0 & 0 & 0 & 0 & 0 & 0\cr
\blue \text  E &  0 & 0 & 0 & 1 & 0 & 1\cr
\blue \text  F &  0 & 0 & 0 & 1 & 0 & 0\cr
}$
\end{center}		

		
		\item %Que signifie le nombre 1 à l'intersection de la troisième ligne et la sixième colonne de $\widearc{M}$ ?
La 3\ieme{} ligne correspond au sommet C et la 6\ieme{} colonne au sommet F; le nombre 1 à l'intersection de la troisième ligne et la sixième colonne de $\widearc{M}$ signifie qu'il y a au moins un chemin allant de C vers F.		

En regardant la matrice $N$, on peut même dire qu'il n'y en a qu'un seul:\\
C $\longrightarrow$ E $\longrightarrow$ F.		
		
	\end{enumerate}
\item Un chemin hamiltonien est un chemin qui passe une fois et une seule par tous les sommets.

Le chemin {\blue B $\longrightarrow$ A $\longrightarrow$ C $\longrightarrow$ E $\longrightarrow$ F $\longrightarrow$ D} est hamiltonien.


\begin{center}
\psset{unit=1.5cm,arrowsize=3pt 2}
\begin{pspicture*}(-2.5,-2.2)(2.5,2.2)
\psset{linewidth=.75pt}
%\psgrid[gridcolor=orange]
%%% 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}$}
%}
%%% sommets
\def\ray{2}
\cnodeput*(\ray;90){A}{\bf A} 
\cnodeput*(\ray;150){B}{\bf B}  
\cnodeput*(\ray;210){C}{\bf C}  
\cnodeput*(\ray;-90){D}{\bf D}
\cnodeput*(\ray;-30){E}{\bf E} 
\cnodeput*(\ray;30){F}{\bf F}  

%%% arcs
\ncline[linecolor=blue]{->}{A}{C}  \ncline{->}{A}{D} \ncline{->}{A}{E}
\ncline[linecolor=blue]{->}{B}{A} \ncline{->}{B}{C} \ncline{->}{B}{E} \ncline{->}{B}{F} 
\ncline[linecolor=blue]{->}{C}{E}
\ncline{->}{E}{D} \ncline[linecolor=blue]{->}{E}{F} 
\ncline[linecolor=blue]{->}{F}{D}    
\end{pspicture*} 
\end{center}


%Si oui, en indiquer un.
\end{enumerate}

Remarque: comme le sommet B n'a pas de prédécesseur, un chemin hamiltonien doit forcément commencer par B, et comme le sommet D n'a pas de successeur, il doit forcément se terminer par D.

\newpage

\textbf{Partie B}

\medskip

Dans un parc informatique, chaque machine connectée à un réseau peut être identifiée à l'aide d'une adresse IPv4.

\medskip

\begin{enumerate}
\item 
	\begin{enumerate}
		\item Dans la base 2, un octet est constitué de 8 chiffres.

Le plus grand entier noté en base 10 qu'on peut écrire sous la forme d'un octet est le nombre décimal correspondant à $
\overline{11111111}^{2}$ soit\\
$1+2+2^2+2^3+2^4+2^5+2^6 + 2^7 = 1+2+4+8+16+32+64+128=255$.

		\item Une adresse IPv4 étant constituée de 4 octets notés en base 10 et séparés par un point, le nombre maximal d'adresses IPv4 qui peuvent être attribuées est\\
		$255^4 = \np{4228250625}$.
	\end{enumerate}
\end{enumerate}

\medskip

Le routeur C de la partie A gère les connexions réseaux d'un parc informatique de 8
machines étiquetées de 1 à 8.

Le DHCP de ce routeur est paramétré de telle façon qu'il attribue une plage de 49 adresses IPv4 allant de 192.168.1.2 jusqu'à 192.168.1.50.

Les 8 machines sont identifiées grâce aux adresses IPv4 suivantes:

\begin{center}
\begin{tabularx}{0.7\linewidth}{|*{2}{>{\centering \arraybackslash}X|}}\hline
Etiquette de la machine &Adresse IPv4 de la machine\\ \hline
1&192.168.1.2\\ \hline
2& 192.168.1.4\\ \hline
3& 192.168.1.12\\ \hline
4& 192.168.1.49\\ \hline
5& 192.168.1.48\\ \hline
6& 192.168.1.50\\ \hline
7& 192.168.1.5\\ \hline
8& 192.168.1.6\\ \hline
\end{tabularx}
\end{center}

\begin{enumerate}[resume]
\item % Écrire le premier octet commun aux adresses de ces machines sous forme binaire puis sous forme hexadécimale.
Le premier octet commun s'écrit en décimal 192; on écrit 192 en binaire puis en hexadécimal.

$192 = 128 + 64 = 1\times 2^7 + 1\times 2^6 + 0\times 2^5  + 0\times 2^4 + 0\times 2^3 + 0\times 2^2 + 0\times 2^1 + 0\times 2^0= \overline{11000000}^{2}$

$192 = 12\times 16 + 0\times 16^{0}= \overline{\texttt{C0}}^{16}$

\end{enumerate}

%%%%%%%%%  EXERCICE 2 manquant
\bigskip

\textbf{\large Exercice 2 \hfill 5 points}

\medskip

Le spam, courriel indésirable ou pourriel, est une communication électronique non sollicitée, en premier lieu via le courrier électronique. Il s'agit en général d'envois en grande quantité effectués à des fins publicitaires.

Un étudiant en BTS SIO a développé un logiciel anti spam. Le filtre mis en place par l'étudiant se base sur les trois variables booléennes suivantes :

\setlength\parindent{9mm}
\begin{itemize}
\item[$\bullet~~$] $a$ l'objet du message contient au moins un terme douteux (gratuit, offre, promotion, gagner ...), $\overline{a}$ l'objet du message ne contient aucun terme douteux ;
\item[$\bullet~~$] $b$ le corps du message contient des images ou des hyperliens, $\overline{b}$ le corps du message ne contient ni images, ni hyperliens ;
\item[$\bullet~~$] $c$ les messages de l'expéditeur sont rarement lus, $\overline{c}$ les messages de l'expéditeur sont lus fréquemment.
\end{itemize}
\setlength\parindent{0mm}

Avec ce logiciel, un courriel est considéré comme indésirable si :

%\setlength\parindent{9mm}
\begin{list}{\textbullet}{}
\item l'objet du message contient au moins un terme douteux avec un corps du message
contenant des images ou des hyperliens ;

ou
\item l'objet du message ne contient aucun terme douteux et les messages de l'expéditeur sont rarement lus ;

ou

\item les messages de l'expéditeur sont rarement lus et le corps du message ne contient ni images, ni d'hyperliens ;
\end{list}
%\setlength\parindent{0mm}

\medskip

\begin{enumerate}
\item %Traduire chaque condition par une expression booléenne en fonction des variables $a$, $b$ et $c$ puis déterminer l'expression booléenne $E$ traduisant les conditions pour qu'un courriel soit considéré comme indésirable.
Le \og et \fg{} se traduit en produit et le \og ou \fg{} se traduit en somme.

\begin{list}{\textbullet}{Donc:}
\item l'objet du message contient au moins un terme douteux (appelé $a$) avec un corps du message contenant des images ou des hyperliens  (appelé $b$), se traduit en $a.b$,

\item ou, se traduit par $+$,
\item l'objet du message ne contient aucun terme douteux (appelé $\overline{a}$) et les messages de l'expéditeur sont rarement lus (appelé $c$), se traduit en $\overline{a}.c$;

\item ou, se traduit par $+$,

\item les messages de l'expéditeur sont rarement lus (appelé $c$) et le corps du message ne contient ni images, ni d'hyperliens (appelé $\overline{b}$), se traduit en $\overline{b}.c$.
\end{list}

Donc $E = a.b + c.\overline{a\phantom{b}} + \overline{b}.c$.

\smallskip

\item 
	\begin{enumerate}
		\item On présente $E$ dans une table de Karnaugh.
		
\begin{multicols}{3}

\begin{center}
$a.b$
\end{center}

{\footnotesize
%\begin{tabular}{|c|*4{p{4pt}}|}
$\begin{array}{|*5{c|}}
\hline
$\diagbox{$a$}{$bc$}$ & 00 &  \; 01 \;  & 11 & 10 \\
 \hline
0 & & & & \\
 \hline
1 & &   & \blue 1  & \blue 1  \\
 \hline
\end{array}$
}

\columnbreak

\begin{center}
$\overline{a\vphantom{b}}.c$
\end{center}

{\footnotesize
$\begin{array}{|*5{c|}}
\hline
$\diagbox{$a$}{$bc$}$ & 00 & 01  & 11 & 10 \\
 \hline
0 & & \blue 1 & \blue 1 &  \\
 \hline
1 & & & & \\
 \hline
\end{array}$
}

\columnbreak

\begin{center}
$\overline{b}.c$
\end{center}

{\footnotesize
%\setlength{\arraycolsep}{2pt}
$\begin{array}{|*5{c|}}
\hline
$\diagbox{$a$}{$bc$}$ & 00 & 01  & 11 & 10 \\
 \hline
0 & &  \blue 1 & & \\
 \hline
1 & &  \blue 1 & & \\
 \hline
\end{array}$
}
\end{multicols}

%\bigskip


\begin{center}
$E=a.b+\overline{a\vphantom{b}}.c + \overline{b}.c$
\end{center}

\begin{center}
%\renewcommand{\arraystretch}{1}
$\begin{array}{|*5{c|}}
\hline
$\diagbox{$a$}{$bc$}$ & 00 & 01  & 11 & 10  \\
 \hline
0 & &\blue 1  & \blue 1 &  \\
 \hline
1 &   & \blue 1  & \blue 1  & \blue 1 \\
 \hline
\end{array}$
\end{center}
		
		\item Un courriel, ayant comme objet \og promotion : une réduction de 50\,\% ... \fg{} (appelé $a$), et dont les messages de l'expéditeur sont lus fréquemment (appelé $\overline c$), est donc codé $a.\overline c$. On le représente dans une table de Karnaugh:
		
\begin{center}
$a.\overline c$
\end{center}

\begin{center}
%\renewcommand{\arraystretch}{1}
$\begin{array}{|*5{c|}}
\hline
$\diagbox{$a$}{$bc$}$ & 00 & 01  & 11 & 10  \\
 \hline
0 & &  &  &  \\
 \hline
1 &  \red 1 &   &   & \blue 1 \\
 \hline
\end{array}$
\end{center}		
		
En comparant avec la table de $E$, on peut ne pas considérer ce courriel comme indésirable.		
		
		\item En utilisant  la table de Karnaugh, on déduit l'expression simplifiée de $E$.
		
		\begin{pspicture}(-5,-2.5)(6,2)
\uput[r](-4.5,1){$E=a.b+\overline{a\vphantom{b}}.c + \overline{b}.c$}
\psframe[linecolor=blue,linearc=5pt,cornersize=absolute](3.4,-1.2)(4.8,-0.6)%%% a
\psline[linecolor=blue](4.8,-0.8)(5.4,-0.8) \uput[r](5.4,-0.75){\blue $a.b$}
\psframe[linearc=5pt,cornersize=absolute](2.4,-1.3)(4.2,0.6)%%% c
\psline(3,-1.3)(3,-1.8) \uput[d](3,-1.8){$c$}
\begin{tabular}{|*5{c|}}
\hline
\diagbox{$a$}{$bc$} & 00 & 01  & 11 & 10  \\
 \hline
0 & &\blue 1  & \blue 1 &   \rule[-12pt]{0pt}{30pt}\\
 \hline
1 & & \blue 1  & \blue 1  & \blue 1  \rule[-12pt]{0pt}{30pt}\\
 \hline
\end{tabular}
\end{pspicture}

Donc $E=c+a.b$.

	\end{enumerate}
\item La règle $E$ pour considérer un courriel comme indésirable est:

\begin{list}{\textbullet}{}
\item Les messages de l'expéditeur sont rarement lus ($c$),  

ou ($+$)

\item l'objet du message contient au moins un terme douteux ($a$) et ($\times$)  le corps du message contient des images ou des hyperliens ($b$).
\end{list}

\item En partant de la table de Karnaugh de $E$, on écrit celle de $\overline{E}$ par complément:

\begin{pspicture}(-1,-2.5)(6,2.2)
%\psgrid[gridcolor=orange]
\uput[r](8,0){Donc $\overline{E} = \overline{b}.\overline{c\vphantom{b}} + \overline{a\vphantom{b}}.\overline{c\vphantom{b}}$.}
\psframe[linecolor=blue,linearc=5pt,cornersize=absolute](1.8,-0.2)(4.8,0.5)%%% 
\psline[linecolor=blue](4.8,0.2)(5.4,0.2) \uput[r](5.4,0.25){\blue $\overline a. \overline c$}
\psframe[linearc=5pt,cornersize=absolute](1.9,-1.3)(2.3,0.6)%%% 
\psline(2.1,-1.3)(2.1,-1.8) \uput[d](2.1,-1.8){$\overline{b}.\overline{c\vphantom{b}}$}
\begin{tabular}{|*5{c|}}
\hline
\diagbox{$a$}{$bc$} & 00 & 01  & 11 & 10  \\
 \hline
0 & \red 1 &  &  & \red 1  \rule[-12pt]{0pt}{30pt}\\
 \hline
1 & \red 1 &   &   &   \rule[-12pt]{0pt}{30pt}\\
 \hline
\end{tabular}
\end{pspicture}

\medskip

En utilisant les formules $\overline{\left (x+y\right )}=\overline{x}.\overline{y}$ et $\overline{\left (x.y\right )}=\overline{x}+\overline{y}$, on retrouve ce résultat:

$\overline{E} = \overline{c+a.b}
=\overline{c\vphantom{b}}.\overline{\left (a.b\right )}
=\overline{c\vphantom{b}}.\left (\overline{a\vphantom{b}}+\overline{b}\right )
=\overline{c\vphantom{b}}.\overline{a\vphantom{b}}+\overline{c\vphantom{b}}.\overline{b}$

\end{enumerate}

%\bigskip
\newpage

\textbf{\large Exercice 3 : Codage de Hill\hfill 5 points}

\medskip

Dans le tableau suivant, on associe à chaque lettre de l'alphabet, en majuscule, son rang dans l'alphabet en commençant par $0$. 

\begin{center}
\begin{tabularx}{\linewidth}{|*{13}{>{\centering \arraybackslash}X|}}\hline
A	&B	&C	&D	&E	&F	&G	&H	&I	&J	&K	&L	&M\\ \hline
0	&1	&2	&3	&4	&5	&6	&7	&8	&9	&10	&11	&12\\ \hline\hline
N	&O	&P	&Q	&R	&S	&T	&U	&V	&W	&X	&Y	&Z\\ \hline
13	&14	&15	&16	&17	&18	&19	&20	&21	&22	&23	&24	&25\\ \hline
\end{tabularx}
\end{center}

%La procédure pour chiffrer un message est décrite dans l'exemple ci-dessous:
%
%Pour chiffrer le message \og CARTES\fg{} avec la clé de chiffrement  $W= \begin{pmatrix}1&2& 1 \\2&1& 3\\2&4&2\end{pmatrix}$ :
%
%\medskip
%
%\starredbullet~On remplace chaque lettre par son rang : C par 2, A par 0, R par 17, T par 19, E par 4 et S par 18.
%
% On obtient ainsi une matrice à 3 colonnes $M= \begin{pmatrix}2&0&17\\19&4&18\end{pmatrix}$;
% 
%\starredbullet~On effectue le produit matriciel $M \times W$ ; on a $M\times W = \begin{pmatrix}36&72&36\\63&114&67\end{pmatrix}$ ;
%
%\starredbullet~On remplace chaque coefficient de la matrice $M \times W$ par le reste de sa division euclidienne par 26. 
%
%Ce qui revient à trouver, pour chaque coefficient, l'unique entier compris entre 0 et 25 qui lui est congru modulo 26.
%
%On a $36 \equiv 10\,\, [26]\,,\quad 72 \equiv20 \,\,[26],\quad 63 \equiv 11 \,\,[26],\quad 114 \equiv 10 \,\,[26],\quad 67 \equiv 15\, \,[26]$ ;
%
%Ainsi on obtient la matrice $\begin{pmatrix}10&20&10\\11 &10& 15\end{pmatrix}$ ;
%
%\starredbullet~On remplace chaque nouveau coefficient de  $M\times W$ par la lettre correspondante ;
%
%\starredbullet~On obtient donc  $\begin{pmatrix}\text{K}&\text{U}&\text{K}\\\text{L}&\text{K}&\text{P}\end{pmatrix}$ ;
%
%\starredbullet~Donc le message chiffré est \og KUKLKP \fg.

\bigskip

\textbf{Partie A }

\medskip

Dans cette partie, on considère la clé de chiffrement  $W= \begin{pmatrix}1&2&1\\2&1& 3\\2&4&2\end{pmatrix}$.

Cette clé permet de chiffrer le mot \og BUR \fg{} en \og XMR \fg.

\medskip

\begin{enumerate}
\item Le message \og JUA \fg{} correspond aux nombres 9 -- 20 -- 0, donc à la matrice 
$M=
\begin{pmatrix}
9 & 20 & 0
\end{pmatrix}$.

$M\times W =
\begin{pmatrix}
49 & 38 & 69
\end{pmatrix}$
ce qui donne pour restes modulo 26:
$\begin{pmatrix}
23 & 12 & 17
\end{pmatrix}$.

Cette matrice correspond à \og XMR \fg{} donc le message chiffré est \og XMR \fg{}.

\item% Que peut-on remarquer ? 
Les deux séquences \og BUR \fg{} et \og JUA \fg{} correspondent au même message chiffré \og XMR \fg{}; la clé de chiffrement n'est donc pas bonne. 
%Que pensez-vous de cette clé de chiffrement?
\end{enumerate}

\bigskip

\textbf{Partie B}

\medskip

Dans cette partie, on considère la clé de chiffrement  $W = \begin{pmatrix}11&n&14\\7& 9& 21\\17& 0&3\end{pmatrix}$, où $n$ est un entier naturel compris entre 15 et 25.

On sait que cette clé permet de chiffrer le mot \og GEL\fg{} en \og VMT \fg.

\medskip

\begin{enumerate}
\item %Vérifier que $6n + 36 \equiv 12 \;(\text{mod}\,\, 26)$.
Le mot \og GEL\fg{} correspond aux nombres 6 -- 4 -- 11 donc à la matrice
$M=
\begin{pmatrix}
6 & 4 & 11
\end{pmatrix}$.

$M\times W = 
\begin{pmatrix}
281 & 6n+36 & 201
\end{pmatrix}$

Le mot \og VMT \fg{} correspond à 21 -- 12 -- 19 soit à la matrice
$\begin{pmatrix}
21 & 12 & 19
\end{pmatrix}$.

\begin{list}{\textbullet}{}
\item $281 = 10\times 26 + 21$ donc $281$ correspond au nombre 21 donc à la lettre V;
\item $201 = 7\times 26 + 19$ donc $201$ correspond au nombre 19 donc à la lettre T;
\end{list}

Pour que \og GEL \fg{} se code en \og VMT \fg{}, il faut donc que $6n+36$ corresponde à la lettre M, donc corresponde au nombre 12; il faut donc que 
$6n + 36 \equiv 12 \;(\text{mod } 26)$.

\item %Déterminer la valeur de l'entier naturel $n$.
On cherche tous les restes de la division de $6n+36$ dans la division par 26, pour $n$ variant entre 15 et 25:


\begin{center}
$\begin{array}{|*{12}{c|}}
\hline
n & 15 & 16 & 17 & 18 & 19 & 20 & 21 & 22 & 23 & 24 & 25\\
\hline
6n+36 & 126 & 132 & 138 & 144 & 150 & 156 & 162 & 168 & 174 & 180 & 186\\
\hline
\text{restes} & 22 & 2 & 8 & 14 & 20 & 0 & 6 & \blue 12 & 18 & 24 & 4\\
\hline
\end{array}$
\end{center}

Pour $n=22$, on a: $6n+36 \equiv 12\;(\text{mod }26)$, donc la valeur de $n$ cherchée est 22.

\end{enumerate}


\end{document}
