Викия

Математика

Лексикографический порядок

1457статей на
этой вики
Добавить новую страницу
Обсуждение0 Share

Обнаружено использование расширения AdBlock.


Викия — это свободный ресурс, который существует и развивается за счёт рекламы. Для блокирующих рекламу пользователей мы предоставляем модифицированную версию сайта.

Викия не будет доступна для последующих модификаций. Если вы желаете продолжать работать со страницей, то, пожалуйста, отключите расширение для блокировки рекламы.

Лексикографический порядок последовательностей это естественный способ упорядочивания последовательностей на основе сравнения индивидуальных символов.

Определение Править

Пусть дано конечное семейство множеств \{A_n\}_{n=1}^N, и на каждом множестве A_n задано отношение частичного порядка \preceq_n. Тогда на их декартовом произведении A_1 \times \cdots \times A_N можно определить частичный порядок \preceq^N следующим образом:

\Bigl( (x_1,\ldots, x_N) \preceq^N (y_1,\ldots,y_N) \Bigr) \Leftrightarrow \Bigl( \exists m \in \{1,\ldots,N\}\; \forall n < m\quad \bigl(x_n = y_n\bigr) \wedge \bigl( x_m \preceq_m y_m\bigr)\Bigr).

Замечание Править

Неформально говоря, лексикографический порядок задаётся следующей процедурой. Сравним первые символы в обоих словах. Если они равны, переходим ко вторым и так далее.

Примеры Править

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


Эта статья содержит материал из статьи Лексикографический порядок русской Википедии.

Викия-сеть

Случайная вики