Vikipedi’den alınmış tanımıyla algoritma, belli bir problemi çözmek veya belirli bir amaca ulaşmak için tasarlanan yol.
Matematik ve bilgisayar biliminde ise bir işi yapmak için tanımlanan, bir başlangıç durumundan başlandığında, açıkça belirlenmiş bir son durumunda sonlanan sonlu işlemler kümesidir.
Yukarıdaki iki cümlenin özeti olarak; bazı girdilere karşılık, bazı değerler ya da değer kümeleri üreten iyi tanımlanmış hesaplama süreçlerinin hepsine algoritma diyebiliriz.
Hesap modeli kavramını anlayabilmek için üstte okuduğumuz bilgileri iyi anlamış olmamız gerekiyor. Çünkü, hesap modelleri “iyi tanımlanmış hesaplama süreçlerinin” çalışma sürelerini ölçmek için kullanılırlar.
Bu yazıda RAM Hesap Modeli(The Ram Model) ve Asimptotik Analizi(Asymptotic Analysis) inceleyeceğiz. Bu incelemelere girmeden önce neden algoritma analizi yapıyoruz sorusuna cevap arayalım.
Algoritma Analizi Neden Gereklidir?
En temel anlamda algoritmanın gerektirdiği kaynakları öngörmek için yaparız. Öngördüğümüz kaynak miktarlarına göre bir sistem belirlemek ya da elimizdeki veri setine en uygun algoritmayı belirlemek için algoritma analizi gerekli bir adım olarak karşımıza çıkıyor.
RAM Hesap Modeli
Yazının bu bölümüne kadar RAM kelimesini hep baş harfleri ile kullandık. RAM, Rassal-Erişimli Makine(Random-Access Machine) kelimesinin kısaltılmışdır.
Bu model, bir veri setindeki algoritmayı yürütmek için gereken adım sayısını toplayarak bir algoritmanın çalışma süresini ölçmeye çalışır. RAM Hesap Modeli, bilgisayar programlarının çalışma sürelerini ölçmek için gerçekten iyi bir yaklaşımdır. Nedenlerini alt bölümlerde daha iyi bir şekilde göreceksiniz fakat önce RAM Hesap Modelinin çalışma prensiplerini inceleyelim:
- Basit mantıksal veya aritmetik işlemler(+, *, =, if, >, <, …) bir zaman adımında yapıldığı kabul edilir.
- Döngüler ve alt programlar çoklu zaman adımlarında yapılan kompleks işlemlerdir.
- Bütün hafıza erişimleri bir zaman adımda yapılır.
Üstte yazmış olduğumuz üç maddenin kesin olarak “bir zaman adımı, çoklu zaman adımı” gibi ifadelerle tanımlandığına dikkat edin. Peki neden her şeyi bu şekilde uzun uzun adımlar halinde tanımlıyoruz?
Birkaç paragraf üstte belirttiğim üzere RAM Hesap Modeli’ni herhangi bir algoritmanın gerçek bilgisayardaki çalışma süresini hesaplamak için kullanıyoruz. Bu yüzden tanımlanan bu modelin gerçek bilgisayarların çalıştırabildiği adımlara sahip olmasını isteriz. Çünkü, eğer RAM Hesap Modeli yukarıda saydığımız fonksiyonlar haricinde bir de sıralama gibi bir fonksiyona sahip olsaydı sadece tek bir komutla sıralama problemini çözebilirdik. Bu durum da bize sıralama problemi özelinde gerçek bilgisayarlar için güzel bir yaklaşım sunmazdı. Bu da bizim perspektifimiz için uygun olmazdı.
Her ne kadar perspektifimizin gerçek bilgisayarları taklit etmek olduğunu düşünsek de aslında RAM Hesap Modeli bu adımları tamamen taklit edemez. Örneğin; gerçek bir bilgisayar toplama işlemi için birkaç adım uyguluyorsa, RAM Hesap Modeli’nde tek bir adım olarak tanımlarız.
Algoritmaların gerçek bir bilgisayar üzerinde çalışma süresinin kesin olarak analizi çok zor bir görevdir. Çünkü, bir algoritmanın gerçek bir bilgisayarda çalışma süresi onlarca parametreye bağlıdır. Bu parametrelerin her birini göz önünde bulundurarak bir algoritmayı analiz etmek çok zor olacaktır. RAM Hesap Modeli tam da bu noktada işimize yaramakta. Çoğu işlem için yaptığı varsayımlar basitlik ile gerçek bir bilgisayar arasında bir denge oluşturmakta ve pratikte çok yararlı bir araç olarak karşımıza çıkmaktadır.
Algoritma analizi ile ilgili herhangi bir ders alan bir öğrencinin yaşadığı en büyük problemlerden birisi bu analizleri neden, nasıl ve neye dayanarak yaptığımızdır. Temelde kullanılan RAM Hesap Modeli hem soyut hem de algoritma analizi anlamında çok faydalı bir araçtır.
Özetle, gerçek bir bilgisayarı taklit etmeye çalışır.
Sınırlama Fonksiyonları
Buraya kadar her şey güzel. Elimizde bir hesap modeli var ve bu model ile verimli bir şekilde bir analiz yapabiliyoruz. Bu noktada soracağımız soru ise şu, “Analizimizi nasıl açıklarız?”. Çünkü, RAM modeli karışık bir sonuç üretecektir. Bu sonuçları bir şekilde basitleştirmeli, anlamlandırmalı ve çıkarımlar sağlayabilecek hale getirmeliyiz. Mesela, bir problem için “En kötü, ortalama ve en iyi durumlar için bu algoritma nasıl çalışır?” sorusunu sorarsak basite indirgediğimiz bu sonucun bize cevap vermesini bekleriz.
Burada ise sınırlama fonksiyonları, bu algoritmanın çalışma süresi hakkında bize bilgiler veriyor.
Bir algoritmanın zorluğunu üç sınır fonksiyonu ile tanımlarız. Bunlar; Üst sınır, alt sınıf ve sıkı sınırdır.
- Üst Sınır (Upper Bound): $f(n) = O(g(n))$
- Alt Sınır (Lower Bound): $f(n) = \Omega(g(n))$
- Sıkı Sınır (Tight Bound): $f(n) = \Theta(g(n))$
Bu üç sıkı sınır fonksiyonu ilk görüldüğünde çok kafa karıştırıcı gibi görünüyor. Bir sonraki yazıda bu üç sıkı sınır fonksiyonuna detaylı bir şekilde inceleyeceğiz.
Diğer yazı yayınlandığı zaman linkini burada ve sosyal medya hesaplarımda bulabilirsiniz.
Kaynaklar
- Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to algorithms. MIT press.
- https://tr.wikipedia.org/wiki/Algoritma
İlk Yorumu Siz Yapın