Burak IŞIKLI :))

Dinamik Programlama(Dynamic Programming)

Posted in Algorithm, C/C++ by Burak IŞIKLI on 14 Ağustos 2009

Dinamik programlama bir problemi çözerken aynı alt-problemi birden fazla çözmemiz gereken durumlarda bu alt-problemi birden fazla kez çözmemizi engelleyen bir tekniktir. Dinamik programalama, matematik ve bilgisayar bilimlerinde karmaşık problemleri çözmek için kullanılan bir metottur. Overlapping subproblems ve optimal substructure denilen problemlerde uygunabiliyor.

Eğer problemimiz kendi içinde alt problemlere ayrılabiliyorsa overlapping subproblems’dir. Buna en iyi örnek Fibanicci serisidir. Daha önceden bu yazımda fibonacci serisini anlatmıştım.

Shortest Path Optimal SubstructureFakat problemimiz kendi içinde alt problemlere ayrıldığında daha iyi bir performans sağlıyorsa buna optimal substructure deniliyor. Buna en iyi örnek ise greedy algoritmasıdır. Dinamik programlamada geçen programlama sözcüğü sadece bilgisayar programlarını kapsamamaktadır, çünkü burada kullandığımız program sözcüğü “matematiksel programlama” dan gelmektedir, ki bu da kısaca sıkça kullandığımız optimizasyon(bir nevi iyileştirme demek optimizasyon belki kullanmayan da vardır 🙂 kelimesine denk gelmektedir.

Dinamik programlama uygulamalarımızda temel olarak 3 teknikten faydalanacağız:

  • Çözümü aynı olan alt-problemler
  • Büyük bir problemi küçük parçalara bölmek ve bu küçük parçaları kullanarak baştaki büyük problemimizin sonucuna ulaşmak
  • Çözdüğümüz her alt-problemin sonucunu bir yere not almak ve gerektiğinde bu sonucu kullanarak aynı problemi tekrar tekrar çözmeyi engellemek.

Şimdi örneğimiz olan fibonacci dizimize başlayalım. Fibonacci dizimizi kısaca bir hatırlayalım.

Eğer herhangi bir sayının Fibonacci karşılığına F(n) dersek,

F(0) = F(1) = 1 olmak üzere

F(n) = F(n-1) + F(n-2)’dir.

İlk yaptığımız prosesimizin fonksiyonunu hatırlayalım:

fib.cpp

// Recursive Function
int fib(int num) {
 if ((num == 0) || (num == 1))
 return num;
 else
 return (fib(num - 1) + fib(num - 2));
}

Bu kadar kısa bir kod yazarak çözümü sağlamıştık. Ancak bu yöntem kodun kısa olmasına rağmen performans açısından kötü bir yöntemdir.  Nedenine gelirsek mesela F(3)’ü adım adım hesaplayalım:

F(4) = (F(2) + F(1)))

= ((F(1) + F(0)) + F(1)) + F(2)

= ((F(1) + F(0)) + F(1)) + (F(1) + F(0))

Görüldüğü gibi F(4) değerini hesaplarken F(1)’ye 2 defa ihtiyacımız oldu ama 2 seferde de hesapladık. Prosesimizi değiştirerek bir de şu hale getirelim.

fib2.cpp

/*
 *
 * Program:  Fibonacci Series v2
 * Programmer: Burak ISIKLI
 *
 */

#include <iostream.h>

unsigned int fib2(unsigned int num);

unsigned int fibArray[1000];

// Main Function
int main() {
 unsigned int number, result;
 cout << "Fibonacci serisinin(fib(x)) sayisini giriniz x = ";
 cin >> number;

 result = fib2(number);
 cout << "fib( " << number << " ) = " << result << "\n\n";

 return 0;
}

unsigned int fib2(unsigned int num)
{
 unsigned int i = 2;
 fibArray[0] = fibArray[1] = 1;
 while(i <= num)
 {
 fibArray[i] = fibArray[i - 1] + fibArray[i - 2];
 i++;
 }
 return fibArray[num];
}

Burada yaptığımız işlem ise şu. Hesapladığımız Fibonacci sayılarını bir diziye kaydediyoruz. Daha sonra lazım olunca bu değerleri direkt diziden hazır bi şekilde alıyoruz. Böylece aynı işlemi tekrar tekrar yapmaktan kurtuluyoruz.

Performans karşılaştırması yapacak olursak kendi bilgisayarımda fibonacci(50) 8dk. 36 sn’de sonuç verirken fibonacci2(50) 0.003 sn’de sonuç veriyor. Daha bilimsel konuşacak olursak problemi temelde aynı mantıkla çalışan iki fonksiyonun birincisi O(2^n) iken ikincisi O(n) zamanda çözmektedir.

Kaynaklar:

http://en.wikipedia.org/wiki/Dynamic_programming

http://en.wikipedia.org/wiki/Optimal_substructure

http://e-bergi.com/2008/Mart/Dinamik-Programlama

/*
 *
 * Program:  Fibonacci Series v2
 * Programmer: Burak ISIKLI
 *
 */

#include <iostream.h>

unsigned int fib2(unsigned int num);

unsigned int fibArray[1000];

// Main Function
int main() {
 unsigned int number, result;
 cout << "Fibonacci serisinin(fib(x)) sayisini giriniz x = ";
 cin >> number;

 result = fib2(number);
 cout << "fib( " << number << " ) = " << result << "\n\n";

 return 0;
}

unsigned int fib2(unsigned int num)
{
 unsigned int i = 2;
 fibArray[0] = fibArray[1] = 1;
 while(i <= num)
 {
 fibArray[i] = fibArray[i - 1] + fibArray[i - 2];
 i++;
 }
 return fibArray[num];
}

Asal Sayı(Prime Number) Algoritması:

Posted in Algorithm, C/C++ by Burak IŞIKLI on 24 Temmuz 2009

Bir forumda gördüğüm konu üzerine ufak bir araştırma yaptım. Konuda asal sayıların bulma algoritmasının nasıl olacağı soruluyordu. Bu soru iki şekilde anlaşılabilir. Birincisi verilen sayının asal sayı olup olmadığı, ikincisi ise verilen sayı aralığındaki bütün asal sayıların bulunmasıdır. Öncelikle asal sayının ne olduğunu hatırlayalım.

Asal sayılar’, yalnız ve yalnız iki böleni olan doğal sayılardır. Kendisinden ve 1 sayısından başka böleni olmayan, 1’den büyük pozitif tam sayılar biçiminde de tanımlanmaktadır.(kendisinden küçük asal sayıların hiçbirine tam bölünmeyen sayılardır) Yüzden küçük asal sayılar 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89 ve 97 dir. Tam listesi için burayı tıklayın.

Şimdi birinci algoritmamızı yapalım. Bu algoritmada tanımdan gidiyoruz. “Sayı kendisinden ve 1’den başka sayıya bölünemez”. Boolean fonksiyonu ve for döngüsü yardımıyla herhangi bir sayıyı bölündüğünü yakaladığımız takdirde false döndürerek asal sayı olmadığına karar veriyoruz. Bu algoritmanın çözüm karmaşıklığı O(n)’dir.

Prime.cpp

/*
 * Process:  Prime Number
 * Programmer: Burak ISIKLI
 *
 */

#include<iostream.h>

bool isPrimeNumber(long int num);

int main() {
 long int number;
 cout << "Find primes: ";
 cin >> number;

 if (isPrimeNumber(number))
 cout << endl << number << ", is a prime number" << endl;
 else
 cout << endl << number << ", isn't a prime number" << endl;

 return 0;
}

bool isPrimeNumber(long int num) {
 for (long int i = 2; i < num; i++) {
 if (num % i == 0)
 return false;
 }
 return true;
}

Bu prosesimiz bize Çözmek istediğimiz sayıyı soruyor. Öğrenmek istediğimiz sayıyı girdiğimizde sayının asal olup olmadığını söylüyor.

Peki ama bu algoritmayı daha verimli yapamaz mıyız? Elbette yapabiliriz. Eğer n sayımızın şu şekilde bir fonksiyon aralığında olduğunu düşünürsek d (1 < d < n) ve bu fonksiyonun tamamının karekökünü alırsak d0 (1 < d0 < √n) şeklinde bir fonksiyon elde ederiz. Eğer n sayımızın tamamen karekökü alınabiliyorsa mükemmel karedir ancak asal değildir. Aksi halde farzedelimki ilk bulduğumuz bölüm d1,  √n < d1 < n olsun. Ama n, √n’den az olan d2 = n / d1 tarafından tamamen bölünüyor. Bu nedenle tahmin yanlıştır ve eğer √n’den daha büyük bir bölen varsa o zaman çifti √n’den azdır. Böylelikle ifademiz kanıtlanmış oldu.

Son olarak kodumuzu vermeden bir iyileştirmeden daha bahsetmeliyim. Farz edelimki n tek bir sayı(2 bölen olamaz) olsun. Eğer n 2’ye kalansız bölünemiyorsa başka hiçbir çift sayıya tamamen bölünemez. İşte bu iyileştirmeden sonra değişen algoritmamız ve prosesimiz şu şekilde oluyor:

Prime.v2.cpp

/*
 * Process:  Prime Number
 * Programmer: Burak ISIKLI
 *
 */

#include<iostream.h>
#include<math.h>

bool isPrimeNumber(long int num);

int main() {
 long int number;
 cout << "Find primes: ";
 cin >> number;

 if (isPrimeNumber(number))
 cout << endl << number << ", is a prime number" << endl;
 else
 cout << endl << number << ", isn't a prime number" << endl;

 return 0;
}

bool isPrimeNumber(long int num) {
 if (number == 2)
 return true;
 if (number % 2 == 0)
 return false;
 for (long int i = 3; i <= (long int) sqrt((double) num); i++) {
 if (num % i == 0)
 return false;
 }
 return true;
}

Bu algoritmamızın iyileştirmelerden sonraki çözüm karmaşıklığı O(√n / ln(n)) oldu.

İkinci algoritma girilen sayı aralığına kadar asal sayıları listeleme. Aslında bunun için özelleşmiş spesifik bir algoritma mevcut. “Sieve Algoritması” adı verilen algoritmanın çözüm karmaşıklığı O(n1 / 2loglogn / logn)’dir.

Sieve.cpp


/*
 * Process:  Prime Number - Sieve Algorithm
 * Programmer: Burak ISIKLI
 *
 */

#include <iostream.h>
#include <math.h>
#include <assert.h>
#include <time.h>

int main() {
 int i;
 clock_t start, stop;
 double t = 0.0;
 cout << "Find primes up to: ";
 cin >> i;

 assert((start = clock())!=-1);

 //create prime list
 int prime[i];
 int c1, c2, c3;

 //fill list with 0 - prime
 for (c1 = 2; c1 <= i; c1++) {
 prime[c1] = 0;
 }

 //set 0 and 1 as not prime
 prime[0] = 1;
 prime[1] = 1;

 //find primes then eliminate their multiples (0 = prime, 1 = composite)
 for (c2 = 2; c2 <= (int) sqrt(i) + 1; c2++) {
 if (prime[c2] == 0) {
 c1 = c2;
 for (c3 = 2 * c1; c3 <= i + 1; c3 = c3 + c1) {
 prime[c3] = 1;
 }
 }
 }

 stop = clock();
 t = stop - start;

 //print primes
 for (c1 = 0; c1 < i + 1; c1++) {
 if (prime[c1] == 0)
 cout << c1 << "\t";
 }
 cout << endl << "Run time: " << t << endl; //print time to find primes

 return 0;
}

Bu prosesimiz bize hangi sayıya kadar bulmak istediğimizi soruyor. Sayıyı girdiğimiz takdirde asal sayıları listeleyip çalışma süresini yazıyor.

Asal sayılar özellikle şifreleme(cryptography) alanında sıkça kullanılan bir konudur. Örneğin bizden 100 basamaklı asal sayı üretilmesi istense, görünüş olarak algoritmamız iyi bir zamanda sayıları kontrol edemez. İşte bu nedenle bizim algoritmamız pratikte kullanılmak amacıyla uygulanmıştır. Ancak büyük sayıların asal olup olmadığını test etmek istediğimizde olasılıksal algoritma(probabilistic algorithm) kullanılır.

Kaynaklar:

http://tr.wikipedia.org/wiki/Asal_say%C4%B1

http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes

http://www.dreamincode.net/code/snippet3315.htm

http://mathworld.wolfram.com/PrimeNumber.html

http://www.algolist.net/Algorithms/Number_theoretic_algorithms/Sieve_of_Eratosthenes

Faktoriyel(Factorial) Bulma

Posted in Algorithm, C/C++ by Burak IŞIKLI on 15 Haziran 2009

Rekürsif fonksiyolarda kullanılan en sık örneklerden biri de faktoriyel bulmadır. Bildiğiniz üzere faktoriyel örneğin 5 faktoriyel=5!=5*4*3*2*1 şeklinde sayıdan geriye giderek 0’a kadar çarpılır. Ancak 0! ve 1! 1’e eşittir.

// Program:  Factorial Number
// Programmer: Burak ISIKLI

#include

// Prototype Function
int fac(int num);

// Main Function
int main()
{
int number, result;
cout << "Lutfen hesaplatacaginiz sayiyi giriniz: x!= "; cin >> number;
result = fac(number);
cout << number << "! = " << result << "\n\n"; return 0; } // Recursive Function int fac(int num) { if(num == 0 || num == 1) return 1; else return num * fac(num-1); } [/sourcecode] Kullanıcıya sayıyı sorup hesaplatıp ekrana yazdıran basit bir faktoriyel bulma programıdır.