Algoritma Ders\'leri. (1)

PROGRAMLAMA DİLİNDE ALGORİTMA

Algoritma Nedir?

Bir sorunu çözebilmek için gerekli olan sıralı mantıksal adımların tümüne denir. Doğal dille yazılabileceği için fazlaca formal değildir. Bir algoritma için aşağıdaki ifadelerin mutlaka doğrulanması gereklidir.

Her adım son derece belirleyici olmalıdır. Hiç bir şey şansa bağlı değildir.

Belirli bir sayıda adım sonunda algoritma sonlanmalıdır.

Algoritmalar karşılaşılabilecek tüm ihtimalleri ele alabilecek kadar genel olmalıdır.

Akış Çizgesi Nedir?

Bir algoritmanın daha görsel gösterimidir. Çizgiler, Dörtgen, daire vb. geometrik şekillerle algoritmanın gösterilmesini sağlar. Doğal dille yazılmadığı için daha formal olduğu düşünülebilir.

Algoritmalar

I.S. 9.yy da Iranli Musaoglu Horzumlu Mehmet

(Alharezmi adini araplar takmıştır.) problemlerin çözümü için genel kurallar oluşturdu. Algoritma Alharezmi’nin Latince okunuşu.

I.S. 9.yy da Iranli Musaoglu Horzumlu Mehmet

(Alharezmi adini araplar takmistir) problemlerin çözümü için genel kurallar oluşturdu. Algoritma Alharezmi’nin Latince okunuşu.

Her algoritma aşağıdaki kriterleri sağlamalıdır.

1. Girdi: Sıfır veya daha fazla değer dışarıdan verilmeli.

2. Çıktı: En azından bir değer üretilmeli.

3. Açıklık: Her işlem (komut) açık olmalı ve farklı anlamlar içermemeli.

4. Sonluluk: Her türlü olasılık için algoritma sonlu adımda bitmeli.

5. Etkinlik: Her komut kişinin kalem ve kağıt ile yürütebileceği kadar basit olmalıdır.

Not: Bir program için 4. özellik geçerli değil. işletim sistemleri gibi program sonsuza dek çalışırlar

Bir bilgisayar programı aslında sıra düzensel olarak tanımlanmış bir dizi komuttan başka bir şey değildir. Bu açıdan bizim yazmaya çalışacağımız programda bir dizi komut yani eylem topluluğudur. Her programda bu eylemler yazıldıkları sırada gerçekleştirilir veya çalıştırılırlar. Aslında bizim günlük hayattaki yaşantı tarzımız dahi düzenli olarak bir takım işlemlerin sıra ile yapılması şeklindedir. Yani bir iş yapabilmek için bir takım alt iş veya olayları peş peşe gerçekleştiririz.

Algoritmanın tanımını daha önce vermiştik burada bu tanımı tekrar etmek faydalı olacaktır. Bir sorunu çözebilmek için gerekli olan sıralı mantıksal adımların tümüne algoritma denir. Bir algoritmadan beklenen bir takım özellikler olduğunu da yine daha önceki tanımlar bölümünde bahsetmiştik. Biz şimdi mümkün olduğu kadar bu tanım ve özelliklerden yola çıkarak örneklerle bir kaç algoritma vermeye çalışacağız.

Öncelikle bir ev hanımının pasta yapmak istediğini varsayalım. Bu pastanın yapılabilmesi için gerekli bir takım işlemler ve alt adımlar bellidir. bir ev hanımıda sıra ile bu adımları uygulayarak bu pastayı yapar. Şöyle ki:

Pastanın yapımı için gerekli malzemeleri hazırla

Yağı bir kaba koy

Şekeri aynı kaba yağın üzerine koy

Yağ ve şekeri çırp

Karışımın üzerine yumurtayı kır

Tekrar çırp

Kıvama geldimi diye kontrol et

a. Kıvamlı ise 9. adıma devam et

b. Değilse 6. adıma dön.

Karışıma un koy

Karışıma vanilya, kabartma tozu vb. koy

Karışımı Kıvama gelinceye kadar çırp

Pastayı Kek kalıbına koy

Yeteri kadar ısınan fırına pastayı koy

Pişimi diye kontrol et

a. Pişmiş ise 16. adıma devam et

b. Değilse 14. adıma dön

Keki fırından çıkart

Fırını kapat

Kekin soğumasını bekle

Keki servis edebilirsin.

Bu algoritma günlük hayattan bir örnek. Gerçekte biz her işimizi algoritmik olarak yaparız ancak bunu farkına varmayız. Yukarıdaki algoritmayı inceleyecek olursak bir kekin yapılması için gerekli tüm adımlar sıra ile yer almış durumda. Gerçi algoritma anlatacağımız konuların daha iyi anlaşılabilmesi için biraz farklı ele alınmıştır ama gerçek bir Pasta yapım aşamasını içerir. Bu algoritma ve diğer tüm algoritmalar için bilmemiz gereken bazı konular bulunmaktadır:

Her adım son derece belirleyici olmalıdır. Hiç bir şey şansa bağlı olmamalıdır.

Belirli bir sayıda adım sonunda algoritma sonlanmalıdır.

Algoritmalar karşılaşılabilecek tüm ihtimalleri ele alabilecek kadar genel olmalıdır.

Algoritmada algoritmanın genel işleyişini etkileyebilecek hiç bir belirsizlik olmamalıdır. (Bu örnekte öyle bir belirsizlik var. Bir fırının yeteri kadar ısına bilmesi hangi koşula bağlıdır, bu fırın ne zaman açılmış olmalıdır ve kaç dereceye ayarlanmış olmalıdır. gibi…)

Algoritmada bazı adımlar yer değiştirebilir . Ancak bir çok adımın kesinlikle yer değiştiremeyeceğini bilmeliyiz. Yanlış sıradaki adımlar algoritmanın yanlış çalılaşmasına neden olacaktır. (9 ve 10. adım değiştirilebilir. 2-3. adımlar yer değiştirebilir.) Ancak 13-16. adımlar kesinlikle yer değiştiremezler.

Peki Bilgisayarda çözülecek bir sorunu nasıl algoritma ile ifade ederiz? Bunun için öncelikle bir sorun tanımlayalım. Başlangıç ta basit olması için şöyle bir problem üzerinde düşünelim: Bilgisayara verilecek iki sayıyı toplayıp sonucu ekrana yazacak bir program için algoritma geliştirmek isteyelim. Sorun son derece basit ancak sistem tasarımının net yapılabilmesi için sorun hakkında anlaşılamayan tüm belirsiz noktalar açıklığa kavuşturulmalıdır. Örneğin sayışlar bilgisayara nereden verilecek, Klavye, Dosya veya belki başka bir ortam. Bu ve buna benzer soru ve tereddütleriniz varsa sorun sahibine bunları sormalı ve sistem analizi yapmalısınız.

Sonra bulacağımız çözümü algoritma haline dönüştürebiliriz.

BAŞLA

A sayısını oku

B sayısını oku

TOPLAM=A + B işlemini yap

TOPLAM değerini ekrana yaz

SON

Biraz daha bir sorun şöyle olsun: Klavyeden girilecek iki sayıdan büyük olanından küçük olanını çıkarıp sonucu ekrana yazacak program için bir algoritma geliştiriniz.

BAŞLA

A sayısını oku

B sayısını oku

Eğer A büyüktür B SONUC=A-B

Değilse SONUC=B-A

SONUC değerini ekrana yaz

SON

Bu algoritmalar oldukça basit algoritmalar olup algoritma kavramının yerleşmesini sağlayan örneklerdir .Bütün bunların dışında algoritmaların yazılım geliştirme konusunda da önemli görevi vardır .Aşağıdaki sıralamada bu önem sanırım daha iyi ortaya çıkacaktır.

Yazılım Geliştirme

Yazılım Geliştirilirken Bir Programcı ve Yazılım Gurubunun takip edeceği adımlar şu şekildedir.

Bu çizgeden anlaşılacağı gibi adımlardan birinde bir sorunla karşılaşılırsa bu sorunu çözebilmek için bir önceki adıma geri dönmek gerekecektir. Bu geri dönüş bazen bir kaç adım olabilir.

Sistem Analizi : Sorunun çözülebilmesi için tamamen anlaşılmasını sağlayan çalışmalardır.

Tasarım : İsteklerle ilgili olarak belirlenen bir takım çözümlerin tanımlanmasıdır.

Programlama Stili :

Algoritma : Çözümün adımlarla ifade edilmesidir.

Akış Çizgesi : Algoritmanın şekillerle ifade edilmesidir.

Programlama Dili Seçimi : Çözümün netleşmesinden sonra yapılacak işlemleri kolay bir şekilde bilgisayar ortamına aktaracak dilin seçilmesidir. Önemli olan bu dilin özelliklerinin programcı tarafından iyi bilinmesidir.

Programın Yazılması : Seçilen Programlama dilinin kuralları kullanılarak program yazılmaya başlanır. bu amaçla çoğunlukla sade bir metin editörü kullanılır. Bazı durumlarda Syntax highlighting denilen bir özelliğe sahip olan daha akıllı editörler de kullanılabilir. Bazen de editör ile Programlama dilinin derleyicisinin, bağlayıcısının hatta hata ayıklayıcısının iç içe bulunduğu IDE (Integrated Development Environment) denilen türde derleyiciler kullanılır.

Derleme : Programlama Dili ile yazılmış programın yazım hatalarının olup olmadığının kontrol edilmesini ve ara kod olarak Obje kodun üretilmesini sağlama adımıdır.

Bağlama : Derlenmiş ara kod diğer kütüphane ve parça programlarla birleştirilerek Makine dilinde programın oluşturulması adımıdır. Ancak bazı IDE ortamlarda ve derleyicilerde Derleme ve Bağlama bir bütündür ve beraberce halledilirler. Programcının ayrıca bir bağlama işlemi yapması gerekmez.

Çalıştırma : Oluşturulan Makine dili Programının çalıştırılması adımıdır. Yukarıdaki adımların hepsi yolunda gittiyse program sorunsuz olarak çalışabilmelidir.

Test : Programın Mantıksal olarak test edilmesini sağlar ve içerik olarak her ihtimal için doğru sonuçlar üretip üretmediğini kontrol etmenizi sağlar.

Yaşam Döngüsünün Sağlanması : Yukarıdaki Akış Çizgesi dikkat edilirse aslında bir döngüdür. Hatta test aşamasında sorun çıkmazsa bile Sorunun tanımında yani ihtiyaçlarda bazı değişiklikler olursa adımlar baştan aşağı tekrar incelenmek zorunda kalınır. Bu çizgiye bir Yazılımın Yaşam Döngüsü de denilebilir. Bu çizimde Yazılımın Bakım süreci göz önüne alınmamıştır.

Örnek 1.2.1 : 1'den 100'e kadar olan sayıların toplamını veren algoritma.

1. Toplam T, sayılar da i diye çağırılsın.

2. Başlangıçta T’nin değeri 0 ve i’nin değeri 1 olsun.

3. i’nin değerini T’ye ekle.

4. i’nin değerini 1 arttır.

5. Eğer i’nin değeri 100'den büyük değil ise 3. adıma git.

6. T’nin değerini yaz.

Algoritmaların yazım dili değişik olabilir. Günlük konuşma diline yakın bir dil olabileceği gibi simgelere dayalı da olabilir. Akis seması eskiden beri kullanıla gelen bir yapıdır. Algoritmayı yazarken farklı anlamlar taşıyan değişik şekildeki kutulardan yararlanılır. Yine ayni amaç için kullanılan programlama diline yakın bir (sözde kod = pseudo code) dil , bu kendimize özgü de olabilir, kullanılabilir.

Ayni Algoritmayı aşağıdaki gibi yazabiliriz.

1. T=0 ve i=0

2. i’nin değerini T’ye ekle.

3. i’yi 1 arttır.

4. i<101 ise 2.adima git.

5. T&#8217;nin değerini yaz.

Algoritmayı bir de akis seması ile gerçekleyelim.

T=0

I=0

I?nin Devrini T?ye ekle

I?yi bir arttır

I<101

T?yi yaz

Örnek 1.2.2 : ax2+bx+c=0 tipi bir denklemin köklerini veren algoritma.

Girdi : a, b ve c katsayıları Çıktı : denklemin kökleri

1. a, b ve c katsayılarını al.

2. D = b2-4ac değerini hesapla.

3. D<0 ise gerçel kök yok. 7. adıma git.

4.

5 .

6. değerlerini yaz.

7. Dur.

Döngü Gösterimi

Tekrarlanan adımlar

Koşul sağlandığı sürece

n.1 &#8230;

n.2 &#8230; tekrarlanan adımlar

n.3 &#8230;

Örnek 1.2.3 : İki tamsayının çarpma işlemini sadece toplama işlemi kullanarak gerçekleyin.

Girdi : iki tamsayı

Çıktı : sayıların çarpımı

a ve b sayılarını oku

c =0

b>0 olduğu sürece tekrarla

.3.1. c=c + a

3.2. b = b-1

4. c değerini yaz ve dur

Örnek 1.2.4 : Bir tamsayının faktoriyelini hesaplayınız.

Girdi : Bir tamsayı

Çıktı : sayının faktoriyel

İlgili formül: Faktoriyel(n)=1*2*&#8230;*n

n değerini oku

F=1

n >1 olduğu sürece tekrarla

.3.1. F=F*n

3.2. n= n-1

F değerini yaz

Örnek 1.2.5 : İki tamsayının bölme işlemini sadece çıkarma işlemi kullanarak gerçekleyin. Bölüm ve kalanın ne olduğu bulunacak.

1. a ve b değerlerini oku

2. m=0

3. a>=b olduğu sürece tekrarla

a=a-b

m = m + 1

4. kalan a ve bölüm m &#8216;yi yaz

Örnek 1.2.6 : 100 tane sayıyı okuyup, ortalamasını bul

T=0,i=0

i<101 olduğu sürece tekrarla

m değerini oku

T = T + m

i = i + 1

T = T / 100

Ortalama T ?yi yaz

Dur

Örnek 1.2.7 : Bir sınava giren öğrencilerin not ortalamasının hesaplanması

Tüm sınav kağıtlarını inceleyip notların toplamını hesapla

Ortalamayı notların toplamını incelenen sınav kağıdına bölerek hesapla

Ortalamayı yaz.

notların toplamını ve incelenen sınav kağıdı şayisini Sıfır kabul et

Sıradaki sınav kağıdının notunu notların toplamına ekle

İncelenen sınav kağıdı şayisini Bir arttır

İncelenecek sınav kağıdı var ise 2. adıma git

Ortalamayı notların toplamını incelenen sınav kağıdına bölerek hesapla

Ortalamayı yaz

notların toplamını ve incelenen sınav kağıdı şayisini Sıfır kabul et

Her bir sınav kağıdı için

Sıradaki sınav kağıdının notunu notların toplamına ekle

İncelenen sınav kağıdı şayisini bir arttır

Ortalamayı notların toplamını incelenen sınav kağıdına bölerek hesapla

Ortalamayı yaz

Koşul Gösterimi

Koşul doğru ise

n.D.1

n.D.2 doğru olduğunda islenen adımlar

n.D.3

aksi halde

n.Y.1

n.Y.2 yanlış olduğunda islenen adımlar

n.Y.3

Kök bulma örneğinde 3. Adimi tekrar yazarsak

D>=0 ise

3.D.1

3.D.2

aksi halde

3.Y.1 Reçel kök yoktur

Sorular:

* Girilen üç sayıdan en büyüğünü bulan Algoritmayı yazınız.

* Tamsayılarda üs alma işlemini gerçekleştiren Algoritmayı yazınız ( ab ).

* 1-100 arasında tutulan bir sayıyı tahmin eden Algoritmayı yazınız.

Örnek 1.2.8 : Aracın otopark ücretinin hesaplanması. Araçların en fazla 24 saat kaldığını varsayın.

0 - 2 saat 150 bin

2 - 8 saat 300 bin

8-24 saat 500 bin

Aracın kaç saat kaldığını öğren ( t olsun ).

t <= 2 ise

2.D.1. ücret = 150 bin

Aksi halde

2.Y.1. t<=8 ise

2.Y.1.D.1. ücret = 300 bin

Aksi halde

2.Y.1.Y.1. ücret = 500 bin

ücreti yaz

Dur

Örnek 1.2.9: Sınavdaki en büyük notun bulan algoritma.

En büyük = ilk sınav kağıdındaki not (ya da olabilecek en düşük değer kabul edilebilir).

İncelenecek sınav kağıdı var ise

sınav kağıdındaki not > En büyük ise En büyük = sınav kağıdındaki not

En büyük değerini yaz.

Dur

Algoritmanın yazımı daha simgesel olabilir. Niş İ. Öğrencinin notu olsun.

EB = N1

i = 2

İncelenecek sınav kağıdı var ise

Niş>EB => EB = Niş

i = i + 1

EB? yi yaz.

Dur

Örnek 1.2.10 : Programın C dili ile yazılıp çalışır hale getirilmesi.

Programı bilgisayara gir

Kaynak dosya olarak kaydet

Kaynak dosyayı derle ( com pile)

Derleme sonucunda hata var ise

Hataları düzelt

3. adıma git

Oluşan amaç dosyasına diğer dosyaları bağla (link)

Bağlama sonucunda hata var ise

Hataları düzelt

Hatalar kaynak dosya ile ilgili ise 2. adıma aksi halde 5. adıma git

Program çalıştırılmaya hazi2- Programlamaya Giriş

Program : Belirli bir problemi çözmek için bir bilgisayar dili kullanılarak yazılmış deyimler dizisi.

Önceki bölümde bir problemin çözümü ile ilgili teknikler sunmuştuk. Bir problemi bilgisayar ile çözmek için geliştireceğimiz Programın yazımında izleyeceğimiz adımlar:

i) Problemin ne olduğunu kavra. Çözüm için gereksinimleri belirle.

i) Problemin girdilerini, çıktılarını ve diğer kısıtlama ve gereksinimleri belirle ( bilgilerin Giriş ve çıkış biçimlerinin nasıl olacağına kadar).

içi) Problemin çözümünü veren Algoritmayı yaz.

iv) Algoritmayı bir programla dili ile yaz.

v) Programın doğru çalışıp çalışmadığını test et. Bu testi değişik veriler (girdiler) için tekrarla.

2.1 İlk Program Örneği

#include kullanılan islevler ile ilgili baslık dosyası

mail()

ine i ; Değişken tanımı

scanf(&#8221;%d&#8221;,&i); Programın gövdesi

i:=i*i;

printf(&#8221;%d&#8221;,i);

BCPL à B (1967 Ken Thompson) à C (Denis Ritchie unix i yazmak için)

az sayıda saklı sözcük

kısa ve etkin program

çok sayıda işleç

assembler e yakın kod

taşınabilir kod

kullanıcıya bırakılan kontroller (dizinin boyutu gibi )

düşük okunabilirlik

source &#8212;&#8211;> compiler &#8212;&#8211;> object &#8212;&#8211;> link

kaynak derleyeli amaç Bağlama

kaynak kod : C dili ile yazılmış olan program.

derleyeli : Kaynak kodu makine koduna çevirir

amaç kodu : Kaynak kodun makine dilindeki karşılığı

Bağlama : Birden fazla amaç kodu dosyasının tek dosyada birleştirilmesi

Akış Çizgeleri

Bir algoritmanın şekillerle görsel gösterimidir. Dikkat edildiyse algoritma doğal dille yazıldığı için herkes tarafından anlaşılamayabilir ya da istenmesele başka anlamlar çıkarılabilir. Ancak akış çizgelerinde her bir şekil standart bir anlam taşıdığı için farklı yorumlanıp anlaşılamaması mümkün değildir. Bir algoritmanın ifade edilebilmesi için kullanılan şekiller ve anlamları şunlardır:

Bir algoritmanın başladığı konumu göstermektedir. Tek çıkışlı bir şekildir.

Bir algoritmanın bittiği konumu göstermektedir. Tek girişli bir şekildir.

Bir algoritmada aritmetik işlem yapılmasını sağlayan şekildir. Bu dörtgen kutu içerisine yapılmak istenen işlem yazılır. Tek girişli ve tek çıkışlı bir şekildir.

Algoritmada bir bilginin ekrana yazılacağı konumu gösteren şekildir. Ekrana yazılacak ifade ya da değişken bu şekil içerisine yazılır.

Bir algoritmada başka bir yerde tanımlanmış bloğun yerleştiği konumu gösteren şekildir. Kutu içerisine bloğun adı yazılabilir.

Klavyeden Bilgisayara bilgi girilecek konumu belirten şekildir. Girilecek bilginin hangi değişkene okunacağını kutu içerisine yazabilirsiniz.

Giriş Çıkış komutunun kullanılacağı yeri belirler ve kutu içerisine hangi değişkeni ve OKU mamı YAZ mı yapılacağını belirtmeniz gerekir

Bilginin Yazıcıya yazılacağı konumu gösteren şekildir.

Bir algoritmanın birden fazla alana yayılması durumunda bağlantı noktalarını gösteren şekildir. Tek girişli veya tek çıkışlı olarak kullanılırlar.

Bir işlemin belli bir sayıda veya belli bir koşul doğru olduğu sürece tekrar edilmesini sağlayan döngü komutunu gösteren şekildir. Bu döngüde altıgen içerisine ya koşul yada döngünün başlangıç, adım ve sonlanma değerlerini belirtebilirsiniz. DÖNGÜ olarak belirlenen blokta da tekrar edilmek istenen komutlar yer almaktadır.

Bir algoritmada bir kararın verilmesini ve bu karara göre iki seçenekten birinin uygulanmasını sağlayan şekildir. burada eşkenar dörtgen içerisine kontrol edilecek mantıksal koşul yazılır. Program akışı sırasında koşulun doğru olması durumunda &#8220;Evet&#8221; yazılan kısma Yanlış olması durumunda &#8220;Hayır&#8221; yazılan kısma sapılır. Tek girişli ve çift çıkışlı bir şekildir.

Programın bittiği yer ya da yerleri gösteren bir şekildir.

Bu şekiller kullanılarak algoritma ile oluşturulan çözümler akış çizgelerine çevrilir. Bu şekiller herkes tarafından anlaşılabilir ve doğru olarak yorumlanabilir bir özellik arz ederler.

Algoritma Kurma

Algoritma, verilen herhangi bir sorunun çözümüne ulaşmak için uygulanması gerekli adımların hiç bir yoruma yer vermeksizin açık, düzenli ve sıralı bir şekilde söz ve yazı ile ifadesidir. Algoritmayı oluşturan adımlar özellikle basit ve açık olarak sıralandırılmalıdır. Algoritmik çözüm yöntemlerine ilk örneği günlük yaşantımızdan verelim.

Örnek 1: Örneğimiz bir insanın evden çıkıp işe giderken izleyeceği yolu ve işyerine girişinde ilk yapacaklarını tanımlamaktadır.

Çözüm 1:

Evden dışarıya çık

Otobüs durağına yürü

Durakta gideceğin yöndeki otobüsü bekle

Otobüsün geldiğinde otobüse bin

Biletini bilet kumbarasına at

İneceğin yere yakınlaştığında arkaya yürü

İneceğini belirten ikaz lambasına bas

Otobüs durunca in

İşyerine doğru yürü

İş yeri giriş kapısından içeriye gir

Mesai arkadaşlarınla selamlaş

İş giysini giy

İşini yapmaya başla.

Yukarıdaki örnekte görüldüğü gibi, evden işe gidişte yapılabilecek işlemler adım adım sırasıyla, kısa ve açık olarak tanımlanmaya çalışılmıştır. Yukarıdaki algoritma kişinin otobüsü kaçırma olasılığı düşünülmeden oluşturulmuştur. Kişi durağa geldiğinde bineceği otobüsü kaçırmış ise algoritmamız aşağıdaki şekilde değiştirilebilir.

Çözüm 2:

Evden dışarıya çık

Otobüs durağına yürü

Otobüsün saati geçmiş ?

Durakta gideceğin yöndeki bir sonraki otobüsü bekle

Bir sonraki otobüs gelene kadar 4. adımı uygula

Otobüsün geldiğinde otobüse bin

Biletini bilet kumbarasına at

İneceğin yere yakınlaştığında arkaya yürü

İneceğini belirten ikaz lambasına bas

Otobüs durunca in

İşyerine doğru yürü

İş yeri giriş kapısından içeriye gir

Mesai arkadaşlarınla selamlaş

İş giysini giy

İşini yapmaya başla.

Her iki örnekte görüldüğü gibi sorunu çözüme götürebilmek için gerekli olan adımlar sıralı ve açık bir biçimde belirlenmiştir. Algoritmanın herhangi bir adımındaki küçük bir yanlışlık doğru çözüme ulaşmayı engelleyebilir. Bu nedenle algoritma hazırlandıktan sonra dikkatle incelenmeli ve varsa adımlardaki yanlışlıklar düzeltilmelidir.

Programlamanın temeli olan algoritma hazırlanmasında dikkat çekici bir nokta, aynı sorunu çözmek için hazırlanabilecek olası algoritma sayısının birden çok olmasıdır. Başka deyişle, bir sorunun çözümü için bir birinden farklı birden fazla sayıda algoritma hazırlanabilir. Bu da gösteriyor ki herhangi bir problemin çözümü için bir birinden farklı yüzlerce bilgisayar programı yazılabilir.

Bir bilgisayar programı için hazırlanacak olan algoritma da aynı şekilde çözüm yolunu bilmeyen bir kişiye, çözüme ulaşmak için neler yapması gerektiği anlatılıyormuş gibi hazırlanmalı ve eksik bir nokta bırakmaksızın gerekli tüm adımları açık ve düzenli olarak içermelidir. Çözüm için kullanılacak bilgilerin nereden alınacağı, nerede saklanacağı ve çözümün program kullanıcısına nasıl ulaştırılacağı algoritma adımları arasında belirtilmelidir.

Aşağıda değişik işlemlere ilişkin algoritma örnekleri verilmiştir.

Örnek 2: İki sayıyı toplamak için gerekli programa ait algoritmanın oluşturulması.

Algoritma:

A1 :Birinci sayıyı gir

A2 :İkinci sayıyı gir

A3 :İki sayının toplamını yap

A4 :Toplamın değerini yaz

A5 :Bitir.

Bu tam bir algoritmadır. Sözcüklerin ortaya çıkaracağı yanlış anlamaların ortadan kaldırmak amacıyla semboller ve matematik dilini gerektiren bazı kısaltmalar kullanmak daha uygun olacaktır. Bir algoritma yazılırken şu metot izlenmelidir:

Programda kullanılacak elemanları temsil etmek üzere uygun isimler veya değişkenler seç.

Bazı isimlere başlangıç değeri olarak çözümün gerektirdiği uygun değerler ver.

Gerekirse programa girilecek verileri düzenle.

Cebirsel notasyon ve kararlar kullanarak aritmetik işlemleri gerçekleştir.

Çıkışı düzenle.

Bitir.

Yukarıda iki sayının toplanması için oluşturduğumuz algoritmayı bu yeni gereksinimlere uyarak yeniden yazalım.

Toplam adı için Z

Birinci Sayı için X

İkinci Sayı için Y değerleri kullanılırsa;

Algoritma:

A1 :X değerini gir

A2 :Y değerini gir

A3 :Z ¬ X+Y

A4 :Z? yi yaz

A5 :Bitir

Görüldüğü üzere bu şekilde bir algoritma ile çözüm yolunu izlemek daha kolaydır. Bundan sonra bu tip algoritma kullanılacaktır.

A6 :Bitir

Bu örnekte Ort değeri ile iki sayının ortalaması temsil edilmiştir.

Örnek 4: Beş sayının toplamını ve ortalamasını veren programa ait algoritmanın oluşturulması

Toplam adı için Top

Ortalama adı için Ort

Girilen sayılar için X

Arttırma için Sayaç kullanılırsa

Algoritma:

A1 :Top ¬ 0, Sayaç ¬ 0

A2 :X?i gir

A3 :Top¬ Top+X

A4 : Sayaç ¬ Sayaç +1

A5 :Eğer Sayaç <5 ise A2?ye git

A6 : Ort¬ Top/5

A7 :Top ve Ort değerlerini yaz

A8 :Bitir

Örnek 5: Kenar uzunlukları verilen dikdörtgenin alan hesabını yapan programa ait algoritmanın hazırlanması. Kenar uzunlukları negatif olarak girildiği durumda veri girişi tekrarlanacaktır.

Dikdörtgenin kısa kenarı : a

Dikdörtgenin uzun kenarı : b

Dikdörtgenin alanı : Alan

Algoritma:

A1 :a değerini gir

A2 :a<0 ise 1. adımı tekrarla

A3 :b değerini gir

A4 : b<0 ise 3. adımı tekrarla

A5 :Alan ¬ a*b

A6 :Alan değerini yaz

A7 :Bitir

Örnek 7: Verilen bir sayının faktoriyelini hesaplayan programın algoritmasının oluşturulması

Sayının faktoriyeli :Fak

Faktoriyel değişkeni :X

faktoriyeli hesaplanacak sayı :Y

Algoritma:

A1 :Fak¬ 1, X¬ 0

A2 :Y?i gir

A3 :Y<0 ise 2. adımı tekrarla

A4 :X¬ X+1

A5 :Fak¬ Fak*X

A6 :X

A7 :Fak değerini yaz

A8 :Bitir

Bu algoritmada 1. adımda X e 0 ve Fak değişkenine 1 değeri atanıyor. 2. adımda Y değeri giriliyor ve 3. adımda Y değerinin 0 dan küçük bir değer olup olmadığı denetleniyor ve denetim sonucuna göre gerekli komut veriliyor. 4. adımda X?in değeri 1 arttırılıyor ve 5. adımda X için Fak değeri hesaplanıyor. 6. adımda X in değerinin faktoriyeli hesaplanacak sayıdan küçük olması durumunda 4. adımdan itibaren işlemlerin tekrarlanması komutu veriliyor, X? in değerinin Y?ye eşit olması durumunda işlemler tamamlanarak hesaplanan değerin yazdırılması işleminden sonra programın çalışması sona ermektedir.

Doğru Algoritmaları

Ekran gibi piksellerden oluşan bir görüntü aracı gerçek dünyadaki görüntüleri hiçbir zaman tam olarak veremez. Dijitize işlemi analog olan gerçek dünyanın sadece yaklaşımlarını üretir. Eğer piksel büyüklüğü gözün seçebileceğinden daha küçükse bu durum büyük bir problem oluşturmaz ancak yine de mümkün olduğunca doğru yaklaşımı yapmak gerekir. Şekil 1'de piksel bazlı bir sistemdeki yatay doğru ile eğik doğru örnekleri gösterilmektedir.

Şekil 1

Doğrular gitmeleri gerekli yolu takip ederler ancak karakterleri farklıdır. Yatay doğrunun kalınlığı her yerinde 1 piksele karşılık gelmektedir, ancak eğik doğrunun kalınlığı sürekli 0 ile 1.414 piksel arasında değişmektedir. Ortalama kalınlığı 0.707 piksele karşılık gelmektedir. Uzaktan bakan bir göz her ikisini de doğru olarak algılayacak ancak eğik olanın olması gerekenden daha dar olduğunu fark edecektir.

Bir doğruda olması gereken özellikler şöyledir:

uzunluğu boyunca sabit kalınlığa sahip olmak

eğikliğinden bağımsız standart bir kalınlığa sahip olmak

doğru koordinatlarda başlamak ve bitmek

İdeal doğrunun izleyeceği yola mümkün olduğunca yakın bir yol izlemek.

Donanım ve yazılım açısından değerlendirdiğimizde doğrunun çizilmesi implemente edilebilecek kadar basit ve kaynak israf etmeyecek kadar da verimli olmalıdır. Dolayısıyla şu özelliklere de sahip olmalıdır:

Doğruyu efektif olarak çizebilmek için hesaplanması gerekli piksel sayısı minimum olmalı

Sadece tamsayı aritmetiği ile koordinatlar hesaplanabilmeli

Sadece toplama, çıkarma ve kaydırma (İkiyle çarpma ve ikiye bölme) işlemleri kullanılmalı

Şekil 2'de ideal doğru ile onun piksel yüzeyde implemente edilmiş hali görülmektedir.

Bir doğru algoritması implemente edilirken yukarıdaki tüm hususlara uymaya dikkat edilmelidir. Ancak pek çok temel grafik algoritması farklı özellikler içermektedir çünkü bunlar sadece yazılım değil donanım olarak da desteklenmektedirler. Dolayısıyla implemente edilecek algoritma sadece yazılım değil aynı zamanda bir elektronik devre olarak da dizayn edilebilmelidir.

Şekil 2

Aşağıda verilen algoritmalar bizim şöyle bir fonksiyon ile doğru çizilmesini istediğimiz temeline dayanacaklardır:

PROCEDURE DrawLine(X1, Y1, X2, Y2: Integer);

Ayrıca bu doğruyu çizerken istediğimiz yere piksel koymamızı sağlayan bir fonksiyonun sistem tarafından sağlandığı varsayılacaktır.

BASİT DDA

Doğru algoritmaları arasındaki en basit algoritmadır. Doğrunun matematiksel tanımını temel alır. Doğruyu şekil 3'te görüldüğü gibi eşit aralıklı parçalara ayırır.

Şekil 3

Doğrunun yatay uzunluğu: HL = X2 - X1

Düşey uzunluğu: VL = Y2 - Y1

Doğrunun gerçek uzunluğu SQRT(SQR(HL)+SQR(VL)) ile hesaplanır ancak yaklaşık olarak şu şekilde bulunabilir:

L = ABS(HL) + ABS(VL)

Eğer doğruyu L sayıda eşit parçaya bölersek her parçanın yatay uzunluğu dX=HL/L, düşey uzunluğu dY=VL/L olacaktır. Eğer (X1, Y1) noktasından başlarsak doğru boyunca bize gerekli noktalar (dX, dY) olacaktır. Böylece bu koordinata en yakın pikseli boyayarak doğrumuzu çizebileceğiz. Bu algoritma ile ilgili Pascal kodu aşağıda verilmiştir.

PROCEDURE DrawLine(X1, Y1, X2, Y2: Integer);

VAR

HL, VL, L: Integer;

dX, dY, X, Y: Real;

Count: Integer;

BEGIN

HL := X2 - X1;

VL := Y2 - Y1;

L := Abs(HL) + Abs(VL);

dX := HL / L;

dY := VL / L;

X := X1;

Y := Y1;

FOR Count := 0 TO L DO

BEGIN

PutPixel(Round(X), Round(Y), White);

X := X + dX;

Y := Y + dY

END

END;

Bu algoritmanın bazı eksiklikleri vardır. Doğruyu çizmemiz için gerekenden daha fazla nokta hesaplar. Yani aynı piksel bir kaç kere boyanabilir, ya da pikseller bir bir yerde toplanarak eşit olmayan kalınlığa sebep olabiliriler. Ayrıca bu algoritma gerçel (real) aritmetik ve bölme işlemi içerdiği için oldukça yavaş kalacaktır. (Borland Pascal içindeki Line prosedürü ile hızı kıyaslandığı zaman bu yavaşlık anlaşılacaktır)

Bresenham Algoritması

Bresenham algoritması bir doğruyu uyması gereken tüm kriterlere uyacak şekilde implemente eder. Ancak bu haliyle verimli değildir. Burada anlatılan bu algoritmanın modifiye edilmiş şeklidir ve tamamen optimize edilmiştir.

Algoritma temelde 0 ile 45 derece arasında bir açıdaki doğrunun çizimini implemente eder. Ancak diğer kuadrantlardaki doğrular basit bir işlemle bu doğrudan türetilebileceği için muhtemel tüm doğruları kapsar. Algoritma yatay, düşey ve 45 derecelik doğrular için geçersizdir, zaten bu doğrular da hiçbir hesaplama gerektirmeden doğrudan çizilebilirler.

Bresenham algoritmasına göre her pikselden önce mutlaka çaprazında bir piksel bulunmalı. Ama bu piksel daha aşağıda da olabilir aynı hizada da olabilir. Pikselin aşağıya mı yoksa yana mı ilerleyeceğini belirlemek için hata kontrolü yapılır. Gerçek doğrunun eğimi (dy/dx) biz bir piksel ilerlerken gerçek doğrunun ekranın neresine kaldığını bulmamıza yardımcı olur. Gerçek doğrunun olması gereken yer ile elimizdeki pikselin farkını karşılaştırarak hatayı buluruz. Şekil 4'te diyagramatik olarak gösterilmiştir:

Şekil 4

Eğer y koordinatı değiştirmezsek, doğru boyunca ilerlerken hatamız her yatay pikselde dy/dx kadar artacaktır. Bir noktada hata 0.5'ten daha büyük olacaktır, o zaman bir aşağıdaki piksele geçilerek hatanın 1'den çıkarılmasıyla 0.5'ten daha küçük bir hata elde edilecektir. Bu algoritma için Pascal kodu aşağıda verilmiştir.

PROCEDURE DrawLine(X1, Y1, X2, Y2: Integer);

VAR

Error, DYbyDX: Real;

Count: Integer;

BEGIN

DYbyDX := (Y2 - Y1)/(X2 - X1);

Error := 0;

FOR Count := X1 TO X2 DO

BEGIN

PutPixel(Count, Y1, White);

Error := Error + DYbyDX;

IF Error > 0.5 THEN

BEGIN

Y1 := Y1 + 1;

Error := Error - 1

END

END

END;

Buradan da görüleceği gibi, hala gerçek (real) aritmetik ve bölme işlemi kullanılmaktadır ancak koordinatların hesaplanmasında sadece tamsayılar vardır. Bu algoritma her ne kadar geliştirilmiş olsa da efektif olması için üzerinde daha fazla çalışılmalıdır. Sonraki bölümlerde bunun nasıl yapılacağı anlatılmaktadır.

Geliştirilmiş Bresenham Algoritması

Bresenham algoritması sadece karşılaştırma maksadıyla kullanılan hata katsayısını hesaplamak için gerçel sayılar kullanmaktaydı. Şimdi biraz matematik diyelim ve nasıl geliştirebileceğimize bakalım. Basit bir matematik kuralıyla başlayalım:

Eğer a>b ve c>0 => a*c > b*c

Şimdi algoritmamız içinde karşılaştırma yaptığımız yere bakalım:

error > 0.5

Bu ifadede karşılaştırmadaki eşitsizliğin her iki tarafı da gerçel sayılar. Eğer iki tarafı da 2 ile çarparsak eşitsizlik hala geçerli olacak ancak sağ taraf tam sayı olacaktır.

2*error > 1

Hata katsayısını her iterasyonda dy/dx ile topluyoruz. Eğer eşitsizliğin her iki tarafını da dx ile çarparsak iki tarafı da tamsayı haline getirmiş oluruz:

2*dX*error > dX

Şimdi algoritmamızı hataya -dX değeri verip baştan ele alırsak daha basite indirgemiş oluruz, sadece 0 ile karşılaştırma yapmak kalır.

2*dX*error - dX > 0

Bu şekilde tüm değerleri önceden hesaplatırsak aşağıda verilen Pascal kodunu elde etmiş oluruz:

PROCEDURE DrawLine(X1, Y1, X2, Y2: Integer);

VAR

Error, DXtimes2, DYtimes2: Integer;

Count: Integer;

BEGIN

DYtimes2 := (Y2 - Y1) SHL 1;

DXtimes2 := (X2 - X1) SHL 1;

Error := X1 - X2;

FOR Count := X1 TO X2 DO

BEGIN

PutPixel(Count, Y1, White);

Error := Error + DYtimes2;

IF Error > 0 THEN

BEGIN

Y1 := Y1 + 1;

Error := Error - DXtimes2
END

END

END;

Örnek: Katsayıları dışarıdan girilen ikinci dereceden denklemin köklerini bulan program.

Örnek: Fibonacci serisini bulan programın akış çizelgesini çizelim .Bu seri 1 1 2 3 5 8 13 21&#8230;şeklinde ilerleyen bir seridir. Dışardan girilen bir sayıya göre o sayıya kadar olan seri elemanlarını bulalım.

Örnek: Dışarıdan girilen N sayısına göre 1 den N e kadar olan çift sayıların toplamını bulan programın algoritmasını oluşturalım.

Bu daha başlangıcı. :D:D

keşke alıntı olduğunuda yazsaydın

MortaL : keşke alıntı olduğunuda yazsaydın

Keşke. : ) Hee. Bu arada.

Ben bu konuları biliyorum, bilmiyenler öğrensin.

En azından basit mantığını bilmek çok önemli. Döküman çok güzel olmuş ellerine sağlık.

Kontrollü ve hataya yer vermeyen sistemler oluşturmak için algoritma oluşturabilmemiz şart arkadaşlar. Algoritmayı oluşturduğunuz zaman zaten kodlar kendiliğinden gelecektir emin olabilirsiniz.