Bagian 19.8 Sage

Sage mendukung himpunan terurut parsial (“poset”) maupun latis, serta menyediakan representasi visual yang sangat baik untuk keduanya.

Subbagian 19.8.1 Membuat Himpunan Terurut Parsial

Contoh 19.1.6 dalam teks merupakan contoh yang baik untuk dibuat ulang sebagai demonstrasi perintah Sage. Pertama-tama kita mendefinisikan unsur-unsur himpunan \(X\text{.}\)

Kode Sage (cadangan statis)

X = (24).divisors()
X

Keluaran referensi (cadangan statis)

[1, 2, 3, 4, 6, 8, 12, 24]

Salah satu cara membuat relasi adalah menetapkan setiap keadaan ketika suatu unsur dapat dibandingkan dengan unsur lain. Jadi, kita membuat daftar pasangan, dengan setiap pasangan memuat unsur-unsur yang dapat dibandingkan, dan unsur yang lebih kecil ditempatkan lebih dahulu. Inilah himpunan relasinya.

Kode Sage (cadangan statis)

R = [(a,b) for a in X for b in X if a.divides(b)]; R

Keluaran referensi (cadangan statis)

[(1, 1), (1, 2), (1, 3), (1, 4), (1, 6), (1, 8), (1, 12), (1, 24),
 (2, 2), (2, 4), (2, 6), (2, 8), (2, 12), (2, 24), (3, 3), (3, 6),
 (3, 12), (3, 24), (4, 4), (4, 8), (4, 12), (4, 24), (6, 6),
 (6, 12), (6, 24), (8, 8), (8, 24), (12, 12), (12, 24), (24, 24)]

Kita menyusun poset dengan memberikan daftar yang memuat unsur dan relasi kepada konstruktor Poset. Setelah itu, kita dapat dengan mudah memperoleh “plot” poset tersebut. Perhatikan bahwa plot hanya menampilkan “relasi penutup” —yaitu himpunan minimal perbandingan yang, dengan asumsi transitivitas, dapat diperluas menjadi himpunan semua relasi.

Kode Sage (cadangan statis)

D = Poset([X, R])
D.plot()

Cara lain membuat Poset adalah membiarkan konstruktornya memeriksa semua pasangan unsur, sedangkan kita cukup memberinya cara untuk menguji apakah dua unsur dapat dibandingkan. Fungsi pembanding kita menerima dua unsur, lalu mengembalikan True atau False. Fungsi “lambda” merupakan salah satu cara untuk membuat fungsi semacam itu dengan cepat. Gagasan ini mungkin baru bagi Anda, tetapi menguasai fungsi lambda dapat sangat memudahkan pekerjaan. Perhatikan bahwa “lambda” merupakan kata yang dicadangkan khusus untuk tujuan ini (jadi, misalnya, lambda bukan pilihan yang baik sebagai nama nilai eigen suatu matriks). Terdapat cara lain untuk membuat fungsi dalam Sage, tetapi fungsi lambda merupakan cara tercepat jika fungsinya sederhana.

Kode Sage (cadangan statis)

divisible = lambda x, y: x.divides(y)
L = Poset([X, divisible])
L == D

Keluaran referensi (cadangan statis)

True

Kode Sage (cadangan statis)

L.plot()

Sage juga menyediakan koleksi poset bawaan. Sebagiannya merupakan konstruksi tunggal, sedangkan yang lain merupakan anggota keluarga berparameter. Gunakan pelengkapan tab pada Posets. untuk melihat daftar lengkapnya. Berikut beberapa contoh.

Suatu konstruksi tunggal. Barangkali hasilnya sesuai dengan yang Anda bayangkan, meskipun mungkin terdapat alternatif lain yang sama masuk akalnya.

Kode Sage (cadangan statis)

Q = Posets.PentagonPoset()
Q.plot()

Suatu keluarga berparameter. Ini adalah contoh klasik dengan unsur-unsur berupa himpunan bagian dari suatu himpunan berunsur \(n\) dan relasinya adalah “merupakan himpunan bagian dari.”

Kode Sage (cadangan statis)

S = Posets.BooleanLattice(4)
S.plot()

Tersedia pula poset acak. Poset ini dapat berguna untuk pengujian dan eksperimen, tetapi kecil kemungkinannya menampilkan kasus khusus yang mungkin penting. Anda dapat menjalankan perintah berikut berkali-kali sambil mengubah argumen kedua, yang merupakan batas atas kasar bagi peluang bahwa sebarang dua unsur dapat dibandingkan. Ingat bahwa plot hanya menampilkan relasi penutup. Semakin banyak unsur yang dapat dibandingkan, semakin “memanjang secara vertikal” plot tersebut.

Kode Sage (cadangan statis)

T = Posets.RandomPoset(20,0.05)
T.plot()

Subbagian 19.8.2 Sifat-Sifat Poset

Setelah memiliki suatu poset, apa yang dapat Anda lakukan dengannya? Mari kembali ke contoh pertama kita, D. Tentu saja kita dapat menentukan apakah suatu unsur lebih kecil daripada unsur lain, yang merupakan struktur mendasar suatu poset.

Kode Sage (cadangan statis)

D.is_lequal(4, 8)

Keluaran referensi (cadangan statis)

True

Kode Sage (cadangan statis)

D.is_lequal(4, 4)

Keluaran referensi (cadangan statis)

True

Kode Sage (cadangan statis)

D.is_less_than(4, 8)

Keluaran referensi (cadangan statis)

True

Kode Sage (cadangan statis)

D.is_less_than(4, 4)

Keluaran referensi (cadangan statis)

False

Kode Sage (cadangan statis)

D.is_lequal(6, 8)

Keluaran referensi (cadangan statis)

False

Kode Sage (cadangan statis)

D.is_lequal(8, 6)

Keluaran referensi (cadangan statis)

False

Perhatikan bahwa 6 dan 8 tidak dapat dibandingkan dalam poset ini (urutannya bersifat parsial). Metode .is_gequal() dan .is_greater_than() bekerja dengan cara serupa, tetapi mengembalikan True jika unsur pertama lebih besar (atau sama).

Kode Sage (cadangan statis)

D.is_gequal(8, 4)

Keluaran referensi (cadangan statis)

True

Kode Sage (cadangan statis)

D.is_greater_than(4, 8)

Keluaran referensi (cadangan statis)

False

Kita dapat mencari unsur maksimal dan minimal dari suatu poset. Poset berikut merupakan poset acak yang dibangun dengan peluang 10%, tetapi disalin di sini agar hasilnya dapat direproduksi.

Kode Sage (cadangan statis)

X = range(20)
C = [[18, 7],  [9, 11], [9, 10], [11, 8], [6, 10],
     [10, 2],   [0, 2],  [2, 1],  [1, 8], [8, 12],
     [8, 3],  [3, 15], [15, 7], [7, 16],  [7, 4],
     [16, 17], [16, 13], [4, 19], [4, 14], [14, 5]]
P = Poset([X, C])
P.plot()

Kode Sage (cadangan statis)

P.minimal_elements()

Keluaran referensi (cadangan statis)

[18, 9, 6, 0]

Kode Sage (cadangan statis)

P.maximal_elements()

Keluaran referensi (cadangan statis)

[5, 19, 13, 17, 12]

Unsur-unsur suatu poset dapat dipartisi menjadi himpunan tingkat. Dalam plot poset, unsur-unsur pada tingkat yang sama digambar pada ketinggian vertikal yang sama. Setiap himpunan tingkat diperoleh dengan menghapus semua himpunan tingkat sebelumnya, lalu mengambil unsur-unsur minimal dari hasilnya.

Kode Sage (cadangan statis)

P.level_sets()

Keluaran referensi (cadangan statis)

[[18, 9, 6, 0], [11, 10], [2], [1], [8], [3, 12],
 [15], [7], [4, 16], [14, 19, 13, 17], [5]]

Jika kita membuat dua unsur dalam R dapat dibandingkan padahal sebelumnya tidak, hasilnya merupakan suatu perluasan dari R. Perhatikan semua perluasan yang mungkin dari satu poset—kita dapat membentuk poset dari semua perluasan tersebut, dengan inklusi himpunan sebagai relasinya. Perluasan linear merupakan unsur maksimal dalam poset dari poset-poset ini. Secara informal, kita menambahkan sebanyak mungkin relasi baru yang konsisten dengan poset asal dan sedemikian sehingga hasilnya merupakan urutan total. Dengan kata lain, terdapat pengurutan unsur yang konsisten dengan urutan dalam poset. Kita dapat membangun objek semacam itu, tetapi keluarannya hanya berupa daftar unsur dalam urutan linear. Seorang ilmuwan komputer cenderung menyebutnya “pengurutan topologis.”

Kode Sage (cadangan statis)

linear = P.linear_extension(); linear

Keluaran referensi (cadangan statis)

[18, 9, 11, 6, 10, 0, 2, 1, 8, 3, 15, 
 7, 4, 14, 5, 19, 16, 13, 17, 12]

Kita dapat menyusun subposet dengan memberikan himpunan unsur yang menginduksi poset baru. Di sini kita mengambil kira-kira “separuh bagian bawah” dari poset acak P dengan menginduksi subposet pada gabungan beberapa himpunan tingkat.

Kode Sage (cadangan statis)

level = P.level_sets()
bottomhalf = sum([level[i] for i in range(5)], [])
B = P.subposet(bottomhalf)
B.plot()

Dual suatu poset mempertahankan himpunan unsur yang sama, tetapi membalik semua perbandingan.

Kode Sage (cadangan statis)

Pdual = P.dual()
Pdual.plot()

Mengambil dual dari poset keterbagian dalam Contoh 19.1.6 sama seperti mengubah relasinya menjadi “merupakan kelipatan dari.”

Kode Sage (cadangan statis)

Ddual = D.dual()
Ddual.plot()

Subbagian 19.8.3 Latis

Setiap latis merupakan poset, sehingga semua perintah di atas bekerja sama baiknya untuk latis. Namun, bagaimana cara membuat latis? Mudah—pertama buatlah poset, lalu masukkan poset tersebut ke konstruktor LatticePoset(). Namun, perlu disadari bahwa hanya karena Anda memberikan poset kepada konstruktor ini, bukan berarti hasilnya selalu berupa latis. Hanya jika poset tersebut sudah merupakan latis, Sage akan meningkatkan statusnya dari poset menjadi latis; jika peningkatan itu tidak mungkin, Anda akan memperoleh ValueError. Terakhir, perhatikan bahwa beberapa poset yang dibuat Sage sudah dikenali sebagai latis, misalnya BooleanLattice yang prototipikal.

Kode Sage (cadangan statis)

P = Posets.AntichainPoset(8)
P.is_lattice()

Keluaran referensi (cadangan statis)

False

Kode Sage (cadangan statis)

LatticePoset(P)

Keluaran referensi (cadangan statis)

Traceback (most recent call last):
...
ValueError: not a meet-semilattice: no bottom element

Komposisi bilangan bulat dari \(n\) adalah daftar bilangan bulat positif yang jumlahnya \(n\text{.}\) Suatu komposisi \(C_1\) menutupi komposisi \(C_2\) jika \(C_2\) dapat dibentuk dari \(C_1\) dengan menjumlahkan bagian-bagian yang berurutan. Sebagai contoh, \(C_1 = [2, 1, 2] \succeq [3, 2] = C_2\text{.}\) Dengan relasi ini, himpunan semua komposisi bilangan bulat dari suatu bilangan bulat tetap \(n\) merupakan poset yang juga merupakan latis.

Kode Sage (cadangan statis)

CP = Posets.IntegerCompositions(5)
C = LatticePoset(CP)
C.plot()

Temu atau gabung merupakan operasi mendasar dalam latis.

Kode Sage (cadangan statis)

par = C.an_element().parent()
a = par([1, 1, 1, 2])
b = par([2, 1, 1, 1])
a, b

Keluaran referensi (cadangan statis)

([1, 1, 1, 2], [2, 1, 1, 1])

Kode Sage (cadangan statis)

C.meet(a, b)

Keluaran referensi (cadangan statis)

[2, 1, 2]

Kode Sage (cadangan statis)

c = par([1, 4])
d = par([2, 3])
c, d

Keluaran referensi (cadangan statis)

([1, 4], [2, 3])

Kode Sage (cadangan statis)

C.join(c, d)

Keluaran referensi (cadangan statis)

[1, 1, 3]

Setelah status suatu poset ditingkatkan menjadi latis, tersedia perintah-perintah tambahan, atau sifat hasil perintah yang ada berubah.

Contoh untuk kemungkinan pertama adalah metode .is_distributive().

Kode Sage (cadangan statis)

C.is_distributive()

Keluaran referensi (cadangan statis)

True

Contoh untuk kemungkinan kedua adalah metode .top(). Apa yang disebut teks ini sebagai unsur terbesar dan unsur terkecil suatu latis disebut Sage sebagai top dan bottom. Untuk poset, .top() dan .bottom() mungkin mengembalikan suatu unsur atau mungkin tidak (dengan mengembalikan None), tetapi untuk latis, keduanya dijamin mengembalikan tepat satu unsur.

Kode Sage (cadangan statis)

C.top()

Keluaran referensi (cadangan statis)

[1, 1, 1, 1, 1]

Kode Sage (cadangan statis)

C.bottom()

Keluaran referensi (cadangan statis)

[5]

Perhatikan bahwa semua nilai yang dikembalikan merupakan unsur latis, dalam hal ini berupa daftar terurut bilangan bulat yang jumlahnya \(5\text{.}\)

Kini komplemen bermakna dalam suatu latis. Hasil metode .complements() adalah kamus yang menggunakan unsur-unsur latis sebagai kunci. Kita mengatakan bahwa kamus tersebut “diindeks” oleh unsur-unsur latis. Hasilnya berupa daftar komplemen dari unsur tersebut. Daftar ini kita sebut “nilai” dari pasangan kunci-nilai. (Anda mungkin mengenal kamus sebagai “larik asosiatif”, tetapi pada dasarnya kamus hanyalah fungsi yang lebih canggih.)

Kode Sage (cadangan statis)

comp = C.complements()
comp[par([1, 1, 1, 2])]

Keluaran referensi (cadangan statis)

[[4, 1]]

Latis komposisi bilangan bulat merupakan latis berkomplemen, sebagaimana terlihat dari hasil bahwa setiap unsur memiliki satu komplemen tunggal, yang ditunjukkan oleh daftar berpanjang \(1\) pada nilai-nilai kamus. Atau kita dapat langsung menanyakannya kepada Sage melalui .is_complemented(). Kamus tidak memiliki urutan bawaan, sehingga Anda mungkin memperoleh keluaran yang berbeda setiap kali memeriksa kamus tersebut.

Kode Sage (cadangan statis)

comp

Keluaran referensi (cadangan statis)

{[1, 1, 1, 1, 1]: [[5]],
 [1, 1, 1, 2]: [[4, 1]],
 [1, 1, 2, 1]: [[3, 2]],
 [1, 1, 3]: [[3, 1, 1]],
 [1, 2, 1, 1]: [[2, 3]],
 [1, 2, 2]: [[2, 2, 1]],
 [1, 3, 1]: [[2, 1, 2]],
 [1, 4]: [[2, 1, 1, 1]],
 [2, 1, 1, 1]: [[1, 4]],
 [2, 1, 2]: [[1, 3, 1]],
 [2, 2, 1]: [[1, 2, 2]],
 [2, 3]: [[1, 2, 1, 1]],
 [3, 1, 1]: [[1, 1, 3]],
 [3, 2]: [[1, 1, 2, 1]],
 [4, 1]: [[1, 1, 1, 2]],
 [5]: [[1, 1, 1, 1, 1]]}

Kode Sage (cadangan statis)

[len(e[1]) for e in comp.items()]

Keluaran referensi (cadangan statis)

[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]

Kode Sage (cadangan statis)

C.is_complemented()

Keluaran referensi (cadangan statis)

True

Masih banyak perintah lain yang berlaku untuk poset dan latis, jadi buatlah beberapa contoh dan gunakan pelengkapan tab secara leluasa untuk menjelajahinya. Ada lebih banyak hal yang dapat ditemukan daripada yang mampu kita bahas dalam satu bab, tetapi kini Anda memiliki perkakas dasar untuk mempelajari poset dan latis secara produktif dalam Sage.

Sblm.Paling Atas Lanjut