Veri Yapıları ve Algoritma Analizi

Karmaşıklık analizi, temel veri yapıları, ağaçlar, hash tabloları, graflar, sıralama ve aramanın yanında böl-ve-yönet, greedy, dinamik programlama, amortize/rastgele analiz ve NP-zorluk sınırlarını kapsayan ders notları.

Veri yapıları ve algoritmalar notlarını yalnız yapıların tanımını değil, her işlemin maliyetini birlikte görmek için tutmuştum. Dizi, bağlı liste, yığın, kuyruk, ağaç, hash ve graf yapıları algoritma analiziyle birlikte ele alınır; Big-O yorumlarında en kötü, ortalama ve amortize maliyetler birbirinden ayrılır.

Ünite 1: Giriş ve Temel Kavramlar

Yazılım ve program

Bir program, belirli bir problemi çözmek veya belirli bir görevi yerine getirmek için tanımlanmış algoritmanın bir programlama diliyle ifade edilmiş biçimidir. Yazılım ise tek bir programdan daha geniş bir kavramdır. Programların yanında yapılandırma bilgileri, veri dosyaları, kütüphaneler, testler, belgeler ve çalıştırma için gerekli diğer bileşenleri de kapsayabilir.

Veri yapıları ve algoritmalar açısından temel ayrım şudur:

algoritma, çözümün işlem adımlarını,
veri yapısı, bu adımlarda kullanılan verinin nasıl düzenlendiğini

belirler.

Aynı problem farklı veri yapılarıyla çözüldüğünde algoritmanın çalışma süresi ve bellek gereksinimi önemli ölçüde değişebilir.

Donanım ve bellek

Bilgisayar donanımı işlemci, bellek, depolama birimleri ve G/Ç bileşenlerinden oluşur.

Bir program çalışırken temel olarak:

komutlar,
değişkenler,
veri yapıları,
çağrı yığını,
dinamik olarak ayrılan alanlar

bellekte bulunur.

Bellek tek tip değildir. İşlemciye yakınlık ve erişim süresine göre genel hiyerarşi:

Yazmaçlar
    ↓
Önbellek
    ↓
Ana bellek
    ↓
Kalıcı depolama

biçiminde düşünülebilir.

Bir veri yapısının gerçek performansı yalnız teorik karmaşıklığa değil, bellekteki yerleşimine ve erişim örüntüsüne de bağlıdır.

İşletim sistemi

İşletim sistemi uygulamalarla donanım arasında kaynak yönetimi ve soyutlama sağlar.

Başlıca görevleri:

süreç ve iş parçacığı yönetimi,
bellek yönetimi,
dosya sistemi,
aygıt yönetimi,
güvenlik ve yetkilendirme,
ağ hizmetleri,
zamanlama

olarak özetlenebilir.

Veri yapıları uygulama düzeyinde görünse de birçok temel yapı işletim sistemlerinde doğrudan kullanılır. Örneğin:

kuyruklar zamanlamada,
ağaçlar dosya sistemlerinde ve sanal bellekte,
hash tabloları çekirdek içi hızlı aramalarda,
grafik yapıları bağımlılık ve kaynak ilişkilerinde

kullanılabilir.

Veri yapısı ve veri modeli

Veri yapısı, verinin bellekte veya başka bir saklama ortamında nasıl düzenlendiğini ifade eder.

Örnekler:

dizi,
bağlantılı liste,
yığın,
kuyruk,
ağaç,
hash tablosu,
graf.

Veri modeli ise problemdeki nesnelerin ve ilişkilerin nasıl kavramsallaştırıldığını anlatır.

Örneğin bir yol ağı graf modeliyle ifade edilebilir. Bu graf bellekte:

komşuluk matrisi,
komşuluk listesi,
kenar listesi

gibi farklı veri yapılarıyla tutulabilir.

Bu nedenle veri modeli ile veri yapısı aynı kavram değildir.

Algoritma

Algoritma, belirli girdilerden beklenen çıktıyı üretmek için tanımlanmış sonlu ve açık işlem dizisidir.

Bir algoritmanın temel özellikleri:

girdileri açık olmalıdır,
çıktısı tanımlı olmalıdır,
adımları belirsizlik içermemelidir,
sonlu sürede tamamlanmalıdır,
uygulanabilir işlemlerden oluşmalıdır.

Aynı problemi çözen algoritmalar arasında seçim yapılırken yalnız doğruluk değil:

çalışma süresi,
bellek gereksinimi,
veri büyüklüğü,
veri dağılımı,
güncelleme sıklığı,
uygulama ortamı

da değerlendirilir.

Program çalışma hızı ve bellek gereksinimi

Bir programın duvar saatiyle ölçülen çalışma süresi:

işlemciye,
derleyiciye,
işletim sistemine,
önbellek davranışına,
giriş verisine,
sistem yüküne

bağlıdır.

Algoritmaları donanımdan daha bağımsız karşılaştırmak için asimptotik karmaşıklık kullanılır.

İki temel ölçüt:

zaman karmaşıklığı,
alan karmaşıklığıdır.

Örneğin bir dizinin bütün elemanlarını bir kez dolaşan algoritma:

O(n)

zaman karmaşıklığına sahiptir.

İki iç içe tam dolaşım:

O(n^2)

olabilir.

İşlemci, makine kodu ve assembly

İşlemci yalnız kendi komut kümesinde tanımlı makine komutlarını yürütür.

Makine kodu doğrudan işlemci tarafından çözümlenebilen ikili komut gösterimidir.

Assembly dili aynı komutları insan için daha okunabilir simgesel adlarla ifade eder.

Örneğin:

MOV
ADD
SUB
JMP

gibi komut adları assembly gösterimidir.

Modern yüksek düzeyli diller kaynak kodu doğrudan veya ara gösterimler üzerinden makine koduna dönüştürür.

Programlama dilleri

Programlama dili algoritmayı yürütülebilir sisteme aktarmanın aracıdır.

Programlama dilleri farklı soyutlama düzeylerine ve çalışma modellerine sahiptir.

Örnekler:

C ve C++ sistem programlama,
Java ve C# yönetilen çalışma ortamları,
Python genel amaçlı ve bilimsel uygulamalar,
Rust bellek güvenli sistem programlama

alanlarında kullanılabilir.

"Alt düzey", "orta düzey" ve "üst düzey" ayrımı kesin teknik sınıflandırma değildir. Bir dilin uygunluğu problem alanı, performans ihtiyacı, araç ekosistemi ve bakım gereksinimine göre değerlendirilmelidir.

Veri tabanı ve SQL

Veri tabanı büyük ve kalıcı veri kümelerinin düzenli biçimde saklanmasını sağlar.

İlişkisel veri tabanlarında SQL:

veri tanımlama,
sorgulama,
ekleme,
güncelleme,
silme,
yetkilendirme

işlemlerinde kullanılır.

Veri tabanının fiziksel iç yapısında da bu derste ele alınan veri yapıları bulunur. Örneğin indekslerde B-tree ailesi, hash yapıları ve farklı sıralı erişim mekanizmaları kullanılabilir.

Böl ve yönet

Böl ve yönet yaklaşımı büyük problemi aynı yapıya sahip daha küçük problemlere ayırır.

Genel yapı:

Problemi böl
    ↓
Alt problemleri çöz
    ↓
Sonuçları birleştir

Örnek algoritmalar:

merge sort,
quicksort,
binary search.

Böl ve yönet çoğu zaman özyinelemeli ifade edilir ancak özyineleme zorunlu değildir.

Ağ programlama

Ağ programlama farklı süreç veya bilgisayarların protokoller üzerinden veri alışverişinde bulunmasını sağlar.

Günümüzde TCP/IP ailesi genel ağ iletişiminin temelidir.

Veri yapıları açısından ağ yazılımlarında:

gönderim ve alım kuyrukları,
bağlantı tabloları,
yönlendirme grafikleri,
zaman aşımı listeleri,
tamponlar

önemli rol oynar.

Kıyaslama

Başarım ölçümü, bir algoritma veya sistemin belirli iş yükü altında ölçülmesidir.

Sağlıklı kıyaslama için:

aynı problem,
aynı veri kümesi,
aynı donanım,
aynı derleyici ayarları,
yeterli tekrar sayısı,
ısınma etkilerinin denetlenmesi

gerekir.

Asimptotik analiz ile başarım ölçümü birbirinin alternatifi değildir.

Asimptotik analiz büyüme davranışını, başarım ölçümü ise belirli gerçekleştirim ve ortamın gerçek davranışını gösterir.

Ünite 2: Veri Yapıları

Ham veriden bilgiye

Bellek fiziksel olarak bit dizileri saklar. Bu bitlerin anlamı veri tipine göre belirlenir.

Aynı bit dizisi:

tamsayı,
karakter,
yüzen nokta,
komut,
renk,
adres

olarak farklı yorumlanabilir.

Bu nedenle veri yalnız bit dizisi değildir. Anlam için bir gösterim biçimi gerekir.

Veri yapılarının sınıflandırılması

Temel düzeyde veri yapıları iki grupta düşünülebilir:

Temel veri tipleri

tamsayı,
yüzen nokta,
karakter,
Boolean.

Bileşik veya kullanıcı tanımlı yapılar

dizi,
record/struct,
union,
sınıf,
bağlantılı yapı.

Daha üst düzey soyut veri tipleri ise:

stack,
kuyruk,
set,
map,
tree,
graph

gibi davranış sözleşmeleri tanımlar.

Bilgisayar belleği

Modern genel amaçlı sistemlerde bellek bayt adreslidir.

Bir bayt:

8 bit

olarak kabul edilir.

Adres:

0
1
2
3
...

şeklinde her bayta erişim sağlar.

Çok baytlı değerlerde byte order önemlidir:

little-endian,
big-endian.

Örneğin 32 bit 0x12345678 değeri little-endian bellekte:

78 56 34 12

sırasıyla bulunabilir.

Veri yapılarında gerçek bellek tüketimi yalnız alanların toplamından oluşmayabilir. Hizalama ve dolgulama ek alan oluşturabilir.

Karakter verisi

ASCII 7 bitlik bir karakter kodlamasıdır ve 128 kod noktası tanımlar.

Modern sistemlerde temel karakter standardı Unicode'dur.

Unicode karakterleri tek bir sabit 16 bit değerle sınırlı değildir. Unicode bir kod noktası uzayı tanımlar. Bu kod noktaları farklı kodlama biçimleriyle saklanabilir:

UTF-8,
UTF-16,
UTF-32.

UTF-8 değişken uzunlukludur ve ASCII ile ilk 128 kod noktasında uyumludur.

Bu nedenle:

karakter sayısı != bayt sayısı

olabilir.

Özellikle Unicode metinlerinde indisleme, uzunluk ve kesme işlemlerinde kod noktası ile kullanıcı tarafından algılanan karakter arasındaki fark da önemlidir.

İşaretsiz tamsayı

n bitlik işaretsiz tamsayı:

0 ... 2^n - 1

aralığındadır.

8 bit için:

0 ... 255

İşaretli tamsayı

Modern bilgisayarlarda signed integer için temel yöntem iki'nin tümleyenidir.

n bit signed aralık:

-2^(n-1) ... 2^(n-1)-1

32 bit için:

-2^31 ... 2^31 - 1

İki'nin tümleyeninin avantajları:

tek sıfır gösterimi,
toplama ve çıkarma donanımının sadeleşmesi,
işaret genişletmenin kolay olmasıdır.

Bir'in tümleyeni ve işaretli-genlik tarihsel gösterimlerdir.

BCD

Binary Coded Decimal, her onluk rakamı ayrı ikili kodla temsil eder.

Örneğin:

packed olmayan temel BCD düşüncesinde:

0001 0010 0011

olarak kodlanabilir.

BCD özellikle tam onluk davranışın önemli olduğu belirli finansal ve donanımsal uygulamalarda tarihsel ve pratik öneme sahiptir.

Yüzen nokta sayılar

Gerçel sayıların bilgisayardaki yaygın gösterimi IEEE 754 standardına dayanır.

Binary32:

1 bit  sign
8 bit  exponent
23 bit fraction

Binary64:

1 bit  sign
11 bit exponent
52 bit fraction

Normal bir binary32 sayı:

(-1)^s x 1.f x 2^(e-127)

biçiminde yorumlanır.

Üs iki'nin tümleyeni olarak değil, bias'lı üs olarak tutulur.

IEEE 754 ayrıca:

pozitif ve negatif sıfır,
sonsuzluk,
NaN,
subnormal sayılar

gibi özel değerleri tanımlar.

Yüzen nokta aritmetiği reel sayı aritmetiğinin tam karşılığı değildir. Yuvarlama hataları oluşabilir.

Örneğin birçok ikili yüzen nokta sisteminde:

0.1 + 0.2

matematiksel 0.3 değerinin tam ikili gösterimini üretmez.

Karakter dizisi

Bir karakter dizisi, yani string, bir karakterler dizisidir.

C dilinde klasik gösterim sonlandırıcı sıfır karakterini kullanır:

char text[] = "abc";

bellekte:

'a' 'b' 'c' '\0'

olarak tutulur.

Başka diller:

uzunluğu ayrıca tutabilir,
immutable string kullanabilir,
farklı Unicode kodlamaları uygulayabilir.

Bu nedenle string'in iç gösterimi dile ve çalışma ortamına bağlıdır.

Diziler

Dizi aynı türdeki elemanları ardışık mantıksal indislerle saklar.

A[0]
A[1]
A[2]
...

Bir boyutlu dizi için eleman adresi yaklaşık olarak:

adres(A[i]) =
taban_adresi + i x eleman_boyutu

olduğundan indisle erişim:

O(1)

zamanlıdır.

Dizinin ortasına eleman eklemek veya çıkarmak ise eleman kaydırmayı gerektirebilir:

O(n)

Çok boyutlu diziler

Matris:

A[i][j]

gibi iki boyutlu yapıdır.

Bellekte çoğunlukla doğrusal alana dönüştürülür.

İki yaygın yerleşim:

satır-major,
column-major.

C ailesi dillerde klasik çok boyutlu diziler satır-major yerleşime sahiptir.

Struct

C dilindeki struct, farklı tipte alanları tek kayıt altında birleştirir.

struct Person {
    int id;
    char name[64];
    double score;
};

Bellek boyutu alanların aritmetik toplamından daha büyük olabilir. İşlemcinin hizalama gereksinimleri dolgulama oluşturabilir.

Union

union içindeki alanlar aynı bellek bölgesini paylaşır.

union Value {
    int i;
    float f;
};

Union boyutu genel olarak en büyük üyenin gereksinimine ve hizalamaya göre belirlenir.

Union bellek tasarrufu sağlayabilir ancak aynı bellek bölgesinin farklı tiplerle yorumlanması dilin kurallarına uygun yapılmalıdır.

Bit alanları

C dilinde bit field kullanılarak bazı alanlar bit düzeyinde tanımlanabilir.

Örnek:

struct Flags {
    unsigned ready : 1;
    unsigned mode  : 3;
};

Bit field yerleşiminin bazı ayrıntıları derleyici ve ABI'ye bağlı olabilir.

Taşınabilir protokol veya dosya biçimlerinde açık bit maskeleri çoğu zaman daha öngörülebilir çözüm sağlar.

Ünite 3: Veri Modelleri

Liste

Liste, elemanların belirli sırada tutulduğu doğrusal modeldir.

Temel işlemler:

ekleme,
silme,
arama,
dolaşma,
güncelleme.

Liste dizi veya bağlantılı listeyle gerçekleştirilebilir.

Bağlantılı liste

Bağlantılı listede elemanlar bellekte fiziksel olarak ardışık olmak zorunda değildir.

Her düğüm veri ve bağlantı bilgisi taşır.

Tek yönlü liste:

[veri|next] -> [veri|next] -> [veri|null]

Avantajı belirli konuma erişildikten sonra bağlantının değiştirilmesiyle ekleme ve silmenin yapılabilmesidir.

Dezavantajı indisle rastgele erişimin olmamasıdır.

Ağaç modeli

Ağaç hiyerarşik ilişkileri temsil eder.

Temel kavramlar:

kök,
düğüm,
kenar,
ebeveyn,
çocuk,
kardeş,
yaprak,
alt ağaç,
derinlik,
yükseklik.

Dosya sistemi, sözdizim ağacı ve indeks yapıları ağaç modeline örnektir.

Graf modeli

Graf:

G = (V, E)

biçiminde düğümler ve kenarlar kümesi olarak tanımlanır.

Graf:

yönlü,
yönsüz,
ağırlıklı,
ağırlıksız

olabilir.

Yol ağları, sosyal ilişkiler, iletişim ağları ve bağımlılık grafikleri bu modele uygundur.

Durum makinesi

Durum makinesi bir sistemin:

durumlarını,
girdilerini veya olaylarını,
durum geçişlerini

tanımlar.

Basit gösterim:

Bekliyor --başlat--> Çalışıyor
Çalışıyor --durdur--> Bekliyor
Çalışıyor --hata--> Hata

Durum makineleri:

protokol,
kullanıcı arabirimi,
gömülü sistem,
ayrıştırıcı,
iş akışı

tasarımında kullanılır.

İlişkisel veri modeli

İlişkisel model veriyi tablolar ve bu tablolar arasındaki ilişkiler üzerinden temsil eder.

Bir tablo:

satırlar,
sütunlar,
anahtarlar

üzerinden tanımlanır.

Bu model veri yapısından çok kavramsal ve mantıksal veri modelidir.

Ağ modeli

Tarihsel veri tabanı terminolojisindeki network model, kayıtlar arasında birden çok bağlantıya izin veren veri modelidir.

Günümüzde genel amaçlı veri tabanlarında ilişkisel model daha yaygındır. Graf veri tabanları ise bağlantı yoğun problemlerde farklı bir modern yaklaşım sunar.

Ünite 4: Algoritmik Program Tasarımı

Program tasarımı

Program tasarımı doğrudan kod yazmakla başlamamalıdır.

Genel süreç:

problemi tanımla,
girdileri ve çıktıları belirle,
veri modelini seç,
veri yapısını belirle,
algoritmayı oluştur,
doğruluğunu incele,
karmaşıklığını değerlendir,
kodla,
test et.

Veri yapısı seçimi algoritmadan bağımsız değildir.

Örneğin arama problemi:

sırasız dizide O(n),
sıralı dizide binary search ile O(log n),
dengeli arama ağacında O(log n),
uygun hash tablosunda ortalama O(1)

davranabilir.

Sözde kod

Sözde kod, algoritmayı belirli programlama dilinin sözdizimine bağlamadan ifade eder.

Örnek:

ortalama(A, n):
    toplam <- 0

    her x elemanı için A içinde:
        toplam <- toplam + x

    döndür toplam / n

Sözde kodun amacı çalıştırılabilir kod üretmek değil, algoritmanın mantığını açık hale getirmektir.

Gerçek kod

Gerçek kod:

veri tipleri,
bellek modeli,
hata denetimi,
API kuralları,
dil sözdizimi

gibi ayrıntıları içerir.

İyi sözde kod ile gerçek kod arasındaki geçiş mekanik olmak zorunda değildir. Gerçekleştirim ayrıntıları algoritmanın performansını değiştirebilir.

Akış şemaları

Akış şemaları kontrol akışını görsel olarak ifade eder.

Temel öğeler:

başlangıç/bitiş,
işlem,
karar,
giriş/çıkış,
akış oku.

Küçük algoritmalar için anlaşılır olabilir. Büyük yazılımlarda sözde kod, durum diyagramı, UML veya doğrudan kod daha uygun olabilir.

Koşullu dallanma

Temel yapı:

eğer koşul:
    işlem A
değilse:
    işlem B

Programlama karşılığı:

if / else

biçimindedir.

Döngü

Bir işlemin koşula bağlı tekrarıdır.

Yaygın modeller:

for
while
do-while

Her döngüde:

başlangıç,
devam koşulu,
durum güncellemesi

açık olmalıdır.

İç içe döngüler

İç içe döngüler karmaşıklığı doğrudan etkileyebilir.

Örneğin:

for i = 1..n
    for j = 1..n
        işlem

toplam yaklaşık:

n x n = n^2

işlem yapar.

Bu nedenle karmaşıklık:

O(n^2)

olur.

İkinci derece denklemin kökleri

Denklem:

ax^2 + bx + c = 0

Diskriminant:

D = b^2 - 4ac

a != 0 için:

D > 0: iki reel kök,
D = 0: tek çift katlı reel kök,
D < 0: karmaşık eşlenik kökler

bulunur.

Algoritma yalnız formülü uygulamadan önce a = 0 durumunu da denetlemelidir.

Aritmetik ortalama

n eleman için:

ortalama =
(x1 + x2 + ... + xn) / n

Bütün elemanların okunması gerektiğinden zaman karmaşıklığı:

Theta(n)

ek alan gereksinimi ise giriş dışında:

Theta(1)

olabilir.

En küçük elemanı bulma

Bir dizide minimum bulmak için:

min <- A[0]

A[1..n-1] üzerinde:
    eğer A[i] < min:
        min <- A[i]

algoritması yeterlidir.

Karşılaştırma sayısı:

n - 1

olur.

Dolayısıyla:

Theta(n)

zamanlıdır.

Ünite 5: Zaman ve Alan Karmaşıklığı

Algoritma analizi

Algoritma analizi belirli makinenin saniye cinsinden süresinden çok, giriş büyüklüğü arttıkça kaynak kullanımının nasıl büyüdüğünü inceler.

n çoğunlukla giriş büyüklüğüdür.

Örneğin:

dizide eleman sayısı,
grafta düğüm veya kenar sayısı,
sayıdaki bit sayısı

olabilir.

Çalışma süresi

Bir algoritmanın tam işlem sayısı:

T(n)

ile gösterilebilir.

Örneğin:

T(n) = 3n + 5

ise büyük n için doğrusal terim baskındır.

Asimptotik olarak:

Theta(n)

davranışı gösterir.

Büyük O

O(g(n)) asimptotik üst sınır ifade eder.

Bir algoritma:

T(n) <= c g(n)

koşulunu yeterince büyük n için sağlıyorsa:

T(n) = O(g(n))

denebilir.

Büyük O'nun tek başına "tam karmaşıklık" olarak kullanılması yaygındır ancak matematiksel olarak üst sınırdır.

Büyük Omega

Omega(g(n)) asimptotik alt sınırdır.

Büyük Theta

Theta(g(n)) hem alt hem üst sınırın aynı büyüme sınıfında olduğunu gösterir.

Bir algoritmanın büyüme hızını daha kesin ifade etmek için çoğu zaman Theta kullanılır.

Yaygın büyüme sınıfları

Karmaşıklık: O(1); Örnek: Dizi indis erişimi
Karmaşıklık: O(log n); Örnek: Binary search
Karmaşıklık: O(n); Örnek: Doğrusal tarama
Karmaşıklık: O(n log n); Örnek: Merge sort
Karmaşıklık: O(n^2); Örnek: Basit çift döngüler
Karmaşıklık: O(n^3); Örnek: Klasik bazı matris işlemleri
Karmaşıklık: O(2^n); Örnek: Bazı alt küme aramaları
Karmaşıklık: O(n!); Örnek: Tüm permütasyonların denenmesi

Girdi büyüdükçe düşük dereceli büyüme sınıfı genellikle büyük avantaj sağlar.

En iyi, ortalama ve en kötü durum

Algoritma maliyeti veri düzenine göre değişebilir.

Örneğin linear search:

en iyi: ilk elemanda bulur, O(1),
en kötü: bütün diziyi tarar, O(n),
ortalama: veri dağılımına bağlı olarak Theta(n).

Quicksort:

beklenen/ortalama: O(n log n),
kötü pivot seçimlerinde: O(n^2).

Amortize analiz

Bazı işlemler ara sıra pahalı olsa da uzun işlem dizisinin ortalama maliyeti düşük olabilir.

Dinamik dizide kapasite büyütme örneği:

çoğu ekleme O(1),
zaman zaman bütün dizi kopyalanır.

Geometrik kapasite artışıyla append işleminin amortize maliyeti:

O(1)

olabilir.

Alan karmaşıklığı

Algoritmanın kullandığı ek belleğin büyümesini ifade eder.

Örnek:

minimum bulma: O(1) ek alan,
merge sort: klasik dizi gerçekleştiriminde O(n) ek alan,
recursive DFS: çağrı yığını nedeniyle O(V) düzeyine çıkabilir.

Kod belleği

Programın makine kodu da bellek kullanır. Ancak algoritma analizinde çoğunlukla giriş boyutuna göre büyüyen veri alanı daha önemlidir.

Çağrı yığını

Her fonksiyon çağrısı:

dönüş adresi,
parametreler,
yerel değişkenler,
saklanan yazmaçlar

için stack frame oluşturabilir.

Özyinelemeli algoritmalarda çağrı derinliği alan karmaşıklığını etkiler.

Örneğin dengeli binary tree üzerinde recursive traversal:

O(h)

çağrı yığını kullanır.

h ağacın yüksekliğidir.

Başarım ölçümü ile analiz arasındaki fark

Teorik olarak O(n log n) algoritma küçük veri için O(n^2) algoritmadan daha yavaş olabilir.

Sabit çarpanlar, önbellek davranışı ve veri özellikleri etkilidir.

Bu nedenle mühendislikte:

Asimptotik analiz + gerçek ölçüm

birlikte kullanılmalıdır.

Ünite 6: Bağlantılı Listeler

Bağlantılı liste modeli

Bağlantılı listede her düğüm:

veri,
bir veya daha fazla bağlantı

içerir.

Tek yönlü düğüm:

+------+------+
| veri | next |
+------+------+

Liste:

head
 ↓
[A|•] -> [B|•] -> [C|null]

biçimindedir.

Dizi ile bağlantılı liste farkı

İşlem: İndisle erişim; Dizi: O(1); Tek yönlü bağlantılı liste: O(n)
İşlem: Baştan ekleme; Dizi: O(n) olabilir; Tek yönlü bağlantılı liste: O(1)
İşlem: Bilinen düğümden sonra ekleme; Dizi: O(n) kaydırma; Tek yönlü bağlantılı liste: O(1)
İşlem: Arama; Dizi: O(n); Tek yönlü bağlantılı liste: O(n)
İşlem: Bellek yerleşimi; Dizi: Ardışık; Tek yönlü bağlantılı liste: Dağınık olabilir
İşlem: Ek bağlantı belleği; Dizi: Yok; Tek yönlü bağlantılı liste: Vardır

Bağlantılı liste her durumda diziden üstün değildir.

Modern işlemcilerde dizilerin ardışık bellek yerleşimi önbellek açısından önemli avantaj sağlar.

Tek yönlü bağlantılı liste

Her düğüm yalnız sonraki düğümü gösterir.

head -> A -> B -> C -> null

Sondan başa doğrudan hareket edilemez.

Çift yönlü bağlantılı liste

Her düğüm:

önceki,
sonraki

düğümü gösterir.

null <- A <-> B <-> C -> null

Avantajı iki yönde dolaşma ve bilinen düğümün silinmesinde bağlantı düzenlemesinin kolay olmasıdır.

Karşılığında her düğüm ek işaretçi alanı kullanır.

Çevrimsel liste

Son düğüm tekrar ilk düğüme bağlanır.

A -> B -> C
^         |
|_________|

Round-robin zamanlama gibi döngüsel dolaşım gereken problemlerde kullanılabilir.

Dinamik bellek

C dilinde düğümler:

malloc()

ile dinamik ayrılabilir ve:

free()

ile serbest bırakılabilir.

Temel hata sınıfları:

memory leak,
dangling pointer,
double free,
use-after-free.

Yönetilen dillerde garbage collection birçok manuel serbest bırakma sorununu azaltır ancak veri yapısının mantıksal bağlantıları yine doğru yönetilmelidir.

Listeye ekleme

Başa ekleme:

yeni.next <- head
head <- yeni

işlemleriyle yapılır.

Zaman:

O(1)

Sona ekleme yalnız head tutuluyorsa:

O(n)

olabilir.

Ayrıca tail tutulursa:

O(1)

olabilir.

Listeleme

Bütün düğümler:

p <- head

while p != null:
    işle(p)
    p <- p.next

ile dolaşılır.

Karmaşıklık:

Theta(n)

Arama

Sıralı olmayan listede arama:

O(n)

zamanlıdır.

Bağlantılı listenin sıralı tutulması karşılaştırmayı bazı durumlarda erken bitirebilir ancak rastgele erişim olmadığı için binary search avantajı elde edilmez.

Silme

Tek yönlü listede bir düğümü silmek için genellikle önceki düğümün bilinmesi gerekir.

prev.next <- current.next

Ardından dinamik bellek kullanılıyorsa current serbest bırakılır.

Düğüm aranarak bulunacaksa toplam maliyet:

O(n)

olabilir.

Çift yönlü listede silme

Düğümün adresi biliniyorsa:

node.prev.next <- node.next
node.next.prev <- node.prev

ile O(1) bağlantı güncellemesi yapılabilir.

Baş ve son durumları ayrıca ele alınmalıdır.

Sentinel düğümler

Özel baş veya son sentinel düğümleri sınır durumlarını azaltabilir.

Örneğin:

HEAD <-> A <-> B <-> TAIL

Bu yaklaşım ekleme ve silme kodunu sadeleştirebilir.

Ünite 7: Ağaç Veri Modeli

Ağaç kavramı

Ağaç hiyerarşik ve döngüsüz bir yapıdır.

Temel kavramlar:

root,
parent,
child,
sibling,
leaf,
subtree,
depth,
height.

Bir ağacın n düğümü varsa bağlı bir ağaçta:

n - 1

kenar bulunur.

Düğüm derecesi

Bir düğümün çocuk sayısına düğüm derecesi denebilir.

Ağacın derecesi, düğümler arasındaki en yüksek çocuk sayısıyla ilişkilidir.

İkili ağaçta her düğümün en fazla iki çocuğu vardır.

Ağaçların bellekte gösterimi

Genel bir ağaç çeşitli biçimlerde tutulabilir:

her çocuk için ayrı bağlantı,
çocuk listesi,
ilk çocuk/sonraki kardeş,
indis bağıntılı dizi.

İlk çocuk ve sonraki kardeş

Genel ağaç iki bağlantıyla tutulabilir:

node.firstChild
node.nextSibling

Bu yöntem değişken sayıda çocuk için sabit sayıda bağlantı alanı kullanır.

Dizi tabanlı ağaç

Tam veya tama yakın ağaçlarda düğümler dizi üzerinde verimli tutulabilir.

İkili öbek için sıfır tabanlı indislerle:

parent(i) = floor((i - 1) / 2)
left(i)   = 2i + 1
right(i)  = 2i + 2

Bu yöntem seyrek ağaçlarda büyük boşluklar oluşturabilir.

Dengeli ağaç

AVL ağacındaki dengesizliğin dönüş işlemiyle giderilmesi ve dengeli yapının yeniden oluşması — AVL dönüşü

Bir arama ağacının yüksekliği performans için kritiktir.

Ağaç tek yönde büyürse:

h ≈ n

olabilir ve arama:

O(n)

davranışına düşer.

Dengeli yapılarda hedef:

h = O(log n)

olmasıdır.

AVL ağacı

AVL ağacında her düğüm için sol ve sağ alt ağaç yüksekliği farkı en fazla 1'dir.

Denge faktörü:

BF = height(left) - height(right)

Geçerli değerler:

-1, 0, +1

Ekleme veya silme dengeyi bozarsa rotasyon yapılır.

Temel rotasyonlar:

sağ rotasyon,
sol rotasyon,
sol-sağ,
sağ-sol.

AVL ağacında arama, ekleme ve silme:

O(log n)

zamanında yapılabilir.

Öbek

Öbek tamamlanmış ikili ağaca dayanan öncelik yapısıdır.

Max-öbek:

parent >= children

Min-öbek:

parent <= children

Öbek bütün elemanları tamamen sıralı tutmaz. Yalnız parent-child öncelik özelliğini korur.

Önemli karmaşıklıklar:

minimum/maksimumu görme: O(1),
ekleme: O(log n),
kökü çıkarma: O(log n),
öbek oluşturma: O(n).

Öbek, priority kuyruk gerçekleştiriminde yaygın olarak kullanılır.

Trie

Trie karakter veya simge dizilerini ortak önekler üzerinden saklar.

Örnek:

Kelime arama maliyeti veri sayısından çok anahtar uzunluğuyla ilişkilidir.

Yaklaşık:

O(m)

m, anahtar uzunluğudur.

Sözlük, otomatik tamamlama ve routing benzeri önek aramalarında kullanılabilir.

Huffman kodlama

Huffman algoritması simge frekanslarından önek kodu üretir.

Temel süreç:

her simgeyi frekansıyla min-öbeğe koy,
en küçük iki frekansı çıkar,
bunları yeni ortak düğüm altında birleştir,
toplam frekansla öbeğe geri koy,
tek kök kalana kadar sürdür.

Üretilen kod prefix-free'dir. Hiçbir kod sözcüğü başka kod sözcüğünün öneki değildir.

Bu sayede ayırıcı kullanmadan bit dizisi çözülebilir.

Shannon-Fano

Shannon-Fano da simge olasılıklarına göre önek kod üretir.

Simgeler olasılıklarına göre sıralanır ve toplam olasılıkları birbirine yakın iki gruba bölünür.

Huffman ile aynı değildir.

Huffman, sembol bazlı ikili prefix kodları bağlamında optimal kod ağacı üretir. Shannon-Fano her zaman Huffman kadar iyi sonuç vermeyebilir.

Ünite 8: İkili Ağaçlar

İkili ağaç

İkili ağaçta her düğümün en fazla:

sol çocuk,
sağ çocuk

olmak üzere iki çocuğu vardır.

Tam, dolu ve dengeli ağaç

Terimler kaynaklara göre farklı kullanılabildiği için açık tanım önemlidir.

Full binary tree: Her düğümün ya sıfır ya iki çocuğu vardır.

Complete binary tree: Son seviye dışında seviyeler doludur; son seviye soldan sağa doldurulur.

Perfect binary tree: Bütün iç düğümlerin iki çocuğu vardır ve bütün yapraklar aynı düzeydedir.

Balanced tree: Yüksekliğin O(log n) düzeyinde tutulduğu veya belirli denge koşulunu sağlayan ağaçtır.

Dolaşma

Üç klasik depth-first traversal:

Preorder

Root
Left
Right

Inorder

Left
Root
Right

Postorder

Left
Right
Root

Preorder

preorder(node):
    eğer node = null:
        dön

    işle(node)
    preorder(node.left)
    preorder(node.right)

Inorder

inorder(node):
    eğer node = null:
        dön

    inorder(node.left)
    işle(node)
    inorder(node.right)

Binary search tree üzerinde inorder dolaşma anahtarları sıralı üretir.

Postorder

postorder(node):
    eğer node = null:
        dön

    postorder(node.left)
    postorder(node.right)
    işle(node)

Alt ağaçların önce işlenmesi gereken silme veya ifade değerlendirme işlemlerinde yararlı olabilir.

Level-order

Düğümleri seviye seviye dolaşır.

Kuyruk kullanılır:

enqueue(root)

while queue boş değil:
    node <- dequeue()
    işle(node)

    varsa node.left enqueue
    varsa node.right enqueue

Bu, ağaç üzerindeki BFS'dir.

Infix, prefix ve postfix

İfade ağacı:

için:

Infix

(a + b) * c

Prefix

* + a b c

Postfix

a b + c *

Prefix Polonyalı gösterim, postfix ters Polonyalı gösterim olarak da bilinir.

Binary Search Tree

BST için temel kural:

sol alt ağaç < düğüm < sağ alt ağaç

eşit anahtarların politikası uygulama tarafından ayrıca belirlenir.

Arama:

search(node, key):
    while node != null:
        eğer key = node.key:
            döndür node
        eğer key < node.key:
            node <- node.left
        değilse:
            node <- node.right

    döndür null

Maliyet:

O(h)

h ağacın yüksekliğidir.

Dengeli durumda:

O(log n)

kötü durumda:

O(n)

BST ekleme

Aramayla benzer biçimde uygun boş yaprağa ilerlenir.

Maliyet:

O(h)

BST silme

Üç durum vardır.

Yaprak düğüm: Doğrudan çıkarılır.

Tek çocuk: Çocuk düğüm silinen düğümün yerine bağlanır.

İki çocuk: Genellikle inorder successor veya predecessor bulunur, anahtar aktarılır ve daha basit silme durumuna indirgenir.

Dengeli arama ağaçları

AVL dışında:

Red-Black Tree,
B-tree,
B+ tree

gibi dengeli yapılar da vardır.

Red-Black Tree birçok standart kütüphane ve çekirdek veri yapısında kullanılmıştır.

B-tree ailesi yüksek fan-out nedeniyle disk ve veri tabanı indekslerinde önemlidir.

Ünite 9: Yığın ve Kuyruk

Yığın

Stack:

LIFO
Last In, First Out

davranışına sahiptir.

Temel işlemler:

push,
pop,
peek/top,
isEmpty.

Örnek:

push A
push B
push C

pop -> C
pop -> B

Yığın kullanım alanları

fonksiyon çağrıları,
expression evaluation,
undo,
ayrıştırıcı,
DFS,
backtracking.

Dizi üzerinde yığın

top = 0

push(x):
    A[top] = x
    top++

pop():
    top--
    return A[top]

Sabit kapasiteli dizide overflow denetlenmelidir.

Dinamik dizide kapasite büyütülebilir.

Push ve pop:

O(1)

amortize veya doğrudan zamanlı olabilir.

Bağlantılı liste üzerinde yığın

Başa ekleme ve baştan silme kullanılır.

top -> A -> B -> C

push ve pop:

O(1)

zamanlıdır.

Kuyruk

Kuyruk:

FIFO
First In, First Out

davranışına sahiptir.

Temel işlemler:

enqueue,
dequeue,
front/peek,
isEmpty.

Kaydırmalı dizi kuyruğu

Her dequeue işleminde bütün elemanları kaydırmak:

O(n)

maliyet oluşturabilir.

Bu nedenle doğrudan tercih edilmez.

Çevrimsel kuyruk

Dizinin sonundan sonra başına dönülür.

next(i) = (i + 1) mod capacity

head ve tail indisleri tutulur.

Enqueue/dequeue:

O(1)

zamanlıdır.

Bağlantılı liste kuyruğu

Hem head hem tail tutulur.

Enqueue sona, dequeue başa yapılır.

İki işlem de:

O(1)

olabilir.

Deque

Double-ended kuyruk iki uçtan da ekleme ve çıkarma sağlar.

Temel işlemler:

push_front,
push_back,
pop_front,
pop_back.

Sliding window ve bazı graph algoritmalarında yararlıdır.

Öncelikli kuyruk

Priority kuyruk FIFO sırasından farklıdır. Eleman seçimi öncelik değerine göre yapılır.

Yaygın gerçekleştirim:

binary heap

Min-priority kuyruk:

minimum: O(1),
insert: O(log n),
extract-min: O(log n).

Dijkstra ve Prim gibi algoritmalar öncelikli kuyruktan yararlanabilir.

Ünite 10: Sıralama Algoritmaları

Sıralama

Sıralama, elemanların belirli anahtara göre düzenlenmesidir.

Anahtar:

sayı,
metin,
tarih,
bileşik alan

olabilir.

Örneğin:

öğrenci -> numara
personel -> soyad
dosya -> tarih

İç ve dış sıralama

İç sıralama: Veri ana bellekte işlenebilir.

Dış sıralama: Veri ana belleğe sığmaz ve disk/SSD gibi dış saklama katmanları gerekir.

Dış sıralamada I/O maliyeti CPU karşılaştırma sayısından daha önemli olabilir.

External merge sort bu bağlamda temel algoritmadır.

Kararlı sıralama

Stable sort, eşit anahtarlı elemanların göreli sırasını korur.

Örneğin:

(Ali, 80)
(Ayse, 80)

not alanına göre sıralandığında önceki göreli sıra korunuyorsa algoritma kararlıdır.

Yerinde sıralama

In-place algoritma büyük ek veri alanı kullanmadan diziyi kendi üzerinde düzenler.

Kesin tanım kaynaklara göre değişebilse de genel olarak ek alan:

O(1)

veya çok sınırlı kabul edilir.

Insertion sort

Dizinin sol kısmını sıralı tutar ve yeni elemanı uygun konuma sokar.

for i = 1..n-1:
    x = A[i]
    j = i - 1

    while j >= 0 and A[j] > x:
        A[j+1] = A[j]
        j--

    A[j+1] = x

Karmaşıklık:

en iyi: O(n),
ortalama: O(n^2),
en kötü: O(n^2).

Küçük veya büyük ölçüde sıralı dizilerde etkilidir.

Kararlıdır ve yerinde gerçekleştirilebilir.

Selection sort

Her turda kalan bölümün en küçük elemanını seçer.

for i = 0..n-2:
    min = i

    for j = i+1..n-1:
        if A[j] < A[min]:
            min = j

    swap(A[i], A[min])

Karşılaştırma sayısı:

Theta(n^2)

olur.

Yer değiştirme sayısı görece azdır.

Klasik gerçekleştirim kararlı değildir.

Bubble sort

Komşu elemanları karşılaştırıp ters sıradaysa değiştirir.

repeat:
    swapped = false

    for i:
        if A[i] > A[i+1]:
            swap
            swapped = true
until not swapped

Ortalama ve kötü durumda:

O(n^2)

olur.

Eğitim açısından basittir fakat genel amaçlı büyük veri sıralamasında tercih edilmez.

Merge sort

Böl ve yönet yaklaşımını kullanır.

mergeSort(A):
    eğer |A| <= 1:
        dön

    A'yı ikiye böl
    mergeSort(sol)
    mergeSort(sağ)
    merge(sol, sağ)

Zaman:

Theta(n log n)

en iyi, ortalama ve kötü durumda aynıdır.

Klasik dizi gerçekleştiriminde ek alan:

O(n)

gerektirir.

Kararlı yapılabilir.

Bağlantılı listeler ve dış sıralama için güçlü bir seçenektir.

Öbek sort

Önce max-öbek oluşturur. Kök en büyük elemandır.

Her turda:

kökü son elemanla değiştir,
öbek boyutunu azalt,
öbek özelliğini yeniden kur.

Zaman:

O(n log n)

Ek alan:

O(1)

olabilir.

Klasik öbek sort kararlı değildir.

Quicksort

Bir pivot seçilir ve dizi pivot etrafında bölünür.

quicksort(A):
    pivot seç
    A'yı pivot etrafında partition et
    solu sırala
    sağı sırala

Beklenen zaman:

O(n log n)

Kötü durum:

O(n^2)

Random pivot veya iyi pivot stratejileri kötü durum olasılığını azaltır.

Quicksort pratikte iyi önbellek davranışı ve düşük sabit maliyet nedeniyle çok etkilidir.

Sıralama algoritmalarının karşılaştırılması

Algoritma: Insertion; En iyi: O(n); Ortalama: O(n^2); En kötü: O(n^2); Ek alan: O(1); Kararlı: Evet
Algoritma: Selection; En iyi: O(n^2); Ortalama: O(n^2); En kötü: O(n^2); Ek alan: O(1); Kararlı: Genellikle hayır
Algoritma: Bubble; En iyi: O(n) optimize; Ortalama: O(n^2); En kötü: O(n^2); Ek alan: O(1); Kararlı: Evet
Algoritma: Merge; En iyi: O(n log n); Ortalama: O(n log n); En kötü: O(n log n); Ek alan: O(n) dizi; Kararlı: Evet
Algoritma: Öbek; En iyi: O(n log n); Ortalama: O(n log n); En kötü: O(n log n); Ek alan: O(1); Kararlı: Hayır
Algoritma: Quick; En iyi: O(n log n); Ortalama: O(n log n); En kötü: O(n^2); Ek alan: çağrı yığını; Kararlı: Genellikle hayır

Karşılaştırma tabanlı genel sıralama için karar ağacı modeli altında alt sınır:

Omega(n log n)

olarak bilinir.

Counting sort ve radix sort gibi karşılaştırmasız algoritmalar belirli anahtar varsayımlarında bu sınırın dışında davranabilir.

Ünite 11: Arama ve Hash Tabloları

Arama problemi

Amaç belirli anahtara sahip kaydı veri kümesinde bulmaktır.

Verinin yapısı arama algoritmasını belirler.

Doğrusal arama

Sırasız dizide:

for i = 0..n-1:
    if A[i] = key:
        return i

return NOT_FOUND

En iyi:

O(1)

En kötü:

O(n)

Ortalama:

Theta(n)

Binary search

Önkoşul:

Veri arama anahtarına göre sıralı olmalıdır.

Algoritma:

left = 0
right = n - 1

while left <= right:
    mid = left + (right - left) / 2

    if A[mid] == key:
        return mid
    else if A[mid] < key:
        left = mid + 1
    else:
        right = mid - 1

Her adımda arama alanı yaklaşık yarıya iner.

Zaman:

O(log n)

Binary search tree üzerinde arama

BST araması:

O(h)

zamanlıdır.

Dengeli ağaçta:

O(log n)

kötü biçimde dengesiz ağaçta:

O(n)

olabilir.

Hash fonksiyonu

Hash fonksiyonu anahtarı tablo indisine dönüştürür.

h(key) -> [0, m-1]

Basit tamsayı örneği:

h(k) = k mod m

İyi hash fonksiyonu anahtarları tabloya dengeli dağıtmaya çalışır.

Hash fonksiyonu ile kriptografik hash aynı gereksinimlere sahip değildir.

Veri yapısındaki hash fonksiyonu öncelikle hızlı ve dengeli dağılımlı olmalıdır.

Hash tablosu

Hash tablosunda ortalama durumda:

arama,
ekleme,
silme

işlemleri:

O(1)

olabilir.

Kötü durumda çok sayıda çakışma oluşursa:

O(n)

davranışı görülebilir.

Çakışma

İki farklı anahtar aynı tablo konumuna eşlenirse çakışma oluşur.

h(k1) = h(k2)

çakışmanın yanlış hash anlamına geldiğini göstermez. Sonlu tabloya daha geniş anahtar uzayından eşleme yapıldığında çakışma doğal olarak mümkündür.

Separate chaining

Her bucket ayrı liste veya benzeri yapı tutar.

table[3] -> A -> B -> C

Ortalama performans load factor'a ve hash dağılımına bağlıdır.

Open addressing

Bütün kayıtlar tablonun kendi hücrelerinde tutulur.

Çakışmada başka hücre aranır.

Yöntemler:

linear probing,
quadratic probing,
double hashing.

Linear probing

h_i(k) = (h(k) + i) mod m

Basittir ve önbellek açısından iyi olabilir.

Dezavantajı primary clustering oluşturabilmesidir.

Quadratic probing

Deneme uzaklığı karesel büyür.

h_i(k) =
(h(k) + c1 i + c2 i^2) mod m

Primary clustering etkisini azaltabilir.

Double hashing

İkinci hash fonksiyonu adım büyüklüğünü belirler.

h_i(k) =
(h1(k) + i h2(k)) mod m

İyi parametre seçimiyle daha dengeli probe dizileri oluşturur.

Yük faktörü

Hash tablosu için:

alpha = n / m

n: eleman sayısı,
m: bucket veya hücre sayısıdır.

Load factor büyüdükçe çakışma ve probe maliyeti artabilir.

Open addressing'de tablo doluluğunun kontrol altında tutulması özellikle önemlidir.

Rehash

Tablo belirli yük oranını aşınca:

daha büyük tablo oluşturulur,
bütün anahtarlar yeni kapasiteye göre yeniden hash edilir.

Bu işlem tek seferde O(n) maliyetli olsa da geometrik büyüme stratejisinde uzun vadeli ekleme maliyeti amortize olarak düşük kalabilir.

Ünite 12: Graflar

Graf modeli

Graf:

G = (V, E)

olarak tanımlanır.

V: düğümler,
E: kenarlar.

Örnek kullanım alanları:

yol ve rota sistemleri,
bilgisayar ağları,
sosyal ağlar,
bağımlılık analizi,
görev planlama,
devreler,
moleküler yapılar.

Yönsüz graf

Kenarın yönü yoktur.

{u, v}

ilişkisi u ile v arasında iki yönlü bağlantıyı ifade eder.

Yönlü graf

Kenar yön taşır.

(u, v)

u düğümünden v düğümüne bağlantıdır.

Ağırlıklı graf

Kenarlarda maliyet bulunur.

(u, v, w)

Buradaki w:

mesafe,
süre,
ücret,
kapasite,
risk

gibi değeri temsil edebilir.

Derece

Yönsüz grafta düğümün degree değeri bağlı kenar sayısıdır.

Yönlü grafta:

indegree,
outdegree

ayrı hesaplanır.

Yol

Bir düğümden başka düğüme ardışık kenarlar üzerinden gidilebilen düğüm dizisidir.

Yol maliyeti ağırlıklı grafta kenar ağırlıklarının toplamı olabilir.

Çevrim

Başlangıç düğümüne tekrar dönen yol çevrim oluşturabilir.

Çevrimsiz yönlü graf:

DAG
Directed Acyclic Graph

olarak adlandırılır.

DAG:

görev bağımlılığı,
derleme sırası,
veri işleme hattı

gibi problemlerde önemlidir.

Komşuluk matrisi

V düğümlü graf için:

V x V

matris kullanılır.

Yönsüz ağırlıksız grafta:

A[i][j] = 1

ise kenar vardır.

Alan karmaşıklığı:

O(V^2)

Yoğun graflarda uygundur.

Kenar varlığına bakmak:

O(1)

olabilir.

Komşuluk listesi

Her düğüm komşularının listesini tutar.

Alan:

O(V + E)

olur.

Seyrek graflarda daha verimlidir.

Kenar listesi

Bütün kenarlar:

(u, v, w)

kayıtları halinde tutulur.

Kruskal gibi kenar odaklı algoritmalarda doğal gösterimdir.

Bitişiklik matrisi

Incidence matrix düğümler ile kenarların ilişkisini gösterir.

Boyut:

V x E

olabilir.

Genel graph algoritmalarında adjacency list kadar yaygın değildir ancak graf kuramında yararlıdır.

DFS

Depth-First Search mümkün olduğunca derine gider.

Recursive gösterim:

DFS(u):
    visited[u] = true

    her v komşusu için:
        eğer visited[v] değil:
            DFS(v)

Zaman:

O(V + E)

komşuluk listesi kullanıldığında.

Kullanım alanları:

bağlı bileşen,
çevrim bulma,
topological sort,
yol araştırma.

BFS

Breadth-First Search düğümleri seviye seviye dolaşır.

Kuyruk kullanır.

BFS(s):
    visited[s] = true
    enqueue(s)

    while queue boş değil:
        u = dequeue()

        her v komşusu için:
            eğer visited[v] değil:
                visited[v] = true
                enqueue(v)

Zaman:

O(V + E)

Ağırlıksız graf için başlangıçtan en az kenarlı yolları bulur.

DFS ve BFS karşılaştırması

Özellik: Temel yapı; DFS: Stack/özyineleme; BFS: Kuyruk
Özellik: Dolaşım; DFS: Derinlik; BFS: Seviye
Özellik: Ağırlıksız en kısa yol; DFS: Doğrudan garanti yok; BFS: Evet
Özellik: Topological sort; DFS: Uygun; BFS: Kahn yaklaşımıyla BFS de kullanılabilir
Özellik: Bellek kullanımı; DFS: Yapıya bağlı; BFS: Geniş graflarda yüksek olabilir

Greedy yaklaşımı

Greedy algoritma her adımda yerel olarak en uygun görünen seçimi yapar.

Her problemde global optimum garanti etmez.

Doğru greedy algoritma için problemin gerekli yapısal özelliklere sahip olduğu gösterilmelidir.

Örnekler:

Kruskal,
Prim,
Dijkstra'nın negatif olmayan ağırlıklı sürümü,
Huffman.

Dijkstra algoritması

Tek kaynaktan en kısa yolları bulur.

Önkoşul:

Kenar ağırlıkları negatif olmamalıdır.

Temel yapı:

dist[source] = 0
diğer dist = sonsuz

priority queue'ya source ekle

while queue boş değil:
    u = en küçük dist

    her (u,v,w) için:
        eğer dist[u] + w < dist[v]:
            dist[v] = dist[u] + w
            parent[v] = u

Binary öbek ve adjacency list ile tipik karmaşıklık:

O((V + E) log V)

olarak ifade edilebilir.

Negatif kenarlar varsa Bellman-Ford gibi başka algoritmalar gerekir.

Minimum spanning tree

Bağlı, yönsüz, ağırlıklı grafta bütün düğümleri bağlayan ve toplam kenar ağırlığı en küçük olan spanning tree aranır.

İki temel algoritma:

Kruskal,
Prim.

Kruskal algoritması

Kenarları ağırlığa göre sıralar.

kenarları sırala

her kenar (u,v):
    eğer u ve v farklı bileşendeyse:
        kenarı seç
        bileşenleri birleştir

Çevrim denetimi için Disjoint Set Union kullanılır.

Karmaşıklık çoğunlukla sıralama tarafından belirlenir:

O(E log E)

Disjoint Set Union

DSU birbirinden ayrık kümeleri yönetir.

İşlemler:

find,
union.

Path compression ve union by rank/size ile amortize maliyet çok düşüktür:

O(alpha(n))

Buradaki alpha, ters Ackermann fonksiyonudur ve pratik boyutlarda çok yavaş büyür.

Prim algoritması

Bir düğümden başlayarak mevcut ağaca en ucuz bağlantıyı ekler.

Priority kuyruk ile:

O(E log V)

düzeyinde gerçekleştirilebilir.

Kruskal kenar merkezli, Prim büyüyen ağaç merkezli düşünülebilir.

Graf renklendirme

Düğüm renklendirmede komşu düğümlere farklı renkler atanır.

Amaç çoğu zaman renk sayısını en aza indirmektir.

Genel graph coloring problemi zor bir optimizasyon problemidir. Basit greedy coloring hızlı çözüm sağlar ancak minimum renk sayısını garanti etmez.

Kullanım alanları:

zamanlama,
register bellek ayırma,
frekans atama.

Topological sort

DAG üzerindeki düğümleri:

u -> v

kenarı varsa u, v'den önce gelecek biçimde sıralar.

Kullanım alanları:

bağımlılık çözme,
ders önkoşulları,
derleme sistemi,
iş akışı.

DFS veya indegree tabanlı Kahn algoritmasıyla:

O(V + E)

zamanda yapılabilir.

Ünite 13: Algoritma Tasarım Paradigmaları ve Zorluk Sınırları

Veri yapısı seçimi ile algoritma tasarım tekniği ayrı kararlardır. Aynı veri modeli farklı problem çözme paradigmalarıyla işlenebilir; doğru yaklaşım problemin alt problem yapısına, optimal alt yapıya ve girdi özelliklerine bağlıdır.

Böl ve yönet

Böl ve yönet yaklaşımında problem daha küçük bağımsız alt problemlere ayrılır, alt problemler çözülür ve sonuçlar birleştirilir.

problem
  ↓ böl
alt problemler
  ↓ çöz
kısmi sonuçlar
  ↓ birleştir
sonuç

Merge sort klasik örnektir. Birçok böl-ve-yönet algoritmasının maliyeti recurrence ile ifade edilir:

T(n) = a T(n/b) + f(n)

Bu ifade yalnız Big-O sonucu vermek için değil, işin hangi katmanda çoğaldığını görmek için kullanılır.

Dinamik programlama

Aynı alt problemler tekrar tekrar çözülüyorsa sonuçlar saklanabilir. Dinamik programlamanın iki temel koşulu örtüşen alt problemler ve optimal alt yapıdır.

Top-down memoization ve bottom-up tablo yaklaşımı aynı bağıntıyı farklı yürütme düzeniyle çözebilir. Ancak her recursive algoritma dinamik programlamaya uygun değildir; alt problemlerin bağımlılık yapısı açıkça kurulmalıdır.

Açgözlü yaklaşım

Greedy algoritma her adımda yerel olarak en iyi görünen seçimi yapar. Bu seçimin global optimum verdiği ayrıca kanıtlanmalıdır. "Her adımda en büyük değeri seçmek" tek başına doğruluk gerekçesi değildir.

Exchange argument, cut property veya problem özelindeki invariant'lar greedy doğruluğunu göstermek için kullanılabilir.

Amortize analiz

Tek bir işlem pahalı olsa bile uzun bir işlem dizisinin ortalama maliyeti düşük olabilir. Dinamik dizi kapasitesinin geometrik büyütülmesi tipik örnektir.

1, 2, 4, 8, 16, ...

Bazı append işlemleri yeniden ayırma nedeniyle O(n) maliyetli olabilir; buna rağmen n eklemenin toplam maliyeti O(n) mertebesinde kalır ve amortize işlem maliyeti O(1) olur.

Bu sonuç olasılıksal "ortalama durum" ile aynı değildir. Amortize analiz belirli bir işlem dizisi üzerindeki toplam maliyeti sınırlar.

Rastgele algoritmalar

Randomized algoritmalar rastgele seçimi algoritmanın parçası yapar. Randomized quicksort'ta pivot seçiminin rastgeleleştirilmesi düşmanca veya düzenli girdilere karşı beklenen davranışı iyileştirebilir.

Monte Carlo algoritması sınırlı sürede küçük hata olasılığıyla sonuç üretirken Las Vegas algoritması doğru sonucu garanti eder fakat çalışma süresi rastgele olabilir. Bu ayrım özellikle güvenilirlik gereksinimlerinde önemlidir.

NP-zorluk ve yaklaşık çözüm

Bir problemin optimal çözümünü küçük girdilerde bulmak, büyük girdiler için verimli genel algoritma bulunduğu anlamına gelmez. NP-zor problemler için pratik yaklaşım:

tam çözüm küçük n
   +
özel durum algoritması
   +
yaklaşık / sezgisel çözüm
   +
ölçülebilir kalite sınırı

şeklinde olabilir.

Sezgisel yöntem hızlı sonuç verebilir fakat optimum garantisi sunmayabilir. Approximation algorithm ise problem için matematiksel bir kalite oranı sağlayabilir. Genetik algoritma, tabu arama veya benzeri meta-sezgisel yöntemlerin yeri bu sınırdan sonra değerlendirilmelidir.

Algoritma mühendisliğinde temel soru yalnız "karmaşıklık nedir?" değildir. Doğruluk garantisi, veri boyutu, bellek yerelliği, en kötü durum, tekrar üretilebilirlik ve kabul edilebilir yaklaşık hata aynı tasarım kararının parçalarıdır.

Veri Yapılarının Birlikte Kullanımı

Veri yapısı seçimi doğrudan işleme bağlıdır.

Gereksinim: İndisle hızlı erişim; Uygun yapı: Dizi
Gereksinim: Sık baş/orta ekleme; Uygun yapı: Bağlantılı liste
Gereksinim: Son giren ilk çıksın; Uygun yapı: Stack
Gereksinim: İlk giren ilk çıksın; Uygun yapı: Kuyruk
Gereksinim: Önceliğe göre seçim; Uygun yapı: Öbek / Priority Kuyruk
Gereksinim: Anahtarla çok hızlı ortalama arama; Uygun yapı: Hash table
Gereksinim: Sıralı dinamik veri; Uygun yapı: Dengeli arama ağacı
Gereksinim: Hiyerarşik veri; Uygun yapı: Tree
Gereksinim: Ağ ve genel ilişkiler; Uygun yapı: Graph
Gereksinim: Önek araması; Uygun yapı: Trie

Tek bir veri yapısı bütün işlemleri en iyi biçimde gerçekleştirmez.

Mühendislik kararı:

veri özellikleri
+ işlem dağılımı
+ zaman gereksinimi
+ bellek gereksinimi

birlikte değerlendirilerek verilir.

Eski Optimizasyon Projelerinden Uygulamalı Örnekler

Üstel arama alanının neden yalnız mikro-optimizasyonla çözülemeyeceğini Subset Sum Optimizasyonu projesinde; durum bilgisini yeniden kullanarak arama alanını küçültme fikrini ise Dudley's Hat çözüm algoritması çalışmasında tarihsel uygulama örnekleri olarak koruyorum.

Algoritma Seçimini Veri ve Sistem Kısıtlarıyla Birleştirmek

Bir algoritmanın Big-O sınıfı önemli olmakla birlikte tek karar ölçütü değildir. Veri boyutu, veri dağılımı, bellek erişim örüntüsü, ek bellek ihtiyacı, kararlılık (stability), çevrim içi/çevrim dışı çalışma ve diske taşan veri gibi özellikler gerçek seçimi belirler.

Sıralama algoritmalarını karşılaştırma

Insertion sort küçük veya büyük ölçüde sıralı dizilerde düşük sabit maliyetle yararlı olabilir; genel durumda O(n²) zaman alır.
Selection sort da O(n²) karşılaştırma yapar ve az sayıda swap avantajı sağlayabilir.
Merge sort O(n log n) worst-case davranış ve kararlı sıralama sunabilir; tipik dizi uygulamasında ek bellek gerekir.
Quicksort ortalamada O(n log n) ve cache açısından güçlü olabilir; pivot stratejisine bağlı olarak kötü durumda O(n²) davranış mümkündür.
Heapsort worst-case O(n log n) ve O(1) ek dizi alanıyla çalışabilir; fakat cache locality ve sabit maliyetleri pratik performansı etkiler.

“En hızlı sıralama algoritması” veriden bağımsız tek bir cevap değildir. Standard-library implementasyonları da sıklıkla birden fazla tekniği birleştirir.

Kararlılık ve in-place özelliği

Kararlı sıralama, eşit anahtarlı elemanların göreli sırasını korur. Bu özellik ardışık çok anahtarlı sıralamalarda önem kazanabilir. In-place terimi ise algoritmanın girişe ek olarak ne kadar yardımcı alan kullandığını ifade eder; kararlılık ile aynı kavram değildir.

Arama ve veri yapısı ilişkisi

Binary search O(log n) karşılaştırma sağlar ancak veri sıralı ve random-access yapıda olmalıdır. Hash table ortalama O(1) arama hedefleyebilir fakat hash dağılımı, load factor, collision çözümü ve yeniden boyutlandırma maliyeti vardır. Dengeli arama ağaçları O(log n) sınırıyla sıralı dolaşım ve range query desteği sağlar.

Dolayısıyla arama algoritması veri yapısından bağımsız seçilmez.

Graf algoritmaları

BFS ağırlıksız bir grafta en az kenar sayılı yolları bulabilir ve queue kullanır. DFS stack/özyineleme ile derinlemesine ilerler; cycle detection, component ve topological işlemlerde temel yapı taşıdır. Dijkstra negatif olmayan kenar ağırlıklarında tek kaynak en kısa yolları çözer; negatif kenar varsa varsayımı bozulur.

Algoritmanın önkoşulu doğrulanmadan yalnız adı uygulanmamalıdır.

Greedy ve dinamik programlama

Greedy yaklaşım her adımda yerel olarak uygun seçim yapar; ancak yerel optimumun küresel optimum üreteceği problem özelliği kanıtlanmalıdır. Dinamik programlama örtüşen alt problemleri ve optimal alt yapı özelliğini kullanarak durum sonuçlarını saklar. Memoization top-down, tabulation bottom-up gerçekleştirilebilir.

Her recursion dinamik programlama değildir; her DP çözümü de recursion kullanmak zorunda değildir.

Harici sıralama

Veri RAM'e sığmadığında CPU karmaşıklığından çok disk/SSD G/Ç maliyeti belirleyici olabilir. External merge sort veriyi belleğe sığan parçalarda sıralar ve sonra sıralı run'ları birleştirir. Bu yaklaşım, algoritma analizinin gerçek sistemde bellek hiyerarşisi ve G/Ç modeliyle birlikte yapılması gerektiğini gösterir.

Öklid algoritması ve EBOB

İki tamsayının en büyük ortak böleni (EBOB; İngilizce GCD), Öklid algoritmasıyla kalan alma işlemi yinelenerek verimli biçimde hesaplanabilir. Temel bağıntı gcd(a,b) = gcd(b, a mod b) biçimindedir ve ikinci değer sıfır olduğunda kalan değer sonuçtur. Bu örnek, bir problemi tekrar eden daha küçük eşdeğer alt probleme dönüştürmenin klasik örneklerinden biridir.

Ölçüm ilkesi

Teorik karmaşıklık ölçekleme davranışını açıklar; benchmark ise belirli implementasyon, veri dağılımı ve donanımdaki maliyeti ölçer. Biri diğerinin yerine geçmez. Doğru mühendislik önce algoritmik üst sınırı, sonra gerçek darboğazı birlikte değerlendirir.

Önbellek yerelliği ve düşmanca girdiler

Asimptotik karmaşıklık algoritma karşılaştırmasının temelidir; fakat aynı Big-O sınıfındaki iki yapı gerçek makinede çok farklı davranabilir. Ardışık bellekte tutulan bir dizi, pointer ile dağılmış düğümlerden oluşan yapıya göre daha iyi cache yerelliği ve daha az dolaylı erişim sağlayabilir.

Hash tablosunda beklenen O(1) erişim, hash dağılımı ve yük faktörüne bağlıdır. Düşmanca seçilmiş girdiler çok sayıda çakışma üretebiliyorsa güvenlik açısından yalnız ortalama durum analizi yeterli değildir.

Algoritma seçimi bu nedenle üç katmanda yapılmalıdır: asimptotik sınır, veri dağılımı ve gerçek donanım maliyeti. Mikrobenchmark ancak temsilî veri, doğru ısınma ve optimizasyon koşullarıyla anlamlıdır.

Karmaşıklık iddiasını deneyle ilişkilendirmek

Big-O üst sınırı, belirli bir makinedeki çalışma süresinin doğrudan tahmini değildir. Aynı asimptotik sınıftaki iki yapı cache yerelliği, sabit katsayılar ve veri dağılımı nedeniyle farklı sonuç verebilir.

Bir benchmark yapılacaksa veri üretimi ölçüm bölümünden ayrılmalı, ısınma ve tekrar sayısı belirtilmeli, en azından medyan ve dağılım raporlanmalıdır. Rastgele veri ile sıralı, ters sıralı veya çok tekrar içeren veri aynı algoritmayı farklı zorlayabilir.

Doğruluk için invariant ve sınır durumları önemlidir. Boş koleksiyon, tek eleman, yinelenen anahtar, maksimum/minimum değer ve kötü durum girdisi; yalnız “normal” örneklerin sağlayamadığı kanıtı sağlar.

Veri Yapıları, Arama ve Yapay Zekâ

Yapay zekâ yöntemlerinin önemli bir bölümü, büyük bir olası durum veya aday kümesinden sınırlı maliyetle doğru adaya ulaşmaya çalışır. Bu nedenle veri yapıları ve algoritma analizi ile yapay zekâ arasındaki bağ yalnız “AI kodu da algoritma kullanır” düzeyinde değildir. Arama uzayının nasıl temsil edildiği, hangi adayın önce incelendiği ve ara sonuçların nasıl saklandığı doğrudan yöntemin uygulanabilirliğini belirler.

Klasik durum uzayı araması bunun en açık örneğidir. Bir problem graf olarak modellenebiliyorsa düğümler durumları, kenarlar geçerli geçişleri temsil eder. BFS en az kenarlı yolu; Dijkstra negatif olmayan ağırlıklarda en düşük maliyetli yolu; A* ise maliyet ile sezgisel kestirimi birleştirerek hedefe yönelmiş aramayı sağlayabilir:

f(n) = g(n) + h(n)

Burada öncelik kuyruğu yalnız bir uygulama ayrıntısı değildir. En düşük f(n) değerli adayın etkin seçilebilmesi, aramanın pratik maliyetini belirler. Aynı algoritmanın uygun olmayan veri yapısıyla gerçeklenmesi asimptotik ve gerçek çalışma süresini değiştirebilir.

Oyun ağacı ve planlama problemlerinde ağaç/graph ayrımı daha da önemlidir. Aynı duruma farklı yollardan ulaşılabiliyorsa durumu yalnız ağaç düğümü gibi ele almak tekrar hesaplama üretir. Hash table ile ziyaret edilen durumların tutulması veya transposition table kullanılması, aynı durumun yeniden genişletilmesini azaltır. Burada hash fonksiyonunun dağılımı, bellek kullanımı ve collision davranışı doğrudan arama kapasitesine dönüşür.

Makine öğrenmesinde komşuluk tabanlı yöntemler başka bir bağlantı kurar. k-NN kavramsal olarak basittir; ancak her sorguda bütün veri kümesini taramak büyük veri üzerinde pahalıdır. Boyut ve metriğe göre k-d tree, ball tree veya approximate nearest-neighbor indeksleri aday alanını daraltabilir. Yüksek boyutta klasik uzaysal ağaçların etkinliği azalabilir; bu kez yaklaşık arama yapıları ve veri temsili daha önemli hale gelir. Yani veri yapısı seçimi, verinin geometrisinden bağımsız değildir.

Priority queue, heap ve queue yapıları üretim AI sistemlerinde de görülür. İsteklerin önceliklendirilmesi, batch oluşturulması, beam search adaylarının tutulması veya olay akışlarının işlenmesi bunlara örnektir. Fakat aynı yapı her problemde doğru değildir. Beam search'te yalnız en iyi k aday tutulurken eksiksiz aramada eleme yapılmaz; veri yapısı algoritmanın karar politikasını gerçekleştiren araçtır.

Graf yapıları modern öğrenmede de veri modelinin kendisi olabilir. Sosyal ilişkiler, moleküler bağlar, iletişim ağları veya bilgi grafı düğüm ve kenarlarla temsil edilir. Graph Neural Network bu graf üzerinde öğrenme yapabilir; fakat grafın adjacency list, sparse matrix veya edge list biçiminde tutulması bellek ve yürütme maliyetini değiştirir. Öğrenme katmanı graf veri yapısının gereksinimlerini ortadan kaldırmaz.

Algoritma analizi burada temel sınırı koyar. Eğitimde O(n²) görünen bir adım, birkaç bin kayıt için kabul edilebilirken milyonlarca kayıt için baskın maliyet olabilir. Ancak yalnız Big-O yeterli değildir. Cache locality, allocation, branch behavior, paralellik ve veri dağılımı gerçek çalışma süresini etkiler. Yapay zekâ sistemlerinde de önce problem boyutu ve erişim örüntüsü ölçülmelidir.

Bu bağlamda üç katman ayrılmalıdır:

problem temsili → veri yapısı
arama / öğrenme kuralı → algoritma
fiziksel yürütme → sistem ve donanım

Yapay zekâ bu üç katmanın üzerinde çalışır. Veri yapıları ve algoritmalar, “zekâ” kavramını tanımlamaz; arama, komşuluk, planlama ve büyük aday uzaylarının hesaplanabilir biçimde yönetilmesini sağlar. Bu nedenle Ayrık Matematik kuramsal graf ve mantık temelini verirken, bu ders aynı yapıların çalıştırılabilir ve maliyeti ölçülebilir karşılığını kurar.

Bir algoritmayı seçmeden önce

Bir soruda doğru veri yapısını seçmek, çoğu zaman algoritmanın adını hatırlamaktan daha önemlidir. Önce hangi işlemlerin baskın olduğunu belirlemek gerekir: arama, ekleme, silme, en küçük/en büyük öğeyi alma, sıralı dolaşma ya da komşuluk sorgusu. Aynı veri kümesi için dizi, bağlı liste, yığın, kuyruk, karma tablosu, ağaç veya graf farklı maliyetler üretir.

Asimptotik gösterim büyüme hızını anlatır; küçük girdilerde gerçek çalışma süresini tek başına belirlemez. O(n log n) bir yöntem, sabit maliyetleri veya bellek erişim örüntüsü nedeniyle küçük n değerlerinde O(n^2) bir yöntemden yavaş olabilir. Buna karşılık girdi büyüdükçe baskın terim belirleyici hale gelir. Bu nedenle karmaşıklık hesabında önce hangi işlemin kaç kez çalıştığı çıkarılmalı, ardından baskın terim sadeleştirilmelidir.

Bir graf sorusunda da problem türü ayırt edilmelidir. Ağırlıksız bir grafta en az kenarlı yol için BFS doğal seçimdir; negatif olmayan kenar ağırlıklarında Dijkstra kullanılabilir. Negatif ağırlıklar bulunduğunda Dijkstra'nın temel varsayımı bozulur. Benzer biçimde açgözlü bir yöntem yerel olarak iyi kararlar verse de, çözümün optimal alt yapı ve uygun seçim özelliği yoksa küresel optimumu garanti etmez; bu durumda dinamik programlama gerekebilir.

Kısa bir doğrulama yöntemi, seçilen çözümün değişmezini açıkça yazmaktır. İkili aramada aranan değer varsa her adımın sonunda hâlâ kalan aralıkta bulunmalıdır. Dijkstra'da kesinleştirilmiş düğümün uzaklığı daha sonra küçülmemelidir. Yığın kullanan bir parantez denetiminde ise işlenen önek için açık parantezlerin düzeni korunmalıdır. Karmaşıklık hesabı çözümün ne kadar pahalı olduğunu, değişmez ise neden doğru olduğunu açıklar.

Kaynakça

Mark Allen Weiss. Data Structures and Algorithm Analysis in C++. Pearson, 2012.

Robert Sedgewick; Kevin Wayne. Algorithms. Addison-Wesley, 2011.

Stuart Russell, P. N. Artificial Intelligence: A Modern Approach, 4th ed. Pearson, 2021.

Thomas H. Cormen; Charles E. Leiserson; Ronald L. Rivest; Clifford Stein. Introduction to Algorithms. MIT Press, 2009.