Cours de mathématiques discrètes PDF

MÉTHODES MATHÉMATIQUES POUR LINFORMATIQUE

22 févr. 2013 C'est la raison pour laquelle Jacques Vélu et les éditions Dunod vous proposent avec cet ouvrage cinq vidéos de corrigés d'exercices. Pour ...

Cours de mathématiques discrètes

21 avr. 2008 21 Exercices sur les grammaires langages et automates ... reliée `a la notion mathématique de mise en bijection avec une partie de N? de ...

Mathématiques appliquées à linformatique

www.courstechinfo.be/Math_Info.pdf Exercices sur les nombres entiers en base 10 . ... 2.4 Nombres de codes possibles avec N chiffres en base B ..

Mathématiques pour informaticien

1 mai 2018 Merci `a Jules Desharnais de nous avoir permis d'emprunter certains éléments et exercices des notes de cours qu'il a lui-même rédigées. Nous ...

Mathématiques

Mathématiques pour l'informatique. C o urs & exercices corrigés Exercices d'entraînement corrigés ... 5.2 Étude de l'équation avec second membre .

Mathématiques pour les Médias Numériques

Les exercices et problèmes corrigés classiques ou plus originaux

Corrigés des exercices du livre et en ligne

Or la procédure budgétaire ou la comptabilité de gestion sont des outils qui permettront de réaliser ce type de contrôle avec un jugement porté sur l'atteinte

Mathématiques pour linformatique 1

20 sept. 2021 Exercice 1.6. Bien que complète la preuve de la proposition 1.5 ne fournit pas explicite- ment de proposition équivalente à ? ? ? utilisant ...

??? ????? ?????? ?????? ??????? Algorithmes daccélération de la 5 519

le output to test PDF Combine only pratique Avec exercices et corrigés. Méot Alain. 519/00241/1 ... Mathématiques pour chimistes. Giroux

Exercices de mathématiques - Exo7

Montrer que ? est compatible avec ? et que l'application quotient associée est une bijection. [003032]. Exercice 128 Équivalences sur EE.

Mathématiques pour l’informatique 1 - uliegebe

exercices Larépartitionestlasuivante: WIMS 5 Interrogationdemi-quadri 15 Examendejanvier 80 — Remédiation :Deux séances de remédiation seront organisées les 29 novembre et 6 décembre En cas d’échec à l’interrogation de mi-quadrimestre ces séances sont obligatoires

Searches related to mathématiques pour linformatique avec 309 exercices corrigés pdf PDF

cet ouvrage cinq vidéos de corrigés d’exercices Pour chaque corrigé vous aurez à l’écran toutes les étapes de la solution sous forme d’animations avec les explications détaillées de l’auteur en arrière-plan audio

Qu'est-ce que le manuel de mathématiques pour l'informatique ?

Ce manuel correspond au cours de Mathématiques pour l’informatique du BTS SIO. Il reprend la structure de l’unité de cours, qui se compose de deux modules : Dans la partie Mathématiques, on trouvera le cours, présentant les notions essentielles du programme, des travaux dirigés ainsi que de nombreux exercices corrigés.

Qu'est-ce que les mathématiques et les bases de l'informatique?

Toutes les mathématiques et les bases de l’informatiqueest particulièrement conçu : –pour un accès rapide à une source d’information lors de la résolution de problèmes, –comme aide-mémoire lors de la préparation d’examens, –comme livre de référence pour les personnels de recherche. Chaque chapitre constitue une unité en soi qui réunit :

Quels sont les cours de l'informatique?

Informatique 1:Introduction à l'informatique COURS TD RESUME CONTROLES Langue et Terminologie I COURS CONTROLES smia s2 Analyse 2:Intégration COURS TD RESUME CONTROLES Analyse 3:Formule de Taylor,Développement Limité et Applications COURS TD RESUME CONTROLES ALGEBRE 3:Espaces Vectoriels,Matrices et Déterminants COURS TD RESUME CONTROLES

Quels sont les exercices corrigés de mathématiques ?

Les écritures littérales et les identités remarquables : Il y a 15 fiches d'exercices corrigés de mathématiques ainsi que le cours en vidéo sur les écritures littérales et les identités remarquables, 3 jeux interactifs sur le calcul mental, 2 évaluations et des sujets gratuits de brevet en classe de troisième ( 3ème ).

Math´ematiques pour l'informatique

Christophe GUYEUX

guyeux@iut-bm.univ-fcomte.fr

21 avril 2008

Table des mati`eres

I Th´eorie des ensembles13

1 Introduction`a la th´eorie des ensembles14

I. Rappels de th´eorie des ensembles. . . . . . . . . . . . . . . . . . . . 14

1 Notion premi`ere d'ensemble. . . . . . . . . . . . . . . . . . 14

2 R`egles de fonctionnement. . . . . . . . . . . . . . . . . . . 15

3 Sous-ensembles, ensemble des parties. . . . . . . . . . . . . 16

4 Repr´esentation graphique. . . . . . . . . . . . . . . . . . . . 16

5 Exercices. . . . . . . . . . . . . . . . . . . . . . . . . . . . 17

II. Op´erations sur les ensembles. . . . . . . . . . . . . . . . . . . . . . 18

1´Egalite de deux ensembles. . . . . . . . . . . . . . . . . . . 18

2 R´eunion, intersection. . . . . . . . . . . . . . . . . . . . . . 18

3 Compl´ementation. . . . . . . . . . . . . . . . . . . . . . . . 20

4 Produit cart´esien. . . . . . . . . . . . . . . . . . . . . . . . 20

III. Exercices. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20

2 Relations binaires entre ensembles23

I. D´efinitions. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23

1 D´efinition. . . . . . . . . . . . . . . . . . . . . . . . . . . . 23

2 Remarques. . . . . . . . . . . . . . . . . . . . . . . . . . . 24

3 Exercices. . . . . . . . . . . . . . . . . . . . . . . . . . . . 24

II. Application d'un ensemble dans un autre. . . . . . . . . . . . . . . . 24

1 D´efinition d'une application, d'une relation fonctionnelle. . . 24

2 Image et ant´ec´edent d'un ´el´ement. . . . . . . . . . . . . . . 25

3 Applications injectives. . . . . . . . . . . . . . . . . . . . . 26

4 Applications surjectives. . . . . . . . . . . . . . . . . . . . 27

5 Applications bijectives. . . . . . . . . . . . . . . . . . . . . 29

III. Cardinal et puissance d'un ensemble. . . . . . . . . . . . . . . . . . 30

1 Cas des ensembles finis. . . . . . . . . . . . . . . . . . . . . 30

2 Cas des ensembles infinis. . . . . . . . . . . . . . . . . . . 31

3 Nombre d'infinis. . . . . . . . . . . . . . . . . . . . . . . . 32

IV. Relations d'ordre. . . . . . . . . . . . . . . . . . . . . . . . . . . . 33

1 D´efinition. . . . . . . . . . . . . . . . . . . . . . . . . . . . 33

2 Ordre partiel, ordre total. . . . . . . . . . . . . . . . . . . . 35

3 Exercices. . . . . . . . . . . . . . . . . . . . . . . . . . . . 36

4´El´ements maximaux. . . . . . . . . . . . . . . . . . . . . . 37

5 Treillis. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39

V. Relations d'´equivalence. . . . . . . . . . . . . . . . . . . . . . . . . 41

1 D´efinition. . . . . . . . . . . . . . . . . . . . . . . . . . . . 41

2 Classes d'´equivalence. . . . . . . . . . . . . . . . . . . . . 42

3 Ensemble-quotient. . . . . . . . . . . . . . . . . . . . . . . 44

4 Exercices. . . . . . . . . . . . . . . . . . . . . . . . . . . . 45

VI. Compatibilit´e entre une op´eration et une relation binaire. . . . . . . 46

3 Relationsn-aires48

I. D´efinitions. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48

1 Relations orient´ees et non orient´ees. . . . . . . . . . . . . . 48

2 Relations ´equivalentes, relations ´egales. . . . . . . . . . . . 50

3 Interpr´etation fonctionnelle. . . . . . . . . . . . . . . . . . . 51

4 SGBD. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51

II. Projections. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51

1 D´efinitions. . . . . . . . . . . . . . . . . . . . . . . . . . . 51

2 Th´eor`eme des projections. . . . . . . . . . . . . . . . . . . 52

III. Op´erations sur les relationsn-aires. . . . . . . . . . . . . . . . . . . 52

1 Somme et produit. . . . . . . . . . . . . . . . . . . . . . . . 52

2 R´eunion et intersection. . . . . . . . . . . . . . . . . . . . . 53

3 Produit cart´esien. . . . . . . . . . . . . . . . . . . . . . . . 53

IV. S´election d'une relationn-aire. . . . . . . . . . . . . . . . . . . . . 53 V. D´ependances fonctionnelles et cl´es. . . . . . . . . . . . . . . . . . . 54

1 D´ependances fonctionnelles. . . . . . . . . . . . . . . . . . 54

2 Th´eor`eme des d´ependances fonctionnelles. . . . . . . . . . . 55

3 Cl´es. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56

II Arithm´etique57

4 Ensembles de nombres entiers58

I. Nombres entiers naturels (N). . . . . . . . . . . . . . . . . . . . . . 58

1 D´efinition. . . . . . . . . . . . . . . . . . . . . . . . . . . . 58

2 Op´erations et relation d'ordre dansN. . . . . . . . . . . . . 60

3 Nombres premiers. . . . . . . . . . . . . . . . . . . . . . . 60

4 Relation de divisibilit´e. . . . . . . . . . . . . . . . . . . . . 62

5 Entiers relatifs. . . . . . . . . . . . . . . . . . . . . . . . . 63

II. Division euclidienne dansZet applications. . . . . . . . . . . . . . 64

1 D´efinition. . . . . . . . . . . . . . . . . . . . . . . . . . . . 64

2 Repr´esentation des nombres entiers. . . . . . . . . . . . . . 65

3 Arithm´etique modulon. . . . . . . . . . . . . . . . . . . . . 67

4 Division??enti`ere??informatique et division euclidienne. . . 70

5 Arithm´etique modulo2ndans les ordinateurs. . . . . . . . . 71

III. Algorithmes d'Euclide et applications. . . . . . . . . . . . . . . . . 75

1 PGCD de deux entiers. . . . . . . . . . . . . . . . . . . . . 75

2 Algorithme d'Euclide. . . . . . . . . . . . . . . . . . . . . . 75

3 Th´eor`eme de B´ezout. . . . . . . . . . . . . . . . . . . . . . 77

4 Algorithme d'Euclide g´en´eralis´e. . . . . . . . . . . . . . . . 78

5 Repr´esentation des nombres r´eels en machine81

I. Introduction. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81 II. Les formats IEEE. . . . . . . . . . . . . . . . . . . . . . . . . . . . 82

1 La norme IEEE 754. . . . . . . . . . . . . . . . . . . . . . 82

2 Format??single??. . . . . . . . . . . . . . . . . . . . . . . . 83

3 Format??double??. . . . . . . . . . . . . . . . . . . . . . . . 83

4 Format??extended??. . . . . . . . . . . . . . . . . . . . . . 83

5 D'une mani`ere g´en´erale.... . . . . . . . . . . . . . . . . . . 84

6 Format??extended??des microprocesseurs.. . . . . . . . . . 86

III. R´eels repr´esentables et pr´ecision. . . . . . . . . . . . . . . . . . . . 86

6 Cryptologie et arithm´etique90

I. M´ethodes de cryptage??`a cl´e publique??. . . . . . . . . . . . . . . . 90

1 Principe. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90

2 Utilisation de l'indicatrice d'Euler. . . . . . . . . . . . . . . 91

II. Choix d'un nombre n. . . . . . . . . . . . . . . . . . . . . . . . . . 93

1 Nombres premiers. . . . . . . . . . . . . . . . . . . . . . . 93

2 D´ecomposition en facteurs premiers. . . . . . . . . . . . . . 94

7 Tests de primalit´e95

I. Th´eor`eme de Fermat. . . . . . . . . . . . . . . . . . . . . . . . . . 95 II. Test de Miller-Rabin. . . . . . . . . . . . . . . . . . . . . . . . . . 96 III. Tests de Lucas, Selfridge et Pocklington. . . . . . . . . . . . . . . . 96

8 D´ecomposition en facteurs premiers98

I. Divisions successives. . . . . . . . . . . . . . . . . . . . . . . . . . 98 II. Algorithme de Monte-Carlo (1975). . . . . . . . . . . . . . . . . . . 99

1 Pr´esentation. . . . . . . . . . . . . . . . . . . . . . . . . . . 99

2 L'algorithme. . . . . . . . . . . . . . . . . . . . . . . . . . 99

3 Discussion. . . . . . . . . . . . . . . . . . . . . . . . . . . 100

III. Algorithme du crible quadratique QS de Pomerance. . . . . . . . . . 100 IV. Algorithme(p-1)de Pollard. . . . . . . . . . . . . . . . . . . . . 101 V. Algorithme de Lenstra (courbes elliptiques). . . . . . . . . . . . . . 103

1 Introduction aux courbes elliptiques. . . . . . . . . . . . . . 103

2 Algorithme de Lenstra. . . . . . . . . . . . . . . . . . . . . 104

III Logique105

9 Alg`ebre de Boole106

I. Propri´et´es g´en´erales. . . . . . . . . . . . . . . . . . . . . . . . . . . 106

1 D´efinition. . . . . . . . . . . . . . . . . . . . . . . . . . . . 106

2 R`egles de calcul dans une alg`ebre de Boole. . . . . . . . . . 108

II. Fonctions bool´eennes. . . . . . . . . . . . . . . . . . . . . . . . . . 110

1 D´efinitions. . . . . . . . . . . . . . . . . . . . . . . . . . . 110

2 Fonctions bool´eennes ´el´ementaires. . . . . . . . . . . . . . . 111

3 Correspondance entre maxtermes et mintermes. . . . . . . . 113

4 Principaux r´esultats concernant mintermes et maxtermes. . . 114

5 Formes canoniques d'une fonction bool´eenne. . . . . . . . . 115

III. Repr´esentation et simplification des fonctions. . . . . . . . . . . . . 118

1 Diagrammes de Karnaugh. . . . . . . . . . . . . . . . . . . 118

2 M´ethode des consensus. . . . . . . . . . . . . . . . . . . . . 121

IV. Compl´ement : R´esolution d'´equations bool´eennes. . . . . . . . . . . 129

1 Pr´esentation de la m´ethode. . . . . . . . . . . . . . . . . . . 129

2 Exercice. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 130

V. Exercices. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 130

10 Calcul Propositionnel133

I. Introduction. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 133

1 Objets de la logique. . . . . . . . . . . . . . . . . . . . . . 133

2 Production automatique. . . . . . . . . . . . . . . . . . . . 133

3 Des probl`emes de l'´evidence. . . . . . . . . . . . . . . . . . 134

II. Les fondements de la logique des Propositions. . . . . . . . . . . . . 134

1 Les Propositions. . . . . . . . . . . . . . . . . . . . . . . . 134

2 Les connecteurs logiques. . . . . . . . . . . . . . . . . . . . 136

3 Variables et Formes Propositionnelles. . . . . . . . . . . . . 143

III. Premier point de vue : la Logique des valeurs de v´erit´e. . . . . . . . 148

1 Fonctions de v´erit´e. . . . . . . . . . . . . . . . . . . . . . . 148

2 Tautologies, antilogies, cons´equences logiques. . . . . . . . 150

3 Simplification du calcul des fonctions de v´erit´e. . . . . . . . 155

4 Conclusion. . . . . . . . . . . . . . . . . . . . . . . . . . . 158

5 Exercices. . . . . . . . . . . . . . . . . . . . . . . . . . . . 159

IV. Deuxi`eme point de vue : th´eorie de la d´emonstration. . . . . . . . . 162

1 Pr´esentation. . . . . . . . . . . . . . . . . . . . . . . . . . . 162

2 Les axiomes logiques. . . . . . . . . . . . . . . . . . . . . . 163

3 Les r`egles d'inf´erence. . . . . . . . . . . . . . . . . . . . . 164

4 D´emonstrations et d´eductions sous hypoth`eses. . . . . . . . 165

5 Th´eor`eme de la d´eduction. . . . . . . . . . . . . . . . . . . 167

6 Quelques th´eor`emes classiques et quelques r`egles d'inf´erence

annexes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 170 4

7 Technique de l'hypoth`ese suppl´ementaire. . . . . . . . . . . 173

8 M´ethodes de d´emonstration. . . . . . . . . . . . . . . . . . 175

9 Exercices. . . . . . . . . . . . . . . . . . . . . . . . . . . . 176

10 Tableaux de Beth. . . . . . . . . . . . . . . . . . . . . . . . 179

V. Compl´etude du calcul propositionnel. . . . . . . . . . . . . . . . . . 180

1 Th´eor`eme de compl´etude. . . . . . . . . . . . . . . . . . . . 180

2 Th´eor`eme de compl´etude g´en´eralis´e. . . . . . . . . . . . . . 184

11 Calcul des pr´edicats185

I. Introduction. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 185

1 Insuffisances de la formalisation en Calcul Propositionnel. . 185

2 Univers du discours, sujets et individus. . . . . . . . . . . . 187

3 Groupes op´eratoires et termes. . . . . . . . . . . . . . . . . 187

4 Groupes relationnels et atomes. . . . . . . . . . . . . . . . . 189

5 Les quantificateurs. . . . . . . . . . . . . . . . . . . . . . . 190

6 Formules du calcul des pr´edicats. . . . . . . . . . . . . . . . 194

7 Champ d'un quantificateur. . . . . . . . . . . . . . . . . . . 194

II. Th´eorie de la validit´e en calcul des pr´edicats. . . . . . . . . . . . . . 195

1 Extension des valeurs de v´erit´e au calcul des pr´edicats. . . . 195

2´Equivalences classiques entre formules. . . . . . . . . . . . 199

3 Substitutions libres. . . . . . . . . . . . . . . . . . . . . . . 200

4´Elimination et introduction des quantificateurs. . . . . . . . 201

III. Th´eorie de la d´emonstration en calcul des pr´edicats. . . . . . . . . . 202

1 Axiomes et r`egles d'inf´erence. . . . . . . . . . . . . . . . . 202

2 Validit´e des r´esultats ´etablis en calcul propositionnel. . . . . 202

3 Le ( m´eta- ) th´eor`eme de la d´eduction. . . . . . . . . . . . . 202

IV. Le syst`eme formel??PR??. . . . . . . . . . . . . . . . . . . . . . . 203

1 D´efinition. . . . . . . . . . . . . . . . . . . . . . . . . . . . 203

2 Calcul des pr´edicats ´egalitaire. . . . . . . . . . . . . . . . . 203

3 Interpr´etations de??PR??. . . . . . . . . . . . . . . . . . . . 204

4 (M´eta-)Th´eor`eme de compl´etude. . . . . . . . . . . . . . . . 204

5 Satisfiabilit´e et insatisfiabilit´e. . . . . . . . . . . . . . . . . 204

V. Traitement des formules de??PR??. . . . . . . . . . . . . . . . . . . 205

1 Forme pr´enexe. . . . . . . . . . . . . . . . . . . . . . . . . 205

2 Forme de Skolem. . . . . . . . . . . . . . . . . . . . . . . . 207

3 Forme clausale. . . . . . . . . . . . . . . . . . . . . . . . . 208

VI. Syst`eme de Herbrand. . . . . . . . . . . . . . . . . . . . . . . . . . 209

1 Introduction. . . . . . . . . . . . . . . . . . . . . . . . . . . 209

2 Univers, atomes, syst`eme de Herbrand. . . . . . . . . . . . . 209

3 Th´eor`eme de Herbrand. . . . . . . . . . . . . . . . . . . . . 210

4 Algorithme de Herbrand. . . . . . . . . . . . . . . . . . . . 210

12 Algorithme de r´esolution211

I. R´esolution sans variables. . . . . . . . . . . . . . . . . . . . . . . . 211

1 Cadre. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 211

2 Le syst`eme formel RSV. . . . . . . . . . . . . . . . . . . . 211

3 Principes g´en´eraux. . . . . . . . . . . . . . . . . . . . . . . 211

4 Le syst`eme formel RSV. . . . . . . . . . . . . . . . . . . . 211

5 Quelques indications sur les algorithmes de r´esolution. . . . 212

6 Exemples complets de r´esolution. . . . . . . . . . . . . . . . 215

7 Exercices. . . . . . . . . . . . . . . . . . . . . . . . . . . . 219

II. R´esolution avec variable. . . . . . . . . . . . . . . . . . . . . . . . 220

1 Unification. . . . . . . . . . . . . . . . . . . . . . . . . . . 221

2 R´esolution. . . . . . . . . . . . . . . . . . . . . . . . . . . 222

3 Strat´egie de r´esolution. . . . . . . . . . . . . . . . . . . . . 224

4 Exemples complets de r´esolution. . . . . . . . . . . . . . . . 225

5 Exercices. . . . . . . . . . . . . . . . . . . . . . . . . . . . 226

III. Clauses de Horn. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 228

1 D´efinition. . . . . . . . . . . . . . . . . . . . . . . . . . . . 228

2 D´eduction ordonn´ee. . . . . . . . . . . . . . . . . . . . . . 229

3 Le r´esultat ´evoqu´e dans le paragraphe pr´ec´edent. . . . . . . 229

13 Exercices sur la logique230

IV Langages, grammaires et automates232

14 Compilation, langages et grammaires233

I. Introduction `a la compilation. . . . . . . . . . . . . . . . . . . . . . 233

1 Le probl`eme pos´e est.... . . . . . . . . . . . . . . . . . . . . 233

2 Les diverses phases d'une compilation. . . . . . . . . . . . . 233

II. Les grammaires. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 234

1 D´efinition de la notion de grammaire. . . . . . . . . . . . . 234

2 Le formalisme BNF. . . . . . . . . . . . . . . . . . . . . . 235

3 Les symboles terminaux. . . . . . . . . . . . . . . . . . . . 235

4 Les symboles non terminaux. . . . . . . . . . . . . . . . . . 235

5 Exercices. . . . . . . . . . . . . . . . . . . . . . . . . . . . 236

III. Un exemple complet. . . . . . . . . . . . . . . . . . . . . . . . . . 238

1 Principes g´en´eraux. . . . . . . . . . . . . . . . . . . . . . . 238

2 La grammaire du langage. . . . . . . . . . . . . . . . . . . . 238

3 Analyseur syntaxique pur. . . . . . . . . . . . . . . . . . . 239

4 Analyseur syntaxique avec messages d'erreur. . . . . . . . . 240

5 Analyseur syntaxique avec interpr´etation s´emantique. . . . . 240

15 Introduction aux expressions rationnelles242

I. Pr´esentation. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 242 II. R`egles de d´efinition. . . . . . . . . . . . . . . . . . . . . . . . . . . 243 III. Propri´et´es des op´erateurs. . . . . . . . . . . . . . . . . . . . . . . . 244 IV. De nouvelles abr´eviations. . . . . . . . . . . . . . . . . . . . . . . . 245 V. Universalit´e des expressions rationnelles. . . . . . . . . . . . . . . . 245

16 Automates Finis247

I. Automates finis. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 247

1 Introduction. . . . . . . . . . . . . . . . . . . . . . . . . . . 247

2 M´ecanismes. . . . . . . . . . . . . . . . . . . . . . . . . . . 247

II. Automates finis `a comportement d´etermin´e. . . . . . . . . . . . . . 249

1 D´efinition. . . . . . . . . . . . . . . . . . . . . . . . . . . . 249

2 Automates finis avec sorties (machines de Moore et de Mealy)251

3 Automates de Moore. . . . . . . . . . . . . . . . . . . . . . 253

III. Langage associ´e `a un automates de Moore. . . . . . . . . . . . . . . 253

1 D´efinition du langage. . . . . . . . . . . . . . . . . . . . . . 253

2 Exemple et exercices. . . . . . . . . . . . . . . . . . . . . . 254

IV. Automates finis `a comportement non d´etermin´e. . . . . . . . . . . . 255

1 D´efinitions et exemples. . . . . . . . . . . . . . . . . . . . . 255

2 Utilit´e. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 258

V. D´etermination d'un AFND. . . . . . . . . . . . . . . . . . . . . . . 258

1 M´ethode de construction par sous-ensemble. . . . . . . . . . 258

2 En pratique. . . . . . . . . . . . . . . . . . . . . . . . . . . 259

VI. Exercices. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 260

1 Propri´et´es d'un automate `an´etats. . . . . . . . . . . . . . . 261

2 Les palindromes. . . . . . . . . . . . . . . . . . . . . . . . 261

17 Optimisation d'automates finis263

I. Congruences d'automates. . . . . . . . . . . . . . . . . . . . . . . . 263

1 Quelques rappels. . . . . . . . . . . . . . . . . . . . . . . . 263

2 D´efinition. . . . . . . . . . . . . . . . . . . . . . . . . . . . 264

3 Ensemble quotient. . . . . . . . . . . . . . . . . . . . . . . 265

II.´Equivalence de N´erode. . . . . . . . . . . . . . . . . . . . . . . . . 268

1 L'´equivalence. . . . . . . . . . . . . . . . . . . . . . . . . . 268

2 L'algorithme. . . . . . . . . . . . . . . . . . . . . . . . . . 269

III. M´ethode du dual. . . . . . . . . . . . . . . . . . . . . . . . . . . . 271

1 Dual d'un automate. . . . . . . . . . . . . . . . . . . . . . . 271

2 M´ethode du dual. . . . . . . . . . . . . . . . . . . . . . . . 271

IV. Synth`ese. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 274

1 Outils. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 274

2 M´ethodes d'optimisation. . . . . . . . . . . . . . . . . . . . 275

18 Construction d'automates finis`a partir d'expressions rationnelles276

I. Automates `a transitions instantan´ees. . . . . . . . . . . . . . . . . . 276 II. Donn´ees et r´esultat. . . . . . . . . . . . . . . . . . . . . . . . . . . 276 III. Algorithme. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 276 IV. Exemple. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 278 V. Finalisation. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 279

19 Automates`a pile281

I. Automates `a pile, d´eteministes ou pas.. . . . . . . . . . . . . . . . . 281

1 Automate `a pile non d´eterministe. . . . . . . . . . . . . . . 281

2 Automate `a pile d´eterministe. . . . . . . . . . . . . . . . . . 283

II. Calcul dans un automate `a pile. . . . . . . . . . . . . . . . . . . . . 284

1 Encore quelques d´efinitions.... . . . . . . . . . . . . . . . . 284

2 Premiers exemples. . . . . . . . . . . . . . . . . . . . . . . 285

3 Exemple plus complet : le langage{0n1n|n?N?}. . . . . . 286

III. Construction d'un automate `a pile. . . . . . . . . . . . . . . . . . . 287

1 Introduction `a la m´ethode. . . . . . . . . . . . . . . . . . . 287

2 Utilisation d'un symbolisme. . . . . . . . . . . . . . . . . . 287

3 Algorithme de construction. . . . . . . . . . . . . . . . . . . 287

4 Exercices. . . . . . . . . . . . . . . . . . . . . . . . . . . . 288

20 Description d'un langage par une grammaire291

I. Langages. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 291 II. Grammaires. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 292

1 D´efinitions. . . . . . . . . . . . . . . . . . . . . . . . . . . 292

2 Types de grammaires de Chomsky. . . . . . . . . . . . . . . 292

III. Un exemple de grammaire contextuelle. . . . . . . . . . . . . . . . 293

21 Exercices sur les grammaires, langages et automates295

V Th´eorie des graphes297

22 Graphes non orient´es298

I. D´efinitions et premiers exemples. . . . . . . . . . . . . . . . . . . . 298

1 D´efinitions. . . . . . . . . . . . . . . . . . . . . . . . . . . 298

2 Exemples. . . . . . . . . . . . . . . . . . . . . . . . . . . . 298

3 Degr´e, chaˆıne. . . . . . . . . . . . . . . . . . . . . . . . . . 299

4 circuit-cycle. . . . . . . . . . . . . . . . . . . . . . . . . . . 301

5 Exercices. . . . . . . . . . . . . . . . . . . . . . . . . . . . 302

II. Quelques types particuliers de graphes. . . . . . . . . . . . . . . . . 303

1 Graphes planaires. . . . . . . . . . . . . . . . . . . . . . . . 303

2 Multigraphes. . . . . . . . . . . . . . . . . . . . . . . . . . 303

3 Graphes connexes. . . . . . . . . . . . . . . . . . . . . . . 304

4 Graphes complets. . . . . . . . . . . . . . . . . . . . . . . . 304

5 Graphes biparti. . . . . . . . . . . . . . . . . . . . . . . . . 305

6 Exercices. . . . . . . . . . . . . . . . . . . . . . . . . . . . 306

III. Repr´esentation des graphes. . . . . . . . . . . . . . . . . . . . . . . 307

1 Matrice d'incidence. . . . . . . . . . . . . . . . . . . . . . 307

2 Matrice d'adjacence. . . . . . . . . . . . . . . . . . . . . . 308

3 Listes d'adjacence. . . . . . . . . . . . . . . . . . . . . . . 310

23 Graphes eul´eriens, planaires et hamiltoniens312

I. Circuits eul´eriens. . . . . . . . . . . . . . . . . . . . . . . . . . . . 312

1 Introduction : les ponts de K¨onigsberg. . . . . . . . . . . . . 312

2 D´efinitions. . . . . . . . . . . . . . . . . . . . . . . . . . . 313

3 R´esultat d'Euler. . . . . . . . . . . . . . . . . . . . . . . . 314

4 Exercice : les dominos. . . . . . . . . . . . . . . . . . . . . 314

II. Graphes planaires. . . . . . . . . . . . . . . . . . . . . . . . . . . . 314

1 Graphes partiels et sous-graphes. . . . . . . . . . . . . . . . 314

2 Graphe planaire. . . . . . . . . . . . . . . . . . . . . . . . . 318

3 Exemples. . . . . . . . . . . . . . . . . . . . . . . . . . . . 319

4 Probl`emes de d´enombrement. . . . . . . . . . . . . . . . . . 320

5 Caract´erisation des graphes planaires. . . . . . . . . . . . . 321

III. Circuit hamiltonien. . . . . . . . . . . . . . . . . . . . . . . . . . . 322

1 Les dod´eca`edres de Hamilton. . . . . . . . . . . . . . . . . 322

2 D´efinition. . . . . . . . . . . . . . . . . . . . . . . . . . . . 323

3 R´esultat. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 323

4 Le probl`eme du voyageur de commerce. . . . . . . . . . . . 324

24 Arbres et arborescence325

I. Pr´esentation g´en´erale. . . . . . . . . . . . . . . . . . . . . . . . . . 325

1 D´efinitions. . . . . . . . . . . . . . . . . . . . . . . . . . . 325

2 Caract´erisation des arbres. . . . . . . . . . . . . . . . . . . 326

3 Nombre minimal de feuilles. . . . . . . . . . . . . . . . . . 326

4 Exercices. . . . . . . . . . . . . . . . . . . . . . . . . . . . 326

II. Codage de Pr¨ufer. . . . . . . . . . . . . . . . . . . . . . . . . . . . 327

1 Pr´esentation. . . . . . . . . . . . . . . . . . . . . . . . . . . 327

2 Codage. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 327

3 D´ecodage. . . . . . . . . . . . . . . . . . . . . . . . . . . . 331

4 Th´eor`eme de Cayley. . . . . . . . . . . . . . . . . . . . . . 336

5 Exercices. . . . . . . . . . . . . . . . . . . . . . . . . . . . 336

III. Arbres couvrants. . . . . . . . . . . . . . . . . . . . . . . . . . . . 337

1 D´efinition. . . . . . . . . . . . . . . . . . . . . . . . . . . . 337

2 Arbre maximal de poids minimum. . . . . . . . . . . . . . . 338

IV. Arborescence. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 340 9

1 D´efinitions et exemples. . . . . . . . . . . . . . . . . . . . . 340

2 Arborescences ordonn´ees. . . . . . . . . . . . . . . . . . . . 341

3 Codage de Huffman. . . . . . . . . . . . . . . . . . . . . . 343

V. Parcours en largeur d'un graphe. . . . . . . . . . . . . . . . . . . . 348

1 Pr´esentation. . . . . . . . . . . . . . . . . . . . . . . . . . . 348

2 Id´ee de l'algorithme. . . . . . . . . . . . . . . . . . . . . . 348

25 Probl`emes de coloration349

I. Coloration des sommets. . . . . . . . . . . . . . . . . . . . . . . . . 349

1 Notion de stabilit´e. . . . . . . . . . . . . . . . . . . . . . . 349

2 La coloration. . . . . . . . . . . . . . . . . . . . . . . . . . 349

3 Encadrement du nombre chromatique. . . . . . . . . . . . . 350

4 Algorithme de coloration de Welsh et Powell. . . . . . . . . 352

5 Exercices. . . . . . . . . . . . . . . . . . . . . . . . . . . . 352

II. Coloration des sommets d'un graphe planaire. . . . . . . . . . . . . 354

1 Pr´esentation. . . . . . . . . . . . . . . . . . . . . . . . . . . 354

2 Formulation en th´eorie des graphes. . . . . . . . . . . . . . 355

3 Exercice. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 356

III. Coloration des arˆetes. . . . . . . . . . . . . . . . . . . . . . . . . . 356

1 Pr´esentation du probl`eme. . . . . . . . . . . . . . . . . . . . 356

2 Lien avec la coloration des sommets. . . . . . . . . . . . . . 357

3 Exercice. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 358

26 Graphes orient´es359

I. D´efinitions. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 359

1 Digraphe (graphe orient´e), sommet, arc. . . . . . . . . . . . 359

2 Exemples. . . . . . . . . . . . . . . . . . . . . . . . . . . . 360

3 Degr´e d'un sommet d'un digraphe. . . . . . . . . . . . . . . 360

4 Chemins et circuits. . . . . . . . . . . . . . . . . . . . . . . 362

5 Circuits eul´eriens. . . . . . . . . . . . . . . . . . . . . . . . 363

II. Digraphe fortement connexe. . . . . . . . . . . . . . . . . . . . . . 363

1 D´efinitions. . . . . . . . . . . . . . . . . . . . . . . . . . . 363

2 Exercices. . . . . . . . . . . . . . . . . . . . . . . . . . . . 364

III. Matrice et listes d'adjacences. . . . . . . . . . . . . . . . . . . . . . 365

1 Matrice d'incidence. . . . . . . . . . . . . . . . . . . . . . 365

2 Matrice d'adjacences. . . . . . . . . . . . . . . . . . . . . . 366

3 Lien entre matrices d'adjacences et d'incidences. . . . . . . 367

quotesdbs_dbs9.pdfusesText_15

[PDF] philosophie de voltaire

[PDF] dictionnaire philosophique voltaire analyse

[PDF] la matiere et l'esprit def philo

[PDF] mathématique discrète exercice corrigé

[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] Cours de mathématiques discrètes