Eléments de mathématiques discrètes
Louis Frécon
Presses Polytechniques et Universitaires Romandes
Département d'informatiqueV
SommaireVII
Première partie Fondements1
Chapitre 0 Mémento de logique3
0.1 Logique des propositions3
0.2 Logique des prédicats11
0.3 Exercices15
0.4 Problèmes17
0.5 Piste de réflexion18
0.6 Lectures18
Chapitre 1 Ensembles & éléments21
1.1 Présentation21
1.2 Inclusions23
1.3 Parties d'un ensemble25
1.4 Union26
1.5 Intersection27
1.6 Différence ensembliste28
1.7 Couvertures29
1.8 Différence symétrique31
1.9 Partitions32
1.10 Paires & produits cartésiens34
1.11 Exercices35
1.12 Problèmes37
1.13 Lectures40
Chapitre 2 Relations binaires41
2.1 Vue en extension41
2.2 Vue en compréhension44
2.3 Relation inverse45
2.4 Union, intersection, finesse46
2.5 Composition46
2.6 Exercices47
2.7 Problèmes48
2.8 Lectures48
Chapitre 3 Fonctions51
3.1 Relations binaires régulières51
3.2 Fonctions51
3.3 Surjection53
3.4 Image & inverse54
3.5 Injection & bijection54
3.6 Synoptiques56
3.7 Composition de fonctions57
3.8 Ensembles dénombrables et finis58
3.9 Relations n-aires59
3.10 Fonctions généralisées61
3.11 Exercices63
3.12 Problèmes64
3.13 Lectures65
Chapitre 4 Relations binaires internes67
4.1 Présentation67
4.2 Propriétés des relations binaires internes68
4.3 Restriction72
4.4 Equivalence72
4.5 Ordres75
4.6 Préordre79
4.7 Récapitulatifs84
4.8 Exercices85
4.9 Problèmes87
4.10 Thèmes de réflexion92
4.11 Lectures94
Chapitre 5 Fonctions, calculabilité, récurrence95
5.1 Calculabilite, decidabilité95
5.2 Calculabilité et récursivité96
5.3 Récursivités convergente, divergente, stationnaire101
5.4 Ensembles récursifs et récursivement énumérables103
5.5 Aux sources de l'arithmétique et de l'algèbre104
5.6 Exercices106
5.7 Problèmes107
5.8 Pistes de réflexion108
5.9 Lectures109
Chapitre 6 Notion de complexité111
6.1 Premier exemple111
6.2 Règles d'estimation de la complexité112
6.3 Préordre de complexité115
6.4 Classes de complexité115
6.5 Optimisation du calcul d'une fonction117
6.6 Représentations d'une table creuse121
6.7 Exercices123
6.8 Problèmes124
6.9 Lectures125
Deuxième partie Graphes127
Chapitre 7 Des points et des flèches129
7.1 Présentation129
7.2 Degrés & demi-degrés129
7.3 Prédécesseurs, successeurs, adjacents130
7.4 Sommets initiaux, terminaux, isolés130
7.5 Sous-graphe130
7.6 Graphe partiel131
7.7 Graphe complet, cliques131
7.8 Représentations131
7.9 Propriétés des relations binaires et graphes associés133
7.10 Propriété faible / propriété forte135
7.11 Graphe valué135
7.12 Exercices136
7.13 Problèmes136
7.14 Thèmes de réflexion137
7.15 Lectures137
Chapitre 8 Chemins & circuits139
8.1 Les chemins139
8.2 Circuits et boucles dans un graphe141
8.3 Chemins élémentaires dans un graphe141
8.4 Recherche de chemins dans un graphe143
8.5 Méthodes matricielles145
8.6 Méthode locale 1 : recherche par niveaux152
8.7 Méthode locale 2 : méthode du meilleur d'abord155
8.8 Méthode locale 3 : recherche en profondeur158
8.9 Problèmes hamiltoniens161
8.10 Problèmes eulériens162
8.11 Exercices164
8.12 Problèmes165
8.13 Thèmes de réflexion169
8.14 Lectures169
Chapitre 9 Fermetures transitives171
9.1 Fermeture transitive et descendance stricte171
9.2 Fermeture réflexo-transitive et descendance large171
9.3 Interprétation des relations quelconques172
9.4 Accessibilité dans les systèmes à états174
9.5 Exercices179
9.6 Problèmes179
9.7 Lectures181
Chapitre 10 Arbres & connexité183
10.1 Chaînes & cycles183
10.2 Graphe (fortement) connexe184
10.3 Composante connexe d'un graphe184
10.4 Composantes fortement connexes185
10.5 Centres, rayon, diamètre d'un graphe185
10.6 Arbres, forêts, hiérarchies, arborescences187
10.7 Arbre couvrant188
10.8 Arbre couvrant minimal189
10.9 Points, ensembles d'articulation190
10.10 Isthme191
10.11 k-Connexité et robustesse structurelle191
10.12 Multi-graphes192
10.13 Exercices196
10.14 Problèmes197
10.15 Pistes de réflexion198
10.16 Vocabulaire198
10.17 Lectures200
Chapitre 11 Graphes multipartis201
11.1 Présentation201
11.2 Tests de multipartisme202
11.3 Jeux & fonctions de Grundy204
11.4 Coloriage de graphes207
11.5 Graphes bipartis212
11.6 Graphes et hypergraphes214
11.7 Exercices218
11.8 Problèmes219
11.9 Pistes de réflexion220
11.10 Lectures220
Troisième partie Algèbres221
Chapitre 12 Opérateurs & algèbres223
12.1 Opérateurs & signatures223
12.2 Syntaxe des expressions224
12.3 Sémantique formelle des expressions225
12.4 Algèbres225
12.5 Propriétés des opérateurs227
12.6 Eléments remarquables pour un opérateur228
12.7 Déparenthésages231
12.8 Propriétés inter-opérateurs236
12.9 Morphismes237
12.10 Formes normales & canoniques239
12.11 Exercices240
12.12 Problèmes241
12.13 Pistes de réflexion242
12.14 Lectures243
Chapitre 13 Monoïdes & groupes245
13.1 Présentation245
13.2 Semi-Groupe248
13.3 Groupe249
13.4 Monoïde finiment engendré251
13.5 Langages formels254
13.6 Grammaires254
13.7 Exercices256
13.8 Problèmes258
13.9 Pistes de réflexion260
13.10 Lectures261
Chapitre 14 Dioïdes263
14.1 Présentation263
14.2 Semi-anneau264
14.3 Anneau264
14.4 Corps265
14.5 Graphe valué265
14.6 Calculs matriciels267
14.7 Thèse centrale267
14.8 Taille illimitée267
14.9 Taille limitée269
14.10 Exemples270
14.11 Graphes multivalués273
14.12 Exercices274
14.13 Problèmes277
14.14 Pistes de réflexion277
14.15 Lectures279
14.16 Famille des dioïdes279
Chapitre 15 Algèbre de Boole281
15.1 Intérêt281
15.2 Algèbre de boole élémentaire282
15.3 Modélisation booléenne de technologies283
15.4 Fonctions booléennes285
15.5 Géométrie booléenne286
15.6 Bases d'une fonction289
15.7 Des sommes de monômes aux produits de clauses300
15.8 Approches dichotomiques305
15.9 Equations booléennes308
15.10 Anneau de Boole309
15.11 Equivalences majeures312
15.12 Exercices313
15.13 Problèmes313
15.14 Piste de réflexion314
15.15 Lectures314
Chapitre 16 Algèbre de Kleene & automates à états finis317
16.1 Notion d'automate à états finis317
16.2 Grammaires de Kleene321
16.3 Algèbre de Kleene322
16.4 Propriété centrale325
16.5 Des expressions régulières aux graphes de transition328
16.6 Synoptique333
16.7 Exercices333
16.8 Problèmes335
16.9 Pistes de réflexion336
16.10 Lectures337
Annexe Indications sur les exercices & problèmes339
Chapitre 0 : Memento de logique339
Chapitre 1 : Ensembles & éléments341
Chapitre 2 : Relations binaires344
Chapitre 3 : Fonctions345
Chapitre 4 : Relations binaires internes348
Chapitre 5 : Fonctions, calculabilité, récurrence352
Chapitre 6 : Notion de complexité354
Chapitre 7 : Des points et des flèches355
Chapitre 8 : Chemins & circuits356
Chapitre 9 : Fermetures transitives357
Chapitre 10 : Arbres & connexité359
Chapitre 11 : Graphes multipartis359
Chapitre 12 : Opérateurs et algèbres361
Chapitre 13 : Monoïdes361
Chapitre 14 : Dioïdes363
Chapitre 15 : Algèbre de Boole364
Chapitre 16 : Algèbres de Kleene & automates à états finis364
Index367