Quotes Today : Bapak

بسم الله الرحمن الرحيم

Sebodoh apapun kamu jangan pernah menyesal sama pilihanmu. Rampok yang jelas-jelas salah aja nggak pernah menyesal ngerampok masa kamu nyesel

-bapak, diterjemahkan dan diedit seperlunya-

Aku

بسم الله الرحمن الرحيم

Ini loh hikmahnya kita ngga diberi tahu masa depan. Biar kalo kita usaha ga itung-itungan. Maksimalkan aja apa yang bisa. Gausah liat orang lain. Nasib tiap orang beda. Toh ya kalo rejekimu ga bakal kemana-mana kan 

-anonymous

The Power of Data

بسم الله الرحمن الرحيم

Berbeda dengan TPB, sekarang yang namanya waktu UTS bener-bener ada. Maksudnya jelas bisa dibedakan dengan waktu kuliah biasa

Eh UTS lo kapan?

Masih minggu depan. Selo

Enak banget! Gue besok mulai UTS

Bandingkan dengan TPB yang tiap Sabtunya dipenuhi UTS. Sungguh malang nasibnya.. HAHAHAHA
Sebenernya gak juga sih. Semua baliknya ke manajemen waktu masing-masing

Jadi beberapa minggu ini saya sudah jarang sekali buka CF. Yah selain karena UTS dan kegiatan di kampus juga terhitung banyak, juga karena saya baru dapet mainan baru. Nih

tampilan awal kaggle.com

Kaggle.com. Situs ini mirip Topcoder tapi lebih fokus untuk hal-hal yang berkaitan dengan data mining. 

Apaan tuh data mining?

Sekilas buat yang belum tau, data mining itu bisa dibilang cara mengekstrak informasi dari data. Bisa dibilang data itu bahan mentahnya yang tidak semuanya bisa kita pakai, sedangkan informasi itu hasil matangnya yang bisa langsung dipakai.

Contoh rilnya, kita punya data tinggi badan semua mahasiswa ITB 2013. Data-data itu tidak mungkin kita pergunakan semuanya. Tapi kita bisa mencari tinggi badan rata-ratanya, sebaran tinggi badan, standar deviasi, bahkan hubungan tinggi badan dengan tingkat pendapatan keluarga jika kita punya data penghasilan orang tua juga. Kurang lebih itu yang data mining. Tertarik? Masih ada yang lebih seru. Akan saya tunjukkan salah satu "game" dalam situs ini. 

Pembaca pasti tidak asing dengan kapal Titanic. Jadi dalam "game" ini kita akan bermain-main seputar kapal Titanic dan penumpangnya. Kita diberikan sejumlah data orang yang ditemukan selamat dan tidak. Nama, asal, jenis kelamin, umur, jumlah anggota keluarga, nomor tiket, kelas kabin (kelas I, II, III), terminal keberangkatan, dan lain-lain yang akan kita butuhkan dalam induksi. Kita juga tahu orang tersebut selamat (hidup) atau ditemukan tewas. Lalu tugas kita sekarang adalah diberikan sisa data-data orang-orang yang hilang (persis seperti sebelumnya kecuali status selamat tidaknya), kita akan mencari tahu apakah orang tersebut kira-kira masih hidup atau tidak. Masih tidak tertarik?

Memang kebutuhan manusia akan informasi segitu besarnya apalagi di jaman sekarang. Hanya dengan informasi, kita bisa mengendalikan suatu negara. Bahkan orang yang punya resource melimpah sekalipun tidak bisa apa-apa jika dia tidak memiliki informasi cukup tentang resource yang dimiliki. Apalagi di era sekarang, ketika informasi banyak bertebaran. Kalau kita tidak update informasi, kita akan tertinggal jauh. 

Oiya, bidang data science ini juga bisa dibilang sepupunya machine learning dan artificial intelligence (AI). Karena itu saya tertarik untuk bermain disini heheh :)

Selain diisi problemset, dalam kaggle juga ada forum, tutorial, dan job. Bener-bener tempatnya orang-orang AI berkumpul. Jadi selain bisa mengasah skill kita, kita juga bisa mengikuti perkembangan terbaru AI dan bertukar ide di forum. Juga ada informasi tentang job dan internship bagi yang berminat. 

Sekian. Semoga bermanfaat :)

Jadul

بسم الله الرحمن الرحيم

"Witing trisna jalaran saka kulina"

Kurang lebih artinya, "datangnya cinta berawal dari kebiasaan". Inilah pepatah Jawa yang sering sekali kita dengar dari orang tua, guru, masyarakat, media, atau bahkan buku-buku bacaan. Tapi jangan remehkan pepatah ini. Bisa jadi pepatah ini ada benarnya.

Kalau kita tidak suka mengajar, bisa jadi karena kita tidak pernah merasakan asiknya mengajar anak-anak.

Kalau kita tidak suka berbuat baik pada orang, bisa jadi memang kita tidak pernah berbuat baik pada orang yang kita temui.

Begitupun kalau kita merasa malas shalat di masjid ataupun membaca Qur'an. Mungkin selama ini kita tidak pernah meluangkan waktu untuk shalat jamaah maupun tilawah. Mungkin kita terlalu sibuk mengurus kuliah/sekolah, pekerjaan, unit/ekskul, organisasi, dan sebajek aktivitas lainnya.

Mulailah membiasakan diri. Pasang target rutin yang harus dilakukan tiap hari. Sedikit dulu saja. Kalau sudah konsisten baru tambah target lagi. Begitu terus sampai kita bisa semua menikmati kegiatan-kegiatan positif itu.

Begitupun ... err ... tentang memilih jodoh #eaa. Mereka yang langgeng sampai akhir hayatnya bukan cuma karena memang mereka jodoh - walaupun sebenarnya iya itu takdir. Tapi mereka menikmati proses berkeluarga karena memang mereka sudah terbiasa. Witing trisna jalaran saka kulina. Mereka memilih, lalu meyakini bahwa itu jodoh terbaik mereka dan teguh dalam komitmen mereka.

Ya, menjaga komitmen. 

About Fibonacci : Identitas Fibonacci - part 4

بسم الله الرحمن الرحيم

Setelah sekian lama tidak berjumpa dengan pembaca setia -kalau ada-, kali ini saya menemukan persoalan menarik tentang fibonacci. Saya tidak akan bahas persoalan sebenarnya (yang mana mungkin jauh lebih susah dari topik yang akan ditulis) tapi akan saya fokuskan ke identitas barisan Fibonacci yang lain. Selamat membaca :)

Review

Di pos sebelumnya tentang fibonacci kita sudah dapat menyatakan fibonacci dalam matriks berpangkat, yaitu

\[ \left( \begin{array}{cc} F_{n+1} & F_n \\ F_n & F_{n-1} \end{array}\right) = \left( \begin{array}{cc} 1 & 1 \\ 1 & 0 \end{array}\right)^n \]

Coba jika kita pecah menjadi dua buah matriks berpangkat

\[ \left( \begin{array}{cc} 1 & 1 \\ 1 & 0 \end{array}\right)^n = \left( \begin{array}{cc} 1 & 1 \\ 1 & 0 \end{array}\right)^k \left( \begin{array}{cc} 1 & 1 \\ 1 & 0 \end{array}\right)^{n-k} \]
\[ \left( \begin{array}{cc} F_{n+1} & F_n \\ F_n & F_{n-1} \end{array}\right) = \left( \begin{array}{cc} F_{k+1} & F_k \\ F_k & F_{k-1} \end{array}\right) \left( \begin{array}{cc} F_{n-k+1} & F_{n-k} \\ F_{n-k} & F_{n-k-1} \end{array}\right) \]

Perhatikan bahwa
\[ F_n = F_{k+1} F_{n-k} + F_k F_{n-k-1}\]
atau dalam bentuk lain
\[ F_{m+n} = F_{n+1} F_m + F_n F_{m-1}\]
muncul ketika kita menyamakan perkalian baris pertama dan kolom kedua. Inilah yang akan saya sebut sebagai magic identity karena sangat useful untuk penyelesaian parsial fibonacci.

Aplikasi pada dynamic range query

Sebagai contoh, misalkan kita pada suatu range \( [L \dots R] \) ingin menambah semua array dalam range itu dengan \(F_1\), \(F_2\), \(F_3\), dan seterusnya sampai \(F_{R-L+1}\) lalu mencari jumlah semua elemen dalam range tersebut. Dengan bruteforce hal ini mungkin dilakukan, tapi akan sangat memakan waktu jika proses tersebut dilakukan berulang-ulang.

Maka kita hanya perlu menambah parameter update \(F_1\), \(F_2\), dan \(Sum\). Dengan ketiga parameter tersebut kita bisa menggunakan magic identity yang telah dibuktikan di atas dengan sedikit memodifikasinya menjadi
\[ S_n = F_{k+1} S_{n-k} + F_k S_{n-k-1}\]
dengan \(k = 1\), menjadi
\[ S_n = F_2 S_{n-1} + F_1 S_{n-2} \]
untuk mengupdate \(Sum\) yang telah di precompute sebelumnya. Presum dari Fibonacci \(S_n\) bisa di precompute di awal. Sehingga update dan pencarian nilai bisa dilakukan dengan cepat.

Hal ini akan sangat terasa ketika berhadapan dengan soal dynamic query yang menggunakan Fibonacci sebagai update query nya. Sebagai contoh, soal yang baru saja saya solve menggunakan struktur data segment tree dan magic identity diatas yaitu Codeforces Round #FF Div2 E.

Back-Fibonacci  dan d'Ocagne's identity

Sejauh ini kita telah membahas bilangan Fibonacci berindeks non-negatif. Kita tidak memasukkan indeks negatif karena definisi yang dipakai adalah persamaan yang tersusun menaik
\[ F_n = F_{n-2} + F_{n-1} \]
Bagaimana jika kita ubah definisinya menjadi
\[ F_n = F_{n+2} - F_{n+1} \]
Maka, akan ada definisi untuk Fibonacci berindeks negatif kan? Lalu untuk apa kita harus mencari bilangan Fibonacci berindeks negatif?

Coba perhatikan barisan berikut
\( 0, 1, 1, 2, 3, 5, 8, 11, \dots \)
Barisan di atas tidak akan berakhir. Jika kita susun barisan mundur, juga akan didapati barisan tiada berakhir
\( \dots, 13, -8, 5, -3, 2, -1, 1, 0, 1, 1, 2, 3, 5, 8, 13, \dots \)

Perhatikan bahwa akan didapat hubungan antara bilangan berindeks negatif dengan bilangan berindeks positifnya, yaitu
\[ F_{-n} = (-1)^{n+1} F_n \]

Pembuktiannya sederhana, bisa dengan induksi atau dengan yang lain ( coba pembaca buktikan sendiri :) ).

Lalu, setelah ini apa?
Kita akan menemukan bahwa identitas negativitas diatas bersama-sama magic identity berpotensi menimbulkan identitas baru, yang ditemukan oleh d'Ocagne. Coba kita turunkan persamaan ini.

Kita telah mengetahui bahwa bilangan Fibonacci dapat dinyatakan dalam jumlah dari 2 perkalian Fibonacci
\[ F_{m+n} = F_{n+1} F_m + F_n F_{m-1}\]
Jika kita asumsikan \(m < 0\), maka kita subtitusikan identitas negativitas menjadi
\begin{array}{lcl}
 F_{n-m} & = & F_{n+1} F_{-m} + F_n F_{-m-1}
\\ & = & F_{n+1} (-1)^{m-1} F_m + F_n (-1)^{m+2} F_{m+1}
\\ & = & - (-1)^m F_{n+1} F_m + (-1)^m F_n F_{m+1}
\end{array}
Kalikan kedua ruas dengan \((-1)^m\) menjadi
\[ (-1)^m F_{n-m} = F_n F_{m+1} - F_{n+1} F_m \]

Inilah identitas d'Ocagne yang tidak kalah serunya dengan magic identity. Jika pada segment tree kita cukup memerlukan magic identity, maka pada binary indexed tree(BIT) kita memerlukan identitas yang bisa mengupdate sum dengan lebih fleksibel ( Ini karena yang dilakukan BIT yaitu 'hanya' mengupdate presum dari query. Kita akan bahas kedua struktur data ini lebih lanjut nanti ;D )

Sum of Fibonacci

Banyak problem yang mensyaratkan penjumlahan elemen-elemen Fibonacci dalam inti soalnya. Dan kadang kita tidak dapat menggunakan precompute untuk menghitungnya entah karena terlalu banyak atau batasan memori maupun runtime yang memaksa kita menggunakan cara yang lebih canggih.

Sebenarnya percaya atau tidak penjumlahan dari elemen-elemen Fibonacci itu adalah elemen Fibonacci lain. Percaya nggak?
Kali ini akan saya buktikan sedikit tentang Fibonacci summation yang sebenarnya sangat sederhana.

Perhatikan bahwa \( F_n = F_{n+2} - F_{n+1} \) maka jika kita jumlahkan \(F_1\) sampai \(F_n\) dengan menyubtitusikan persamaan ini, akan didapatkan \begin{array}{lcl} \sum_{i=1}^{n} F_i & = & F_1 + F_2 + F_3 + \dots + F_n \\ & = & (F_3 - F_2) + (F_4 - F_3) + \cdots + (F_{n+2} - F_{n+1}) \\ & = & F_{n+2} - F_2 \end{array}

Simple but cool, right?
Trik ini juga bisa diaplikasikan pada soal serupa dengan yang disebut di atas. Tanpa melakukan precompute kita bisa menggunakan formula ini sebagai pengganti. Lumayan menghemat runtime processing.

Penutup

Sebenarnya ada banyak identitas Fibonacci yang bisa didapatkan dengan berbagai cara (yang tentunya pembuktian lengkapnya akan diserahkan pada pembaca), diantaranya :

• Catalan identity : \( F_n^2 - F_{n+r}F_{n-r} = (-1)^{n-r}F_r^2 \) ( Hint : bukti menggunakan pemangkatan matriks dan determinan )
• Cassini identity : \( F_n^2 - F_{n+1}F_{n-1} = (-1)^{n-1} \) ( Kasus khusus dari Catalan identity )

dan lain sebagainya yang mungkin terlalu banyak jika diuraikan disini.

Sekian bahasan tentang identitas Fibonacci, mungkin juga bahasan terakhir tentang bilangan Fibonacci. Jika ada kekurangan mohon dimaklumi dan dikoreksi sebagai pelajaran berharga bagi saya. Terima kasih :)

Catatan :
Saya terinspirasi untuk membahas ini setelah melihat berbagai variasi jawaban untuk soal Codeforces yang di pos diatas. Karena saya anggap soal ini unik dan bisa disolve dengan banyak theorem dan struktur data, maka saya memutuskan menulis tentang ini.