Ünite 4: Algoritma Tasarımı

Hangi Problemler Algoritmalar ile Çözülebilir?

Günlük hayatımızda birçok problemi çözmek için algoritmaları kullanırız. Örneğin İstanbul’dan Sivas’a araba ile gitmek istediğimizi varsayalım. Hangi yolları kullanırsak en kısa mesafede istediğimiz yere ulaşabiliriz? Günümüzde yol tabiileri için animasyon cihazları kullanılmaktadır. Bu cihazlar ulaşmak istediğimiz yer için en kısa mesafeyi hesaplayıp yol tarifleri verebilmektedir. Bu cihazlarda, çeşitli ölçütler doğrultusunda en kısa mesafeyi hesaplayan algoritmalar çalışmaktadır. İnternette bir arama motoruna ulaşmak istediğimiz bilgiyi yazdığımızda, ilgili bütün sayfaları ve dokümanları sıralayabilmektedir. Bu işlem sırasında sadece ilgili sayfaları gösterebilmek için bir metin arama algoritması çalışmaktadır. Arama motorunun sonuç ekranında en çok ilgili olandan en az ilgili olana kadar bütün sonuçları listelemektedir. İnternetin yaygınlaşmasıyla arama motorları bilgiye ulaşmamızı kolaylaştırmaktadır. Örneğin, bankacılık işlemlerinde hem bilgisayarlarımızı hem de akıllı telefonlarımızı sıklıkla kullanmaya başladık. İşlemlerin çoğu elektronik olarak gerçekleştirildiği için bankacılık sistemlerinin güvenliliği önemini giderek arttırdı. Bankalar güvenliklerini arttırmak için çeşitli şifreleme algoritmaları kullanmaktadırlar. Akıllı telefonlarımızda kullandığımız uygulamalar ve oynadığımız oyunlar, algoritma kullanımının birer örneğidir. Akıllı telefonlarımızda ya da dijital fotoğraf makinelerinde yüz tanıma algoritmaları kullanılmaktadır. Böylece resim çekerken yüz bölgesine odaklama yapılabilmektedir.

Teknolojik Olarak Algoritmalar

Bulduğumuz çözüm yönteminin doğru cevap ile sonuçlandığını gösterebilmek için de algoritmalarla çalışmamız gerekmektedir. Her ne kadar günümüzde bilgisayarlar oldukça hızlı olsa da sonsuz hızda değiller ve ayrıca bilgisayar hafızalarının da belirli bir maliyeti bulunmaktadır. Sonsuz hızda bir bilgisayarımız olmadığı için algoritmalarla çalışmak neredeyse bir zorunluluktur. Elimizdeki rastgele 100 tane sayıyı sıralamak istiyorsak günümüz bilgisayarlarında hangi algoritmayı kullandığımızın fazla bir önemi olmayacaktır. Seçtiğimiz algoritma muhtemelen milisaniyeler içerisinde sonuç verecektir. Ancak, 100 yerine 10100 tane sayıyı sıralamak istersek bu sefer çok kısa sürelerde sonuç beklememiz söz konusu olamayacaktır. Bu sebeple, algoritmalar üzerinde çalışılması bir zorunluluk hâline gelmiştir. Algoritma tasarımını yaparken nerede ve ne şekilde kullanacağımızı düşünerek bilgisayarın hızını ve hafıza kapasitesini de göz önünde bulundurmamız gerekmektedir.

Algoritma ile Problem Çözme

Temel olarak bir algoritma tasarım ve analiz sürecinin isleyişinde ilk basamak problemi bütün ayrıntılarıyla anlamaktır. Problem tanımını okuyup kafamızda hiçbir şüphe kalmayacak şekilde anlamamız gerekmektedir. Algoritmayı tasarlamaya geçmeden önce ufak veri setleri üzerinde elle deneme yapmak, problemi anlamamızı kolaylaştırabilecektir. Karşılaşılabilecek bütün özel durumları da düşünmemiz gerekmektedir. Sadece toplama ve çıkarma operasyonlarını kullanarak bölme işlemi yapan bir algoritma tasarlamak istediğimizi düşünelim. Böyle bir problemde karşılaşabileceğimiz özel durum sıfıra bölme işlemi olabilir ve bölme işleminin sonucu tanımsız olacaktır. Problemi bütün ayrıntılarıyla anladıktan sonra düşünmemiz gereken husus, tasarlayacağımız algoritmayı hangi konfigürasyona sahip bilgisayarda çalıştırmak istediğimizdir. Kullanacağımız bilgisayarın işlemci hızı, hafıza kapasitesi vb. özellikleri tasarlayacağımız algoritmada etkilidir. Problemimiz çok karmaşık ve çözümü uzun süre gerektiriyorsa paralel programlama yöntemlerini kullanmaya karar verebiliriz. Problemimizi küçük parçalara böldükten sonra her bir parçayı ayrı bir bilgisayarda çözüp sonuçları birleştirerek asıl sonucu elde edebiliriz. Böylece problemimizi çok daha hızlı bir şekilde çözmüş oluruz. Sonraki aşamada, algoritma tasarlama süreci gelmektedir. Algoritmaları tasarlarken diziler, kuyruklar, ağaçlar vb. veri yapılarından faydalanabiliriz. Veri yapısını seçerken mutlaka avantajlarını ve dezavantajlarını dikkate almalıyız. Ayrıca kullanacağımız programlama dili de algoritma tasarımında değerlendirmemiz gereken hususlardan biri olmalıdır. Nesne tabanlı bir dil kullanacaksak, tasarımlarımız da bu dile uygun olmalıdır. Algoritma tasarımını yaparken doğal konuşma dili kullanabiliriz. Ancak programcılar arasında bir bütünlük sağlamak ve problemin çözümünü daha iyi ifade edebilmek amacıyla sözde kod (pseudocode) kullanabiliriz. Sözde kod, doğal dil ile programlama dili arasında bir problemin çözümünü ifade ediş biçimidir.

Tasarladığımız algoritmayı göstermenin diğer bir yöntemi de akış diyagramı kullanmaktır. Akış diyagramıyla basit algoritmaları rahatlıkla gösterebiliriz. Ancak karmaşık algoritmalar akış diyagramı ile gösterime çok uygun olmayabilir (Devitin, 2012). Algoritmaları tasarlarken interaktif veya özyinelemeli fonksiyonlardan hangisini kullanacağımıza karar verip, tasarımı bu doğrultuda yapmamız gerekmektedir. Algoritmayı tasarladıktan sonra, algoritmamızın bütün girişler için doğru sonucu vereceğini doğrulamamız gerekmektedir. Bu işlem bazı algoritmalar için nispeten kolay olmakla birlikte bazı algoritmalar için karmaşık bir süreç gerektirmektedir. Bir algoritmanın hatalı çalıştığını gösterebilmek için sadece bir tane yanlış sonuç yeterlidir, ancak doğru çalıştığını ispatlamak için bütün verilerde doğru çalıştığını teyit etmek gerekir. Örnek olarak sıralama algoritmasını ele alalım. Problemimizin kısıtlarını da düşünerek, tasarladığımız algoritmanın farklı eleman sayısı ve farklı elemanları sıralamak istediğimizde doğru sonucu vermesi gerekmektedir. Daha önce belirttiğimiz özel durumları da tasarımda göz önünde bulundurmalıyız. Örneğin, bölme işlemi yapan algoritmanın, sıfıra bölüm için tanımsız sonucunu vereceği de kontrol edilmelidir. Hazırladığımız algoritmanın kodunu yazmaya başlamadan önceki son işlemimiz algoritmayı analiz etmektir. Algoritmanın çalışma zamanı, başka bir ifadeyle, algoritma karmaşıklık düzeyi ve hafıza gereksinimleri analiz edilmelidir. Son işlemimiz, seçtiğimiz programlama dilinde algoritmamızın kodunu yazmaktır. Bu esnada, kullanacağımız programlama dilinin sunduğu imkânlar ölçüsünde bazı hazır fonksiyonlardan da faydalanmamız mümkün olabilir. Hazır fonksiyonlar beklentilerimizi tam olarak karşılamıyor ise kendi fonksiyonlarımızı kodlamamız gerekecektir. Kodu yazdıktan sonra belirli testlerden geçirmek, programın güvenilirliğini arttıracaktır.

Algoritma Tasarlama Teknikleri

Algoritmaları temel olarak iki gruba ayırabiliriz. Bunlar döngü (tekrarlama) algoritmaları ve özyinelemeli fonksiyon algoritmalarıdır. Döngü algoritmalarında, problemin çözümünü döngü içerisindeki tekrarlarla buluruz. Özyinelemeli fonksiyon algoritmalarında ise yazdığımız fonksiyon kendi içerisinde yine kendini çağırarak sonuca ulaşır. Her iki grubun da kendine has özellikleri vardır.

Döngü-Tekrarlama Algoritmaları

Elimizde n tane elemandan oluşan bir dizi olduğunu düşünelim. Bu dizinin içerisindeki en büyük elemanı nasıl buluruz? Bu problemde ilk akla gelen çözüm bütün elemanlara tek tek bakıp en büyük olan elemanı bulmak olabilir. Bu işlemi su şekilde yapabiliriz. Başlangıçta, dizinin ilk elemanını en büyük kabul ederiz. Daha sonra, en büyük kabul ettiğimiz değeri sırasıyla dizinin bütün elemanlarıyla karşılaştırırız. Herhangi bir sıradaki elemanın değeri, en büyük kabul ettiğimiz değerden büyükse en büyük eleman değerimizi güncelleriz. Dizinin sonraki elemanlarını karşılaştırırken güncellenmiş en büyük değerimizi kullanırız. Dizinin sonuna geldiğimizde ise dizinin tamamı açısından en büyük elemanı bulmuş oluruz.

Küçült-Fethet (Decrease&Conquer) Yöntemi ile Algoritma Tasarlama:

Bu algoritma tasarım yönteminde, problemin tamamının çözümüyle küçük bir parçasının çözümü arasında bir bağlantı vardır. Problemin çözümü aşağıdan yukarıya ya da yukarıdan aşağıya olabilir. Tanıma bakacak olursak problemin özyinelemeli fonksiyon uygulaması ile çözüleceğini düşünsek de döngü-tekrar algoritmaları ile de çözüme ulaşabiliriz (Devitin, 2012). Bunun için verilebilecek örneklerden biri araya sokma sıralama algoritmasıdır. Bu sıralama algoritması iskambil kâğıtlarını sıraladığımız algoritmaya benzemektedir. Bu algoritmada, problemi birer birer küçülterek çözüme ulaşırız. Örnekten de anlaşılacağı üzere, her iterasyonda bir tane elemanı, o anki sıralı dizide yerine koymaktayız. k’ıncı iterasyonda dizinin ilk k tane elemanı kendi içerisinde sıralıdır. k+1 aşamada [k+1] elemanını, var olan sıralı dizimizde uygun yere koyarız. Böylece dizideki eleman sayısı kadar iterasyon geçtiğinde, dizimiz sıralı hâle gelir.

Özyinelemeli Fonksiyon Algoritmaları ve BölFethet (Divite & Conquer) Yöntemi ile Algoritma Tasarımı

Böl-Fethet yöntemi en iyi bilinen algoritma tasarım yöntemlerinden biridir. yöntemindeki algoritmalar aşağıdaki gibi isleyiş yapısına sahiptir:

1. Öncelikli olarak problem genellikle eşit büyüklükteki alt parçalara ayrılır.
2. Her bir alt problem, genellikle özyinelemeli fonksiyon aracılığı ile çözülür.
3. Bütün alt problemlerin çözümü birleştirilerek genel sonuç elde edilir.

Örnek olarak problemimizin dört parçadan oluştuğunu varsayalım. Her bir alt problem teker teker çözülür. Alt problemlerin çözümünden sonra elimizdeki dört çözüm birleştirilir ve ana çözümü elde etmiş oluruz.