YGS-LYS Ders Notları ve YGS-LYS PDF Kitaplar


Konuyu Oyla:
  • Toplam: 2 Oy - Ortalama: 2
  • 1
  • 2
  • 3
  • 4
  • 5

Öklid Algoritması


Öklid Algoritması konusu, 11.SINIF forumunda tartışılıyor.
#1
Öklid Algoritması


İki A ve B tam sayısının Ortak Bölenlerinin En Büyüğünün (OBEB), A ve B'yi bölen en büyük tam sayı olduğunu hatırlayalım.
Öklid Algoritması, iki tam sayının OBEB'ini hızlıca bulmak için kullanılan bir yöntemdir.
Algoritma
OBEB(A,B)'nin bulunması için Öklid Algoritması şu şekildedir:
  • Eğer A=0 ise, OBEB(0,B)=B olacağı için OBEB(A,B)=B olur ve bu noktada durabiliriz. 
  • Eğer B=0 ise, OBEB(A,0)=A olacağı için OBEB(A,B)=A olur ve bu noktada durabiliriz. 
  • A sayısını bölüm ve kalan formunda yazın (A=B⋅Q+R)
  • OBEB(A,B)=OBEB(B,R) olduğu için, OBEB(B,R)'yi Öklid Algoritmasını kullanarak bulun

Example:
270 ve 192'nin OBEB'ini bulun
  • A=270, B=192
  • A ≠0
  • B ≠0
  • Bölme yapılarak, bölüm 270/192 = 1 ve kalan 78 olarak bulunr. Bu işlemi 270 = 192 * 1 +78 şeklinde de yazabiliriz
  • OBEB(270,192)=OBEB(192,78) olduğu için OBEB(192,78)'i bulun

    A=192, B=78
  • A ≠0
  • B ≠0
  • Bölme yaparak, bölüm 192/78 = 2 ve kalan 36 olarak bulun. Bunu şöyle yazabiliriz:
  • 192 = 78 * 2 + 36
  • OBEB(192,78)=OBEB(78,36) olduğu için, OBEB(78,36)'yı bulun

    A=78, B=36
  • A ≠0
  • B ≠0
  • Bölme yapılarak, bölüm 78/36 = 2 ve kalan 6 olarak bulun. Bunu şöyle yazabiliriz:
  • 78 = 36 * 2 + 6
  • OBEB(78,36)=OBEB(36,6) olduğu için, OBEB(36,6)'yı bulun

    A=36, B=6
  • A ≠0
  • B ≠0
  • Bölme yapılarak, bölüm 36/6 = 6 ve kalan 0 olarak bulunur. Bunu şöyle yazabiliriz:
  • 36 = 6 * 6 + 0
  • OBEB(36,6)=OBEB(6,0) olduğu için, OBEB(6,0)'yı bulun

A=6, B=0
  • A ≠0
  • B =0, GCD(6,0)=6

Böylece şunu göstermiş olduk:
OBEB(270,192) = OBEB(192,78) = OBEB(78,36) = OBEB(36,6) = OBEB(6,0) = 6
OBEB(270,192) = 6
 
Öklid Algoritmasını Anlamak
 
Öklid Algoritmasını incelersek, aşağıdaki özellikleri kullandığını görürüz:
  • OBEB(A,0) = A
  • OBEB(0,B) = B
  • Eğer A = B⋅Q + R ve B≠0 ise bu durumda OBEB(A,B) = OBEB(B,R) burada Q bir tam sayıdır, R 0 ve B-1 arasında bir tam sayıdır

İlk iki özellik, iki sayıdan birinin 0 olması durumunda OBEB'i bulmamızı sağlar. Üçüncü özellik ise, daha büyük ve zor sayıları alıp, daha küçük, basit sayılara indirgeyerek problemi çözmemizi sağlar.
Öklid Algoritması, üçüncü özelliği sayesinde problemin hızla ve ilk iki özellik kullanılarak çözülebilecek hale gelene kadar daha basit problemlere dönüştürülerek çözülmesini sağlar.
Bu özelliklerin neden işe yaradığını onları ispatlayarak anlayabiliriz.
OBEB(A,0)=A özelliğinin ispatı şu şekildedir:
  • A'yı kalansız bölebilecek en büyük tam sayı A'nın kendisidir.
  • Herhangi bir C tam sayısı için C⋅ 0 = 0 olduğu için, bütün tam sayılar 0'ı kalansız bölebilir. Öyleyse A tam sayısının da 0'ı kalansız bölebileceği sonucuna varabiliriz.
  • A ve 0'ı bölen en büyük tam sayı, A tam sayısıdır.

OBEBO(0,B)=B özelliğinin ispatı da hemen hemen aynıdır. (İspat aynıdır, ancak A yerine B koyarız).
OBEB(A,B)=OBEB(B,R) olduğunu ispatlayabilmemiz için, önceOBEB(A,B)=OBEB(B,A-B) olduğunu göstermemiz gereklidir.
d6568dc48504e7a948ceffc61de4802868d28f76.pngA-B=C koşuluyla A,B ve C diye üç tam sayımız olduğunu varsayalım.
OBEB(A,B)'nin C'yi kalansız böldüğünün ispatı
Tanıma göre OBEB(A,B)'nin A'yı kalansız böldüğünü biliyoruz. Bu durumda, A tam sayısı OBEB(A,B)'nin bir katı olmalıdır. Yani, X⋅OBEB(A,B)=A, burada X bir tam sayıdır
Gene tanımı nedeniyle OBEB(A,B)'nin B'yi kalansız böldüğünü biliyoruz. Bu durumda, B tam sayısı OBEB(A,B)'nin bir katı olmalıdır. Yani, Y⋅OBEB(A,B)=B, burada Y bir tam sayıdır
A-B=C bize şunu verir:
  • X⋅OBEB(A,B) - Y⋅OBEB(A,B) = C
  • (X - Y)⋅OBEB(A,B) = C

Böylelikle, OBEB(A,B)'nin C'yi kalansız böldüğünü görmüş oluyoruz.
Bu ispatın bir örneği, aşağıdaki şeklin sol kısmında gösterilmiştir:
6b6e1950ccd637d77235017c258b86378a4cba54.pngOBEB(B,C)'nin A'yı kalansız böldüğünün ispatı
Tanıma göre, OBEB(B,C)'nin B'yı kalansız böldüğünü biliyoruz. Bu durumda, B tam sayısı OBEB(B,C)'nin bir katı olmalıdır. Yani, M⋅OBEB(B,C)=B, burada M bir tam sayıdır
Tanıma göre OBEB(B,C)'nin C'yi kalansız böldüğünü biliyoruz. Bu durumda, C tam sayısı OBEB(B,C)'nin bir katı olmalıdır. Yani, N⋅GCD(B,C)=C, burada N bir tam sayıdır
A-B=C bize şunu verir:
  • B+C=A
  • M⋅OBEB(B,C) + N⋅OBEB(B,C) = A
  • (M + N)⋅OBEB(B,C) = A

Böylelikle, OBEB(B,C)'nin A'yı kalansız böldüğünü görmüş oluyoruz.
Bu ispatın bir örneği, aşağıdaki şekilde gösterilmiştir:
bdaae4e94ab086d57f14df18ee01abf5f36f49e4.pngOBEB(A,B)=OBEB(A,A-B) olduğunun ispatı
  • Tanımı gereği, OBEB(A,B), B tam sayısını kalansız böler.
  • OBEB(A,B)'nin C tam sayısını kalansız böldüğünü zaten ispatlamıştık.
  • OBEB(A,B) hem B'yi, hem de C'yi kalansız böldüğü için, B ve C'nin ortak bölenlerinden biridir.

OBEB(A,B), OBEB(B,C)'den küçük veya OBEB(B,C)'ye eşit olmalıdır; çünkü OBEB(B,C), B ve C tam sayılarının “en büyük” ortak bölenidir.
  • Tanımı gereği, OBEB(B,C), B tam sayısını kalansız böler.
  • OBEB(B,C)'nin A'yı kalansız böldüğünü zaten ispatlamıştık.
  • OBEB(B,C) hem A'yı, hem de B'yi kalansız böldüğü için, A ve B'nin ortak bölenlerinden biridir.

OBEB(B,C), OBEB(A,B)'den küçük veya OBEB(A,B)'ye eşit olmalıdır; çünkü OBEB(A,B), A ve B tam sayılarının “en büyük” ortak bölenidir.
OBEB(A,B)≤OBEB(B,C) ve OBEB(B,C)≤OBEB(A,B) özellikleri sayesinde, şu sonuca varabiliriz:
OBEB(A,B)=OBEB(B,C)
Bu, şuna eşittir:
OBEB(A,B)=OBEB(B,A-B)
Bu ispatın bir örneği, aşağıdaki şeklin sağ kısmında gösterilmiştir.
d6568dc48504e7a948ceffc61de4802868d28f76.pngOBEB(A,B) = OBEB(B,R) olduğunun ispatı
OBEB(A,B)=OBEB(B,A-B) olduğunu ispatladık
Terimlerin sırası önemli olmadığından, OBEB(A,B)=OBEB(A-B,B) diyebiliriz
OBEB(A,B)=OBEB(A-B,B) özelliğini tekrar tekrar uygulayarak şu sonuca ulaşabiliriz:
OBEB(A,B)=OBEB(A-B,B)=OBEB(A-2B,B)=OBEB(A-3B,B)=...=OBEB(A-Q⋅B,B)
Ancak A= B⋅Q + R olduğundan, A-Q⋅B = R olur
Böylece OBEB(A,B)=OBEB(R,B) olur
Terimlerin sırası önemli olmadığı için, şöyle de diyebiliriz:
OBEB(A,B)=OBEB(B,R)
Bir sonraki makalemizde, Öklid Algoritmasının kullanımıyla modüler ters çarpanların nasıl bulunabileceğini göstereceğiz.



(https://tr.khanacademy.org/ sitesinden alınmıştır)

Ara
Cevapla
|


[-]
Hızlı Cevap
Konu


Güvenlik Kodu:
Lütfen, resmin üzerindeki harf ve rakamlardan oluşan Güvenlik Kodunu, aşağıdaki metin kutusuna giriniz.

Anahtar Kelimeler

Öklid Algoritması, Öklid Algoritması indir, Öklid Algoritması Videosu, Öklid Algoritması online izle, Öklid Algoritması Bedava indir, Öklid Algoritması Yükle, Öklid Algoritması Hakkında, Öklid Algoritması nedir, Öklid Algoritması Free indir, Öklid Algoritması oyunu, Öklid Algoritması download


Hızlı Menü:


Konuyu Okuyanlar: 1 Ziyaretçi

 

Yandex.Metrica