]> AND Private Git Repository - cours-maths-dis.git/blob - partiels/131105S1/controle.tex~
Logo AND Algorithmique Numérique Distribuée

Private GIT Repository
t
[cours-maths-dis.git] / partiels / 131105S1 / controle.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. Contrôle de mathématiques discrètes.\\  
25 Semestre 1 (Novembre 2013). Durée 1h.}
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 exercices de ce sujet sont indépendants les uns des autres. 
35 Dans tout ce qui suit, on considère une algèbre de Boole
36 munie des opérateurs classiques ``+'', ``.'', 
37 ``$\overline{\begin{array}{l}~\end{array}}$'' et des variables booléennes 
38 $a$, $b$, $c$, $d$.
39
40
41 \vspace{-1em}
42 \section{Cours (3pts) }
43
44 \begin{enumerate}
45 \item Soit $A$ et $B$ deux ensembles d'un 
46 univers $\Omega$ tels que $A \subseteq B$. Définir $B\setminus A$ en compréhension.
47 \item L'ensemble vide appartient-il à tout ensemble? Justifier.
48 \end{enumerate}
49
50
51
52
53 \vspace{-1em}
54 \section{(6pts) Simplification de formules booléennes (d'après sujet de BTS-IG-2008)}
55 La société Jurabois exploite des coupes d'arbres constitués exclusivement de
56 feuillus et de résineux. Elle désire simplifier le règlement que les salariés 
57 doivent appliquer pour la coupe du bois.
58 Actuellement, le règlement dit qu'un arbre est à abattre dans les quatre cas 
59 suivants:
60 \begin{itemize}
61 \item si c'est un résineux au tronc droit mesurant plus de 20 m de hauteur;
62 \item si c'est un feuillus de 50 ans ou plus;
63 \item s'il a moins de 50 ans et mesure plus de 20 m de hauteur;
64 \item s'il est tordu. 
65 \end{itemize}
66 Pour un arbre quelconque, on définit les variables booléennes suivantes par:
67 \begin{itemize}
68 \item $a=1$ si l'arbre est un résineux;
69 \item $b=1$ si l'arbre a moins de 50 ans;
70 \item $c=1$ si l'arbre mesure plus de 20 m de hauteur;
71 \item $d=1$ si l'arbre est tordu.
72 \end{itemize}
73
74
75 \begin{enumerate}
76 \item Écrire la fonction booléenne $f(a,b,c,d)$ qui traduit le règlement 
77   actuel d'abattage d'un arbre. 
78
79 \item Grâce à une bonne gestion des forêts que la société exploite,
80   il n'y a maintenant plus d'arbre tordu.
81 \begin{enumerate}
82 \item Montrer que le nouveau règlement d'abattage se traduit par la fonction 
83 $
84 g(a,b,c) = ac + \overline{a}\overline{b} + bc
85 $.
86 \item A l'aide d'une table de Karnaugh donner l'expression $G$ qui 
87   serait la forme la plus réduite de $g$. 
88
89 \item Justifier algébriquement que l'on a l'égalité $G = g$.
90
91 \item Écrire la nouvelle règle d'abattage d'un arbre sous la forme 
92   la plus simple possible.
93 \end{enumerate}
94 \end{enumerate}
95
96
97
98 \vspace{-1em}
99 \section{(5pts) Démonstrations ensemblistes}
100 Soit $A$ et $B$ deux sous-ensembles de $\Omega$. 
101 \begin{enumerate}
102 \item Soit $A_0=\{1,2,3\}$ et $B_0=\{3,4\}$. 
103 Définir $A_0 \cup B_0$, $P(A_0)$, $P(B_0)$, $P(A_0\cup B_0)$ et 
104 $P(A_0) \cup P(B_0)$.
105 \item A-t-on l'égalité $P(A \cup B) = P(A) \cup P(B)$? Justifier.
106 \item Montrer que l'on a $P(A \cap B) = P(A) \cap P(B)$. 
107 \end{enumerate}
108
109
110
111 \vspace{-1em}
112 \section{(6 pts) Relation entre puissances d'éléments}
113
114
115 Sur $\N^*$ on définit la relation
116 $a \mathcal{R} b$ si   $a^b \leq b ^a$.
117 \begin{enumerate}
118 \item A-t-on $2 \mathcal{R} 3$? $2 \mathcal{R} 7$? $2 \mathcal{R} 4$? $3 \mathcal{R} 3$? $4 \mathcal{R} 2$? Justifier à chaque fois.
119
120 \item La relation est-elle réflexive? Le démontrer. 
121
122 \item La fonction logarithme népérien $\ln: \R^{+*} \rightarrow \R$ étant 
123   croissante, montrer que sur $\N^*$
124   $a \mathcal{R} b$ si   $\dfrac{\ln(a)}{a} \leq \dfrac{\ln(b)}{b}$.
125 \item La relation est-elle transitive? Pour justifier votre réponse, on 
126   pourra utiliser  la question précédente.
127 \item La relation est-elle antisymétrique? Le justifier.
128 \end{enumerate}
129
130
131
132
133
134 \end{document}