Cours FC PDF [PDF]

Zitiervorschau

Cours de mathématiques Formation continue Laurent Thomann

2

Table des matières 1 Algèbre de Boole 1.1 Définitions . . . . . . . . . . . . . . . . . . 1.1.1 La somme logique (OR) . . . . . . 1.1.2 Le produit logique (AND) . . . . . 1.1.3 L’inversion logique (NOT) . . . . . 1.1.4 La somme logique exclusive (XOR) 1.2 Propriétés dérivées . . . . . . . . . . . . . 1.3 Expressions booléennes . . . . . . . . . . . 1.4 Application aux circuits logiques . . . . . 1.5 Application à l’analyse d’argumentation .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

7 7 7 8 9 9 10 12 13 14

2 Statistiques 2.1 Quelques éléments de statistique descriptive . . . . 2.2 Étude et représentation d’une variable qualitative . 2.2.1 Diagramme en bâton . . . . . . . . . . . . . 2.2.2 Diagramme circulaire . . . . . . . . . . . . . 2.3 Étude et représentation d’une variable quantitative 2.3.1 Étude d’une variable à valeurs discrètes . . 2.3.2 Étude d’une variable à valeurs continues . . 2.3.3 Représentations . . . . . . . . . . . . . . . . 2.4 Régression linéaire . . . . . . . . . . . . . . . . . . 2.4.1 Introduction . . . . . . . . . . . . . . . . . . 2.4.2 Covariance . . . . . . . . . . . . . . . . . . 2.4.3 Méthode des moindres carrés . . . . . . . . 2.5 Ajustement non-linéaire . . . . . . . . . . . . . . . 2.5.1 Ajustement de la forme y = a ln x + b . . . 2.5.2 Ajustement de la forme y = bax . . . . . . .

. . . . . . . . . . . . . . .

. . . . . . . . . . . . . . .

. . . . . . . . . . . . . . .

. . . . . . . . . . . . . . .

. . . . . . . . . . . . . . .

. . . . . . . . . . . . . . .

. . . . . . . . . . . . . . .

. . . . . . . . . . . . . . .

. . . . . . . . . . . . . . .

. . . . . . . . . . . . . . .

. . . . . . . . . . . . . . .

. . . . . . . . . . . . . . .

. . . . . . . . . . . . . . .

. . . . . . . . . . . . . . .

. . . . . . . . . . . . . . .

. . . . . . . . . . . . . . .

. . . . . . . . . . . . . . .

15 15 16 16 17 18 18 19 20 21 21 23 25 27 27 27

. . . . . . . . . .

29 29 29 30 31 31 32 32 33 36 39

3 Probabilités 3.1 Dénombrement . . . . . . . . . . . . . 3.1.1 Arrangements et combinaisons 3.1.2 Combinaisons . . . . . . . . . . 3.2 Probabilités . . . . . . . . . . . . . . . 3.2.1 Expériences aléatoires . . . . . 3.2.2 Événements . . . . . . . . . . . 3.2.3 Calculs de probabilités . . . . . 3.2.4 Variables aléatoires discrètes . 3.2.5 Variables aléatoires continues . 3.3 Loi des grands nombres . . . . . . . . 3

. . . . . . . . . .

. . . . . . . . . .

. . . . . . . . .

. . . . . . . . . .

. . . . . . . . .

. . . . . . . . . .

. . . . . . . . .

. . . . . . . . . .

. . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

4

TABLE DES MATIÈRES 3.4

3.5

Application aux intervalles de confiance . . . . . . . . . . . . . . . . . . 3.4.1 L’intervalle de confiance de la moyenne d’une loi normale quand type est connu . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.4.2 Intervalle de confiance pour un sondage . . . . . . . . . . . . . . Application aux tests d’hypothèses . . . . . . . . . . . . . . . . . . . . . 3.5.1 Principes généraux des tests . . . . . . . . . . . . . . . . . . . . . 3.5.2 Test de la moyenne d’une loi normale dont l’écart-type est connu 3.5.3 Test d’une proportion . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . l’écart. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

40 40 42 43 43 44 45

4 Applications de l’arithmétique 4.1 Division euclidienne . . . . . . . . . . . . . . . . . . . . . 4.2 Crible d’Eratosthène . . . . . . . . . . . . . . . . . . . . . 4.3 Systèmes de numération . . . . . . . . . . . . . . . . . . . 4.3.1 Écriture en base décimale . . . . . . . . . . . . . . 4.3.2 Écriture en binaire . . . . . . . . . . . . . . . . . . 4.3.3 Écriture en base b . . . . . . . . . . . . . . . . . . 4.3.4 Écriture en base hexadécimale (base 16) . . . . . . 4.4 Congruences, calcul modulo n . . . . . . . . . . . . . . . . 4.5 Règles de divisibilité . . . . . . . . . . . . . . . . . . . . . 4.5.1 Divisibilité par 2 . . . . . . . . . . . . . . . . . . . 4.5.2 Divisibilité par 5 . . . . . . . . . . . . . . . . . . . 4.5.3 Divisibilité par 3 . . . . . . . . . . . . . . . . . . . 4.5.4 Divisibilité par 9 . . . . . . . . . . . . . . . . . . . 4.6 Application 1 : Génération de nombres pseudo-aléatoires . 4.7 Application 2 : Calcul de la clé d’un RIB . . . . . . . . . . 4.8 Application 3 : Vérification d’un numéro de billet en euros 4.9 Application 4 : Chiffrement affine . . . . . . . . . . . . . . 4.10 Application 5 : Cryptographie RSA . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . .

47 47 48 48 48 49 51 51 52 54 54 54 55 55 55 57 58 59 59

5 Systèmes linéaires 5.1 Introduction . . . . . . . . . . . . . . . . . . . . . 5.1.1 Exemple introductif . . . . . . . . . . . . 5.1.2 Équations de droites . . . . . . . . . . . . 5.1.3 Systèmes . . . . . . . . . . . . . . . . . . 5.2 Résolution par substitution . . . . . . . . . . . . 5.3 Méthode du pivot de Gauss . . . . . . . . . . . . 5.3.1 Systèmes échelonnés . . . . . . . . . . . . 5.3.2 Opérations sur les équations d’un système 5.4 Quelques rappels sur les matrices . . . . . . . . . 5.4.1 Définition . . . . . . . . . . . . . . . . . . 5.4.2 Matrices particulières . . . . . . . . . . . 5.4.3 Addition de matrices . . . . . . . . . . . . 5.4.4 Multiplication de matrices . . . . . . . . . 5.4.5 Pièges à éviter . . . . . . . . . . . . . . . 5.4.6 Matrice identité . . . . . . . . . . . . . . . 5.4.7 Inverse d’une matrice . . . . . . . . . . . . 5.4.8 Déterminant d’une matrice carrée . . . . . 5.5 Algorithme du simplexe . . . . . . . . . . . . . . 5.5.1 Résolution graphique . . . . . . . . . . . . 5.5.2 Présentation de l’algorithme du simplexe .

. . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . .

65 65 65 65 65 66 67 67 67 69 69 69 70 70 71 72 72 73 73 74 74

. . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . .

TABLE DES MATIÈRES 5.5.3

5

Complexité de l’algorithme du simplexe . . . . . . . . . . . . . . . . . . .

77

6 Graphes et arbres 6.1 Graphes orientés . . . . . . . . . . . . . . . . . . . . . . 6.1.1 Définitions . . . . . . . . . . . . . . . . . . . . . 6.1.2 Matrice d’adjacence . . . . . . . . . . . . . . . . 6.2 Graphes non orientés . . . . . . . . . . . . . . . . . . . . 6.2.1 Vocabulaire . . . . . . . . . . . . . . . . . . . . . 6.3 Problèmes de coloration de graphes . . . . . . . . . . . . 6.3.1 Coloration de sommets . . . . . . . . . . . . . . . 6.3.2 Coloration d’arêtes . . . . . . . . . . . . . . . . . 6.4 Arbre recouvrant de poids minimum . . . . . . . . . . . 6.4.1 Introduction . . . . . . . . . . . . . . . . . . . . . 6.4.2 Algorithme de Kruskal . . . . . . . . . . . . . . . 6.4.3 Algorithme de Prim . . . . . . . . . . . . . . . . 6.4.4 Complexité des algorithmes précédents . . . . . . 6.5 Algorithme de plus court chemin . . . . . . . . . . . . . 6.5.1 Introduction et définitions . . . . . . . . . . . . . 6.5.2 Algorithme de Bellman-Ford-Moore . . . . . . . . 6.5.3 Exemple du voyageur de commerce . . . . . . . . 6.5.4 Modélisation des problèmes de plus court chemin 6.6 Algorithme de recherche de flot maximal . . . . . . . . . 6.6.1 Présentation du problème . . . . . . . . . . . . . 6.6.2 Un exemple . . . . . . . . . . . . . . . . . . . . . 6.6.3 Algorithme de Ford-Fulkerson . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . .

79 79 79 80 81 81 82 82 84 85 85 86 88 90 91 91 91 96 98 101 101 103 104

7 Initiation aux chaînes de Markov et applications 7.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . 7.2 Théorème de Chapman-Kolmogorov . . . . . . . . . 7.3 Comportement asymptotique des chaînes de Markov 7.4 Application à l’algorithme PageRank de Google . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

109 109 110 111 113

. . . .

117 117 118 120 121

8 Tests du khi-deux 8.1 Principes des tests statistiques . . . . . . . 8.2 Quelques résultats de probabilité . . . . . . 8.3 Test d’ajustement d’une loi empirique à une 8.4 Test d’indépendance . . . . . . . . . . . . . A Fonctions logarithme, exponentielle A.1 Fonction logarithme . . . . . . . . A.2 Fonction exponentielle . . . . . . . A.3 Fonction puissance . . . . . . . . . Références

. . . .

. . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . loi de probabilité théorique . . . . . . . . . . . . . . . .

. . . .

. . . .

. . . .

. . . .

et puissance 123 . . . . . . . . . . . . . . . . . . . . . . . . . . 123 . . . . . . . . . . . . . . . . . . . . . . . . . . 123 . . . . . . . . . . . . . . . . . . . . . . . . . . 124 125

6

TABLE DES MATIÈRES

Chapitre 1

Algèbre de Boole L’algèbre de Boole que l’on appelle aussi calcul booléen se trouve à l’intersection de la logique, de l’électronique et des mathématiques. Elle s’intéresse aux opérations et aux fonctions sur les variables logiques. On travaillera donc sur des techniques algébriques pour résoudre des problèmes du calcul des propositions. Son utilisation par Shannon dans les années 1930 pour fabriquer des circuits à l’aide de relais électromagnétiques est une des étapes fondamentales dans l’invention de l’informatique. L’algèbre de Boole ne concerne que des éléments (variables ou constantes booléennes) pouvant prendre les valeurs 0 et 1. Ces éléments servent souvent à représenter des tensions sur des fils (niveaux logiques) ou des conditions logiques (vrai ou faux) : • • • • •

le courant passe / le courant ne passe pas vrai / faux marche / arrêt ouvert / fermé bas / haut

Objectif : Comprendre et savoir manier les règles de base de l’algèbre de Boole. Savoir modéliser un problème concret à l’aide ce formalisme.

1.1 1.1.1

Définitions La somme logique (OR)

La somme logique est définie par la table d’addition suivante : + 0 1

0 1 0 1 1 1

Soient x et y deux variables booléennes (c’est à dire que x ∈ {0, 1} et y ∈ {0, 1}), on associe une variable booléenne d’identificateur x+y dont les valeurs sont données par la table de vérité suivante qui est la table de vérité de l’opérateur logique OU (en anglais OR) : x 0 0 1 1

y 0 1 0 1

x+y 0 1 1 1 7

8

CHAPITRE 1. ALGÈBRE DE BOOLE La somme logique possède les propriétés algébriques remarquables suivantes : • associativité : ∀(x, y, z) ∈ {0, 1}3 ,

(x + y) + z = x + (y + z) ;

• commutativité : ∀(x, y) ∈ {0, 1}2 ,

x + y = y + x;

• élément neutre : ∀x ∈ {0, 1},

x + 0 = 0 + x = x.

Preuve : On montre seulement l’associativité. On fait un tableau de vérité, et on est amené à étudier 23 = 8 cas : x 0 0 0 0 1 1 1 1

y 0 0 1 1 0 0 1 1

z 0 1 0 1 0 1 0 1

x + y (x + y) + z y + z x + (y + z) 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1

Les colonnes 5 et 7 sont identiques, donc on a bien l’égalité. Une autre façon de procéder est de considérer les différents cas possibles. On suppose que x = 1, alors 1 + y = 1, puis (1 + y) + z = 1 + z = 1 = 1 + (y + z). Maintenant si x = 0, alors 0 + y = y, puis (0 + y) + z = y + z = 0 + (y + z). Ilustration par un circuit électrique :

Il a deux interrupteurs, chacun actionné par la valeur d’une entrée. Quand l’entrée est un 1, l’interrupteur se ferme, et le courant peut passer. Quand l’entrée est un 0, l’interrupteur s’ouvre, et le courant ne passe pas. Ici les deux interrupteurs sont en parallèle, donc le courant peut passer dans le circuit dès qu’un des deux interrupteurs est fermé. Si le courant passe on note 1, sinon on note 0.

1.1.2

Le produit logique (AND)

Le produit logique est défini par la table de multiplication : . 0 1

0 1 0 0 0 1

Soient x et y deux variables booléennes, on associe une variable booléenne d’identificateur x.y dont les valeurs sont données par la table de vérité suivante qui est la table de vérité de l’opérateur logique ET (en anglais AND) : x y x.y 0 0 0 0 1 0 1 0 0 1 1 1

1.1. DÉFINITIONS

9

Le produit logique possède les propriétés algébriques remarquables suivantes : • associativité : ∀(x, y, z) ∈ {0, 1}3 , • commutativité : ∀(x, y) ∈

{0, 1}2 ,

• élément neutre : ∀x ∈ {0, 1},

(x.y).z = x.(y.z) ; x.y = y.x ;

x.1 = 1.x = x.

Ilustration par un circuit électrique :

Les règles sont les mêmes que dans le cas du OU, mais ici les deux interrupteurs sont en série. Ainsi le courant passe dans le circuit si et seulement si les deux interrupteurs sont fermés.

1.1.3

L’inversion logique (NOT)

L’inversion est notée avec une barre et elle est définie par 0 = 1 et 1 = 0. Soit x une variable booléenne, on associe une variable booléenne d’identificateur x dont les valeurs sont données par la table de vérité suivante qui est la table de vérité de l’opérateur logique NON (en anglais NOT) : x x

0 1 1 0

Les propriétés de l’inversion logique sont les suivantes : • ∀x ∈ {0, 1},

x + x = 1;

• ∀x ∈ {0, 1},

x.x = 0.

Ilustration par un circuit électrique :

Il y a exactement un interrupteur qui reçoit l’entrée. L’ampoule est une résistance et l’interrupteur est situé sur une branche qui offre une résistance inférieure à celle de l’ampoule. Quand l’entrée est un 1, i.e. que l’interrupteur se ferme, alors le courant passe surtout par la branche parallèle, et l’ampoule s’éteint (ou luit très faiblement). Quand l’entrée est un 0, i.e. que l’interrupteur est ouvert, alors tout le courant passe par l’ampoule, et le résultat est un 1.

1.1.4

La somme logique exclusive (XOR)

La somme logique exclusive est définie par la table d’addition suivante : ⊕ 0 1

0 1 0 1 1 0

10

CHAPITRE 1. ALGÈBRE DE BOOLE

Soient x et y deux variables booléennes, on associe une variable booléenne d’identificateur x ⊕ y dont les valeurs sont données par la table de vérité suivante qui est la table de vérité de l’opérateur logique OU-exclusif (en anglais XOR) : x 0 0 1 1

y 0 1 0 1

x⊕y 0 1 1 0

Le produit logique possède les propriétés algébriques remarquables suivantes : • associativité : ∀(x, y, z) ∈ {0, 1}3 , • commutativité : ∀(x, y) ∈

{0, 1}2 ,

• élément neutre : ∀x ∈ {0, 1},

(x ⊕ y) ⊕ z = x ⊕ (y ⊕ z) ; x ⊕ y = y ⊕ x;

x ⊕ 0 = 0 ⊕ x = x;

• élément symétrique : ∀x ∈ {0, 1},

x ⊕ x = 0.

Ilustration par un circuit électrique :

L’interrupteur de gauche est en position supérieure quand il reçoit un 1 et en position inférieure quand il reçoit un 0. L’interrupteur de droite est en position inférieure quand il reçoit un 1 et en position supérieure quand il reçoit un 0. On voit bien que le courant passe dans le circuit quand un des deux interrupteurs reçoit un 1, et l’autre, un 0. Exercice : Vérifier que pour tout (x, y) ∈ {0, 1}2 on a x⊕y = x.y +x.y. Ainsi la somme exclusive peut s’obtenir à l’aide des opérations logiques élémentaires précédentes. Pour conclure, on donne la définition suivante : Définition 1.1 Tout ensemble muni de deux éléments particuliers 1 et 0 et des trois opérations somme, produit et inversion logiques vérifiant toutes les propriétés énoncées précédemment est une algèbre de Boole, souvent notée (B, +, .) avec B = {0, 1}.

1.2

Propriétés dérivées

Les propriétés suivantes sont des propriétés dérivées d’une algèbre de Boole : • dualité : tout énoncé exprimé en fonction de + et de 0 est vrai lorsque l’on remplace + par . et 0 par 1 ; • unicité : les éléments neutres 0 et 1 pour la somme et le produit logiques, respectivement, sont uniques ; l’inverse de tout élément est unique ; • involution : ∀x ∈ {0, 1},

x=x

1.2. PROPRIÉTÉS DÉRIVÉES

11

• idempotence : ∀x ∈ {0, 1},

x+x=x

∀x ∈ {0, 1},

x.x = x

• élément absorbant : ∀x ∈ {0, 1},

x+1=1

∀x ∈ {0, 1},

x.0 = 0

• absorption : ∀(x, y) ∈ {0, 1}2 ,

x + x.y = x

∀(x, y) ∈ {0, 1}2 ,

x.(x + y) = x

(?)

• simplification : ∀(x, y) ∈ {0, 1}2 ,

x + x.y = x + y

∀(x, y) ∈ {0, 1}2 ,

x.(x + y) = x.y

• formules de De Morgan : ∀(x, y) ∈ {0, 1}2 ,

x + y = x.y

(?)

∀(x, y) ∈ {0, 1}2 ,

x.y = x + y

(?)

• distributivité du produit sur la somme : ∀(x, y, z) ∈ {0, 1}3 ,

x.(y + z) = (x.y) + (x.z)

• distributivité de la somme sur le produit : ∀(x, y, z) ∈ {0, 1}3 ,

(x + y).(x + z) = x + (y.z)

Preuve : Les démonstrations sont élémentaires. On peut soit raisonner en traitant les différents cas possibles ou en faisant une table de vérité. • Démontrons par exemple la propriété de simplification par disjonction de cas. Si x = 0, alors x + x.y = 0 + 1.y = y = x + y. Si x = 1, x + x.y = 1 + 0.y = 1 = x + y. • Démontrons par exemple les formules de De Morgan avec une table de vérité. x 0 0 1 1

y 0 1 0 1

x+y x+y 0 1 1 0 1 0 1 0

x 1 1 0 0

y x.y 1 1 0 0 1 0 0 0

Les colonnes 4 et 7 sont identiques, donc on a bien x + y = x.y.

12

CHAPITRE 1. ALGÈBRE DE BOOLE

1.3

Expressions booléennes

Définition 1.2 Soient x1 , x2 , . . . , xn un ensemble de variables booléennes, on appelle expression booléenne sur les variables x1 , x2 , . . . , xn toute variable exprimée à l’aide des opérations + , . et de l’inversion. Exemple : L’expression f (x, y, z) = (x.y + z).(y + z) est une expression booléenne. Les propriétés des expressions booléennes sont les suivantes : • La somme de 2 expressions booléennes est une expression booléenne ; • le produit de 2 expressions booléennes est une expression booléenne ; • l’inverse d’une expression booléenne est une expression booléenne. En général, les expressions booléennes ne sont pas écrites sous forme optimale. On dispose de plusieurs méthodes pour simplifier les expressions booléennes. Par exemple, on peut utiliser le calcul algébrique et les propriétés vues au paragraphe précédent. Exemple : Simplifier l’expression f (x, y, z) = (x.y + z).(y + z). On peut la développer : f (x, y, z) = x.y.y + x.y.z + y.z + z.z = x.y + x.y.z + y.z + z = x.y + z, en utilisant l’idempotence et l’absorption. Une autre méthode, appelée méthode du consensus, repose sur le résultat suivant Proposition 1.3 Soient A et B des expressions booléennes et x une variable booléenne. Alors on a l’égalité suivante : x.A + x.B = x.A + x.B + A.B Le monôme A.B est appelé le consensus des deux premiers. Preuve : On peut démontrer ce résultat à l’aide d’une table de vérité : x A B 0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1

x.A + x.B A.B x.A + x.B + A.B 0 0 0 1 0 1 0 0 0 1 1 1 0 0 0 0 0 0 1 0 1 1 1 1

Exemple : Soit f (x, y, z) = x + x.y. Alors f (x, y, z) = x + x.y + y = x+y .

(consensus) (absorption).

1.4. APPLICATION AUX CIRCUITS LOGIQUES

13

On peut énumérer toutes les fonctions booléennes à deux variables, il y a en a 24 = 16. On consigne le résultat dans le tableau suivant

x 0 0 1 1

y 0 1 0 1

0 0 0 0 0

1 OR NOR AND NAND x y XOR NXOR ⇔ ⇔ 6 ⇒ ⇐ ; : 1 0 1 0 1 1 1 0 1 0 1 1 1 0 0 1 1 0 0 1 1 0 1 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 0 0 1 0 1 1 0 1 1 0 1 0 0 0 0 1 1 0 1 1 0 0

Toutes les fonctions booléennes de ce tableau peuvent être écrites à l’aide des fonctions de base : somme, produit et inversion (en fait l’inversion et l’une des deux autres suffisent). Exercice : Écrire « ⇒ » à l’aide des fonctions élémentaires.

1.4

Application aux circuits logiques

L’intérêt principal est de minimiser les composants électroniques en vue de minimiser les coûts. Les fonctions booléennes de base peuvent se réaliser par des circuits logiques combinatoires. On utilise des portes logiques dont voici les principaux : La porte Inverseur (ou NOT) :

La porte AND :

La porte OR :

La porte Inverseur (ou NAND) :

La porte NOR :

La porte XOR :

On peut ajouter un complémenté (une inversion) à l’aide d’un rond. On peut donc construire un circuit réalisant une fonction définie par une expression booléenne. Mais aussi, on peut exprimer sous forme d’une fonction booléenne un circuit logique, et ainsi essayer de le simplifier. Exemple : Voici un circuit et sa fonction booléenne associée

Grâce aux règles algébriques du calcul booléen, on peut simplifier les expressions obtenues.

14

CHAPITRE 1. ALGÈBRE DE BOOLE

1.5

Application à l’analyse d’argumentation

On peut utiliser l’algèbre booléenne pour analyser une argumentation. Exemple : Un crime a été commis : André, Bernard et Claude sont suspects. Ils sont interrogés et déclarent : • André : Bernard est coupable et Claude est innocent. • Bernard : Si André est coupable alors Claude aussi. • Claude : Je suis innocent mais l’un des deux autres est coupable. Que penser de cette affaire ? • La première déclaration donne la fonction booléenne : P1 = B.C • La deuxième déclaration donne la fonction booléenne : P2 = (A ⇒ C) • La troisième déclaration donne la fonction booléenne : P3 = C.(A + B) On est alors amené à étudier la fonction booléenne P1 .P2 .P3 = (B.C).(A ⇒ C).(C.(A + B)). 1. Vérifier que (A ⇒ C) = A.C + A = A + C. 2. En déduire que P1 .P2 .P3 = A.B.C. Si l’on considère que tous ont dit la vérité, alors Bernard est le meurtrier B = 1,

A = C = 0.

Chapitre 2

Statistiques Objectif : L’objectif de ce chapitre est d’acquérir les notions de base en statistiques. Le but est de savoir traiter et interpréter des données.

2.1

Quelques éléments de statistique descriptive

On appelle statistique descriptive l’ensemble des méthodes et techniques mathématiques permettant de représenter, décrire et résumer un ensemble de données. Une population statistique est l’ensemble sur lequel on effectue des observations. Les individus sont les éléments de la population. Pour chaque individu, on dispose d’une ou plusieurs observations. Une variable statistique est ce qui est observé ou mesuré sur chacun des individus d’une population statistique. Les valeurs de la variable s’appellent modalité. Une variable peut être : • Quantitative : Elle exprime une quantité sur laquelle on peut faire des opérations (par exemple : taille, âge, salaire, . . .) • Qualitative : Elle exprime une modalité sur laquelle on ne peut pas faire d’opération (par exemple : couleur des yeux, sexe, nationalité, . . .) Exemple : On considère un groupe de stagiaires P1 , P2 , P3 , P4 dont on a regroupé quelques informations :

P1 P2 P3 P4

Couleur des yeux V B N N

Sexe H H F H

Temps dans les transports 25 12 05 50

Taille 1.80 1.65 1.71 1.75

Frères et soeurs 1 2 0 1

La population est le groupe de stagiaires. Les individus sont les stagiaires. Les variables statistiques qualitatives sont la couleur des yeux, le sexe ; les variables quantitatives sont le temps passé dans les transports, le taille et le nombre de frères et soeurs (quantitatives discrètes). 15

16

CHAPITRE 2. STATISTIQUES

2.2

Étude et représentation d’une variable qualitative

Soit x une variable qualitative, pouvant prendre K modalités, x1 , . . . , xK . On commence par donner la distribution d’effectifs Modalités x1 x2 ... xk ... xK Total

Effectifs n1 n2 ... nk ... nK n = n1 + · · · + nK

Fréquences f1 f2 ... fk ... fK f1 + · · · + fK = 1

nk . n On appelle mode, la modalité de la variable x qui a l’effectif le plus grand.

On calcule la fréquence (ou proportion) de chaque modalité par fk =

Exemple : Loi de Mendel Un croisement entre roses rouges et blanches a donné en seconde génération des roses rouges, roses et blanches. Sur un échantillon de taille 600, on a trouvé les résultats suivants Couleur Rouges Roses Blanches Total

Effectifs 141 315 144 600

Fréquences 0.235 0.525 0.240 1

On s’intéresse maintenant aux représentations possibles de ces données. On va le faire sur un exemple. Les recettes fiscales de l’État en 2015 sont de 378.6 milliards d’euros dont • TVA (taxe sur la valeur ajoutée) : 193.3 milliards ; • IR (impôt sur le revenu) : 75.3 milliards ; • IS (impôt sur les sociétés) : 58.1 milliards ; • TICPE (taxe intérieure de consommation sur les produits énergétiques) : 14 milliards ; • Autres : 37.9 milliards.

2.2.1

Diagramme en bâton

Chaque modalité en abscisse est représentée par une barre dont la hauteur est proportionnelle à la fréquence de la modalité. On peut mettre l’ordre que l’on veut en abscisse (il n’y a pas de relation d’ordre naturelle entre les différentes quantités). Calcul des fréquences de chaque impôt : TVA : 51.1 % ; IR : 19.9 % ; IS : 15.3 % ; TICPE : 3.7% ; Autres : 10.0 %.

17

0

10

20

30

40

50

2.2. ÉTUDE ET REPRÉSENTATION D’UNE VARIABLE QUALITATIVE

TVA

IR

IS

TICPE

Autres

Pour faire cette représentation, on utilise le logiciel R avec le code suivant : x