Yazar admin

Programlamanın temellerinden olan Algoritma kavramı ve konuları üzerine yayımladığımız makale serimize devam ediyoruz.
Bu bölümümüzde "Arama Algoritmaları"nı ele alacak, örneklerle detaylandırmaya çalışacağız.

Arama bilgi kümesi içerisinde belirli bir anahtar sözcüğe dayanılarak onunla ilgili diğer bilgilere erişme işlemidir.

En yalın arama şekli ,bilgiye ait verilere baştan sona kadar tek tek bakılarak yapılmasıdır;Ardışıl arama (sequential search) olarak adlandırılan bu yöntemde arama programının yazılması kolay ancak programın çalışma hızı çok düşük olur.

Tercih edilen arama yöntemi ise İkili arama (binary search) olarak adlandırılan algoritmadır.

En hızlı arama algoritması Çırpı fonksiyonu (hash function) olarak adlandırılandır ancak burada da çatışmaların olmadığı bir ideal bir çıpı fonksiyonu bulunması gerekir.

Özetle arama algoritmaları:

1-Ardışıl & Doğrusal arama
2-İkili (Binary) arama
3-Çırpı (Hashing) Fonksiyonu

Şayet kümedeki eleman sayısı yüzler mertebesinde ise kullanılacak algoritmanın ne olacağı çok da önemli değildir.Ancak eleman sayısı onbinler, yüzbinler veya milyonlar mertebesinde ise seçilecek arama algoritması önem kazanır.

İkili ağaç üzerinde ikili arama
Bilgilerin sıralı tutulduğu dizi üzerinde ise hem doğrusal hem de ikili arama algoritmaları kullanılabilir
Veriler dizi örneğinde olduğu gibi birer indis ile numaralanarak saklanmışsa çırpı algoritması kullanılır.

Arama işlemi belirli bir veya birkaç sözcüğe dayanılarak gerçekleştirilir: Bu sözcükler Anahtar sözcük (keyword) olarak adlandırılır.

Eğer veri anahtar sözcüğe göre önceden sıralanmış durumda ve dizi üzerinde tutuluyorsa arama işlemi oldukça hızlı yapılabilir,bu durumda ikili arama (binary search) kullanılır.

Dahili arama : (internal search) arama işlemi bellek üzerinde tutulan veriler üzerinde yapılır.

Harici arama: (external search) arama işlemi disk yedekleme birimi gibi belleğe göre daha yavaş olan saklama birimleri üzerinde yapılır.

Arama işlemlerinde kullanılan anahtar sözcükler farklı anlamlarda olabilmektedirler:
1-Birincil anahtar sözcük(primary keyword)-tek sonuç
2-İkincil anahtar sözcük (secondary keyword)-çok sonuç

Ardışıl aramada çalışma hızını artırmak amacıyla sıklıkta yöreselliğe dayanılarak en son aranıp da bulunanları bilgi kümesinin başına taşımak bir çözüm şeklidir.

İkili arama sıralı veriler üzerinde çalışır.

Çırpı fonksiyonu veriler üzerinde arama yapmak için en hızlı yöntemdir ancak herzaman ideal bir çırpı fonksiyonu bulmak mümkün olmayabilir.Çırpı fonksiyonu 3 ayrı bölümden oluşur:

1-çırpı fonksiyonu
2-çırpı tablosu veya tablo üzerinde tutulan veriler
3-çatışmaların çözümlenmesi

İKİLİ ARAMA YÖNTEMİ(Bisection):

1) dizi okutulur
2) sıralanır
3) ilk eleman B=1 ve son eleman indisi S=N+1 alınır
4) ilk indis ile son indis toplanır ve ikiye bölünerek tam kısmı alınarak yeni indis K bulunur.
5) Bu adresteki eleman ile aranan sayı A kıyaslanır

………………………….. a)D(K)

………………………….. c)D(K)=A ise eleman bulundu
6) Aksi halde eleman yoktur.
7) Max-16 aramada eleman bulunur yoksa yok demektir.

Örnek:
1- basla
2- I=1 al
3- D(I) gir
4- eğer I=N ise 6.adıma git
5- I=I+1 ve 3.adıma git
6- A gir
7- B=1 S=N+1
8- K=TAM((B+S)/2)
9- eğer D(K) = A ise 14.adıma git
10- Eğer S = B+1 ise 15.adıma git
11- eğer D(K) < A ise 13.adıma git
12- S = K al ve 8.adıma git
13- B = K al ve 8.adıma git
14- D(K) yaz ve 16. adıma git
15- “Bu sayı yok”
16- dur

UYGULAMA 1:

5 15 16 20 27 30 45 51 60 90

B=1 S=10+1

A=20

K=tam(1+11)/2=6 D(K)>A S=K,B=1

K=tam(1+6)/2=3 D(K) S=6,B=K=3

K=tam(3+6)/2=4 D(K)=A

UYGULAMA 2:

A=90

K=tam(1+11)/2=6 D(K) B=K,S=11

K=tam(6+11)/2=8 D(K) B=K,S=11

K=tam(8+11)/2=9 D(K) B=K,S=11

K=tam(9+11)/2=10 D(K)=A

Akış Şeması:

MATRİSLER VE MATRİSLERE İLİŞKİN ALGORİTMA VE

AKIŞ ŞEMALARI

Bazı problemlerde büyük diziler kullanılır ki bu durumlarda Matrislere gerek duyulabilir.Matrislerde her bir satır bir dizi şeklinde düşünülebilir.Kullanılan indisler satır ve sütunu tanımlar.Örneğin 10 satır ve 10 sütundan oluşan bir A matrisini A(10,10) şeklinde tanımlayabiliriz.I satırı,J sütunu göstermek üzere A matrisini A(I,J) olarak da belirleyebiliriz veya A(N,M) olarak da belirleyebiliriz.Burada eleman sayısı IxJ veya NxM kadardır.

ÖRNEK 1:

NxN lik bir matrisin esas köşegeni üzerindeki elemanların toplamını bulan bir algoritma hazırlayalım.

A1. Basla
A2. N gir
A3. I=1,
A4. J=1 al
A5. A(I,J) gir
A6. Eğer J=N ise A8. adıma git
A7. J=J+1 ve A5.adıma git
A8. Eğer I=N ise A10.adıma git
A9. I=I+1 al ve A4.adıma git
A10. TOPLAM=0,I=1 al
A11. TOPLAM=TOPLAM+A(I,I)
A12. Eğer I=N ise A14.adıma git
A13. I=I+1 al ve A11.adıma git
A14. TOPLAM değerini yaz
A15. Dur.

Algoritmalar ve Programlama konulu tüm dersleri okumak için tıklayınız.