Veri Yapıları ve Algoritma Analizi

Karmaşıklık analizinden dizi ve bağlı listelere, yığın ve kuyruktan ağaç, hash, graf, sıralama ve arama algoritmalarına uzanan ayrıntılı 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. Bu sürümde dizi, bağlı liste, yığın, kuyruk, ağaç, hash ve graf yapılarını algoritma analiziyle birlikte bıraktım; Big-O ifadelerinde en kötü, ortalama ve amortize maliyetlerin birbirine karıştırılmamasına dikkat ettim.

Ü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

Benchmark, 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 benchmark birbirinin alternatifi değildir.

Asimptotik analiz büyüme davranışını, benchmark 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,
queue,
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 padding 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:

row-major,
column-major.

C ailesi dillerde klasik çok boyutlu diziler row-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 padding 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 | Örnek | | --- | --- | | O(1) | Dizi indis erişimi | | O(log n) | Binary search | | O(n) | Doğrusal tarama | | O(n log n) | Merge sort | | O(n^2) | Basit çift döngüler | | O(n^3) | Klasik bazı matris işlemleri | | O(2^n) | Bazı alt küme aramaları | | O(n!) | 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.

Benchmark 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, cache 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 | Dizi | Tek yönlü bağlantılı liste | | --- | --- | --- | | İndisle erişim | O(1) | O(n) | | Baştan ekleme | O(n) olabilir | O(1) | | Bilinen düğümden sonra ekleme | O(n) kaydırma | O(1) | | Arama | O(n) | O(n) | | Bellek yerleşimi | Ardışık | Dağınık olabilir | | Ek bağlantı belleği | Yok | Vardır |

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

Modern işlemcilerde dizilerin ardışık bellek yerleşimi cache 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 heap 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ç

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.

Heap

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

Max-heap:

parent >= children

Min-heap:

parent <= children

Heap 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),
heap oluşturma: O(n).

Heap, priority queue 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-heap'e koy,
en küçük iki frekansı çıkar,
bunları yeni ortak düğüm altında birleştir,
toplam frekansla heap'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.

Queue 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,
parser,
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

Queue:

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 queue 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 queue 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 queue:

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.

Heap sort

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

Her turda:

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

Zaman:

O(n log n)

Ek alan:

O(1)

olabilir.

Klasik heap 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 cache davranışı ve düşük sabit maliyet nedeniyle çok etkilidir.

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

| Algoritma | En iyi | Ortalama | En kötü | Ek alan | Kararlı | | --- | --- | --- | --- | --- | --- | | Insertion | O(n) | O(n^2) | O(n^2) | O(1) | Evet | | Selection | O(n^2) | O(n^2) | O(n^2) | O(1) | Genellikle hayır | | Bubble | O(n) optimize | O(n^2) | O(n^2) | O(1) | Evet | | Merge | O(n log n) | O(n log n) | O(n log n) | O(n) dizi | Evet | | Heap | O(n log n) | O(n log n) | O(n log n) | O(1) | Hayır | | Quick | O(n log n) | O(n log n) | O(n^2) | çağrı yığını | 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 collision oluşursa:

O(n)

davranışı görülebilir.

Çakışma

İki farklı anahtar aynı tablo konumuna eşlenirse collision 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 cache 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.

Queue 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 | DFS | BFS | | --- | --- | --- | | Temel yapı | Stack/özyineleme | Queue | | Dolaşım | Derinlik | Seviye | | Ağırlıksız en kısa yol | Doğrudan garanti yok | Evet | | Topological sort | Uygun | Kahn yaklaşımıyla BFS de kullanılabilir | | Bellek kullanımı | Yapıya bağlı | 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 heap 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 queue 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 allocation,
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ı,
build sistemi,
iş akışı.

DFS veya indegree tabanlı Kahn algoritmasıyla:

O(V + E)

zamanda yapılabilir.

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

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

| Gereksinim | Uygun yapı | | --- | --- | | İndisle hızlı erişim | Dizi | | Sık baş/orta ekleme | Bağlantılı liste | | Son giren ilk çıksın | Stack | | İlk giren ilk çıksın | Queue | | Önceliğe göre seçim | Heap / Priority Queue | | Anahtarla çok hızlı ortalama arama | Hash table | | Sıralı dinamik veri | Dengeli arama ağacı | | Hiyerarşik veri | Tree | | Ağ ve genel ilişkiler | Graph | | Önek araması | 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.