Лексикографический порядок — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 1: Строка 1:
 +
{| class="wikitable" align="center" style="color: red; background-color: black; font-size: 56px; width: 800px;"
 +
|+
 +
|-align="center"
 +
|'''НЕТ ВОЙНЕ'''
 +
|-style="font-size: 16px;"
 +
|
 +
24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян.
 +
 +
Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием.
 +
 +
Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей.
 +
 +
Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить.
 +
 +
''Антивоенный комитет России''
 +
|-style="font-size: 16px;"
 +
|Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению.
 +
|-style="font-size: 16px;"
 +
|[https://meduza.io/ meduza.io], [https://www.youtube.com/c/popularpolitics/videos Популярная политика], [https://novayagazeta.ru/ Новая газета], [https://zona.media/ zona.media], [https://www.youtube.com/c/MackNack/videos Майкл Наки].
 +
|}
 +
 
{{Определение
 
{{Определение
 
|definition=Пусть даны две последовательности <tex> ~A = a_1 a_2 \dots a_n </tex>  и <tex> ~B = b_1 b_2 \dots b_m </tex>  
 
|definition=Пусть даны две последовательности <tex> ~A = a_1 a_2 \dots a_n </tex>  и <tex> ~B = b_1 b_2 \dots b_m </tex>  

Версия 09:35, 1 сентября 2022

НЕТ ВОЙНЕ

24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян.

Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием.

Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей.

Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить.

Антивоенный комитет России

Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению.
meduza.io, Популярная политика, Новая газета, zona.media, Майкл Наки.


Определение:
Пусть даны две последовательности [math] ~A = a_1 a_2 \dots a_n [/math] и [math] ~B = b_1 b_2 \dots b_m [/math]

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

  • [math] n \lt m [/math] и при этом [math] a_i = b_i [/math] для всех [math]i \in [1 .. n] [/math],
  • [math] \exists k\leqslant \min(n, m): a_k \lt b_k [/math] и при этом [math] \forall j : j \lt k ~a_j = b_j [/math].


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

function compare(A, B : list <T>): 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], то первая перестановка лексикографически меньше)
Compareperm.png
  • Сочетания (так как [math]4 \lt 6[/math], то первое сочетание лексикографически меньше)
Comparechoose.png
Compare part.png
  • Последовательность чисел в любой системе счисления, записанных в фиксированной разрядной сетке ([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].

См. также

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