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=1cm, tmargin=-0.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{( 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 \begin{enumerate}
  60 \item Dans cette question, un code est correct
  61 s'il ne contient pas de 0 consécutifs (par exemple $1011$).
  62 Le but de cette question est de concevoir la fonction $G$  qui renvoie 1
  63 si le code de 4 bits $abcd$ est correct et 0 sinon.
  64 \begin{enumerate}
  65 \item Écrire la table de vérité de cet analyseur dans une table de Karnaugh.
  66 \item Donner l'expression la plus simplifiée de la fonction $G$.
  67 \end{enumerate}
  68 \item Dans cette question,  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{( pts) Relations binaires entre ensembles}
  83
  84
  85 \begin{enumerate}
  86 \item
  87 Soit $P^*$ l'ensemble des nombres premiers supérieurs à 2. 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 $\mathcal{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{( 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 \end{enumerate}
 120
 121 \vspace{-1em}
 122 \section{( pts) Plus Grand Commun Diviseur}
 123 Dans ce qui suit, $n$ est un entier naturel strictement positif.
 124 On considère trois suites
 125 $(U_n)_{n \in \N^*}$, $(U_n)_{n \in \N^*}$ et $(U_n)_{n \in \N^*}$
 126 définies par
 127 $A_n = n^2 - 2n +2$,
 128 $B_n = n² +2n +2$
 129  et
 130 $d_n= A_n \land B_n$.
 131
 132 \begin{enumerate}
 133 \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$?
 134 \item Montrer que si un entier naturel
 135   $d$ divise  à la fois $A_n$ et $n$, alors $d$ divise 2.
 136 \item Montrer que si un entier naturel
 137   $d$ divise  à la fois $A_n$ et $B_n$, alors $d$ divise $4n$.
 138 \item  Dans cette question on suppose que $n$ est impair.
 139 \begin{enumerate}
 140 \item  Montrer que $A_n$ et $B_n$ sont impairs.
 141   En déduire que $d_n$ est impair.
 142 \item Montrer que $d_n$ divise $n$.
 143 \item En utilisant la question 1, en déduire que $d_n$ divise 2,
 144   puis que $A_n$ et $B_n$ sont premiers entre eux.
 145 \end{enumerate}
 146 \item  On suppose maintenant que $n$ est pair.
 147 \begin{enumerate}
 148 \item Montrer que $d_n$ est pair.
 149 \item Montrer que 4 ne divise pas $A_n$. En déduire la même chose pour  $B_n$
 150 \item Montrer que $d_n$ peut s'écrire sous la forme $d_n = 2.p$,
 151   où $p$ est impair.
 152 \item En utilisant entre autre la question 2., en déduire
 153   que $p$ divise $n$.
 154 \item En utilisant entre autre la question 1., en déduire que $d_n=2$.
 155 \end{enumerate}
 156 \end{enumerate}
 157
 158
 159
 160 \vspace{-1em}
 161 \section{( pts) Nombres (premiers ou pas) de Fermat}
 162 Pour $p \in \N$, les nombres de Fermat sont ceux de la forme
 163 $F_p = 2^{2^p}+1$.
 164
 165
 166 \begin{enumerate}
 167 \item Question préliminaire: montrer que les deux égalités suivantes sont établies:
 168 \begin{enumerate}
 169 \item $x^n- 1 = (x-1)(x^{n-1}+x^{n-2}+\ldots+ x + 1)$  pour tout entier naturel $n$ strictement positif.
 170 \end{enumerate}
 171
 172 \item
 173 Montrer que si $n$ n'est pas une puissance de 2, alors
 174 $2^n+1$ n'est pas un nombre premier.
 175 On pourra se servir de l'égalité
 176 $$
 177 x^n+ 1 = (x+1)(x^{n-1}-x^{n-2}+\ldots - x + 1)
 178 $$  qui est établie
 179 pour tout entier naturel $n$ impair.
 180
 181 \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?
 182
 183 \item Montrer que, $F_{n+1} = (F_n - 1)^2 +1$.
 184
 185 \item Montrer que $F_{n+1} - 2$ est divisible par $F_{n}$.
 186
 187 \item Montrer $F_{n+1}$ et $F_{n}$ sont premiers entre eux.
 188
 189 \end{enumerate}
 190
 191
 192
 193 \end{document}