4625
правок
Лексикографический порядок: различия между версиями
Перейти к навигации
Перейти к поиску
Лексикографический порядок (посмотреть исходный код)
Версия от 13:02, 29 апреля 2011
, 29 апреля 2011нет описания правки
KEV (обсуждение | вклад) Нет описания правки |
KEV (обсуждение | вклад) Нет описания правки |
||
| Строка 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. | |||