title: Ordine lessicografico
text: # Ordine lessicografico
  
  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 $\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}}$,
  
  si dice 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}}$
      $k=n\land 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\rightarrow n+1$)
     * se questi sono diversi, il loro ordine è l'ordine delle stringhe
  
  ## 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.
  
  ## 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},\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}\neq b_{k}$, allora $\mathbf {a} <\mathbf {b} \Leftrightarrow a_{k}<b_{k}$, e $\mathbf {a} >\mathbf {b} \Leftrightarrow a_{k}>b_{k}$.
  
  