\documentclass[french,10pt,a4paper]{article}
\RequirePackage{etex}
\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}
\usepackage{fourier}
\usepackage[scaled=.875]{helvet}
\usepackage{courier}
\usepackage{amsfonts,amsthm,amsmath,amssymb}
%\DecimalMathComma
%\frenchbsetup{StandardLists=true}

\usepackage[table]{xcolor}
\usepackage{colortbl}
\usepackage{graphicx}
\usepackage{fancybox,fancyhdr}
\usepackage{enumitem}
\usepackage{array}
\usepackage{multicol}
\usepackage{setspace}
\usepackage{soul}
\usepackage{ulem}
\usepackage{mathrsfs}
\usepackage{bm}
\usepackage{xlop}
\usepackage{stmaryrd}
\usepackage{variations}
\usepackage{caption}
\usepackage{euscript}
\usepackage{calc}
\usepackage{multirow}
\usepackage{diagbox}
\usepackage{layout}
\usepackage{pstricks,pstricks-add,pst-plot,pst-tree,pst-blur,pst-grad,pst-coil,pst-func}
\usepackage{tikz}%tkz-tab
\usepackage{eurosym}
\usepackage{tabularx}
\usepackage{framed}
\usepackage[left=3cm, right=3cm, top=3cm, bottom=3cm]{geometry}
\newcommand{\vect}[1]{\overrightarrow{\,\mathstrut#1\,}}
%\usepackage[top=2.cm, bottom=2.cm, left=3.5cm,right=3.5cm, headheight=48pt,marginparwidth=2.cm]{geometry}
\newcommand{\barre}[1]{\overline{\,\mathstrut#1\,}}
\usepackage{hyperref}

\DeclareGraphicsExtensions{.eps}

\newcounter{nexo}
\setcounter{nexo}{0}
\newcommand{\exercice}[1]{%
\stepcounter{nexo}
{\noindent{\textbf{Exercice \arabic{nexo}}\hfill\textbf{#1 points}}}}
\newcommand{\N}{\ensuremath{\mathbb{N}}}
\newcommand{\Z}{\ensuremath{\mathbb{Z}}}
\newcommand{\Q}{\ensuremath{\mathbb{Q}}}
\newcommand{\R}{\ensuremath{\mathbb{R}}}
\newcommand{\C}{\ensuremath{\mathbb{C}}}
\newcommand{\Vect}[1]{\overrightarrow{\strut{\mathrm{#1}}}}
\newcommand{\OIJ}{\ensuremath{\left(\mathrm{O},~\mathrm{I},~\mathrm{J}\right)}}
\newcommand{\Oij}{\ensuremath{\left(\mathrm{O}~;~\vec{\imath},~\vec{\jmath}\right)}}
\newcommand{\Degre}{\ensuremath{^\circ}}
\renewcommand{\labelenumi}{%
\textbf{\theenumi.}}
\renewcommand{\labelenumii}{%
\textbf{\theenumii.}}
\renewcommand{\d}{\,\mathrm{d}}
\newcommand{\e}[1]{\,\mathrm{e}^{#1}}
\renewcommand{\i}{\mathrm{\,i}}
\newcommand{\integrale}[4]{\ensuremath{\displaystyle\int_{#1}^{#2} #3\d #4}}
\renewcommand{\gcd}{\mathrm{PGCD}~}
\newcommand{\intervFF}[2]{\ensuremath{\left[#1~;~#2\right]}}
\newcommand{\intervFO}[2]{\ensuremath{\left[#1~;~#2\right[}}
\newcommand{\intervOF}[2]{\ensuremath{\left]#1~;~#2\right]}}
\newcommand{\intervOO}[2]{\ensuremath{\left]#1~;~#2\right[}}
\usepackage[french]{babel}
\usepackage[autolanguage,np]{numprint}
\setlength{\parindent}{0pt}
\begin{document}
\pagestyle{fancy}
\lhead{}
\chead{}
\rhead{\small{Session 2019}}
\lfoot{}
\cfoot{\thepage}
\rfoot{}
\thispagestyle{empty}
\begin{center}
\textbf{\large BTS SERVICES INFORMATIQUES AUX ORGANISATIONS Nouvelle-Calédonie\\[5pt](obligatoire) décembre 2019}
\end{center}

\bigskip

\begin{exercice}{4}\

\medskip

Une Box possède huit diodes électroluminescentes alignées en façade. Chaque diode possède deux états qui traduisent les chiffres binaires : 1 pour une diode allumée et 0 pour une diode éteinte.

L'alignement des huit chiffres binaires reflétant l'état de la Box donne l'écriture binaire d'un  nombre $N$.

Exemple :

Si la Box est éteinte, les huit diodes le sont aussi et le nombre $N$ associé est $0000~0000_{2}$, soit $0_{10}$.

Si les huit diodes sont allumées, le nombre $N$ associé est $1111~1111_{2}$, soit $255_{10}$.

\begin{enumerate}
	\item
	\begin{enumerate}
		\item Quel est le nombre $N$ exprimé en base 10 correspondant au nombre $0001~0101_{2}$ ?
		
		\item Quel sera le nombre $N$ exprimé en base 2 correspondant au nombre $57_{10}$ ?
		
		\item Montrer qu'il y a 256 valeurs différentes possibles du nombre $N$.
	\end{enumerate}
	\item L'affichage des huit diodes, éteintes ou allumées, peut aussi signaler un problème particulier (absence de réseau, saturation, panne, \dots{}). On suppose dans cette question qu'il n'y a que 57 problèmes différents possibles.
	\begin{enumerate}
		\item On considère l'ensemble $E$ des nombres entiers entre $1$ et $57$, c'est-à-dire 
		
$E = \left\lbrace 1~;~2~;~\cdots~;~57\right\rbrace$. et l'ensemble $E'$ des écritures binaires du nombre $N$ : 
		
$E' = \left\lbrace 0000~0000~;~0000~0001~; \ldots ;~1111~1111\right\rbrace$.
		L'application qui à tout élément de $E$ associe l'écriture binaire dans $E'$ est-elle injective ? Surjective ? Bijective ?
		
		\item Pour traduire 57 problèmes différents, combien de diodes auraient été suffisantes ?
	\end{enumerate}
	\item Le fournisseur de la Box envisage de remplacer les diodes par l'affichage de deux symboles correspondant à un code hexadécimal.
	\begin{enumerate}
		\item Quelle serait l'écriture du nombre $N$ exprimé en base hexadécimale correspondant au problème (numéroté en base 10) : 43 ?
		
		\item Que signifierait dans le contexte de l'exercice  l'écriture en base hexadécimale $FF$ du nombre $N$ ?
	\end{enumerate}
\end{enumerate}
\end{exercice}

\bigskip

\begin{exercice}{8}\

\medskip

Un site internet permet de partager des commentaires sur des mangas.

\medskip

\textbf{Partie A : étude du nombre de commentaires}

\medskip

Au début de l'étude, au mois numéro 0, il y avait 550 commentaires proposés. Les modérateurs constatent que 80\,\% des commentaires donnent lieu à un autre commentaire que l'on comptabilise le mois suivant. De plus, 240 commentaires sur de nouveaux sujets apparaissent d'un mois à l'autre.

\smallskip

Pour tout $n \in \N$, on note $u_{n}$ le nombre de nouveaux commentaires émis au mois numéro $n$.

\begin{enumerate}
	\item Justifier que la suite $\left(u_{n}\right)$ est définie par $u_{0} = 550$ et pour tout $n \in \N$, $u_{n+1} = 0,8u_{n} + 240$.
	
	\item Calculer $u_{1}$ et $u_{2}$. Interpréter les résultats obtenus dans le contexte de l'exercice.
	
	\item On admet que pour tout $n \in \N$, $u_{n} = \np{1200} - 650 \times (0,8)^{n}$. Pour quelle valeur de $n$, $u_{n} \geqslant \np{1000}$ ?
	
	\item Peut-on dépasser \np{1200} nouveaux commentaires avec ce modèle ? Justifier.
\end{enumerate}

\medskip

\textbf{Partie B : archivage des commentaires}

\medskip

Afin de limiter l'espace de stockage nécessaire, un commentaire n'est conservé que s'il répond au moins à l'un des critères suivants :

\begin{itemize}
	\item le commentaire a eu strictement moins de 100 vues et est daté de strictement moins de 6 mois,
	\item ou le commentaire a été écrit par un anonyme et a eu 100 vues ou plus,
	\item ou le commentaire est daté de 6 mois ou plus et a eu 100 vues ou plus,
	\item ou le commentaire est daté de strictement moins de 6 mois et n'a pas été écrit par un anonyme.
\end{itemize}

On définit les variables booléennes $a$, $b$ et $c$ de la façon suivante :

\begin{itemize}
	\item $a=1$ si le commentaire a strictement moins de 6 mois ; $a=0$ sinon ;
	\item $b=1$ si le commentaire comptabilise strictement moins de 100 vues ; $b=0$ sinon ;
	\item $c=1$ si l'auteur du commentaire est anonyme ; $c=0$ sinon.
\end{itemize}

On admet qu'une expression booléenne $E$ traduisant qu'un commentaire est conservé est donnée par :
\[E = ab + \barre{b}c + \barre{a}\barre{b} + a\barre{c}\]

\begin{enumerate}
	\item À quel critère correspond l'expression $\barre{b}c$ ?
	
	\item Déterminer une écriture simplifiée de $E$ sous la forme d'une somme de deux termes. En déduire une interprétation des conditions pour que le commentaire soit conservé.
	
	\item Un commentaire date de 6 mois ou plus et son auteur est anonyme. Est-il toujours conservé ?
	
	\item Donner une expression simple de $\barre{E}$. À quelle condition un commentaire est-il supprimé ?
\end{enumerate}
\end{exercice}

\bigskip

\begin{exercice}{8}\

\medskip

\textbf{Partie A}

\medskip

Une entreprise fabrique 28 produits différents. Elle dispose d'un site internet pour les présenter au grand public. On suppose que les 28 produits sont référencés par un nombre entier compris entre 0 et 27.

Sur la page d'accueil de son site, l'entreprise souhaiterait mettre en avant chaque jour un produit différent, sans l'afficher nécessairement dans l'ordre de référencement, mais en étant certaine que tous les produits soient affichés un jour ou l'autre.

\begin{enumerate}
	\item
	\begin{enumerate}
		\item Décomposer $28$ en produit de facteurs premiers.
		
		\item Calculer le PGCD de $12$ et $28$.
		
		\item Les nombres $15$ et $28$ sont-ils premiers entre eux ?
	\end{enumerate}
\end{enumerate}

L'entreprise choisit de commencer par présenter le produit référencé numéro $0$.

À partir du deuxième jour, pour obtenir le numéro du produit mis en avant, on ajoute un nombre entier positif $a$ au numéro précédent et on calcule le reste de cette somme dans la division par $28$. Le nombre obtenu est le numéro du produit mis en avant.

Par exemple, en choisissant $a=12$, la liste des numéros des produits mis en avant sur le site dans l'ordre est : $0$ -- $12$ -- $24$ -- $8$ -- $20$.

\begin{enumerate}
\setcounter{enumi}{1}
	\item Compléter la liste des numéros des 11 premiers produits mis en avant pour $a=12$.
	
	\item Ce choix du nombre $a$ permet-il de présenter tous les produits ?
	
	\item Parmi les valeurs suivantes de $a$ : $1$ ; $2$ ; $17$ ; $24$ ; $25$, dire lesquelles permettent de mettre en avant tous les produits ? On ne demande pas de justification.
\end{enumerate}

\medskip

\textbf{Partie B}

\medskip

Le site internet de cette entreprise est composé de 4 pages WEB : une page d'accueil A, une page de présentation des produits B, une page de commande C et une page de facturation D.

\begin{itemize}
	\item La page A permet d'aller sur les pages B et C.
	
	\item La page B permet d'aller sur la page C.
	
	\item Seule la page C permet d'aller sur la page D.
	
	\item Les pages B et D permettent d'aller sur la page A.
\end{itemize}

\begin{enumerate}
	\item Représenter l'ensemble de ces liens par un graphe orienté de sommets A, B, C, D.
	
	\item Donner la matrice $M$ d'adjacence de ce graphe.
	
	\item Vérifier que $M^{2} = \begin{pmatrix}1&0&1&1\\0&1&1&1\\1&0&0&0\\0&1&1&0\end{pmatrix}$. Combien existe-t-il de circuits de longueur 2 ? Les citer.
	
	\item Existe-t-il un ou des chemin(s) de longueur 2 allant de la page A vers la page D ? Si oui, le(s) citer.
	
	\item Calculer $M^{3}$. Existe-t-il au moins un chemin de longueur 3 allant de B vers A ? Si oui, en citer au moins un.
	
	\item Déterminer la matrice $\widehat{M}$ de fermeture transitive du graphe. Interpréter ce résultat dans le contexte de l'exercice.
\end{enumerate}
\end{exercice}
\end{document}
\newpage
\setcounter{page}{1}

\begin{center}
\begin{LARGE}
\begin{bfseries}
\textsc{Correction}
\end{bfseries}
\end{LARGE}
\end{center}

\bigskip

\begin{exercice}{4}\

\begin{enumerate}
	\item
	\begin{enumerate}
		\item \emph{Expression de $N = 0001~0101_{2}$ en base 10} :
		
		$N = 0001~0101_{2} = \boxed{21_{10}}$
		
		\item \emph{Expression de $N = 57_{10}$ en base 2} :
		
		$N = 57_{10} = \boxed{0011~1001_{2}}$
		
		\item \emph{Nombre de valeurs possibles du nombre $N$} :
		
		$N$ est un nombre de 8 chiffres en binaire. Chaque chiffre a deux valeurs possibles ($0$ et $1$), il y a donc $2^{8}$ nombres possibles, c'est-à-dire 256.
	\end{enumerate}
	\item
	\begin{enumerate}
		\item \emph{Injectivité de l'application} :
		
		Chaque élément de $E'$ a au plus un antécédent dans $E$, donc l'application est injective.
		
		\emph{Surjectivité de l'application} :
		
		 Il existe des éléments de $E'$ ($0000~0000_{2}$ par exemple) qui n'ont pas d'antécédent dans $E$, donc l'application n'est pas surjective.
		 
		 \emph{Bijectivité de l'application} :
		 
		 Puisque l'application n'est pas surjective, elle n'est pas bijective.
		 
		 \item \emph{Nombre de diodes nécessaires pour traduire 57 problèmes différents} :
		 
		 On a vu à la question \textbf{1.b.} que l'écriture en base 2 de $57_{10}$ est $0011~1001_{2}$. Les diodes correspondant à $2^{7}$ et $2^{8}$ restent donc éteintes pour représenter en base 2 les entiers inférieurs à $57$. Il suffit donc de 6 diodes pour traduire 57 problèmes différents.
	\end{enumerate}
	\item
	\begin{enumerate}
		\item \emph{Expression de $N = 43_{10}$ en base hexadécimale} :
		
		$N = 43_{10} = \boxed{2B_{16}}$
		
		\item \emph{Signification dans l'écriture $FF$ en base hexadécimale du nombre $N$} :
		
		Le nombre $FF$ en base hexadécimale correspond à $1111~1111_{2}$ donc toutes les diodes sont allumées.
	\end{enumerate}
\end{enumerate}
\end{exercice}

\bigskip

\begin{exercice}{8}\

\medskip

\textbf{Partie A : étude du nombre de commentaires}

\medskip

\begin{enumerate}
	\item \emph{Justification de l'expression de la suite $\left(u_{n}\right)$} :
	
	D'un mois sur l'autre 80~\% des commentaires donnent lieu à un autre commentaire, donc si $u_n$ est le nombre de commentaire au moins numéro $n$, ils donnent lieu à $0,8 \times u_{n}$ au mois numéro $n+1$. Par ailleurs il y a 240 nouveaux commentaires qui viennent s'ajouter, on a donc bien :
	
	$u_{n+1} = 0,8u_{n} + 240$.
	
	\item \emph{Calcul de $u_{1}$} :
	
	$u_{1} = 0,8 \times u_{0} + 240 = 0,8 \times 550 + 240 = \boxed{640}$
	
	\emph{Interprétation du résultat} :
	
	Il y a 640 commentaires sur le site au mois numéro 1.
	
	\emph{Calcul de $u_{2}$} :
	
	$u_{2} = 0,8 \times u_{1} + 240 = 0,8 \times 640 + 240 = \boxed{784}$
	
	\emph{Interprétation du résultat} :
	
	Il y a 784 commentaires sur le site au mois numéro 2.
	
	\item \emph{Détermination de la valeur  de $n$ à partir de laquelle $u_{n} \geqslant \np{1000}$} :
	
	On utilise l'algorithme suivant :~~
	\fbox{\parbox{5cm}{%
	L1~~U $\gets$ 550\\
	L2~~N $\gets$ 0\\
	L3~~Tant que U < \np{1000}\\
	L3~~\hspace{1cm}U $\gets$ \np{1200}-650 * $0,8^{_text{N}}$\\
	L4~~\hspace{1cm}N $\gets$ N + 1\\
	L5~~Fin Tant que\\
	L6~~Afficher N
	}}
	
	On obtient $\boxed{n=6}$.
	
	\item \emph{Limite de la suite $\left(u_{n}\right)$} :
	
	On sait que $\lim\limits_{n \to +\infty}0,8^{n} = 0$ puisque $0 < 0,8 < 1$.
	
	On a donc $\lim\limits_{n \to  +\infty}-650 \times 0,8^{n} = 0 \implies \lim\limits_{n \to +\infty}\left(\np{1200} -650 \times 0,8^{n}\right) = \boxed{\np{1200}}$.
	
	On ne pourra donc pas dépasser \np{1200} nouveaux commentaires.
\end{enumerate}

\medskip

\textbf{Partie B}

\medskip

\begin{enumerate}
	\item \emph{Critère correspondant à l'expression $\barre{b}c$} :
	
	L'expression $\barre{b}c$ correspond à \og le commentaire comptabilise 100 vues ou plus et l'auteur est anonyme \fg.
	
	\item \emph{Écriture simplifiée de $E$} :
	
	On utilise un tableau de Karnaugh :
	
	\begin{center}
	\psset{unit=1.5cm,algebraic=true,dimen=middle,linewidth=1.2pt, dotstyle=+,dotsize=5pt 0,arrowsize=4pt 2,arrowinset=.25}
	\begin{pspicture*}(-2,0)(7,4)
	\multido{\i=0+1}{6}{\psline[linewidth=1.5pt](\i,0)(\i,3)}
	\multido{\i=0+1}{4}{\psline[linewidth=1.5pt](0,\i)(5,\i)}
	\psline(0,3)(1,2)
	\uput{.25}[45](0,2){\large{$a$}}
	\uput{.25}[-135](1,3){\large{$bc$}}
	\rput(0.5,0.5){\large{$1$}}
	\rput(0.5,1.5){\large{$0$}}
	\rput(1.5,2.5){\large{$00$}}
	\rput(2.5,2.5){\large{$10$}}
	\rput(3.5,2.5){\large{$11$}}
	\rput(4.5,2.5){\large{$01$}}
	\psline{|-|}(-0.25,0)(-0.25,1)
	\uput[180](-0.25,0.5){\large{$a$}}
	\psline{|-|}(2,3.25)(4,3.25)
	\uput[90](3,3.25){\large{$b$}}
	\psline{|-|}(3,3.75)(5,3.75)
	\uput[90](4,3.75){\large{$c$}}
	\rput(1.5,1.5){\Huge{$1$}}
	\rput(1.5,0.5){\Huge{$1$}}
	\rput(2.5,0.5){\Huge{$1$}}
	\rput(3.5,0.5){\Huge{$1$}}
	\rput(4.5,0.5){\Huge{$1$}}
	\rput(4.5,1.5){\Huge{$1$}}
	\psframe[framearc=.5,linewidth=1.5pt,linecolor=red](1.2,0.2)(4.8,0.8)
	\psline[linecolor=red]{<-}(4.8,0.5)(5.2,0.5)
	\uput[0](5.2,0.5){\red{\LARGE{$a$}}}
	\psline[linearc=.25,linewidth=1.5pt,linestyle=dashed, linecolor=blue](1.2,0.2)(1.8,0.2)(1.8,1.8)(1.2,1.8)
	\psline[linearc=.25,linewidth=1.5pt,linestyle=dashed, linecolor=blue](4.8,0.2)(4.2,0.2)(4.2,1.8)(4.8,1.8)
	\psline[linecolor=blue]{<-}(4.2,1.1)(5.2,1.5)
	\uput[0](5.2,1.5){\blue{\LARGE{$\barre{b}$}}}
	\end{pspicture*}
	\end{center}
	
	On a donc : $\boxed{E = a + \barre{b}}$.
	
	\emph{Interprétation des conditions pour que le commentaire soit conservé} :
	
	Le commentaire est conservé s'il a strictement moins de 6 mois ou s'il comptabilise plus de 100 vues.
	
	\item \emph{Conservation du commentaire datant de 6 mois ou plus et dont l'auteur est anonyme} :
	
	Un commentaire datant de 6 mois ou plus et dont l'auteur est anonyme correspond à l'expression $\barre{a}c$. Le commentaire sera donc conservé s'il comptabilise plus de 100 vues et ne sera pas conservé s'il comptabilise strictement moins de 100 vues.
	
	\item \emph{Expression de $\barre{E}$} :
	
	$\barre{E} = \barre{a + \barre{b}} = \barre{a} \cdot \barre{\barre{b}} = \boxed{\barre{a}b}$
	
	\emph{Condition pour qu'un commentaire soit supprimé} :
	
	D'après l'expression de $\barre{E}$, un commentaire est supprimé s'il date de 6 mois ou plus et s'il comptabilise strictement moins de 100 vues.
\end{enumerate}
\end{exercice}

\bigskip

\begin{exercice}{8}\

\medskip

\textbf{Partie A}

\medskip

\begin{enumerate}
	\item
	\begin{enumerate}
		\item \emph{Décomposition en facteurs premiers de $28$} :
		
		$\boxed{28 = 2^{2} \times 7}$
		
		\item \emph{PGCD de 12 et 28} :
		
		On a $12 = 2^{2} \times 3$ donc $\boxed{\gcd{(12~;~28)} = 4}$
		
		\item \emph{$15$ et $28$ premiers entre eux} :
		
		On a $15 = 3 \times 5$, donc le seul diviseur commun de $15$ et $28$ est $1$, donc $15$ et $28$ sont premiers entre eux.
	\end{enumerate}
	\item \emph{Liste des numéros des 11 premiers produits mis en avant pour $a=12$} :
	\begin{multicols}{3}
	$0 + 12 = 12$ ; $12 = 28 \times 0 + \bm{12}$
	
	$12 + 12 = 24$ ; $24 = 28 \times 0 + \bm{24}$
	
	$24 + 12 = 36$ ; $36 = 28 \times 1 + \bm{8}$
	
	$8 + 12 = 20$ ; $20 = 28 \times 0 + \bm{20}$
	
	$20 + 12 = 32$ ; $32 = 28 \times 1 + \bm{4}$
	
	$4 + 12 = 16$ ; $16 = 28 \times 0 + \bm{16}$
	
	$16 + 12 = 28$ ; $28 = 28 \times 1 + \bm{0}$
	
	$0 + 12 = 12$ ; $12 = 28 \times 0 + \bm{12}$
	
	$12 + 12 = 24$ ; $24 = 28 \times 0 + \bm{24}$
	\end{multicols}
	On a donc la liste suivante : $\boxed{\left\lbrace 0~;~12~;~24~;~8~;~20~;~4~;~16~;~0~;~12~;~24~;~8 \right\rbrace}$
	
	\item \emph{Possibilité d'afficher tous les produits avec ce choix de nombre} :
	
	On voit que dans la liste des 11 premiers produits affichés, il n'y a pas tous les produits et que cette liste est cyclique, on n'affiche que 7 produits différents.
	
	\item \emph{Valeurs permettant d'afficher tous les produits} :
	
	Les valeurs $1$, $17$ et $25$ permettent d'afficher tous les produits (car ces entiers sont premiers avec $28$).
\end{enumerate}

\medskip

\textbf{Partie B}

\medskip

\begin{enumerate}
	\item \emph{Graphe représentant l'ensemble des liens} :
	
	\begin{center}
	\psset{xunit=1.5cm,yunit=1.5cm,nodesep=2pt,arrowsize=4pt 2, arrowinset=0.25}
	\begin{pspicture*}(-0.5,-0.5)(3.5,3.5)
	\cnode(0.,3.){4mm}{A}
	\cnode(3.,3.){4mm}{B}
	\cnode(3.,0.){4mm}{C}
	\cnode(0.,0.){4mm}{D}
	\rput(0.,3.){\large{A}}
	\rput(3.,3.){\large{B}}
	\rput(3.,0.){\large{C}}
	\rput(0.,0.){\large{D}}
	\ncarc[ArrowInside=->,arcangle=15]{A}{B}
	\ncarc[ArrowInside=->,arcangle=15]{B}{A}
	\ncarc[ArrowInside=->,arcangle=0]{A}{C}
	\ncarc[ArrowInside=->,arcangle=0]{B}{C}
	\ncarc[ArrowInside=->,arcangle=0]{C}{D}
	\ncarc[ArrowInside=->,arcangle=0]{D}{A}
	\end{pspicture*}
	\end{center}
	
	\item \emph{Matrice d'adjacence du graphe} :
	
	$\boxed{M = \begin{pmatrix}0&1&1&0\\1&0&1&0\\0&0&0&1\\1&0&0&0\end{pmatrix}}$
	
	\item \emph{Calcul de $m^{2}$} :
	
	$\begin{array}{rcl}
		M^{2} &=& \begin{pmatrix}0&1&1&0\\1&0&1&0\\0&0&0&1\\1&0&0&0\end{pmatrix} \times \begin{pmatrix}0&1&1&0\\1&0&1&0\\0&0&0&1\\1&0&0&0\end{pmatrix} = \begin{pmatrix}0+1+0+0 & 0+0+0+0 & 0+1+0+0 & 0+0+1+0 \\ 0+0+1+0 & 1+0+0+0 & 1+0+0+0 & 0+0+1+0 \\ 0+0+0+1 & 0+0+0+0 & 0+0+0+0 & 0+0+0+0 \\ 0+0+0+0 & 1+0+0+0 & 1+0+0+0 & 0+0+0+0\end{pmatrix}\\
		&=& \boxed{\begin{pmatrix}1&0&1&1\\0&1&1&1\\1&0&0&0\\0&1&1&0\end{pmatrix}}
	\end{array}$
	
	\emph{Existence de circuits de longueur 2} :
	
	On sait que les coefficients de la matrice $M^{n}$ (où $M$ est la matrice d'adjacence du graphe) donnent le nombre de chemins de longueur $n$ dans le graphe. Ici, donc, $M^{2}$ donne les chemins de longueur 2. 
	
	Un circuit est un chemin dont les deux extrémités sont identiques, ils correspondent donc aux coefficients de la diagonale. Donc, pour connaître le nombre de circuits de longueur 2, on fait la somme de ces coefficients.
	
	On a donc 2 circuits de longueur 2 dans le graphe.
	
	\emph{Circuits de longueur 2 dans le graphe} :
	
	Les deux circuits sont : \fbox{A-B-A} et \fbox{B-A-B}.
	
	\item \emph{Existence d'un chemin de longueur 2 entre les sommets A et D} :
	
		Pour savoir s'il existe une chemin entre le sommet A et le sommet D, c'est-à-dire entre les pages A et D on regarde le coefficient de la 1\up{e} ligne et 4\up{e} colonne. C'est $1$, donc il existe un chemin de longueur 2 entre la page A et la page D.
	
	Ce chemin est A-C-D.
	
	\item \emph{Calcul de $M^{3}$} :
	
	$\boxed{M^{3} = \begin{pmatrix}1&1&1&1\\2&0&1&1\\0&1&1&0\\1&0&1&1\end{pmatrix}}$
	
	\emph{Existence de chemins de longueur 3 de B vers A} :
	
	D'après la matrice $M^{3}$, il existe deux chemins de longueur 3 de B vers A.
	
	\emph{Chemins de longueur 3 de B vers A} :
	
	Les deux chemins de longueur 3 de B vers A sont : \fbox{B-A-B-A} et \fbox{B-C-D-A}.
	
	\item \emph{Matrice de fermeture transitive $\widehat{M}$ du graphe} :
	
	$\begin{array}{rcl}
		\widehat{M} &=& M^{[1]} + M^{[2]} + M^{[3]} + M^{[4]}\\
		&=& \begin{pmatrix}0&1&1&0\\1&0&1&0\\0&0&0&1\\1&0&0&0\end{pmatrix} + \begin{pmatrix}1&0&1&1\\0&1&1&1\\1&0&0&0\\0&1&1&0\end{pmatrix} + \begin{pmatrix}1&1&1&1\\1&0&1&1\\0&1&1&0\\1&0&1&1\end{pmatrix} + \begin{pmatrix}1&1&1&\\1&1&1&1\\1&0&1&1\\1&1&1&1\end{pmatrix}\\
		&=& \boxed{\begin{pmatrix}1&1&1&1\\1&1&1&1\\1&1&1&1\\1&1&1&1\end{pmatrix}}
	\end{array}$
\end{enumerate}
\end{exercice}

\end{document}