Programlama Ve Algoritmalar

Yanıt Açıklaması: Algoritmayı oluşturan adımlar yapılan iş için kabul edilebilir bir süre içerisinde tamamlanmalıdır. Ayrıca algoritmanın genellik özelliğine göre bir algoritma aynı türdeki tüm problemlere uygulanabilir olmalıdır.

Yanıt Açıklaması: Doğal dil ile programlama dili arasında bir problemin çözümünü ifade ediş biçimi doğal koddur.

Yanıt Açıklaması: İkili arama yöntemi kullanıldığında iki elemanın da dizide olmadığı göz önünde bulundurularak her biri için 3 karşılaştırma yapılması gerektiği anlaşılmaktadır. Toplam 3+3 = 6 karşılaştırma yapmak gerekir.

Yanıt Açıklaması: Bir algoritmayı analiz etmek, genel olarak şu adımlardan oluşmaktadır 1. Problemin girdi büyüklüğünü veren parametre belirlenir. 2. Algoritmanın temel operasyonu belirlenir. 3. Temel operasyonun sadece girdi büyüklüğüne bağlı olarak mı değiştiği kontrol edilir. Eğer başka parametrelere göre de değişiyorsa bunlar belirlenir. 4. Temel operasyon için toplam ifadesi bulunur. 5. Toplam ifadeleri için verilen standart formüller ve kurallar kullanılarak algoritmanın ait olduğu verimlilik sınıfı bulunur.

Yanıt Açıklaması: Dizinin ilk elemanı seçilip daha sonraki elemanlar bu elemana göre karşılaştırılığında en büyük değeri bulmayı garanti etmek için N-1 defa döngü çalıştırılmalıdır.

Yanıt Açıklaması: C seçeneği hash fonksiyonları ile ilgili bir seçenek değildir. Soruda tanımlanan yöntem açık adresleme ve buradaki doğrusal sınamayı tarif etmektedir.

Yanıt Açıklaması: En kötü durumdaki zaman karmaşıklığı, algoritmanın çalışmasının en uzun sürebileceği durumu ifade etmek için kullanılır.  İkili arama algoritması n elemanlı bir dizi için en kötü durumda log2(n) adet karşılaştırma yapmaya ihtiyaç duymaktadır. Dolayısıyla ikili arama algoritmasının en kötü durumdaki zaman karmaşıklığının O(log(n)) olduğunu söyleyebiliriz. 128 elemanlı bir dizi için ikili arama algoritmasının en kötü durumdaki zaman karmaşıklığı:’dir.

Yanıt Açıklaması: Çok yüksek miktarda ikili arama sonucu aranılan elemanlar bazen 1. Bazen 2., bazen 3. vb … bazen de 9. karşılaştırmada bulunacaktır. Sonuçta ortalamaya vurulduğu taktirde (1 + 9) / 2 = 5 sonucuna ulaşılmaktadır. İkili aramada en hızlı cevap 1. karşılaştırmada, en yavaş cevap da log2(512) = 9 karşılaştırmada elde edilecektir.

Yanıt Açıklaması: Dizi incelendiğinde hem 5 hem 10 bu dizi içinde yer almamakta. Dolayısıyla baştan sona tüm dizi elemanları kontrol edilmektedir. Dizi eleman sayısı 9 olduğundan 2*9 = 18 karşılaştırma yapılması gerekir.

Yanıt Açıklaması: Ikinci karşılaştırma adımında soldaki üç eleman üzerine işlem yapılır.

Yanıt Açıklaması: Araya sokarak sıralama algoritması, dizinin elemanlarının kendilerinden önce gelen elemanlarla karşılaştırılması ve gerektiğinde birbirleriyle yer değiştirmeleri prensibine dayanır. Her bir adımda (iterasyonda), dizi elemanları üzerinde soldan sağa doğru hareket edilerek, kendisinden önce gelenlerle karşılaştırılacak bir anahtar eleman seçilir. Bu anahtar eleman, kendisinden önce gelen diğer tüm elemanlarla sırayla karşılaştırılır. Küçükten bü- yüğe doğru sıralama yaparken, kendisinden önce gelen eleman daha büyük ise bu eleman dizide sağa doğru kaydırılır. Dolayısıyla her adımda, dizide anahtar olarak seçilen eleman geçici olarak silinecektir. Bu karşılaştırma ve kaydırma işlemi, anahtar elemandan öncekiler kendisinden daha büyük olduğu sürece devam eder. Karşılaştırmalar tamamlanmışşa anahtar olarak seçilen eleman dizide uygun bir konuma yerleştirilir.

Yanıt Açıklaması: Bir veri kümesi içerisinde en küçük elemanın hızlıca bulunmasını sağlayan veri yapısı yığın ağaçlarıdır.

Yanıt Açıklaması: Kod yazma tasarım işleminin son adımıdır.

Yanıt Açıklaması: 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.

Yanıt Açıklaması: Bir algoritmayı analiz etmek, genel olarak aşağıda verilen adımlardan oluşmaktadır: Problemin girdi büyüklüğünü veren parametre belirlenir. Algoritmanın temel operasyonu belirlenir. Temel operasyonun sadece girdi büyüklüğüne bağlı olarak mı değiştiği kontrol edilir. Eğer başka parametrelere göre de değişiyorsa bunlar belirlenir. Temel operasyon için toplam ifadesi bulunur. Toplam ifadeleri için verilen standart formüller ve kurallar kullanılarak algoritmanın ait olduğu verimlilik sınıfı bulunur. Bu bilgilerden anlaşıldığı gibi A seçeneği bu adımlar arasında yer almaz.

Yanıt Açıklaması: Enine arama, çizgenin bir düğümünden başlanarak, o düğümün komşu düğümlerinin ve onların da komşularının sırayla ziyaret edildiği arama algoritmasıdır. Dolayısıyla takip edilen ziyaret sırası S, A, B, C, D, E, F, H, G’dir.

Yanıt Açıklaması: ardışık arama algoritması için zaman karmaşıklığı O(n) dir.

Yanıt Açıklaması: Ikinci karşılaştırmada sağdaki üç eleman üzerinde işlem yapılır ve 5,6,7 olarak sıralanırlar.

Yanıt Açıklaması: Birleştirerek sıralama O(n 2 ) karmaşıklık seviyesine sahip değildir.

Yanıt Açıklaması: Özyinelemeli fonksiyonların analizini yaparken gerçekleştirilecek işlemler aşağıdaki gibidir: Girdi büyüklüğünü veren parametre belirlenir. Algoritmanın temel operasyonu belirlenir. Girdi parametresine göre problemin temel operasyonunun çalışma sayısının değişip değişmeyeceği belirlenir. Başlangıç koşulları ile birlikte algoritmanın özyinelemeli fonksiyon bağıntısı yazılır. Fonksiyonların büyümesi ve toplam ifadeleri kullanılarak özyineleme bağıntısı çözülür ve zaman karmaşıklığı bulunur.