ALGORİTMALAR VE PROGRAMLAMA

Bir algoritmanın sahip olması gereken temel özellikler aşağıda listelenmiştir:

Girdi ve Çıktı Bilgisi: Algoritmalarda girdi ve çıktı bilgileri olmalıdır. Girdi bilgisi algoritmaya dışarıdan verilirken, çıktı bilgisi ise algoritma içerisinde üretilir. Bu

bilgiler, algoritma için tanımlı veri kümesine ait olmalıdır.

Açıklık: Algoritmayı oluşturan adımlar doğru ve kesin bir şekilde tanımlanmalıdır.

Doğruluk: Farklı girdi bilgileri ile çalışabilen algoritmalar, her girdi için doğru bir

çıktı üretmelidir.

Sonluluk: Algoritmaların daima bir sonu olmalıdır. Girilen veri boyutundan ba-

ğımsız bir şekilde, algoritma adımları farklı bir aşamaya geçebilmeli veya son- lanmalıdır. Algoritma adımları gerçekleştirilirken, algoritma sonsuz döngüye girmemelidir.

Verimlilik: Algoritmayı oluşturan adımlar, yapılan iş için kabul edilebilir bir süre içerisinde tamamlanmalıdır.

Genellik: Bir algoritma, aynı türdeki problemlerin hepsine uygulanabilir olmalıdır.

Sözde kod (pseudocode), bir algoritma veya program oluşturulurken kullanılan, konuşma diline benzer bir yapıya sahip, programlama dillerinin detaylarından uzak bir anlatım şeklidir.

Algoritmaların sözde kod ile gösterimi, oldukça yaygın ve etkili bir yöntemdir. Sözde kodlarda bir programlama diline benzeyen ifadeler kullanılsa da bu ifadelerin bilgisayar tarafından anlaşılması mümkün değildir.

Sözde kodlar, programlama mantığı ile konuşma dili cümlelerinin harmanlanmasından meydana gelir ve herkes tarafından rahatlıkla anlaşılabilir. Sözde kodu okuyan bir kişi, programlama dillerinin detaylarına takılmadan, algoritmanın çalışma mantığını kavrayabilir.

Verimlilik: Algoritmayı oluşturan adımlar, yapılan iş için kabul edilebilir bir süre içerisinde tamamlanmalıdır.

Bir algoritmanın açıklaması ve algoritmada yer alan adımlar, konuşma dili kuralları çerçe- vesinde ifade edilebilir. Bu gösterim yönteminde, algoritma açık ve kesin bir dille tanımlanır. Algoritmada yer alan adımlar liste halinde yazılır.

Akış şeması, algoritmaların gösteriminde kullanılan faydalı bir yöntemdir. Bir akış şemasında algoritma adımlarını ifade eden kutucuklar, adımlar arası geçişleri gösteren oklar, karar verme mekanizmaları olarak kullanılan şekiller bulunabilir.

Akış şeması, bir algoritmanın görsel halini ifade eder. Görsellik, algoritmaların daha kolay anlaşılabilmesine olanak sağlar. Programcılar ve çözümleyiciler tarafından yaygın olarak kullanılan akış şemalarını oluşturmak için birçok farklı çizim yazılımı bulunmaktadır.

Kendisini doğrudan veya dolaylı olarak çağıran algoritmalara özyinelemeli algoritma adı verilir. Bu algoritmalarda, problemler daha küçük ve basit parçalara indirgenir. Küçük parçalar için oluşturulan çözümlerin birleştirilmesiyle ana problemin çözümü elde edilir.

Geri izlemeli algoritmalar, genellikle optimizasyon problemlerinde kullanılan, prob- lem çözümünde tüm olasılıkları deneyen algoritmalardır. Bu algoritmalarda çözüm kademeli şekilde oluşturulur. Algoritma çözüm aşamasında ilerlerken, olası çözüm yollarının hepsini deneyerek bir sonraki adıma geçmeye çalışır. Algoritmanın dene- diği çözüm yolundan sonuç alınamazsa, algoritma bir önceki adımda bulunan diğer olası çözüm yollarına geri döner.

Geri izlemeli algoritmaların kullanımı ile çözülen birçok problem vardır. Bu problem- lerin başlıcaları aşağıda listelenmiştir:

Sudoku: 9 x 9’luk bir tablonun her satır ve sütununda 1’den 9’a kadar sayıların ol- ması gerekmektedir. Bazı değerlerin dolu olarak verildiği bulmaca nasıl çözülür?

Sekiz Vezir Problemi: Sekiz vezir, bir satranç tahtasına birbirlerine hamle yapama- yacak şekilde nasıl yerleştirilir?

Sırt Çantası Problemi: Elimizde kapasitesi belirli bir sırt çantası, ağırlığı ve değeri belirli nesneler vardır. Sırt çantasına hangi nesneler doldurulduğunda, çantaya ko- nan nesnelerin toplam değeri en fazla olur?

Böl ve yönet algoritmaları, problemlerin mümkün olan en küçük alt parçalara ayrıldığı, her bir alt parçanın diğerlerinden bağımsız şekilde çözüldüğü algoritmalardır. Problemin genel çözümü elde edilirken alt parçalara ait çözümler belirli bir sırayla bir araya getirilir.

Böl ve yönet algoritmaları, genellikle üç ana aşamadan meydana gelmektedir:

Bölme (Divide): Problemin daha küçük parçalara ayrıldığı aşamadır. Problem daha alt parçalara bölünemeyecek hale gelene kadar, özyinelemeli bir yaklaşımla

bölme işlemi gerçekleştirilir.

Yönetme (Conquer): Problemin alt parçalarının, birbirlerinden bağımsız olarak

çözüldüğü aşamadır.

Birleştirme (Merge): Problemin alt parçalarına ait çözümlerin, özyinelemeli bir

yaklaşımla birleştirildiği aşamadır.

Bir problem için mümkün olan en doğru çözümü hedefleyen algoritmalara açgözlü algo- ritmalar adı verilir. Açgözlü algoritmalarda yerel olarak optimum sonuç elde edilirken, bulunan sonuç her zaman için en iyi çözüme karşılık gelmeyebilir.

Açgözlü algoritmalar ile problem çözümündeki temel yaklaşım, problemin küçük bir alt kümesi için çözüm oluşturmak ve bu çözümü problemin geneline yaymaktır. Algorit- ma içerisinde yapılan bir seçim, o an için doğru olsa bile sonraki seçimlerde olumsuz etki yapabilir.

Bir problem için mümkün olan en doğru çözümü hedefleyen algoritmalara açgözlü algo- ritmalar adı verilir. Açgözlü algoritmalarda yerel olarak optimum sonuç elde edilirken, bulunan sonuç her zaman için en iyi çözüme karşılık gelmeyebilir.

Açgözlü algoritmalar ile problem çözümündeki temel yaklaşım, problemin küçük bir alt kümesi için çözüm oluşturmak ve bu çözümü problemin geneline yaymaktır. Algorit- ma içerisinde yapılan bir seçim, o an için doğru olsa bile sonraki seçimlerde olumsuz etki yapabilir.

Bir şehirden yola çıkan gezginin en fazla seyahat edeceği yolu hesaplama problemi, açgözlü bir algoritma ile çözülebilir. Bu yöntemde, mevcut şehirden gidilebilecek en uzak şehre gidilir. Şekil 1.5’teki ilk haritada gezgin 7 + 12 + 9 = 28 ile en uzak mesafeyi kat eder ve problemin en iyi çözümünü elde eder. İkinci haritada ise; gezgin yine 7 + 12 + 9 = 28 yolunu kullanır fakat en iyi çözümü elde edemez. Açgözlü algoritmanın yerel optimumda bulamadığı 7 + 10 + 32 = 49 yolu, en fazla seyahat edilen yol olmalıdır.

Bir algoritmanın sahip olması gereken temel özellikler aşağıda listelenmiştir:

Akış şeması, algoritmaların gösteriminde kullanılan faydalı bir yöntemdir. Bir akış şemasında algoritma adımlarını ifade eden kutucuklar, adımlar arası geçişleri gösteren oklar, karar verme mekanizmaları olarak kullanılan şekiller bulunabilir.

Akış şeması, bir algoritmanın görsel halini ifade eder. Görsellik, algoritmaların daha kolay anlaşılabilmesine olanak sağlar. Programcılar ve çözümleyiciler tarafından yaygın olarak kullanılan akış şemalarını oluşturmak için birçok farklı çizim yazılımı bulunmaktadır.

Kendisini doğrudan veya dolaylı olarak çağıran algoritmalara özyinelemeli algoritma adı verilir. Bu algoritmalarda, problemler daha küçük ve basit parçalara indirgenir. Küçük parçalar için oluşturulan çözümlerin birleştirilmesiyle ana problemin çözümü elde edilir.

Geri izlemeli algoritmalar, genellikle optimizasyon problemlerinde kullanılan, problem çözümünde tüm olasılıkları deneyen algoritmalardır. Bu algoritmalarda çözüm kademeli şekilde oluşturulur. Algoritma çözüm aşamasında ilerlerken, olası çözüm yollarının hepsini deneyerek bir sonraki adıma geçmeye çalışır. Algoritmanın denediği çözüm yolundan sonuç alınamazsa, algoritma bir önceki adımda bulunan diğer olası çözüm yollarına geri döner.

Böl ve yönet algoritmaları, problemlerin mümkün olan en küçük alt parçalara ayrıldığı, her bir alt parçanın diğerlerinden bağımsız şekilde çözüldüğü algoritmalardır. Problemin genel çözümü elde edilirken alt parçalara ait çözümler belirli bir sırayla bir araya getirilir.

Böl ve yönet algoritmaları, genellikle üç ana aşamadan meydana gelmektedir:

Dinamik programlama, karmaşık problemleri küçük parçalar halinde çözen, elde edilen sonuçları bilgisayar hafızasında bir veri yapısında saklayan, genel çözümü elde ederken de veri yapılarında saklanan sonuçları kullanan bir programlama yöntemidir.

Bir problemin dinamik programlama ile çözülebilmesi için problemin alt parçalara ayrılabilmesi ve genel çözümün bu alt parçalardan oluşturulabilmesi gerekmektedir. Dinamik programlama yaygın olarak optimizasyon problemlerinde kullanılır.

Bir problem için mümkün olan en doğru çözümü hedefleyen algoritmalara açgözlü algoritmalar adı verilir. Açgözlü algoritmalarda yerel olarak optimum sonuç elde edilirken, bulunan sonuç her zaman için en iyi çözüme karşılık gelmeyebilir.

Açgözlü algoritmalar ile problem çözümündeki temel yaklaşım, problemin küçük bir alt kümesi için çözüm oluşturmak ve bu çözümü problemin geneline yaymaktır. Algoritma içerisinde yapılan bir seçim, o an için doğru olsa bile sonraki seçimlerde olumsuz etki yapabilir.

Bir problemin çözümü aşamasında, kabul edilebilir bir çözüm elde edene kadar tüm olasılıkları deneyen algoritmalara kaba kuvvet algoritmaları denir.

Kaba kuvvet algoritmaları, genellikle problemin tanımından yola çıkarak en basit çözüm yolunu uygular ve rahatlıkla kodlanır. Fakat bu algoritmalarda çok fazla işlem yapılır ve çözüm yolu optimumdan uzaktır. Problemdeki veri hacmi büyüdükçe, kaba kuvvet algoritması ile çözüm şansı da azalır.

Bir liste içerisinde eleman aramak, kaba kuvvet algoritmaların kullanımıyla çözülebilecek problemlere bir örnektir. Listenin tüm elemanları sırayla kontrol edilerek, aranan elemanın listede olup olmadığına bakılabilir. Listenin eleman sayısı arttıkça, kaba kuvvet algoritmasının çalışma süresi ve yaptığı karşılaştırmalar da artacaktır.

Üst düzey programlamada veri içerisinde arama yapmak, veriye hızlı bir şekilde ulaşmak, bilgisayarın işlemcisini verimli kullanmak, aynı anda birçok isteğe cevap verebilmek gibi gereksinimler söz konusudur. Bilgisayar programlarının karmaşıklığı ve programda işlenen veri büyüklüğü arttıkça, verilerin daha sistematik ve verimli yönetilmesi gerekir.

Bilgisayar programlarında verilerin sistematik ve etkili bir şekilde organize edilmesi için veri yapıları kullanılır. Bir veri yapısı, içerdiği elemanların mantıksal düzeni ve elemanlar üzerinde yapılabilecek işlemler ile tanımlanır.

Bazı veri yapıları şunlardır:

Veri yapılarına örnek olarak, oldukça sık kullanılan bir veri yapısı çeşidi olan kuyruk verilebilir. Her kuyruğun bir başı ve sonu olur. Veriler kuyruğun baş tarafından girerken, son tarafından çıkar. Bu özellikten dolayı kuyruk veri yapısını bir marketteki ödeme sırasına benzetebiliriz.