Gini dan Desil

Halo! Kali ini, kita bahas tentang ilmu statistika.

Beberapa waktu lalu, sempat ramai mengenai desil dan keanehan-keanehan yang ada pada saat ini. Namun, aku ingin membahas lebih banyak dari sisi statistika, dimulai dari kuantil.

Kuantil (Desil dan Sebagainya)

Kuantil adalah cara untuk menentukan letak suatu data tunggal dalam sampel/populasi. Kuartil adalah cara untuk mengelompokkan sampel/populasi menjadi 4 tingkat/kelompok. Desil mengelompokkan menjadi 10 kelompok. Persentil mengelompokkan menjadi 100 kelompok.

Ilustrasi kuartil (4), desil (10), dan persentil (100)

Sebagai contoh, ada contoh data berikut yang akan dihitung kuartilnya. Cara membaginya adalah dengan mengurutkan dan kemudian membaginya menjadi empat.

7	6	3	3	5	6	9	8	2	3	8	1	2	4	5	1
↓↓↓   Urutkan   ↓↓↓
1	1	2	2	3	3	3	4	5	5	6	6	7	8	8	9
↓↓↓   Partisi   ↓↓↓
1	1	2	2	3	3	3	4	5	5	6	6	7	8	8	9
Kuartil 1				Kuartil 2				Kuartil 3				Kuartil 4

Setelah data dibagi menjadi empat kelompok itu, tiap kelompok bisa diukur ciri-cirinya, seperti jumlah dan rata-rata.

Kuartil	Jumlah	Rata-Rata
Q1	6 (8,2%)	1,50
Q2	13 (17,8%)	3,25
Q3	22 (30,1%)	5,50
Q4	32 (43,8%)	8,00
Total	73 (100%)

Selain melihat ukuran-ukuran tiap kelompok, kita juga bisa melihat ukuran kumulatif tiap kelompok. Kumulatif yang dimaksud adalah mengelompokkan suatu kelompok dengan kelompok-kelompok sebelumnya (atau setelahnya, tergantung urutan yang dimaksud). Misalnya, kumulatif sampai kuartil ketiga dari bawah adalah gabungan dari kuartil pertama, kuartil kedua, dan kuartil ketiga.

Kuartil	Jumlah Kumulatif
Q1	6 (8,2%)
Q2	19 (26,0%)
Q3	41 (56,2%)
Q4	73 (100,0%)

Ukuran kumulatif seperti di atas digunakan dalam banyak hal. Di bidang pengolahan citra misalnya, ukuran kumulatif digunakan untuk meningkatkan kualitas kontras citra dengan metode histogram equalization. Kali ini, yang akan kita bahas adalah contoh di bidang ekonomi.

Koefisien Gini

Koefisien Gini adalah ukuran penyebaran data yang dimaksudkan untuk mewakili ketimpangan pendapatan, ketimpangan pemasukan, atau ketimpangan konsumsi dalam sebuah bangsa atau sebuah kelompok sosial. Koefisien ini memiliki rentang nilai dari 0 (tidak ada ketimpangan) hingga 1 atau 100% (ketimpangan maksimum). Nama koefisien ini diambil dari nama ahli sosiologi Corrado Gini.

Sebagai contoh, koefisien Gini pendapatan masyarakat di keseluruhan Uni Eropa pada tahun 2025 sebesar 29,2% (Eurostat, 2026). Koefisiennya di Amerika Serikat pada tahun 2024 sebesar 41,8% (World Bank, 2024) dan di Indonesia pada tahun 2025 sebesar 34,4% (World Bank, 2025).

Secara matematis, koefisien Gini dihitung menggunakan kurva Lorenz. Kurva Lorenz adalah gambaran persebaran pendapatan atau kekayaan. Kurva ini adalah grafik kumulatif yang menyatakan sekian persen sampel/populasi terbawah memiliki sekian persen total pendapatan atau kekayaan. Selain kurva Lorenz, ada juga garis kesetaraan yang dimulai dari kiri-bawah (0, 0) ke kanan-atas (1, 1). Koefisien Gini adalah perbandingan luas di bawah garis kesetaraan (X) dan di atas kurva Lorenz dibagi dengan luas bawah kurva Lorenz (Y). Gambar berikut menggambarkan luasan yang dimaksud.

Garis kesetaraan, kurva Lorenz, daerah X, dan daerah Y

Pada praktiknya, kurva Lorenz tidak bisa bersifat kontinu dan hanya bisa didekati secara diskret. Salah satu cara yang bisa digunakan adalah dengan menggunakan kuantil yang tersedia karena menghitung jutaan (bahkan ratusan juta) data sekaligus untuk menghitung kurva Lorenz terlalu berat dan rawan terkena derau dalam data (overfitting).

Sebagai contoh, misalkan 50% populasi terbawah hanya memiliki 20% kekayaan. Kurva Lorenz bisa didekati dengan bentuk trapesium. Berikut ilustrasinya.

Contoh kasus dua kelompok

Koefisien Gini adalah luas X dibagi luas X + Y. Untuk kasus ini, misalkan tidak ada yang memiliki kekayaan minus, maka luas X + Y adalah 0,5. Kita bisa menggunakan rumus luas trapesium untuk menghitung luas Y.

Y = (1/2) × (0% + 20%) × 50% + (1/2) × (20% + 100%) × 50%

Y = 0,5 × 0,2 × 0,5 + 0,5 × 1,2 × 0,5

Y = 0,05 + 0,3

Y = 0,35

Kemudian, kita hitung koefisien Gini darinya.

Gini = X / (X + Y)

Gini = (0,5 - Y) / (0,5)

Gini = (0,5 - 0,35) / (0,5)

Gini = (0,15) / (0,5)

Gini = 0,3 = 30%

Hasilnya ditunjukkan di ilustrasi di atas.

Gini ke Desil

Kita juga bisa memperkirakan nilai tiap desil berdasarkan koefisien Gini yang diketahui. Meski bentuk kurva Lorenz yang berbeda bisa memiliki koefisien Gini yang sama, setidaknya kita jadi mendapat gambaran secara kasar dengan asumsi-asumsi tertentu yang kita tentukan sebelumnya.

Kekayaan masyarakat di Indonesia

Sebagai contoh, koefisien Gini kekayaan masyarakat di Indonesia pada tahun 2021 sebesar 78,2% (Credit Suisse, 2022), di atas Kamboja (78,3%) dan di bawah Ginea-Bisau dan Tunisia (78,0%).

Dengan asumsi kekayaan masyarakat tiap desil mengikuti pola cx^k + 10^-4 dengan x adalah nilai desil dibagi 10 lalu ditambah 0,05. Dengan metode bisection, kita bisa mendekati nilai k dan c, yaitu k ≈ 7,80014 dan c ≈ 9,04713.

Perkiraan persebaran kekayaan untuk koefisien Gini sebesar 78,2%.

Dari grafik di atas, sangat terlihat perbedaan persentase kekayaan tiap desil, terutama desil-desil atas. Desil 10 bahkan menguasai sekitar 60% kekayaan masyarakat jika menggunakan asumsi di atas.

Pendapatan masyarakat di Indonesia

Kita ambil contoh lain. Koefisien Gini pendapatan masyarakat di Indonesia pada tahun 2025 sebesar 34,4% (World Bank, 2025). Selain itu, desil ke-10 pendapatan masyarakat menguasai 41,24% total pendapatan nasional (World Inequality Database, 2024). Dengan asumsi pola desil yang sama, kecuali desil 10 yang sudah diketahui, kita bisa mendekati nilai k dan c, yaitu k ≈ 0,13625 dan c ≈ 1,14898.

Perkiraan persebaran pendapatan untuk koefisien Gini sebesar 34,4% dengan desil ke-10 pendapatan masyarakat menguasai 41,24% total pendapatan nasional

Dari grafik di atas, sangat timpang persentase pendapatan desil ke-10 bila dibandingkan dengan desil-desil lainnya.

Desil vs. Persentil

Dari kedua contoh pemodelan di atas, desil ke-10 sangat timpang bila dibandingkan dengan desil-desil lain. Hal ini membuat sebagian bertanya, "Apakah desil sudah cukup detail?" Hal ini diperkuat oleh data dari World Inequality Database (2024) yang menunjukkan persebaran pendapatan dan kekayaan masyarakat yang sangat timpang. Berikut data untuk Indonesia pada tahun 2024.

Kuantil	Pendapatan	Kekayaan
1% teratas	17,85%	21,32%
10% teratas	46,86%	60,38%
50% terbawah	12,45%	2,44%

Persentil ke-100 menguasai 38,09% pendapatan dan 35,31% kekayaan desil ke-10. Hal ini menunjukkan bahwa data tiap desil perlu dilengkapi dengan data tiap persentil, terutama untuk desil ke-10. Ini adalah kritik kepada lembaga-lembaga yang mengurusi statistik penduduk.

Dalam operasional sistem, biasa dikenal ukuran statistik P90, P95, dan P99 (90% terbawah, 95% terbawah, dan 99% terbawah) untuk mengetahui kasus-kasus yang jarang terjadi (anomali) dalam rentang waktu tertentu. Kalau semisal lembaga-lembaga tersebut belum bisa (atau belum berani) memublikasikan keseluruhan persentil, setidaknya publikasikan juga ketiga bagian/kuantil itu di samping data tiap desil yang sudah ada.

Penutup

Kalau kita melihat ketimpangan yang ada di sekitar, rasanya memang menyedihkan, terlebih lagi banyak yang seharusnya berwenang itu justru skill issue dalam menanganinya (bahkan justru mengisi kantung pribadi). Yang bisa kita lakukan, ya, ikut membantu sesama: rakyat bantu rakyat.

Cukup sekian tulisanku. Semoga kita bisa sukses bersama. Sampai jumpa!

Satuan Word dan Bita dalam Pemrograman

Halo!

Pada tulisanku sebelumnya, kita sudah membahas tentang satuan bit dalam pemrograman. Kali ini, kita bahas satuan word dan bita, ya.

Sejarah

Kemampuan tiap sistem/prosesor sangat beragam pada mulanya. Ada yang bisa mengolah hingga 36 bit sekaligus, tetapi juga ada yang hanya bisa mengolah 6 bit dalam sekali jalan. Sebagai contoh, IBM 704 mampu mengolah 36 bit sekaligus, tetapi hanya untuk bilangan. Untuk karakter alfanumerik, IBM 704 mengolah tiap karakter sebagai desimal berkode biner (BCD) berukuran 6 bit. Perbedaan ini baru dalam satu sistem yang sama. Sistem-sistem lain bisa memiliki ketentuan masing-masing sesuai kapasitas masing-masing sehingga tidak ada ukuran pasti untuk satuan word dan bita.

Pada tahun 1964, IBM meluncurkan IBM System/360 sekaligus membuat standar ukuran 1 bita sama dengan 8 bit. Selain itu, sistem ini juga menggunakan alamat memori dalam satuan bita juga alih-alih satuan bit ataupun satuan word. Karena IBM menguasai pasar komputer pada waktu itu, kebanyakan sistem akhirnya juga mengikuti standar 1 bita = 8 bit ini.

Meski satuan bita sudah terstandar, tiap sistem masih memiliki ukuran word yang berbeda-beda. Hanya saja, sejak satuan bita sudah distandardisasi, ukuran word menjadi kelipatan dari bita. Sebagai contoh, IBM System/360 yang dibahas sebelumnya itu memiliki ukuran word sebesar 4 bita (32 bit).

Tahun 1970-an menjadi tahun mikroprosesor dengan ukuran word sebesar 8 bit. Contoh mikroprosesor pada masa ini adalah Intel 8008, Intel 8080, dan Zilog Z80. Komputer/konsol permainan rumahan yang menggunakan ukuran word ini ada Commodore 64, Nintendo Entertainment System, dan Game Boy.

Akhir 1970-an dan awal 1980-an adalah masa ukuran word sebesar 16 bit. Intel meluncurkan mikroprosesor Intel 8086 pada tahun 1978. Intel 8086 menjadi salah satu pelopor ukuran word 16 bit dan menjadi asal mula keluarga/arsitektur x86 yang masih menjadi mayoritas arsitektur prosesor saat ini. IBM juga meluncurkan IBM PC pada tahun 1981 yang menggunakan Intel 8088, variasi dari Intel 8086. IBM PC yang populer pada masa itu menjadi penanda penggunaan ukuran word 16 bit untuk keperluan bisnis di lapangan.

Sebelum lanjut ke masa-masa berikutnya, aku mau cerita tentang Apollo Guidance Computer (AGC), komputer yang memandu wahana Apollo selama misi ke Bulan. AGC pertama kali diumumkan pada tahun 1966, sebelum ukuran word 8 bit menjadi populer. Namun, AGC sudah menggunakan ukuran word 16 bit. Pada praktiknya, yang digunakan hanya 15 bit karena 1 bit digunakan untuk pemeriksaan kesalahan (akibat radiasi di luar angkasa misalnya). Dengan ukuran RAM yang hanya 2.048 word (sekitar 4 kilobita) dan ukuran penyimpanan internal yang hanya 36.864 word (sekitar 72 kilobita), AGC bisa mengantarkan astronot ke Bulan dan pulang ke Bumi lagi. Sebagai perbandingan, foto jepretan kamera HP sekarang berukuran sekitar 3 megabita (sekitar 3 ribu kilobita).

Pada tahun 1986, Intel meluncurkan prosesor yang menjadi salah satu pelopor ukuran word 32 bit, yaitu Intel 80386 atau i386. Prosesor ini dikembangkan bersama dengan AMD dan IBM. Ukuran word 32 bit ini cukup lama menjadi standar komputer, bahkan hingga tahun 2010-an. Prosesor lainnya yang mungkin teman-teman masih ingat ada Intel Pentium, Intel Core i3, i5, dan i7 juga bermula dari sini. Sistem operasi yang kita kenal dahulu seperti Windows XP utamanya disusun dengan memperhatikan ukuran word ini. (Catatan untuk Windows: Meski demikian, tipe data WORD dalam API Windows berukuran 16 bit, DWORD [double word] berukuran 32 bit, dan QWORD [quad word] berukuran 64 bit.)

Pada tahun 2003, AMD meluncurkan prosesor Athlon 64 yang menjadi salah satu pelopor ukuran word 64 bit. Apple juga menyusul segera dengan Power Mac G5. Ukuran word 64 bit ini juga menjadi titik awal dukungan untuk RAM berukuran lebih dari 4 gigabita. Per tahun 2010-an, hampir semua komputer yang dirakit sudah menggunakan ukuran word ini. Sekarang, ponsel pintar pun sudah menggunakan ukuran word ini juga.

Untuk keluarga/arsitektur x86, meski sudah ada dukungan untuk ukuran word yang lebih besar, tiap prosesor yang lebih baru mendukung operasi untuk data dengan ukuran yang lebih kecil.

Ukuran Data dalam Pemrograman

Keragaman ukuran word ini bisa membuat hasil jalan program tidak sesuai rancangan awal. Sebagai contoh, sebuah program didesain untuk bisa menerima data sampai 1 kuintiliun (10¹⁸) karena ditujukan untuk prosesor yang mendukung 64 bit. Namun, program itu akan gagal jalan atau tidak memberikan hasil yang sesuai jika dijalankan pada prosesor yang hanya mendukung 32 bit.

Tiap bahasa pemrograman memiliki cara masing-masing dalam menyatakan ukuran sebuah variabel. Sebagai contoh, standar bahasa C tidak memberikan ukuran pasti untuk char, int, dan long, tetapi hanya mengatur ukuran minimalnya (≥8, ≥16, dan ≥32 bit masing-masing). Ukuran pastinya bergantung pada implementasi di tiap-tiap komputer. Pada tahun 1999, standar C99 akhirnya memberikan tipe data baru untuk menyatakan dengan pasti ukuran tiap variabel. Contohnya ada int8_t, int16_t, int32_t, dan int64_t untuk ukuran 8, 16, 32, dan 64 bit.

Bahasa Java mengatur ukuran tiap tipe data secara pasti untuk short, int, dan long dengan ukuran 16, 32, dan 64 bit. Bahasa Go bahkan tidak lagi menggunakan nama-nama seperti C dan Java, tetapi langsung menyatakan ukurannya secara tersurat. Contohnya ada int16, int32, dan int64 untuk ukuran 16, 32, dan 64 bit..

Selain bahasa-bahasa yang mengatur ukuran tiap variabel itu, ada juga bahasa yang menyeragamkan untuk semua ukuran. Bahasa JavaScript menggunakan tipe data Number untuk bilangan bulat dan bilangan pecahan serta BigInt untuk bilangan yang berukuran besar. Bahasa Python menggunakan tipe data int yang akan secara otomatis memperbanyak jumlah bit yang diperlukan sesuai bilangan yang dimuat oleh variabel tersebut.

Secara ringkas, berikut tabel yang menunjukkan contoh cara-cara bahasa pemrograman menyatakan ukuran variabel.

Bahasa	8 bit	16 bit	32 bit	64 bit
C	char	short	int	long
C (C99)	int8_t	int16_t	int32_t	int64_t
Java	byte	short	int	long
Go	int8	int16	int32	int64
JavaScript	Number			BigInt
Python	int

Penutup

Cukup sampai di sini bahasa tentang satuan word dan bita dalam pemrograman. Lebih banyak bahas sejarahnya ternyata kali ini. Semoga membantu, ya!

Satuan Bit dalam Pemrograman

Halo!

Kita mungkin sudah biasa dengan satuan bita (byte) dalam pemrograman. Tahukah kalian bahwa ada cara lain untuk mengatur data?

Setidaknya, ada tiga cara pandang utama dalam mengatur data dalam pemrograman, yaitu bit, word, dan bita. Kali ini, kita bahas satuan bit, ya.

Sejarah

Pada mulanya, komputer perlu diprogram bit demi bit. Pemrogram komputer akan mengatur tiap bit saat menyetel, memrogram, dan memasukkan data. Karena untaian bit sulit dibaca dan rentan keliru saat diatur, dibuatlah kartu tebuk (punch card) sebagai gantinya. Konsep kartu tebuk awalnya berasal dari mesin tenun otomatis. Mesin-mesin tenun ini dapat menyusun pola berdasarkan lubang pada kartu tebuk.

Kartu tabuk biner (Arnold Reinhold, CC BY-SA 2.5)

Pada masa kini pun, pengaturan data dalam satuan bit masih digunakan. Kriptografi mengolah data dalam satuan bit untuk menyandikan dan membuka sandi suatu data. Saat menggunakan perangkat keras, misalnya sensor atau aktuator, kita perlu menyalakan bit-bit tertentu untuk menerima data atau mengirim perintah.

Oleh karena itu, dalam banyak bahasa pemrograman, masih ada dukungan untuk manipulasi bit walau satuan utamanya tidak lagi dalam bit. Contohnya ada operasi OR, AND, dan XOR untuk mengatur bit-bit tertentu serta operasi NOT untuk membalik nilai bit. Ada juga operasi SHL (shift left), SHR (shift right), ROL (rotate left), dan ROR (rotate right) untuk melakukan geser atau geser melingkar. Aku pernah membahas contoh operasi geseran melingkar pada tulisanku sebelumnya tentang jaringan substitusi-permutasi.

Bit Mask (Tabir Bit)

Contoh kasusnya adalah penggunaan bit mask (tabir bit). Tiap setelan biner (ya-tidak atau nyala-mati) diwakili oleh satu bit. Untaian bit ini bisa berisi banyak setelan sekaligus.

Misalkan ada sebuah mobil mainan yang memiliki motor mandiri untuk tiap rodanya. Keadaan motor tiap roda kita kumpulkan dalam suatu untaian bit. Kita bisa mengatur motor tiap roda dengan operasi bit.

kendali = WXYZ
X--Y (depan)
|  |
|  |
W--Z (belakang)

Untuk menyalakan, kita bisa menggunakan operasi OR dengan 1 pada bit yang dimaksud dan dengan 0 pada bit-bit lainnya.

   0000 (semuanya mati)
OR 1000
   1000 (kiri belakang nyala, lainnya mati)

Untuk mematikan, kita bisa menggunakan operasi AND dengan 0 (awas, kebalikan dari operasi lain) pada bit yang dimaksud dan dengan 1 pada bit-bit lainnya.

    1000 (kiri belakang nyala, lainnya mati)
AND 0111
    0000 (semuanya mati)

Untuk membalikkan keadaan, kita bisa menggunakan operasi XOR dengan 1 pada bit yang dimaksud dan dengan 0 pada bit-bit lainnya.

    0000 (semuanya mati)
XOR 1000
    1000 (kiri belakang nyala, lainnya mati)
XOR 1000
    0000 (semuanya mati)

Untuk memeriksa keadaan, kita bisa menggunakan operasi AND dengan 1 pada bit yang dimaksud dan dengan 0 pada bit-bit lainnya, lalu melihat hasilnya (bernilai nol atau tidak).

    1111 (semua nyala)
AND 1000 (periksa kiri belakang)
    1000 (lebih dari nol: kiri belakang nyala)

Agar mudah digunakan dan dibaca, biasanya tiap bit disimpan ke dalam variabel.

KIRI_BELAKANG  = 1000
KIRI_DEPAN     = 0100
KANAN_DEPAN    = 0010
KANAN_BELAKANG = 0001

Kita juga bisa menggabungkan beberapa roda sekaligus untuk mengaturnya dalam sekali jalan.

KIRI     = KIRI_BELAKANG  OR KIRI_DEPAN
KANAN    = KANAN_BELAKANG OR KANAN_DEPAN
BELAKANG = KIRI_BELAKANG  OR KANAN_BELAKANG
DEPAN    = KIRI_DEPAN     OR KANAN_DEPAN
SEMUA    = KIRI           OR KANAN
SEMUA    = BELAKANG       OR DEPAN

Berikut contoh penggunaannya:

kendali AND NOT SEMUA         (0000, semuanya mati)
kendali OR      KIRI_BELAKANG (1000, kiri belakang nyala, lainnya mati)
kendali AND NOT KIRI_BELAKANG (0000, kiri belakang mati juga)
kendali OR      DEPAN         (0110, depan nyala, belakang mati)
kendali XOR     KIRI_DEPAN    (0010, kanan depan nyala, lainnya mati)

kendali AND KANAN_DEPAN > 0 = BENAR (kanan depan nyala)

Penutup

Sepertinya cukup sampai di sini bahasa tentang satuan bit dalam pemrograman. Untuk selanjutnya, masih ada satuan word dan satuan bita yang bisa kita bahas bersama. Semoga membantu dan sampai jumpa!

Perbandingan Terbalik dan Lama Pengerjaan

Halo!

Mungkin teman-teman pernah membaca soal-soal sejenis ini:

Sebuah gedung akan selesai dibangun dalam waktu 6 bulan oleh 20 orang pekerja. Jika ternyata pembangunan gedung perlu selesai dalam waktu 4 bulan, berapa jumlah pekerja yang diperlukan?

Soal-soal sejenis ini biasanya digunakan untuk belajar materi perbandingan terbalik. Dalam perbandingan biasa, makin besar suatu nilai dalam perbandingan, makin besar pula nilai aslinya. Kebalikannya, dalam perbandingan terbalik, makin besar suatu nilai dalam perbandingan, justru makin kecil nilai aslinya.

Contoh perbandingan biasa adalah perbandingan jarak dengan lama perjalanan: jarak 60 km perlu 1 jam, maka jarak 120 km perlu 2 jam. Contoh perbandingan terbalik, ya, yang ada pada soal di atas: 6 bulan perlu 20 orang pekerja, maka 4 bulan perlu 30 orang pekerja.

Sebenarnya, rumus asalnya masih sama untuk perbandingan, yaitu x : y = A : B. Hanya saja, yang membedakannya adalah nilai x dan y yang digunakan. Pada perbandingan biasa, nilainya sesuai yang diketahui. Pada perbandingan terbalik, nilainya adalah kebalikannya (1/x). Nilai ini biasa kubayangkan sebagai "kecepatan" karena sering muncul pada soal yang membahas lama pengerjaan.

Meski cocok untuk belajar perbandingan terbalik, perhitungan ini belum tentu bisa diterapkan di dunia nyata. Terdapat bagian-bagian pekerjaan yang tidak bisa dipercepat meski ada tambahan tenaga ataupun bahan. Dalam contoh pembangunan gedung misalnya, menunggu hasil cor tidak bisa dipercepat dengan tambahan tenaga.

Dalam topik rekayasa perangkat lunak pun, konsepnya juga sama. Ada batas atas ukuran tim dalam mengerjakan suatu sistem atau komponen sistem (tergantung ukuran dan kompleksitasnya). Bila ukuran tim sudah melebihi batas itu, tidak ada peningkatan laju pengerjaan dan justru ada masalah baru, yaitu komunikasi antar-anggota tim.

Aku pernah menemukan soal di internet yang "agak lain" juga terkait perbandingan terbalik:

Sebuah orkestra menyelesaikan satu lagu dalam waktu 30 menit oleh 20 orang pemain. Jika mendapatkan 10 orang pemain tambahan, mereka akan menyelesaikan satu lagu dalam waktu berapa lama?

Ini, ceritanya, memainkan lagunya dipercepat begitukah? Ya ... namanya juga hanya contoh soal cerita. Tidak apa-apa meleset sedikit dari aslinya di dunia nyata.

Cukup sekian tulisanku kali ini. Sampai jumpa!

Jika dan Hanya Jika

Halo!

Pernahkah kalian dengar ungkapan jika dan hanya jika? Kata-kata ini biasanya muncul dalam konteks matematika, logika, atau hukum. Istilah ini terdiri dari dua bagian, yaitu (1) jika dan (2) hanya jika.

Kata jika menjadi kata depan yang menandai sebab dari suatu kejadian. Contohnya, dalam kalimat, "Aku akan tetap pergi jika dia tidak mengabariku," klausa dia tidak mengabariku menjadi sebab/faktor terjadi aku akan tetap pergi. Namun, hal sebaliknya tidak demikian. Kejadian aku akan tetap pergi belum tentu selalu disebabkan oleh dia tidak mengabariku.

Secara matematis, operasi jika atau implikasi disimbolkan dengan panah kanan (→). Contohnya, A → B. Yang harus diperhatikan adalah bahwa operasi ini hanya bernilai salah saat B salah, padahal A benar. Cara mengingatnya adalah dengan selalu berpikir bahwa (1) penyebab/faktor suatu kejadian bisa ada lebih dari satu dan (2) definisi faktor itu memang hal yang menyebabkan sesuatu terjadi.

Sebaliknya, istilah hanya jika adalah kebalikan arah dari jika. Operasi ini disimbolkan dengan panah kiri (←). Contohnya, A ← B. Dalam matematika, operasi pembalikan ini disebut konvers dari suatu pernyataan. Yang harus diperhatikan adalah bahwa implikasi tidak sama dengan hasil konversnya, yaitu suatu kejadian belum tentu akibat dari faktor yang dimaksud (bisa disebabkan oleh faktor lain).

Ringkasnya, tabel kebenaran dari implikasi dan konversnya adalah berikut:

A	B	A → B (implikasi)	A ← B (konvers)
benar	benar	benar	benar
benar	salah	salah	benar
salah	benar	benar	salah
salah	salah	benar	benar

Terakhir, yang dimaksud jika dan hanya jika (↔) adalah hasil konjungsi (operasi dan) dari operasi jika dan operasi hanya jika. Dari tabel di atas, yang bernilai benar untuk keduanya hanya saat A dan B benar. Karena itulah, operasi ini juga bisa disimbolkan dengan sama dengan tiga (≡).

Jadi, kalau bertemu kata-kata jika dan hanya jika, jangan bingung lagi, ya, dengan maksudnya. Semoga bermanfaat!

Urutan Operasi dan Sifat Asosiatif

Pernahkah kalian menemukan kalimat matematika yang berisi operasi dengan prioritas/urutan pengerjaan yang sama? Sebagai contoh, 7 - 3 - 2 akan menghasilkan 2 (bukan 6) karena yang terletak di sebelah kiri dikerjakan terlebih dahulu walaupun kedua pengurangan memiliki prioritas yang sama. Kira-kira mengapa, ya?

Apa itu prioritas? Urutan pengerjaan itu apa?

Dalam matematika, urutan pengerjaan adalah kumpulan aturan/konvensi urutan operasi yang dilakukan saat menghitung sebuah kalimat matematika. Prioritas atau urutan pengerjaan suatu operasi juga disebut dengan preseden (precedence). Prioritas yang lebih tinggi berarti akan dikerjakan terlebih dahulu. Begitu juga sebaliknya.

Keberadaan urutan pengerjaan ini digunakan untuk mengurangi ambiguitas, tetapi tetap hemat notasi. Kalau ingin mendahulukan salah satu operasi, kita bisa menggunakan tanda kurung, ( dan ), untuk membungkus operasi yang perlu didahulukan. Sebagai contoh, 7 × (3 - 2) akan menghasilkan 7 (bukan 19). Kalau ada lebih dari satu tingkat kurung, kita bisa menggunakan jenis kurung yang berbeda untuk menghindari kebingungan. Misalnya, [5 × (4 + 2)] - 7.

Urutan pengerjaan konvensional yang diadopsi dalam berbagai bidang, termasuk di luar matematika, adalah sebagai berikut:

1. tanda kurung,
2. perpangkatan dan akar,
3. perkalian dan pembagian, lalu
4. penjumlahan dan pengurangan.

Kalau kita perhatikan, terdapat beberapa operasi yang menempati prioritas yang sama. Bagaimana menentukan yang didahulukan kalau berturutan? Ini yang disebut dengan sifat asosiatif atau keasosiatifan (associativity).

Apa itu asosiatif?

Dalam matematika, sifat asosiatif adalah sifat suatu operator biner (operasi terhadap dua bilangan) yang tidak mengubah hasil ketika tanda kurungnya diubah. Sebagai contoh, (2 + 3) + 5 sama dengan 2 + (3 + 5) sama dengan 10 sehingga operasi penjumlahan bersifat asosiatif.

Yang perlu diperhatikan adalah asosiatif tidak mengubah urutan penulisan operator. Asosiatif berbeda dengan komutatif. Contoh yang umum memang memiliki kedua sifat tersebut sehingga tak jarang disalahpahami oleh kebanyakan orang.

Sifat komutatif adalah sifat operator biner yang tidak mengubah hasil ketika urutan penulisan kedua bilangan yang dikenai operasinya ditukar. Sebagai contoh, 2 + 3 sama dengan 3 + 2 sama dengan 5 sehingga operasi penjumlahan bersifat komutatif.

Memang ada, ya, operasi yang bersifat komutatif, tetapi tidak bersifat asosiatif?

Operasi yang bersifat komutatif, tetapi tidak bersifat asosiatif, memang ada, tetapi memang jarang muncul. Sebagai contoh, operasi batu-gunting-kertas (atau gajah-manusia-semut) memiliki sifat komutatif, tetapi tidak bersifat asosiatif.

• batu vs. gunting = batu
• gunting vs. batu = batu

... tetapi ....

• (batu vs. gunting) vs. kertas = kertas
• batu vs. (gunting vs. kertas) = batu

Jadi, operasi batu-gunting-kertas memiliki sifat komutatif, tetapi tidak bersifat asosiatif.^[1][2] Ini juga alasan permainan batu-gunting-kertas hanya boleh dimainkan oleh tepat dua orang, tidak boleh kurang ataupun lebih.^[3]

Bagaimana dengan operasi non-asosiatif?

Operasi yang tidak memiliki sifat asosiatif memiliki urutan pengerjaan masing-masing. Biasanya, hal ini diatur dengan menentukan suatu operasi sebagai asosiatif kiri atau kanan. Asosiatif kiri adalah mengerjakan dari kiri ke kanan. Asosiatif kanan sebaliknya.

• Asosiatif kiri: 1 ▫ 2 ▫ 3 ▫ 4 = ((1 ▫ 2) ▫ 3) ▫ 4
• Asosiatif kanan: 1 ▪ 2 ▪ 3 ▪ 4 = 1 ▪ (2 ▪ (3 ▪ 4))

Contoh asosiatif kiri adalah pengurangan dan pembagian:

• 1 - 2 - 3 - 4 = ((1 - 2) - 3) - 4
• 1 ÷ 2 ÷ 3 ÷ 4 = ((1 ÷ 2) ÷ 3) ÷ 4

Contoh asosiatif kanan adalah perpangkatan:

• 234 = 2(34)

Namun, ada juga yang wajib menggunakan tanda kurung karena tidak ada konvensinya, misalnya perkalian silang vektor (cross product):

• A̅ × (B̅ × C̅) ≠ (A̅ × B̅) × C̅

Penutup

Dengan mengetahui urutan operasi/preseden dan sifat asosiatif tiap operasi, kita bisa mulai untuk mengubah kalimat matematika dari notasi sisipan ke notasi akhiran untuk kalimat yang lebih kompleks. Selanjutnya, kita coba bahas algoritma shunting yard/depo gerbong, yuk! Semoga bermanfaat!

Catatan akhir

Aku menerapkan konsep dalam tulisanku kali ini untuk menyelesaikan masalah pada program pembuat soal di web TTL. Aku juga menyiarkannya di YouTube, loh!

Notasi Sisipan dan Notasi Akhiran dalam Kalimat Matematika

Pernahkah kalian memperhatikan perbedaan kalkulator dagang dengan kalkulator ilmiah? Bagaimana bisa kalkulator ilmiah menentukan urutan perhitungan? Loh, kalkulator yang di ponsel pintar itu kalkulator ilmiah?

Apa perbedaannya?

Perbedaan keduanya ada pada urutan menghitungnya. Kalkulator dagang memiliki keterbatasan memori dan daya komputasi sehingga perhitungan langsung dilakukan setiap tombol operator berikutnya ditekan (termasuk tanda sama dengan), sedangkan kalkulator ilmiah membaca kalimat matematika (KM) secara keseluruhan, menentukan urutan perhitungan, lalu melakukan perhitungan sesuai urutan seharusnya.

Sebagai contoh, berikut yang muncul ketika menekan tombol 2 + 3 × 7 = pada kalkulator dagang. Perhatikan bahwa perhitungan langsung dijalankan setiap tombol operator ditekan dan nilai itu yang disimpan dalam memorinya yang terbatas.

Tombol yang Ditekan	Hasil pada Layar	Memori Internal	Kalimat Matematika
2	2	0	2
+	2	2	2 +
3	3	2	2 + 3
×	5	5	(2 + 3) ×
7	7	5	(2 + 3) × 7
=	35	35	((2 + 3) × 7)

Bagaimana kalkulator ilmiah menentukan urutan perhitungan?

Sebagai manusia, kita biasanya akan mencari operator yang urutannya didahulukan, misalnya perkalian (×) lebih dahulu daripada penjumlahan (+). Kalimat matematika (KM) yang biasa kita pakai menggunakan notasi sisipan (infix notation), yaitu tanda operator berada di antara dua bilangan/KM yang akan dikenai operasi. Misalnya 2 + 3 berarti operasi penjumlahan antara 2 dan 3 dengan tanda tambah (+) berada di antara keduanya.

Salah satu cara yang lebih mudah bagi komputer adalah dengan menggunakan notasi akhiran (postfix notation atau reverse Polish notation/RPN), yaitu tanda operator berada di akhir dua bilangan/KM yang akan dikenai operasi. Misalnya 2 3 + berarti operasi penjumlahan antara 2 dan 3 dengan tanda tambah (+) berada di akhir/setelah keduanya.

Cara ini lebih mudah untuk diprogram dan dijalankan oleh komputer dengan menggunakan struktur data tumpukan/stack. Kita cukup memasukkan tiap bilangan/KM ke dalam tumpukan. Bila kita bertemu dengan tanda operator, kita ambil dua teratas dari tumpukan lalu melakukan operasi terhadap keduanya. Hasilnya ditaruh di atas tumpukan kembali. Setelah selesai, hasilnya adalah satu bilangan di tumpukan itu.

Sebagai contoh, berikut cara menghitung 2 3 7 × + dengan notasi akhiran. Perhatikan tumpukan setiap kita sampai tanda operator.

Tumpukan	Kursor	Sisa Kalimat
2	2	3 7 × +
3 2	3	7 × +
7 3 2	7	× +
21 2	×	+
23	+

Bagaimana cara mengubah dari notasi sisipan ke notasi akhiran?

Ada beberapa cara untuk mengubahnya. Yang terkenal karena sederhana adalah algoritma shunting yard/depo gerbong karena bisa diilustrasikan dengan depo gerbong. Algoritma ini ditemukan oleh Edsger Wybe Dijkstra dalam artikelnya tahun 1961. Kita bahas lain kali, ya.

Diagram depo gerbong

Eh, kalkulator di ponsel pintar bagaimana?

Oh, iya. Coba saja jalankan 2 + 3 × 7 = pada kalkulator di ponsel pintar kalian. Jawaban yang mana yang muncul?

Penutup

Itu yang bisa kutulis kali ini. Topik ini terpikirkan karena sempat ada masalah pada program pembuat soal di web TTL, khususnya pembuat soal operasi pecahan yang masih menggunakan cara kalkulator dagang dan belum menggunakan cara kalkulator ilmiah. Semoga bermanfaat!

Algoritma LFSR dan Bilangan Acak pada Komputer

Suatu program komputer tidak bisa menghasilkan bilangan acak sejati karena program komputer bersifat deterministik, yaitu hasilnya hanya ditentukan oleh masukannya. Namun, program komputer bisa menerima masukan dari sumber di luar program komputer sehingga bisa mendapatkan bilangan acak sejati dari luar program komputer.

Bagaimana komputer mendapatkan bilangan acak sejati?

Sebagai contoh, prosesor keluarga x86 memiliki perintah khusus untuk mendapatkan bilangan acak sejati, yaitu RDSEED (panduan lebih lanjut: Intel Digital Random Number Generator dan AMD Secure Random Number Generator). Untuk prosesor lain, seperti ARM, sumber bilangan acak sejati didapat dari komponen lain dalam sebuah sistem-pada-cip (system-on-chip/SoC). Ada juga komputer yang memang tidak memiliki perangkat keras untuk mendapatkan bilangan acak sejati. Dengan kata lain, komputer tersebut hanya mengandalkan pengolahan data oleh perangkat lunak untuk mendapatkan bilangan acak, misal dari jam komputer, gerakan tetikus, dan suara mikrofon.

Meski demikian, penghasil bilangan acak sejati ini hanya mampu menghasilkan 16/32/64 bita acak setiap ratusan siklus, bahkan ribuan siklus, karena komponen ini perlu mengumpulkan cukup data agar entropi dari bilangan acak cukup tinggi. Selain itu, tidak ada jaminan bahwa hasil dari RDSEED atau sejenisnya memiliki distribusi yang seragam. Ada kemungkinan nilai yang diperoleh darinya condong (skew) kepada bilangan tertentu.

Penghasil bilangan acak semu (pseudo-random number generator/PRNG) dibuat untuk menjawab masalah tersebut. Selain lebih cepat, algoritma-algoritma PRNG juga bisa diuji secara matematis bahwa distribusinya seragam sehingga hasilnya lebih bagus. Terdapat banyak contoh PRNG, antara lain, Xorshift, Mersenne Twister, linear-feedback shift register (LFSR), linear congruential generator (LCG), dan metode middle-square. Tiap algoritma PRNG memiliki kelebihan dan kekurangan masing-masing. Yang akan dibahas kali ini adalah linear-feedback shift register (LFSR).

Jadi, apa itu LFSR?

Linear-feedback shift register (LFSR) adalah register geser ke kanan yang menggunakan kombinasi linear dari bit-bit terpilih (disebut taps) untuk mengisi bit paling kiri (sebagai feedback). Operasi XOR sering digunakan sebagai operator kombinasi linear sehingga LFSR biasanya tersusun dari operasi geser dan operasi XOR. Hasil dari LFSR adalah untaian bit yang dikeluarkan dari bit paling kanan/bit satuan.

LFSR berukuran n akan melakukan siklus melalui semua kemungkinan dikurangi satu (2ᵐ - 1, nol tidak dihitung), kecuali jika register sejak awal bernilai nol yang berarti akan selalu nol. Sebagai contoh, LFSR 2-bit akan mulai dari 01, ke 10, ke 11, dan kembali ke 01. Namun, bila dimulai dari 00, LFSR tersebut hanya akan menghasilkan 00.

LFSR dengan XOR memiliki dua bentuk: LFSR Fibonacci dan LFSR Galois. Bentuk Fibonacci mengambil XOR dari bit-bit taps untuk mengisi bit paling kiri, sedangkan bit-bit taps dalam bentuk Galois mengambil XOR dari bit sebelah kiri dengan bit keluaran/paling kanan sebelum pergeseran. Keduanya digambarkan oleh ilustrasi di bawah ini. Perhatikan bahwa penomoran bit LFSR Fibonacci dan LFSR Galois terbalik.

Diagram kerja LFSR Fibonacci 4-bit

Diagram kerja LFSR Galois 4-bit

n.b. Pada diagram LFSR Galois, bit paling kiri tidak memiliki gerbang logika XOR karena 0 XOR x akan menghasilkan x pula.

Dari mana kita tahu taps yang sesuai?

Salah satu cara untuk mengetahui taps yang sesuai adalah dengan mencoba kombinasi taps yang mungkin. Namun, untuk mempersempit ruang pencarian, kombinasi taps yang dicari hanyalah yang menggunakan taps berjumlah genap (Ahmad dkk., 1997). Berikut adalah cuplikan tabel taps LFSR Galois yang disusun oleh Ward dan Molteno (2012).

n	Jumlah kombinasi	Bit-bit taps
2	3	2 dan 1
3	7	3 dan 2
4	15	4 dan 3
8	255	8, 6, 5, dan 4
16	65.535	16, 14, 13, dan 11
32	±4,3 miliar	32, 30, 26, dan 25
64	±18 kuintiliun	64, 63, 61, dan 60

Bagaimana langkah-langkah pengerjaannya?

Sebagai contoh, kita akan melakukan LFSR Fibonacci 3-bit dengan taps bit ke-2 dan bit ke-3 serta nilai register awal 001. Untuk tiap iterasi, bit-bit register digeser ke kanan, lalu bit ke-1 adalah hasil XOR dari bit ke-2 dan bit ke-3 sebelum pergeseran.

Bit ke-			Keterangan
1	2	3
0	0	1	(nilai register awal)
1	0	0	0 XOR 1 = 1
0	1	0	0 XOR 0 = 0
1	0	1	1 XOR 0 = 0
1	1	0	0 XOR 1 = 1
1	1	1	1 XOR 0 = 1
0	1	1	1 XOR 1 = 0
0	0	1	1 XOR 1 = 0 (kembali ke awal)

LFSR tersebut menghasilkan untaian 7 bit 1001011 berulang. Untaian bit tersebut cukup "acak". Untuk lebih acak, kita bisa menggunakan ukuran register yang lebih besar agak untaian bit lebih panjang sebelum akhirnya berulang lagi.

Bonus: Contoh Program

register = 1
for i in range(8):
	print(f"{register:03b} -- {(register & 1):01b}")
	bit_baru = (register ^ (register >> 1)) & 1
	register = (register >> 1) | (bit_baru << 2)

Hasil keluaran

001 -- 1
100 -- 0
010 -- 0
101 -- 1
110 -- 0
111 -- 1
011 -- 1
001 -- 1

Cara mendapatkan bit baru (paling kiri) cukup dengan menghitung XOR dari register dan register >> 1 (yang sudah digeser ke kanan sekali), lalu mengambil AND darinya dengan 1 (mengambil bit satuan). Hal tersebut sama dengan melakukan XOR bit terakhir (bit ke-3) dengan bit kedua terakhir (bit ke-2).

Penutup

Itu yang bisa kutulis kali ini. Topik LFSR ini mendadak terpikirkan saat aku mencari ide untuk menulis di blogku ini. Ada dua video yang cocok sebagai pengayaan dari tulisanku ini, sekaligus menjadi inspirasiku dalam menulis pos ini, yaitu "True Random Numbers" dan "Random Numbers with LFSR" yang keduanya dari saluran YouTube Computerphile. Semoga bermanfaat!

Jaringan Substitusi-Permutasi

Pada pembahasan kali ini, kita beralih dari penyandian teks menjadi penyandian untaian bita secara umum. Karena komputer melihat data sebagai untaian bita-bita, penyandian untaian bita secara umum memampukan kita untuk melakukan penyandian data apa pun, seperti gambar, suara, video, dan dokumen jenis apa pun.

Sandi substitusi dan sandi transposisi (khususnya permutasi) dapat digabungkan menjadi suatu jaringan yang disebut sebagai jaringan substitusi-permutasi (SP). Jaringan SP terdiri atas operasi substitusi (biasa disebut sebagai kotak-S) dan operasi permutasi (kotak-P) yang disusun secara bergantian dan diulang beberapa kali. Jumlah pengulangan SP biasa disebut sebagai jumlah ronde.

Seperti penyandian pada umumnya, jaringan SP mengubah teks pesan menjadi teks tersandi dengan kunci yang diberikan. Untuk mengembalikan teks pesan, teks tersandi dimasukkan ke dalam inversi jaringan SP, yaitu sama dengan jaringan SP, tetapi urutan operasinya dibalik. Sebagai contoh, jaringan K-S-P-K-S-P-K memiliki inversi sebagai berikut: K-P-S-K-P-S-K. K adalah operasi penambahan kunci ke dalam teks.

Komponen Jaringan SP

Kotak-S berisi daftar konversi dari satu bita ke bita lain atau satu untaian bit ke untaian bit lain. Hal ini seperti konversi A menjadi B, lalu B menjadi K, dan seterusnya. Hal ini menyebabkan nilai-nilai bita hasil konversi tidak lagi memiliki hubungan linear terhadap nilai-nilai bita masukan.

Kotak-P berisi cara memetakan suatu bit dalam suatu bita ke bit lain dalam bita lain. Sebagai contoh, dari masukan 8 bita, bit ke-5 dalam bita ke-2 dipetakan ke bit ke-7 dalam bita ke-5. Hal ini menyebabkan susunan bit tidak lagi sama dengan sebelumnya sehingga relasi antara teks pesan dan teks tersandi menjadi sulit dimengerti.

Sebelum, setelah, dan di antara operasi substitusi dan permutasi, terdapat operasi penambahan kunci ke dalam teks. Namun, kunci yang digunakan berbeda-beda untuk tiap ronde, padahal hanya ada satu kunci yang diberikan. Caranya adalah penjadwalan kunci.

Penjadwalan kunci adalah cara untuk mendapatkan nilai kunci yang berbeda-beda untuk tiap ronde berdasarkan satu kunci yang diberikan. Terdapat beberapa cara untuk melakukannya, misalnya TEA membagi kunci 128 bit menjadi empat kunci 32 bit yang digunakan bergantian atau AES memiliki prosedur yang lebih kompleks untuk menjadwalkan kunci.

Contoh Kasus

Sebagai contoh, kita akan menyandikan pesan C5 37 2B 9F dengan menggunakan struktur K-S-P-K-S-P-K dan ukuran masukan empat bita. Selain itu, kunci yang diberikan juga empat bita: 58 65 9F DD.

Spesifikasi Jaringan SP

Berikut adalah nilai kotak-S yang digunakan dalam AES:

	_0	_1	_2	_3	_4	_5	_6	_7	_8	_9	_A	_B	_C	_D	_E	_F
0_	63	7C	77	7B	F2	6B	6F	C5	30	01	67	2B	FE	D7	AB	76
1_	CA	82	C9	7D	FA	59	47	F0	AD	D4	A2	AF	9C	A4	72	C0
2_	B7	FD	93	26	36	3F	F7	CC	34	A5	E5	F1	71	D8	31	15
3_	04	C7	23	C3	18	96	05	9A	07	12	80	E2	EB	27	B2	75
4_	09	83	2C	1A	1B	6E	5A	A0	52	3B	D6	B3	29	E3	2F	84
5_	53	D1	00	ED	20	FC	B1	5B	6A	CB	BE	39	4A	4C	58	CF
6_	D0	EF	AA	FB	43	4D	33	85	45	F9	02	7F	50	3C	9F	A8
7_	51	A3	40	8F	92	9D	38	F5	BC	B6	DA	21	10	FF	F3	D2
8_	CD	0C	13	EC	5F	97	44	17	C4	A7	7E	3D	64	5D	19	73
9_	60	81	4F	DC	22	2A	90	88	46	EE	B8	14	DE	5E	0B	DB
A_	E0	32	3A	0A	49	06	24	5C	C2	D3	AC	62	91	95	E4	79
B_	E7	C8	37	6D	8D	D5	4E	A9	6C	56	F4	EA	65	7A	AE	08
C_	BA	78	25	2E	1C	A6	B4	C6	E8	DD	74	1F	4B	BD	8B	8A
D_	70	3E	B5	66	48	03	F6	0E	61	35	57	B9	86	C1	1D	9E
E_	E1	F8	98	11	69	D9	8E	94	9B	1E	87	E9	CE	55	28	DF
F_	8C	A1	89	0D	BF	E6	42	68	41	99	2D	0F	B0	54	BB	16

Untuk kasus ini, kita bisa membuat kotak-P agar menukar satu bita dengan bita sebelahnya. Sebagai contoh, empat bit pertama dari bita ke-1 ditukar dengan empat bit kedua dari bita ke-2, empat bit pertama dari bita ke-3 ditukar dengan empat bit kedua dari bita ke-4, dan seterusnya.

Operasi penambahan kunci hanya melakukan XOR dengan kunci. Selain itu, penjadwalan kunci yang akan kita gunakan sederhana, yaitu hanya melakukan geseran melingkar ke kiri (<<<) sebanyak satu bita untuk tiap ronde.

Perhitungan

Perhitungan dari kasus di atas ditunjukkan dalam tabel berikut:

Operasi	Teks				Kunci
Keadaan awal	C5	37	2B	9F	58	65	9F	DD
Penambahan kunci	9D	52	B4	42	58	65	9F	DD
Substitusi	5E	00	8D	2C	<<<
Permutasi	0E	05	CD	28
Penambahan kunci	6B	9A	10	70	65	9F	DD	58
Substitusi	7F	B8	CA	51	<<<
Permutasi	8F	B7	1A	5C
Penambahan kunci	10	6A	42	39	9F	DD	58	65

Hasil penyandiannya adalah 10 6A 42 39.

Bonus: Program C

Program C

#include <stdio.h>
#include <stdint.h>

#define UKURAN 4

void penambahanKunci(uint8_t *A, const uint8_t *kunci) { // K
	for (int i = 0; i < UKURAN; i ++)
		A[i] ^= kunci[i];
}

void substitusi(uint8_t *A, const uint8_t *kotakS) { // S
	for (int i = 0; i < UKURAN; i ++)
		A[i] = kotakS[A[i]];
}

void permutasi(uint8_t *A) { // P
	for (int i = 0; i < UKURAN; i += 2) {
		uint8_t lawas1 = A[i + 0];
		uint8_t lawas2 = A[i + 1];
		A[i + 0] = lawas1 & 0x0F | (lawas2 << 4) & 0xF0;
		A[i + 1] = lawas2 & 0xF0 | (lawas1 >> 4);
	}
}

void geserKunci(uint8_t *kunci) { // <<<
	uint8_t k = kunci[0];
	for (int i = 0; i < UKURAN - 1; i ++)
		kunci[i] = kunci[i + 1];
	kunci[UKURAN - 1] = k;
}

void jaringanSP(uint8_t *pesan, uint8_t *kunci, const uint8_t *kotakS) {
	penambahanKunci(pesan, kunci); // K
	substitusi(pesan, kotakS);     // S
	permutasi(pesan);              // P
	geserKunci(kunci);             // <<<
	penambahanKunci(pesan, kunci); // K
	substitusi(pesan, kotakS);     // S
	permutasi(pesan);              // P
	geserKunci(kunci);             // <<<
	penambahanKunci(pesan, kunci); // K
}

int main() {
	uint8_t pesan[] = {0xC5, 0x37, 0x2B, 0x9F};
	uint8_t kunci[] = {0x58, 0x65, 0x9F, 0xDD};
	uint8_t kotakS[256] = {};
	// https://id.wikipedia.org/wiki/Kotak-S_Rijndael
	initialize_aes_sbox(kotakS);
	jaringanSP(pesan, kunci, kotakS);
	printf("%X %X %X %X\n", pesan[0], pesan[1], pesan[2], pesan[3]);
	return 0;
}

Prinsip Shannon

Jaringan SP memenuhi prinsip pengacakan dan penghamburan Shannon.

• Pengacakan: Bila salah satu bit teks pesan diubah, hasil dari kotak-S akan jauh berbeda yang kemudian akan makin tersebar oleh kotak-P. Hal ini berulang dalam beberapa ronde. Hasilnya adalah teks tersandi sulit untuk ditebak hanya dengan perubahan kecil.
• Penghamburan: Bila salah satu bit kunci diubah, kunci ronde disebar ke seluruh/potongan teks sehingga perubahan teks tersandi sulit dilacak.

Penutup

Sekian dahulu tulisanku kali ini. Aku sudah ingin membahas ini sejak lama, terutama bagian menulis kode programnya, tetapi menunggu tulisan pembahasan sandi substitusi dan sandi transposisi selesai agar pembahasannya runtut. Semoga bermanfaat!

Soal-Soal Konsep Pemrograman Gambar Bentuk

Beberapa hari lalu, ada yang mengetwit tentang contoh soal konsep pemrograman. Konsep yang diuji sederhana, sih, yaitu percabangan dan perulangan. Soal-soal sejenis ini juga biasa muncul dalam mata kuliah Konsep Pemrograman.

Betul, soal-soal yang kumaksud adalah membuat program yang mencetak bentuk-bentuk tertentu menggunakan teks (seperti seni ASCII). Ada yang berbentuk segitiga, persegi, jajaran genjang, belah ketupat, dan jam pasir. Ada yang terisi penuh; ada yang hanya bingkai/garis tepinya. Ada yang hanya teks, ada yang berisi urutan bilangan tertentu.

Enam Belas Soal Gambar Bentuk

Ada enam belas soal. Berikut daftarnya:

Daftar Enam Belas Soal Gambar Bentuk

Nama	Target Hasil
Segitiga Kiri Bawah	* * * * * * * * * * * * * * *
Segitiga Kanan Bawah	* * * * * * * * * * * * * * *
Segitiga Sama Sisi	* * * * * * * * * * * * * * *
Segitiga Kiri Atas	* * * * * * * * * * * * * * *
Segitiga Kanan Atas	* * * * * * * * * * * * * * *
Segitiga Sama Sisi Terbalik	* * * * * * * * * * * * * * *
Jajaran Genjang	* * * * * * * * * * * * * * * * * * * *
Belah Ketupat	* * * * * * * * * * * * * * * *
Jam Pasir	* * * * * * * * * * * * * * * * * * *
Bingkai Persegi	* * * * * * * * * * * * * * * *
Bingkai Segitiga Sama Sisi	* * * * * * * * * * * *
Bintang Segitiga Sama Sisi Terbalik	* * * * * * * * * * * *
Bingkai Belah Ketupat	* * * * * * * * * * * *
Bingkai Jam Pasir	* * * * * * * * * * * * * * * * *
Segitiga Floyd	1 2 3 4 5 6 7 8 9 10
Segitiga Pascal	1 1 1 1 2 1 1 3 3 1

Kita bahas satu-satu, ya. Perlu diingat bahwa pembahasan berikut menganggap bahwa spasi pada akhir baris berpengaruh sehingga tidak boleh ada.

Tiap soal akan dijawab dengan dua bahasa pemrograman, yaitu bahasa Python dan C. Khusus bahasa C, berikut ada fungsi pembantu untuk memudahkan dalam menulis kode.

void cetak_ulang(char teks[], int jumlah) {
	for (int i = 0; i < jumlah; i ++)
		printf(teks);
}

Oh, iya. Kode-kode program berikut kutulis dalam sehari. Jadi, mungkin ada cara yang lebih efektif/optimal untuk membuat bentuk yang diminta.

Segitiga Kiri Bawah

*
* *
* * *
* * * *
* * * * *

Ini bentuk paling sederhana. Kita cukup membuat perulangan dua tingkat: satu untuk baris dan satu lagi untuk kolom. Kalau spasi pada akhir baris tidak dianggap, kita cukup mengulang teks "* ". Namun, karena itu berpengaruh, kita ubah menjadi cetak "*" sekali, lalu cetak " *" untuk sisanya.

Jawaban

Python

def segitiga_kiri_bawah(ukuran):
	for i in range(1, ukuran + 1):
		print('*' + ' *' * (i - 1))

C

void segitiga_kiri_bawah(int ukuran) {
	for (int i = 1; i <= ukuran; i ++) {
		printf("*");
		cetak_ulang(" *", i - 1);
		printf("\n");
	}
}

Segitiga Kanan Bawah

        *
      * *
    * * *
  * * * *
* * * * *

Bentuk ini mirip dengan sebelumnya, tetapi perlu ditambah spasi sebelum mulai mencetak tiap barisnya. Jumlah spasi berbanding terbalik dengan nomor baris (dari 2 × [nomor baris - 1] sampai 0). Cara lainnya adalah dengan mengulang cetak 2 spasi (" ") sebanyak (nomor baris - 1) sehingga tidak perlu ada kali 2 pada jumlah pengulangannya.

Jawaban

Python

def segitiga_kanan_bawah(ukuran):
	for i in range(1, ukuran + 1):
		print('  ' * (ukuran - i) + '*' + ' *' * (i - 1))

C

void segitiga_kanan_bawah(int ukuran) {
	for (int i = 1; i <= ukuran; i ++) {
		cetak_ulang("  ", ukuran - i);
		printf("*");
		cetak_ulang(" *", i - 1);
		printf("\n");
	}
}

Segitiga Sama Sisi

    *
   * *
  * * *
 * * * *
* * * * *

Ini mirip dengan sebelumnya, tetapi jumlah spasinya tidak perlu dikali dua sehingga hanya setengah dari yang sebelumnya. Yang sebelumnya pakai 2 spasi cukup mengubahyna menjadi 1 karakter spasi.

Jawaban

Python

def segitiga_sama_sisi(ukuran):
	for i in range(1, ukuran + 1):
		print(' ' * (ukuran - i) + '*' + ' *' * (i - 1))

C

void segitiga_sama_sisi(int ukuran) {
	for (int i = 1; i <= ukuran; i ++) {
		cetak_ulang(" ", ukuran - i);
		printf("*");
		cetak_ulang(" *", i - 1);
		printf("\n");
	}
}

Segitiga Kiri Atas

* * * * *
* * * *
* * *
* *
*

Soal ini mirip dengan soal Segitiga Kiri Bawah, tetapi urutan barisnya dibalik. Membaliknya bisa dengan mengubah urutan nilai i pada perulangan baris.

Jawaban

Python

def segitiga_kiri_atas(ukuran):
	for i in range(ukuran, 0, -1):
		print('*' + ' *' * (i - 1))

C

void segitiga_kiri_atas(int ukuran) {
	for (int i = ukuran; i > 0; i --) {
		printf("*");
		cetak_ulang(" *", i - 1);
		printf("\n");
	}
}

Segitiga Kanan Atas

* * * * *
  * * * *
    * * *
      * *
        *

Yang ini juga mirip dengan sebelumnya. Kita cukup mengubah urutan baris dari Segitiga Kanan Bawah.

Jawaban

Python

def segitiga_kanan_atas(ukuran):
	for i in range(ukuran, 0, -1):
		print('  ' * (ukuran - i) + '*' + ' *' * (i - 1))

C

void segitiga_kanan_atas(int ukuran) {
	for (int i = ukuran; i > 0; i --) {
		cetak_ulang("  ", ukuran - i);
		printf("*");
		cetak_ulang(" *", i - 1);
		printf("\n");
	}
}

Segitiga Sama Sisi Terbalik

* * * * *
 * * * *
  * * *
   * *
    *

Ini masih sama, ya. Kita cukup mengubah urutan baris dari Segitiga Sama Sisi.

Jawaban

Python

def segitiga_sama_sisi_terbalik(ukuran):
	for i in range(ukuran, 0, -1):
		print(' ' * (ukuran - i) + '*' + ' *' * (i - 1))

C

void segitiga_sama_sisi_terbalik(int ukuran) {
	for (int i = ukuran; i > 0; i --) {
		cetak_ulang(" ", ukuran - i);
		printf("*");
		cetak_ulang(" *", i - 1);
		printf("\n");
	}
}

Jajaran Genjang

* * * *
 * * * *
  * * * *
   * * * *
    * * * *

Untuk membuat jajaran genjang, kita bisa mulai dengan membuat persegi panjang. Kita perlu dua perulangan: tingkat pertama untuk baris (dari 0 sampai tinggi) dan tingkat kedua untuk kolom (dari 0 sampai alas). Sebelum mencetak tiap baris, kita perlu mencetak spasi sebanyak 2 × (nomor baris - 1).

Jawaban

Python

def jajaran_genjang(alas, tinggi):
	if alas <= 0:
		return
	for i in range(tinggi):
		print(' ' * i + '*' + ' *' * (alas - 1))

C

void jajaran_genjang(int alas, int tinggi) {
	if (alas <= 0)
		return;
	for (int i = 0; i < tinggi; i ++) {
		cetak_ulang(" ", i);
		printf("*");
		cetak_ulang(" *", alas - 1);
		printf("\n");
	}
}

Belah Ketupat

   *
  * *
 * * *
* * * *
 * * *
  * *
   *

Belah ketupat bisa dibagi menjadi dua segitiga. Segitiga yang di atas sama dengan Segitiga Sama Sisi. Segitiga yang di bawah sama dengan Segitiga Sama Sisi Terbalik. Salah satunya dikurangi satu baris agar tidak ada baris ganda di tengah.

Jawaban

Python

def belah_ketupat(sisi):
	if sisi <= 0:
		return
	for i in range(1, sisi):
		print(' ' * (sisi - i) + '*' + ' *' * (i - 1))
	for i in range(sisi, 0, -1):
		print(' ' * (sisi - i) + '*' + ' *' * (i - 1))

C

void belah_ketupat(int sisi) {
	for (int i = 1; i < sisi; i ++) {
		cetak_ulang(" ", sisi - i);
		printf("*");
		cetak_ulang(" *", i - 1);
		printf("\n");
	}
	for (int i = sisi; i > 0; i --) {
		cetak_ulang(" ", sisi - i);
		printf("*");
		cetak_ulang(" *", i - 1);
		printf("\n");
	}
}

Jam Pasir

* * * *
 * * *
  * *
   *
  * *
 * * *
* * * *

Bentuk ini kebalikan dari Belah Ketupat. Segitiga yang di atas sama dengan Segitiga Sama Sisi Terbalik (!). Segitiga yang di bawah sama dengan Segitiga Sama Sisi. Jangan lupa bahwa salah satunya dikurangi satu baris agar tidak ada baris ganda di tengah.

Jawaban

Python

def jam_pasir(sisi):
	for i in range(sisi, 1, -1):
		print(' ' * (sisi - i) + '*' + ' *' * (i - 1))
	for i in range(1, sisi + 1):
		print(' ' * (sisi - i) + '*' + ' *' * (i - 1))

C

void jam_pasir(int sisi) {
	for (int i = sisi; i > 1; i --) {
		cetak_ulang(" ", sisi - i);
		printf("*");
		cetak_ulang(" *", i - 1);
		printf("\n");
	}
	for (int i = 1; i <= sisi; i ++) {
		cetak_ulang(" ", sisi - i);
		printf("*");
		cetak_ulang(" *", i - 1);
		printf("\n");
	}
}

Bingkai Persegi

* * * * *
*       *
*       *
*       *
* * * * *

Bentuk ini dibuat dalam tiga tahap. Pertama, cetak sisi atas. Kedua, cetak sisi kiri dan kanan secara berulang. Ketiga, cetak sisi bawah.

Jawaban

Python

def bingkai_persegi(sisi):
	if sisi > 0:
		print('*' + ' *' * (sisi - 1))
	for i in range(sisi - 2):
		print('*' + '  ' * (sisi - 2) + ' *')
	if sisi > 1:
		print('*' + ' *' * (sisi - 1))

C

void bingkai_persegi(int sisi) {
	if (sisi > 0) {
		printf("*");
		cetak_ulang(" *", sisi - 1);
		printf("\n");
	}
	for (int i = 1; i < sisi - 1; i ++) {
		printf("*");
		cetak_ulang("  ", sisi - 2);
		printf(" *");
		printf("\n");
	}
	if (sisi > 1) {
		printf("*");
		cetak_ulang(" *", sisi - 1);
		printf("\n");
	}
}

Bingkai Segitiga Sama Sisi

    *
   * *
  *   *
 *     *
* * * * *

Bentuk ini adalah versi bingkai dari Segitiga Sama Sisi. Untuk bagian tengah, yang tadinya cetak karakter bintang berulang itu diubah menjadi hanya cetak karakter bintang pada sisi kiri dan sisi kanan.

Jawaban

Python

def bingkai_segitiga_sama_sisi(ukuran):
	for i in range(1, ukuran + 1):
		print(' ' * (ukuran - i), end='*')
		if i == ukuran:
			print(' *' * (i - 1))
		else:
			print('  ' * (i - 2) + ' *' if i > 1 else '')

C

void bingkai_segitiga_sama_sisi(int ukuran) {
	for (int i = 1; i <= ukuran; i ++) {
		cetak_ulang(" ", ukuran - i);
		printf("*");
		if (i == ukuran)
			cetak_ulang(" *", i - 2);
		else
			cetak_ulang("  ", i - 2);
		if (i > 1)
			printf(" *");
		printf("\n");
	}
}

Bintang Segitiga Sama Sisi Terbalik

* * * * *
 *     *
  *   *
   * *
    *

Yang ini juga sama dengan sebelumnya, tetapi untuk versi yang terbalik.

Jawaban

Python

def bingkai_segitiga_sama_sisi_terbalik(ukuran):
	for i in range(ukuran, 0, -1):
		print(' ' * (ukuran - i), end='*')
		if i == ukuran:
			print(' *' * (i - 1))
		else:
			print('  ' * (i - 2) + ' *' if i > 1 else '')

C

void bingkai_segitiga_sama_sisi_terbalik(int ukuran) {
	for (int i = ukuran; i > 0; i --) {
		cetak_ulang(" ", ukuran - i);
		printf("*");
		if (i == ukuran)
			cetak_ulang(" *", i - 2);
		else
			cetak_ulang("  ", i - 2);
		if (i > 1)
			printf(" *");
		printf("\n");
	}
}

Bingkai Belah Ketupat

   *
  * *
 *   *
*     *
 *   *
  * *
   *

Bentuk ini gabungan dari dua bingkai segitiga sebelumnya.

Jawaban

Python

def bingkai_belah_ketupat(sisi):
	if sisi <= 0:
		return
	for i in range(1, sisi):
		print(' ' * (sisi - i), end='*')
		print('  ' * (i - 2) + ' *' if i > 1 else '')
	for i in range(sisi, 0, -1):
		print(' ' * (sisi - i), end='*')
		print('  ' * (i - 2) + ' *' if i > 1 else '')

C

void bingkai_belah_ketupat(int sisi) {
	if (sisi <= 0)
		return;
	for (int i = 1; i < sisi; i ++) {
		cetak_ulang(" ", sisi - i);
		printf("*");
		cetak_ulang("  ", i - 2);
		if (i > 1)
			printf(" *");
		printf("\n");
	}
	for (int i = sisi; i > 0; i --) {
		cetak_ulang(" ", sisi - i);
		printf("*");
		cetak_ulang("  ", i - 2);
		if (i > 1)
			printf(" *");
		printf("\n");
	}
}

Bingkai Jam Pasir

* * * *
 *   *
  * *
   *
  * *
 *   *
* * * *

Untuk yang ini, kita membalik segitiga seperti sebelumnya.

Jawaban

Python

def bingkai_jam_pasir(sisi):
	for i in range(sisi, 1, -1):
		print(' ' * (sisi - i), end='*')
		if i == sisi:
			print(' *' * (i - 1))
		else:
			print('  ' * (i - 2) + ' *' if i > 1 else '')
	for i in range(1, sisi + 1):
		print(' ' * (sisi - i), end='*')
		if i == sisi:
			print(' *' * (i - 1))
		else:
			print('  ' * (i - 2) + ' *' if i > 1 else '')

C

void bingkai_jam_pasir(int sisi) {
	for (int i = sisi; i > 1; i --) {
		cetak_ulang(" ", sisi - i);
		printf("*");
		if (i == sisi)
			cetak_ulang(" *", i - 2);
		else
			cetak_ulang("  ", i - 2);
		if (i > 1)
			printf(" *");
		printf("\n");
	}
	for (int i = 1; i <= sisi; i ++) {
		cetak_ulang(" ", sisi - i);
		printf("*");
		if (i == sisi)
			cetak_ulang(" *", i - 2);
		else
			cetak_ulang("  ", i - 2);
		if (i > 1)
			printf(" *");
		printf("\n");
	}
}

Segitiga Floyd

1
2 3
4 5 6
7 8 9 10

Segitiga Floyd pada dasarnya memiliki bentuk yang sama dengan Segitiga Kiri Bawah, tetapi karakter bintang diganti dengan bilangan berurutan yang dimulai dari satu.

Jawaban

Python

def segitiga_Floyd(ukuran):
	k = 1
	for i in range(ukuran):
		for j in range(i + 1):
			print(str(k) + (' ' if j < i else ''), end='')
			k += 1
		print()

C

void segitiga_Floyd(int ukuran) {
	int k = 1;
	for (int i = 1; i <= ukuran; i ++) {
		printf("%d", k ++);
		for (int j = 1; j < i; j ++)
			printf(" %d", k ++);
		printf("\n");
	}
}

Segitiga Pascal

   1
  1 1
 1 2 1
1 3 3 1

Segitiga Pascal adalah segitiga yang baris selanjutnya adalah penjumlahan dua bilangan di kiri-atas dan kanan-atas-nya. Untuk mencetaknya, kita bisa menggunakan pola yang sama dengan Segitiga Sama Sisi. Untuk menentukan bilangan yang akan dicetak, kita perlu menghitung per baris.

Karena jumlah bilangan per baris sama dengan nomor baris, kita cukup menyiapkan sebuah larik (array) yang berisi nilai 0 sebanyak jumlah baris. Kemudian, bilangan pertama diatur menjadi 1. Untuk menghitung baris selanjutnya, kita bisa mulai dari bilangan ke-2 yang merupakan penjumlahan dari bilangan ke-1 dan bilangan ke-2 pada baris sebelumnya. Begitu pula seterusnya dengan pola bilangan ke-n baris baru = bilangan ke-(n-1) baris sebelumnya + bilangan ke-n baris sebelumnya. Kita memulai dari bilangan ke-2 karena bilangan ke-1 tidak pernah berubah, yaitu selalu 1.

Jawaban

Python

def segitiga_Pascal(ukuran):
	if ukuran <= 0:
		return
	nilai = [0] * ukuran
	nilai_baru = [0] * ukuran
	nilai[0] = 1
	nilai_baru[0] = 1
	for i in range(1, ukuran + 1):
		print(' ' * (ukuran - i), end='')
		print(nilai[0], end='')
		for j in range(1, i):
			print(' ' + str(nilai[j]), end='')
		print()
		for k in range(1, ukuran):
			nilai_baru[k] = nilai[k - 1] + nilai[k]
		nilai = nilai_baru.copy()

C

void segitiga_Pascal(int ukuran) {
	if (ukuran <= 0)
		return;
	int nilai[ukuran];
	int nilai_baru[ukuran];
	nilai[0] = 1;
	nilai_baru[0] = 1;
	for (int i = 1; i < ukuran; i ++) {
		nilai[i] = 0;
		nilai_baru[i] = 0;
	}
	for (int i = 1; i <= ukuran; i ++) {
		cetak_ulang(" ", ukuran - i);
		printf("%d", nilai[0]);
		for (int j = 1; j < i; j ++)
			printf(" %d", nilai[j]);
		printf("\n");
		for (int j = 1; j < ukuran; j ++)
			nilai_baru[j] = nilai[j - 1] + nilai[j];
		for (int j = 0; j < ukuran; j ++)
			nilai[j] = nilai_baru[j];
	}
}

Penutup

Sekian dahulu yang bisa kutulis. Buatku, ini latihan sekaligus mengenang masa-masa ketika aku belajar konsep pemrograman. Kalau ada masukan, jangan sungkan untuk tinggalkan komentar, ya. Semoga bermanfaat!