BİL204U-ALGORİTMALAR
Ünite 3: Algoritma Tasarım İlkeleri ve Gösterim Yöntemleri
Giriş
Programcıların program yazmak için genellikle üst düzey diller kullanırlar. Ancak, yeni bir projeye başladıklarında, asla ilk adım olarak kod yazmaya başlamazlar. Programın bir tasarımını oluşturarak başlarlar. Programlar yazılmadan önce dikkatlice tasarlanmalıdır. Tasarım sürecinde programcılar, program modelleri oluşturmak için sözde kod ve akış şemaları gibi araçlar kullanır.
Bilgisayar Programları ve Algoritmalar
Bilgisayarlar programlanabildikleri için çok çeşitli şeyler yapabilirler. Bu, bilgisayarların yalnızca bir işi yapmak için değil, programlarının onlara yapmalarını söylediği herhangi bir işi yapmak için tasarlandıkları anlamına gelir. Aslında her bilgisayar programı, bilgisayarın bir görevi gerçekleştirmek için izlediği bir dizi talimattır.
Bilgisayar Programı
Programlar genellikle yazılım olarak adlandırılır. Yazılım bir bilgisayar için son derece hayatidir çünkü yazılım olmadan bilgisayar hiçbir şey yapamaz. Bilgisayarlarımızı kullanışlı hâle getirmek için kullandığımız tüm yazılımlar, programcılar tarafından oluşturulur. Bilgisayarlarımızı kullanışlı hale getirmek için kullandığımız tüm yazılımlar, programcılar veya yazılım geliştiriciler olarak bilinen kişiler tarafından oluşturulur. Bir programcı veya yazılım geliştiricisi, bilgisayar programlarını tasarlamak, oluşturmak ve test etmek için gerekli eğitim ve becerilere sahip bir kişidir.
Bir Programı Tasarlamak
Günümüzde bir programcının, program yazmak için tipik olarak yüksek seviyeli diller kullanması gerekmektedir ancak hangi profesyonel programcıya sorarsanız sorun program yazmadan önce dikkatlice tasarlanması gerektiğini size söyler. Başlanacak yeni bir projede her zaman ilk adım doğrudan kodlamanın içine girmek değil, programı tasarlamaktır.
Program tasarlandıktan sonra bir yüksek seviye dilde kod yazılmaya başlanır. Unutulmamalıdır ki nasıl, insanların birbirleri ile iletişimi kurarken kullandıkları dillerin bazı söz dizimi kuralları varsa, programlama dillerinin de vardır. Bir dilin söz dizimi kuralları, anahtar kelimelerin, operatörlerin ve noktalama karakterlerinin nasıl kullanılabileceğini ve komutların yapısını belirler.
Program bir söz dizimi hatası veya yanlış yazılmış bir anahtar sözcük gibi basit bir hata içeriyorsa, derleyici veya yorumlayıcı hatanın ne olduğunu belirten bir hata mesajı görüntüler. Hemen hemen tüm kodlar, ilk yazıldığında söz dizimi hataları içerir, bu nedenle programcının bunları düzeltmek için genellikle biraz zaman harcaması gerekmektedir. Tüm söz dizimi hataları ve basit yazım hataları düzeltildikten sonra, program derlenebilir ve bir makine dili programına çevrilebilir (veya kullanılan dile bağlı olarak bir yorumlayıcı tarafından yürütülebilir).
Kod yürütülebilir bir formda olduğunda, herhangi bir mantık hatası olup olmadığını belirlemek için test edilmedir. Mantık hatası, programın çalışmasını engellemeyen ancak yanlış sonuçlar vermesine neden olan bir hatadır. Matematiksel hatalar, mantık hatalarının yaygın nedenlerinden biridir.
Mantık hataları varsa, programcı kodun hatalarını ayıklar. Bu, programcının hataya neden olan kodu bulup düzelttiği anlamına gelir. Bazen bu süreç sırasında programcı orijinal tasarımın değiştirilmesi gerektiğini fark eder. Program geliştirme döngüsü olarak bilinen tüm bu süreç, programda hiçbir hata kalmayana kadar tekrarlanmalıdır.
Algoritma Tasarımı
Algoritma, bir görevi gerçekleştirmek için atılması gereken bir dizi iyi tanımlanmış mantıksal adımdır. Algoritma tasarlama süreci aşağıdaki iki adımda özetlenebilir:
• Programın gerçekleştireceği görevi anlamak • Program verilen görevleri gerçekleştirecekken uygulaması gereken adımları hesaplamak
Programın gerçekleştireceği adımları belirlemeden önce bir programın ne yapması gerektiğini anlamanız önemlidir. Tipik olarak, profesyonel bir programcı bunu doğrudan müşteriyle çalışarak anlamaya çalışır.
Görüşme sırasında müşteri, programın gerçekleştirmesi gereken görevi açıklayacak ve programcı görev hakkında mümkün olduğunca çok ayrıntıyı ortaya çıkarmak için sorular soracaktır.
Programcı, görüşmeler sırasında müşteriden toplanan bilgileri inceler ve farklı yazılım gereksinimlerinin bir listesini oluşturur. Bir yazılım gereksinimi, müşteriyi memnun etmek için programın gerçekleştirmesi gereken tek bir işlevdir.
Programın gerçekleştireceği görev anlaşıldıktan ve işlev listesi oluşturulduktan sonra, her bir işlev bir dizi alt adıma bölünür. Bu süreç, bir görevi başka bir kişinin izleyebileceği bir dizi adıma bölmenize benzer.
Örneğin, küçük kız kardeşinizin size suyu nasıl kaynatacağınızı sorduğunu varsayalım. Ocağın yanında iş yapmasına güvenilecek kadar büyük olduğunu varsayarsak, bu görevi aşağıdaki gibi bir dizi adıma bölebiliriz:
1. Cezveye istenilen miktar kadar su koy. 2. Cezveyi ocağa yerleştir. 3. Ocağı yüksek ateşe ayarla. 4. Sudan büyük kabarcıklar çıkana kadar suyu izle. Bu olduğunda su kaynamıştır.
Bu, bir görevi gerçekleştirmek için atılması gereken bir dizi iyi tanımlanmış mantıksal adım olan bir algoritma örneğidir. Bu algoritmadaki adımların sıralı verildiğine dikkat edin. Örneğin; Adım 1, Adım 2’den önce gerçekleştirilmelidir. Küçük kız kardeşiniz bu adımları tam olarak göründükleri gibi ve doğru sırayla takip ederse, suyu başarıyla kaynatabilmesi gerekir.
Bir programcı, elindeki programın gerçekleştirmesi gereken görevi benzer şekilde parçalara ayırabilir. Böylece, atılması gereken tüm mantıksal adımları listeleyen bir algoritma oluşturulur. Örneğin, saatlik ücretli bir çalışanın brüt ücretini hesaplamak ve görüntülemek için bir program yazmanızın istendiğini varsayalım. Bu durumda atılması gereken adımlar aşağıdaki gibi olmalıdır. Bu algoritma günlük dilde ifade edilmiştir.
1. Çalışılan saat sayısını alın. 2. Saatlik ödeme ücretini alın. 3. Çalışılan saat sayısını saatlik ücret oranıyla çarpın. 4. Adım 3’te gerçekleştirilen hesaplamanın sonucunu görüntüleyin.
Algoritma Gösterimleri
Esasen algoritma bir problemi çözmek için geliştirilen çözüm yolunu ifade etmekten başka bir şey değildir. Programlama sürecindeki amaç algoritma adımlarının koda çevrilmesidir. Bu noktada algoritmanın programlama dilinin yapısından ve söz diziminden bağımsız olarak ifade edilmesi gerekmektedir. Geliştirilen algoritmaları ifade etmenin birçok yolu bulunmaktadır. Bu yollar görsel veya metinsel olabilmektedir. Algoritmayı ifade etmenin en bilinen yolları günlük dil, akış diyagramları ve sözde (pseudo) koddur.
Günlük Dil
Algoritmaların ifade edilmesi için kullanılabilecek ilk yol, adımların herkesin anlayabileceği şekilde verildiği günlük dil kullanımıdır. Günlük dil kullanımı programlama dillerinden oldukça uzak ve kurallardan olabildiğince arınmış bir kullanımdır.
Sözde (Pseudo)Kod
Her programlama dilinin, programcının bir program yazarken uyması gereken, söz dizimi olarak bilinen katı kuralları olduğundan, programcı bu kuralları ihlal eden bir kod yazarsa, bir söz dizimi hatası ortaya çıkar ve program derlenemez veya yürütülemez. Bu durumda, programcının hatayı bulması ve düzeltmesi gerekir.
Yanlış yazılmış kelimeler ve unutulmuş noktalama işaretleri gibi küçük eksiklikler bile söz dizimi hatalarına neden olabilir (ör: String yerine string ifadesinin kullanılması). Bu nedenle uygulama kodlama yüksek düzeyde dikkat ve zaman gerektiren bir süreçtir. Programcılar bu süreci hızlandırmak ve ilk tasarım aşamalarını kolaylaştırmak için, programları sözde kod ile yazmayı yararlı bulurlar. Programcılar başlangıçta sözde kod kullanarak programların “modellerini” oluşturmayı tercih eder. Bu sayede başlangıç aşamasında programlama dillerinin kodlama yükünden kurtulmuş olurlar.
Burada sözde kelimesi sahte anlamına gelir. Bu nedenle sözde kod, sahte koddur. Söz dizimi kuralları olmayan ve derlenmesi veya yürütülmesi amaçlanmayan gayriresmî bir dildir. Programcılar sözde kod yazarken söz dizimi hataları hakkında endişelenmek zorunda olmadıkları için tüm dikkatlerini programın tasarımına odaklayabilirler. Sözde
kod ile tatmin edici bir tasarım oluşturulduktan sonra, sözde kod doğrudan gerçek koda çevrilebilir.
Sözde kodun gerçek bir programlama dili olmadığını unutmamak gereklidir. Esasen sözde kod söz dizimi kuralları hakkında endişelenmeden bir algoritmanın ifadelerini yazmanın genel bir yoludur. C#, Java, C++ veya Python gibi gerçek bir programlama dili için bir derleyici veya yorumlayıcıya yanlışlıkla sözde kod yazılırsa çalışmayacak ve hatalar verecektir. Yazılan sözde kodun ilerleyen aşamada istenilen bir programlama diline çevrilmesi gerekmektedir.
Akış Şeması
Akış şeması, programcıların program tasarlamak için kul- landığı başka bir araçtır. Akış şeması, bir programda yer alan adımları grafiksel olarak gösteren bir diyagramdır.
Akış şemaları çizmenin birkaç farklı yolu vardır. Belki de en basit ve en ucuz yol, akış şemasını kalem ve kağıtla elle basitçe çizmektir. Akış şemalarını elle çizmenin dezavantajı, hataların elle silinmesi ve çoğu durumda tüm sayfanın yeniden çizilmesini gerektirmesidir. Akış şemaları oluşturmanın daha verimli ve profesyonel bir yolu yazılım kullanmaktır. Akış şemaları oluşturmanıza izin veren birkaç özel yazılım paketi mevcuttur. Temel akış şeması sembolleri ve açıklamaları, kitabın 54. sayfasındaki tablo 3.1’de yer almaktadır.
Örnek Algoritma Tasarımı
Maç başına sayı ortalaması (mbso) basketbol oyuncularının hücum yeteneklerinin göstergesi olarak kullanılan bir değerdir. Bir oyuncunun mbso’nı hesaplamak için aşağıdaki formül kullanılır:
mbso = Toplam Kaydettiği Sayı / Oynadığı Maç Sayısı
Burada toplam kaydettiği sayı (tks), bir oyuncunun sezon boyunca ürettiği toplam sayıyı ifade etmektedir. Oynadığı maç sayısı (oms) ise oyuncunun sezon boyunca oyuna ilk beşte başladığı veya sonradan oyuna dahil olduğu oyunların toplam sayısını ifade etmektedir. Örneğin bir oyuncu sezon boyunca 50 maçta oynarsa ve toplam 300 sayı atmış ise, maç başına sayı ortalaması (300/50) 6 olacaktır.
Bir programın eylemleri tipik olarak aşağıdaki üç aşamaya ayrılabilir:
• Girdinin alınması • Girdi üzerinde bazı işlemler (hesaplama gibi) yapılması • Çıktının üretilmesi
İlk adımınız, her aşamada neyin gerekli olduğunu belirlemektir. Genellikle bu gereksinimler doğrudan sorun açıklamasında belirtilmez. Örneğin, mbso problem tanımı, mbso’nun ne olduğunu açıklar ve sadece herhangi bir oyuncunun mbso’sunu hesaplamak için bir program tasarlamanızı söyler.
Girdinin Alınması
Bir programın girdi gereksinimlerini gidermek ve programın görevini tamamlaması için gerekli olan veri parçalarını belirlemelisiniz. Mbso formülüne bakarsak, hesaplamayı gerçekleştirmek için iki değere ihtiyaç olduğunu görürüz. Bu değerler bilinmediğinden, programın kullanıcıdan bunları girmesini istemesi gerekecektir. Her girdi parçası bir değişkende saklanacaktır. Programı tasarlarken bu değişkenleri bildirmeniz gerekecek, bu nedenle bu aşamada her bir değişkenin adını ve hatta algoritma açısından gerekli olmasa da veri türünü düşünmek faydalı olacaktır. Mbso programında, toplam kaydettiği sayı değişken için tks adını ve oynadığı maç sayısını tutan değişken için oms adını kullanacağız. Ayrıca, bu değerlerin her ikisinin de tam sayı olacağı öngörülmektedir. Dolayısıyla sözde kodun, yüksek seviyeli bir dile döndürülmesinde eksiklik olmaması adına değişken tanımlamalarını da bu aşamada yapmak uygun olacaktır.
Girdilerin İşlenmesi
Program gerekli girdiyi topladıktan sonra, bu girdiyi gerekli hesaplamalarda veya diğer işlemlerde kullanmaya devam edebilir. Programın tks değerini oms değerine bölmesi gerekmektedir. Hesaplamanın sonucu, oyuncunun mbso değeridir.
Matematiksel bir hesaplama yapıldığında, genellikle bu hesaplamanın sonucu bir değişkende saklanır. Bu nedenle, bu aşamada ihtiyaç duyulan tüm değişkenlerin adlarını ve veri türlerini düşünmelisiniz. Bu örnekte, maç başına sayı ortalaması için hâlihazırda kısaltma olarak kullandığımız mbso adını aynı zamanda değişken adı olarak kullanacağız. Dahası, bu değişken bir bölmenin sonucunu depolayacağından ondalıklı sayıların (ör: 7,34) saklayabilecek biçimde tanımlanması uygun olacaktır.
Çıktının Üretilmesi
Bir programın çıktısı, tipik olarak gerçekleştirdiği işlem veya işlemlerin sonucu olacaktır. Mbso programının çıktısı, mbso adlı bir değişkende saklanan bir hesaplama sonucu olacaktır. Program bu değerin ne olduğunu açıklayan bir mesaj da gösterecektir. Kitabın 55. sayfasında, ilgili örneğe ait sözde kodu ve şekil 3.4’te akış şemasını görebilirsiniz.
Algoritma ve Akış Şeması Örnekleri
Kitabın 56-58 sayfaları arasında algoritma ve akış şemasına dair örnekleri inceleyebilirsiniz.