Ordine lessicografico

Questa voce o sezione sull'argomento matematica non cita le fonti necessarie o quelle presenti sono insufficienti.

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.

Un alfabeto finito totalmente ordinato di simboli è un insieme ${\displaystyle \Sigma =\left(\delta _{1},\delta _{2},....\delta _{n}\right)}$, dotato di un ordine totale ${\displaystyle \delta _{1}<\delta _{2}<\,\ldots <\delta _{n}}$.

Date due sequenze di simboli

${\displaystyle I=\delta _{i_{1}}\delta _{i_{2}}\ldots \delta _{i_{n}}}$

${\displaystyle J=\delta _{j_{1}}\delta _{j_{2}}\ldots \delta _{j_{m}}}$,

si dice che ${\displaystyle I<J}$ se esiste un numero ${\displaystyle k\in \mathbb {N} }$ per cui ${\displaystyle \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:

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

${\displaystyle k=n\land n<m}$.

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

• si pone ${\displaystyle 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 (${\displaystyle n\rightarrow n+1}$)
  • se questi sono diversi, il loro ordine è l'ordine delle stringhe

Data una famiglia di insiemi ${\displaystyle {\mathcal {A}}=\left\{A_{1},\,A_{2},\,\ldots ,\,A_{n}\right\}}$, con i rispettivi ordini totali ${\displaystyle \left\{<_{1},\,<_{2},\,\ldots ,\,<_{n}\right\}}$, l'ordine lessicografico dell'insieme prodotto

${\displaystyle A_{1}\times A_{2}\times \ldots \times A_{n}}$

è dato da

${\displaystyle (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 ${\displaystyle A_{1}=A_{2}=\ldots =A_{n}=\Sigma }$, con lo stesso ordine totale, si ottiene la definizione precedentemente data.

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

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 ${\displaystyle x_{1},x_{2},\ldots }$ si possono ordinare tutti i monomi considerando dapprima l'esponente di ${\displaystyle x_{1}}$, quindi l'esponente di ${\displaystyle 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 ${\displaystyle \mathbf {a} =x_{1}^{a_{1}}x_{2}^{a_{2}}\ldots }$ e ${\displaystyle \mathbf {b} =x_{1}^{b_{1}}x_{2}^{b_{2}}\ldots }$, con ${\displaystyle a_{i},b_{i}\in \mathbb {Z} }$, sono due monomi, e ${\displaystyle k}$ è il minimo valore per cui ${\displaystyle a_{k}\neq b_{k}}$, allora ${\displaystyle \mathbf {a} <\mathbf {b} \Leftrightarrow a_{k}<b_{k}}$, e ${\displaystyle \mathbf {a} >\mathbf {b} \Leftrightarrow a_{k}>b_{k}}$.

• Relazione binaria
• Ordine alfabetico
• Ordinamento sul grado totale

• (EN) Eric W. Weisstein, Lexicographic Order, su MathWorld, Wolfram Research.

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