What is an Algorithm

Kategori: Algorithm Design and Analysis , 29 Mayıs 2020 , JanFranco


Breadboard üzerinde inşa ettiğimiz bilgisayar projesine siparişlerimin yurt dışından hala gelmemesi üzerine ara verip eski yazılarımı paylaşmaya karar verdim.

Algoritma, mantıklı bir girdinin belirli bir zaman içinde istenen çıktıya dönüşmesini sağlamak gibi problemlerin çözümü için, kesin adımlar içeren dizidir. Girdilerin aralığı mutlaka belirtilmelidir. Ne istenildiği her zaman bilinmelidir. Aynı algoritma farklı şekillerde tarif edebilir ve aynı problem için birden fazla algoritma yazılabilir. Aynı problem için çok farklı algoritma olabilir ve bu algoritmalar problemi farklı hızlarda çözebilir.


Örnek olması açısından en büyük ortak bölen bulan algoritmalara bakalım. 3. yüzyılda Euclid of Alexandria tarafından bulunan bulunan Euclid's Algorithm aşağıdaki şekilde çalışıyor:

gcd(m, n) = gcd(n, m mod n)

Burada m ve n negatif olmayan ve aynı anda 0 olamayan iki tam sayıdır. m mod n ise m / n işleminin kalanıdır. Algoritma recursive (kendini tekrar tekrar çağıran) bir şekilde işliyor ve m mod n 0 olduğunda algoritma duruyor. 60 ve 24 sayıları için deneyelim:

gcd(60, 24) = gcd(24, 12) = gcd(12, 0) = 12

Algoritma adımlarını görelim:

Step 1 - Eğer n = 0 ise doğru cevap m değeridir, algoritmayı durdur; aksi halde Step 2'ye geç.
Step 2 - m sayısını n sayısına böl ve kalanı r değerine at.
Step 3 - n ve m değerlerini r ve n değerlerine ata, Step 1'e geç.

Algoritmaları bu şekilde ifade edebileceğimiz gibi pseudocode ile de ifade edebiliriz:


while n != 0 do
    r <- m mod n
    m <- n
    n <- r
return m
Aynı problemi çözen bir başka algoritma görelim. Bu algoritma sayıları tek tek deniyor. Algoritmanın ilk önerdiği şey m ve n değerlerinin minimumunu almak. En büyük ortak bölen bu iki sayının minimumundan büyük olamayacağına göre başlangıç sayımız bu olabilir. Daha sonra bu sayıyı sürekli deneyeceğiz ve olmadığı takdirde bir azaltacağız. Örneğin 60 ve 24 sayıları için ilk önce 24'ü daha sonra 23'ü deneyeceğiz ve bu şekilde 12'ye geldiğinde duracak:

Step 1 - min{m, n} değerini t değerine ata.
Step 2 - m / t işlemini yap. Eğer kalan 0 ise Step 3'e git, değilse Step 4'e git.
Step 3 - n / t işlemini yap. Eğer kalan 0 ise t cevaptır, dur; değilse Step 4'e git.
Step 4 - t değerini bir azalt, Step 2'ye git.

Aynı problemi çözen bir başka algoritma görelim:

Step 1 - m değerinin asal çarpanlarını bul.
Step 2 - n değerinin asal çarpanlarını bul.
Step 3 - Step 1 ve Step 2'de elde edilen çarpanlardan ortak olanlarını al.
Step 4 - Bu değerleri çarp.

60 ve 24 sayıları için örnek yapalım:

60 = 2 * 2 * 3 * 5
24 = 2 * 2 * 2 * 3
gcd(60, 24) = 2 * 2 * 3 = 12

Bu gösterdiğim son algoritmada bazı sıkıntılar mevcut. Asal çarpanları nasıl bulacağımızı bilmeden bu algoritmayı implemente edemeyiz. Ayrıca iki sıralanmış dizide ortak değerler nasıl bulunur? İlk olarak sieve of Eratosthenes (MÖ 200) algoritmasını inceleyelim. Bu algoritma, limit değerini belirlediğimizde 2'den başlayarak limite kadar olan asal sayıları buluyor. n = 25 için bir örnek yapalım:


2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
2 3   5   7   9    11    13    15    17    19    21    23    25
2 3   5   7 	   11 	 13 	     17    19 	       23    25
2 3   5   7 	   11 	 13 	     17    19 	       23
2'nin katları kendisi hariç listeen siliniyor. Daha sonra 3'ün katları siliniyor. 4 için böyle bir işlem yapmamıza gerek yok, zaten 2'nin katlarını silerek 4'ü elemiş olduk. 5'in katları siliniyor. Algoritma bu şekilde sayıların elenemeyecek duruma gelmesine kadar çalışıyor. Pseudocode'u görelim:


for p <- 2 to n do A[p] <- p

for p <- 2 to [sqrt(n)] do
    if A[p] != 0
	j <- p * p
	while j <= n do
	    A[j] <- 0
	    j <- j + p

for p <- 2 to n do
    if A[p] != 0
	L[i] <- A[p]
	i <- i + 1

return L
p * p işleminin sonucu sqrt(n) değerinden büyük olamayacğaına göre ikinci döngü bu değere kadar çalışacaktır. sqrt(n) yerine p * p <= n şeklinde bir koşul da belirtebilirdik aynı anlama denk geliyor.


Sonraki Yazı: Important Problem Types
Yorumlar

Henüz bir yorum bulunmuyor.