Thursday, February 28, 2013

FSM Final Task - Sejarah Algoritma



Sejarah Algoritma     

I.                Pendahuluan
a.       Latar Belakang
Sebagian besar mahasiswa yang mempelajari komputer dan pemrogramman pastinya sudah mengetahui walaupun sedikit mengenai ‘algoritma’. Umumnya, algoritma didefinisikan sebagai merupakan kumpulan perintah untuk menyelesaikan suatu masalah. Algoritma juga dikenal sebagai suatu urutan langkah-langkah suatu kegiatan ataupun teori. Sekecil apapun yang kita lakukan di dunia ini tak akan lepas dari algoritma. Mulai dari bangun tidur, mandi, hingga berpakaian, semuanya menggunakan algoritma.
Algoritma yang secara nyata telah berperan penting dalam kehidupan kita, ternyata tidak banyak yang tahu bagaimana asal-usul dan sejarah perkembangannya. Algoritma kini lebih terkenal di kalangan pemerhati dunia komputer, khususnya pemrogramman.

 
Sebagai mahasiswa Pendidikan Matematika, ada baiknya jika kita mengetahui sejarah algoritma, karena kita akan sering menemukan dan menggunakan istilah tersebut di dalam berbagai teorema dan kesempatan lainnya. Algoritma bukanlah suatu teorema yang sejarahnya berupa rumus atau pembuktian dari teori-teori sebelumnya. Penulis menekankan pada sejarah dan perkembangannya hingga menjadi jantung informatika seperti saat sekarang ini.
Algoritma sangat mudah kita jumpai dalam sehari-hari, namun sangat sedikit yang mengetahui bahwa segala sesuatu yang mereka lakukan adalah suatu algoritma yang jika dibalik atau salah satu langkah saja, akan merubah hasilnya. Algoritma lah yang mengakibatkan perbedaan-perbedaan di kehidupan. Berbagai algoritma berbeda ada yang menghasilkan produk yang sama, namun ada juga algoritma yang tidak bisa dibalik-balik untuk mendapatkan hasil yang serupa.
Kata ‘algoritma’ yang sangat mudah diucapkan hari ini, seharusnya kita juga mengetahui bagaimana dan dari mana asal mulanya kata tersebut dan bagaimana pula perkembangannya. Untuk itulah, penulis mengambil Algoritma sebagai tema dalam penulisan  makalah kali ini.

b.      Rumusan Masalah
1)      Bagaimanakah asal-usul dan sejarah kata Algoritma?
2)      Siapa sajakah matematikawan yang dikenal sebagai pahlawan Algoritma?
3)      Bagaimanakah perkembangan Algoritma di abad ke-20?

c.       Tujuan
1)      Untuk mengetahui sejarah dan asal-usul kata Algoritma
2)      Untuk mengetahui siapa saja ilmuwan yang terkenal dalam perkembangan Algoritma
3)      Untuk mengetahui perkembangan Algoritma di abad ke-20
d.      Manfaat
1)      Dapat menambah pengetahuan mengenai sejarah Algoritma
2)      Dapat mengetahui peran matematikawan dalam mengembangkan Algoritma
3)      Dapat mengetahui perkembangan algoritma pada abad ke-20



II.             Pembahasan
a.      Asal Mula Kata Algoritma
Saat ini setiap orang menggunakan kata "Algoritma" sebagai hal yang biasa, tetapi untuk sebagian besar definisi yang tepat, kata tersebut telah sejak lama menjadi sebuah misteri. Kata ini tidak muncul dalam kamus Webster hingga akhir tahun 1957. Orang hanya menemukan kata ‘algorism’ yang berarti proses menghitung dengan angka Arab.
Algoritma memiliki sejarah panjang dan kata dapat ditelusuri kembali ke abad ke-9. Pada saat ini ilmuwan astronom, matematikawan Persia dan Abdullah Muhammad bin Musa al-Khwarizmi yang juga dikenal dengan sebutan "Bapak Aljabar", secara tidak langsung bertanggung jawab atas penciptaan kata "Algoritma".
Pada abad ke-12 setelah salah satu bukunya yang diterjemahkan ke dalam bahasa Latin beredar luas, di mana namanya diberikan dalam bahasa Latin sebagai "Algorithmi". Tapi ini bukan awal dari algoritma.
Dalam analisis yang mendalam, Hunke melacak sejarah algoritma kata dari asal-usulnya ke dalam ketidakjelasan relatif hingga zaman modern. Sementara menjadi pelayan di istana El-Khalifeh El-Mamoun (813-833 AD), Al-Khawarizmi menulis teks ilmiah dalam astronomi, geografi, dan aljabar, serta matematika umum. Pada abad kedua belas, aljabar dan matematika teks lainnya diterjemahkan ke dalam bahasa Latin, Spanyol, dan Jerman, dan beredar di Eropa abad pertengahan.
Tentara Jerman memodifikasi nama Al-Khawarizmi ke Algorizmus (Algorismus sebagai setara Latin/Perancis) untuk kemudahan pengucapan. Al-Khawarizmi meninggal pada tahun 840 Masehi, dan pada abad ketiga belas, dunia telah menggunakan algoritmatapi lupa asal algoritma.
Di antara tahun1808 dan 1811, matematikawan Perancis Antoine-Andre-Louis Reynaud (1.771-1.844) menjadi tertarik pada algoritma. Dia telah diakui sebagai salah satu orang pertama yang memberikan analisis eksplisit algoritma. Pada saat itu ia telah mengetahui bahwa kata algoritma berasal dari nama matematikawan terkenal Al-Khawarizmi.
Sejak saat Al-Khwarizmi, algoritma telah memainkan peran progresif dalam peradaban Barat, untuk meneruskan ilmu pengetahuan dan teknologi, serta industri manfaat dan perdagangan. Sebagai komputer dan pengolahan data dikembangkan, algoritma mulai mewujudkan sistem posisional dalam bit, kata-kata dan unit aritmatika, mengatakan Dasgupta, Papadimitriou dan Vazirani.
Pada tahun 1950, kata Algoritma pertama kali digunakan dalam Algoditma Euclidean. Euclid, seorang matematikawan asal Yunani, dalam bukunya yang berjudul Element, menuliskan langkah-langkah untuk menemukan pembagi bersama terbesar.
b.      Pahlawan Algoritma
Walaupun hampir seluruh ilmuwan dan matematikawan menggunakan istilah algoritma, namun ada beberapa nama yang dikenal sebagai pahlawan Algoritma.
                    i.      Euclid

Dalam matematika, algoritma Euclidean atau algoritma Euclid, adalah metode yang efisien untuk menghitung pembagi bersama terbesar (GCD) dari dua bilangan bulat, juga dikenal sebagai faktor umum terbesar (GCF) atau faktor umum tertinggi (HCF). Hal ini dinamai matematika Euclid Yunani, yang dijelaskan dalam Buku VII dan X Elements nya.
Dalam bentuk yang paling sederhana, algoritma Euclid dimulai dengan sepasang bilangan bulat positif dan membentuk sepasang baru yang terdiri dari jumlah yang lebih kecil dan perbedaan antara angka yang lebih besar dan lebih kecil. Mengulangi proses sampai angka adalah sama. Angka itu kemudian adalah pembagi umum terbesar dari pasangan asli.
Deskripsi awal hidup dari algoritma Euclidean dalam Elemen Euclid (c. 300 SM), membuatnya menjadi salah satu algoritma numerik tertua yang masih umum digunakan. Algoritma asli dijelaskan hanya untuk nomor alami dan panjang geometris (bilangan real), namun algoritma menjadi umum di abad ke-19 untuk jenis nomor lainnya, seperti bilangan bulat Gaussian dan polinomial dalam satu variabel. Hal ini menyebabkan pengertian yang modern aljabar abstrak seperti domain Euclidean. Algoritma Euclidean telah umum lebih lanjut untuk struktur matematika lainnya, seperti knot dan polinomial multivariat.
Algoritma ini memiliki aplikasi teoritis dan praktis. Ini dapat digunakan untuk menghasilkan hampir semua yang paling penting irama musik tradisional yang digunakan dalam budaya yang berbeda di seluruh dunia. Ini adalah elemen kunci dari algoritma RSA, publik-kunci enkripsi metode yang luas digunakan dalam perdagangan elektronik. Hal ini digunakan untuk memecahkan persamaan Diophantine, seperti menemukan nomor yang memenuhi beberapa congruences (teorema sisa Cina) atau invers perkalian dari lapangan terbatas. Hal ini juga dapat digunakan untuk membangun terus pecahan, dalam metode rantai Sturm untuk menemukan akar nyata polinomial, dan dalam beberapa algoritma faktorisasi modern yang bulat. Akhirnya, itu adalah alat dasar untuk membuktikan teorema di nomor teori modern, seperti empat-persegi Teorema Lagrange dan teorema dasar aritmatika (faktorisasi yang unik).
Jika diimplementasikan menggunakan sisa dari pembagian Euclidean bukan subtractions, algoritma Euclid menghitung GCD jumlah besar secara efisien: tidak pernah memerlukan langkah-langkah pembagian lebih dari lima kali jumlah digit (basis 10) dari integer yang lebih kecil. Hal ini terbukti dengan Gabriel Lame pada tahun 1844, dan menandai awal dari teori kompleksitas komputasi. Metode untuk meningkatkan efisiensi algoritma yang dikembangkan pada abad ke-20.
GCD dari dua angka adalah jumlah terbesar yang membagi keduanya tanpa meninggalkan sisanya. Algoritma Euclidean didasarkan pada prinsip bahwa pembagi bersama terbesar dari dua angka tidak berubah jika jumlah yang lebih kecil dikurangi dari jumlah yang lebih besar. Karena jika k, m, dan n adalah bilangan bulat, dan k adalah faktor umum dari dua bilangan bulat A dan B, maka A dan B = nk = mk menyiratkan A - B = (n - m) k, sehingga k juga umum faktor perbedaan.
Bahwa k juga dapat mewakili pembagi umum terbesar terbukti di bawah ini. Sebagai contoh, 21 adalah GCD dari 252 dan 105 (252 = 12 × 21, 105 = 5 × 21), sejak tahun 252-105 = (12 - 5) × 21 = 147, GCD dari 147 dan 105 juga 21.
Ketika lebih dari dua angka berkurang, mengulangi proses ini memberikan angka berturut-turut lebih kecil sampai salah satu dari mereka adalah nol. Ketika itu terjadi, GCD adalah jumlah nol yang tersisa. Dengan membalikkan langkah-langkah dalam algoritma Euclidean, GCD dapat dinyatakan sebagai jumlah dari dua bilangan asli masing-masing dikalikan dengan bilangan bulat positif atau negatif, misalnya, 21 = [5 × 105] + [(-2) × 252]. Sifat ini sangat penting dan dikenal sebagai identitas Bézout ini.

                  ii.      Al-Khwarizmi
Al-Khawarizmi menulis buku yang berjudul Kitab Al Jabar Wal-Muqabala yang artinya “Buku Pemugaran dan Pengurangan” (The book of restoration and redu  ction). Dari judul buku itu kita juga memperoleh akar kata “Aljabar” (Algebra). Perubahan kata dari Algorism menjadi Algorithm muncul karena kata Algorism sering dikelirukan dengan Arithmetic, sehingga akhiran –sm berubah menjadi –thm. Karena perhitungan dengan angka Arab sudah menjadi hal yang biasa. Maka lambat laun kata Algorithm berangsur-angsur dipakai sebagai metode perhitungan (komputasi) secara umum, sehingga kehilangan makna kata aslinya. Dalam Bahasa Indonesia, kata Algorithm diserap menjadi Algoritma.
iii. Hilbert
 David Hilbert adalah seorang matematikawan Jerman yang merupakan salah satu matematikawan paling berpengaruh pada abad ke-19 dan awal abad ke-20. Ia diakui sebagai matematikawan dan ilmuwan besar yang menemukan atau mengembangkan beberapa gagasan, seperti teori invarian, aksiomisasi geometri, persamaan-persamaan integral dan gagasan ruang Hilbert. Ia dilahirkan di Königsberg, Prussia Timur (sekarang Kaliningrad, Russia), dan menempuh pendidikan S1 di University of Königsberg.
Hilbert menjabarkan aksiomatisasi geomatri Euclid secara lebih akurat dan lengkap pada tahun 1899. Dalam “Permasalahan Matematika”, pidato terkenal yang disampaikan pada Kongres Matematika Internasional pada tanggal 8 Agustus 1900 di Paris, ia menjabarkan sepuluh masalah matematika yang belum dipecahkan (yang disebut Hilbert’s Problems). Ketika diterbitkan dalam bentuk buku, daftar masalah diperluas ke 23, beberapa di antaranya masih belum terselesaikan sampai hari ini.
Hilbert dengan 10th Problem nya telah menciptakan perubahan besar dalam dunia matematika, yang membuat ia berjasa dalam pengembangan algoritma di abad ke-19.
iv.    Alan Turing
Alan Turing, lahir pada 23 Juni 1912 dan akhirnya menjadi seorang peneliti di bidang matematika dan komputer.
Selama Perang Dunia II, Turing bekerja untuk GCCS di Bletchley Park, sebuah pusat pengkodean di Inggris. Untuk sementara waktu ia menjabat sebagai kepala Hut 8, bagian yang bertanggung jawab untuk pembacaan sandi angkatan laut Jerman. Dia menemukan sejumlah teknik untuk memecahkan cipherJerman, termasuk cara Bombe, sebuah mesin elektromekanis yang dapat menemukan pengaturan untuk mesin Enigma.
Alan Turing dikenal sebagai orang yang berkecimpung di dunia matematika, namun disamping itu dia juga termasuk orang yang sangat berpengaruh dalam dunia komputer sehingga tidak heran dia  mendapatkan gelar Bapak Ilmu Komputer.
Alan Turing mencetuskan konsep algoritma dan komputerisasikan yang diaplikasikan pada sebuah mesin yang sama dengan namanya, Turing. Mesin itu sering disebut sebaga cikal bakal komputer saat ini, sebuah mesin yang bisa menjalankan perintah-perintah.
Alan Turing meninggal pada tahun 1945, 2 minggu sebelum tiba hari ulang tahunnya yang ke-42. Sampai saat ini, penyebab kematian ALan Turing masih menyisakan misteri. Dari hasil investigasi ditemukan bahwa penyebab kematiannya adalah bunuh diri, namun keluarga menyangkalnya dan mengatakan bahwa Alan meninggal karena kecelakaan.
c.       Perkembangan Algoritma Abad ke-20
Algoritma terus berkembang dan  menjadi jantung informatika seperti yang sudah kita rasakan pada saat ini. Perkembangannya sangat pesat di bagian barat, yaitu di benua Eropa. Pada abad ke-20, banyak algoritma yang bermunculan dan terkenal dari para ahli sains di berbagai belahan dunia. Penulis telah merangkum Top 3 Algoritma Abad ke-20, yaitu sebagai berikut :
1)      Algoritma Metropolis/Metode Monte Carlo (Oleh Francis Sulivan, Neumann, Ulam, Metropolis, 1946)
Melalui proses secara acak, algoritma ini menawarkan cara yang efisien untuk menyelesaikan masalah yang terlalu rumit hingga bisa diselesaikand engan mudah. Metode Monte Carlo adalah satu-satunya pilihan yang dapat digunakan untuk menghitung permasalahan dimensi tinggi.
Pengujian dan penerapan algoritma Metropolis telah dilakukan pada lembarkerja Excel. Pengujian dilakukan dengan cara mensimulasikan pembalikan spin dan menghitung magnetisasi bahan feromagnetik berupa model Ising 2D.
2)      Metode Simplex untuk Program Linear (Oleh Danzig, 1947)
Suatu penyelesaian elegan untuk seluruh permasalahan rencana dan mengambil keputusan, yaitu program linear. Dalam optimasi matematika, simplex algoritma Dantzig (atau metode simpleks) adalah algoritma yang populer untuk pemrograman linear. Komputasi jurnal Science and Engineering terdaftar sebagai salah satu dari 10 besar algoritma dari abad kedua puluh .
Nama algoritma ini berasal dari konsep simplex dan disarankan oleh TS Motzkin. Algoritma simpleks beroperasi pada program linier dalam bentuk standar, yaitu masalah pemrograman .
Metode ini bekerja dengan menunjukkan bahwa untuk program linier dalam bentuk standar, jika fungsi tujuan memiliki nilai minimum pada daerah feasible maka memiliki nilai ini pada (setidaknya) salah satu poin yang ekstrim. Hal ini sendiri mengurangi masalah untuk perhitungan terbatas karena ada sejumlah terbatas titik ekstrim, namun jumlah titik ekstrim tidak dapat dikelola besar untuk semua tapi program linear terkecil.
Hal ini juga dapat menunjukkan bahwa jika titik ekstrim bukanlah titik minimum dari fungsi tujuan maka ada kelebihan yang mengandung titik sehingga fungsi tujuan adalah sangat menurun di tepi bergerak menjauh dari titik. Tepi adalah terbatas maka tepi menghubungkan ke jalur ekstrim di mana fungsi tujuan memiliki nilai yang lebih kecil, jika fungsi tujuan tak terbatas bawah di tepi dan program linear tidak memiliki solusi. Algoritma simpleks berlaku wawasan ini dengan berjalan di sepanjang tepi polytope ke titik ekstrim dengan nilai-nilai objektif yang lebih rendah dan lebih rendah. Ini terus berlanjut sampai nilai minimum tercapai atau keunggulan tak terbatas dikunjungi, menyimpulkan bahwa masalah tersebut tidak memiliki solusi.
Algoritma selalu berakhir karena jumlah simpul di polytope yang terbatas, apalagi karena kita melompat antara simpul selalu dalam arah yang sama (bahwa dari fungsi tujuan), kami berharap bahwa jumlah simpul dikunjungi akan menjadi kecil.
Solusi dari program linear dilakukan dalam dua langkah. Pada langkah pertama, yang dikenal sebagai Tahap I, titik ekstrim awal ditemukan. Tergantung pada sifat dari program ini mungkin sepele, tetapi secara umum dapat diselesaikan dengan menerapkan algoritma simpleks untuk versi modifikasi dari program asli. Kemungkinan hasil Tahap I yang baik solusi yang layak dasar ditemukan atau bahwa daerah feasible kosong. Dalam kasus terakhir program linier disebut tidak layak. Pada langkah kedua, Tahap II, algoritma simpleks diterapkan menggunakan solusi layak dasar yang ditemukan dalam Tahap I sebagai titik awal. Hasil yang mungkin dari Tahap II yang baik merupakan solusi yang layak optimum dasar atau keunggulan yang tak terbatas di mana fungsi tujuan tak terbatas.
3)      Decompositional Approach to Matrix Computations (Oleh Householder, 1951)
Serangkaian teknik numerical dari aljabar linear yang membukakan jalan untuk menyelesaikan paket permasalahan matrix, yaitu memfaktorkan matriks ke dalam bentuk triangular, diagonal, orgthogonal, tri-diagonal, dan bentuk lainya.
Dalam aljabar linear, transformasi Householder (juga dikenal sebagai refleksi Householder atau reflektor SD) adalah transformasi linear yang menggambarkan refleksi tentang pesawat atau hyperplane mengandung asal. Transformasi rumah banyak digunakan dalam aljabar linear numerik, untuk melakukan dekomposisi QR dan pada langkah pertama dari algoritma QR. Transformasi Householder diperkenalkan pada tahun 1958 oleh Scott Householder Alston.





III.             Penutup
a.  Kesimpulan
Algoritma, sebuah kata yang kita kenal sebagai suatu urutan proses terjadinya sesuatu, ternyata pada awalnya bukan merupakan suatu kesengajaan. Matematikawan Arab, Al Khawarizmi, yang memerkenalkan angka dan beberapa teori Matematika ke seluruh dunia, mengalami perubahan nama yang disebut oleh masyarakat Jerman. Pengucapan nama Khawarizmi berubah menjadi Algorismi yang lama kelamaan menjadi Algorithm, atau dalam bahasa Indonesia disebut Algoritma. Algoritma menjadi jantung informatika setelah Alan Turing mengemukakan gagasannya, sehingga ia dikenal sebagai salah satu pahlawan algoritma, bersama Euclide, Hillbert, dan tentunya Al Khawarizmi.
Algoritma terus berkembang hingga melalui abad ke-20 di mana para ilmuwan berlomba-lomba menemukan algoritma baru. Berbagai algoritma mulai bermunculan dan menambah daftar panjang ilmuwan yang tertarik pada algoritma. Algoritma telah membukakann banyak pintu ilmu dalam berbagi cabang, terutama ilmu sains dan informatika..




Daftar Pustaka

Ariyanto, Dedi. 2008. ALGORITMA. http://dedylamongan. blogspot.com/2012/01/makalah-algoritma.html.Diakses pada tanggal 1 Januari 2013
Baraka, Anis. 1998. The Origin of the “Algorithm. http://journals. lww.com/anesthesiology/Fulltext/1998/07000/The_Origin_of_the__Algorithm_.52.aspx. Diakses pada tanggal 28 Desember 2012

Eurekalert. 2002. Algorithms -- A new perspective on data.http://cs-exhibitions.uni-klu.ac.at/index.php?id=389. Diakses pada tanggal 28 Desember 2012

Greenfie. 2004. The Euclidean Algorithm.http://www.math. rutgers.edu/~greenfie/gs2004/euclid.html. Diakses pada tanggal 28 Desember 2012

Hongwei, Huo. 2000. Design and Analysis of Algorithms. www.batan.go.id/ppin/lokakarya/LKSTN_13/Bunjamin.pdf. Diakses pada tanggal 13 Januari 2013

Riefz, 2009. Sejarah Algoritma. http://napsters91. blogspot.com/2010/09/.sejarah-algoritma.html. Diakses pada tanggal 28 Desember 2012

Scott, Jenny L. 2008. The History of the Algorithm. http://www. ehow.com/facts_6901393_history-algorithm.html. Diakses pada tanggal 1 Januari 2013

Wikipedia. 2011. Hilbert’s Tenth Problem. http://en.wikipedia. org/wiki/Hilbert%27s_tenth_problem. Diakses pada tanggal 1 Januari 2013

Wikipedia. 2010. Euclide’s Algorithm. http://en.wikipedia. org/wiki/Euclidean_algorithm. Diakses pada tanggal 1 Januari 2013

Wikipedia. 2010. Simplex Algorithm. http://en.wikipedia.org /wiki/Simplex_algorithm. Diakses pada tanggal 13 Januari 2013



No comments:

Post a Comment