Programlama Ve Algoritmalar

Yanıt Açıklaması: II-Problemin girdi büyüklüğü belirlenir. IV)Algoritmanın temel operasyonu belirlenir. V)Temel operasyonun hangi parametreye göre değiştiği belirlenir. I)Temel operasyon için toplam ifadesi bulunur. III) Formüller ve kurallar kullanılarak algoritmanın verimlilik sınıfı bulunur.

Yanıt Açıklaması: Düğümler arasındaki kenar bağlantıları üzerinde sıfırdan farklı sayısal değerlerin yer aldığı çizge türüdür.

Yanıt Açıklaması: Değişken, döngü, fonksiyon derleme gibi ifadeler algoritmayı koda dönüştürürken kullanılan yapılardır. Bir işin nasıl yapılacağını tarif eden adımlar kümesi algoritmadır.

Yanıt Açıklaması: Çatışmalar, hash fonksiyonları için istenmeyen durumlardır. Verimli ve etkin bir hash fonksiyonu, şu özellikleri sağlamalıdır: i. Fonksiyon içerisinde hesaplamalar hızlı yapılmalıdır. ii. Hesaplama sonucu üretilen değerlerde minimum çatışma olmalıdır. iii. Özetleme tablosundaki tüm alanlar kullanılabilir olmalıdır. iv. Özetleme tablosundaki doluluklarda eşit dağılım sağlanmalıdır.

Yanıt Açıklaması: Yığın, verilerin doğrusal bir şekilde tutulduğu, ekleme ve çıkarma işlemlerinin en üst noktadan yapıldığı bir veri yapısıdır.

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

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

Yanıt Açıklaması: Ardışık arama, en temel arama algoritmasıdır. Bu algoritmanın çalışması için dizinin sıralı olmasına ihtiyaç bulunmamaktadır. Aranan eleman, sırasıyla dizinin her bir konumundaki eleman ile karşılaştırılır. Aranan elemanın değerinin dizinin elemanlarından birisiyle aynı olduğu görülürse algoritma başarılı bir şekilde sonlandırılır. Eğer aranan eleman dizinin içerisinde mevcut değilse, karşılaştırmalar dizinin ilk elemanından son elemanına kadar sürecektir.

Yanıt Açıklaması: Bir tümleşik geliştirme ortamında komutların çok hızlı biçimde taranması ve doğru komutun bulunması gerekmektedir. Bu komut yoksa, kullanıcı programı yazarken, yanlış yaptığının belirtilmesi tümleşik geliştirme ortamının kullanışlığını arttıracaktır. Bunun için en iyi yöntem anlık aramanın yapıldığı özetleme tablosu olacaktır.

Yanıt Açıklaması: C dilinde öncelikle dizinin tipi sonrasında dizinin adı ve son olarak dizinin boyutu verilerek tanımlama yapılır. int ile tam sayılardan oluşan bir dizi tanımlanmaktadır. Dizilerin ilk elemanının indisi 0, son elemanının indisi ise dizinin boyutunun bir eksiğidir.

Yanıt Açıklaması: Yönlü çizge, kenar bağlantılarının yönleri temsil eden oklarla gösterildiği çizgedir.

Yanıt Açıklaması: Ardışık arama yapılara 16’yı bulmak için dizide 4 işlem yapılır. 2’yi bulmak için ise 3 işlem yapılır. Toplamda 7 işlem yapılır.

Yanıt Açıklaması: Her diziye sıralama algoritması uygulandığında a seçeneğinde bulunan dizi ilk döngüde [3 1] -> [1 3] [3 2] ->[2 3] olarak dizilip sonuç [1 2 3 6 9] haline gelir. Diğer dizilerde ikinci veya üçüncü döngüde sıralama oluşur.

Yanıt Açıklaması: İkili arama için en kötü durumdaki zaman karmaşıklığı O(log(n)) olmaktadır.

Yanıt Açıklaması: Baloncuk algoritması azalan veya artan fark etmeden sadece yanaşık elemanların değiştiği bir algoritmadır. İlk başta bir boyutlu sonra iki boyutlu… dizilerin kontrolü sonucu algoritma işletildiğinde doğru cevap E’dir.

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.

Yanıt Açıklaması: Ardışık arama yapılara 1’i bulmak için dizide 4 işlem yapılır. 8’i bulmak için ise 3 işlem yapılır. Toplamda 7 işlem yapılır.

Yanıt Açıklaması: n tane sayının birleştirme sıralamasının alacağı zaman n.logn şeklinde hesaplanır.

Yanıt Açıklaması: Çözüm: Zaman karmaşıklığı algoritmada doğrudan döngülerle ilintilidir. Baloncuk algoritmasında dış döngü 1den başlayıp n’e kadar giderken iç döngü sırasıyla 1, 2 , 3, …n işlem yapmakta. Sonuçta toplam işlem sayısı : 1+ 2+ 3+ … n-1 olmakta. Matematik geçmişimizi hatırlarsak bu toplam (n-1) * n / 2 ye denk gelmektedir. Yani n 2 /2 + n/2 işlem gerekmektedir. Sonuçta n 2 belirleyici olacağından karmaşıklık O(n 2 ) olacaktır.

Yanıt Açıklaması: İkili arama, sıralı diziler üzerinde arama yapmak için kullanılan bir algoritmadır. Üzerinde arama yapılacak olan dizi sıralı durumda değilse, bu algoritmanın doğru çalışabilmesi için öncelikle dizinin sıralı hale getirilmesi gerekir. İkili arama algoritması çalışmaya başladığında, ilk olarak dizinin ilk ve son elemanlarının konumları tespit edilir. Bu bilgilerden faydalanılarak orta elemanın konumu hesaplanır. Daha sonra, aranan eleman dizinin orta elemanıyla karşılaştırılır ve ikisinin eşit olup olmadığına bakılır. Aranan eleman orta elemana eşit ise arama başarılı bir şekilde sonlandırılır. Aksi takdirde, aranan elemanın dizinin orta elemanından küçük veya büyük olma durumu incelenir. Aranan eleman orta elemandan büyük ise, aramaya orta eleman ile son eleman arasındaki dizi elemanları ile devam edilir. Tam tersi durum söz konusu ise, aramaya ilk eleman ile dizinin orta elemanı arasındaki dizi elemanları ile devam edilir. Bu işlem her tekrar edildiğinde ilk, orta veya son elemanların konumlarının değişmesi söz konusu olabilir. Soruda 7 elemanlı bir dizi bulunmaktadır. Söz konusu dizi içerisinde 25 sayısının aranması söz konusudur. Algoritma çalışmaya başladığında ilk, orta ve son elemanların konumları belirlenecektir. Bu dizinin 4. konumundaki 12 sayısı orta elemandır. Daha sonra, aranan eleman olan 25 sayısının orta elemana eşit, küçük veya büyük olması durumuna bakılmaktadır. Bu sayı, orta elemandan büyük olduğu için aramaya dizinin ortası ile sonu arasındaki elemanlardan devam edilir. Bu sebeple, ilk elemanın konum bilgisi güncellenecektir ve bu güncelleme sonrasında orta elemanın konumu yeniden hesaplanacaktır. Dolayısıyla ikinci karşılaştırma adımında, ilk eleman olan 15’ün konum bilgisi 5, orta eleman olan 20’nin konum bilgisi 6 ve son eleman olan 43’ün konum bilgisi ise 7’dir.