Programlama Ve Algoritmalar Dersi 4. Ünite Sorularla Öğrenelim

Algoritma Tasarımı

Giriş

1- Algoritma nedir?

Cevap: Algoritma belirli değerleri ya da değerler kümesini giriş olarak alan, istenilen amaca uygun olarak bu değerleri bir takım işlemlerden geçirerek bir çıktı ya da çıktı kümesi oluşturan işlemlerin bütünüolarak tanımlanabilir.

2- Bilgisayarlarımız sonsuz hıza sahip ve bilgisayar hafızaları ücretsiz olsaydı yine de algoritmalar üzerinde çalışmamıza gerek olur muydu?

Cevap: Bu soruya vereceğimiz cevap şüphesiz evet olurdu. Bulduğumuz çözüm yönteminin doğru cevap ile sonuçlandığını gösterebilmek için de algoritmalarla çalışmamız gerekmektedir.

3- Bilgisayarın hızı ve hafıza kapasitesi algoritmalar üzerinde nasıl bir etki yapmaktadır?

Cevap: Her ne kadar günümüzde bilgisayarlar oldukça hızlı olsa da sonsuz hızda değiller ve ayrıca bilgisayar hafızalarının da belirli bir maliyeti bulunmaktadır. Başka bir ifadeyle, sonsuz hızda bir bilgisayarımız olmadığı için algoritmalar ve algoritmaların hızı üzerinde çalışmak neredeyse bir zorunluluktur. Şimdi, ünitemizin başında verdiğimiz sıralama algoritmasını düşünelim. Elimizdeki rastgele 100 tane sayıyı sıralamak istiyorsak günümüz bilgisayarlarında hangi algoritmayı kullandığımızın fazla bir önemi olmayacaktır. Seçtiğimiz algoritma muhtemelen milisaniyeler içerisinde sonuç verecektir. Ancak, 100 yerine 10100 tane sayıyı sıralamak istersek bu sefer çok kısa sü- relerde sonuçbeklememiz söz konusu olamayacaktır. Bu sebeple, algoritmalar üzerinde çalışılması bir zorunluluk hâline gelmiştir. Algoritma tasarımını yaparken nerede ve ne şekilde kullanacağımızı düşünerek bilgisayarın hızını ve hafıza kapasitesini de göz önünde bulundurmamız gerekmektedir.

Algoritma ile Problem Çözme

4- Temel olarak bir algoritma tasarım ve işleyiş aşamaları nasıl gerçekleşmektedir?

Cevap: Temel olarak bir algoritma tasarım ve işleyiş aşamaları aşağıdaki şemadaki gibi gerçekleşmektedir.

5- Algoritma tasarımı yaparken problem çok karmaşık ve çözümü uzun sürüyorsa nasıl bir yaklaşım geliştirilebilir?

Cevap: Kullanacağımız bilgisayarın işlemci hızı, hafıza kapasitesi vb. özellikleri tasarlayacağımız algoritmada etkilidir. Problemimiz çok karmaşık ve çözümü uzun süre gerektiriyorsa paralel programlama yöntemlerini kullanmaya karar verebiliriz. Problemimizi küçük parçalara böldükten sonra her bir parçayı ayrı bir bilgisayarda çözüp sonuçları birleştirerek asıl sonucu elde edebiliriz. Böylece problemimizi çok daha hızlı bir şekilde çözmüş oluruz

6- Üçtane sayının ortalamasını hesaplayan bir algoritmayı sözde kod ile nasıl ifade edebiliriz?

Cevap: Üç tane sayının ortalamasını hesaplayan bir algoritma tasarlayıp sözde kod ile ifade edelim: Sayıların değerlerini sayı1, sayı2 ve sayı3 olarak belirle Ortalama = (sayı1 + sayı2 + sayı3) / 3 Kullanıcıya ortalama değerini göster

7- Algoritmanın tasarımı ve analizi yapılırken problemi anlama aşamasından sonra hangi aşama gelir?

Cevap: Problemi anladıktan sonraki aşamada, algoritma tasarlama süreci gelmektedir. Algoritmaları tasarlarken diziler, kuyruklar, ağaçlar vb. veri yapılarından faydalanabiliriz. Veri yapısını seçerken mutlaka avantajlarını ve dezavantajlarını dikkate almalıyız. Ayrıca kullanacağımız programlama dili de algoritma tasarımında değerlendirmemiz gereken hususlardan biri olmalıdır. Nesne tabanlı bir dil kullanacaksak, tasarımlarımız da bu dile uygun olmalıdır.

Algoritma Tasarlama Teknikleri

8- Elimizde n tane elemandan oluşan bir dizi olduğunu düşünelim. Bu dizinin içerisindeki en büyük elemanı nasıl buluruz?

Cevap: Bu problemde ilk akla gelen çözüm bütün elemanlara tek tek bakıp en büyük olan elemanı bulmak olabilir. Bu işlemi şu şekilde yapabiliriz. Başlangıçta, dizinin ilk elemanını en büyük kabul ederiz. Daha sonra, en büyük kabul ettiğimiz değeri sırasıyla dizinin bütün elemanlarıyla karşılaştırırız. Herhangi bir sıradaki elemanın değeri, en büyük kabul ettiğimiz değerden büyükse en büyük eleman değerimizi gün- celleriz. Dizinin sonraki elemanlarını karşılaştırırken güncellenmiş en büyük değerimizi kullanırız. Dizinin sonuna geldiğimizde ise dizinin tamamı açısından en büyük elemanı bulmuş oluruz

Algoritma ile Problem Çözme

9- Akış diyagramları ile daha çok ne tip algoritmalar göstermek doğrudur?

Cevap: Tasarladığımız algoritmayı göstermenin diğer bir yöntemi de akışdiyagramı kullanmaktır. Akışdiyagramıyla basit algoritmaları rahatlıkla gösterebiliriz. Ancak karmaşık algoritmalar akışdiyagramı ile gösterime çok uygun olmayabilir.

Algoritma Tasarlama Teknikleri

10- Algoritmalar temel olarak kaça ayrılır?

Cevap: Algoritmaları temel olarak iki gruba ayırabiliriz. Bunlar döngü (tekrarlama) algoritmaları ve özyinelemeli fonksiyon algoritmalarıdır. Döngüalgoritmalarında, problemin çözümünüdöngüiçerisindeki tekrarlarla buluruz. Özyinelemeli fonksiyon algoritmalarında ise yazdığımız fonksiyon kendi içerisinde yine kendini çağırarak sonuca ulaşır. Her iki grubun da kendine has özellikleri vardır.

Algoritma ile Problem Çözme

11- Algoritma tasarlandıktan sonra doğruluğu nasıl test edilir?

Cevap: Algoritmayı tasarladıktan sonra, algoritmamızın bütün girişler için doğru sonucu vereceğini doğrulamamız gerekmektedir. Bu işlem bazı algoritmalar için nispeten kolay olmakla birlikte bazı algoritmalar için karmaşık bir süreç gerektirmektedir. Bir algoritmanın hatalı çalıştığını gösterebilmek için sadece bir tane yanlışsonuçyeterlidir, ancak doğru çalıştığını ispatlamak için bütün verilerde doğru çalıştığını teyit etmek gerekir. Örnek ola- rak sıralama algoritmasını ele alalım. Problemimizin kısıtlarını da düşünerek, tasarladığımız algoritmanın farklı eleman sayısı ve farklı elemanları sıralamak istediğimizde doğru sonucu vermesi gerekmektedir. Daha önce belirttiğimiz özel durumları da tasarımda göz önünde bulundurmalıyız. Örneğin, bölme işlemi yapan algoritmanın, sıfıra bölüm için tanımsız sonucunu vereceği de kontrol edilmelidir.

12- Algoritma kodunu yazmadan önceki son işlem nedir?

Cevap: Hazırladığımız algoritmanın kodunu yazmaya başlamadan önceki son işlemimiz algoritmayı analiz etmektir.

Algoritmanın çalışma zamanı, başka bir ifadeyle, algoritma karmaşıklık düzeyi ve hafıza gereksinimleri analiz edilmelidir.

Algoritma Tasarlama Teknikleri

13- Verilen bir dizide elemanların toplamını hesaplayan fonksiyonu C dilinde nasıl yazabiliriz?

Cevap: Söz konusu fonksiyon diziyi ve dizideki eleman sayısını girişolarak almaktadır. Öncelik olarak toplam değerini tutacağımız değeri sıfır yapmaktayız. Daha sonra bir döngü içerisinde dizinin bütün elemanlarını sırasıyla bu toplam değerine ekliyoruz. Dizinin sonuna geldiğimizde elimizdeki toplam değeri, aradığımız sonucu oluşturmaktadır.

14- Fibonacci serisinin elemanlarını hesaplayan tekrarlamalı bir algoritma nasıl yazılabilir?

Cevap: Matematikte sıkça karşımıza çıkan ve bilinen problemlerden biri de Fibonacci serisi hakkındadır. Bilindiği üzere, bu serideki bir eleman kendinden önce gelen iki elemanın toplamına eşittir. Bu doğrultuda, Fibonacci serisi aşağıdaki şekilde ilerlemektedir: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ... Şimdi, bu serinin elemanlarını hesaplayan tekrarlamalı bir algoritma yazalım. Serinin tanımında ilk elemanın 0 ve ikinci elemanın 1 olduğu belirtilmişti. Bu doğrultuda, programımızda üç farklı değişken (ilk, iki, sonraki) tanımlayıp programın başlangıcında ilk değişkenine 0 ve iki değişkenine 1 değeri atıyoruz. Sonra, ilk ve son elemanlarını toplayıp serinin tanımında verildiği gibi bir sonraki elemanın değerini hesaplıyoruz. Sonraki iterasyona geçmeden önce ilk ve iki değişkenlerimizin değerini güncelliyoruz. Böylece, bir döngü içerisinde istenilen sayı kadar Fibonacci serisindeki elemanları hesaplayabiliyoruz.

15- Küçült-Fethet yöntemi ile araya sokma algoritması nasıl tasarlanabilir?

Cevap: Bu algoritma tasarım yönteminde, problemin tamamının çözümüyle küçük bir parçasının çözümü arasında bir bağlantı vardır. Problemin çözümüaşağıdan yukarıya ya da yukarıdan aşağıya olabilir. Tanıma bakacak olursak problemin özyinelemeli fonksiyon uygulaması ile çözüleceğini düşünsek de döngü-tekrar algoritmaları ile de çözüme ulaşabiliriz . Bunun için verilebilecek örneklerden biri araya sokma sıralama algoritmasıdır. Bu sıralama algoritması iskambil kağıtlarını sıraladığımız algoritmaya benzemektedir. Bu algoritmada, problemi birer birer küçülterek çözüme ulaşırız. Örnekten de anlaşılacağı üzere, her iterasyonda bir tane elemanı, o anki sıralı dizide yerine koymaktayız. k’ıncı iterasyonda dizinin ilk k tane elemanı kendi içerisinde sıralıdır. k+1 aşamada A[k+1] elemanını, var olan sıralı dizimizde uygun yere koyarız. Böylece dizideki eleman sayısı kadar iterasyon geçtiğinde, dizimiz sıralı hâle gelir. Örnek:

16- Böl-Fethet yöntemindeki algoritmalar nasıl bir işleyiş yapısına sahiptir?

Cevap: Böl-Fethet yöntemi en iyi bilinen algoritma tasarım yöntemlerinden biridir. Böl-Fethet yöntemindeki algoritmalar aşağıdaki gibi işleyişyapısına sahiptir: 1. Öncelikli olarak problem genellikle eşit büyüklükteki alt parçalara ayrılır.2. Her bir alt problem, genellikle özyinelemeli fonksiyon aracılığı ile çözülür.3. Bütün alt problemlerin çözümübirleştirilerek genel sonuç elde edilir.

17- 1'den N'e kadar olan sayıların toplamını hesaplayan özyinelemeli bir fonksiyon nasıl yazılır?

Cevap:

18- 1'den 4'e kadar olan sayıların toplamını hesaplayan C kodu nasıl yazılabilir?

Cevap: Bu problemi, 1’den 3’e kadar olan sayıların toplamına 4 sayısını ekleyerek bulabiliriz. Problemin en küçük parçasına geldiğimizde, yani 1’e kadar olan sayıların toplamını hesapladıktan sonra geriye doğru gelerek bulduğumuz sonuçları birleştirerek ana sonuca ulaşmaktayız.

19- 8 boyutlu bir dizinin toplamını hesaplayan özyineleme ağacı nasıldır?

Cevap: Aşağıdaki şekilde dizideki eleman sayısı 8 olduğundaki özyineleme ağacının yapısı görünmektedir. Problemin çözümüne, ağacın yapraklarındaki sonuçlar birleştirilerek başlanır ve birleştirme işlemi ağacın kökünde son bulur. Böylece genel çözüm hesaplanmışolur.

20- Dördüncü Fibonacci sayısını hesaplayan özyinelemeli fonksiyon ağacı nasıl gösterilebilir?

Cevap: DördüncüFibonacci sayısının özyinelemeli fonksiyon ağacı aşağıdaki şekilde verilmiştir. Bu ağaçtan da görüldüğü üzere ağacımızı oluştururken taban duruma gelince ağacımızın yaprakları oluşmuşolur. Bu dizi için taban durumumuz, dizinin 0. ve 1. elemanlarıdır. Bundan sonra gelecek bütün elemanları, bu elemanlara bağlı olarak hesaplayabiliriz.

Sıra-(Soruid) 1-(866555) 2-(866566) 3-(866578) 4-(866630) 5-(866655) 6-(866672) 7-(867289) 8-(866701) 9-(867298) 10-(867320) 11-(867302) 12-(867310) 13-(866714) 14-(867227) 15-(867228) 16-(867230) 17-(867328) 18-(867234) 19-(867257) 20-(867266)

Yaz Okulu Kayıt ve Ders Seçme
28 Haziran 2021 Pazartesi