\documentclass[11pt]{article}
\usepackage[T1]{fontenc}
\usepackage[utf8]{inputenc} 
\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}
%Tapuscrit : Denis Vergès
%Relecture : 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 17 mai 2023},
allbordercolors = white,
pdfstartview=FitH}  
\usepackage[french]{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{17 mai 2023}}
\pagestyle{fancy}
\thispagestyle{empty}
\marginpar{\rotatebox{90}{\textbf{A. P{}. M. E. P{}.}}}

\begin{center} {\Large \textbf{\decofourleft~BTS Métropole 17 mai 2023~\decofourright\\[7pt]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{Exercice 1 \hfill 5 points}

\medskip

\emph{Cet exercice est un questionnaire à choix multiple.\\
Aucune justification n'est demandée.\\ Pour chaque question, une seule affirmation est exacte.\\
Recopier sur la copie le numéro de la question et la lettre correspondante à la réponse exacte.\\
Une réponse exacte vaut 1 point.\\
Une réponse fausse ou une absence de réponse ne sera pas pénalisée.}

\bigskip

\textbf{Question 1.} On considère le nombre \np{2023} écrit en base dix. 

Son écriture en base seize est  
\begin{center}
\begin{tabularx}{0.75\linewidth}{|*{3}{>{\centering \arraybackslash}X|}}\hline
A\::\quad  E67& B\: \quad  7E7& C\::\quad  6E7\\ \hline
\end{tabularx}
\end{center}

\medskip

\textbf{Question 2.} On considère les nombres, écrits en base deux, $1010_2$ et $1011_2$. La somme écrite en base deux de ces nombres est égale à
\begin{center}
\begin{tabularx}{0.75\linewidth}{|*{3}{>{\centering \arraybackslash}X|}}\hline
A\::\quad $1111_2$& B\: \quad $10011_2$& C\::\quad $10101_2$\\ \hline
\end{tabularx}
\end{center}

\medskip

\textbf{Question 3.} On considère la relation binaire $\mathcal{R}$ définie sur $\R$ par : 
\[x \mathcal{R} y \iff  \left (\strut xy \leqslant 0 \wedge x \ne y\right ) .\]

On a
\begin{center}
\begin{tabularx}{0.75\linewidth}{|*{3}{>{\centering \arraybackslash}X|}}\hline
A\::\quad $(-3) \mathcal{R} 3$& B\: \quad $(-3) \mathcal{R} (-4)$& C\::\quad $(-3) \mathcal{R} (-3)$\\ \hline
\end{tabularx}
\end{center}

\medskip

\textbf{Question 4.} La relation binaire $\mathcal{R}$ définie à la question 3 est 

\begin{center}
\begin{tabularx}{0.75\linewidth}{|*{3}{>{\centering \arraybackslash}X|}}\hline
A\::\quad réflexive& B\: \quad symétrique& C\::\quad transitive\\ \hline
\end{tabularx}
\end{center}

\medskip

\textbf{Question 5.} Une application $f$ d'un ensemble $E$ dans un ensemble $F$ est définie par le diagramme ci-dessous.

\psset{xunit=1.2cm,yunit=0.8cm,arrowsize=2pt 3}
\begin{center}
\begin{pspicture}(12,8)
\psellipse(3,4)(1.5,4) \psellipse(7,4)(1.25,3.5)
\uput[u](3,8){$E$} \uput[u](7,8){$F$} 
\psdots(3,1)(3,2)(3,3)(3,4)(3,5)(3,6)(3,7)
\psdots(7,2.5)(7,3.5)(7,4.5)(7,5.5)(7,6.5)
\uput[l](3,1){7} \uput[l](3,2){6} \uput[l](3,3){5} \uput[l](3,4){4} 
\uput[l](3,5){3} \uput[l](3,6){2} \uput[l](3,7){1} \uput[r](7,2.5){$e$} 
\uput[r](7,3.5){$d$} \uput[r](7,4.5){$c$} \uput[r](7,5.5){$b$} \uput[r](7,6.5){$a$} 
\psline[ArrowInside=->](3,1)(7,2.5)\psline[ArrowInside=->](3,2)(7,2.5)
\psline[ArrowInside=->](3,3)(7,3.5)\psline[ArrowInside=->](3,4)(7,4.5)
\psline[ArrowInside=->](3,5)(7,5.5)\psline[ArrowInside=->](3,6)(7,5.5)
\psline[ArrowInside=->](3,7)(7,6.5)
\end{pspicture}
\end{center}

L'application ainsi définie est

\begin{center}
\begin{tabularx}{\linewidth}{|*{3}{>{\centering \arraybackslash}X|}}\hline
A\::\quad injective et non surjective& B\: \quad surjective et non injective& C\::\quad bijective\\ \hline
\end{tabularx}
\end{center}

\bigskip

\textbf{Exercice 2 \hfill 5 points}

\medskip

\textbf{Partie A}

\medskip

On considère le graphe orienté G comportant 3 sommets notés A, B et C dont la matrice
 d'adjacence est $P$, où $P = \begin{pmatrix}1&0&1\\0&0&1\\1&0&0\end{pmatrix}$.

\medskip

\begin{enumerate}
\item Dessiner une représentation du graphe $G$.
\item 
	\begin{enumerate}
		\item Calculer la matrice $P^2$.
		\item Combien de chemins de longueur 2 ont pour origine B ?
	\end{enumerate}
\item Déterminer la matrice de fermeture transitive $\hat{P}$ et le graphe de la fermeture transitive de $G$.
\end{enumerate}

\bigskip

\textbf{Partie B}

\medskip

Dans un graphe orienté, on définit:

\begin{itemize}
\item le \textbf{degré entrant} d'un sommet comme étant le nombre d'arcs menant à ce sommet.
\item le \textbf{degré sortant} d'un sommet comme étant le nombre d'arcs issus de ce sommet.
\end{itemize}

\medskip

\begin{enumerate}
\item 
	\begin{enumerate}
		\item Calculer le degré entrant du sommet C du graphe $G$ défini dans la partie A.
		\item Calculer le degré sortant du sommet C du graphe $G$ défini dans la partie A.
	\end{enumerate}	
\item On étudie dans cette question les graphes orientés à trois sommets numérotés  de 1 à 3.

On considère l'algorithme ci-dessous écrit en langage naturel où Degré\_sortant désigne une fonction de paramètres $M$ et $s$, $M$ étant une matrice à 3 lignes et 3 colonnes et $s$ un entier compris entre 1 et 3.

Le coefficient de la matrice $M$ situé ligne $i$ colonne $j$ est noté $m_{ij}$.

\begin{center}
\begin{tabular}{|l|}\hline
\textbf{Fonction} Degré\_sortant $(M, s)$\\
\qquad deg $\gets 0$\\
\qquad Pour $j$ allant de 1 à 3 \:\textbf{Faire}\\

\qquad \qquad \textbf{Si} $m_{sj}$ \ldots \ldots \textbf{Faire}\\
\qquad \qquad  \ldots \ldots\\
\qquad \qquad  \textbf{Fin de Si}\\
\qquad \textbf{Fin de Pour}\\
\textbf{Retourner} deg\\ \hline
\end{tabular}
\end{center}

Compléter cet algorithme pour que la fonction renvoie le degré sortant du sommet
numéroté $s$ dans un graphe dont la matrice d'adjacence est $M$. 
\end{enumerate}

\bigskip

\textbf{Exercice 3 \hfill 10 points}

\medskip

Une entreprise décide de mettre en place une authentification à plusieurs étapes permettant à ses employés d'accéder aux services en ligne qu'elle propose.

\bigskip

\textbf{Partie A}

\medskip

La première authentification consiste à utiliser un mot de passe. 

À la première connexion, l'utilisateur doit créer un mot de passe de 8 à 16 caractères. Ces caractères peuvent être des lettres majuscules de l'alphabet ou des chiffres ou des caractères spéciaux (?,\&, \! etc.).

Pour être valide, un mot de passe doit remplir au moins l'une des trois conditions suivantes :
\begin{itemize}
\item il contient au moins trois chiffres et au moins deux caractères spéciaux ;
\item il contient moins de trois chiffres, au moins deux caractères spéciaux et au moins dix lettres;
\item il contient moins de deux caractères spéciaux et au moins dix lettres.
\end{itemize}

\medskip

\begin{enumerate}
\item Les mots de passe suivants sont-ils valides ? Justifier.
\begin{center}ABCDABCD\text{?}\# \qquad STU27ABCABCDE\& \end{center}
\end{enumerate}

On définit les variables booléennes $a$,\: $b$ et $c$ de la manière suivante :

\begin{itemize}
\item[$\bullet~~$] $a$ lorsque le mot de passe contient au moins trois chiffres, $\barre{a}$ sinon ;
\item[$\bullet~~$] $b$ lorsque le mot de passe contient au moins deux caractères spéciaux, $\barre{b}$ sinon ; 
\item[$\bullet~~$] $c$ lorsque le mot de passe contient au moins dix lettres, $\barre{c}$ sinon.
\end{itemize}

\begin{enumerate}[resume]
\item
	\begin{enumerate}
		\item On appelle $E$ l'expression booléenne qui traduit la validité d'un mot de passe.

Traduire chacune des conditions de validité d'un mot de passe à l'aide des variables $a, b$ et $c$, puis en déduire une expression de $E$.
		\item Représenter $E$ dans un tableau de Karnaugh, puis en déduire une expression simplifiée de $E$ sous la forme d'une somme de deux termes.
		\item Traduire par une phrase l'expression simplifiée de $E$.
	\end{enumerate}
\item Déterminer l'expression booléenne $\barre{E}$ négation de $E$.
\end{enumerate}

\bigskip

\textbf{Partie B}

\medskip

Pour la seconde authentification, le serveur de l'entreprise envoie à l'utilisateur un mot de passe codé qu'il devra décoder.

Le serveur de l'entreprise code un mot de passe de la façon suivante:

\begin{itemize}
\item à chaque lettre de l'alphabet, on associe son rang $x$ selon le tableau ci-dessous

\smallskip

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

\smallskip

\item on fixe une clé $(a\,; b)$, où $a$ et $b$ sont deux entiers naturels compris entre 0 et 25;
\item on calcule le reste $y$ de la division de $ax+b$ par 26; on détermine ainsi le plus petit entier naturel $y$ vérifiant $y \equiv ax+b\;[26]$;
\item on cherche ensuite la lettre de l'alphabet dont le rang est $y$;
\item cette lettre code la lettre donnée au départ.
\end{itemize}

\begin{enumerate}
\item Le serveur de l'entreprise utilise la clé $(9\,; 15)$.

\begin{enumerate}
\item Montrer que la lettre C est codée par la lettre H.
\item Par quelle lettre est codée la lettre E?
\end{enumerate}

\item L'utilisateur veut décoder la lettre V associée à l'entier $y=21$. Pour cela il doit déterminer le plus petit entier naturel $x$ vérifiant $21 \equiv 9x+15\;[26]$.

\begin{enumerate}
\item Déterminer un entier $c$ vérifiant $9\times c \equiv 1 \; [26]$. 
\item Montrer que si $21 \equiv 9x+15\;[26]$ alors $x\equiv 18\;[26]$.
\item Décoder la lettre V.
\end{enumerate}

\end{enumerate}

\end{document}