Ordine lessicografico

Da Wikipedia, l'enciclopedia libera.

L'ordine lessicografico è un criterio di ordinamento di stringhe costituite da una sequenza di simboli, per i quali è già presente un ordine interno. La regola di ordinamento corrisponde a quella utilizzata nei dizionari (da cui deriva il nome), anche se estesa ad un qualunque insieme di simboli.

Indice

1 Definizione
2 Algoritmo di confronto
3 L'ordine lessicografico sull'insieme prodotto
4 Proprietà
5 Monomi
6 Voci correlate

[modifica] Definizione

Un alfabeto finito totalmente ordinato di simboli è un insieme $\Sigma = \left ( \delta_1, \delta_2,.... \delta_n \right )$ , dotato di un ordine totale $\delta_1 < \delta_2 < ,\, \ldots < \delta_n$ .

Date due sequenze di simboli

$I = \delta_{i_1}\delta_{i_2}\ldots\delta_{i_n}$

$J = \delta_{j_1}\delta_{j_2}\ldots\delta_{j_m}$ ,

diciamo che $I < J$ se esiste un numero $k \in \mathbb{N}$ per cui $\delta_{i_1}\delta_{i_2}\ldots\delta_{i_k} = \delta_{j_1}\delta_{j_2}\ldots\delta_{j_k}$ e vale una delle seguenti relazioni:

$\delta_{i_{k+1}} < \delta_{j_{k+1}}$

n = k < m

[modifica] Algoritmo di confronto

La regola data sopra è equivalente al seguente algoritmo di confronto:

$n = 1$ ;

si confrontano i simboli nella posizione n-esima della stringa;

* se questi sono diversi, il loro ordine è l'ordine delle stringhe;

* se una delle due stringhe non possiede l'elemento n-esimo, allora è minore dell'altra e l'algoritmo termina;

* se entrambe le stringhe non possidono l'elemento n-esimo, allora sono uguali e l'algoritmo termina;

* se i simboli sono uguali, si passa alla posizione successiva della stringa ( $n \rightarrow n + 1$ ).

[modifica] L'ordine lessicografico sull'insieme prodotto

Data una famiglia di insiemi $\mathcal{A} = \left \{ A_1 ,\, A_2 ,\, \ldots ,\, A_n \right \}$ , con i rispettivi ordini totali $\left \{ <_1 ,\, <_2 ,\, \ldots ,\, <_n \right \}$ , l'ordine lessicografico dell'insieme prodotto

$A_1 \times A_2 \times \ldots \times A_n$

è dato da

$(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)$ .

Con questa regola ogni posizione della stringa può corrispondere a simboli e criteri di ordinamento diversi; per $A_1 = A_2 = \ldots = A_n = \Sigma$ , con lo stesso ordine totale, si ottiene la definizione precedentemente data.

[modifica] Proprietà

La relazione tra stringhe definita dall'insieme lessicografico è di ordine parziale stretto, e gode pertanto della proprietà transitiva e asimmetrica.

[modifica] Monomi

In algebra, e particolarmente in algebra computazionale è fondamentale avere un ordinamento sui termini di un polinomio (ovvero un ordine monomiale); questo problema può essere risolto con una variante dell'ordine lessicografico. In pratica, dato un alfabeto (ordinato) di variabili $x_1, x_2, \ldots$ si possono ordinare tutti i monomi considerando dapprima l'esponente di $x 1$ , quindi l'esponente di $x 2$ , e così via, finché non si trova una differenza tra gli esponenti. A questo punto, si considera minore il monomio per cui l'esponente è minore.

In simboli, se $\mathbf{a} = x_1^{a_1}x_2^{a_2}\ldots$ e $\mathbf{b} = x_1^{b_1}x_2^{b_2}\ldots$ , con $a_i, b_i \in \mathbb{Z}$ , sono due monomi, e $k$ è il minimo valore per cui $a_k \ne b_k$ , allora $\mathbf{a} < \mathbf{b} \Leftrightarrow a_k < b_k$ , e $\mathbf{a} > \mathbf{b} \Leftrightarrow a_k > b_k$ .