Редактирование: СППМ/ЧУМ, 03 лекция (от 30 марта)
Материал из eSyr's wiki.
Внимание: Вы не представились системе. Ваш IP-адрес будет записан в историю изменений этой страницы.
Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия | Ваш текст | ||
Строка 14: | Строка 14: | ||
В общем случае вычисл. лин. порядка — NP-полная задача. | В общем случае вычисл. лин. порядка — NP-полная задача. | ||
- | Известно вот что: на множ. задано два порядка | + | Известно вот что: на множ. задано два порядка <P, ≤_1> = P_1, <P, ≤_2> = P_2, но один есть рподолдение другого (≤_1 ⊂ ≤_2). Тогда e(P_1) ≥ e(P_2) |
- | Рассм. грануированное множество: | + | Рассм. грануированное множество: <граф> |
(l_1)!...(l_k)! ≤ e(P), равенство будет, когда квазицепь | (l_1)!...(l_k)! ≤ e(P), равенство будет, когда квазицепь | ||
Строка 29: | Строка 29: | ||
# построить решётку всех порядков (решётку порядковых идеалов), и посчитать число всех цепей. Решётка порядковых идеалов связано много с чем. | # построить решётку всех порядков (решётку порядковых идеалов), и посчитать число всех цепей. Решётка порядковых идеалов связано много с чем. | ||
# оказывается, это число равно n!vol('''P'''(P)), где vol — объём многогранника '''P'''(P), который строится следующим образом: | # оказывается, это число равно n!vol('''P'''(P)), где vol — объём многогранника '''P'''(P), который строится следующим образом: | ||
- | #: Рассмотрим ЧУМ | + | #: Рассмотрим ЧУМ <P, ≤>, пусть оно имеет n элементов v_1...v_n. Рассмотрим n- мерное евкл. простарнство, координатами которого будут x_1...x_n. Рассмотрим единичный куб. СЕйчас мы строим '''P'''(P), он ограничен ебинич. кубом, понятно, что объём многогр. огр. 1. Строится он вот так: множество всех x_1...x_n ∈ R^n, и если v_i ∈ v_j ⇒ x_i ≤ x_j, то мы проводим такую гиперплоскость. Рассмотрим для |
x_1 x_3 | x_1 x_3 | ||
\ / | \ / | ||
Строка 50: | Строка 50: | ||
Постр. булевую алг. из мин. эл-тов: | Постр. булевую алг. из мин. эл-тов: | ||
- | + | <a,b,c> | |
/ | \ | / | \ | ||
- | + | <a,b> <a,c> <b,c> | |
| X X | | | X X | | ||
- | + | <a> <b> <c> | |
\ | / | \ | / | ||
∅ | ∅ | ||
Строка 81: | Строка 81: | ||
e(P) = n! vol('''P''') — можно считать методом Монте-Карло (раскидать точку по единичному кубу, посчитать те, которые входят в многогранник). Проблема в том, что vol('''P''') — величина малая и требует большое количество попыток. | e(P) = n! vol('''P''') — можно считать методом Монте-Карло (раскидать точку по единичному кубу, посчитать те, которые входят в многогранник). Проблема в том, что vol('''P''') — величина малая и требует большое количество попыток. | ||
- | + | <P, ≤> | |
'''P'''(P) | '''P'''(P) |