www.wikidata.id-id.nina.az

Algoritme Euklides Dalam matematika algoritme Euklides adalah suatu algoritme untuk menentukan faktor persekutuan terbes

Algoritme Euklides

Dalam matematika, algoritme Euklides adalah suatu algoritme untuk menentukan faktor persekutuan terbesar (FPB) dari dua bilangan bulat. Algoritme ini dinamai setelah matematikawan Yunani Euklides menuliskannya dalam Buku VII dan Buku X Elemen Euklides.

Algoritme Euklides muncul dalam buku Elemen Euklides sekitar tahun 300 SM, menjadikannya salah satu algoritme numerik yang tertua dan masih digunakan secara luas.

Algoritme Euklides tidak memerlukan faktorisasi.

Deskripsi algoritme sunting

  1. Diberikan dua bilangan asli dan , periksa apakah adalah nol.
  2. Jika ya, adalah FPB. Jika tidak, ulangi langkah pertama dengan menggunakan sebagai yang baru dan sisa setelah dibagi oleh sebagai yang aru.

Contoh sunting

Sebagai contoh, FPB dari 1071 dan 1029 yang dihitung dengan menggunakan algoritme ini adalah 21, dengan langkah-langkah sebagai berikut:

a b sisa setelah a dibagi oleh b
1071 1029 42
1029 42 21
42 21 0
21 0

Dengan mencatat hasil bagi (yang merupakan bilangan bulat) selama menjalankan algoritme, kita juga dapat menentukan bilangan bulat p dan q di mana ap + bq = fpb(a, b). Hal ini dikenal sebagai perluasan algoritme Euklides.

Bukti kebenaran sunting

Misalkan dan adalah bilangan yang FPB-nya akan ditentukan. Dan misalkan sisa dari pembagian dari oleh adalah . Maka di mana adalah hasil bagi (yang merupakan bilangan bulat) dari pembagian tersebut. Sekarang, setiap pembagi dari dan juga dapat habis membagi (karena dapat ditulis sebagai ). Dengan cara yang sama, setiap pembagi dari dan juga akan habis membagi . Maka faktor persekutuan terbesar dari dan adalah sama dengan FPB dari dan . Oleh karena itu, kita cukup meneruskan proses tadi dengan dan saja. Karena lebih kecil dalam nilai mutlak dari , kita akan mencapai setelah sejumlah langkah.

Implementasi sunting

Algoritme ini dapat dinyatakan dengan menggunakan rekursi kanan: 

 function fpb(a, b) if b = 0 return a else return fpb(b, a modulus b);

Secara iteratif, fungsi ini dapat ditulis sebagai: 

 function fpb(a, b) while b ≠ 0 var t:= b b:= a modulus b a:= t return a

Euklides pada mulanya merumuskan masalah ini secara geometri, sebagai masalah untuk mencari "satuan" yang dapat dipakai untuk panjang dari dua buah garis, dan algoritmanya berlangsung dengan mengulangi pengurangan dari sisi yang lebih pendek dari sisi yang lebih panjang. Implementasi ini sama dengan implementasi berikut ini, yang cukup tidak efisien dibandingkan dengan cara yang telah dijelaskan di atas: 

 function fpb(a, b) while a ≠ b if a > b  a:= a - b else  b:= b - a return a

Efisiensi algoritme sunting

Grafik banyak langkah yang diperlukan algoritme Euklidean untuk mencari fpb(x,y). Titik-titik yang warnanya cerah (merah dan kuning) menandakan langkah yang dibutuhkan relatif sedikit, sedangkan warna yang gelap (violet dan biru) menunjukkan perlu banyak langkah. Daerah yang paling gelap ada di garis y = Φx, di mana Φ adalah rasio emas.

Efisiensi komputasional algoritme Euklides telah dipelajari secara menyeluruh. Efisiensi ini bisa diartikan sebagai banyak langkah pembagian yang perlu dilakukan algoritme, dikali dengan harga komputasi setiap pembagian. Analisis tertua yang diketahui tentang algoritme Euklides berasal dari A. A. L. Reynaud pada tahun 1811, yang menunjukkan bahwa banyak langkah pembagian yang dilakukan dengan masukan tidak mungkin lebih dari ; dia kemudian memperbaiki batas ini menjadi . Kemudian, pada tahun 1841, P. J. E. Finck menunjukkan bahwa banyak langkah pembagian tidak mungkin lebih tinggi dari , dan artinya algoritme Euklides berjalan dalam waktu polinomial dari ukuran masukannya. Émile Léger, pada tahun 1837, mempelajari kasus terburuknya, yaitu ketika masukannya adalah bilangan Fibonacci yang bersebelahan. Analisis Finck kemudian diperbaiki oleh Gabriel Lamé pada tahun 1844, yang menunjukkan bahwa banyak langkah yang diperlukan untuk menyelesaikan algoritme tidak pernah lebih dari lima kali banyak digit bilangan yang lebih kecil .

Penggunaan sunting

Algoritme ini dapat digunakan dalam konteks di mana pembagian bersisa memungkinkan. Ini termasuk polinomial gelanggang dalam suatu medan, juga gelanggang dari bilangan bulat Gauss, dan dalam ranah Euklides umum.

Referensi sunting

  1. Knuth 1997, hlm. 339–364
  2. Reynaud, A.-A.-L. (1811). Traité d'arithmétique à l'usage des élèves qui se destinent à l'École Polytechnique (edisi ke-6th). Paris: Courcier. Note 60, p. 34.  Dikutip oleh (Shallit 1994).
  3. Finck, P.-J.-E. (1841). Traité élémentaire d'arithmétique à l'usage des candidats aux écoles spéciales (dalam bahasa Prancis). Derivaux. 
  4. ^ Shallit, J. (1994). "Origins of the analysis of the Euclidean algorithm". Historia Math. 21: 401–419. doi:10.1006/hmat.1994.1031. 
  5. Lamé, G. (1844). "Note sur la limite du nombre des divisions dans la recherche du plus grand commun diviseur entre deux nombres entiers". Comptes Rendus Acad. Sci. (dalam bahasa Prancis). 19: 867–870. 
  6. Grossman, H. (1924). "On the Number of Divisions in Finding a G.C.D". The American Mathematical Monthly. 31 (9): 443. doi:10.2307/2298146. JSTOR 2298146. 
  7. Honsberger, R. (1976). Mathematical Gems II. The Mathematical Association of America. hlm. 54–57. ISBN 0-88385-302-7. 

Bibliografi sunting

Pranala luar sunting

Wikimedia Commons memiliki media mengenai Algortime Euklidean.
wikipedia, wiki, buku, buku, perpustakaan, artikel, baca, unduh, gratis, unduh gratis, mp3, video, mp4, 3gp, jpg, jpeg, gif, png, gambar, musik, lagu, film, buku, permainan, permainan.
Tanggal penerbitan:
Dalam matematika algoritme Euklides adalah suatu algoritme untuk menentukan faktor persekutuan terbesar FPB dari dua bilangan bulat Algoritme ini dinamai setelah matematikawan Yunani Euklides menuliskannya dalam Buku VII dan Buku X Elemen Euklides Algoritme Euklides muncul dalam buku Elemen Euklides sekitar tahun 300 SM menjadikannya salah satu algoritme numerik yang tertua dan masih digunakan secara luas Algoritme Euklides tidak memerlukan faktorisasi Daftar isi 1 Deskripsi algoritme 2 Contoh 3 Bukti kebenaran 4 Implementasi 5 Efisiensi algoritme 6 Penggunaan 7 Referensi 8 Bibliografi 9 Pranala luarDeskripsi algoritme suntingDiberikan dua bilangan asli a displaystyle a nbsp dan b displaystyle b nbsp periksa apakah b displaystyle b nbsp adalah nol Jika ya a displaystyle a nbsp adalah FPB Jika tidak ulangi langkah pertama dengan menggunakan b displaystyle b nbsp sebagai a displaystyle a nbsp yang baru dan sisa setelah a displaystyle a nbsp dibagi oleh b displaystyle b nbsp sebagai b displaystyle b nbsp yang aru Contoh suntingSebagai contoh FPB dari 1071 dan 1029 yang dihitung dengan menggunakan algoritme ini adalah 21 dengan langkah langkah sebagai berikut a b sisa setelah a dibagi oleh b 1071 1029 42 1029 42 21 42 21 0 21 0 Dengan mencatat hasil bagi yang merupakan bilangan bulat selama menjalankan algoritme kita juga dapat menentukan bilangan bulat p dan q di mana ap bq fpb a b Hal ini dikenal sebagai perluasan algoritme Euklides Bukti kebenaran suntingMisalkan a displaystyle a nbsp dan b displaystyle b nbsp adalah bilangan yang FPB nya akan ditentukan Dan misalkan sisa dari pembagian dari a displaystyle a nbsp oleh b displaystyle b nbsp adalah t displaystyle t nbsp Maka a q b t displaystyle a qb t nbsp di mana q displaystyle q nbsp adalah hasil bagi yang merupakan bilangan bulat dari pembagian tersebut Sekarang setiap pembagi dari a displaystyle a nbsp dan b displaystyle b nbsp juga dapat habis membagi t displaystyle t nbsp karena t displaystyle t nbsp dapat ditulis sebagai t a q b displaystyle t a qb nbsp Dengan cara yang sama setiap pembagi dari b displaystyle b nbsp dan t displaystyle t nbsp juga akan habis membagi a displaystyle a nbsp Maka faktor persekutuan terbesar dari a displaystyle a nbsp dan b displaystyle b nbsp adalah sama dengan FPB dari b displaystyle b nbsp dan t displaystyle t nbsp Oleh karena itu kita cukup meneruskan proses tadi dengan b displaystyle b nbsp dan t displaystyle t nbsp saja Karena t displaystyle t nbsp lebih kecil dalam nilai mutlak dari b displaystyle b nbsp kita akan mencapait 0 displaystyle t 0 nbsp setelah sejumlah langkah Implementasi suntingAlgoritme ini dapat dinyatakan dengan menggunakan rekursi kanan function fpb a b if b 0 return a else return fpb b a modulus b Secara iteratif fungsi ini dapat ditulis sebagai function fpb a b while b 0 var t b b a modulus b a t return a Euklides pada mulanya merumuskan masalah ini secara geometri sebagai masalah untuk mencari satuan yang dapat dipakai untuk panjang dari dua buah garis dan algoritmanya berlangsung dengan mengulangi pengurangan dari sisi yang lebih pendek dari sisi yang lebih panjang Implementasi ini sama dengan implementasi berikut ini yang cukup tidak efisien dibandingkan dengan cara yang telah dijelaskan di atas function fpb a b while a b if a gt b a a b else b b a return aEfisiensi algoritme sunting nbsp Grafik banyak langkah yang diperlukan algoritme Euklidean untuk mencari fpb x y Titik titik yang warnanya cerah merah dan kuning menandakan langkah yang dibutuhkan relatif sedikit sedangkan warna yang gelap violet dan biru menunjukkan perlu banyak langkah Daerah yang paling gelap ada di garis y Fx di mana F adalah rasio emas Efisiensi komputasional algoritme Euklides telah dipelajari secara menyeluruh 1 Efisiensi ini bisa diartikan sebagai banyak langkah pembagian yang perlu dilakukan algoritme dikali dengan harga komputasi setiap pembagian Analisis tertua yang diketahui tentang algoritme Euklides berasal dari A A L Reynaud pada tahun 1811 2 yang menunjukkan bahwa banyak langkah pembagian yang dilakukan dengan masukan u v displaystyle u v nbsp tidak mungkin lebih dari v displaystyle v nbsp dia kemudian memperbaiki batas ini menjadi v 2 2 displaystyle frac v 2 2 nbsp Kemudian pada tahun 1841 P J E Finck menunjukkan 3 bahwa banyak langkah pembagian tidak mungkin lebih tinggi dari 2 log 2 v 1 displaystyle 2 log 2 v 1 nbsp dan artinya algoritme Euklides berjalan dalam waktu polinomial dari ukuran masukannya 4 Emile Leger pada tahun 1837 mempelajari kasus terburuknya yaitu ketika masukannya adalah bilangan Fibonacci yang bersebelahan 4 Analisis Finck kemudian diperbaiki oleh Gabriel Lame pada tahun 1844 5 yang menunjukkan bahwa banyak langkah yang diperlukan untuk menyelesaikan algoritme tidak pernah lebih dari lima kali banyak digit bilangan yang lebih kecil b displaystyle b nbsp 6 7 Penggunaan suntingAlgoritme ini dapat digunakan dalam konteks di mana pembagian bersisa memungkinkan Ini termasuk polinomial gelanggang dalam suatu medan juga gelanggang dari bilangan bulat Gauss dan dalam ranah Euklides umum Referensi sunting Knuth 1997 hlm 339 364 Reynaud A A L 1811 Traite d arithmetique a l usage des eleves qui se destinent a l Ecole Polytechnique edisi ke 6th Paris Courcier Note 60 p 34 Dikutip oleh Shallit 1994 Finck P J E 1841 Traite elementaire d arithmetique a l usage des candidats aux ecoles speciales dalam bahasa Prancis Derivaux a b Shallit J 1994 Origins of the analysis of the Euclidean algorithm Historia Math 21 401 419 doi 10 1006 hmat 1994 1031 Lame G 1844 Note sur la limite du nombre des divisions dans la recherche du plus grand commun diviseur entre deux nombres entiers Comptes Rendus Acad Sci dalam bahasa Prancis 19 867 870 Grossman H 1924 On the Number of Divisions in Finding a G C D The American Mathematical Monthly 31 9 443 doi 10 2307 2298146 JSTOR 2298146 Honsberger R 1976 Mathematical Gems II The Mathematical Association of America hlm 54 57 ISBN 0 88385 302 7 Bibliografi suntingKnuth D E 1997 The Art of Computer Programming Volume 2 Seminumerical Algorithms edisi ke 3rd Addison Wesley ISBN 0 201 89684 2 Pranala luar sunting nbsp Wikimedia Commons memiliki media mengenai Algortime Euklidean Inggris Weisstein Eric W Algoritme Euklidean MathWorld Templat EN Algoritme Euklides di cut the knot Algoritme Euklid di PlanetMath Binary Euclid s Algorithm Java Euclid s Game Java Diperoleh dari https id wikipedia org w index php title Algoritme Euklides amp oldid 18619223