Cours de mathématiques discrètes PDF

Mathématiques pour linformatique 1

20 sept. 2021 Puisque ? ? ? ? ? ? ?. Page 15. CHAPITRE 1. MATHÉMATIQUES DISCRÈTES. 14 les cours de "Mathématiques pour l ...

Cours de mathématiques discrètes

3 nov. 2010 Mathématiques pour l'informatique ... si le critère de Selfridge appliqué aux diviseurs premiers de F aboutit à un succès. – et si F >R

Mathématiques discrètes appliquées à la cryptographie symétrique

10 oct. 2019 L'archive ouverte pluridisciplinaire HAL est destinée au dépôt et à la diffusion de documents scientifiques de niveau recherche

MATHÉMATIQUES DISCRÈTES

Le système de codage informatique des couleurs RGB (de l'anglais ”Red

Cours de mathématiques discrètes

21 avr. 2008 Mathématiques pour l'informatique ... de la division des réels qui est appliqué et non celui de la division euclidienne des entiers.

Evaluation du master Mathématiques et applications de Aix

29 juin 2017 discrètes et fondements de l'informatique qui propose un double diplôme avec ... La spécialité Mathématiques appliquées et sciences sociales ...

Programme Pédagogique National du DUT « INFORMATIQUE

Types de formation pouvant conduire au « DUT Informatique » autres matières informatiques mathématiques appliquées

MÉTHODES MATHÉMATIQUES POUR LINFORMATIQUE

22 févr. 2013 dernier contact avec les Mathématiques discrètes ... mention informatique et mention mathématiques appliquées

LICENCE

Master mention Mathématiques et informatique appliquées aux sciences humaines et sociales La mineure « Mathématiques Discrètes Codes

LICENCE MENTION LLCER (Langues littératures et civilisations

Où ? UFR MIM (Mathématiques informatique

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

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

quotesdbs_dbs6.pdfusesText_11

[PDF] Cours de mathématiques discrètes