Penerapan Algoritma Divide and Conquer pada Perhitungan Nilai Eigen
M. Faizal Hitobeli - 135060571 Program Studi Teknik Informatika Sekolah Teknik Elektro dan Informatika Institut Teknologi Bandung, Jl. Ganesha 10 Bandung 40132, Indonesia 1if16057@students.if.itb.ac.id
Abstract
Secara formal, algoritma adalah langkahlangkah dalam menyelesaikan suatu permasalahan secara terstruktur sehingga dapat ditemukannya penyelesaian. Pada dasarnya, dalam ilmu komputer konteks divide and conquer tidak jauh berbeda dengan maknanya dalam bidang politik maupun militer. Terdapat korelasi dalam memecah kekuatan musuh ke dalam bagian-bagian yang lebih kecil. Namun dalam sudut pandang ilmu komputer, kekuatan musuh yang dimaksud adalah masalah yang dihadapi. Dengan pendekatan algoritma divide and conquer, kita dapat mencoba untuk menyelesaikan permasalahan perhitungan nilai eigen. Berikut akan dibahas mengenai penerapan algoritma divide and conquer pada perhitungan nilai eigen. Pada penerpaan algoritma divide and conquer pada perhitungan nilai eigen, didapat hasil yang cenderung variatif, bergantung kepada spesifikasi komputer yang digunakan, namun penggunaan algoritma ini pada proses penghitungan nilai eigen memerlukan waktu yang relatif cepat. Implementasi algoritma dibantu dengan library LAPACK yang ditulis dengan bahasa Fortran 90. I. PENDAHULUAN
Dalam berbagai aktifitas keseharian, seseorang seringkali berhadapan dengan berbagai masalah. Banyak cara yang dapat digunakan untuk memecahkan masalahmasalah tersebut. Namun, pada dasarnya teknik pemecahan masalah yang dihadapi dapat dibagi menjadi tiga kategori, yaitu dengan menggunakan metode heuristik, algoritmik, serta menggunakan gabungan kedua metode yang ada. Metode heuristik memungkinkan seseorang untuk menemukan solusi dari suatu masalah berdasarkan ketersediaan informasi atas solusi masalah yang sedang dihadapi tersebut. Di lain pihak, metode algoritmik memungkinkan seseorang untuk mendapatkan solusi dari suatu masalah berdasarkan langkah-langkah tertentu. Tidak menutup kemungkinan untuk menggabungkan kedua metode tersebut dalam menyelesaikan suatu persoalan. Secara formal, algoritma adalah langkah-langkah dalam menyelesaikan suatu permasalahan secara terstruktur sehingga dapat ditemukannya penyelesaian. Sering algoritma dikorelasikan dengan penulisan kode dalam proses pembuatan perangkat lunak komputer. Akan tetapi, algoritma tak hanya dapat digunakan untuk membuat sebuah perangkat lunak komputer saja, melainkan dapat pula menyelesaikan persoalan tertentu dalam suatu lingkup permasalahan. Dalam bidang ilmu informatika, program yang baik bukan hanya program yang dapat menyelesaikan masalah. Akan tetapi program tersebut juga layaknya dapat menyelesaikan masalah dengan menggunakan algoritma yang efektif. Salah satu algoritma yang cukup sering digunakan untuk menyelesaikan masalah adalah algoritma Divide and Conquer. Algoritma ini bekerja dengan cara memecah suatu masalah menjadi beberapa masalah yang lebih kecil, sehingga memungkinkan untuk diselesaikan secara efektif. Dalam bidang ilmu matematika, sering ditemukan istilah atau konsep yang disebut dengan nilai eigen (eigenvalue), dan vektor eigen (eigenvector). Nilai eigen dan vektor eigen merupakan konsep yang ada dalam bidang aljabar linear. Salah satu kajian pada aljabar linear adalah transformasi linear, direpresentasikan oleh matriks yang bekerja terhadap vektor. Nilai eigen dan vektor eigen merupakan salah satu properti yang dimiliki oleh matriks bujur sangkar. Matriks bujur sangkar adalah matriks yang memiliki jumlah baris dan kolom yang sama, contoh matriks M2x2, A3x3. Nilai eigen berperan sangat besar dalam studi persamaan diferensial. Selain itu, nilai eigen juga digunakan secara luas dalam berbagai aplikasi ilmu fisika. Oleh karena aplikasinya yang cukup luas, perhitungan nilai eigen secara tepat dari sebuah matriks dapat sangat membantu dalam penerapannya. Dengan pendekatan algoritma divide and conquer, kita dapat mencoba untuk menyelesaikan permasalahan perhitungan nilai eigen. Berikut akan dibahas mengenai penerapan algoritma divide and conquer pada perhitungan nilai eigen.
II. LANDASAN TEORI
A. Algoritma Divide and Conquer
Istilah divide and conquer berasal dari istilah etimpera yang berasal dari bahasa latin yang sering digunakan dalam konteks militer ataupun politis. konteks tersebut, divide and conquer bermakna bahwa suatu kekuatan yang terkonsentrasi harus dipecah terlebih dahulu agar bisa ditaklukkan. Dengan demikian, kekuatan musuh yang lebih besar daripada kekuatan dikalahkan dengan cara memecah kekuatan musuh yang terkonsentrasi tersebut sehingga menjadi kekuatan kecil yang terpisah. Pada dasarnya, dalam ilmu komputer konteks and conquer tidak jauh berbeda dengan maknanya dalam bidang politik maupun militer. Terdapat korelasi dalam memecah kekuatan musuh ke dalam bagian lebih kecil. Namun dalam sudut pandang ilmu komputer, kekuatan musuh yang dimaksud adalah masalah yang dihadapi. Masalah yang didefinisikan dipecah ke masalah dengan tipe yang sama. Selanjutnya, kedua upa masalah tersebut dipecah masing-masing menjadi dua upa masalah yang lain dan seterusnya sampai masalah tersebut menjadi sangat sederhana, sehingga memungkinkan untuk diselesaikan, atau tid dipecah lagi. Jika dianalogikan ke dalam bentuk pohon, simpul akar adalah masalah utama, yang selanjutnya memiliki dua cabang pada tingkat 1. Dua cabang tersebut kemudian masing-masing memiliki dua daun seterusnya. Berikut ilustrasi algoritma divide and conquer dengan representasi pohon.
Gambar 1. Representasi pohon algoritma divide and conquer
Algoritma divide and conquer mempunyai tiga elemen dalam pendekatannya. Pertama, divide, yaitu memecah masalah yang ada menjadi upa masalah. Kedua, yaitu menyelesaikan masalah. Ketiga, menyatukan hasil masalah yang didapat dari setiap upa masalah untuk mendapatkan solusi akhirnya. Berikut contoh pseudo code algoritma conquer:
procedure divide (general parameters) if (trivial) then //condition of triviality solve it else //not trivial then divide into sub-problems
Sem. I Tahun 2010/2011
berasal dari istilah divide yang berasal dari bahasa latin yang sering militer ataupun politis. Dalam bermakna bahwa suatu kekuatan yang terkonsentrasi harus dipecah terlebih dahulu agar bisa ditaklukkan. Dengan demikian, kekuatan musuh yang lebih besar daripada kekuatan kita dapat kekuatan musuh yang terkonsentrasi tersebut sehingga menjadi kekuatan kecil
Pada dasarnya, dalam ilmu komputer konteks divide tidak jauh berbeda dengan maknanya dalam bidang politik maupun militer. Terdapat korelasi dalam h kekuatan musuh ke dalam bagian-bagian yang sudut pandang ilmu komputer, kekuatan musuh yang dimaksud adalah masalah yang
h yang didefinisikan dipecah ke dalam dua upa masalah dengan tipe yang sama. Selanjutnya, kedua upa masing menjadi dua upa masalah yang lain dan seterusnya sampai masalah tersebut menjadi sangat sederhana, sehingga memungkinkan untuk diselesaikan, atau tidak dapat Jika dianalogikan ke dalam bentuk pohon, simpul akar adalah masalah utama, yang selanjutnya memiliki dua cabang pada tingkat 1. Dua cabang tersebut memiliki dua daun, dan begitu divide and conquer
divide and conquer mempunyai tiga elemen , yaitu memecah da menjadi upa masalah. Kedua, conquer, yaitu menyelesaikan masalah. Ketiga, combine, yang didapat dari setiap upa masalah untuk mendapatkan solusi akhirnya. algoritma divide and condition of triviality solve them recursively // until it becomes trivial combine them to get the final solution end if end procedure
B. Definisi Nilai Eigen Definisi nilai eigen
secara formal adalah transformasi linear, vektor non-null x adalah vektor eigen dari A jika ada skalar λ sedemikian sehingga Maka, λ dikatakan nilai eigen dari A sesuai dengan x, dan untuk semua vektor eigen berperilaku seperti x Dalam aljabar linear, terdapat dua macam skalar yang merupakan hanya angka, dan v memiliki panjang dan arah (atau lebih tepatnya vektor adalah anggota ruang vektor). Vektor dapat dianggap sebagai anak panah. Pada fungsi biasa aljabar, fungsi yang paling penting dalam aljabar linier disebut transformasi linear, dan transformasi linear biasanya diberikan oleh matriks, array dari angka fungsi pada aljabar linear direpresenta peulisan f (x), melainkan dengan pe hanya Mv, dimana M adalah matriks dan v adalah vektor. Berikut contoh pencarian nilai eigen pada suatu matriks. Misal terdapat suatu matriks A sebagai berikut:
Jadi, nilai eigen yang didapat adalah:
C. LAPACK Liniear Algebra PACKage (LAPACK)
adalah suatu library perangkat lunak yang disediakan untuk melayani perhitungan aljabar linear numerik. menyediakan kumpulan routines untuk memecahkan sistem persamaan linear, nilai eigen, dan dekomposisi nilai singular. LAPACK ditulis dalam bahasa Fortran 77. Pada perkembangannya LAPACK sekarang ditulis dalam bahasa Fortran 90. Berikut merupakan ilustra komponen di dalam library LAPACK.
Lebih lengkapnya langsung Download yak...disini nih
Tidak ada komentar:
Posting Komentar