Sayılabilirlik Teorisi

      Sayılabilirlik Teorisi

      Programlamada bir çok alışkanlık vardır. Bu alışkanlıklardan biri de bütün sayı serilerini sayma sayılara çevirme alışkanlığıdır.
      Sayma sayıların ne olduğunu hatırlamak ile başlayalım. {1,2,3,4,5,...} şeklinde 1'den başlayarak sonsuza kadar giden sayı serisine sayma sayıları deriz. Yani bizim günlük hayatımızda yaptığımız, sayıları sayma şekli. Sayılabilirlik teorisine göre amacımız, sayma sayılar serisi hariç, bütün sayı serilerini sayma sayılarına çevirmektir.

      Örneğin 10'dan 20'ye kadar olan ve üçe tam bölünebilen sayıları ekranda yazdırmak isteyelim. Bu durum için 10'dan 20'ye kadar olan sayıları tek tek test edip, üçe tam bölünenleri bulup,onları ekrana yazdıran bir kod yazabiliriz.

      Source Code

      1. for (int i = 10; i < 20; i++)
      2. if (i % 3 == 0)
      3. printf("%d\n",i);

      Ve ya bu sayı serisinin {12,15,18,...} şeklinde olduğunu düşünür isek, sayaç değişkenini 12'den 20'ye kadar ayarlayıp,her seferinde üçer üçer arttıran bir kodda yazabiliriz.

      Source Code

      1. for (int i = 12; i < 20; i += 3)
      2. printf("%d\n",i);


      Peki size:
      1 verildiğinde 12
      2 verildiğinde 15
      3 verildiğinde 18
      Değerlerini çıkartan bir formül ve ya bir fonksiyon oluşturun desem? İşte herhangi bir sayı serisini, bu şekilde sayma sayıları şeklinde yazmak sayılabilirlik teorisidir.

      Bu örnek için oluşturacağımız matematiksel fonksiyon şu şekilde olabilir:
      f(x) = 9 + (3*x)
      Şeklinde bir fonksiyon oluşturulabilir.

      f(1) = 9 + (3*1) = 12
      f(2) = 9 + (3*2) = 15
      f(3) = 9 + (3*3) = 18

      Görüldüğü gibi seri sürekli 3 arttığı için,sayma sayılarını 3 ile çarptık ve sonucu 9'a ekledik.Şimdi bu yaptığımız formülü koda dökelim:

      Source Code

      1. for (int i = 1; i <= 3; i++)
      2. printf("%d\n",9 + (3*i));
      Bu kod ile elde etmek istediğimiz sayı serisi olan {12,15,18} serisini sayma sayıları şeklinde yazmış olduk. Burada yapılan tek şey,döngünün {1,2,3,4,5,...} şeklinde yani sayma sayıları şeklinde gitmesini sağlayıp, sayac değişkenin değerlerini az önce oluşturduğumuz formüle soktuk ve istediğimiz sayı değerlerini sayma sayılarını kullanarak elde ettik.

      Aynı formülün fonksiyonlar ile kullanılmış hali:

      Source Code

      1. int f(int x){
      2. return 9 + (3 * x);
      3. }
      4. int main()
      5. {
      6. for (int i = 1; i <= 3; i++)
      7. printf("%d\n",f(i));
      8. }

      Burada oluşturduğumuz formülü bir fonksiyonun içine attık ve for döngüsü ile her seferinde fonksiyonun parametre olarak sayma sayılar almasını sağladık.

      Başka bir örnek, {10,30,60,100...} serisini sayılabilirlik teorisi ile ekrana yazdırmak isteyelim.
      Sayılar arasındaki ilişkiye bakar isek,10'dan 30'a yirmi lik bir artış söz konusu. 30'dan 60'a otuz luk bir artış söz konusu. 60'dan 100'e ise 40 lık bir artış söz konusu.

      Yani artış miktarı en başta 20 den başlayarak,her adımda 10 artmış. Fark önce 20 iken,sırası ile 30 ve 40 olmuş.

      Bu durum için şöyle bir algoritma kurulabilir:
      10*1 + 0 = 10
      10*2 + 10 = 30
      10*3 + 30 = 60
      10*4 + 60 = 100
      Bu formülde öncelik ile verilen sayma sayısı ile 10 sayını çarptık ve bir önceki formülün sonucunu ekledik. Tersten bakalım ve 4 verildiğini farz edelim,10 ile 4 çarpılacak ve bir önceki formülün sonucu yani formüle 3 verildiği zamanki sonuç eklenecek.
      Formüle 3 verildiği zaman 60 olduğuna göre,4 verildiği zamanki sonuç (10*4) + 60 = 100 olur. 3 verildiği zamanda 10*3 + iki verildiği zamanki sonuç yani 10*3 + 30 dan 60.
      Tabi bir sınır noktası koymazsak sonsuza kadar giden bir işlem olur bu yüzden 0 verildiği zamanki değeri 0 olarak varsayacağız.

      Şimdi kodunu yazalım:

      Source Code

      1. int x = 0;
      2. for (int i = 1; i <= 4; i++) {
      3. x = 10 * i + x;
      4. printf("%d\n", x);
      5. }

      Burada x adında bir değişken oluşturduk ve ilk değer olarak 0 atadık. Bu değişkenin yaptığı iş bir önceki işlemden kalan sonucu tutup bu sonucu yeni işleme eklemesidir.

      Bu formülü fonksiyon halinde yazacak olursak:
      f(0) = 0 koşulu ile
      f(x) = 10*x + f(x-1) şeklinde olabilir.
      Görüldüğü üzere bu özyinelemeli(Recursive) bir fonksiyondur. Bu durumda bunu Recursive fonksiyon olarak programlayabiliriz.

      Source Code

      1. int f(int x){
      2. if (x == 0)
      3. return 0;
      4. return 10 * x + f(x - 1);
      5. }
      6. int main()
      7. {
      8. for (int i = 4; i >= 1; i--)
      9. printf("%d\n",f(i));
      10. }


      Görüldüğü gibi, bir çok sayı serisini sayma sayılara indirgeyerek yazabiliriz. Bir çok diyorum çünkü bazı seriler sayma sayılara indirgenemiyor. Örneğin asal sayılar. Matematikte asal sayıların birbirleri ile olan ilişkisi halen bulunamadığından, asal sayıları veren bir fonksiyon yoktur. Dolayısı ile bunu sayılabilirlik teorisi ile yapamayız. Asal sayıları ekrana yazdırmanın tek yolu, sayıları tek tek test edip asal olanları ekrana yazdıran bir kod yazmaktır. Ama sayıları hiç test etmeden direk verilen sayma sayılarından hesaplayan bir kod yazılamıyor. Tabi ilerde asal sayılar arasındaki ilişki bulunur ise böyle bir kodda yazabilir :D

      Post was edited 2 times, last by “LifeHunter” ().

      TheDemenio wrote:

      Anlatım tarzın çok güzel hocam. Okurken çok keyif aldım ^^ Teşekkür etmeden geçmeyim dedim. Ellerine sağlık. İlgilenen arkadaşlara "Ayrık Matematik" hakkında ufak bir araştırma yapmalarını da tavsiye ederim.
      Teşekkürler hocam :D Ayrık matematik bence de kesinlikle araştırılması ve üzerinde düşünülmesi gereken bir konu. Bilgisayar biliminin en temel konularından biri.
      Evet bu formüller belli bir yere kadar olan asal sayıları veriyor ama dediğin gibi sadece belli sayıları veriyor. Bütün asal sayıların bulunabileceği tek bir formül ve ya sadece asal sayıları veren bir formül yok şu an. Çünkü sayılar büyüdükçe var olan asal sayıların azaldığı görülüyor. Örneğin 1 ile 1000 arasında 168 tane asal sayı varken, 1000 ile 2000 arasında 135 tane asal sayı var. Bundan dolayı bütün asal sayıları veren bir fonksiyonun oluşturabileceğine imkansız gözü ile bakılıyor. Tabi tarihte imkansız olarak düşünülen çoğu şey zamanında yapılmıştır. O yüzden böyle bir formülün olup olmayacağını zaman gösterecek.
      Asallarla ilgili bende şöyle ufak bilgiler ekleyim:



      devamı için şu dosayaya bakabilirsiniz : ​[url]http://home.anadolu.edu.tr/~eakyar/dersler/ayrik/sunumlar/sunum_06.pdf[/url] Bir formül oluşturulamamasının en büyük sebebi bu aslında. Aralarında 2 fark olandan milyon fark olanlara kadar tamamen düzensiz bir şekilde sıralanıyorlar. Bu özelliğinden dolayı asal sayılar şifrelemede de kullanılıyor.