Algoritma Analizi - 1. Hafta Giris PDF

Algoritma Bölüm 1 6  7 Algoritma Nedir?  Algoritma,  bir problemin çözmek için bir prosedür veya formüldür.  problemi çözmek için takip edilmesi gereken yönergeler kümesidir.  matematikte ve bilgisayar biliminde bir işi y...

Algoritma Bölüm 1 6  7 Algoritma Nedir?  Algoritma,  bir problemin çözmek için bir prosedür veya formüldür.  problemi çözmek için takip edilmesi gereken yönergeler kümesidir.  matematikte ve bilgisayar biliminde bir işi yapmak için tanımlanan, bir başlangıç durumundan başladığında, açıkça belirlenmiş bir son durumunda sonlanan, sonlu işlemler kümesidir.  Program  Bir programlama dilinde algoritmanın gerçekleştirilmesidir.  8 Algoritmik çözüm  Aynı algoritmik problem için farklı algoritmalar olabilir.  Algoritmaların özellikleri nelerdir?  9 Algoritmaların Özellikleri  Bir algoritmanın taşıması gereken beş tane temel özelliği vardır.  1. Giriş (Input)  Bir algoritmanın sıfır veya daha fazla giriş değişkeni vardır. Giriş değişkenleri algoritma işlemeye başlamadan önce, algoritmaya verilen değerler kümesidir veya değer kaydetmesi için verilen hafıza bölgesidir.  2. Belirlilik (Definiteness)  Bir algoritmanın her adımı için kesin olarak ne iş yapacağı belirlenmelidir ve belirsizlik olmamalıdır. Her durum için hangi işlem gerçekleştirilecekse, o açık olarak tanımlanmalıdır.  3. Çıkış (Output)  Her algoritmanın bir veya daha fazla çıkış değeri vardır. Çıkış değerleri ile giriş değerleri arasında bağıntılar vardır.  4. Etkililik (Efficiency)  Olabildiğince hızlı çalışmalıdır, olabildiğince az hafıza kullanmalıdır. Bunun anlamı yapılan işlemler yeterince temel işlemler olacak ve sınırlı zaman süresince işleyip bitmelidir.  5. Sınırlılık (Boundedness)  Her algoritma sınırlı sayıda çalışma adımı sonunda bitmelidir. Bir algoritma için sınırlılık çok önemlidir. Aynı işlemi yapan iki algoritmadan biri bir milyar adımda bitiyor olsun ve diğeri de yüz adımda bitiyor olsun. Bu durumda yüz adımda biten algoritma her zaman daha iyidir. Bunun anlamı sınırlılık kavramı ile anlatılmak istenen mümkün olan en az sayıda adım ile işlemin bitirilmesidir.  10 Algoritmaların Özellikleri  Diğer bazı kriterler ise algoritmanın bilgisayar ortamına aktarılabilme özelliği, basitliği, vb. gibi özelliklerdir.  Bir problem için birden fazla algoritma verilmişse, bu algoritmalardan en iyisinin seçilmesi gerekir.  İyi algoritmayı belirlemek için uygulanan testler veya yapılan işlemler Algoritma Analizi’ nin konusudur.  11 Algoritmaların Yönleri  1- Algoritmaları Tasarlama  Bulmacaların (puzzel) parçalarını birleştirme,  Veri yapılarını seçme,  Problemin çözümü için temel yaklaşımlar seçme.  En popüler tasarım stratejileri böl ve fethet (divide&conquer), açgözlü(greedy), dinamik programlama, özyineleme (recursive).  2- Algoritma ifadesi ve uygulanması  Algoritmayı tasarladıktan sonra sözde kod (pseudocode) ifadesinin belirlenmesi ve problem için uygulanması  Bu konudaki endişeler, netlik, özlülük, etkinlik vb.  12 Algoritmaların Yönleri  3-Algoritma Analizi (Çözümlenmesi)  Algoritma analizi, algoritmayı gerçekte uygulamadan, bir algoritmayı çalıştırabilmek için gereken kaynakların (zaman, yer gibi) araştırılması demektir.  4- Çözümünüzün yeterince iyi olup olmadığını görmek için alt ve üst sınırları karşılaştırma  Algoritma analizi problemi çözmek için bize alt ve üst sınırları verir.  13 Algoritmaların Yönleri  5- Algoritma veya programı doğrulama  Algoritmanın verilen tüm olası girişler için hesaplama yaptığını ve doğru çıkış ürettiğini göstermektir.  6- Algoritmaların test edilmesi  Test için iki aşama vardır;  Hata ayıklama (Debugging): Programın örnek veriler üzerinde çalıştırılması sırasında oluşan hataları tespit etme ve onları düzeltme işlemi.  Profil oluşturma (Profiling): Çeşitli veriler üzerinde programın çalıştırılması ve sonuçların hesaplaması için gerekli zamanın (ve alan) ölçülmesi işlemi.  14 Algoritma Tasarımı  Algoritmaları tasarlamada kullanılacak yöntemler  Özyineleme  Böl ve fethet  Bilinen probleme indirgeme  Dinamik programlama  Kaba Seçim veya Haris (Greedy) algoritması  Bir veri yapısı icat etme  İhtimali (olasılıksal) çözümler  Yaklaşım çözümleri  15 Algoritmaları tasarlamada kullanılacak yöntemler:  Özyineleme  Problemin çözümünün tekrarlı olması durumunda bilinen bir veya birkaç çözümden faydalanarak bir sonraki çözümü elde etme ve elde edilen çözüm ile önceki çözümlerin birkaçının kullanılması ile bir sonraki çözümün elde edilmesi ile problemi çözme işlemine özyineleme yöntemi denir. Faktöriyel hesabı, özyinelemeli bir algoritma kullanılarak çözülebilecek problemlere güzel bir örnektir Algoritmanın çıkış koşulu belirlenir (1! = 1). 2 sayısının faktöriyeli hesaplanır (2! = 1! * 2 = 2). 3 sayısının faktöriyeli hesaplanır (3! = 2! * 3 = 6). 4 sayısının faktöriyeli hesaplanır (4! = 3! * 4 = 24). 5 sayısının faktöriyeli hesaplanır (5! = 4! * 5 = 120). Beklenen hesaplamaya ulaşıldığı için algoritma sonlandırılır  Algoritmaları tasarlamada kullanılacak yöntemler: Böl ve fethet  Kompleks problemlerin bir bütün olarak çözülmeleri çok zor olacağından dolayı, bu problemler alt problemlere bölünürler. Bu bölünme işleminin yapılabilmesi için alt problemlerin bir üst seviyedeki problem ile aynı özelliği sağlamalıdır. Bu yöntem ile algoritma tasarımı yapmaya böl ve fethet yöntemi denir.  Algoritmaları tasarlamada kullanılacak yöntemler: Dinamik programlama  Böl ve yönet yöntemine benzer olarak alt problemlerin çözümlerini birleştirerek çözüme gitme mantığına sahip olup alt problem tekrarı varsa, bunlardan bir tanesi çözülür ve bu çözüm diğer tekrarlarda kullanılır. Bu yöntem ile yapılan algoritma tasarım yöntemine dinamik programlama yöntemi denir.  Algoritmaları tasarlamada kullanılacak yöntemler: Kaba Seçim veya Haris (Greedy) algoritması  Optimizasyon problemlerinin çözümü için yerel optimumların seçilmesi ilkesinden yola çıkar ve veriyi belli bir kritere göre düzenledikten sonra ilk veri her zaman optimum çözüme götürür mantığına sahiptir. Temel amaç en iyi sonucu elde etmek için en iyi ara adım çözümlerini seçmeye yönelik bir yöntem olduğundan bu yönteme haris algoritması yöntemi denir.  16 Algoritmaları tasarlamada kullanılacak yöntemler:  Bir veri yapısı icat etme  O ana kadar var olamayan bir veri yapısının icat edilmesi ile problemin çözülmesine veri yapısı icat etme yöntemi denir.  Bilinen probleme indirgeme  Kompleks olan bir problemin çözümünü yapmak için çözümü bilinen bir veya birden fazla başka probleme dönüştürüp bu şekilde problemi çözme işlemine bilinen probleme indirgeme yöntemi denir.  İhtimali (olasılıksal) çözümler  Bazı durumlarda gelişigüzellik ilkesi ile etkili bir şekilde problem çözümü yapılabilmektedir. Bunlara örnek olarak Las Vegas polinom-zamanlı ve Monte Carlo polinom-zamanlı algoritmalar verilebilir. Gelişigüzellik kullanılarak yapılan problem çözümlerine ihtimali çözümler yöntemi denir.  Yaklaşım çözümleri  Çözümü deterministik Turing makinası ile yapılamayan yani karmaşık hesaplamaların belirli bir yöntem ile çözülemediği bu problemlerin bir kısmına bazı kriterler uygulayarak yaklaşım mantığı ile çözüm üretilebilmektedir. Bundan dolayı bu mantık ile yapılan algoritma tasarımına yaklaşım çözümler yöntemi adı verilir.  17 Algoritma Analizi  Algoritmaanalizi, bilgisayar programının performansı (başarım) ve kaynak kullanımı konusunda teorik çalışmalardır.  Bir başka ifadeyle, algoritmanın icra edilmesi sırasında duyacağı kaynak miktarının tahmin edilmesine Algoritma Analizi denir.  Kaynak denildiğinde, bellek, iletişim bant genişliği, mantık kapıları akla gelebilir, fakat en önemli kaynak algoritmanın icra edilebilmesi için gerekli olan zamanın tahmin edilmesidir.  Algoritma analizi, farklı çözüm yöntemlerinin verimliğini analiz eder.  Biz bu derste performans yani başarım üzerine yoğunlaşacağız.  18 Algoritma Analizi  Performanstan daha önemli ne vardır ?  modülerlik  doğruluk  bakım kolaylığı  işlevsellik  sağlamlık  kullanıcı dostluğu  programcı zamanı (fiyat)  basitlik  genişletilebilirlik  güvenilirlik  19 Neden algoritmalar ve başarımla uğraşırız?  Başarım (performans) genelde yapılabilir olanla imkansızın arasındaki çizgiyi tanımlar.  Algoritmik matematik program davranışlarını açıklamak için ortak dil oluşturur.  Başarım bilgi işleme'nin para birimidir.  Program başarımından alınan dersler diğer bilgi işleme kaynaklarına genellenebilir.  Hız eğlencelidir!  20 Algoritmik Performans  Algoritmik performansın iki yönü vardır:  Zaman (Time)  Yönergeler veya talimatlar zaman alabilir.  Algoritma ne kadar hızlı bir performans gösteriyor?  Algoritmanın çalışma zamanını (runtime) ne etkiler?  Bir algoritma için gerekli olan zaman nasıl tahmin edilir?  Gerekli olan zaman nasıl azaltılabilir?  Alan (Space)  Veri yapılarıyer kaplar.  Ne tür veri yapıları kullanılabilir?  Veri yapılarının seçimi çalışma zamanını nasıl etkiler?  21 Algoritma Analizi  Bir algoritmanın analizinin yapılabilmesi için matematiksel bilgilere (temel olasılık, kümeler, cebir, v.b.) ihtiyaç duyulduğu gibi bazı terimlerin formül olarak ifade edilmesi gereklidir. Çünkü her giriş için algoritmanın davranışı farklı olabilir.  Benzer problemi çözmek için iki algoritmanın zaman verimliliğini nasıl karşılaştırabiliriz?  Naif( Basit ) yaklaşım: bir programlama dilinde bu algoritmaların uygulanması ve çalışma zamanlarının karşılaştırılması.  22 Algoritma Analizi  Algoritmalar yerine programların karşılaştırılmasında aşağıda belirtilen zorluklar vardır.  Programın kullanabileceği veri nedir?  Analiz yöntemi veriye bağımlı olmamalıdır. Çalışma zamanı verinin büyüklüğü ile değişebilir.  Hangi bilgisayarı kullanmak gerekir?  Algoritmaların verimliliği belirli bir bilgisayara bağımlı olmadan karşılaştırılmalıdır. Çünkü, aynı algoritmanın işlemci hızları farklı iki bilgisayarda çalışma zamanı aynı olmaz.  Algoritma nasıl kodlanmalıdır?  Çalışma zamanını karşılaştırmak, uygulamaları karşılaştırmak anlamına gelir. Uygulamalar, programlama tarzına duyarlı olduğundan karşılaştıramayız. Programlama tarzı çok verimli bir algoritmanın çalışma zamanını bile etkileyebilir.  Programları karşılaştırmak, bir algoritmanın kesin ölçümü için uygun değildir.  23 Algoritmaların Analizi  Algoritma analizi, özel uygulamalardan, bilgisayarlardan veya veriden bağımsızdır.  Algoritma analizi, tasarlanan program veya fonksiyonun belirli bir işleme göre matematiksel ifadesini bulmaya dayanır.  Algoritmaları analiz etmek;  İlk olarak,algoritmanın etkinliğini değerlendirmek için belirli bir çözümde anlamlı olan işlemlerin kaç adet olduğu sayılır.  Daha sonra büyüme fonksiyonları kullanılarak algoritmanın verimliliği ifade edilir.  24 Algoritma Analizi Problem n elemanlı giriş Temel işlem Bir listede arama liste n elemanlı karşılaştırma Bir listede sıralama liste n elemanlı karşılaştırma İki matrisi çarpma n x n boyutlu iki matris çarpma Bir ağaçta dolaşma n düğümlü ağaç Bir düğüme erişme Hanoi kulesi n disk Bir diski taşıma  Not:Temel işlem tanımlayarak bir algoritmanın karmaşıklığını ölçebiliriz ve giriş büyüklüğü n için bu temel işlemi algoritmanın kaç kez gerçekleştirdiğini sayabiliriz.  25 Algoritmaların Analizi  Anlamlı olan işlemler hakkında önemli not:  Eğer problemin boyutu çok küçük ise algoritmanın verimliliğini muhtemelen ihmal edebiliriz.  Algoritmanın zaman ve bellek gereksinimleri arasındaki ağırlığı dengelemek zorundayız.  Dizi tabanlı listelerdegeri alma işlemleri O(1)’dir. Bağlı listelerde geri alma işlemi ise O(n)’dir. Fakat eleman ekleme ve silme işlemeleri bağlı liste uygulamalarında çok daha kolaydır.  26 Algoritmaların Analizi: Çalışma Zamanı fonksiyonu :T(n)  Çalışma zamanı veya koşma süresi (running time) fonksiyonu:  ‘n’ boyutlu bir problemin algoritmasını çalıştırmak için gerekli zamandır ve T(n) ile gösterilir.  Başka bir ifadeyle T(n): bir programın veya algoritmanın işlevini yerine getirebilmesi için, döngü sayısı, toplama işlemi sayısı, atama sayısı gibi işlevlerden kaç adet yürütülmesini veren bir bağıntıdır.  Çalışma Zamanı Ölçü Biriminin Belirlenmesi Zaman verimliliğinin teorik incelenmesi – Zaman verimliliği girdi üzerindeki temel işlemin tekrar sayısı üzerinden değerlendirilir – Temel işlem Algoritmanın çalışma süresince en çok gerçekleştirilen işlem  Çalışma Zamanı Ölçü Biriminin Belirlenmesi cop : – Bir algoritmanın temel işleminin bir bilgisayardaki çalışma süresi C(n) : – Temel işlemin gerçekleşme sayısı T(n) : – Algoritmanın uygulandığı programın çalışma süresi T(n) ≈ cop C(n) – Bu formülün yaklaşık ve tahmini bir değer verdiği unutulmamalı  27 Algoritmaların Çalışma Zamanı  Örnek: Basit if bildirimi  Toplam maliyet  > 1 2 4 6 =  =  =  =  1 F 2 F 4 F 6 F  Görülen karşılaştırma ağacı dengelibir ağaçtır. Bazı durumlarda karşılaştırma ağacının bütün yaprakları aynı seviyede olmayabilir... 71 İkili Arama (Binary Search)  Eğerx değişkeninin değeri Dizi[2k-1] elemanın değerinden küçükse,............ 1 2 2k-1 x elemanı bu parçanın içinde olabilir, diğer parçanın içinde olması mümkün değildir. Eğer x değişkeninin değeri Dizi[2k-1] elemanın değerinden büyükse,............ 2k-1 +1 2k-1 +2 2k x elemanı bu parçanın içinde olabilir, diğer parçanın içinde olması olasılığı sıfırdır. Bu şekilde geriye kalan parçanın içindeki eleman sayısı 2’ nin kuvveti kadar eleman kalacaktır. Bundan dolayı ortadaki elemanı bulmak için taban veya tavan fonksiyonuna ihtiyaç duyulmayacaktır. Dizi üzerinde yapılacak bölme sayısı logn olacaktır... 73 İkili Arama (Binary Search)  Bu algoritmanın da en kötü durumu ile ortalama durumun asimptotik davranışları aynıdır. Fakat en kötü durum ve ortalama durum mertebeleri (çalışma zamanı) logaritmik olduğundan, lineer aramaya göre çok iyi olan bir algoritmadır.  Eğer bir dizi içindeki veriler sıralı ise, her zaman ikili arama algoritmasını kullanmak sistemin performansını arttırır... 74 Binary Arama Analizi  Başarısız Arama : (n) int ikiliArama(int A[], int N, int sayi)  Başarılı Arama: { sol = 0; sag = N-1;  Best-Case: (1) while (sol