Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur Graph Search.
Concept
Ordre lexicographique
Résumé
En mathématiques, un ordre lexicographique est un ordre que l'on définit sur les suites finies d'éléments d'un ensemble ordonné (ou, de façon équivalente, les mots construits sur un ensemble ordonné). Sa définition est une généralisation de l'ordre du dictionnaire : l'ensemble ordonné est l'alphabet, les mots sont bien des suites finies de lettres de l'alphabet. La principale propriété de l'ordre lexicographique est de conserver la totalité de l'ordre initial. On peut définir de façon analogue un ordre lexicographique sur des produits cartésiens d'ensembles ordonnés, dont les éléments sont donc des n-uplets, c’est-à-dire, si l'on veut, des suites finies de longueur fixée.
Bien que l'ordre du dictionnaire soit manipulé dès l'école primaire, on va commencer la formalisation par un cas simple, celui du produit cartésien binaire. C’est-à-dire que les mots de notre dictionnaire ne seront composés tout d'abord que de deux lettres.
Les ensembles (A, ≤) et (B, ≤) sont tous deux ordonnés, l'ordre étant noté de la même façon pour les deux ensembles, une liberté qui ne devrait troubler personne. L'ordre lexicographique sur A × B, que l'on note encore ≤, est défini de la façon suivante, pour (a,b) et (a’,b’) deux couples de A × B :
(a,b) ≤ (a’,b’) si et seulement si [a < a’ ou (a = a’ et b ≤ b’)]
et on en déduit facilement la propriété analogue pour l'ordre lexicographique strict :
(a,b) < (a’,b’) si et seulement si [a < a’ ou (a = a’ et b < b’)].
Il s'agit bien de l'ordre du dictionnaire, par exemple :
lu < ne car l < n (on ne regarde que la première lettre)
le < lu car e < u (les premières lettres sont identiques, on regarde la seconde).
Le choix de la première composante pour commencer la comparaison est purement arbitraire, mais, comme illustré par l'exemple alphabétique qui précède, si l'on commence la comparaison par la seconde composante, on obtient un ordre différent.
L'ordre lexicographique sur {0, 1} × {0, 1} ordonnés usuellement donne (0, 0) < (0, 1) < (1, 0) < (1, 1).
De façon générale l'ordre lexicographique sur {0, 1, .
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.