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.

Definizione[modifica | modifica wikitesto]

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.

Algoritmo di confronto[modifica | modifica wikitesto]

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

  • si pone n = 1
  • si confrontano i simboli nella posizione n-esima della stringa:
    • se una delle due stringhe non possiede l'elemento n-esimo, allora è minore dell'altra e l'algoritmo termina
    • se entrambe le stringhe non possiedono 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)
    • se questi sono diversi, il loro ordine è l'ordine delle stringhe

L'ordine lessicografico sull'insieme prodotto[modifica | modifica wikitesto]

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.

Proprietà[modifica | modifica wikitesto]

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

Monomi[modifica | modifica wikitesto]

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.

Voci correlate[modifica | modifica wikitesto]

matematica Portale Matematica: accedi alle voci di Wikipedia che trattano di matematica