System call’ların da, sistemden sisteme değişiyor olması yazılımcının işini zorlaştırır. Bu değişiklik, bir OS için yazılan programın başka bir OS üzerinde çalışamamasına sebep olur. Bu yüzden programcılar, doğrudan sistem call’lar yerine application program interface(API) kullanmayı tercih ederler.

Neden API kullanılır?

• API’ler programın her sistem üzerinde çalışabilmesini sağlar.
• API kullanımı, her sistemin system call’larını ezbere bilmeyi gerektirmez.
• Birden fazla sistem işlemini kısa fonksiyonlarla yapabilmeyi sağlar. Programcı API fonksiyonunun içeriğiyle ilgilenmez. Fonksiyonun parametrelerini ve dönüş değerini bilmesi yeterlidir.

API’lerin programlamayı oldukça kolaylaştırdığı doğrudur. Ancak daha spesifik işlemler için system call’ları kullanmak gerekebilir.

System Call Tipleri

• Process Control (Süreç Kontrolü)
• bitirme, iptal etme
• yükleme, çalıştırma
• create process(süreç yaratma), terminate process(süreç sonlandırma)
• process attributelerini getirme, process’e attribute atama
• belli bir süre bekleme
• bekleme event’ı, sinyal event’ı
• memory bölgesini allocate, free işlemleri
• File Management (Dosya Yönetimi)
• dosya yaratma, dosya silme
• açma, kapama
• okuma, yazma, konumunu değiştirme(reposition)
• dosya attributelerini getirme, atama
• Device Management (Aygıt Yönetimi)
• request device, release device
• okuma, yazma, reposition
• device attributelerini getirme, atama
• mantıksal olarak aygıtları ilişkilendirmek, ayırmak
• Information Maintenance (Bilgilendirme Hizmeti)
• zamanı veya tarihi getirme, atama
• sistem verisini getirme, atama
• process, dosya veya device attributelerinin getirilmesi, atanması
• Communications (İletişim)
• iletişim bağlantısının yaratılması, silinmesi
• mesaj alma, gönderme
• durum bilgisinin transferi
• Protection (Koruma)
• dosyaların yazma, okuma, çalıştırma izinleri
• kullanıcıların system call’lar üzerindeki yetkileri

Kaynak : Operating System Concepts ~ Eight Edition (s55-s60)

User Interface : Kullanıcıların işletim sistemine ne yapmak istedikleri arayüzdür. Neredeyse tüm işletim sistemleri user interface(UI) içerir. Bazı UI türleri :

• Command-line interface (CLI) : Komutların yazı olarak girildiği UI türüdür. Günümüzde neredeyse tüm işletim sistemleri tarafından kullanılır. Örneğin windows için run -> cmd diyerek ulaşılabilir. Linux’ta terminal veya console olarak görülebilir.
• Batch interface : Yapılacak işlemlerin daha önceden dosyalara kaydedildiği UI türü. İşletim sistemine dışarıdan içi komut dolu dosya verilir ve işletim sistemi bu komutları işler.
• Graphical User Interface (GUI) : En çok kullanılan arayüz şeklidir. Arayüz kullanıcıya pencereler şeklinde gösterilir. Menüleri seçmek, pencerelerde dolaşmak, komutlar vermek için fare gibi nokta belirleyen aygıtlar kullanılır. Klavye ise text girişi vb için kullanılır. Windows, Mac OS X, bazı Linux sürümleri (KDE, Gnome … kullanan) GUI kullanır.

Program Execution : Sistem programları belleğe yükleyebilmeli ve yüklediği bu programları çalıştırabilmelidir. Ayrıca bu programlar normal veya normal olmayan yollardan (ör : Hata vererek) sonlanabilmelidir.

I/O Operations : Çalışan bir program bir aygıttan veya bir dosyadan girdi/çıktı yapmak isteyebilir. I/O işleminin etkin ve güvenli bir şekilde yapılabilmesi için işlem doğrudan kullanıcı tarafından yapılmamalıdır. Bu da işletim sistemlerin I/O desteği vermesini gerekli kılar.

File-System Manupilation : Bir program dosyaları okumak, yazmak; klasörler içerisinde dolaşmak veya dosyaları, klasörlerı oluşturmak, silmek, adlandırmak, isimlerine göre arama yapmak, bilgileri görüntülemek isteyebilir. Bazı programlar dosyayı sahiplenerek dosya, klasör yönetimi hakkına sahip olabilir. Çoğu OS çeşitli file system sunar. Bu seçim kişinin kişisel seçimine veya bazı özelliklere ve performansa bağlı olarak yapılabilir.

Communications : Sistemdeki bir process bir başka process ile iletişime geçmek isteyebilir. Bu iki process aynı bilgisayarda veya ağ üzerindeki farklı bilgisayarlarda olabilir. Processler arasındaki iletişim shared memory veya message passing yöntemlerinden biri ile gerçekleştirilir.

Error detection : OS, oluşabilecek hataların sürekli farkında olmalıdır. Her tür hata için OS doğruluğu ve tutarlılığı sağlamak için uygun işlemi yapmalıdır. Oluşabilecek bazı örnek hatalar :

• CPU ve Bellek hataları : Belleğe erişememe, gücün kesilmesi…
• I/O Aygıtı hataları : bellek aygıtı üzerindeki parity hataları, ağ üzerindeki bağlantının kesilmesi, yazıcıya kağıt sıkışması…
• User Program Hataları : Aritmetik taşmalar, kendine ait olmayan bir bellek bölgesine erişmeye çalışmak, çok fazla CPU kullanımı …

Resource Allocation : Birçok kullanıcı veya birçok görevin (task/job) aynı anda çalıştığı sistemlerde, her biri için kaynaklar ayrılmalıdır.

Accounting : Hangi kullanıcının ne kadar kaynak kullandığı, hangi kaynakları kullandığı gibi bilgilerin tutulması işlemidir. Bilgisayarın yeniden konfigüre edilmesi; donanımının, yazılımının güncellenmesi için gerekli olabilir.

Protection and Security : Çok sayıda process eş zamanlı işletilirken, bir process’in diğer process işleyişine veya bir process’in işletim sisteminin işleyişine karışamıyor olması gereklidir. Bu yüzden bir process, başka bir process’in bellek bölgesine erişemez.

Hardware sistem için temel kaynakları sağlar.  İşlemci (CPU), bellek, Girdi/Çıktı cihazları (I/O devices) gibi.

Application programs kullanıcıların problemlerini çözmek için donanım kaynaklarını kullanan yazılımlardır. Spreadsheet, Web tarayıcıları, derleyiciler gibi.

Operating system ise hardware, application programs ve users arasında köprü görevi görür. Hardware’ı kontrol eder ve birçok user’ın birçok application programda çalışmasına izin verir.

User View

Bir bilgisayarı kullanan kişinin (kullanıcı/user) görüşü kullanılan arayüz’e göre değişir.

Birçok kullanıcı monitör, klavye, fare ve sistem parçalarından oluşan bilgisayarları kullanır. Bu tür bilgisayarlara kişisel bilgisayar(PC/Personal Computer) diyoruz. Bu tür sistemler bir kullanıcının tüm kaynakları tekeline alması için tasarlanmıştır. Burada amaç kullanıcının yapacağı işin performansını en üst seviyeye çıkarmaktır. Bu tür bilgisayarlarda kullanılan işletim sistemi kolay kullanım sağlar. İşletim sisteminin asıl amacı performanstır ve kaynak kullanımını (resource utilization) çok kullanıcıya dağıtma amacı gütmez.

Diğer tür bilgisayarlar kullanıcıların terminalleri kullandıklarıdır. Burada, merkezde çalışan bir mainframe veya minicomputer vardır. Tüm kullanıcılar terminaller vasıtasıyla bu ana bilgisayara bağlanır. Bu tür bilgisayarlarda kullanılan işletim sisteminin asıl amacı kaynak kullanımını (resource utilization) en üst seviyeye çekmektir.

Üçüncü tür bilgisayarlar, kişilerin workstation kullandıklarıdır. Bir workstation diğer workstationlara ve serverlara bağlıdır. Kullanıcıların kendilerine ait kaynakları (resources) vardır fakat aynı zamanda network üzerinde paylaşılan kaynakları da kullanırlar. (dosya saklama, hesaplama yapma, çıktı alma gibi). Bu tür bilgisayarlarda kullanılan işletim sistemi kullanılabilirlik (usability) ve kaynak kullanımını (resource utilization) orantılı şekilde yüksek tutmalıdır.

Dördüncü tür bilgisayarları el bilgisayarları, tabletler, akıllı telefonlar olarak düşünebiliriz. Bu tür cihazların azı artık bağımsız olarak çalışmaktadır. Çoğu kablosuz olarak bir ağa dahildir. Bu tür cihazlar fazla güç harcamamaları için çok hızlı değildir. Bu yüzden de arayüzleri limitlidir. Bu tür bilgisayarlarda bulunan işletim sistemi, bireysel kullanımı kolaylaştırmayı hedefler. Ancak pil ömrü diye bir problem olduğundan olabildiğince az güç tüketmeye çabalar.

Bazı bilgisayarlar ise user view çok az olabilir veya hiç olmayabilir. Evdeki bazı embedded cihazlar, otomobillerdeki bazı embedded bilgisayarlar. Bu tür bilgisayarlar için tasarlanan işletim sistemleri daha çok kullanıcı müdahalesi olmadan çalışabilmesi için tasarlanır.

System View

Resource Allocator : İşletim sistemi bir kaynak ayırıcısıdır. Bir bilgisayar sisteminde birçok kaynak vardır ve bunlar CPU Time, memory space, file-storage space problemlerinin çözümünü gerektirir. OS, bu kaynakların hangi programlar tarafından nasıl kullanacağını belirler. Resource allocation, özellikle çok kullanıcılı bilgisayarlarda hayati önem taşır.

Control program : İşletim sistemi bir kontrol programıdır. Control program user programlarının çalışmasını yönetir. Hatalardan korur ve yanlış kullanımı önler. Ayrıca I/O cihazlarıyla da control program ilgilenir.

İşletim Sisteminin Tanımı

İşletim sistemi için tam bir tanım yapmak mümkün değildir. İşletim sistemleri vardır çünkü kullanılabilir bilgisayar sistemleri kullanılarak problem çözümünde makul çözüm yolları sunarlar.

Bilgisayar sisteminin temel görevi kullanıcı programlarını çalıştırmak ve kullanıcı problemini kolaylıkla çözmektir. Bu amaçla ilk olarak bilgisayar donanımı geliştirildi. Donanımın kendi başına kullanımının zor olduğu anlaşıldığındaysa application programlar geliştirildi. Bu application programların birleştirilip tek bir noktadan çalıştırılan halin işletim sistemi (operating system) diyebiliriz.

İşletim sistemini hangi parçaların oluşturduğu da kesin değildir. Ancak bir işletim sistemini kernel, system programs ve application programs olarak incelemek mümkündür.

Kernel : İşletim sistemi çalıştığı süre boyunca çalışan program. İşletim sisteminin çekirdeği. Bilgisayar açılır açılmaz memorye yüklenen program.

System Programs : Kernel parçası olmayan, ancak bilgisayarın çalışmasını etkileyen, düzenleyen programlar. Sürücüler (drivers) bu gruba alınabilir

Application Programs : İşletim sistemiyle doğrudan ilişkili olmayan programlardır. Daha çok kullanıcıların işlerini halletmeye yöneliktir.

Madem temelde sıradan metodlar gibi,  peki neden delegate kullanılır?

• Delegeler ile birden fazla metodu aynı anda kullanabiliriz.
• Anonim metodlar ile  daha kısa kodlar yazarız.
• Async Delegate kullaranarak, metodların asenkron olarak çalışmasını sağlayabiliriz.
• Delegeleri dizi şeklinde tutarak, metodların döngülerle çağırılmasını sağlayabiliriz.

Örnek bir delege kullanımı :

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

namespace DelegateKullanimi
{
    public delegate void myDel(int c,string d); // myDel isimli delegemi class seviyesinde tanımlıyorum
 
    class Program
    {
        static void Main(string[] args)
        {
            myDel yazdir = new myDel(adFiyatYaz); //Delegemin instance'ını adFiyatYaz fonksiyonunu kullanarak oluşturuyorum
            yazdir += new myDel(kdvYaz); // yazdir delegate'ime yeni bir myDel intance'ı ekliyorum
 
            /* Yukarıda adFiyatYaz ve kdvYaz metodlarımı yazdır isimli myDel tipindeki delegemin içine attım. 
             * myDel delegesini bir integer bir de string alacak şekilde tanımladığımdan, dışarıdan bu iki tip 
dışında veri alan metodları delegem içine eklemeye çalışırsam, derleme sırasında hata alırım.
             */
 
            yazdir(100,"Hoşaf suyu"); // yazdır delegesinin kullanımıyla iki metod birden çağırılmış oldu.
        }
 
        static void adFiyatYaz(int a,string b)
        {
            float fiyat = ((float)a) * 118 / 100;
            Console.WriteLine(b + " ürününün fiyatı: " + fiyat.ToString());
        }
        static void kdvYaz(int a, string b)
        {
            float kdv = a * 18 /100;
            Console.WriteLine("Fiyata dahil KDV : " + kdv.ToString());
        }
    }
}

bir değişken içindeki veriye ulaşabilmek için 40 takla atmanıza, propertyler sayesinde gerek kalmaz.

Örnek :

1
2
3
4
5
6
7
8
9
10

class MyC
{
    private string _isim;
    public string Isim
    {
        get { return _isim; } // getIsim() fonksiyonundan kurtaran get propertysi 
        set { _isim = value; } // setIsim(string isim) fonksiyonundan kurtaran set propertysi
    }
    public MyC(string s){this._isim=s;}  //MyC sınıfımın yapıcı (constructor) metodu
}

Bu da bize getIsim() setIsim(string isim) gibi fonksiyonlarla uğraşmak yerine, veriye aşağıdaki gibi kolaylıkla ulaşmamızı sağlar:

1
2
3

MyC Tol = new MyC("Ali");
Tol.Isim = "Tolga"; // Property üzerinden MyC tipindeki Tol'un _isim değişkenine değer atıyorum
Console.WriteLine(Tol.Isim); // Tol.Isim diyerek Tol'un get propertysinden dönen değeri kullanıyorum

Ayrıca, get ve set alanlarının içi istenildiği şekilde değiştirilerek kontroller yapılabilir, istenen değer atanabilir. Veya, get veya set ‘lerden istediğimizi yazmayarak, propertinin salt okunur veya salt yazılır olmasını sağlayabiliriz.

Propertylerin diğer bir güzelliği de, metodlara göre daha hızlı çalışmaları. Yazılmış program JIT compiler ile derlenirken, property’ler inline yapılarak intermediate language haline getiriliyormuş*.

* Kaynak : Professional C# 2005 with .NET 3.0 : Nagel, Evjen, Glynn,Watson,Skinner

Ancak ref ve out parametresi arasında farklar var. Şöyle ki :

1. out parametresi ile gönderilen bir değişkenin değeri metodun içinde kullanılamaz
2. metod içinde yeni bir değişken yaratılır, fonksiyon sonlanırken referansi metoda gönderilen değişkeninkine atanır
3. metoda out parametresiyle gönderilen bir değişkene ilk değer atanması zorunlu değildir

Hız? Bellek?
Tıpkı referans ile veri göndermede olduğu gibi, out parametresiyle gönderilen veri de bellek kullanımını azaltıyor. Ayrıca verinin kopyalanması sırasında harcanan süreden de kurtulmuş oluyoruz. Yani, hem hızlı hem de az bellek kullanımını sağlıyor diyebiliriz.

Örnek :

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

static void Main(string[] args)
{
    int a; //değişkene bir ilk değer atamak zorunda değilim, çünkü out parametreli bir fonksiyona gönderdim
 
    //Console.WriteLine(a); --> bu satır derleyici tarafından hatalı kabul edilir. Çünkü değişkene değer atayan f fonksiyonu çağırılmamıştır
 
    f(out a);
 
    Console.WriteLine(a);
 
    Console.ReadLine();
}
 
private static void f(out int sayi)
{
    sayi = 20;
}

LCS Problemi ne diyenler için : http://en.wikipedia.org/wiki/Longest_common_subsequence_problem

Dinamik Programlama ne diyenler için : http://tolpp.com/dinamik-programlama-dynamic-programming-nedir/

Aşağıdaki Java kodunu indirmek için : http://tolpp.com/algorithms/LCS.java

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
37
38
39
40
41
42

public class LCS {
	/*
	*@author : tolpp
	*/
 
    public static void main(String[] args) {
        String x = "ZTR123AAAAB";
        String y = "KLMN12BAB";
        int M = x.length();
        int N = y.length();
 
        int[][] cozum = new int[M+1][N+1];// Altkümelerin harfler için ne kadar kere ortak olduğunu tuttuğum matrisim
 
        // LCS uzunluğunun ve tüm alt problemlerin dinamik programlamayla hesaplandığı kısım
        for (int i = M-1; i >= 0; i--) {//Dizi elemanlarını tersten gelerek kontrol ediyorum
            for (int j = N-1; j >= 0; j--) {
                if (x.charAt(i) == y.charAt(j))
                    cozum[i][j] = cozum[i+1][j+1] + 1;// eşleşme varsa bu harfin olduğu fazladan bir alt küme daha olduğunu belirtmek için matris üzerinde bu harflein bulunduğu konumdaki değeri 1 artırıyorum
                else
                    cozum[i][j] = Math.max(cozum[i+1][j], cozum[i][j+1]);// Eşleşme yoksa, o ana kadarki en uzun altküme uzunluğunu en uzun altküme olarak alıyorum
            }
        }
 
        // cozum[][] matrisini kullanarak LCS nin bulunması
        int i = 0, j = 0;
        String out="";
        while(i < M && j < N) {
            if (x.charAt(i) == y.charAt(j)) 
            {// i ve j değerlerine göre x, y stringleri üzerinde dolaşarak eşleşme olup olmadığını kontrol ediyorum
                out += y.charAt(j);
                i++;
                j++;
            }
            else if (cozum[i+1][j] >= cozum[i][j+1]) i++;//her zaman en uzun alt kümeye gidebilmek için bu kontrolleri yapıyorum
            else j++;
        }
        System.out.println("LCS Length : "+out.length());
        System.out.println("LCS        : "+out);
 
    }
 
}

Dinamik Programlama Nedir?

Dinamik programlama karışık problemlerin daha basit düzeylere indirilerek çözülmesini esas alan bir optimizasyon yöntemidir. Optimizasyondaki amaç, problemdeki kısıtlayıcı koşullar altında bu problemle ilgili en iyi karara varmaktır. Bir problem üzerinde dinamik programlama uygulayabilmek için o problemin alt problemlere parçalanabilir veya bir önceki problemin karakteristiğini koruyacak şekilde çözümü daha kolay başka probleme dönüştürülebilir olması yeterlidir

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 ardışıklığıdır. Yani, başlangıçta alt problemlerin çözümü bulunup buradan elde edilen verilerle daha büyük alt problemler çözüldüğünde problemin kendisi de çözülmüş olmaktadır.

Nerelerde Kullanılır?

Dinamik programlama, aynı çözümlü küçük problemlere parçalanabilen tüm problemler için uygulanabilir. Fakat brute-force ile exponential zamanda çözülebilen problemlerde gerçek değerini gösterir. En basitinden fibonacci dizisinin hesabı için brute-force O(n!) zaman karmaşıklığına sahipken, dinamik programlama ile problem O(n) zamanda çözülebilmektedir.

DP ile çözülebilecek birkaç problem:

• Rod-cutting problem
• Knapsack problem
• Matrix-chain multiplication
• Assembly Line Scheduling
• Birçok string problemi(LCS, longest increasing subsequence, Levenshtein distance) …

Yapısı ve Kullanımı

Başlamadan önce, birazdan sıkça göreceğiniz memoization kavramına bakmanızı öneriyorum.

Dinamik Programlama Algoritmasının Kurulması

Bir problem için dinamik programlama algoritması yapmak için aşağıdaki dört adım uygulanır.

1. Characterize the structure of an optimal solution (En iyi çözümün karakteristiğinin belirlenmesi)
2. Recursively define the value of an optimal solution(En iyi çözümün özyinelemeli tanımı)
3. Compute the value of an optimal solution,typically in bottom-up fashion(En iyi çözümün değerini top-down with memoization veya bottom-up yaklaşımdan birini kullanarak hesaplanması(genel olarak bottom-up))
4. Construct an optimal solution from computed information(Hesaplanmış verileri kullanarak en iyi çözümü bul)

Yazılan dört adımın ilk üç adımı dinamik programlamanın temel üç adımıdır. Eğer optimal çözümün yalnızca değerine ihtiyacımız varsa(Ör: LCS probleminde eşleşen harf sayısı) yalnızca ilk üç adımı kullanmak yeterli olacaktır.

Farklı problemler için farklı algoritmalar kurulacağından, Rod-Cutting problemi üzerinden DP’yi anlatmaya çalışacağız.

Rod-Cutting problem (Çubuk kesme problemi)

Problem : n uzunluğunda bir çubuğumuz olsun, bu çubuğun her cm lik parçasınınsa gibi bir fiyatı olsun. Fiyat tablosu aşağıdaki gibi olduğuna göre, farklı n uzunluğundaki çubukları kaç parçaya bölersek en fazla kar edeceğimizi bulalım.

4 birimlik çubuk için soruyu çözecek olursak;

4 : 9
1+3 : 9
2+2 :10
1+1+1+1 : 4
1+1+2 :7 olur. Ve bu durumda en pahalı satışın çubuğu iki parçaya bölerek, 2+2 durumunda yapıldığını görebiliriz.

1- Characterizing a rod-cutting

Çubuğumuzu parçalayacağımız birimler i = 1,2,,n-1,n gibi tam sayılar olduğundan ayrışmanın karakteristiğini belirleyebiliriz. Örneğin 7 = 2+2+3 dersek, 7 birim uzunluğundaki çubuğu 2 adet 2cm ve bir adet 3cm olmak üzere 3 parçaya bölmüş oluruz. i değerim en küçük 1 en büyük n olabileceğinden, parça sayısı k yı 1<k<n şeklinde gösterebiliriz.

Tüm parçaların uzunluklarını toplarsak, elde ederiz.

Çubuğumun fiyatı parçaların fiyatları toplamı olacağından şeklinde gösterebiliriz.

Bir çubuğun en yüksek fiyatını ise şeklinde gösterebiliriz.

Burada, ‘i oluşturan her bir parça da kendini en pahalı yapacak parçalardan oluşmaktadır.

Genelleme yaparsak, maksimum çubuk fiyatı için şöyle diyebiliriz:

2- A Recursive solution

Yukarıdaki top-down recursive fonksiyon, genelleme yaparak bulduğumuz maksimum çubuk fiyatını geri döndürecektir.Dışarıdan p[1..n] şeklinde ücretleri tutan bir tamsayı dizisi ve çubuk uzunluğunu tutan bir n tamsayısı alır.
n == 0, fonksiyonun özyinelemesinin durmasını sağlayan kontroldür. Eşitlik sağlanmışsa 0 döndürülür.
Döndürülecek q değerinin doğru olması içinse q için bir en küçük ilk değeri atanır.5.satırda da bir for döngüsü ile her parça çağırılarak en büyük değer q içine atılır.
Problem çözümü için bu fonksiyonu kullanacak olursak, O(2^n) zaman karmaşıklığı olduğundan en büyük değerleri için çok uzun beklememiz gerekecektir.

3- Compute the maximum value of a price

A. Memoization kullanılarak Top-Down yaklaşım ile

Memoized-Cut-Rod(p,n) fonksiyonu, asıl işlemlerin yapan Memoized-Cut-Rod-Aux(p,n,r) fonksiyonunu çağırır. Bu fonksiyon içinde tanımlanan yardımcı array, bizi her defasında alt problem hesaplamaktan kurtarır.

Memoized-Cut-Rod-Aux(p,n,r) fonksiyonu recursive tanımladığımız Top-Down çalışan Rod-Cut(p,n) fonksiyonuna çok benzer. Farklı olarak ilk adımında dizi üzerinden kontrol yapar. Eğer bir alt problem daha önceden çözülmüşse, tekrar çözmeye gerek kalmadan değer doğrudan dizi üzerinden okunur. Çözülmemiş alt problem ise çözülerek dizi üzerine yazılır.

B. Bottom-Up yaklaşımı ile

Bottom-Up-Cut-Rod(p,n) fonksiyonunda i problem boyutu j alt problem boyutundan küçük olduğu sürece (i

Birinci satırda alt problemlerin çözümünü tutabilmek için r[0..n] dizisi yaratılır. Hemen altındaki satırda ise, hiç parça olmaması durumunun bir fiyatı olmayacağından r[0] elemanına 0 değeri atanır.

3. ve 6. Satırlar arasında j büyüklüğüne sahip tüm at problemler çözülür. j 1 değeriyle başlar ve n olana kadar büyür. Bu sayede en küçük alt problemlerden büyüklere doğru bir çözüm elde etmiş oluruz.

6.satırda r[j-i] de bulunan ücretle o an kontrol edilen ücretin toplamı (r[j-i]+p[i]) ile q, q değerini maksimim yapacak şekilde karşılaştırılır, ve en büyük toplam q ya atanır. 7. Satırda alt problem çözümleri güncellenir. 8. Satırda istenen değer geri döndürülür.
* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *

Dinamik programlama için kullandığımız Top-Down ve Bottom-Up yaklaşımların ikisi de asimptotik çalışma zamanına sahiptir. Bottom-Up-Cut-Rod fonksiyonunda iç içe iki for döngüsü olduğundan çalışma zamanına sahip denebilir. Aynı şekilde, Memoized-Cut-Rod-Aux fonksiyonunun 6 ve 7. Satırlarına bakacak olursak, for içinde fonksiyonun kendini n kere çağırdığını görebiliriz. Özyineleme gerçekleşirken her alt problem yalnızca bir kere hesaplanacağından (memoization sayesinde) 7. Satırda çağıracağımız fonksiyon da bize n gibi bir karmaşıklık getirir. Dolayısıyla Memoized-Cut-Rod için de çalışma zamanına sahip diyebiliriz.

4- Constructing a solution

Yukarıda yaptığımız hesaplamalar bize çözümü değil, yalnızca en iyi çözümün değerini getiriyordu. Eğer ihtiyacımız olan sadece bu değerse, fonksiyonu çağırmamızın ardından bize dönen değeri doğrudan kullanabiliriz. Eğer ki ihtiyacımız olan çözümün kendisiyse kullandığımız hesaplama(computing) algoritmalarından birini genişleterek çözümü de bir yerde tutacak hale getirmemiz gerekir. Bottom-Up-Cut-Rod fonksiyonun genişleterek çözüme gidelim.

Şeklinde bir genişletme ile çözüme ulaşabiliriz. Burada kullandığımız dizisi, tüm en iyi çözümleri içinde tutmaktadır.

Çözümün yazdırılmasını da aşağıdaki fonksiyonla yapalım:

Eğer fonksiyonumuzu Print-Cut-Rod-Solution( ) şeklinde verirsek aşağıdaki gibi bir çözümümüz olacaktır:

Longest Common Subsequance (En uzun ortak alt dizi)(LCS) problem

Problemin dinamik programlama ile çözümüne buradan ulaşabilirsiniz.

Algoritmanın iyileştirilmesi

Dinamik programlama sırasında birçok işlemi yeniden yapmak yerine alt problem çözümünü depoladığımızdan çözüme çok daha hızlı ulaşabiliriz. Fakat çok büyük problemler için bu bize büyük maliyette bir belleğe mal olabilir fibonacci sayısılarının bulunması, rod-cutting gibi problemler tek dizi üzerinde tutulduğundan O(n) bellek kullanırken LCS, Matrix Chain Manipulation gibi problemler O(n^2) bellek kullanırlar. Peki bu sorunun bir çözümü var mıdır?

Eğer bizden çözümün tamamı isteniyorsa maalesef yoktur. Fakat sadece çözümün değeri isteniyorsa çok küçük bellek kullanımlarıyla bu değer elde edilebilir. Örneğin, 35 sayısına kadar olan tüm fibonacci sayılarını listeleyebilmek için dizinin tamamı elimizde olmalıdır. Fakat bizden fib(35) değeri istenirse bunun için fib(34) ve fib(33) değerlerini bilmemiz yeterli olacaktır. Bu da fib(35) değerine O(1) bellek kullanarak ulaşabileceğimiz anlamına gelir. Aynı şekilde LCS probleminde bizden altdizinin ne olduğu yerine altdizinin uzunluğu istenirse, O(n^2) yerine O(n) bellek kullanarak değeri bulabiliriz.

Kaynaklar

“Introduction to Algorithms”, Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein, The MIT Press; 3rd edition, 2009

“Algoritmalar : teoriden uygulamalara” Vasif V. Nabiyev, Seçkin Yayınları,ikinci baskı 2009

www.columbia.edu/~cs2035/courses/csor4231.F09/dynamic.pdf

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

www.cs.cmu.edu/~avrim/451f09/lectures/lect1001.pdf

http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-046j-introduction-to-algorithms-sma-5503-fall-2005/video-lectures/

Hemen bir örnekle :

1
2
3
4
5
6
7
8
9

public class Hayvan{
        public Hayvan(){}
	public void sesCikar(){System.out.println("AbidikGubidik");}
}
public class Kopek extends Hayvan{
        public Kopek(){}
        @Override
	public void sesCikar(){System.out.println("BarkHavBarkHav");}
}

şeklinde iki class’ım olsun. Kopek sınıfımı, Hayvan sınıfımdan türetmiş olayım. Aşağıdaki işlem sırasında;

Hayvan minnos = new Hayvan();
Hayvan fino = new Kopek();
 
minnos.sesCikar();
fino.sesCikar();

minnos’un çıkaracağı ses bellidir -> “AbidikGubidik”
fino.sesCikar() fonksiyonu çağırıldığındaysa Dynamic Dispatch yapılır. fino’nun referansı hayvan olsa bile, Kopek sınıfıyla initialize edildiğinden fino “BarkHavBarkHav” sesi çıkaracaktır.

Not : Java’da override ettiğiniz bir metodun önüne @Override notunu(annotation) yazmasanız da olur. Yazarsanız, compile time errorların azalmasına, compilerın daha kolay işini görmesine yardımcı olursunuz.

Seçmeli sıralamanın gerçekleşimini gösteren animasyon

Seçmeli arama (selection sort) her bir adım sonunda en küçük değerin en başa getirildiği sıralama algoritmasıdır. Dizi içinde dolaşılarak en küçük değer en başa getirilir. Dizideki eleman sayısı N kadar dolaşma işlemi tekrarlandığında dizi üzerinde sırama ede edilmiş olur.

Performans

Dizimiz üzerinde N tane eleman olsun. Bu durumda N kadar kontrol döngüsü çalıştırılır. Bu döngülerden 1. için N, 2.iin N-1 … N-1. için 2, N.için 1 adet kontrol yapılır. Yani bu sayıları dizi toplamı alırsak N x(N+1)/2 = (N²+N)/2 kontrol yapılmış olur. Bu da worst-case O (n²) karmaşıklık anlamına gelir.

Buradan seçmeli sıralamanın çok performanslı bir sıralama olmadığını görebiliriz. Bu yüzden büyük diziler yerine, minik dizilerde kulanılması daha mantıklı olacaktır. Tercih sebebi ise yazımı çok kolay bil algoritmaya sahip olmasıdır.

Adım-Adım Uygulama

Elimizde  5 1 4 2 8 değerlerine sahip 5 elemanlı bir dizi olsun. Bunu selection sort kullanarak adım adım sıralayalım:

İlk döngü:
( 5 1 4 2 8 )
( 5 1 4 2 8 )
( 5 1 4 2 8 )
( 5 1 4 2 8 )
( 5 1 4 2 8 ) –>( 1 5 4 2 8 )

İkinci döngü:
( 1 5 4 2 8 )
( 1 5 4 2 8 )
( 1 5 4 2 8 )
( 1 5 4 2 8 ) –> ( 1 2 4 5 8 )

Üçüncü Döngü:
( 1 2 4 5 8 )
( 1 2 4 5 8 )
( 1 2 4 5 8 ) –> ( 1 2 4 5 8 )

Dördüncü Döngü:
( 1 2 4 5 8 )
( 1 2 4 5 8 ) –> ( 1 2 4 5 8 )

Sıralı dizim : ( 1 2 4 5 8 )

Algoritma gösterilirken, altı çizili değerler o an en küçük kontrolünün yapıldığı değerlerdir. kırmızılarsa o ana kadar karşılaşılan en küçük değer indexini tutar.

Ayrıca dikat edilirse, 2.döngüde sıralı dizi elde edilmesine rağmen iki döngü daha yapılmıştır.Bu yüzden en iyi durumda bile (best-case) algoritma O (n²) zaman karmaşıklığında çalışmaktadır

Pseudocode

[Sıralı arama algoritmasına ait pseudocode]
    for i ← 0 to n-2 do
    min ← i
    for j ← (i + 1) to n-1 do
        if A[j] < A[min]
            min ← j
    swap A[i] and A[min]

Kaynaklar

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