30 Nisan 2015 Perşembe

İTERATİF VE REKURSİF FONKSİYONLAR

İTERATİF VE REKURSİF FONKSİYONLAR
İteratif fonksiyonlar ve rekürsif fonksiyonları öncelikle kısaca hatırlıyalım daha sonra  ise bunlarla ilgili örnekler çözelim

İteratif fonksiyonlar:
İteratif fonksiyona kısaca basit,hantal ya da kendisine verilen görevi yerine getireye çalışan fonksiyonlar diyoruz yani sadece verilen işi yapar geriye bir şey döndürmeyen fonksiyon grupları diyebiliriz   bunda normal kodlamada yaptığımız işlemlerdir  ancak kimi yerde rekürsif kimi yerde ise iteratifi kullanmak daha avantajlıdır zaten Algoritma analizi dersinide bunun için alıyoruz
Şunuda bilmekte yarar var ki mecbur kalmadıkca Rekürsif fonksiyonlara tercih etmemek en iyisidir çünkü Algoritma analalizinde bilinen iki önemli kıstas vardır 1-)Zaman 2-)Hafıza  bunun içindir ki iteratif fonksiyonlar basit olmasından dolayı rekürsif fonksiyonlara göre daha hızlı çalışır ve daha az yer kaplamaktadır

Rekürsif Fonksiyonlar
Rekürsif fonksiyonlar Dinamik programlama  diyebiliriz yani kendisini kullanarak sonuç bulan fonksiyon örneğidir 
Rekürsif fonksiyonlardan olmazsa olmaz 3 şartları:
1-)Başlangıç değerleri
2-)Bitiş değeri
3-)adım değerleri

ÖRNEK:  Faktöriyelin hesabını Rekürsif ile yapalım
                     { 1            n=0  }
F(n)=
                     {n*f(n-1)           }

Örnek 91! İşlemini yapalım
               {1          n=0 }
F(98)=
               {98*F(97)   }


ÖNEMLİ NOT:Rekürsif fonksiyondan iteratif fonksiyona geçiş sağlandığında sonuça daha çok yaklaşırız ve gerek çözümleme gereksede Bilgisayar kodlaması daha kolay bir işlemdir
Rekürsif Fonksiyonlar  ve İteratif Fonksiyonlar Bilgisayar kodu:

8
9
10
11
12
13
14
15
16
//recursive Faktoriyel Hesaplama
public int FaktoriyelRecursive(int n)
{
    if (n <= 1)    // Sonlandırma şartı
        return 1;
    return n * FaktoriyelRecursive(n - 1); // 1 azaltarak kendini çağrıyor
}

//iteratif Faktoriyel Hesaplama
public int FaktoriyelIteratif(int n)
{
    int sonuc = 1;
    for(int i = 1; i <= n; i++)
        sonuc *= i;
    return sonuc;
}



GREEDY ALGORİTMASI

                    GREEDY ALGORİTMASI
Greedy Algoritması,Graf üzerinde belirli bir konuda optimizasyonu sağlamaktadır yani sonuca en yakın ve en iyi sonucu bulabilmek için graf üzerinde dolaşma yaparken bir sonraki düğümü belirlemek için kullanılan bir karar verme mekanizması üerine kurulmuştur
Greedy Algoritması için o an ki secenekler içerisnde en iyi olarak görünen seçilir ve sonuça yaklaşımını daha yakın olmasıdır ve Greedy Yönlü ve maliyetli graflarda kullanabilmekteyiz
Greedy algoritması grafta çözümbulunurken en derine inmeden yüzeysel olarak ilerler bu durum diğer yaklaşımları için örnek teşkil eder ve diğer seçeneklere bakmamıza yarar sağlar
Kısaca bazı sorular vardır ki  bunu tahminen veyya sezgisel olarak çözmemiz gerekmektedir işte bunu sağlayan Greedy Algoritmasıdır
Ancak bu durum her zaman bize doğru sonucu vermez bazende yanıltıcı olabilmektedir ve durumu kullanabilmek içinde şöyle yaparsak önce matematiksel olarak çözersek sonra Greedy algoritmasını kullanırsak sonuç itibariyle daha iyi olur beklenmeyen sonuçlardan arındırılmış olunur


Greedy algoritmasına en iyi örnek kruskal verebiliriz

Dinamik Prgramlama

           DİNAMİK PROGRAMLAMA
Dinamik Programlama Bilgisayar Mühendisliğinde olsun gereksede diğer Mühendislik alanlarında olsun sürekli karşılaşılaşılan önemli bir algoritmadır öyleki  karışık problemlerin daha basit hale indirererek çözülmesi yönünde kolaylık sağlıyan yani bilgisayar Dili olarak söylemek istersem Optimizasyonunu sağlamaktadır
Dinamik programlama amaç problemin alt problemlere parçalayarak ve parçalarkende bir önceki konumunu kouycak şekilde parçalanır başka problemlere dönüştürülerek çözüme giden bir yol olmasıda bizim için yeterli ve aranan bir yoldur amaç zaten problemi çözmektir nasıl ki rekürsif fonksiyonları iteratife dönüştürüp oradan sonuça ulaşmaya çalışılıyorsa dinamikte kolaylık ya da başka forma dönüştürülüp çözme işini sağlamaktadır
Yönteme göre optimum çözüm başlangıç durumundan bağımsız olarak diğer çözümler ile çözüm sonuçlarına göre optimum çözümler birbirinin devamı şeklindedir yani önce alt probleme bölüp daha sonra daha detaylı alt problemler bölüp sonucu bulmaya çalışılıcak

Başka sorulacak soru peki bu Dinamik problemleri nerede kullanabiliriz ? bunun için şöyle söyleyebiliriz  çözümlü olarak daha küçük problemlere parçalanabilen tüm problemlere uygulanabilmekteyiz örneğin Fibonacci normal zaman karmaşıklı O(n^2) ike Dimaikle çözümlendiğinde O(n) yapılabilir bunun bize sağladığı yarar o kadar büyük ki neredeyse sorun yok denecek kadar hafife indirgenmiş oluyor bununla beraber.

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
1
2
3
4
5
6
7
// 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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
/*
 *
 * 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.


BACKTRACKİNG


                   BACKTRACKİNG
Backtracking nedir sorusuyla cevaplayalım Backtracking ingilizceden Türkceye çevirirsek  Geri İzleme anlamına gelmektedir  ve bilgisayar biliminde bir hedefe ulaşmak için  kullanılan Algoritmarından bir tanesidir
Burada bir amaç bulunmalı ve amaca ulaşan farklı yollar arasında bir doğru seçim aranıyor olmalıdır.Örneğin bulmacalarda bulmacalarda kalsikleşmiş olan iki boyutlu labirentler Geri İzleme algortimaları ( Back Tracking  Algoritması) diye söyleyebiliriz
Ve bu örnekte labirentin bir ucundan başlanır ve diğer ucuna kadar çeşitli yollar deneyererek devam edilir  ancak çıkmaz bir sokak yani çıkmaz bir alan gördüğünde en son yol ayrımına kadar  geri gelinip farklı bir yol bularak soruya çözmeye çalışırız ve bunun sonunda doğru yola ulaşmak olasıdır.

2. bir örnekte vermek gerekirse  8 Vezir örneği bu vezirler birbirini yemeden santraç tahtası üzerinde 64 karede 8 tane vezirin birbirini yemeden tahtanın üzerine yerleştirelim  eğer bir vezir diğeri yiyorsa o zaman en son yerlşetirmeden önceki konuma gelip doğru tahta üzerine konumlandıralım yani BackTracking örneği çözmeş oluruz


LOOP İNVARİANT

------------------------LOOP İNVARİANT-------------------------

Bilgisayar bilimlerinde, bir programın incelenmesi sırasında, çeşitli işlemler uygulanmasına karşılık yeknesan olması halidir.Diğer bir deyişle, program çalışır ve çeşitli işlemlerden geçer, ancak bazı şeyler değişmeden kalıyor ve ne kadar işlem yapılırsa yapılsın değişmiyorsa buna yeknesan (değişmez, invariant) ismi verilir.En basit örneği, bir değişkenin (variable) içine değer atanması ama hiç değiştirilememesidir.
int a = 10;
// işlemler
printf("%d",a);
Yukarıdkai kodda, a değerini ilgilendiren işlemler yapılmıyorsa, a için yeknesan olmuş denilebilir. Farklı bir örnek de döngülerde görülür:
for(int i = 0;i<10;i++){
   printf("%d",i);
}
Yukarıdaki döngüde, i<10 şartında bulunan 10’dan küçük olma şartı yeknesan olmuştur. Yani döngünün dönmesi sırasında değişmeden kalmaktadır. Hemen bu noktada önemli bir farkı belirtmek gerekir. Yeknesean kavramı, sabit kavramı ile (constant) karıştırılabilmektedir. Örneğin yukarıdaki döngüde bulunan 10 sayısı bir sabittir ve yeknesan değildir. 10’dan küçük olma durumu ise değişmeden kalan bir yeknesan olarak düşünülmelidir.
Yukarıdaki tip yeknesan örneklerine, özel olarak daire yeknesanı (loop invariant, döngü değişmezi) ismi de verilebilir.
Bu yaklaşım, ayrıca program analizi veya problem analizi sırasında da kullanılabilir. Örneğin MU Probleminin çözümünde, yeknesan bir değer yakalamaya çalışmak gerekir. Benzer şekilde Hoare Mantığı (Hoare Logic), programların belirli bölümlerinde, ön ve son koşullar belirleyerek bunların yeknesan olmasını sağlamaktadır.
Bu yöntem, bilgisayar bilimleri dışında da kullanılır. Örneğin, kanun yapım sürecinde, bütün kanunlarda değişmeyen kötü hasletler vardır. Bu yüzden, hırsızlık veya cinayet gibi suçlar, kanunlar değişmesine karşılık, bütün kanunlarda yerini almaktadır. Bu anlamda, değişen kanun sistemleri için, hırsızlık, yeknesan bir suçtur denilebilir.


RECURSİF HESAPLANMASI

-----------------------Algoritma Analizi Recursif ifadeler------------------
RECURSİF HESAPLANMASI
Resürsif algoritması eğer bilgisayarımızn işlemci güçü iyi ise çok  iyi sonuçlar vermektedir eğer işlemcimiz normal ve biz recursif ifade kullandığımızda inanılmaz bir şekilde bilgisayarın ısınmasına sebeb olacak çünkü recursif ifadeler kendi kendini çağıran metotlardan oluşmaktadır aslında recursif ifadeler kod yazarken  kod yazmamız daha kolay oluyor iteratife göre ancak bazen recursif ifade de çalışmak zor ve karmaşıktır örneğin gezign satıc örneğinde olduğu gibi bunun notasyonu O(2^n) karmaşıklığına sahiptir bu da çok işelm gerektirir işte bunun gibi algoritmalarda recursif yazılmış bir ifadeninin iteratife çevirip oradan da sonuca ulaşmak çok kolaydır
Bu fonksiyonlara örnek olarak faktöriyel fonksiyon, Fibonacci dizisi örnek verebiliriz
Basit bir örnek vereyim; 3,  6,  12,  24,  48,  …
Görüldüğü gibi 3 ile başlayan ve bir sonraki terimi bir önceki teriminin 2 katı olan bir dizidir
Recursif ifade olmazsa olmaz kural bir başlangıç belirlemek (initial condition) ve kendi kendisini çağıran fonksiyon kullanmak ve bunu fonksiyo olarak yazarsak;
Bu dizi rekürsif olarak   şeklinde ya da  şeklinde tanımlanabilir. Yani bir önceki terimi hesaplamadan  terim  formülü ile hesaplanabilir.
NOT: Kaçıncı derecede ise o kadar başlangıçı olmalıdır



Birkaç bağıntı örneği verelim ;
Verilen yinelemeli bağıntı ikinci dereceden sabit katsayılara sahiptir ama homojen değildir (n2 yüzünden). Ve  a1 = 1 ve a2 = 2 başlangıç değerleri için a3=15 ve a4=68  elde etmekteyiz
Bu yinelemeli bağıntı doğrusal olmayan bir bağıntıdır (an-1an-2 çarpım durumunda olduğu için). a1 = 1 ve a2 = 2 başlangıç değerleri için a3 ve a4 sırasıyla 13 ve 68 olarak elde edilebilir.
Bu yinelemeli bağıntı homojen ikinci dereceden bir bağıntıdır. Fakat sabit katsayılara sahip değildir (çünkü an-1 in katsayısı n dir. Bir sabit değildir). a1 = 1 ve a2 = 2 başlangıç değerleri için a3 ve a4 sırasıyla 9 ve 42 olarak elde edilebilir.
Yukarıda verilen yinelemeli bağıntı üçüncü dereceden sabit katsayıları olan bir bağıntıdır. Dolayısıyla 3 farklı başlangıç durumuna ihtiyacımız vardır. Örneğin a1 = 1 ve a2 = 2 ve a3 = 1 başlangıç değerleri için a4, a5  ve a6  sırasıyla 6 , -37 ve 254 olarak elde edilebilir.

İkinci Dereceden Homojen Doğrusal Yinelemeli Bağıntıların Çözümü
Homojen ikinci dereceden ve sabit katsayılara sahip bir bağıntı aşağıda verilen forma sahiptir:
 ya da
Yukarıda verilen ifade de s ve t 0’dan farklı sabitleri simgelemektedir. Biz aşağıda verilen ikinci dereceden bir polinomu yukarıda verilen yinelemeli bağıntı ile ilişkilendirebiliriz:
 polinomuna yinelemeli bağıntının karakteristik polinomu ve bu polinomun köklerine de onun karakteristik kökleri adı verilir.
Teorem. şeklindeki yinelemeli bir bağıntının karakteristik polinomu  şeklinde ve bu bağıntı r1 ve r2 şeklinde iki köke sahip ise o zaman yinelemeli bağıntının genel çözümü aşağıdaki gibi verilebilir:
Genel çözümdeki c1 ve c2 katsayıları başlangıç durumlarından elde edilebilir. Teorem kökler gerçek olmadığı durumlar için de geçerlidir.
Örnek . yineleme bağıntısının genel çözümünü elde ederek a0 = 1 ve a1 = 2 başlangıç durumları için bu genel çözümdeki katsayıları da elde ediniz.
Cevap. polinomunu verilen yinelemeli bağıntı için elde edebiliriz.  Dolayısıyla bu polinomun köklerini de r1= 3 ve r2= -1 şeklinde elde edebiliriz. Yine verilen teorem gereği bu yinelemeli bağıntının genel çözümünü de
 elde edilebilir. Daha sonra;
n = 0 ve a0 =1 için ya da
n = 1 ve a1 = 2 için ya da
Verilen denklemlerden de  ve olarak elde edilir. Sonuç olarak verilen başlangıç durumları için yinelemeli bağıntının tek çözümü şeklinde bulunur.