Algoritmalar ve Karmaşıklık

Algoritmalar ve Karmaşıklık

Algoritma
• Ayrık matematikte karşılaşılan bir çok problem sınıfı mevcuttur.
Örneğin,
– verilen tamsayı grubu içindeki en büyük olanının bulunması,
– verilen bir kümenin bütün alt kümelerinin listelenmesi,
– verilen bir tamsayı kümesinin artan sırada sıraya dizilmesi,
– verilen bir ağ’da iki kenar arasındaki en kısa yol’un bulunması gibi.
• Böyle problemler ile karşılaşıldığında, ilk olarak problemin
matematiksel yapısını içeren bir modelinin bulunması gerekir.
• Böyle modellerde, permutasyonlar, bağıntılar, graflar, ağaçlar ve
sonlu durumlu makineleri gibi ayrık yapılar sıkça kullanılmaktadır.
• Uygun matematiksel modelin kurulması çözümün ilk adımıdır.
• Modeli kullanarak çözümü gerçekleştiren bir yöntem her zaman
gerekli olacaktır.
• Cevabı bulmak için sıralı adımları takip eden bir yordam
(procedure) olacaktır.
• Böyle sıralı işlem adımlarına algoritma denir.

Algoritma
• Tanım: Bir hesaplamayı gerçekleştirmek veya bir problemi
çözmek için kesin işlemlerin sonlu bir kümesine algoritma denir.
– Algoritmadaki her bir adım sonlu zamanda gerçekleştirilebilecek açık
ve belirli talimatlar içerir.
– Her bir adımda çalıştırılacak işlemler açık olarak tanımlanmalıdır.
– İşlemin, adımların sonlu sayıda çalıştırılması sonucunda
sonlandırılması garanti altına alınmalıdır.
• Algoritma kelimesi Türk Matematikçisi olan ve 9. yüzyılda
yaşamış olan El-Harezmi’nin isminden türetilmiştir.
• Aslen Türkistan’da Aral gölünün güneyinde bulunan Harzem
şehrindedir.
• Algoritma kelimesi Harezmi’nin adından gelen
Alkhorizmus=algorisma kelimesinin zamanla farklı dillerdeki
kullanımındaki değişiminden türemiştir.
Ders 11 Yrd.Doç.Dr. İbrahim TÜRKYILMAZ 11-4
Algoritma
Örnek: Sonlu sayıdaki tamsayılar kümesinin en büyük elemanın
bulunması için bir algoritma kurulmaya çalışıldığında:
• Problemin uygulaması çeşitli alanlarda karşımıza çıkabilir:
– Üniversite öğrencileri arasında derecesi en yüksek olanın
belirlenmesi,
– Bir spor organizasyonunda en yüksek dereceli olan sporcunun
belirlenmesi gibi.
• Problemin birçok çözümü olabilir. Bu çözümlerden bir tanesi
aşağıda verilmiştir.
1. Sayıların ilkini geçici en büyük olarak belirle.
2. Bir sonraki sayı ile geçici en büyük tamsayıyı karşılaştır. Eğer yeni
sayı geçici en büyükten büyük ise yeni sayıyı geçici en büyük olarak
belirle.
3. Eğer daha sayı var ise bir önceki adımı tekrarla.
4. Dizide başka eleman kalmamış ise dur. Bu noktada en büyük sayı
geçici en büyük olarak belirlenmiş olan sayı olacaktır.

Pseudocode - Sahtekod
• Algoritma bir bilgisayar dili yardımı ile gösterilebilir. Ancak bunu anlamak çoğu
zaman zor olur. Bunun yerine ortak olarak kullanılan pseudocode (sahtekod) ile
ifade edilir.
• Bu kodda anahtar kelimeler İngilizce olarak ifade edilen işlem adımlarını gösterir.
Pseudocode temel bilgileri:
• Bu bölümde sahtekod ile ilgili temel bilgiler(Algoritmaları anlatmak için kullanılan)
kısa olarak verilecektir.
• Bir algoritmanın sahtekodu procedure (yordam) ifadesiyle başlar. Bu
algoritmanın ismini, girdi değişkenlerinin listesini ve bunların hangi tip olduklarını
tanımlar. Örneğin,
Procedure maximum(L: tamsayı listesi, a:integer)
ifadesi algoritmanın sahtekod tanımlamasının ilk ifadesidir ve algoritmanın isminin
maximum ve L listesindeki tamsayıların maksimumunu bulur.

Sahtekod
Atama ve Diğer Tipten İfadeler
• Atama için := sembolü kullanılır. Atama ifadesi
değişken := ifade
formundadır. Örneğin;
max := a
x:= L listesindeki en büyük eleman
gibi ifadeler atama işlemi için kullanılabilir. Bu ifadeyi gerçek bir
programlama diline ifade etmek için birden fazla kod satırı
yazılmak zorunda kalınabilir. Burada
a ve b değişkenlerinin değerlerini değiştir
gibi ifadelerde kullanılabilir.
• Not: Burada bu yazımların kullanılmasının amacı sahtekodu
algoritmanın gerçek amacını gösterebilmek için kısa tutmaktır.

Sahtekod
İfade Blokları
• İfadeler (statements) kompleks yordamları bloklar içerisinde gruplamak için
kullanılır. Bu bloklar begin ve end ifadeleri kullanılarak tasarlanır. Bir blok
içerisindeki ifadeler aynı miktarda biraz daha içeriden başlatılır.
begin
ifade1
ifade2
…
ifade n
end
Blok içerisindeki ifadeler sırasıyla çalıştırılır.
Yorumlar
• Küme parantezleri içerisindeki ifadeler çalıştırılmaz. Böyle ifadeler, yordamın
nasıl çalıştığı hakkında bilgi sunan yorum satırları olarak kabul edilir. Örneğin
{ x, L listesi içerisindeki en büyük elemandır}
ifadesi okuyucuya x değişkeninin L listesinin en büyük elemanı olduğunu hatırlatır.

Sahtekod
Koşullu Yapılar
• En basit koşullu yapı için
if koşul then ifade
kullanılmaktadır. Blok bir ifadenin çalıştırılması için
if koşul then
begin
ifade bloğu
end
• Diğer bir kullanım türü de
if koşul then ifade1
else ifade2
• Bir diğer türde
if koşul_1 then ifade_1
else if koşul_2 then ifade_2
else if koşul_3 then ifade_3
…
else if koşul_n then ifade_n
else ifade_n+1

Sahtekod
Döngü Yapıları
• Sahtekod içerisinde kullanılan for, while do ve do until gibi
üç değişik döngü yapısından bahsedilecektir:
• for yapısının tek bir ifade ile kullanılan basit formu
for değişken:=başlangıç_değeri to son_değeri step artım
ifade
veya blok ifade içeren diğer bir formu
for değişken:=başlangıç_değeri to son_değeri step artım
begin
ifade
end
• Örneğin, 1’den n’e kadar tamsayıların toplamını hesaplamak istersek
sum:=0
for i:=1 to n
sum:=sum+i

Sahtekod
Döngü Yapıları
• Bir şartın sağlandığı sürece bir veya daha fazla ifadenin çalıştırılabileceği
döngüler while … do yapısı ile gerçekleştirilir:
while koşul [do]
ifade
veya
while koşul [do]
begin
ifade bloğu
end
• Örneğin 1’den n’e kadar tamsayıların toplamını hesaplamak istersek
sum:=0
k:=1
while k<n [do]
begin
sum:=sum+k
k:=k+1
end

Sahtekod
Döngü Yapıları
• Bir şart sağlanıncaya kadar bir veya daha fazla ifadenin
çalıştırılabileceği döngüler do … until yapısı ile gerçekleştirilir.
do
begin
ifade bloğu
end
until koşul
• Örneğin 1’den 10’e kadar tamsayıların toplamını hesaplamak istersek
sum:=0
n:=1
do
begin
sum:=sum+n
n:=n+1
end
until n=10

Sahtekod
• Örnek:Liste içerisindeki en büyük tam sayıyı bulma algoritması
Procedure enbuyuk(a1, a2, ..., an: integers)
enbuyuk := a1
for i := 2 to n
if enbuyuk < ai then enbuyuk := ai
{işlem sonunda en büyük tamsayı bulunmuş olur}
• Başka bir algoritmada bu tamsayıları büyükten küçüğe doğru azalan
şekilde sıralayıp ilk elemanı en büyük olarak almak olabilir.

Algoritmaların Özellikleri
• Algoritmalarda aşağıdaki özellikler bulunur ve bu özellikleri akıldan
çıkartmamak gereklidir.
– Giriş : Belirlenen veri kümesinden algoritma giriş değerleri alır.
– Çıkış : Algoritma her bir giriş kümesinde çıkış değerleri üretir. Bu
değerler problemin çözümüdür.
– Açıklık : Algoritmanın adımları açık olarak tanımlanmalıdır.
– Doğruluk : Algoritma her bir giriş kümesi için doğru çıkış üretmelidir.
– Sonluluk : Algoritma, her bir giriş kümesi için amaçlanan çıkışı, sonlu
işlem adımı(büyük olabilir) sonunda üretmelidir
– Verimlilik : Algoritmanın her bir adımı tam ve sonlu bir zaman
diliminde gerçeklenmelidir.
– Genellik : Yordam formdaki her probleme uygulanabilecek şekilde
genel olmalıdır.

• Verilen listedeki en büyük tamsayıyı bulma algoritması bu açıdan
değerlendirilirse;
– Giriş : Sonlu sayıda tamsayı kümesi
– Çıkış : kümedeki en büyük tamsayı
– Açık olarak adımlar tanımlanmıştır ve doğru sonuç üretir.
– Algoritma sonlu işlem adımı kullanır (n adım)
– Algoritma her bir adımda bir karşılaştırma işlemi yapar
(verimlilik).
– Algoritma bu tür kümelerdeki en büyük tamsayıyı bulacak
şekilde geneldir.

Arama Algoritmaları
• Sıralı listedeki bir elemanın yerinin bulunması çok
değişik olarak karşılaşılan bir problemdir.
– Örneğin sözlükten bir kelime aranması gibi problemlere arama
problemleri denir.
• Genel arama problemi aşağıdaki şekilde açıklanabilir:
– Farklı elemanları a1, a2, …, an olan bir listede bir x elemanın
yerinin öğrenilmesi veya listede olup olmadığının öğrenilmesi
şeklinde olabilir.
– Bu arama probleminin çözümü, x elemanına eşit olan ai elemanın
yerinin bulunmasıdır.
– Eğer x =ai ise x listenin i. elemandır.

Doğrusal Arama Algoritması
• Problemin çözümü için ilk algoritma doğrusal veya ardışık aramadır.
– Doğrusal arama algoritması, x ile a1 karşılaştırarak işleme
başlar.
– Eğer x =a1 ise aranan eleman 1. elemandır.
– Eğer x ≠ a1 ise, x ile a2 karşılaştırılır.
– Eğer x =a2 ise çözüm a2 nin konumudur.
– Eğer x ≠ a2 ise, x , a3 ile karşılaştırılır.
– Bu işlem bir uyuşma bulununcaya kadar devam eder.
– Uyuşma olmadıkça işlem devam eder.
– Eğer bir uyuşma bulunamaz ise sonuç sıfır olarak elde edilir.
– Doğrusal arama algoritmasının sahtekodu aşağıda verilmiştir.

Procedure dogrusalarama(x:integer, a1,a2,…,an:farklı tamsayılar)
i:=1
konum:=0
while( i≤n and x≠ai)
i:=i+1;
if i≤n then konum:=i
else konum:=0
Ders 11 Yrd.Doç.Dr. İbrahim TÜRKYILMAZ 11-18
İkili Arama Algoritması
• Bu algoritmada verilen veriler artan şekilde sıralanmış
olmalıdır.
– Veriler tamsayı ise en küçükten en büyüğe doğru sıralanmış,
eğer kelime iseler alfabetik olarak sıralı şekildedir.
• Böyle bir veri kümesinde bir eleman aranması için algoritma ikili
aramadır.
• İkili arama algoritmasının mantığı; sıralı veri kümesi ortadan iki
kümeye ayrılarak bulunması istenen veri bu alt kümelerden
hangisinin içerisinde olabileceğinin kontrolü prensibine bağlıdır.
• Arama işlemi alt kümelerde tekrarlanarak bulunması gerekli
olan veri bulunmaya çalışılır.

Örnek: 1,2,3,5,6,7,8,10,12,13,15,16,18,19,20,22 sıralı dizisi içerisinde
19 tamsayısı aransın.
• Dizide 16 eleman bulunduğundan 1,2,3,5,6,7,8,10 ve
12,13,15,16,18,19,20,22 şeklinde 8’li iki alt kümeye ayrılır.
• 19 tamsayısı birinci alt kümenin en büyük elemanı ile karşılaştırılır.
10 < 19 olduğundan aranan sayı ikinci alt kümededir.
• Bundan sonra ikinci alt küme 12,13,15,16 ve 18,19,20,22 olmak
üzere 4 elemanlı iki alt kümeye ayrılır. 16 < 19 olduğundan aranan
tamsayı sağ alt kümede olabilecektir.
• Bu nedenle sağ alt küme yine 18,19 ve 20,22 olmak üzere iki
elemanlı iki alt kümeye ayrılır.
• Şimdi 19 tamsayısı, son ikili kümenin en büyük elemanından büyük
olmadığı için arama ilk kümenin 13. ve 14. elemanını içeren kümeyle
sınırlanır.
• Böylece son kümede 18 ve 19 tamsayılı ve birer elemanlı iki alt
kümeye ayrılır. 18 < 19 olduğundan arama 19 tamsayısından oluşan
son kümeye sınırlanır ve kümenin 14. elemanı olarak bulunur.
Ders 11 Yrd.Doç.Dr. İbrahim TÜRKYILMAZ 11-20
İkili Arama Algoritması
• Algoritmanın sahtekodu aşağıda verilmiştir.
Procedure ikiliarama(x:integer, a1,a2,...,an: artan tamsayılar)
i:=1; {i, arama aralığının sol bitiş noktasını gösterir}
j:=n; {j, arama aralığının sağ bitiş noktasını gösterir}
while i<j do
begin
m:=[(i+j)/2];
if x>am then i:=m+1;
else j := m;
end
if x=ai then konum:=i
else konum:=0;
{konum, x’e eşit olan terimin indisidir veya eğer x
bulunamamış ise değeri sıfırdır}

Algoritmaların Karmaşıklığı
• Algoritmaların özellikleri içerisinde verimlilik olması gerektiği açıklanmıştı.
• Algoritmanın verimliliği ne demektir? Bunun analizi nasıl yapılır?
• Verimliliğin bir ölçütü, algoritmanın belirli bir giriş verisine karşın,
problemin çözümü için bilgisayarın harcadığı zamanın ölçülmesidir.
• Diğer bir ölçü ise belirli giriş verisine karşı bilgisayarın kullandığı bellek
miktarıdır.
• Böyle sorular algoritmanın bir hesaplama karmaşıklığının geliştirilmesini
gerektirir.
• Problemi çözmek için algoritmanın harcadığı zamanın analizi zaman
karmaşıklığını, gerekli belleğin analizi ise yer (space) karmaşıklığının
hesabını gerektirir.
• Yer karmaşıklığı probleminin çözümü, algoritmayı gerçeklerken kullanılan
veri yapıları ile bağlantılıdır. Ancak bu konular içerisinde yer
karmaşıklığından bahsedilmeyecektir.
• Algoritmanın zaman karmaşıklığı ise, belirli miktardaki giriş verisine
karşılık, yapılan karşılaştırma, tamsayı toplama, tamsayı çıkartma, tamsayı
çarpma ve bölme işlemleri ile diğer basit işlemlerin sayısı olarak hesaplanır.
Ders 11 Yrd.Doç.Dr. İbrahim TÜRKYILMAZ 11-22
• Bilgisayarda hesaplamalar genellikle aşağıdaki işlemler yardımıyla
gerçekleştirilir:
– Atama
– Karşılaştırma (==, ≠, >, <, ≤, ≥)
– Aritmetik işlemler (+, -, ×, /)
– Mantıksal operasyonlar
• Bu operatörlerin çalıştırılması ne kadar zaman alır?
• Genelde, atama çok hızlı yapılır ve diğer işlemler daha yavaştır.
Çarpma ve bölme de toplama ve çıkarmadan daha yavaştır. Kayan
noktalarla işlem yapmak, tamsayılarla işlem yapmakta daha
yavaştır.
• Çoğu algoritmada bu işlemlerden çok sayıda kullanılmaktadır ve
hepsinin ne kadar zaman alacağını teker teker hesaplamak
oldukça zor olacaktır. Bunun yerine çoğu algoritmada zaman
karmaşıklılığı baskın olan tek bir işlem ile belirlenebilmektedir.

• Algoritma karmaşıklık analizinde dikkat edilmesi
gereken yaklaşımlar:
– Sadece en çok zaman kaybettiren işlemleri hesaba katınız.
– Hesaplama zamanının girdi boyutuna bağlı olarak değiştiğinde
en kötü durumu analiz ediniz.
– Algoritma girdisinin genelde büyük olduğunu kabul ediniz.
– Eğer bir algoritmanın zaman karmaşıklılığının artış oranı
diğerinin sabit bir katı olduğu durumlardaki iki zaman
karmaşıklılığının ayırt etmeye çalışmayınız. Bu durumda her
ikisi de aynı kabul edilir.

Örnek ( Zaman karmaşıklığı için)
• Bir A dizisinin en küçük elemanını bulan algoritmanın zaman karmaşıklığının hesabı:
Procedure enkucuk(A real array, enkucuk:real)
enkucuk := A[1];
for i := 2 to n
begin
if A[i] < enkucuk then enkucuk := A[i]
{en kötü durumda n-1 defa icra edilir}
end {işlem sonunda en küçük ayı bulunmuş olur}
• Bu algoritmanın zaman karmaşıklığı en kötü durumda dizinin büyüklüğü
mertebesindedir.
• Bu yordamın işlem sayısını hesaplamaya çalışalım:
• Karşılaştırma işlemlerinin sayısı : n-1
• Atama işlemlerinin sayısı: n-1 ; Algoritmanın (zaman) karmaşıklığı O(n) dir.
• Karmaşıklığı ifade etmek için O(n) notasyonu kullanılır. O mertebe (order) işareti,
(n) in sonlu bir çarpanla çarpımından daha küçüktür.
• İşlemlerin sayısı ≤ k n { k : sınırlı sabit, n : problemin büyüklüğü olarak tanımlanır}

Örnekler
• En küçük sayıyı bulma algoritması :
n-1 : O(n)
• Hem en küçük hem de en büyüğü bulma :
n-1 + n-2 = 2n-3 : O(n)
• Sıralama yapan algoritma (En küçükten büyüğe):
(n-1) +(n-2) +(n-3) +· · · ·+1 = n*(n-1)/ 2 = n2/2− n/2 : O(n2)
A5 2n 9 15 21 Torba doldurma problemi
A4 n3 10 39 153 Matris Çarpımı
A3 n2 31 244 1897 Geleneksel sıralama
A2 nlog n 140 4893 2 × 105 Sıralama(Quicksort)
A1 n 1000 6 × 104 3.6 × 106 En küçüğü bulma
1 sn. 1 dk. 1 saat
Zaman Çözülebilen En büyük problem Örnek algoritma
Karmaşıklığı
Algoritma
• Burada dikkat edilmesi gereken ilginç bir nokta, mertebe arttıkça
çözebildiğimiz problem sayısı çok çabuk düşmesidir.

Örnek: İkili arama algoritmasının karmaşıklık hesabının yapılması:
Çözüm: Basitlik için a1, a2,.., an listesinde n = 2k eleman olduğunu
varsayalım (k>0).
• Burada k = log2 n olacaktır. Eğer kümedeki elemanların sayısı 2’nin
katı şeklinde değil ise liste 2k+1 elemanlı daha büyük bir liste
olacaktır (burada 2k < n < 2k+1 gerçeklendiği açıktır).
• Aranan sayı bulununcaya kadar i ve j sayıları birbirine yaklaşır.
• İlk adımda liste 2k-1 e sınırlanır. İkinci adımda liste 2k-2 ‘ye
sınırlanır. En sonunda liste 21 = 2 elemanlı olarak kalır.
• Listede tek eleman kalınca karşılaştırma başka eleman olmadığını
gösterir işlem k+1 adımda biter. İkili arama algoritmasını icra
etmek için (her bir adımda 2 karşılaştırma yapıldığından) toplam
2k+2= 2log2 n+2 karşılaştırma yapılır.
• Buradan ikili arama algoritmasının karmaşıklığının en kötü durumda
O(log2 n) olduğu söylenebilir.

• Diğer bir karmaşıklık analizi ortalama durum analizidir. En kötü
durum analizinden daha karmaşık olan bu analiz doğrusal arama
algoritmasının karmaşıklık hesabında kullanılmıştır.
Örnek: Aranan elemanın liste içerisinde olduğunu kabul ederek
doğrusal arama algoritmasının en ortalama durum analizini yapınız:
Çözüm: x in liste içerisinde olduğu n değişik mümkün girdi vardır.
• Eğer x listenin birinci terimi ise, üç karşılaştırma gerekir, biri
listenin sonuna ulaşıldı mı, diğeri x ile birinci terimi karşılaştır, bir
diğeri de döngü dışına çıkılması.
• Eğer listenin ikinci terimi ise ek iki karşılaştırmaya ihtiyaç vardır,
dolayısıyla toplam beş karşılaştırmaya ihtiyaç vardır.
• Eğer x listenin i. terimi ise döngünün her bir i. Adımında iki
karşılaştırma yapılmakta ve bir tane de döngü dışında
yapılmaktadır. Sonuç olarak 2i+1 karşılaştırmaya ihtiyaç vardır.
• Böylece karşılaştırmaları ortalaması
• 3 5 7 (2n 1) 2(1 2 3 n) n 2 ( ) n On
n n
+ + + ⋅⋅⋅ + + + + + ⋅⋅⋅ + +
= = + =

Büyük-O (Big-O) Notasyonu
• f(n) ve g(n) iki zaman karmaşıklığı olsun. Eğer n sayısının yeteri
kadar büyük değerleri için f(n) ≤ c g(n) olacak şekilde bir pozitif
c sayısı varsa f(n) zaman karmaşıklığı O(g(n)) dir.
• Başka bir deyişle, n sayısı yeteri kadar büyük olduğunda, f(n),
g(n) ile aynı büyüklüktedir.

Veri Yapılarına Genel Bakış

Veri Yapılarına Genel Bakış

Algoritmalar ve veri yapılarının bu ilk dersinde bu konular hakkında kısa bilgilendirmeler ve karşılaştırmalara yer vereceğiz. Bu kategoride tarafımdan eklenecek tüm örnek kodların tamamı JAVA dilindedir.

Veri yapılarının incelenmesinde en önemli unsurlar veriye erişim ve yapının karmaşıklığıdır. Şimdi veri yapılarının güçlü ve zayıf yanlarını bir tablo ile gösterelim.

Veri Yapısı	Artıları	Eksileri
Dizi	Hızlı ekleme ve çok hızlı erişim(indis biliniyorsa).	Yavaş arama, yavaş silme ve sabit boyut.
Sıralı Dizi	Sıralanmamış diziye göre daha hızlı arama.	Yavaş arama, yavaş silme ve sabit boyut.
Yığın	Son giren, ilk çıkar(last-in, first-out) erişimi sağlar.	Diğer öğelere yavaş erişim.
Kuyruk	İlk giren, ilk çıkar(first-in, first-out) erişimi sağlar.	Diğer öğelere yavaş erişim.
Bağlı Liste	Hızlı ekleme ve silme.	Yavaş arama.
Hash Tablosu	Hızlı ekleme ve anahtar bilindiğinde çok hızlı erişim.	Yavaş silme, anahtar bilinmediğinde yavaş erişim ve verimsiz bellek kullanımı.
Küme(Heap)	Hızlı ekleme ve silme.	Diğer öğelere yavaş erişim. Başta en büyük öğeye erişim.
İkili Ağaç	Hızlı arama, ekleme ve silme(ağaç dengeli kalmışsa).	Silme algoritması karmaşık.
Graf	Gerçek-dünya problemlerini modelleyebilmesi.	Bazı algoritmaları yavaş çalışmakta ve karmaşıklığı yüksek.

Algoritmalara Genel Bakış
Algoritmalar kısmında anlatılacak konuların bir çoğunda belirli veri yapıları üzerinde uygulamalar gösterilecektir. Birçok veri yapısı için; veri ekleme, belirli bir öğeyi arama ve belirli bir öğeyi silme işlemlerinin nasıl yapıldığını bilmeniz gerekebilir. Ayrıca sıralama algoritmaları, genetik algoritmalar ve özyinelemeli yaklaşımlar konuları da ilerleyen derslerde anlatılacaktır.

Veri yapıları ve algoritmalar-Kuyruklar (queue) örnek uygulama

Veri yapıları ve algoritmalar-Kuyruklar (queue) örnek uygulama

KUYRUK
Kuyrukların Özellikleri
·         Giriş Sırası = Çıkış Sırası
Tek bir kasanın hizmet verdiği bir süpermarkette ödeme yapmak için bekleyen insanların oluşturduğu sıra gibi bir diziye “kuyruk” (queue) adı verilir. Bu ödeme kuyruğuna ilk giren kişi sonra girenlerden önce ödemesini yapıp gider (ilk-gir, ilk-çık, yani first-in, first-out, ya da kısaca FIFO). En son giren işi ise en son ödeme yapacak olan kişidir (son-gir, son-çık, yani last-in, last-out ya da kısaca LILO). Bu FIFO ve LILO özellikleri beraberce “giriş sırasıyla çıkış sırasıyla aynıdır” diye ifade edilebilirler.
·         Sırayla erişim
Bir kuyruk oluşturacak bir veri grubundaki elemanlar birbirleriyle bağlantılı olmalıdır ki kuyruktaki her eleman kuyruğa girdiği sırayla işlem görebilsin. Bağlantılı bir listede olduğu gibi bir kuyrukta da her eleman bir sonraki elemanın yerini bildiren bir adres değişkenine sahip olmalıdır, veya kuyruk elemanlarının adresleri ayrı bir adres değişkenleri dizisinde saklanmalıdır.
Kuyruklarla İlgili Özel İşlemler
·         Sona Ekleme
Bir süpermarket kasası önündeki ödeme kuyruğuna aradaki bir noktadan girilmez. Fiziksel bariyerler yoksa bile etik prensipler veya toplum baskısı bunu engeller. Aynı şey kuyruk oluşturacak şekilde sıralanıp bağlanmış değişkenler için de doğrudur. Bir kuyruğa ancak en son konumdan yeni bir eleman eklenebilir.
Eğer kuyruğun son elemanının adresi pSON gibi bir değikleme için tek gereken şey yeni elemanı son elemandan sonraki eleman olarak tanıtmaktır. Bu işlemden sonra yeni eleman yeni son eleman olacaktır:
2‑8 Bir kuyruğun sona yeni bir eleman eklenmesi
pSON.pSonraki=pYeniEleman
pSON=pYeniEleman
·         Önden Çıkartma
Bir dizi veya listedeki elemanlar, eğer programcı belli bir andan sonra hiç ama hiç gerekli olmayacak elemanları silmek için komutlar yazmamışsa, program çalışıp bitinceye kadar var olmaya devam ederler. Halbuki bir kuyruktaki elemanlar, üzerlerinde gerekli işlemler yapıldığı zaman –tıpkı ödemesini yapmış süpermarket müşterileri gibi- kuyruktan ayrılmalıdırlar. Kural gereği olarak, kuyruğun ilk elemanı kuyruktan ilk ayrılan eleman olacaktır:
2‑9 Öndeki elemanın kuyruktan çıkartılıp silinmesi
pİLK.Değer = BOŞ
pİLK = pİLK.pSonraki
BOŞ değer atanması başlangıçta en önde yer alan elemanın hafızadan silinmesi içindir. Bu işlem yapılmayıp bu değişken hafızada bırakılsa bile ikinci komuttaki işlemle kuyruktan çıkartılmış olacaktır.
Yığınlar (Stacks)[1]
Yığınların Özellikleri
·         Son Giren İlk Çıkar
Aynı anda çok sayıda müşteriye hizmet veren büyük bir lokantada tabaklar bir yandan yıkanıp yığılırken bir yandan da yeni müşterilere servis yapmak için yığından çıkartılırlar. Bu tabak yığınının ilginç bir özelliği vardır: Yığına ilk giren tabak en altta kalmış olacağı için yığındaki diğer tabakları devirmeden yerinden kolayca alınamaz. Dolayısıyla servis yapacak bir garson çabucak işine dönmek için yığının en üstündeki tabağı, yani yığına en son eklenmiş tabağı alıp gidecektir. Kısacası bir yığını diğer veri yapılarından ayırt eden özellik son-gir, ilk-çık (last-in, first-out, kısaca LIFO) diye adlandırılır. Bir yığına ilk giren elemansa son çıkacak olan elemandır (first-in, last-out, kısaca FILO).
·         Bağlantılılık
Bir yığın oluşturacak bir veri grubundaki elemanlar da birbirleriyle bağlantılı olmalıdır. Üstteki eleman çıkartılırsa sıra onun altındakine gelecektir. Üstteki elemanın bir altındaki eleman zaman sırasında göre önceki elemandır, ama liste ve kuyruklarda yaptığımız gibi alttaki elemanı sonraki eleman olarak düşüneceğiz.
Yığınlarla İlgili Özel İşlemler
·         Üste Ekleme
Bir yığına da ancak en üst konumdan yeni bir eleman eklenebilir.
Eğer yığının en üst elemanının adresi pÜST gibi bir adres değişkeniyle belirlenmişse, tek gereken şey bu üst elemanı yeni eklenecek elemandan sonraki eleman olarak tanıtmaktır. Bu işlemden sonra yeni eleman üst eleman olacaktır:
Kod Örneği 2‑10 Bir yığının üstüne yeni bir eleman eklenmesi
pYeniEleman.pSonraki = pÜST
pÜST = pYeniEleman
·         Üstten Çıkartma
Yığındaki en üst eleman üzerinde gerekli işlemler yapıldığı zaman yığından çıkarılmalıdır. Bunun için yapılacak şey boş elemanı “silmek” için gereken işlem neyse onu yapmak ve ondan bir önceki elemanı yeni üst eleman olarak işaretlemektir.
Kod Örneği 2‑11 Yığının üst elemanının çıkartılması
pÜST.Değer = BOŞ
pÜST = pÜST.pSonraki
Nesneye Yönelik Programlama Dillerinde Veri Yapıları
Sınıf Değişkenleri
Bu bölümde kısaca gözden geçirdiğimiz en temel türden veri yapıları üzerinde yapılabilecek işlemler (yeni eleman sokma veya silme, önden çıkartma, sona ekleme, vb.) veri yapısını oluşturan elemanların türlerine bakmaksızın, belli adımlar atılarak gerçekleştirilirler. Dolayısıyla, programında bir bağlantılı liste, bir kuyruk vb. yarataıp kullanacak olan bir programcı belli işlemler için gereken belli adımları bilip o adımları gerçekleştirecek komutları programına eklemelidir. Yüzbinlerce programcı bu tür veri yapıları üzerinde çalışacak komut dizilerini tekrar tekrar yazmak zorunda kalmasınlar diye bu komut dizilerini önceden hazırlanmış fonksiyonlar halinde paketleyip programcıların kullanımına sunmak en mantıklı çözümdür. Yapısal programlama dillerine ait derleyicilerle birlikte gelen fonksiyon kütüphaneleri veri yapılarının kullanımını kolaylaştırabilirler. Nesneye yönelik programlama dilleri ise belli bir veri yapısı üzerinde belli işlemler yapabilecek fonksiyonları veri yapısının kendisiyle birlikte paketleyip sunarak programcıların işlerini daha da kolaylaştırırlar. Nesneye yönelik bir programlama dilinde, bir programcı belli bazı değişkenleri gruplandırarak bir karmaşık değişken veya bir veri yapısı tanımı yatattığında, o değişken grubu üzerinde gerekli işlemler yapacak belli fonksiyonları da değişken grubu tanımına ekleyebilir. Kendisiyle ilişkili fonksiyonları da tanımında barındıran bir veri grubuna “sınıf değişkeni” (class variable) denir.
Üye Fonksiyonlar
Bir sınıf değişkeninin tanımına dahil edilmiş fonksiyonlara “üye fonksiyonlar” (member functions) veya “metodlar” denir. Bir sınıf değişkeni olarak tanımlanmış bir veri yapısını bir programda kullanmak için sınıf değişkeninin üye fonksiyonlarını çağırmak yeterlidir. Örneğin, C++ dilinde bir bağlantılı liste list türü bir sınıf değişkeni ile temsil edilebilir. Tamsayı elemanlardan oluşan bir liste türü değişken
list tamsayi_liste;
şeklinde, ondalıklı sayılardan oluşan bir liste ise
list ondalikli_liste;
şeklinde tanımlanabilir. Aşağıdaki kod örneği bu türden bir tamsayı listesi yaratıp ona elemanlar ekleyip çıkartan bir C++ programının parçasını gösteriyor:
Kod Örneği 2‑12 Bir C++ programında bir bağlantılı liste tanımlanması ve eleman eklenmesi
list tamsayi_liste;
tamsayi_liste.push_back(1);
tamsayi_liste.push_front(2);
tamsayi_liste.push_back(3);
tamsayi_liste.pop_front();
tamsayi_liste.push_back(5);
tamsayi_liste.pop_back(6);
İngilizce bilmeyen okuyucularımız için açıklayalım: Bu örnekte kullanılan push_back() üye fonksiyonu liste sonuna, push_front() üye fonksiyonu ise liste önüne eleman eklemek için kullanılabilir. pop_back() liste sonundan, pop_front() liste başından eleman çıkartmak için kullanılırlar.
Listeler, kuyruklar veya daha karmaşık veri yapılarını temsil eden sınıf değişkenlerini kullanmak programcıların işlerini kolaylaştırdığı gibi, onlara kısa ve kolay anlaşılır programlar yazma imkanını da verir, ama veri yapıları üzerinde yapılacak işlemleri ortadan kaldırmaz veya kısaltmaz. N adım gerektiren bir arama işlemi veya N2 adım gerektiren bir sıralama işlemi, ilgili üye fonksiyonlarını çağıran birer komuttan ibaret bile olsalar aynı sayıda adım gerektirirler. Bu tür bir üye fonksiyon kullanan bir algoritmanın adım sayısını hesaplarken, her bir komutun gerektirdiği adım sayısını bilip ona göre hesap yapmalıyız. Biz bu ders notlarının metin kısmında gerçek program örnekleri vermeyeceğiz, ama bazı kod örneklerimizi daha kısa ve anlaşılır olsunlar diye nesneye yönelik bir programlama dilini kullanıyormuş gibi yazacağız.
[1] Bülent Sankur’un Bilişim Sözlüğü (1) stack terimi için “yığıt” karşılığını öneriyor. Bu kitapta kulağa daha tanıdık gelen bir karşılık seçtik.
ÖRNEK1
#include
#include
using namespace std;
int main ()
{
queue<int> myqueue;
int myint;
cout << “Tam sayi giriniz (enter 0 to end):n”;
do {
cin >> myint;
myqueue.push (myint);
} while (myint);
cout << “kuyrugun icerigi: “;
while (!myqueue.empty())
{
cout << ” ” << myqueue.front();
myqueue.pop();
}
return 0;
}
Örnek 2
// queue::empty
#include
#include
using namespace std;
int main ()
{
queue<int> myqueue;
int sum (0);
for (int i=1;i<=10;i++) myqueue.push(i);
while (!myqueue.empty())
{
sum += myqueue.front();
myqueue.pop();
}
cout << “total: ” << sum << endl;
return 0;
}
çıktı:
total: 55

Algorithmen und Datenstrukturen 2 - Sınav Örnekleri ve Çözümler

link: http://www.filesonic.com/file/4074306355/viyana.us_ad2.rar