PA_full (1127144), страница 24
Текст из файла (страница 24)
множествами337 / 432Прямое произведение: пример 1(c, 1)cba(b, 1)⇥10=(a1)(c, 0)(b, 0)(a, 0)Рис. 5. Прямое произведение цепей 3 и 2Прикладная алгебраНекоторые вопросы теории частично упорядоченных множествОперации над ч.у. множествамиПрямое произведение: пример 2Рис. 6. Зигзаги (или заборы) Z3 и Z4Рис.
7. Прямое произведение Z3 ⇥ Z4338 / 432Прикладная алгебраНекоторые вопросы теории частично упорядоченных множествОперации над ч.у. множествамиТеорема (Оре )Каждый частичный порядок изоморфен некоторомуподмножеству декартова произведения цепей.339 / 432Прикладная алгебраНекоторые вопросы теории частично упорядоченных множествОперации над ч.у. множествамиТеорема (Оре )Каждый частичный порядок изоморфен некоторомуподмножеству декартова произведения цепей.ОпределениеМультипликативной размерностью ч.у.
множества Pназывается наименьшее число k линейных порядков Li таких,существует вложение P ,! L1 ⇥ . . . ⇥ Lk .339 / 432Прикладная алгебраНекоторые вопросы теории частично упорядоченных множествЛинеаризацияРаздел I1Конечные поля или поля ГалуаПоля вычетов по модулю простого числаВычисление элементов в конечных поляхЛинейная алгебра над конечным полемКорни многочленов над конечным полемСуществование и единственность поля Галуа из pnэлементовЦиклические подпространстваЗадачиЧто надо знать2Коды, исправляющие ошибкиПонятие помехоустойчивого кодирования.
Коды ХэммингаГрупповые (линейные) коды340 / 432Прикладная алгебраНекоторые вопросы теории частично упорядоченных множествЛинеаризацияРаздел IIЦиклические кодыКоды БЧХЗадачиЧто надо знать3Теория перечисления ПойаДействие группы на множествеПрименение леммы Бёрнсайда для решениякомбинаторных задачПрименение теоремы Пойа для решения комбинаторныхзадачЗадачиЧто надо знать4Некоторые вопросы теории частично упорядоченныхмножеств341 / 432Прикладная алгебраНекоторые вопросы теории частично упорядоченных множествЛинеаризацияРаздел IIIОсновные понятия теории ч.у. множествОперации над ч.у.
множествамиЛинеаризацияЧто надо знать5Алгебраические решёткиРешётки: определение, основные свойстваМодулярные и дистрибутивные решёткиПрименение теории решёток к задаче классификацииЧто надо знать342 / 432Прикладная алгебраНекоторые вопросы теории частично упорядоченных множествЛинеаризацияПредставление P = h P, 6 i в виде пересечения цепейТеорема (Шпильрайна, принцип продолжения порядка)12Любой частичный порядок 6 может быть продолжен долинейного на том же множестве.Каждый порядок есть пересечение всех своих линейныхпродолжений (линеаризаций).P ! L,P = L1 \ .
. . \ Le(P) ,где e(P) � множество всех линеаризаций ч.у. множества P.343 / 432Прикладная алгебраНекоторые вопросы теории частично упорядоченных множествЛинеаризацияПредставление P = h P, 6 i в виде пересечения цепейТеорема (Шпильрайна, принцип продолжения порядка)12Любой частичный порядок 6 может быть продолжен долинейного на том же множестве.Каждый порядок есть пересечение всех своих линейныхпродолжений (линеаризаций).P ! L,P = L1 \ . . . \ Le(P) ,где e(P) � множество всех линеаризаций ч.у. множества P.Доказательство (для конечного случая, |P | = n)1Если P � не цепь, то в P найдутся несравнимые элементы;произвольно определим порядок на них и продолжим его потранзитивности.
Если получившиеся ч.у. множество ещё нецепь, то выберем новую пару несравнимых элементов ипоступаем, как указано выше. Через конечное число шаговполучаем линейный порядок.343 / 432Прикладная алгебраНекоторые вопросы теории частично упорядоченных множествЛинеаризацияТопологическая сортировка12(продолжение). Т.к. возможен различный выбор парнесравнимых элементов и при каждом выборе можнополагать любой их порядок, то можно получить всевозможные линейные продолжения исходного частичногопорядка.Пересечение всех таких цепей даст исходное ч.у.
множество:если x 6 y, то аналогичное следование будет и во всехполученных линейных порядках, а при x ⌧ y всегда найдётсяпара цепей с противоположным их следованием, что впересечении цепей и даст несравнимость этих элементов.Для конечных ч.у. множеств заданных парами вида a l b, поисктакого линейного продолжения в теоретическомпрограммировании называют топологической сортировкой.Задача решается за линейное время.344 / 432Прикладная алгебраНекоторые вопросы теории частично упорядоченных множествЛинеаризация345 / 432Представление ч.у. множества пересечением цепейcdba=dccdba\baПрикладная алгебраНекоторые вопросы теории частично упорядоченных множествЛинеаризация346 / 432Некоторые ч.у.
множества......Рис. 8. Малая корона snb1b2b3b4b5a1a2a3a4a5Рис. 9. Корона S5Прикладная алгебраНекоторые вопросы теории частично упорядоченных множествЛинеаризация347 / 432�e(P)= ?� � NP-полная задача, но:✓◆n+me(P + Q) =e(P)e(Q), n = |P|, m = |Q|;n✓ ◆12ne(2 ⇥ n) =� числа Каталана;n+1 nX e(Zn ) xnn>0n!= tg x + sec x ,значения Zn при чётных n � числа секанса, а при нечётных �числа тангенса;e(Sn ) = (n + 1)!(n 1)! ;X e(sn )xxn =;n!cos2 xn>1✓◆log(e(B n ))n= log2nbn/2c3log e + o(1) .2Прикладная алгебраНекоторые вопросы теории частично упорядоченных множествЛинеаризацияВероятностное пространство на линеарезацияхПри решении задач комбинаторики, дискретной оптимизации идр.
часто рассматривают связанное с ч.у. множеством Pвероятностное пространство на множестве всех e(P) еголинеаризаций, в котором каждая линеаризация равновероятна.348 / 432Прикладная алгебраНекоторые вопросы теории частично упорядоченных множествЛинеаризацияВероятностное пространство на линеарезацияхПри решении задач комбинаторики, дискретной оптимизации идр. часто рассматривают связанное с ч.у. множеством Pвероятностное пространство на множестве всех e(P) еголинеаризаций, в котором каждая линеаризация равновероятна.В этом пространстве для элементов x, y, z, . . .
данного ч.у.множества рассматривают события E вида x 6 y,(x 6 y) N (x 6 z) и т.д.348 / 432Прикладная алгебраНекоторые вопросы теории частично упорядоченных множествЛинеаризацияВероятностное пространство на линеарезацияхПри решении задач комбинаторики, дискретной оптимизации идр. часто рассматривают связанное с ч.у. множеством Pвероятностное пространство на множестве всех e(P) еголинеаризаций, в котором каждая линеаризация равновероятна.В этом пространстве для элементов x, y, z, . . .
данного ч.у.множества рассматривают события E вида x 6 y,(x 6 y) N (x 6 z) и т.д. Вероятность Pr [E] такого события:Pr [E] =число линеаризаций, в которых имеет место E.e(P)348 / 432Прикладная алгебраНекоторые вопросы теории частично упорядоченных множествЛинеаризацияВероятностное пространство на линеарезацияхПри решении задач комбинаторики, дискретной оптимизации идр.
часто рассматривают связанное с ч.у. множеством Pвероятностное пространство на множестве всех e(P) еголинеаризаций, в котором каждая линеаризация равновероятна.В этом пространстве для элементов x, y, z, . . . данного ч.у.множества рассматривают события E вида x 6 y,(x 6 y) N (x 6 z) и т.д. Вероятность Pr [E] такого события:Pr [E] =число линеаризаций, в которых имеет место E.e(P)Теорема (XYZ-теорема)Пусть h P, 6 i � ч.у. множество и x, y, z 2 P . ТогдаPr [ x 6 y ] · Pr [ x 6 z ] 6 Pr [ (x 6 y) N (x 6 z) ] .348 / 432Прикладная алгебраНекоторые вопросы теории частично упорядоченных множествЛинеаризацияПроблема сортировки и �1/3 – 2/3 предположение�� определить линейный порядк L с помощью минимальногоколичества вопросов �верно ли, что x < y в L?�.Обобщение: L � зафиксированная, но неизвестнаялинеаризация ч.у.
множества P.Оптимальная процедура поиска L включает в себя нахождениеэлементов x и y, для которых Pr [ x < y ] ⇡ 12 .349 / 432Прикладная алгебраНекоторые вопросы теории частично упорядоченных множествЛинеаризацияПроблема сортировки и �1/3 – 2/3 предположение�� определить линейный порядк L с помощью минимальногоколичества вопросов �верно ли, что x < y в L?�.Обобщение: L � зафиксированная, но неизвестнаялинеаризация ч.у.
множества P.Оптимальная процедура поиска L включает в себя нахождениеэлементов x и y, для которых Pr [ x < y ] ⇡ 12 .С.С. Кислицын (1968) высказал �1/3 – 2/3 предположение�:“любое не являющееся цепью ч.у. множество содержит парунесравнимых элементов x и y, для которых126 Pr [ x 6 y ] 6”.33Позднее это утверждение независимо выдвинули американскиеисследователи М. Фредман и Н. Линал.349 / 432Прикладная алгебраНекоторые вопросы теории частично упорядоченных множествЛинеаризация1/3 – 2/3 предположениеПример 2 + 1 показывает,что указанные границынесужаемы (имеется и примердесятиэлементного ч.у. множествасо связанной диаграммой Хассе).350 / 432Прикладная алгебраНекоторые вопросы теории частично упорядоченных множествЛинеаризация1/3 – 2/3 предположениеПример 2 + 1 показывает,что указанные границынесужаемы (имеется и примердесятиэлементного ч.у.
множествасо связанной диаграммой Хассе).Данное предположение до сих пор успешно противостоит всемпопыткам его доказать и представляет собой одну из наиболееинтригующих проблем комбинаторной теории ч.у. множеств(С. Фелснер и У.Т. Троттер).350 / 432Прикладная алгебраНекоторые вопросы теории частично упорядоченных множествЛинеаризация1/3 – 2/3 предположениеПример 2 + 1 показывает,что указанные границынесужаемы (имеется и примердесятиэлементного ч.у.
множествасо связанной диаграммой Хассе).Данное предположение до сих пор успешно противостоит всемпопыткам его доказать и представляет собой одну из наиболееинтригующих проблем комбинаторной теории ч.у. множеств(С. Фелснер и У.Т. Троттер).На сегодняшний день наиболее сильный результат:pp555+ 50, 2764 ⇡6 Pr[x 6 y] 6⇡ 0, 7236 .1010350 / 432Прикладная алгебраНекоторые вопросы теории частично упорядоченных множествЛинеаризацияЧ.у. множества: спектрОпределение:Spec (P) =Pr [ a 6 b ] | a, b 2 P, a 6= b351 / 432Прикладная алгебраНекоторые вопросы теории частично упорядоченных множествЛинеаризацияЧ.у. множества: спектрОпределение:Spec (P) =Pr [ a 6 b ] | a, b 2 P, a 6= bЯсно, чтопоскольку Pr [ a 6 b ] = 1 Pr [ b 6 a ], спектрсимметричен относительно 12 ;для всех неодноэлементных тривиально упорядоченныхмножеств Spec = 12 ;0, 12 , 1� единственный трёхэлементный спектр;все четырёхэлементные спектры должны иметь вид{ 0, ↵, 1 ↵, 1 }, где 0 < ↵ < 12 ;351 / 432Прикладная алгебраНекоторые вопросы теории частично упорядоченных множествЛинеаризацияЧ.у.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
