Ordine lessicografico

Da Wikipedia, l'enciclopedia libera.
Jump to navigation Jump to search

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[modifica | modifica wikitesto]

Un alfabeto finito totalmente ordinato di simboli è un insieme , dotato di un ordine totale .

Date due sequenze di simboli

,

si dice che se esiste un numero per cui e vale una delle seguenti relazioni:

.

Algoritmo di confronto[modifica | modifica wikitesto]

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

  • si pone
  • 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 ()
    • 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 , con i rispettivi ordini totali , l'ordine lessicografico dell'insieme prodotto

è dato da

.

Con questa regola ogni posizione della stringa può corrispondere a simboli e criteri di ordinamento diversi; per , 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 si possono ordinare tutti i monomi considerando dapprima l'esponente di , quindi l'esponente di 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 e , con , sono due monomi, e è il minimo valore per cui , allora , e .

Voci correlate[modifica | modifica wikitesto]

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