Prof. Dra. Kiki Ariyanti Sugeng, M.Si., Ph.D.

Video ini membahas konsep leksikografi dalam Matematika Diskrit, dengan contoh pengurutan pasangan angka dalam produk Cartesian dari Z x Z. Konsep ini memungkinkan kita untuk membandingkan pasangan terurut berdasarkan elemen-elemennya secara berurutan. Dalam leksikografi, urutan pasangan ditentukan berdasarkan elemen pertama, kemudian elemen kedua jika elemen pertama sama. Pengurutan leksikografi juga dapat diterapkan pada produk Cartesian dari himpunan A1, A2 sampai AN. Selain itu, pengurutan leksikografi juga dapat digunakan untuk membandingkan string dengan panjang yang berbeda, dengan menentukan elemen minimum untuk dibandingkan. Konsep ini memungkinkan kita untuk mengurutkan string secara leksikografi berdasarkan elemen-elemen mereka.

Sekarang kita bahas contohnya ya, kalau kita punya poset dari Z x Z yaitu karakterisasi produk dari Z sama Z kemudian relasinya lebih kecil sama dengan.

Sekarang kita lihat apakah pasangan terurut 3,5 itu akan lebih kecil dari 4,8 atau apakah 3,8 lebih kecil dari 4,5?

Dengan asumsi urutannya itu leksikografi dengan relasi lebih kecil sama dengan pada Z.

Oke kita lihat sekarang, kalau kita mau bandingkan 3,5 pasangan terurut 3,5 dan 4,8.

Kita lihat elemen pertamanya dulu, 3 itu lebih kecil dari 4 sehingga kita bisa mengatakan secara leksikografi 3,5 pasangan terurut 3,5 itu lebih kecil dari 4,8.

Nah sekarang yang kedua, tadi ditanyakan 3,8 dan 4,5 itu apakah pasangan terurut 3,8 itu lebih kecil dari pasangan terurut 4,5?

Dan kita lihat elemen pertamanya, 3 lebih kecil dari 4 kita tidak peduli dengan elemen keduanya, kita bisa mengatakan bahwa pasangan terurut 3,8 itu lebih kecil dari 4,5.

Nah sekarang pasangan yang terakhir, 4,9 dengan 4,11.

Kita lihat entry pertamanya itu sama-sama 4 sehingga kita lihat entry keduanya,

4,9 dengan 4,11 maka 9 lebih kecil dari 11 sehingga kita bisa menyimpulkan bahwa di dalam relasi leksikografi 4,9 itu lebih kecil dari 4,11.

Jadi kalau kita lihat pengurutan leksikografi itu bisa digambarkan dalam diagram seperti ini,

jadi kalau kita melihat bilangan bulat yang positif.

Jadi kita kan punya pasangan-pasangan 1,1, 2,1, 3,1, 4,1, 5,1, 6,1, 7,1 dan seterusnya

kemudian nanti 1,2, 2,2, 3,2, 4,2, 5,2, 6,2, 7,2 terus sampai semua pasangan sudah kita cantumkan.

Nah sekarang kalau untuk melihat urutannya bagaimana?

Kalau digambar di diagram ini, kolom 1 itu semua dimulai dengan 1,

jadi artinya sama, jadi setiap kolom itu elemen pertamanya itu dibuat sama semua,

kolom kedua itu kita lihat semuanya dimulai dengan 2,

kolom ketiga kita bisa lihat semua dimulai dengan 3,

sehingga nanti kalau kita mau membandingkan kita lihat di kolom 1 dulu,

kolom 1 itu karena elemen pertamanya 1 semua kita enggak bisa memutuskan,

sehingga kita melihatnya di elemen yang kedua.

1,1 itu sama 1,2 kan 1 lebih kecil 2 berarti untuk yang baris yang paling bawah,

baris 1, kolom 1 itu lebih kecil sama dengan 1,2 terus nanti 1,2 lebih kecil sama dengan 1,3,

1,3 lebih kecil sama dengan 1,4 dan seterusnya ke atas.

Begitu juga untuk kolom-kolom yang lainnya.

Sekarang kalau kita lihat misalnya ke baris,

kalau kita lihat ke baris itu yang sama adalah kolom keduanya,

tapi untuk menentukan urutan leksikografi kan kita melihat dulu elemen pertamanya,

elemen pertamanya di sini kan 1,1,2,1,3,1,4,1 dan seterusnya,

dan 1 lebih kecil 2, 2 lebih kecil 3, 3 lebih kecil 4,

sehingga kita bisa membuat relasi leksikografinya itu berurut,

1,1 lebih kecil 2,1 lebih kecil 3,1 lebih kecil 4,1 dan seterusnya.

Begitu juga untuk baris-baris di atasnya sama.

Sekarang kalau kita mau lihat misalnya urutannya bukan per baris atau per kolom,

misalnya saya ambil aja sembarang di sini 4,4 dengan 6,5.

Kita lihat yang pertama 4,4 sama 6,5 itu 4 yang elemen pertama,

itu kan lebih kecil dari 6 di pasangan terurut yang kedua,

jadi kita bisa mengatakan dia terurut secara leksikografi.

jadi kita punya pasangan 7,2 dan pasangan 6,3.

Kita lihat yang pertama 7 itu lebih besar dari 6,

kemudian kita lihat karena di sini lebih besar berarti kita tidak bisa membandingkan,

jadi kita balik coba 6,3 sama 7,2 ternyata 6 nya lebih kecil dari 7,

jadi ini bisa kita ambil kesimpulan pasangan 6,3 itu lebih kecil dari 7,2.

Jadi kita melihat dari pasangan pertama dulu kemudian yang kedua dan seterusnya.

Ini nanti bisa diperluas bukan hanya diantara dua,

tapi kita juga bisa membuat pengurutan leksikografi

untuk produk cartesian dari A1, A2 sampai AN.

Jadi kita punya nanti anggota himpunannya itu adalah A1, A2, A3 sampai AN,

B1, B2, B3 sampai BN itu nanti kita bisa tentukan juga dengan cara yang sama,

jadi kita lihat kalau A1 nya lebih kecil B1 itu artinya dia lebih kecil,

atau misalnya A1 sama dengan B1 dan seterusnya nanti yang berikutnya yang dilihat

apakah lebih kecil atau tidak, itu cara pengurutan leksikografi.

Kalau tadi kita lihat pada bilangan gimana kalau misalnya kita lihatnya S nya itu adalah string,

jadi string itu bisa dari angka-angka tapi bukan bilangan kan ya,

jadi kita punya string A1 sampai AN dan B1 sampai BN misalnya belum tentu sama panjangnya,

nah ini kita misalkan MN itu karena tidak sama panjangnya pasti ada yang lebih kecil,

Bagaimana kita mengatakan apakah A1, A2 sampai AN itu lebih kecil dari B1 sampai BN?

Yang pertama adalah kita ambil T nya tadi yang minimum kita bandingkan,

kalau A1 sampai AT itu lebih kecil dari B1 sampai BT artinya elemen stringnya itu akan lebih kecil.

Kalau dia ternyata sama itu untuk sampai T kita lihat M nya lebih kecil dari N tidak?

Kalau M lebih kecil dari N berarti dia juga kita bisa urutkan secara leksikografi dengan lebih kecil sama dengan.

Kalau dia tidak sama panjang kita harus menentukan T nya supaya kita bisa bandingkan,

jadi yang lebih besar dari minimumnya itu diabaikan.