Что такое лексикографический порядок
Перейти к содержимому

Что такое лексикографический порядок

  • автор:

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

Лексикографический порядок — отношение линейного порядка на множестве кортежей \Sigma^*; \Sigma— упорядоченный алфавит. Своё название лексикографический порядок получил по аналогии с сортировкой по алфавиту в словаре.

a<b

Кортеж a предшествует кортежу b (), если для некоторого неотрицательного целого числа s первые s членов кортежей a и b совпадают, а (s+1)-й член кортежа a меньше соответствующего члена последовательности b. Если один кортеж является префиксом другого, то более короткий идёт раньше.

Примеры

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

Wikimedia Foundation . 2010 .

  • Голод в СССР 1946—1947
  • Мокуа-Вел

Полезное

Смотреть что такое «Лексикографический порядок» в других словарях:

  • ЛЕКСИКОГРАФИЧЕСКИЙ ПОРЯДОК — порядок на прямом произведении частично упорядоченных множеств Х a, где множество индексов L вполне упорядочена, определяемый следующим образом: если тогда и только тогда, когда либо для, всех либо существует такое что для всех Множество X,… … Математическая энциклопедия
  • Порядок на мономах — Эту статью следует викифицировать. Пожалуйста, оформите её согласно правилам оформления статей. Линейный порядок на пространстве одночленов … Википедия
  • Многокритериальная оптимизация — или программирование (англ. Multi objective optimization),[1][2] это процесс одновременной оптимизации двух или более конфликтующих целевых функций в заданной области определения. Задача многокритериальной оптимизации встречаются во… … Википедия
  • Правильная скобочная последовательность — (ПСП) частный случай скобочной последовательности. Правильные скобочные последовательности образуют язык Дика и формально определяются следующим образом: (пустая строка) ПСП ПСП, взятая в скобки одного типа ПСП ПСП, к которой… … Википедия
  • Правильная скобочная структура — Правильная скобочная последовательность(ПСП) частный случай скобочной последовательности. Формально определяется следующим образом: (пустая строка) ПСП ПСП, взятая в скобки одного типа ПСП ПСП, к которой приписана слева или справа ПСП тоже ПСП … Википедия
  • Правильные скобочные последовательности — Правильная скобочная последовательность(ПСП) частный случай скобочной последовательности. Формально определяется следующим образом: (пустая строка) ПСП ПСП, взятая в скобки одного типа ПСП ПСП, к которой приписана слева или справа ПСП тоже ПСП … Википедия
  • УПОРЯДОЧЕННАЯ ПОЛУГРУППА — полугруппа, наделенная структурой (частичного, вообще говоря) порядка стабильного относительно полугрупповой операции, т. е. для любых элементов а, b, с из следует и Если отношение на У. н. Sесть линейный порядок, то S наз. линейно упорядоченной… … Математическая энциклопедия
  • ряд — ▲ последовательность ↑ дискретный ряд дискретная последовательность. хвост (# обязанностей). вереница (# дней). череда. чреда. гряда (# лет). цепь (# событий). цепочка. каскад. эстафета (# дней). очередность (# действий). очередь (# дел. чья #?… … Идеографический словарь русского языка
  • Строковый тип — В программировании, строковый тип (англ. string «нить, вереница») тип данных, значениями которого является произвольная последовательность (строка) символов алфавита. Каждая переменная такого типа (строковая переменная) может быть… … Википедия
  • ISO 8601 — ISO 8601 международный стандарт, выданный организацией ISO (International Organization for Standardization), который описывает формат даты и времени и даёт рекомендации для его использования в международном контексте. Название нормы … … Википедия
  • Обратная связь: Техподдержка, Реклама на сайте
  • �� Путешествия

Экспорт словарей на сайты, сделанные на PHP,

WordPress, MODx.

  • Пометить текст и поделитьсяИскать в этом же словареИскать синонимы
  • Искать во всех словарях
  • Искать в переводах
  • Искать в ИнтернетеИскать в этой же категории

Поделиться ссылкой на выделенное

Прямая ссылка:

Нажмите правой клавишей мыши и выберите «Копировать ссылку»

алгебра от Галины Валентиновны / Лексикографический порядок

Лексикографический порядок В случае полиномов возникает потребность записи слагаемых многочлена в каком-то порядке. Обычно при этом используют так называемый лексикографический (то есть как в словаре) порядок. При лексикографическом упорядочении вначале сравниваются показатели при x 1 , затем, если они равны, то сравнивают показатели при x 2 и т.д. Итак, рассматриваются мономы вида ax 1 k 1 x 2 k 2 . x n k n . Мономы можно умножать друг на друга, например, моном u 2 x 1 x 2 x 4 3 и моном v 3 x 2 3 x 3 после перемножения дадут uv 6 x 1 x 2 4 x 3 x 4 3 . Если моном u лексикографически старше монома v , то будем писать это так u v или v u . Согласно определению это означает, что имеется хотя бы одна переменная, которая входит в u и v с разными показателями; и первая из переменных (считая слева направо), которая входит в u и v с разными показателями, входит в u с большим показателем, чем в v . Следующие свойства позволяют использовать лексикографическое упорядочение для доказательства теорем по индукции. Теорема (свойства лексикографического порядка). Отношение лексикографического упорядочения обладает следующими свойствами: 1) любые два монома с коэффициентом 1 сравнимы, то есть либо u v либо v u либо v u . 2) если u v и v w , то u w (транзитивность; рефлексивности и симметричности нет); 3) если u v , то uw vw для любого монома w («неравенство можно умножать справа или слева на любой моном»); Точно так же wu wv . 4) если u 1 v 1 и u 2 v 2 , то u 1 u 2 v 1 v 2 («неравенство одинакового смысла можно перемножать»). Доказательство . 1

1) Если мономы не одинаковы, то найдется переменная, по которой показатели этих мономов различаются, рассмотрим первую, считая слева направо, такую переменную. Если показатель по этой переменной больше у монома u , то u v , если наоборот, то v u . 2) Пусть u v и v w . Если u , v имеют разные показатели по x 1 , то как легко видеть u w . Пусть x i первая переменная, по которой показатели мономов u , v различаются. Пусть показатели мономов u , v , w есть соответственно k i , l i , m i . Очевидно, что возможны три случая a. Первая переменная, показатели по которой отличаются у мономов v , w имеет номер j , меньший i . Тогда пер- вой переменной с различными показателями у мономов v , w будет x j , для которой k j l j m j и поэтому u w . b. Первая переменная, показатели по которой отличаются у мономов v , w имеет номер j , равный i . Тогда первой переменной с различными показателями у мономов v , w будет x i , для которой k i l i m i и поэтому u w . c. Первая переменная, показатели по которой отличаются у мономов v , w имеет номер j , больший i . Тогда пер- вой переменной с различными показателями у моно-

мов v , w будет x i , для которой k i l i m i и поэтому
u w .

3) При умножении на w к показателям, с которыми каждая переменная входит в u и v , добавляется одно и то же число, и знак неравенства (или равенства) между этими показателями сохраняется. Поэтому uw vw . 4) Пользуясь предыдущим свойством, получим u 1 u 2 v 1 u 2 v 1 v 2 . Далее по транзитивности u 1 u 2 v 1 v 2 .

Пример . Следующий полином расположен по лексикографическому убыванию членов x 1 2 x 2 x 1 x 2 2 x 3 2 x 1 x 3 2 x 2 x 3 2 x 2 x 3 2 3 . Заметим, что моном x 1 x 2 2 x 3 лексикографически младше чем x 1 2 x 2 , хотя его степень больше. Среди ненулевых мономов любого ненулевого полинома f K x 1 . x n имеется единственный, который лексикографически старше всех остальных. Он называется старшим мономом полинома f . Теорема (о старшем мономе произведения). Старший моном произведения ненулевых полиномов равен произведению их старших мономов. Доказательство . Запишем полиномы f и g в следующем виде. f старший моном u младшие мономы( u i ) g старший моном w младшие мономы( w j ) Тогда u u i , w w j . Поэтому в произведении fg входят мономы ви- да uw j , u i w j , u i w , uw . Ясно, что uw uw j , uw u i w , uw u i w j (проверьте самостоятельно). По- этому uw есть старший моном. Симметрические полиномы Определение . Полином f K x 1 . x n называется симметрическим, если он не изменяется ни при каких перестановках переменных. Поскольку любая перестановка есть произведение транспозиций, и даже более того, порождается транспозициями вида 12 , 13 . 1 n , то достаточно проверять неизменность полинома при перестановке двух индексов. Очевидно, что любая однородная компонента симметрического полинома является симметрическим полиномом. Примеры . 2

1. Элементарные симметрические полиномы являются симметрическими полиномами. 2. Степенные суммы S n x 1 n . x k n , n 1,2. являются симметрическими полиномами. 3. Определитель Вандермонда V x 1 . x n x i x j i j не является симметрическим полиномом. Он меняет знак при нечетной подстановке. Но его квадрат является симметрическим полиномом. 4. При любых перестановках переменных x 1 , x 2 , x 3 , x 4 полиномы h 1 x 1 x 2 x 3 x 4 , h 2 x 1 x 3 x 2 x 4 , h 3 x 1 x 4 x 2 x 3 переходят друг в друга. Поэтому h 1 h 2 h 3 является симметрическим полиномом. Очевидно, что сумма и произведение симметрических полиномов а также произведение симметрического полинома на число являются симметрическими полиномами. Иными словами, симметрические полиномы образуют подалгебру в алгебре всех полиномов. Следовательно, если F K x 1 . x m – произвольный полином от m переменных и f 1 . f m K x 1 . x n – симметрические по- линомы, то F f 1 . f m – также симметрический полином от x 1 . x n .Оказывается, что если взять в качестве f 1 . f m K x 1 . x n элементарные симметрические полиномы, то любой симметрический полином можно выразить в таком виде. Теорема (основнаятеорема о симметрических полиномах). Всякий симметрический полином единственным образом представим в виде полинома от элементарных симметрических полиномов. Лемма (о старшем мономе симметрического полинома).

Пусть u ax 1 k 1 x 2 k 2 . x n k n старший моном симметрического поли- нома. Тогда k n k n 1 . k 1 . Доказательство . Предположим, что k i k i 1 для некоторого числа i . Наряду с мономом u полином должен содержать моном

u ‘ ax k 1 . x k i 1 x k i . x k n , получающийся перестановкой x i и x i 1 . Легко ви-
1 i i 1 n

деть, что u ‘ u . Это противоречит тому, что u старший моном. Лемма (о существовании монома от элементарный симметрических полиномов с заданным старшим мономом)

Пусть имеется моном u ax k 1 x k 2 . x k n , для которого k n k . k . То-
1 2 n n 1 1

гда существуют такие неотрицательные целые числа l 1 . l n , что старший моном полинома 1 l 1 . n l n совпадает с u . Числа l 1 . l n при этом однозначно. Доказательство . Старший моном полинома k равен x 1 x k . Для полинома 1 l 1 . n l n старший моном равен x 1 l 1 x 1 x 1 l 2 . x 1 . x n l n x 1 l 1 . l n x 2 l 2 . l n . x n l n . Приравнивая его одночлену u , получаем систему линейных уравнений l 1 l 2 . l n k 1 l 2 . l n k 1

которая очевидно имеет единственное решение l n k n , l i k i k i 1 , i 1, 2. n 1 . Из того, что k n k n 1 . k 1 , следует, что числа l 1 . l n неотрицательны. 3

Доказательство теоремы . Пусть f K x 1 . x n – симметрический многочлен. Нужно найти такой многочлен F K x 1 . x m , что

F 1 . m f .
Если f 0 , то можно взять F 0 . В противном случае пусть
u 1 ax 1 k 1 x 2 k 2 . x n k n старший член многочлена f . По лемме о старшем мо-
номе симметрического полинома выполняются неравенства
k k . k . По следующей лемме существует моном F l 1 . l n ,
n n 1 1 1 1 n

старший моном которого равен u 1 . Рассмотрим полином f 1 f F 1 . Если он равен 0, то все доказано. В противном случае старший моном для f 1 меньше старшего монома полинома f . Повторяя проделан- ное рассуждение, получим многочлен со старшим мономом u 2 . Старшие мономы удовлетворяют неравенствам u u 1 u 2 . . По- скольку мономов меньших данного конечное число, придем к случаю, когда соответствующая разность станет равна нулевому полиному. То есть теорема доказана. Единственность не доказываем.

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

Тогда последовательность [math] ~A [/math] лексикографически меньше (англ. lexicographically less) последовательности [math] ~B [/math] , если выполняется одно из двух условий:

Приведем псевдокод сравнения последовательностей из элементов множества Т:

function compare(A, B : list ): Ord // Возвращает "LT", если A < B, "GT", если A >B, или "EQ", если последовательности равны for i = 1 to min(len(A), len(B)) if A[i] < B[i] // i-й элемент А меньше i-го элемента B, но префиксы длины i - 1 равны return LT if A[i] > B[i] // i-й элемент А больше i-го элемента B, но префиксы длины i - 1 равны return GT if len(A) < len(B) // А — префикс В, но не равна ей return LT if len(A) > len(B) // В — префикс А, но не равна ей return GT return EQ // Длины последовательностей и все элементы равны 
Определение:
Последовательности записаны в лексикографическом порядке (англ. lexicographical order), если для любых [math] i\lt j [/math] выполняется неравенство [math] S_i\lt S_j [/math] , где [math] S_i [/math] и [math] S_j [/math] последовательности с номерами [math] i [/math] и [math] j [/math] .

Например, слово «сон» лексикографически меньше слова «сонный», так как оно является его префиксом. Слово «низ» лексикографически меньше слова «нос», поскольку первые символы совпадают, а второй символ первого слова меньше, чем второй символ второго.

Примеры

  • Перестановки ( светло-фиолетовым выделен общий префикс, темно-фиолетовым первый отличный элемент, так как [math]4 \lt 6[/math] , то первая перестановка лексикографически меньше)
  • Сочетания (так как [math]4 \lt 6[/math] , то первое сочетание лексикографически меньше)
  • Разбиение на слагаемые (так как [math]4 \lt 9[/math] , то первое разбиение на слагаемые лексикографически меньше)
  • Последовательность чисел в любой системе счисления, записанных в фиксированной разрядной сетке ( [math]000[/math] , [math]001[/math] , [math]002[/math] , [math]003[/math] , [math]004[/math] , [math]005[/math] , [math]\dots[/math] , [math]999[/math] ).
  • Порядок слов в словаре. Предполагается, что буквы можно сравнивать, сравнивая их номера в алфавите. Тогда лексикографический порядок — это, например, [math]AAA[/math] , [math]AAB[/math] , [math]AAC[/math] , [math]AAD[/math] , [math]\dots[/math] , [math]ZZZ[/math] .
  • Эти слова тоже записаны в лексикографическом порядке: [math]airport[/math] , [math]duck[/math] , [math]horse[/math] , [math]house[/math] , [math]sleep[/math] .

См. также

  • Генерация комбинаторных объектов в лексикографическом порядке
  • Получение предыдущего объекта
  • Получение следующего объекта

Источники информации

  • Wikipedia — Lexicographical order
  • Википедия — Лексикографический порядок
  • Дискретная математика и алгоритмы
  • Комбинаторика

Что такое лексикографическое сравнение и что оно собой представляет?

Это сравнение «как в словаре» или «как в телефонном справочнике» — по алфавиту. Если первые буквы совпали, сравниваются вторые, если вторые совпали — третьи, и так далее.

Отслеживать
ответ дан 7 фев 2016 в 12:19
22.3k 2 2 золотых знака 33 33 серебряных знака 53 53 бронзовых знака

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

Слово a предшествует слову b ( a

Если первые m символов слов совпадают, после чего слово a кончается, то оно также считается предшествующим b (т.е. отсутствующий символ меньше любого символа).

Таким образом, относительно лексикографического порядка для строк верны следующие равенства и неравенства:

"abc" == "abc" //true "123" == "123" //true "123" < "124" //true "0999999" < "123" //true "123" < "3" //true "12" < "123" //true "123" < "1234" //true 

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *