Les buts principaux de cet ouvrage qui comble un vide sont de : - donner les concepts et résultats fondamentaux sur les ensembles ordonnés finis, - présenter leurs usages dans des domaines variés (de la RO ou l’IA à la micro-économie), - signaler un certain nombre de résultats et de recherches en cours.
Author(s): Nathalie Caspard, Bernard Monjardet, Bruno Leclerc
Edition: 1
Year: 2007
Language: French
Pages: 340
Table des matières......Page 6
Avant-propos......Page 14
1.1 Ensembles ordonnés......Page 19
1.1.1 Ordres et ordres stricts......Page 20
1.1.2 Graphes associés à un ensemble ordonné......Page 23
1.1.3 Diagramme d'un ensemble ordonné......Page 25
1.1.4 Isomorphisme et dualité......Page 26
1.2 Exemples d'usages......Page 28
1.2.1 Mathématiques......Page 29
1.2.2 Biologie......Page 30
1.2.3 Informatique......Page 31
1.2.4 Sciences sociales......Page 32
1.2.5 Recherche opérationnelle......Page 34
1.3 Sous-ensembles ordonnés et extensions......Page 35
1.3.1 Sous-ensembles ordonnés......Page 36
1.3.2 Chaînes, antichaînes et paramètres fondamentaux......Page 37
1.3.3 Extensions......Page 39
1.4.1 Infimums, supremums, éléments irréductibles......Page 42
1.4.2 Parties commençantes, parties finissantes......Page 45
1.5 Opérations entre ensembles ordonnés......Page 46
1.5.1 Substitution, sommes cardinale et ordinale, produit lexicographique......Page 47
1.5.2 Produit direct......Page 50
1.6 Compléments et références......Page 51
1.7 Exercices......Page 56
2. Classes particulières d'ensembles ordonnés......Page 60
2.1 Ensembles ordonnés rangés, semi-modulaires et bipartis......Page 61
2.2 Ensembles ordonnés définis par configurations exclues......Page 67
2.3 Ensembles ordonnés latticiels : demi-treillis et treillis......Page 69
2.4 Ensembles totalement ordonnés et tournois......Page 75
2.5 Compléments et références......Page 79
2.6 Exercices......Page 84
3. Morphismes d'ensembles ordonnés......Page 87
3.1 Applications isotones et antitones : exponentiation......Page 89
3.2 Parties sup-génératrices et inf-génératrices......Page 90
3.3 Fermetures et ouvertures......Page 96
3.4 Applications résiduées, résiduelles, galoisiennes......Page 100
3.5 Correspondance de Galois associée à une relation......Page 106
3.5.1 Treillis de Galois......Page 107
3.5.2 Table d'un ensemble ordonné......Page 109
3.5.3 Complété d'un ensemble ordonné......Page 112
3.6 Compléments et références......Page 115
3.7 Exercices......Page 119
4. Chaînes et antichaînes......Page 124
4.1 Le théorème de Dilworth......Page 125
4.2 Couplages et transversales dans un ensemble ordonné biparti......Page 129
4.3 La propriété de Sperner......Page 133
4.4 Produits directs de chaînes......Page 137
4.5 Compléments et références......Page 142
4.6 Exercices......Page 145
5. Ensembles ordonnés et treillis distributifs......Page 148
5.1 Treillis distributifs......Page 149
5.2 Treillis distributif associé à un ensemble ordonné......Page 153
5.3 Représentations d'un treillis distributif......Page 156
5.4 Dualités entre préordres et topologies et entre ensembles ordonnés et treillis distributifs......Page 162
5.5 Dualité entre ordres et fuseaux d'ordres totaux......Page 169
5.6 Compléments et références......Page 174
5.7 Exercices......Page 178
6. Codages et dimensions des ordres......Page 183
6.1 Codages booléens et dimension booléenne d'un ensemble ordonné......Page 185
6.2 Dimension d'un ensemble ordonné......Page 190
6.3 Ensembles ordonnés de dimension 2......Page 199
6.4 k-dimension d'un ensemble ordonné......Page 202
6.5 Compléments et références......Page 207
6.6 Exercices......Page 212
7.1 Modélisation des préférences......Page 215
7.2 Agrégation des préférences : théorèmes Arrowiens pour ordres......Page 228
7.3 Les rôles des ordres en classification......Page 238
7.4 Analyse galoisienne des données : fermetures et implications......Page 252
7.5.1 Problème d'ordonnancement à 1 machine......Page 265
7.5.2 Problème d'ordonnancement à m machines......Page 266
7.5.3 Problème d'ordonnancement à 2 étapes (et 2 machines)......Page 269
7.6.1 Modélisation des préférences......Page 273
7.6.2 Agrégation des préférences : théorèmes arrowiens pour ordres......Page 275
7.6.3 Les rôles des ordres en classification......Page 278
7.6.4 Analyse galoisienne des données : fermetures et implications......Page 280
7.6.5 Ordonnancements......Page 282
7.7.1 Modélisation des préférences......Page 283
7.7.2 Agrégation des préférences : théorèmes arrowiens pour ordres......Page 286
7.7.3 Les rôles des ordres en classification......Page 288
7.7.4 Analyse galoisienne des données : fermetures et implications......Page 290
7.7.5 Ordonnancements......Page 291
A. Questions de complexité......Page 293
A.1 Théorie de la complexité......Page 294
A.2 Résultats de complexité......Page 299
A.2.1 Problèmes faciles (algorithmes polynomiaux)......Page 300
A.2.2 Problèmes difficiles (algorithmes exponentiels)......Page 304
A.2.3 Problèmes difficiles et classes particulières d'ordres......Page 306
B. Les 58 types d'ordres connexes à au plus 5 éléments......Page 309
C. Nombres d'ordres et de types d'ordres......Page 311
D.1 Internet et l'incontournable Google......Page 313
D.2 Livres......Page 314
D.4 Textes de synthèse et comptes-rendus de conférences......Page 315
D.5 Logiciels......Page 317
Bibliographie......Page 318
Liste des symboles......Page 344
C......Page 347
E......Page 348
I......Page 349
P......Page 350
R......Page 351
W......Page 352
