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

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.

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.

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ış semalarını oluşturmak için birçok farklı çizim yazılımı bulunmaktadı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.

Dinamik Programlama (Dynamic Programming)

Algoritma türleri şu şekilde sıralanabilir:

Dizi (array), aynı tipteki verilerin tek bir değişken altında tutulmasını sağlayan veri yapısıdır.

Satır ve sütunlardan oluşan tablolar şeklinde tanımlanabilen iki boyutlu diziler, çok boyutlu dizilerin en yalın halidir. m adet satır, n adet sütundan oluşan iki boyutlu bir dizi, toplam (m x n) elemana sahip olabilir. 4 satır ve 3 sütundan oluşan şeklin doğru yanıtı D seçeneğinde verilmiştir.

Bir düğümün sol alt ağacının yüksekliği ile sağ alt ağacının yüksekliği arasındaki farka denge faktörü adı verilir. Doğru cevap B'dir.

Açık adresleme çatışma çözümü için verilen üç fonksiyon da kullanılmaktadır.

Postorder gezinme yönteminde öncelikle sol alt ağaç, sonra sağ alt ağaç ve son olarak kök düğüme gidilir. Bu nedenle doğru cevap C dir.

-1

İkili ağaç veri yapısı kendi içerisinde alt ağaçlardan meydana geldiği için, ikili ağaçları gezinmede özyinelemeli fonksiyonlar kullanılır. İkili ağaçlardaki düğümler dolaşılırken farklı yöntemler uygulanabilirken, bilgisayar programında bu işi yapabilmek için kabul görmüş üç gezinme yöntemi bulunmaktadır:

i. Preorder Gezinme (Kök başta)

ii. Inorder Gezinme (Kök ortada)

iii. Postorder Gezinme (Kök sonda)

Doğru cevap E seçeneğidir.

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.

Çalışma zamanı tasarlanan algoritma ile problemin çözümüne ulaşabilmek için yapılan toplam temel operasyon sayısıdır.

Alan karmaşıklığı algoritmanın eleman sayısının çok büyük olduğu durumlarda, problemin çözümüne ulaşabilmeye yönelik bellek gereksinimidir.

N=56 olduğuna göre,

Bir algoritma çalıştığında kaç birim adımda sonuca ulaşacağı hesaplanarak aynı problemi çözen farklı algoritmaların verimliliği karşılaştırılabilir. Bilgisayar bilimcileri, fonksiyonların büyümesini de göz önünde bulundurarak algoritmaları karşılaştırırken kullanılmak üzere üç tane gösterim tanımlamıştır:

Büyük O Gösterimi

Büyük Ω Gösterimi

Büyük Θ Gösterimi

Bu gösterimlere göre, algoritmaları kendi arasında verimlilik açısından karşılaştırabiliriz.

Büyük O gösterimi ile fonksiyonun üst sınırı belirtilir.