Ordine lessicografico

Template:F L'ordine lessicografico è un criterio di ordinamento di stringhe costituite da una sequenza di simboli per cui è 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

Un alfabeto finito totalmente ordinato di simboli è un insieme $\mathrm{\Sigma }=({\delta }_1,{\delta }_2,....{\delta }_n)$, dotato di un ordine totale ${\delta }_1<{\delta }_2<\dots <{\delta }_n$.

Date due sequenze di simboli

$I={\delta }_{i_1}{\delta }_{i_2}\dots {\delta }_{i_n}$

$J={\delta }_{j_1}{\delta }_{j_2}\dots {\delta }_{j_m}$,

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

${\delta }_{i_{k+1}}<{\delta }_{j_{k+1}}$

$k=n\wedge n<m$.

Algoritmo di confronto

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\to n+1$)
  • se questi sono diversi, il loro ordine è l'ordine delle stringhe

L'ordine lessicografico sull'insieme prodotto

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

$A_1\times A_2\times \dots \times A_n$

è dato da

$(a_1,a_2,\dots ,a_n){<}^d(b_1,b_2,\dots ,b_n)⟺(\mathrm{\exists }m>0)(\mathrm{\forall }i<m)(a_i=b_i)\wedge (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=\dots =A_n=\mathrm{\Sigma }$, con lo stesso ordine totale, si ottiene la definizione precedentemente data.

Proprietà

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

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,\dots$ 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 $𝐚=x_1^{a_1}{x}_2^{a_2}\dots$ e $𝐛=x_1^{b_1}{x}_2^{b_2}\dots$, con $a_i,b_i\in \mathbb{Z}$, sono due monomi, e $k$ è il minimo valore per cui $a_k\ne b_k$, allora $𝐚<𝐛\iff a_k<b_k$, e $𝐚>𝐛\iff a_k>b_k$.

Voci correlate

• Relazione binaria
• Ordine alfabetico
• Ordinamento sul grado totale

Collegamenti esterni

• Template:Collegamenti esterni