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

Материал из WikiGrapp
Перейти к навигации Перейти к поиску
(Создана новая страница размером '''Лексикографический порядок''' (''Lexicographic order'') - Порядок слов в словаре, опре...)
 
Нет описания правки
 
(не показана 1 промежуточная версия этого же участника)
Строка 1: Строка 1:
'''Лексикографический порядок''' (''Lexicographic order'') -
'''Лексикографический порядок''' (''[[Lexicographic order]]'')
Порядок слов в словаре, определяемый последовательностью букв
Порядок слов в словаре, определяемый последовательностью букв алфавита. В более общем случае рассматривается множество <math>\,S</math>, строго
алфавита. В более общем случае рассматривается множество </math>S<math>, строго
упорядоченное отношением <math>\,<</math>. Пусть для <math>\,n > 0</math> имеется множество
упорядоченное отношением </math><<math>. Пусть для </math>n > 0<math> имеется множество
<math>\,T</math> <math>\,n</math>-кортежей
</math>T<math> </math>n<math>-кортежей
<math>(x_{1}, x_{2}, \ldots, x_{n})</math>
</math>(x_{1}, x_{2}, \ldots, x_{n})<math>
с элементами <math>x_{j} \in S</math>. Тогда отношение упорядочения этих кортежей
с элементами </math>x_{j} \in S<math>. Тогда отношение упорядочения этих кортежей
можно определить так, что
можно определить так, что
</math>(x_{1}, x_{2}, \ldots, x_{n}) < (y_{1}, y_{2}, \ldots, y_{n})<math>
<math>(x_{1}, x_{2}, \ldots, x_{n}) < (y_{1}, y_{2}, \ldots, y_{n})</math>
тогда и только тогда, когда </math>x_{1} < y_{1}<math>или существует некоторое
тогда и только тогда, когда <math>\,x_{1} < y_{1}</math>или существует некоторое
</math>k<math>, </math>1 \leq k \leq n<math>, для которого </math>x_{i} = y_{i}<math>при </math>1 \leq i <
<math>\,k</math>, <math>1 \leq k \leq n</math>, для которого <math>\,x_{i} = y_{i}</math> при <math>1 \leq i <
k<math>, и </math>x_{k} < y_{k}<math> Множество </math>T<math> лексикографически упорядочено,
k</math>, и <math>\,x_{k} < y_{k}</math> Множество <math>\,T</math> лексикографически упорядочено,
если кортежи расположены в соответствии с указанным отношением.
если кортежи расположены в соответствии с указанным отношением.
Рассмотренное понятие можно обобщить для строк неодинаковой длины.
Рассмотренное понятие можно обобщить для строк неодинаковой длины.
==Литература==
==Литература==
[Словарь]
* Толковый словарь по вычислительным системам. — М.: Машиностроение, 1991.

Текущая версия от 13:02, 29 апреля 2011

Лексикографический порядок (Lexicographic order) — Порядок слов в словаре, определяемый последовательностью букв алфавита. В более общем случае рассматривается множество [math]\displaystyle{ \,S }[/math], строго упорядоченное отношением [math]\displaystyle{ \,\lt }[/math]. Пусть для [math]\displaystyle{ \,n \gt 0 }[/math] имеется множество [math]\displaystyle{ \,T }[/math] [math]\displaystyle{ \,n }[/math]-кортежей [math]\displaystyle{ (x_{1}, x_{2}, \ldots, x_{n}) }[/math] с элементами [math]\displaystyle{ x_{j} \in S }[/math]. Тогда отношение упорядочения этих кортежей можно определить так, что [math]\displaystyle{ (x_{1}, x_{2}, \ldots, x_{n}) \lt (y_{1}, y_{2}, \ldots, y_{n}) }[/math] тогда и только тогда, когда [math]\displaystyle{ \,x_{1} \lt y_{1} }[/math]или существует некоторое [math]\displaystyle{ \,k }[/math], [math]\displaystyle{ 1 \leq k \leq n }[/math], для которого [math]\displaystyle{ \,x_{i} = y_{i} }[/math] при [math]\displaystyle{ 1 \leq i \lt k }[/math], и [math]\displaystyle{ \,x_{k} \lt y_{k} }[/math] Множество [math]\displaystyle{ \,T }[/math] лексикографически упорядочено, если кортежи расположены в соответствии с указанным отношением. Рассмотренное понятие можно обобщить для строк неодинаковой длины.

Литература

  • Толковый словарь по вычислительным системам. — М.: Машиностроение, 1991.