ALGORİTMALAR VE PROGRAMLAMA - Deneme Sınavı - 14

Özyinelemeli algoritma: Kendisini doğrudan veya dolaylı olarak çağıran algoritmalara denir. 

Geri izlemeli algoritma: Problem çözümünde tüm olasılıkları deneyen algoritmalardır.

Böl ve yönet algoritması: Her bir alt parçanın diğerlerinden bağımsız şekilde çözüldüğü algoritmalardır.

Açgözlü algoritmalar: Bir problem için mümkün olan en doğru çözümü hedefleyen algoritmalara denir.

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

Bölme, yönetme ve birleştirme aşamalarından oluşan algoritma türü "Böl ve Yönet Algoritmaları"dır.

Veri yapıları şunlardır:

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.

Problemin alt parçalarının, birbirlerinden bağımsız olarakçözüldüğü aşama “yönetme” olarak adlandırılır. Birleştirme aşamasında ise özyinelemeli bir yaklaşım problemin alt parçalarına ait çözümler birleştirilir.

Her problem dinamik algoritma ile çözülemez. 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.

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?