Porządek leksykograficzny


Porządek leksykograficzny w encyklopedii

Z Wikipedii, wolnej encyklopedii Przejdź do nawigacji Przejdź do wyszukiwania

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

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

Spis treści

Definicja | edytuj kod

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

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

Przykłady | edytuj kod

  • 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 | edytuj kod

  1. Istnieje taki na mocy zasady minimum.

Linki zewnętrzne | edytuj kod

Na podstawie artykułu: "Porządek leksykograficzny" pochodzącego z Wikipedii
OryginałEdytujHistoria i autorzy