72
правки
Изменения
Нет описания правки
Пусть дано линейно упорядоченное множество <tex>~E=\{e_1<e_2<e_3<...<e_k\}</tex> - алфавит. Словом назовем упорядоченное множество <tex> ~S </tex> элементов алфавита <tex> ~A </tex>. Тогда если на алфавите <tex> A </tex> задан порядок, то порядок задан и на слове <tex> ~S </tex>. Тогда говорят, что множество слов <tex> ~A </tex> задано в лекcикографическом порядке, если для <math>\mathcal {8} i \in A </math> <math>\mathcal {8} j \in A </math> таких, что <tex> i < j </tex> выполнено, что слово <tex> ~A_i </tex> меньше, чем слово <tex> ~A_j </tex>.
== Сравнение слов ==
Что же значит, что слово <tex> ~A </tex> меньше слова <tex> ~B </tex>, и как вообще можно сравнивать слова?
Говорят, что слово <tex> ~A </tex> меньше слова <tex> ~B </tex>, если:
1. Длина (количество элементов) слова <tex> ~A </tex> меньше длины слова <tex> ~B </tex>ю
2. Длины слов равны, но <math>\mathcal {9} i </math> <tex> \ge 0 </tex> такое, что для всех <tex> j < i </tex> выполнено неравенство <tex> A_j = B_j </tex>, а <tex> A_i < B_i </tex>. Элементы слова мы можем сравнивать, так как это элементы алфавита, а на алфавите задан строгий порядок.
== Примеры ==
# Последовательность чисел в любой системе счисления, записанных в фиксированной разрядной сетке (000, 001, 002, 003, 004, 005, …, 999).
# Порядок слов в словаре. Предполагается, что буквы можно сравнивать, сравнивая их номера в алфавите. Тогда лексикографический порядок — это, например, ААА, ААБ, ААВ, ААГ, …, ЯЯЯ.
== Ссылки ==
