Форум Статьи Контакты
Строительство — возведение зданий и сооружений, а также их капитальный и текущий ремонт, реконструкция, реставрация и реновация.

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

Дата: 11-06-2022, 18:00 » Раздел: Статьи  » 

Лексикографический порядок — отношение линейного порядка на множестве слов над некоторым упорядоченным алфавитом Σ {displaystyle Sigma } . Своё название лексикографический порядок получил по аналогии с сортировкой по алфавиту в словаре.

Определение

Слово α {displaystyle alpha } предшествует слову β {displaystyle eta } ( α {displaystyle alpha } < β {displaystyle eta } ), если

  • либо первые m {displaystyle m} символов этих слов совпадают, а m + 1 {displaystyle m+1} -й символ слова α {displaystyle alpha } меньше (относительно заданного в Σ {displaystyle Sigma } порядка) m + 1 {displaystyle m+1} -го символа слова β {displaystyle eta } (например, АБАК < АБРАКАДАБРА, так как первые две буквы у этих слов совпадают, а третья буква у первого слова меньше, чем у второго);
  • либо слово α {displaystyle alpha } является началом слова β {displaystyle eta } (например, МАТЕМАТИК < МАТЕМАТИКА; см. конкатенация).

Примеры

  • Порядок слов в словаре. Предполагается, что буквы можно сравнивать, сравнивая их номера в алфавите. Например, следующие слова идут в лексикографическом порядке: А < АА < ААА < ААБ < ААВ < АБ < Б < … < ЯЯЯ.
  • Естественный порядок на неотрицательных целых n {displaystyle n} -значных числах в любой позиционной системе счисления, записанных в разрядной сетке фиксированной длины (000, 001, 002, 003, 004, 005, …, 998, 999).

(голосов:0)

Пожожие новости
Комментарии

Ваше Имя:   

Ваш E-Mail: