%!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{enumitem} \usepackage{pifont} \usepackage{textcomp} \newcommand{\euro}{\eurologo} %Tapuscrit : Denis Vergès \usepackage{pst-plot,pst-text,pst-node,pst-tree} \newcommand{\R}{\mathbb{R}} \newcommand{\N}{\mathbb{N}} \newcommand{\D}{\mathbb{D}} \newcommand{\Z}{\mathbb{Z}} \newcommand{\Q}{\mathbb{Q}} \newcommand{\C}{\mathbb{C}} \setlength{\textheight}{23,5cm} \newcommand{\vect}[1]{\mathchoice% {\overrightarrow{\displaystyle\mathstrut#1\,\,}}% {\overrightarrow{\textstyle\mathstrut#1\,\,}}% {\overrightarrow{\scriptstyle\mathstrut#1\,\,}}% {\overrightarrow{\scriptscriptstyle\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)$} \setlength{\voffset}{-1,5cm} \usepackage{fancyhdr} \usepackage{hyperref} \hypersetup{% pdfauthor = {APMEP}, pdfsubject = {BTS}, pdftitle = {Métropole 11 mai 2017}, 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{11 mai 2017}} \renewcommand \footrulewidth{.2pt} \pagestyle{fancy} \thispagestyle{empty} \marginpar{\rotatebox{90}{\textbf{A. P{}. M. E. P{}.}}} \begin{center} {\Large \textbf{\decofourleft~BTS Métropole 11 mai 2017~\decofourright\\Services informatiques aux organisations}} \vspace{0,25cm} \textbf{Épreuve obligatoire} \end{center} \vspace{0,25cm} \textbf{Exercice 1 \hfill 8 points} \medskip Cet exercice envisage deux. problèmes relatifs à l'équipement d'une salle informatique d'une entreprise. Les deux parties sont indépendantes. \medskip \begin{center} \textbf{Partie 1 : Choix d'un réseau} \end{center} Le réseau informatique qui équipera la salle doit satisfaire au moins l'une des conditions suivantes : \setlength\parindent{9mm} \begin{itemize} \item[$\bullet~~$] le réseau compte 5 postes ou plus et il existe un poste qui ne reçoit pas de données en entrée \item[$\bullet~~$] il existe un poste qui ne reçoit pas de données en entrée, et le réseau compte strictement moins de 5 postes, et il comporte strictement plus de 12 connexions ; \item[$\bullet~~$] le réseau comporte 12 connexions ou moins. \end{itemize} \setlength\parindent{0mm} \smallskip On définit les variables booléennes suivantes: \setlength\parindent{9mm} \begin{itemize} \item[$\bullet~~$] $a = 1$ si le réseau compte 5 postes ou plus, $a = 0$ sinon; \item[$\bullet~~$] $b = 1$ s'il existe un poste qui ne reçoit pas de données en entrée, $b = 0$ sinon; \item[$\bullet~~$] $c = 1$ si le réseau comporte 12 connexions ou moins, $c = 0$ sinon. \end{itemize} \setlength\parindent{0mm} \medskip \begin{enumerate} \item Cette question est une question à choix multiple. Une seule réponse est correcte. Recopier sur la copie seulement la réponse correcte. On ne demande pas de justification. Parmi les quatre phrases suivantes, donner celle qui traduit la variable $\overline{b}$ : \setlength\parindent{9mm} \begin{itemize} \item réponse A : \og il existe un poste qui reçoit des données en entrée \fg{} ; \item réponse B : \og tout poste reçoit des données en entrée \fg{} ; \item réponse C : \og il existe un poste qui envoie des données en sortie \fg{} ; \item réponse D : \og aucun poste ne reçoit des données en entrée \fg. \end{itemize} \setlength\parindent{0mm} \item Donner l'expression booléenne E traduisant les critères voulus pour un réseau informatique. \item À l'aide d'un tableau de Karnaugh ou par des calculs, exprimer $E$ comme somme de deux variables booléennes. \item Traduire les critères de sélection simplifiés, à partir de l'expression obtenue à la question 3. \item Un réseau dans lequel 2 postes ne reçoivent pas de données en entrée et qui comporte 15 connexions répond-il aux critères voulus ? Justifier la réponse. \end{enumerate} \begin{center} \textbf{Partie 2 : Étude des connexions}\end{center} \parbox{0.65\linewidth}{La salle informatique doit comprendre cinq postes numérotés de 1 à 5 et branchés en réseau selon le graphe orienté ci-contre. Dans ce graphe, une flèche d'un poste A vers un poste B traduit le fait que l'on peut envoyer des données de A vers B. \smallskip \begin{enumerate} \item Donner la matrice d'adjacence $M$ de ce graphe en prenant les numéros des postes dans l'ordre croissant. \end{enumerate}}\hfill \parbox{0.33\linewidth}{\psset{unit=1cm,arrowsize=2pt 3} \begin{pspicture}(4,3) \rput(0.5,0.5){\circlenode{A}{2}} \rput(2,0.5){\circlenode{B}{1}} \rput(3.5,0.5){\circlenode{C}{4}} \rput(3.5,2.5){\circlenode{D}{5}} \rput(0.5,2.5){\circlenode{E}{3}} \ncline{->}{B}{A}\ncline{->}{B}{C} \ncarc[arcangle=30]{->}{A}{E}\ncarc[arcangle=30]{->}{E}{A} \ncarc[arcangle=30]{->}{C}{D}\ncarc[arcangle=30]{->}{D}{C} \nccircle[angleA=180]{->}{A}{0.25cm} \nccircle[angleA=180]{->}{B}{0.25cm}\nccircle[angleA=180]{->}{C}{0.25cm}\nccircle[nodesep=0pt]{<-}{D}{0.25cm}\nccircle[nodesep=0pt]{<-}{E}{0.25cm} \end{pspicture} } \begin{enumerate}[resume] \item Déterminer la matrice $\hat{M}$ de la fermeture transitive de ce graphe. \item Pour permettre l'envoi de données entre les postes, même en cas de défaillance d'une connexion on utilise la fermeture transitive du graphe. Dessiner sur la copie le graphe correspondant à cette fermeture transitive. \end{enumerate} \vspace{0,5cm} \textbf{Exercice 2\hfill 7 points} \medskip Le but de cet exercice est d'étudier, sur des exemples numériques simples, deux variantes d'une méthode de cryptage inventée par Gilbert Vernam en 1917, et appelée \og masque jetable \fg. Dans tout l'exercice, on note respectivement $M$ le mot initial, $K$ la clé de cryptage et $Y$ le mot crypté. Les trois nombres $M$, $K$, $Y$ sont des entiers naturels. \emph{Les deux parties de cet exercice sont indépendantes} \medskip \begin{center}\textbf{Partie 1 : Masque jetable}\end{center} La méthode décrite dans cette partie utilise le connecteur logique \og \emph{xor} \fg, appelé \og ou exclusif \fg, qui est défini par la table de vérité suivante : \begin{center} \begin{tabularx}{0.5\linewidth}{|*{3}{>{\centering \arraybackslash}X|}}\hline $P$ &$Q$ &$P\: xor\: Q$\\ \hline 0 &0 &0\\ \hline 0 &1 &1\\ \hline 1 &0 &1\\ \hline 1 &1 &0\\ \hline \end{tabularx} \end{center} Par exemple les deux premières lignes signifient que $0\: xor\: 0 = 0$ et que $0\: xor\: 1 = 1$. \medskip \begin{enumerate} \item Recopier intégralement la table de vérité ci-après et compléter la dernière colonne. \begin{center} \begin{tabularx}{0.7\linewidth}{|*{3}{>{\centering \arraybackslash}X|}c|}\hline $P$ &$Q$ &$P xor Q$&$(P\: xor\: Q) \:xor\: Q$\\ \hline 0 &0 &0&\\ \hline 0 &1 &1&\\ \hline 1 &0 &1&\\ \hline 1 &1 &0&\\ \hline \end{tabularx} \end{center} \item Parmi les quatre propositions $P$, $Q$, $(P\: xor\: Q)$ et $((P\: xor\: Q)\: xor\: Q)$, deux sont équivalentes. À l'aide de la table 2 complétée, déterminer lesquelles, en expliquant la réponse. \end{enumerate} Dans la suite de l'exercice, on note ab l'écriture du nombre entier $a$ en base $b$. \begin{enumerate}[resume] \item Donner la représentation binaire de l'entier qui s'écrit $26_{10}$ en décimal. \item Soit $M$ et $K$ deux entiers naturels écrits en binaire, tels que la longueur de l'écriture de $K$ est supérieure ou égale à celle de $M$. Pour crypter le mot $M$ avec la clé $K$, on procède comme suit : pour chaque chiffre $m$ du mot initial $M$, on considère le chiffre $k$ de la clé $K$ qui a la même position que $m$ dans l'écriture. On obtient alors le chiffre $y$ du mot crypté $Y$ qui a la même position que $m$ dans l'écriture du mot initial $M$, par la relation : $y = m \:xor\: k$. L'écriture binaire du mot crypté $Y$ est la juxtaposition dans le même ordre des chiffres $y$ calculés pour chaque chiffre $m$ du mot $M$. \end{enumerate} \begin{center} \begin{tabularx}{\linewidth}{|X|}\hline \emph{Exemple }: avec $M = 01_2$ et $K = 10_2$\\ \begin{itemize} \item Avec le chiffre de rang 1 en partant de la droite : $m = 1$ et $k = 0$ \item avec le chiffre de rang 2 : $m = 0$ et $k = 1$ ; donc $y = 0 \:xor\: 1 = 1$. \end{itemize}\\ Donc le mot crypté est $Y = 11_2$ \\ \hline \end{tabularx} \end{center} \smallskip \textbf{Question} : avec le mot initial $M = 011_2$ et la clé $K = 101_2$, déterminer le mot crypté~$Y$. \smallskip \emph{Remarque} : d'après la question 2, le décryptage s'effectue de la même manière que le cryptage. \begin{center}\textbf{Partie 2 : Masque jetable hexadécimal}\end{center} \medskip Cette partie envisage le cryptage de nombres entiers écrits dans le système hexadécimal. Les chiffres hexadécimaux sont notés 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, F. \medskip \begin{enumerate} \item Questions préliminaires \begin{enumerate} \item Donner la représentation en hexadécimal de l'entier binaire $1011101_2$. \item Calculer en travaillant dans le système hexadécimal les sommes $7_{16} + 4_{16}$ et $\text{A}_{16} + \text{C}_{16}$. \end{enumerate} \item Soit $M$ et $K$ deux entiers naturels écrits en hexadécimal, tels que la longueur de l'écriture de $K$ est supérieure ou égale à celle de $M$, et tels que l'écriture de $K$ ne comporte aucun chiffre $0$. Pour crypter le mot $M$ avec la clé $K$, on procède comme suit : pour chaque chiffre $m$ du mot initial $M$, on considère le chiffre $k$ de la clé $K$ qui a la même position que $m$ dans l'écriture. On obtient alors le chiffre $y$ du mot crypté $Y$ qui a la même position que $m$ dans l'écriture du mot initial $M$, de la façon suivante : $y$ est le chiffre hexadécimal des unités de la somme $m + k$. Le mot crypté $Y$ est déterminé en hexadécimal par la juxtaposition dans le même ordre des chiffres $y$ calculés pour chaque chiffre $m$ du mot $M$. \begin{center} \begin{tabularx}{\linewidth}{|X|}\hline \emph{Exemple} : avec $M =49_{16}$ et $K = 19_{16}$ \begin{itemize} \item Avec le chiffre de rang 1 en partant de la droite : $m = 9$ et $k = 9$ ; donc $m + k = 12_{16}$ et par suite $y = 2$ ; \item avec le chiffre de rang 2 : $m = 4$ et $k = 1$ ; donc $m +k = 5_{16}$ et par suite $y = 5$. \end{itemize}\\\hline \end{tabularx} \end{center} Donc le mot crypté est $Y = 52_{16}$. \smallskip \textbf{Question }: avec le mot initial $M = 7 \text{A}_{16}$ et la clé $K = 4\text{C}_{6}$, déterminer le mot crypté $Y$. \item Par cette méthode, on admet que le décryptage suit les mêmes étapes en remplaçant la clé $K$ par une autre clé $K'$. Lorsque l'écriture de $K$ comporte au maximum deux chiffres hexadécimaux, la clé $K'$ est l'écriture en hexadécimal de la différence (écrite en décimal) $272_{10} - K_{10}$. \smallskip Cette question est une question à choix multiple. Une seule réponse est exacte. Recopier sur la copie seulement la réponse exacte. On ne demande pas de justification. \smallskip Avec la clé de cryptage $K = 19_{16}$, la clé de décryptage $K'$ est égale à : \begin{center} \begin{tabularx}{0.75\linewidth}{X X} \textbf{Réponse A~~} : $253_{16}$ &\textbf{Réponse B~~} : $247_{16}$\\ \textbf{Réponse C~~} : FD$_{16}$ &\textbf{Réponse D~~} : F$7_{16}$\\ \end{tabularx} \end{center} \end{enumerate} \vspace{0,5cm} \textbf{Exercice 3\hfill 5 points} \medskip Pour effectuer des calculs, un ordinateur représente les nombres en binaire. Cet exercice étudie l'effet d'une perte de précision initiale sur une suite de calculs. Dans tout l'exercice, on note $a_b$ l'écriture du nombre $a$ en base $b$. \medskip \begin{enumerate} \item Représentation binaire de quelques nombres décimaux \begin{enumerate} \item Cette question est une question à choix multiple. Une seule réponse la copie seulement la réponse exacte. On ne demande pas de justification. \smallskip La représentation binaire du nombre qui s'écrit en décimal $15,5_{10}$ est : \begin{center} \begin{tabularx}{0.8\linewidth}{X X} \textbf{Réponse A~~} : $10101,101_2$ &\textbf{Réponse B~~} : $1111,1_2$\\ \textbf{Réponse C~~} : $1111,0101_2$ &\textbf{Réponse D~~}: $10101,1_2$\\ \end{tabularx} \end{center} \item Justifier que le nombre décimal $15,625_{10}$ a pour représentation binaire $1111,101_2$. \end{enumerate} \item On considère la suite géométrique $\left(u_n\right)$ de terme initial $u_0 = 32$ et de raison $15,625$. \begin{enumerate} \item Calculer la valeur exacte de $u_1$. \item Donner l'expression de $u_n$ en fonction de $n$. \end{enumerate} \item Pour calculer les termes de la suite $\left(u_n\right)$, on utilise un logiciel qui arrondit le nombre $15,62$ et le transforme en $15,5$. L'arrondi se répercute sur tous les termes calculés. qui sont alors ceux de la suite géométrique $\left(v_n\right)$ qui a le même terme initial que la suite $\left(u_n\right)$ c'est-à-dire $v_0 = u_0 = 32$, et dont la raison est égale à $15,5$. Ainsi, par exemple, $v_1 = 496$. Pour tout entier naturel $n$, on définit la perte de précision relative $e_n$ sur le $n$-ième terme par la relation : \[e_n = \dfrac{v_n}{u_n}.\] \begin{enumerate} \item Démontrer que la suite $\left(e_n\right)$ est la suite géométrique de terme initial $e_0 = 1$ et de raison $0,992$. \item Déterminer le plus petit entier naturel $n$ tel que $e_n < 0,9$. \end{enumerate} \end{enumerate} \end{document}