Algoritma Analizi Ders Notu(1.Hafta)

 

Algoritma Nedir ?

Algoritma

    Bir problemi çözmek için gerekli sonlu adımlar(işlemler) bütünüdür. Problem yada sorunların çözülmesi için takip edilmesi gereken yönergeler kümesidir.

Program

    Bir programlama dili, algoritmanın bilgisayar ortamına aktarılarak adımları(işlemleri) çözmek için bilgisayarın hesaplama gücünden faydalanmamızı sağlar.

Algoritmaların 5 Temel özelliği vardır :

    1.Giriş(input)

        Bir algoritmanın sıfır yada daha fazla giriş değeri vardır. Algoritma adımları(işlemleri) başlamadan önce algoritmaya verilen veri kümesidir.

    2.Kesinlik(definiteness)

        Bir algoritmanın her adımı için kesin olarak ne iş yapacağının belirlenmesidir. Her durum için adımlar(işlemler) kesin olarak belirtilmelidir.

    3.Çıkış(output)

    Algoritmanın verilen veri kümesini işlemesi sonucunda çıkan bilgidir. Her algoritmanın bir veya daha fazla çıkış bilgisi olabilir. Ayrıca veri kümesi ile çıkış bilgisi arasında  her zaman bağıntı vardır.

    4.Verimlilik(efficiency)

        Algoritmanın olabildiğince az bellek kullanması ve olabildiğince hızlı(yada kısa sürede) çalışmasıdır. Bu sebeple algoritma adımları(işlemleri) en temel işlemlere indirgenmiş olması gerekir.

    5. Sınırlılık(boundedness)

    Algoritmanın sınırlı ve sonlu adımda sonlanmasıdır. 

İyi bir algoritmayı belirlemek için uygulanan testler ve yapılan işlemlere algoritma analizi denir.

Algoritmanın oluşturulmasında nasıl bir yol izlenir?

1.Algoritma tasarlama

    Algoritma için en uygun veri yapısı seçilir ve problemin çözümü için temel yaklaşımlar seçilir.(Böl ve yönet, aç gözlü, dinamik programlama, öz yinelemeli yada yeni bir yaklaşım getirilir.

2.Algoritma ifadesi ve uygulaması

    Algoritmayı tasarladıktan sonra sözde kod(pseude code) ifadesinin belirlenmesi ve problem için uyarlanması(uygulanması) adımıdır.

3.Algoritma analizi(çözümlemesi)

    Algoritma analizi algoritmayı gerçekte uygulamak için gereken kaynakların araştırılma kısmıdır.

    
4.Üst ve alt sınırların karşılaştırılması

    Üst sınır, o algoritma için verilen durumdan daha uzun sürmeyeceği garantisi verir. Alt sınır, Omega ile ölçülen değerden daha hızlı bir değer elde etmemizin mümkün olmadığı sınırdır.

5.Algoritma yada programla doğrulama

    Algoritmanın verilen tüm olası verilerin giriş yapıldığı, doğru bilgi çıkışlarını ve hesaplamalarının yapıldığı adımdır.    

6.Algoritmanın test edilmesi

    Test için iki aşama mevcuttur;

        a.Hata ayıklama(debugging)

            Algoritmanın örnek veriler üzerinde çalıştırıp oluşan hataların tespit edilmesi ve düzeltilmesi aşamasıdır.

        b.Profil oluşturma(profiling)

            Çeşitli veriler üzerinde algoritmanın çalıştırılması ve sonuçlar(çıktılar) için gerekli zaman ve kaynak ölçümlerinin yapıldığı işlemdir.

Algoritma tasarlamada kullanılabilecek yöntemler

1.Özyineleme

    Problemin çözümünün tekrarlı olması durumunda bilinen bir yada bir kaç çözümden faydalanarak bir sonraki çözümü elde etme işlemine denir.

2.Böl ve yönet

    Kompleks problemlerin bütün çözümleri çok zor ve maliyetli olacağından dolayı, bu problemleri alt problemler halinde parçalara bölünür. Bu bölme işleminin yapılabilmesi için alt problemlerin üst problemle aynı özellikleri sağlaması gerekmektedir. Alt problemlerin çözümü bağımsız olarak yapılır ve geriye doğru birleştirme işlemi yapılarak ana problem çözülür. Çok fazla dallanmaya sebep olur.

3.Dinamik programlama

    Böl ve yönet yöntemine benzer olarak alt problemler oluşturulur ve alt problemlerin çözümü birleştirilerek ana problem çözülür. Farklı olarak alt problemlerde tekrar varsa bunlardan bir tanesi çözülür ve bu çözüm diğer benzer alt problemlerde uygulanır.

4.Kaba seçim veya Haris(greedy) algoritması

    Optimizasyon problemlerin çözümü için yerel optimumların seçilmesi ilkesinden yararlanılır. Ve veriyi belirli 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 sonuç elde etmek olduğunda kullanılır. En iyi ara adım çözümlerini seçmeye yönelik bir sistemdir.

5.Yaklaşım yöntemi

    Çözümü deterministik Turing makinesi ile yapılmayan yani karmaşık hesaplamaların belirli bir yöntem ile çözülemediği bu problemlerin bir kısmına bazı kriterler uygulanarak yaklaşım mantığı işe çözüm üretilmesidir.

Algoritma Analizi

    Bilgisayar programının performansı ve kaynak kullanımı hakkında teorik çalışmaların yapılmasıdır. Algoritmaların icra edilmesi(çalıştırılması) sırasında ihtiyacı olan kaynak miktarının belirlenmesi yada tahmin edilmesine denir. Kaynak, bellek(ram), iletişim bant genişliği, mantık kapıları ve en önemlisi zaman'dır.

Algoritmanın diğer önemli faktörleri

1. Modülerlik
2. Doğruluk
3. Bakım kolaylığı
4. İşlevsellik
5. Sağlamlık
6. Kullanıcı dostu
7. Program maliyeti
8. Basitlik
9. Genişletilebilirlik
10. Güvenirlilik

Neden Algoritmalar ve başarımları ile uğraşırız?

    Başarım(performans) genelde yapılabilir olanla imkansız arasındaki çizgiyi tanımlar. Algoritmik matematik, program davranışlarını açıklamak için ortak bir dil oluşturur. Başarım(performans) bilgi işlemenın para birimidir.

    Algoritma Başarımı(performansı)

        Algoritma başarımının iki yönü vardır;

            Zaman(Time)

                Yönergeler ve talimatlar zaman alabilir.

                Algoritma ne kadar hızlı başarım(performans) gösteriyor?

                Algoritmanın çalışma zamanını(runtime) ne etkiler?

                Bir algoritma için gerekli olan zaman hesaplaması nasıl yapılır?

                Algoritma için kullanılan zaman nasıl azaltılır?

            Alan(Space)

                Veri yapıları alan kaplar.

                Ne tür veri yapıları kullanılır?

                Veri yapıları seçimi çalışma zamanını nasıl etkiler?

    

    Bir algoritmanın analizinin yapılabilmesi için matematiksel bilgi ve yöntemlere başvurulur(olasılık, kümeler, cebir, v.b.). Bazı terimlerin ise formül olarak ifade edilmesi gerekmektedir.

Benzer problemler için iki algoritmanın zaman verimliliğini nasıl karşılaştırırız?

    Naif(Basit) Yaklaşım:

        Bir programlama dilinde bu algoritmaların uygulanması ve çalışma zamanlarının karşılaştırılması işlemidir. Bu işlemde büyük bir faktör olan programlama dilindeki karşılaştırma olumsuzlukları şunlardır;

        Programın kullanacağı veri yapısı nedir?

            Analiz yöntemi veri yapısına bağlı olmamalıdır. Çalışma zamanı veri yapısının büyüklüğü ile değişebilir.

        Hangi bilgisayarı kullanmalıyım?

            Algoritma verimliliği bir bilgisayara bağlı kalmadan belirlenmelidir.

        Algoritma nasıl kodlanmalıdır?

            Çalışma zamanı karşılaştırmak, uygulama zamanı karşılaştırmak demektir. Uygulamalar programlama tarzına duyarlı oldukları için karşılaştırma yapmak doğru analiz sonucu vermeyebilir.

Programları karşılaştırmak, bir algoritmanın kesin veri analizi için uygun değildir.

    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(performansı) ifade edilir.

Anlamlı işler hakkında not:

    Algoritmanın zaman ve bellek gereksinimlerini dengede tutmalıyız. Dizi(liste) tabanlı işlemlerde geri alma maliyeti O(1)'dir. Bağlı listelerde ise O(n)'dir. Fakat eleman ekleme ve silme işlemleri bağlı liste uygulamalarında daha kolaydır.

Çalışma Zamanı Fonksiyonu T(n)

    Çalışma zamanı(runtime), 'n' boyutlu bir problemin algoritmasını çalıştırmak için gerekli zamandır ve T(n) ile gösterilir. n belirlenen temel işlem sayısıdır.

Temel işlem tablosu

Örnek :

    Basit bir if işlemi

Toplam maliyet <= c1 + max(c2,c3)

son güncelleme 7/10/2020 17:20