Ordem lexicográfica

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa

Em matemática, uma ordem lexicográfica, (também conhecida como ordem do dicionário, ordem alfabética ), é uma estrutura de ordem natural do produto cartesiano de dois conjuntos ordenados.

Dadas dois conjuntos parcialmente ordenados A e B, a ordem lexicográfica sobre o produto cartesiano A x B é definida como

(a,b) ≤ (a′,b′) se e somente se a < a′ ou (a = a′ e bb′).

O resultado é uma ordem parcial. Se A e B são totalmente ordenados, então o resultado é uma ordem total também.

Mais genericamente, pode-se definir a ordem lexicográfica sobre o produto cartesiano de n conjuntos ordenados, no produto cartesiano de uma família infinita enumerável de conjuntos ordenados, e sobre a união de tais conjuntos.

Motivação e usos[editar | editar código-fonte]

O nome da ordem lexicográfica vem de sua generalização da ordem dada às palavras em um dicionário: uma seqüência de letras (isto é, uma palavra)

a1a2 ... ak

aparece em um dicionário antes de uma seqüência

b1b2 ... bk

se e somente se o primeiro ai que é diferente de bi vem antes de bi no alfabeto. Isso pressupõe que ambos têm o mesmo comprimento; o que geralmente é feito é preencher a palavra mais curta de texto com símbolos para "em branco", e considerar que um branco é um novo elemento mínimo ('inferior').

Para os propóstos de dicionários, etc, pode-se supor que todas as palavras têm o mesmo comprimento, adicionando espaços em branco no final, e considerando o espaço em branco como um caracter especial, que vem antes de qualquer outra letra do alfabeto. Isso também permite a ordenação de frases. Veja ordem alfabética.

Uma propriedade importante da ordem lexicográfica é que ela preserva relações bem-ordenadas, isto é, se A e B são um conjunto bem ordenado, então o conjunto de produtos A × B com a ordem lexicográfica é também bem-ordenado.

Uma exploração importante da ordenação lexicográfica é expressa no esquema de formatação de data da ISO 8601, que expressa uma data no formato YYYY-MM-DD. Este formato de data serve para a ordenação de strings que contenham data sejam ordenadas de forma direta, ficando em ordem cronológica, sem necessidade de um tratamento especial para datas. Note, no entanto, que para que isso funcione, deve haver sempre quatro dígitos para o ano, dois para o mês e dois para o dia, por isso, por exemplo, os dias de um único dígitos devem ser preenchidos com um zero resultando em '01 ',' 02 '... , '09 '.

Caso de vários produtos[editar | editar código-fonte]

Suponha que


  \{ A_1, A_2, \cdots, A_n \}

é uma n-tupla de conjuntos, com os respectivos ordenamentos totais


  \{ <_1, <_2, \cdots, <_n \}

O ordenamento do dicionário


\ \ <^{d}

de


  A_1 \times A_2 \times \cdots \times A_n

é então


  (a_1, a_2, \dots, a_n) <^d (b_1,b_2, \dots, b_n) \iff
    (\exists\ m > 0) \  (\forall\ i < m) (a_i = b_i) \land (a_m <_m b_m)

Ou seja, se um dos termos


 \ \   a_m <_m b_m

e todos os termos anteriores são iguais.

Informalmente,


 \ \  a_1

representa a primeira letra,


 \ \  a_2

a segunda e assim por diante, ao procurar uma palavra num dicionário, daí o nome.

Isto poderia ser declarado de forma mais elegante se definindo recursivamente a ordem de qualquer conjunto


 \ \   C= A_j \times A_{j+1} \times \cdots \times A_k

representada por


 \ \   <^d (C)

Isto irá satisfazer


  a <^d (A_i) a'  \iff (a <_i a')

  (a,b) <^d (A_i \times B) (a',b') \iff 
    a <^d (A_i) a' \lor ( a=a' \  \land \ b <^d (B) b')

onde 
  B = A_{i+1} \times A_{i+2} \times \cdots \times A_n.

Para colocar de forma mais simples, compare os primeiros termos. Se eles são iguais, compare os segundos termos - e assim por diante. A relação entre os primeiros termos correspondentes que não são iguais, determina a relação entre o conjunto inteiro de elementos.

Grupos e espaços vetoriais[editar | editar código-fonte]

Se os conjuntos de componentes são grupos ordenados então o resultado é um grupo não arquimediano, porque por exemplo n(0,1) < (1,0) for all n.

Se os conjuntos de componentes são espaços vetoriais ordenados sobre R (em particular simplesmente R), então o resultado é também um espaço vetorial ordenado.

Ordenamento de seqüências de vários comprimentos[editar | editar código-fonte]

Dado um conjunto parcialmente ordenado A, as considerações acima permitem definir naturalmente uma ordem lexicográfica parcial <^\mathrm{d} sobre o monóide livre A* formado pelo conjunto de todas as sequências finitas de elementos em A, com a concatenação de seqüência como a operação do monóide, como se segue:

u <^\mathrm{d} v se
  • u é um prefixo de v, ou
  • u=wau' e v=wbv', onde w é o maior prefixo comum de u e v, a e b são membros de A tais que a<b, e u' e v' são membros de A*.

Se < é uma ordem total sobre A, então também é a ordem lexicográfica <d em A*. Se A é um alfabeto finito e totalmente ordenado, A* é o conjunto de todos as palavras sobre A, e nós recuperamos o conceito de ordenação no dicionário usado em lexicografia que deu seu nome as ordenações lexicográficas. No entanto, em geral, isto não é um relação bem-ordenada, mesmo que seja no alfabeto A, por exemplo, se A= {a, b}, a linguagem {anb | n ≥ 0} não tem último elemento: ... <d aab <d ab <d b. Uma relação bem-ordenada para strings, baseada na ordem lexicográfica, é a ordem shortlex.

Da mesma forma, também podemos comparar uma string finita e uma infinita, ou duas strings infinitas.

Comparando-se strings de comprimentos diferentes também pode ser modelado como sendo comparações de strings de comprimento infinito preenchendo-se à direita com espaços em branco, se, como de costume, o espaço em branco é o último elemento do alfabeto (ou, se não é originalmente do alfabeto, acrescentando-o como o último elemento).

Generalização[editar | editar código-fonte]

Considere o conjunto de funções f de um conjunto bem ordenado X a um conjunto totalmente ordenado Y. Por duas funções f e g, a ordem é determinada pelos valores para o menor x tal que f(x) ≠ g(x).

Se Y também é bem-ordenado e X é finito, então a ordem resultante é bem-ordenada. Como já foi mostrado acima, se o X é infinito isso não é em geral o caso.

Se X é infinito e Y tem mais de um elemento, então o conjunto resultante YX não é um conjunto contável.

Alternativamente, considere as funções f de um inversamente bem-ordenado X para um bem-ordenado Y com o mínimo de 0, restrito àqueles que são diferentes de zero em apenas um subconjunto finito de X. O resultado é bem-ordenado.

Correspondentemente, podemos também considerar um bem-ordenado X e aplicar a ordem lexicográfica, onde um maior x é uma posição mais significativa. Isso corresponde a exponenciação YX. Se o X e o Ysão contáveis, então o conjunto resultante é também contável.

Monómios[editar | editar código-fonte]

Em álgebra é tradicional se ordenar termos em um polinômio, ordenando os monômios nos indeterminados. Isso é fundamental, para se ter um forma normal. Tais questões são tipicamente deixadas implícitas na discussão entre os seres humanos, mas tem naturalmente de ser tratadas com exatidão na álgebra computacional. Na prática, tem-se um alfabeto de indeterminantes X, Y, ... e as ordens de todos os monômios formados a partir deles, uma variante da ordem lexicográfica. Por exemplo, se se decidir ordenar o alfabeto por

X < Y < ...

e também olhar para os termos mais altos em primeiro lugar, o que significa ordenar

... < X3 < X2 < X

e também

X < Yk for all k.

Há uma certa flexibilidade na ordenação de monômios, e isso pode ser explorado na teoria das bases de Gröbner.

Frações decimais[editar | editar código-fonte]

As frações decimais do ponto decimal, a < b se aplica de forma equivalente para a ordem numérica e a ordem lexicográfica, desde que os números com decimais 9 recorrentes como 0,399999... não estejam incluídos no conjunto de strings que representam os números. Com essa restrição existe uma bijeção de preservação de ordem entre as strings e os números.

Ordem lexicográfica inversa[editar | editar código-fonte]

Em uma variação comum da ordem lexicográfica, se compara elementos através da leitura a partir da direita em vez da esquerda, ou seja, o componente mais à direita é o mais significativo, por exemplo, aplicados em um dicionário de rimas.

No caso de monómios pode-se classificar os expoentes em ordem decrescente, com o expoente da primeira base variável como a chave principal de classificação, por exemplo:

 x^2 y z^2 < x y^3 z^2 .

Alternativamente, a ordenação pode ser feita pela soma dos expoentes, em ordem decrescente.

Ver também[editar | editar código-fonte]