19.8: Шавлія

Last updated
Save as PDF

Page ID: 64353

\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)

Sage має підтримку як частково впорядкованих наборів («posets»), так і решіток, і робить відмінну роботу з надання візуальних зображень обох.

Створення частково впорядкованих наборів

Приклад\(19.6\) у тексті є хорошим прикладом для реплікації як демонстрації команд Sage. Спочатку визначаємо елементи множини\(X\text{.}\)

Один підхід до створення зв'язку полягає в тому, щоб вказати кожен екземпляр, де один елемент можна порівняти з іншим. Таким чином, ми будуємо список пар, де кожна пара містить зіставні елементи, з меншим першим. Це сукупність відносин.

Ми будуємо poset, надаючи конструктору Poset список, що містить елементи та відносини. Потім ми можемо легко отримати «сюжет» посади. Зверніть увагу, що сюжет просто показує «відносини покриття» - мінімальний набір порівнянь, який припущення про транзитивність розшириться на множину всіх відносин.

Інший підхід до створення Poset полягає в тому, щоб дозволити конструктору poset працювати над усіма парами елементів, і все, що ми робимо, це дати конструктору спосіб перевірити, чи можна порівняти два елементи. Наша функція порівняння повинна очікувати двох елементів, а потім повернути True або False. Функція «лямбда» - це один із способів швидкого побудови такої функції. Це може бути для вас новою ідеєю, але освоєння лямбда-функцій може бути великою зручністю. Зверніть увагу, що «лямбда» - це слово, зарезервоване саме для цієї мети (так, наприклад, лямбда є поганим вибором для імені власного значення матриці). Є й інші способи створення функцій у Sage, але лямбда-функція найшвидша, коли функція проста.

Шавлія також має колекцію запасних посетів. Деякі є одноразовими конструкціями, а інші є членами параметризованих сімей. Використовуйте доповнення табуляції на Posets. щоб побачити повний список. Ось кілька прикладів.

Однократна конструкція. Можливо, те, що ви очікуєте, хоча можуть бути й інші, не менш правдоподібні, альтернативи.

Параметризоване сімейство. Це класичний приклад, де елементи є підмножинами множини з\(n\) елементами, а відношення - «підмножина».

І випадкові поети. Вони можуть бути корисними для тестування та експериментів, але навряд чи виявлять особливі випадки, які можуть бути важливими. Ви можете виконати наступну команду багато разів і змінити другий аргумент, який є грубою верхньою межею на ймовірність того, що будь-які два елементи можна порівняти. Пам'ятайте, що сюжет показує лише прикриття відносин. Чим більше елементів можна порівняти, тим більше «вертикально витягнутим» буде сюжет.

Властивості допису

Як тільки у вас є поета, що ви можете зробити з ним? Повернемося до нашого першого прикладу, D. Ми, звичайно, можемо визначити, чи один елемент менше іншого, що є фундаментальною структурою посади.

Зверніть увагу, що 6 і 8 не можна порівняти в цій посади (це частковий порядок). Методи .is_gequal () і.is_greater_than () працюють аналогічно, але повертають True, якщо перший елемент більший (або дорівнює).

Ми можемо знайти найбільші та найменші елементи посади. Це випадкова публікація, побудована з ймовірністю 10%, але скопійована тут, щоб бути повторюваною.

Елементи посади можна розділити на набори рівнів. На ділянках пошет елементи на одному рівні наносяться вертикально на однаковій висоті. Кожен набір рівнів виходить шляхом видалення всіх попередніх наборів рівнів, а потім взяття мінімальних елементів результату.

Якщо ми зробимо два елементи в R порівнянними, коли вони раніше не були, це розширення R. Розглянемо всі можливі розширення однієї посади - ми можемо зробити poset з усіх цих, де включення set є співвідношенням. Лінійне розширення є максимальним елементом у цій позі. Неофіційно ми додаємо якомога більше нових відносин, узгоджуючись з оригінальною позицією і так, щоб результат був загальним порядком. Іншими словами, існує впорядкування елементів, яке узгоджується з порядком у позеті. Ми можемо побудувати таку річ, але вихід просто список елементів в лінійному порядку. Комп'ютерний вчений був би схильний називати це «топологічним сортом».

Ми можемо побудувати підмножини, даючи набір елементів, щоб викликати нову позицію. Тут ми беремо приблизно «нижню половину» випадкової позиції P шляхом індукції підмножини на об'єднання деяких наборів рівнів.

Подвійне повідомлення зберігає той самий набір елементів, але змінює будь-які порівняння.

Беручи подвійну позицію подільності з Прикладу,\(19.6\) було б схоже на зміну відношення на «є кратним».

решітки

Кожна решітка є poset, тому всі команди вище будуть виконувати однаково добре для решітки. Але як же створити решітку? Простий — спочатку створіть poset, а потім подайте його в конструктор LatticePoset (). Але зрозумійте, що тільки тому, що ви даєте цьому конструктору poset, це не означає, що решітка завжди повернеться. Тільки якщо poset вже є решіткою, він буде оновлений з poset до решітки для цілей мудреця, і ви отримаєте ValueError, якщо оновлення неможливо. Нарешті, зверніть увагу, що деякі з посетів конструкцій Sage вже визнані гратами, наприклад, прототипова BooleanLattice.

Цілочисельний склад\(n\) - це список натуральних чисел, які сумуються до\(n\text{.}\) A композиції, яка\(C_1\) охоплює композицію,\(C_2\) якщо її\(C_2\) можна сформувати\(C_1\) шляхом додавання послідовних частин. Наприклад,\(C_1 = [2, 1, 2] \succeq [3, 2] = C_2\text{.}\) При такому співвідношенні множина всіх цілих композицій фіксованого цілого числа\(n\) є позицією, яка також є решіткою.

Зустріч або з'єднання - це фундаментальна операція в решітці.

Після того, як добірка оновлюється до стану решітки, стають доступними додаткові команди або змінюється характер їх результатів.

Прикладом першого є метод.is_distributive ().

Прикладом останнього є метод.top (). Те, що ваш текст називає найбільшим елементом і найменшим елементом решітки, мудрець називає верх і низ. Для poset .top () і.bottom () можуть повертати елемент, а може і ні (повертаючи None), але для решітки гарантовано поверне рівно один елемент.

Зверніть увагу, що повернуті значення - це всі елементи решітки, в цьому випадку впорядковані списки цілих чисел підсумовуються до\(5\text{.}\)

Доповнення тепер мають сенс в решітці. Результатом методу.complements () є словник, який використовує елементи решітки як ключі. Ми говоримо, що словник «індексується» елементами решітки. В результаті вийде список доповнень елемента. Ми називаємо це «значенням» пари ключ-значення. (Ви можете знати словники як «асоціативні масиви», але вони насправді просто фантазії функції.)

Решітка цілочисельних композицій являє собою доповнену решітку, як ми бачимо по результату, що кожен елемент має єдине (унікальне) доповнення, про що свідчать списки довжини\(1\) в значеннях словника. Або ми можемо просто запитати Sage через.is_upplemented (). Словники не мають властивого порядку, тому ви можете отримувати різні результати кожного разу, коли перевіряєте словник.

Є багато інших команд, які застосовуються до позетів і решіток, тому створіть декілька і використовуйте доповнення табуляції ліберально для вивчення. Існує більше, щоб виявити, ніж ми можемо охопити лише в одній главі, але тепер у вас є основні інструменти для вигідно вивчення повідомлень та решіток у Sage.