[PDF] Cours de mathématiques discrètes

View - Download Cours de mathématiques discrètes

Previous PDF

Next PDF

Mathématiques pour l'informatique

Christophe GUYEUXet Jean-François COUCHOT

3 novembre 2010

Table des matières

I Théorie des ensembles10

1 Introduction à la théorie des ensembles11

I Rappels de théorie des ensembles. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 I.1 Notion première d'ensemble. . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 I.2 Règles de fonctionnement. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 I.3 Sous-ensembles, ensemble des parties. . . . . . . . . . . . . . . . . . . . . . . 12 I.4 Représentation graphique. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 I.5 Exercices. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 II Opérations sur les ensembles. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 II.1 Égalite de deux ensembles. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 II.2 Réunion, intersection. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 II.3 Complémentation. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 II.4 Produit cartésien. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 III Exercices. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 III.1 Ensembles de base. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 III.2 La différence symétrique. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 III.3 Généraux. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17

2 Relations binaires entre ensembles19

I Relations. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 II Relations d'ordre. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19

II.1 Réflexivité, antisymétrie, transitivité. . . . . . . . . . . . . . . . . . . . . . . . 20

II.2 Relation d'ordre. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 II.3 Ordre partiel, ordre total. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 II.4 Éléments maximaux. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21

III Relations d'équivalence. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22

III.1 Classes d'équivalence. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 III.2 Ensemble-quotient. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24

IV Compatibilité entre une opération et une relation binaire. . . . . . . . . . . . . . . . . 25

3 Application d'un ensemble dans un autre26

I Application et relation fonctionnelle. . . . . . . . . . . . . . . . . . . . . . . . . . . . 26

II Image et antécédent d'un élément. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26

III Applications injectives. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 IV Applications surjectives. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 V Image d'un ensemble par une application. . . . . . . . . . . . . . . . . . . . . . . . . 28 VI Applications bijectives. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 1

4 Relations-aires30

I Définitions. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30

I.1 Relations orientées et non orientées. . . . . . . . . . . . . . . . . . . . . . . . 30 I.2 Relations équivalentes, relations égales. . . . . . . . . . . . . . . . . . . . . . 31 I.3 Interprétation fonctionnelle. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 I.4 SGBD. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 II Projections. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 II.1 Définitions. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 II.2 Théorème des projections. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32

III Opérations sur les relations-aires. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33

III.1 Somme et produit. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 III.2 Réunion et intersection. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 III.3 Produit cartésien. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 IV Sélection d'une relation-aire. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34

V Dépendances fonctionnelles et clés. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34

V.1 Dépendances fonctionnelles. . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 V.2 Théorème des dépendances fonctionnelles. . . . . . . . . . . . . . . . . . . . . 35 V.3 Clés. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35

II Arithmétique37

5 Ensembles de nombres entiers38

I Nombres entiers naturels (N). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38 I.1 Définition deN. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38 I.2 Opérations et relation d'ordre dansN. . . . . . . . . . . . . . . . . . . . . . . 40 I.3 Nombres premiers. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 I.4 Relation de divisibilité. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41 I.5 Entiers relatifs. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42 II Division euclidienne dansZet applications. . . . . . . . . . . . . . . . . . . . . . . . 43 II.1 Définition. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43 II.2 Représentation des nombres entiers. . . . . . . . . . . . . . . . . . . . . . . . 43 II.3 Arithmétique modulo. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45 II.4 Division " entière» informatique et division euclidienne. . . . . . . . . . . . . 47 II.5 Arithmétique modulondans les ordinateurs. . . . . . . . . . . . . . . . . . . 48 III Algorithmes d'Euclide et applications. . . . . . . . . . . . . . . . . . . . . . . . . . . 51 III.1 PGCD de deux entiers. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51 III.2 Algorithme d'Euclide. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51 III.3 Théorème de Bézout. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52 III.4 Algorithme d'Euclide généralisé. . . . . . . . . . . . . . . . . . . . . . . . . . 53

6 Représentation des nombres réels en machine55

I Introduction. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55 II Les formats IEEE. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55 II.1 La norme IEEE 754. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55 II.2 Format " single». . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56 II.3 Format " double ». . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56 II.4 Format " extended ». . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57 II.5 D'une manière générale.... . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57 II.6 Format " extended » des microprocesseurs.. . . . . . . . . . . . . . . . . . . . 58

III Réels représentables et précision. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59

2

7 Cryptologie et arithmétique.61

I Méthodes de cryptage " à clé publique ». . . . . . . . . . . . . . . . . . . . . . . . . . 61

I.1 Principe. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61 I.2 Utilisation de l'indicatrice d'Euler. . . . . . . . . . . . . . . . . . . . . . . . . 62 II Choix d'un nombre n. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63 II.1 Nombres premiers. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63 II.2 Décomposition en facteurs premiers. . . . . . . . . . . . . . . . . . . . . . . . 63

8 Tests de primalité65

I Théorème de Fermat. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65 II Test de Miller-Rabin. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65 III Tests de Lucas, Selfridge et Pocklington. . . . . . . . . . . . . . . . . . . . . . . . . . 66

9 Décomposition en facteurs premiers67

I Divisions successives. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67 II Algorithme de Monte-Carlo (1975). . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67 II.1 Présentation. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67 II.2 L'algorithme. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68 II.3 Discussion. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69 III Algorithme du crible quadratique QS de Pomerance. . . . . . . . . . . . . . . . . . . . 69 IV Algorithme?de Pollard. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69 V Algorithme de Lenstra (courbes elliptiques). . . . . . . . . . . . . . . . . . . . . . . . 71 V.1 Introduction aux courbes elliptiques. . . . . . . . . . . . . . . . . . . . . . . . 71 V.2 Algorithme de Lenstra. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71

III Logique72

10 Algèbre de Boole73

I Propriétés générales. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73

II Règles de calcul dans une algèbre de Boole. . . . . . . . . . . . . . . . . . . . . . . . 74

III Fonctions booléennes. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75

III.1 Définitions. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75 III.2 Fonctions booléennes élémentaires. . . . . . . . . . . . . . . . . . . . . . . . . 76 III.3 Correspondance entre maxtermes et mintermes. . . . . . . . . . . . . . . . . . 77 III.4 Principaux résultats concernant mintermes et maxtermes. . . . . . . . . . . . . 77 III.5 Formes canoniques d'une fonction booléenne. . . . . . . . . . . . . . . . . . . 78 IV Diagrammes de Karnaugh. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80

V Résolution d'équations booléennes. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83

VI Méthode des consensus. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84

11 Calcul propositionnel89

I Introduction. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89 II Les fondements de la logique des propositions. . . . . . . . . . . . . . . . . . . . . . . 89 II.1 Les propositions. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89 II.2 Les connecteurs logiques. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90 II.3 Variables et formules propositionnelles. . . . . . . . . . . . . . . . . . . . . . 93 III Sémantique du calcul propositionnel. . . . . . . . . . . . . . . . . . . . . . . . . . . . 96 III.1 Fonctions de vérité. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96 III.2 Formules propositionnelles particulières. . . . . . . . . . . . . . . . . . . . . . 96 III.3 Conséquences logiques. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98 III.4 Formules équivalentes. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99 3 III.5 Simplification du calcul des fonctions de vérité. . . . . . . . . . . . . . . . . . 100 III.6 Conclusion. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103

12 Calcul propositionnel : déductions syntaxiques104

I Présentation de la théorie de la démonstration. . . . . . . . . . . . . . . . . . . . . . . 104

II Axiomes logiques et règles d'inférence du système formel " PR ». . . . . . . . . . . . . 104

III Démonstrations avec ou sans hypothèses. . . . . . . . . . . . . . . . . . . . . . . . . . 105

III.1 Démonstration d'un théorème. . . . . . . . . . . . . . . . . . . . . . . . . . . 105 III.2 Démonstration sous hypothèses. . . . . . . . . . . . . . . . . . . . . . . . . . 106

IV Théorème de la déduction. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106

V Quelques théorèmes classiques et quelques règles d'inférence annexes. . . . . . . . . . 109

VI Théorèmes de complétude du calcul propositionnel. . . . . . . . . . . . . . . . . . . . 110

13 Calcul des prédicats112

I Introduction. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112 I.1 Introduction aux "prédicats ». . . . . . . . . . . . . . . . . . . . . . . . . . . 112 I.2 Introduction à l'"univers du discours». . . . . . . . . . . . . . . . . . . . . . 112 I.3 Introduction à la "quantification ». . . . . . . . . . . . . . . . . . . . . . . . . 112

II Définitions. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112

II.1 Termes. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112 II.2 Prédicats et atomes. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113 III Quantificateurs. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113 III.1 Quantificateur universel. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113 III.2 Quantificateur existentiel. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114 III.3 Alternance de quantificateurs. . . . . . . . . . . . . . . . . . . . . . . . . . . . 114 III.4 Portée d'un quantificateur. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115 III.5 Formules du calcul des prédicats. . . . . . . . . . . . . . . . . . . . . . . . . . 116

IV Sémantique. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 116

IV.1 Valeurs de vérité. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 116 IV.2 Simplification de formules quantifiées. . . . . . . . . . . . . . . . . . . . . . . 117 IV.3 Substitutions. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119

14 Méthode de résolution120

I Cas propositionnel. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 120 I.1 Clauses propositionnelles. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 120 I.2 Résolvantes d'une paire de clauses. . . . . . . . . . . . . . . . . . . . . . . . . 121 I.3 Résolution d'un ensemble de clauses. . . . . . . . . . . . . . . . . . . . . . . 121 II Formes normales en logique des prédicats. . . . . . . . . . . . . . . . . . . . . . . . . 122 II.1 Forme prénexe. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122 II.2 Forme de Skolem. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123 II.3 Forme clausale. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 124

III Résolution en logique des prédicats. . . . . . . . . . . . . . . . . . . . . . . . . . . . 124

III.1 Résolvante d'une paire de clauses. . . . . . . . . . . . . . . . . . . . . . . . . 124 III.2 Résolution d'un ensemble de clauses. . . . . . . . . . . . . . . . . . . . . . . 124 III.3 Mise en oeuvre de la résolution. . . . . . . . . . . . . . . . . . . . . . . . . . . 125

IV Langages, grammaires et automates127

15 Compilation, langages et grammaires128

I Introduction à la compilation. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 128

I.1 Le problème posé est.... . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 128 4 I.2 Les diverses phases d'une compilation. . . . . . . . . . . . . . . . . . . . . . . 128 II Les grammaires. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 129 II.1 Définition de la notion de grammaire. . . . . . . . . . . . . . . . . . . . . . . 129 II.2 Le formalisme BNF. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 129 II.3 Les symboles terminaux. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 129 II.4 Les symboles non terminaux. . . . . . . . . . . . . . . . . . . . . . . . . . . . 130 II.5 Exercices. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 130 III Un exemple complet. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 131 III.1 Principes généraux. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 131 III.2 La grammaire du langage. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 131 III.3 Analyseur syntaxique pur. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 132 III.4 Analyseur syntaxique avec messages d'erreur. . . . . . . . . . . . . . . . . . . 132 III.5 Analyseur syntaxique avec interprétation sémantique. . . . . . . . . . . . . . . 133

16 Introduction aux expressions rationnelles135

I Présentation. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 135

II Règles de définition. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 135

III Propriétés des opérateurs. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 136

IV De nouvelles abréviations. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 137

V Universalité des expressions rationnelles. . . . . . . . . . . . . . . . . . . . . . . . . . 137

17 Automates Finis138

I Automates finis. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 138 I.1 Introduction. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 138 I.2 Mécanismes. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 138

II Automates finis à comportement déterminé. . . . . . . . . . . . . . . . . . . . . . . . 139

II.1 Définition. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 139 II.2 Automates finis avec sorties (machines de Moore et de Mealy). . . . . . . . . . 141 II.3 Automates de Moore. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 142

III Langage associé à un automates de Moore. . . . . . . . . . . . . . . . . . . . . . . . . 142

III.1 Définition du langage. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 142 III.2 Exemple et exercices. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 142

IV Automates finis à comportement non déterminé. . . . . . . . . . . . . . . . . . . . . . 144

IV.1 Définitions et exemples. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 144quotesdbs_dbs5.pdfusesText_10

[PDF] environnement fle a2

[PDF] fiche pedagogique environnement fle

[PDF] cornériser définition

[PDF] la démocratie dans le monde daujourdhui pdf

[PDF] arguments pour la démocratie

[PDF] vocabulaire environnement fle

[PDF] signifiant signifié référent

[PDF] signifiant signifié semiologie

[PDF] machine pour fabrication de bonbon

[PDF] signification emoji francais

[PDF] insérer note de bas de page openoffice

[PDF] openoffice note de bas de page sur deux pages

[PDF] numérotation bas de page open office

[PDF] dans un traitement de texte comment doit-on faire pour numéroter automatiquement les pages ?

[PDF] note de bas de page exemple