Лексикографический порядок — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Ссылки)
Строка 1: Строка 1:
 
== Определение ==
 
== Определение ==
Пусть дано множество <math>~A=\{a_1<a_2<a_3<...<a_k\}</math> и <math>A^*=\bigcup^{\infty}_{i=0} A^i</math>, тогда после лексикографического упорядочивания элементов множества<math>~A^*</math> любые два элемента (пусть <math>~x<y; x,y \in A^*; x=\{x_1,x_2,...,x_{i_1}\}; y=\{y_1,y_2,...,y_{i_2}\}; x_j,y_j \in A</math>) этого множества будут удовлетворять условиям:
+
Пусть дано линейно упорядоченное множество <tex>~A=\{a_1<a_2<a_3<...<a_k\}</tex> - алфавит, <tex>A^*</tex> назовем множество подпоследовательностей конечной длины из алфавита <tex> A </tex>, <tex>A^*=\bigcup^{\infty}_{i=0} A^i</tex>, тогда лексикографическим порядком на множестве <tex>~A^*</tex> назовем такой порядок, при котором любые два элемента из множества <tex>A^*</tex> удовлетворяют условиям:
* либо <math>~i_2>i_1</math> и <math>\forall j\le{i_1}:x_j=y_j</math>
+
* пусть <tex>~x<y; x,y \in A^*; x=\{x_1,x_2,...,x_{i_1}\}; y=\{y_1,y_2,...,y_{i_2}\}; x_j,y_j \in A</tex>) этого множества будут удовлетворять условиям:
* либо <math>\exists n\le{min(i_1,i_2)}:\forall j<n:x_j=y_j; x_n<y_n</math>
+
  * либо <tex>~i_2>i_1</tex> и <tex>\forall j\le{i_1}:x_j=y_j</tex>
 +
  * либо <tex>\exists n\le{\min(i_1,i_2)}:\forall j<n:x_j=y_j; x_n<y_n</tex>
 
== Примеры ==
 
== Примеры ==
 
# Последовательность чисел в любой системе счисления, записанных в фиксированной разрядной сетке (000, 001, 002, 003, 004, 005, …, 999).
 
# Последовательность чисел в любой системе счисления, записанных в фиксированной разрядной сетке (000, 001, 002, 003, 004, 005, …, 999).

Версия 15:29, 24 декабря 2010

Определение

Пусть дано линейно упорядоченное множество [math]~A=\{a_1\lt a_2\lt a_3\lt ...\lt a_k\}[/math] - алфавит, [math]A^*[/math] назовем множество подпоследовательностей конечной длины из алфавита [math] A [/math], [math]A^*=\bigcup^{\infty}_{i=0} A^i[/math], тогда лексикографическим порядком на множестве [math]~A^*[/math] назовем такой порядок, при котором любые два элемента из множества [math]A^*[/math] удовлетворяют условиям:

  • пусть [math]~x\lt y; x,y \in A^*; x=\{x_1,x_2,...,x_{i_1}\}; y=\{y_1,y_2,...,y_{i_2}\}; x_j,y_j \in A[/math]) этого множества будут удовлетворять условиям:
  * либо [math]~i_2\gt i_1[/math] и [math]\forall j\le{i_1}:x_j=y_j[/math]
  * либо [math]\exists n\le{\min(i_1,i_2)}:\forall j\lt n:x_j=y_j; x_n\lt y_n[/math]

Примеры

  1. Последовательность чисел в любой системе счисления, записанных в фиксированной разрядной сетке (000, 001, 002, 003, 004, 005, …, 999).
  2. Порядок слов в словаре. Предполагается, что буквы можно сравнивать, сравнивая их номера в алфавите. Тогда лексикографический порядок — это, например, ААА, ААБ, ААВ, ААГ, …, ЯЯЯ.

Ссылки