%!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}
\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}
\usepackage{fancyhdr}
\hypersetup{%
pdfauthor = {APMEP},
pdfsubject = {BTS SIO obligatoire},
pdftitle = {Polynésie  -  mai 2014},
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 Polynésie}
\lfoot{\small{Services informatiques aux organisations\\ épreuve obligatoire}}
\rfoot{\small{mai  2014}}
\renewcommand \footrulewidth{.2pt}
\pagestyle{fancy}
\thispagestyle{empty}
\marginpar{\rotatebox{90}{\textbf{A. P{}. M. E. P{}.}}}

\begin{center}{\Large\textbf{\decofourleft~Brevet de technicien supérieur Polynésie~\decofourright\\mai 2014 - Services informatiques aux organisations}}

\vspace{0,25cm}

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

\vspace{0,25cm}

\textbf{Exercice 1 \hfill 7 points}

\medskip

Un amateur a publié un site internet avec 5 pages, notées P$_1$, P$_2$, P$_3$, P$_4$ et P$_5$.

La page d'accueil du site est la page P$_1$. 

Chaque page contient des liens permettant de naviguer vers d'autres pages, 

Pour améliorer la navigation sur son site, il demande conseil à un informaticien, qui modélise le site par un graphe. 

Les 5 sommets S$_1$, S$_2$, S$_3$, S$_4$ et S$_5$ de ce graphe représentent les 5 pages, 

Un lien d'une page vers une autre est représenté par un arc orienté allant du sommet associé à la page de départ vers celui associé à la page d'arrivée, 

Le tableau des successeurs obtenu par l'informaticien est le suivant : 

\begin{center}
\begin{tabularx}{0.9\linewidth}{|l|*{5}{>{\centering \arraybackslash}X|}}\hline
Sommet		& S$_1$& S$_2$ 		& S$_3$&   S$_4$&   S$_5$\\ \hline   
Successeurs	& S$_2$, S$_3$, S$_5$& S$_3$&   S$_2$&   S$_3$&   S$_1$, S$_2$, S$_4$\\ \hline  
\end{tabularx}
\end{center}

\begin{enumerate}
\item 
	\begin{enumerate}
		\item Déterminer la matrice d'adjacence $M$ de ce graphe, 
		\item Donner une représentation géométrique de ce graphe orienté. 
	\end{enumerate}
\item Existe-t-il un chemin hamiltonien dans ce graphe? Si oui, en indiquer un. 
\item Calculer la matrice $M^2$. 
\item 
	\begin{enumerate}
		\item Combien existe-t-il de chemins de longueur 2 dans le graphe ? 
		\item Combien existe-t-il de chemins de longueur 2 issus du sommet S$_1$ ? 
	\end{enumerate}
\item On rappelle que la matrice $M'$ de fermeture transitive du graphe est donnée par l'addition booléenne : $M' = M \oplus M^{[2]}  \oplus M^{[3]} \oplus M^{[4]} \oplus M^{[5]}$. 


On admet que $M' = \begin{pmatrix}1& 1& 1& 1&1\\
0& 1& 1& 0& 0\\ 
0& 1& 1& 0& 0\\ 
0& 1& 1& 0& 0\\ 
1& 1& 1& 1& 1\\
\end{pmatrix}$. 
	\begin{enumerate}
		\item Quelles sont les pages du site qui sont accessibles depuis toutes les autres pages en quelques clics ? Justifier. 
		\item Interpréter les $0$ de la première colonne de la matrice $M'$ dans le contexte de l'énoncé. 
	\end{enumerate}
\end{enumerate}

\vspace{0,5cm}

\textbf{Exercice 2 \hfill 6 points}

\medskip

Une société de création de jeux vidéo commercialise un nouveau produit. Avec les bénéfices escomptés, elle souhaite renouveler son parc informatique. 

\medskip

\textbf{Partie A : choix des ordinateurs}

\medskip 

Les ordinateurs envisagés offrent les composants suivants: 

$\bullet~~$un processeur quad-core ou dual-core; 

$\bullet~~$une carte graphique avec 4 Go ou 2 Go de mémoire; 

$\bullet~~$un disque dur SA TA ou SSD. 

Pour un ordinateur quelconque, on définit les variables booléennes suivantes: 

$\bullet~~$$a = 1$ s'il possède un processeur quad-core, $a = 0$ sinon ; 

$\bullet~~$$b = 1$ si la carte graphique a 4 Go de mémoire, $b = 0$ sinon ; 

$\bullet~~$$c = 1$ si l'ordinateur possède un disque dur SAT A, $c = 0$ sinon. 

Le responsable informatique a pu tester différentes combinaisons de composants. 

Il décide de retenir, pour les équipements informatiques futurs de la société, des ordinateurs satisfaisant aux critères de choix suivants: 

$\bullet~~$être équipé d'un processeur quad-core et d'un disque dur SSD ; 

$\bullet~~$ou être équipé d'un processeur dual-core et d'une carte graphique de 4 Go ; 

$\bullet~~$ou être équipé d'un processeur quad-core, d'une carte graphique de 4 Go et d'un disque dur SATA. 

\medskip

\begin{enumerate}
\item Traduire par une expression booléenne $E$ les critères de choix du responsable informatique. 
\item À l'aide d'un tableau de Kanaugh ou d'un calcul booléen, trouver une expression simplifiée de $E$ sous la forme d'une somme de deux termes. 
\item Traduire par une phrase, dans le contexte de l'énoncé, l'expression simplifiée trouvée à la question précédente. 
\end{enumerate}

\bigskip

\textbf{Partie B : financement du projet}

\medskip 

Le renouvèlement du parc informatique est échelonné sur 12 trimestres, pour un coût total de \np{95500}~\euro. 

Le service comptable propose le financement suivant: 

$\bullet~~$pour le 1\up{er} trimestre, verser un montant de \np{6000}~\euro ; 

$\bullet~~$chaque trimestre, le montant versé augmente de 5\,\% par rapport à celui du trimestre précédent. 

On note $u_n$ le montant, exprimé en euro, versé le $n$-ième trimestre. On a donc $u_1 = \np{6000}$. 

\medskip

\begin{enumerate}
\item Vérifier que $u_2 = \np{6300}$ et calculer $u_3$. 
\item Montrer que la suite $\left(u_n\right)$ est une suite géométrique dont on donnera la raison. 
\item  
	\begin{enumerate}
		\item Exprimer $u_n$ en fonction de $n$. 
		\item Calculer le montant versé au dernier trimestre, arrondi à l'euro, 
	\end{enumerate}
\item On rappelle que, pour une suite géométrique $\left(U_n\right)$ de raison $q$ différente de 1 et de premier terme $U_1$ on a la formule : 

\[U_1 + U_2 + \cdots + U_n = U_1 \times \dfrac{1 - q^n}{1 - q}.\] 

Le financement prévu permet-il de renouveler le parc informatique ? Justifier. 

\end{enumerate}

\vspace{0,5cm}

\textbf{Exercice 3 \hfill 7 points}

\medskip 

Alice souhaite que Bob lui envoie des données confidentielles par Internet. Pour éviter que ces données puissent être exploitées par une tierce personne, ils ont recours à un cryptage de type RSA. 

Aucune connaissance sur le cryptage RSA n'est attendue dans cet exercice. 

\bigskip

\textbf{Partie A - Création des clés publique et privée par Alice}

\medskip 

\begin{enumerate}
\item Il faut tout d'abord choisir deux nombres premiers distincts notés $p$ et $q$, puis calculer leur produit noté $n$. Alice décide de prendre $p = 5$ et $q = 23$, ce qui donne $n = 115$. 

Expliquer pourquoi $23$ est un nombre premier. 
\item Il faut ensuite calculer $K = (p - 1) \times (q - 1)$, ce qui donne ici $K = 4 \times 22 = 88$, puis trouver un entier naturel $c$, compris entre $2$ et $K$, qui soit premier avec $K$. Le couple d'entiers $(n,\: c)$ est la clé publique. Alice décide de prendre $c = 9$. 
	\begin{enumerate}
		\item Donner la décomposition en produit de facteurs premiers de $88$. 
		\item Expliquer pourquoi $9$ et $88$ sont deux nombres premiers entre eux. 
	\end{enumerate}
\item Il faut enfin trouver un entier $d$ tel que $d \times c \equiv 1 \mod K$. Le couple d'entiers $(n,\:d)$ est la clé privée. Alice a trouvé $d = 49$. 

Expliquer pourquoi $49 \times 9 \equiv 1 \mod 88$. 
\end{enumerate}

\bigskip

\textbf{Partie B - Cryptage du message à envoyer par Bob avec la clé publique d'Alice}

\medskip 

Alice envoie sa clé publique à Bob et celui-ci s'en sert pour crypter un nombre $a$, qui doit être un entier naturel strictement inférieur à $n$. Le nombre crypté $b$ est alors égal au reste dans la division euclidienne de $a^c$ par $n$. C'est ce nombre crypté $b$ que Bob envoie à Alice, 

Bob veut transmettre à Alice le nombre $12$. 

Déterminer le nombre crypté $b$ que Bob envoie à Alice. 

\bigskip

\textbf{Partie C - Décryptage d'un message reçu par Alice avec sa clé privée} 

\medskip

Cette partie est indépendante de la précédente. 

Alice reçoit un nouveau nombre crypté de la part de Bob : le nombre $2$. Pour le décrypter, Alice utilise sa clé privée, c'est-à-dire le couple $(n,\:d)$. 

On admet que le nombre non crypté transmis par Bob, noté $a$, est égal au reste dans la division euclidienne de $2^{49}$ par $n$. 

Alice doit donc calculer le reste dans la division euclidienne de $2^{49}$ par $115$ pour trouver $a$. 

Mais sa calculatrice ne permet pas de calculer la valeur exacte de $2^{49}$. Cependant, elle a pu obtenir les résultats suivants: 

\[2^{33} = \np{8589934592}\quad  \text{et} \quad  \np{8589934592} \equiv 47 \mod 115,\]
 \[2^{16} = \np{65536}\quad  \text{et}\quad  \np{65536} \equiv 101 \mod 115.\] 

À partir de ces résultats, calculer le nombre $a$ transmis par Bob à Alice. 
\end{document}