Porządek leksykograficzny

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacja, szukaj

Porządek leksykograficzny – porządek w zbiorze ciągówX^* pewnego zbioru X indukowany przez porządek \preccurlyeq w zbiorze X.

X może być zbiorem liczb całkowitych, zbiorem symboli pewnego alfabetu, lub jakimkolwiek innym zbiorem, którego elementy potrafimy porównywać.

Definicja

Relację leksykograficzną \preccurlyeq między ciągami \alpha, \beta \in X^* ustala się następująco:

  • jeśli istnieje wskaźnik j taki, że \alpha(j) \neq \beta(j), to znajdujemy najmniejszy i o tej własności[a]. Wówczas
  •  \alpha  \preccurlyeq  \beta gdy   \alpha(i)  \preccurlyeq  \beta(i)  lub  \beta  \preccurlyeq  \alpha gdy   \beta(i)  \preccurlyeq  \alpha(i) (tzn. relacja między ciągami jest zgodna z relacją między odpowiednimi elementami)
  • jeśli taki j nie istnieje, to
  • jeśli oba są skończone i tej samej długości, to  \alpha = \beta
  • jeśli oba ciągi są nieskończone, to  \alpha = \beta
  • jeśli są różnej długość np.  \beta jest dłuższy od  \alpha (w szczególności  \beta może być nieskończony), to  \alpha\  \preccurlyeq\  \beta

Przykłady:

  • zakładając naturalny porządek na liczbach, ciąg (1, 0, 0, 0) jest leksykograficznie większy (późniejszy) od ciągu (0, 10, 100, 1000) – na pierwszej różniącej się pozycji liczba w pierwszym ciągu (1) jest większa niż w drugim (0).
  • zakładając porządek alfabetyczny, słowo "krowa" jest większe od słowa "kot" – na pierwszej różniącej się pozycji "r" jest większe od "o".

Nazwa porządku leksykograficznego pochodzi od sposobu w jaki słowa są uporządkowane w słowniku, najpierw według pierwszej litery, następnie według drugiej, i tak dalej.

W teorii ekonomii porządek leksykograficzny ma znaczenie głównie jako prosty przykład preferencji, których nie można przedstawić przy pomocy ciągłej funkcji użyteczności.

Uwagi

  1. istnieje taki na mocy zasady minimum

Linki zewnętrzne[edytuj]