partiels/131217S1/partiel.tex

   1 \documentclass[11pt,a4paper,french]{article}
   2 \usepackage[francais]{babel}
   3 \usepackage[utf8]{inputenc}
   4 \usepackage{a4}
   5 \usepackage{amsmath}
   6 \usepackage{amsfonts}
   7 \usepackage{amssymb}
   8 \usepackage{framed}
   9 \usepackage[amsmath,thmmarks,thref,framed]{ntheorem}
  10 \usepackage[dvips]{graphics}
  11 \usepackage{epsfig}
  12 \usepackage{calc}
  13 \usepackage{tabls}
  14 \usepackage{times}
  15 \usepackage{tabularx}
  16 \usepackage{textcomp}
  17 \usepackage{pst-all}
  18 \usepackage[a4paper]{geometry}
  19
  20 \input{symboles.sty}
  21 \geometry{hmargin=1.5cm, tmargin=1.5cm, bmargin=1.5cm}
  22
  23 \title{
  24 DUT d'informatique. Partiel de mathématiques discrètes.\\
  25 Semestre 1 (Décembre 2013). Durée 1h30.}
  26
  27 \date{}
  28
  29 \begin{document}
  30 \maketitle
  31
  32 %\vspace{-3em}
  33 \noindent Seule une fiche manuscrite de format A5 est autorisée.
  34 Tous les moyens de communications sont interdits.
  35 Tous les exercices de ce sujet sont indépendants les uns des autres.
  36 Dans tout ce qui suit, on considère une algèbre de Boole
  37 munie des opérateurs classiques ``+'', ``.'',
  38 ``$\overline{\begin{array}{l}~\end{array}}$'' et des variables booléennes
  39 $a$, $b$, $c$, $d$.
  40
  41
  42 %\vspace{-1em}
  43 \section{(5 pts) Algèbre de Boole }
  44 On cherche à  analyser les codes binaires sur 4 bits.
  45
  46
  47 \begin{enumerate}
  48 \item Dans cette question, un code est correct s'il contient au
  49 plus deux 1 consécutifs. Par exemple $1010$ est dit correct
  50 (il ne contient pas de 1 consécutifs) tandis
  51 $0111$ ne l'est pas  (il contient trois 1 consécutifs).
  52 Le but de cette question est de concevoir la fonction $F$  qui renvoie 1
  53 si le code de 4 bits $abcd$ est correct et 0 sinon.
  54 \begin{enumerate}
  55 \item Écrire la table de vérité de cet analyseur dans une table de Karnaugh.
  56 \item Donner l'expression la plus simplifiée de la fonction $F$.
  57 \end{enumerate}
  58
  59 \item Dans cette question, un code est correct
  60 s'il ne contient pas de 0 consécutifs (par exemple $1011$).
  61 Le but de cette question est de concevoir la fonction $G$  qui renvoie 1
  62 si le code de 4 bits $abcd$ est correct et 0 sinon.
  63 \begin{enumerate}
  64 \item Écrire la table de vérité de cet analyseur dans une table de Karnaugh.
  65 \item Donner l'expression la plus simplifiée de la fonction $G$.
  66 \end{enumerate}
  67
  68 \item Dans cette question,  un code est correct
  69 s'il vérifie les deux contraintes précédentes.
  70 Le but de cette question est de concevoir la fonction $H$  qui renvoie 1
  71 si le code de 4 bits $abcd$ est correct et 0 sinon.
  72 \begin{enumerate}
  73 \item Sans utiliser de table de Karnaugh, résoudre algébrique de ce
  74 problème.
  75 \item Exprimer $H$ sous la forme d'une somme de trois monômes.
  76 \item Comment pourrait-on vérifier le résultat sur les tables de Karnaugh
  77 remplies aux deux premières questions.
  78 \end{enumerate}
  79 \end{enumerate}
  80
  81 %\vspace{-1em}
  82 \section{(4 pts) Relations binaires entre ensembles}
  83
  84
  85 \begin{enumerate}
  86 \item
  87 Soit $P^*$ l'ensemble des nombres premiers impairs. On considère
  88 la relation $\mathcal{R}$ entre deux éléments de $P^*$ définie par:
  89 $$
  90 p \mathcal{R} q \textrm{ si et seulement si }
  91 \dfrac{p+q}{2} \textrm{ appartient à $P^*$.}
  92 $$
  93 Montrer qu'elle n'est pas transitive.
  94
  95 \item On considère
  96 la relation $\mathcal{S}$ entre deux éléments de $\Z$ définie par:
  97 $$
  98 m \mathcal{S} n \textrm{ si et seulement si }
  99 m^2 + m = n^2 + n.
 100 $$
 101 \begin{enumerate}
 102 \item Montrer que c'est une relation d'équivalence.
 103 \item Construire la classe de 0, nommée $\dot{0}$.
 104 \item Pour tout entier relatif $m$, construire la classe de $m$,
 105   nommée $\dot{m}$.
 106 \end{enumerate}
 107 \end{enumerate}
 108
 109 %\vspace{-1em}
 110 \section{(3 pts) Démonstration par récurrence}
 111 On considère la suite $(U_n)_{n \in \N}$ définie pour
 112 tout $n \in \N$ par $U_n = 10^n.(9n-1)+1$.
 113 \begin{enumerate}
 114 \item Calculer $U_0$, $U_1$ et $U_2$.
 115 \item Montrer que pour tout $n \in \N$ par
 116 $U_{n+1} = U_n + 9^2.10^n.(n+1)$.
 117 \item Montrer que $U_n$ est divisible par 81 pour tout $n \in \N$.
 118 \end{enumerate}
 119
 120 %\vspace{-1em}
 121 \section{(7 pts) Plus Grand Commun Diviseur}
 122 Dans ce qui suit, $n$ est un entier naturel strictement positif.
 123 On considère trois suites
 124 $(A_n)_{n \in \N^*}$, $(B_n)_{n \in \N^*}$ et $(d_n)_{n \in \N^*}$
 125 définies par
 126 $A_n = n^2 - 2n +2$,
 127 $B_n = n² +2n +2$
 128  et
 129 $d_n= A_n \land B_n$.
 130
 131 \begin{enumerate}
 132 \item Calculer $A_1$, $A_2$, $A_3$, $A_4$,  $B_1$, $B_2$, $B_3$, $B_4$,  $d_1$, $d_2$, $d_3$ et  $d_4$. Quelles intuitions avez vous à propos de $d_n$?
 133 \item \label{itm:Q1} Montrer que si un entier naturel
 134   $d$ divise  à la fois $A_n$ et $n$, alors $d$ divise 2.
 135 \item \label{itm:Q2} Montrer que si un entier naturel
 136   $d$ divise  à la fois $A_n$ et $B_n$, alors $d$ divise $4n$.
 137 \item  Dans cette question on suppose que $n$ est impair.
 138 \begin{enumerate}
 139 \item  Montrer que $A_n$ et $B_n$ sont impairs.
 140   En déduire que $d_n$ est impair.
 141 \item En utilisant entre autre la question~\ref{itm:Q2}, montrer que $d_n$ divise $n$.
 142 \item En utilisant entre autre la question~\ref{itm:Q1}, en déduire que $d_n$ divise 2,
 143   puis que $A_n$ et $B_n$ sont premiers entre eux.
 144 \end{enumerate}
 145 \item  On suppose maintenant que $n$ est pair.
 146 \begin{enumerate}
 147 \item Montrer que $d_n$ est pair.
 148 \item Montrer que 4 ne divise pas $A_n$. En déduire la même chose pour  $B_n$
 149 \item Montrer que $d_n$ peut s'écrire sous la forme $d_n = 2.p$,
 150   où $p$ est impair.
 151 \item En utilisant entre autre la question~\ref{itm:Q2}, en déduire
 152   que $p$ divise $n$.
 153 \item En utilisant entre autre la question~\ref{itm:Q1}, en déduire que $d_n=2$.
 154 \end{enumerate}
 155 \end{enumerate}
 156
 157
 158
 159 %\vspace{-1em}
 160 \section{(5 pts) Nombres (premiers ou pas) de Fermat}
 161 Pour $p \in \N$, les nombres de Fermat sont ceux de la forme
 162 $F_p = 2^{2^p}+1$.
 163
 164
 165 \begin{enumerate}
 166 \item
 167 Montrer que si $n$ n'est pas une puissance de 2, alors
 168 $2^n+1$ n'est pas un nombre premier.
 169 On pourra se servir de l'égalité
 170 $$
 171 x^n+ 1 = (x+1)(x^{n-1}-x^{n-2}+\ldots - x + 1)
 172 $$  qui est est consiédérée comme admise
 173 pour tout entier naturel $n$ impair.
 174
 175 \item Le calcul de $F_5$ donne $F_5 = 4294967297 = 6700417\times641$. Que dire de $F_5$? Est-ce contradictoire avec la question précédente?
 176
 177 \item Montrer que $F_{n+1} = (F_n - 1)^2 +1$.
 178
 179 \item Montrer que $F_{n+1} - 2$ est divisible par $F_{n}$.
 180
 181 \item Montrer $F_{n+1}$ et $F_{n}$ sont premiers entre eux.
 182
 183 \end{enumerate}
 184
 185
 186
 187 \end{document}