Veri Yapıları all.pdf

Veri Yapıları Bandırma 17 Eylül Üniversitesi Mühendislik ve Doğa Bilimleri Fakültesi Dr. Emrah DÖNMEZ Veri Yapıları Arama ve Sıralama Arama & Sıralama Doğrusal (Lineer) Arama • Doğrusal arama teknikleri en basit tekniktir. • Bu teknikte elemanlar tek tek aranır. • Bu prosedür, sıralanmamış veri...

Veri Yapıları Bandırma 17 Eylül Üniversitesi Mühendislik ve Doğa Bilimleri Fakültesi Dr. Emrah DÖNMEZ Veri Yapıları Arama ve Sıralama Arama & Sıralama Doğrusal (Lineer) Arama • Doğrusal arama teknikleri en basit tekniktir. • Bu teknikte elemanlar tek tek aranır. • Bu prosedür, sıralanmamış veri seti için de geçerlidir. • Doğrusal arama, sıralı arama olarak da bilinir. • Zaman karmaşıklığı n O(n) mertebesinde olduğu için doğrusal olarak adlandırılır. Arama & Sıralama Doğrusal (Lineer) Arama • Doğrusal Arama Tekniğinin Karmaşıklığı • Zaman Karmaşıklığı: O(n) • Uzay Karmaşıklığı: O(1) • Giriş ve çıkış Girdi: Bir veri listesi: 20 4 89 75 10 23 45 69 Aranan eleman: 10 Çıktı: Bulunduğu yer: 4 Arama & Sıralama Doğrusal (Lineer) Arama Algoritma dogrusalArama(dizi, boyut, anahtar) • Girdi − Sıralanmış bir dizi, dizinin boyutu ve arama anahtarı • Çıktı - anahtarın konumu (eğer bulunursa), aksi takdirde yanlış konum. Arama & Sıralama Doğrusal (Lineer) Arama 1. 2. 3. Begin for i := 0 to size -1 do if array[i] = key then 4. return i 5. done 6. return invalid location 7. End Arama & Sıralama Doğrusal (Lineer) Arama • ÖRNEK Arama & Sıralama İkili (Binary) Arama • Liste sıralandığında, listedeki öğeleri bulmak için ikili arama tekniğini kullanabiliriz. • Bu prosedürde, tüm liste iki alt listeye bölünür. • Öğe orta konumda bulunursa, konumu döndürür, • Aksi takdirde sol veya sağ alt listeye atlar ve öğeyi bulana veya aralığı geçene kadar aynı işlemi tekrar yapar. Arama & Sıralama İkili (Binary) Arama • İkili Arama Tekniğinin Karmaşıklığı • Zaman Karmaşıklığı: En iyi durumda O(1). Ortalama ve en kötü durumda O(log2 n) • Uzay Karmaşıklığı: O(1) • Giriş ve çıkış Girdi: Sıralı veri listesi: 12 25 48 52 67 79 88 93 Aranan eleman: 79 Çıktı: Bulunduğu yer: 5 Arama & Sıralama İkili (Binary) Arama Algoritma ikiliArama(dizi, baslangic, bitiş, anahtar) • Girdi − Sıralanmış bir dizi, başlangıç ve bitiş noktaları ve arama anahtarı • Çıktı - anahtarın konumu (eğer bulunursa), aksi takdirde yanlış konum. Arama & Sıralama İkili (Binary) Arama 1. Begin 2. if start <= end then 3. mid := start + (end - start) /2 4. if array[mid] = key then 5. return mid location 6. if array[mid] > key then 7. call binarySearch(array, mid+1, end, key) 8. else when array[mid] < key then 9. call binarySearch(array, start, mid-1, key) 10. else 11. return invalid location 12. End Arama & Sıralama İkili (Binary) Arama • ÖRNEK Arama & Sıralama Üstel (Eksponansiyel) Arama • Üstel arama, iki katına veya dörtnala arama olarak da bilinir. • Bu mekanizma, arama anahtarının bulunabileceği aralığı bulmak için kullanılır. • L ve U listenin üst ve alt sınırıysa, L ve U her ikisi de 2'nin kuvvetidir. • Son bölüm için, U listenin son konumudur. • Bu nedenle üstel olarak bilinir. • Belirli aralığı bulduktan sonra, arama anahtarının tam yerini bulmak için ikili arama tekniğini kullanır. Arama & Sıralama Üstel (Eksponansiyel) Arama • İkili Arama Tekniğinin Karmaşıklığı • Zaman Karmaşıklığı: En iyi durumda O(1). Ortalama ve en kötü durumda O(log2 i). i arama anahtarının bulunduğu konumdur. • Uzay Karmaşıklığı: O(1) • Giriş ve çıkış Girdi: Sıralı veri listesi: 10 13 15 26 28 50 56 88 94 127 159 356 480 567 689 699 780 850 956 995 Aranan eleman: 780 Çıktı: Bulunduğu yer: 16 Arama & Sıralama Üstel (Eksponansiyel) Arama Algoritma ustelArama(dizi, baslangic, bitiş, anahtar) • Girdi − Sıralanmış bir dizi, başlangıç ve bitiş noktaları ve arama anahtarı • Çıktı - anahtarın konumu (eğer bulunursa), aksi takdirde yanlış konum. Arama & Sıralama Üstel (Eksponansiyel) Arama - 1 1. Begin 2. if start <= end then 3. mid := start + (end - start) /2 4. if array[mid] = key then 5. return mid location 6. if array[mid] > key then 7. call binarySearch(array, mid+1, end, key) 8. else when array[mid] < key then 9. call binarySearch(array, start, mid-1, key) 10. else 11. return invalid location 12. End Arama & Sıralama Üstel (Eksponansiyel) Arama - 2 1. Begin 2. if (end – start) <= 0 then 3. return invalid location 4. i := 1 5. while i < (end - start) do 6. if array[i] < key then 7. i := i * 2 //increase i as power of 2 8. else 9. terminate the loop 10. done 11. call binarySearch(array, i/2, i, key) 12. End Arama & Sıralama Üstel (Eksponansiyel) Arama • ÖRNEK Arama & Sıralama Diğer Arama Yöntemleri - Enterpolasyon • İkili arama tekniği için listeler eşit parçalara bölünür. • Enterpolasyon arama tekniği için prosedür, enterpolasyon formülünü kullanarak tam konumu bulmaya çalışacaktır. • Tahmini konumu bulduktan sonra, o konumu kullanarak listeyi ayırabilir. • Her seferinde tam yerini bulmaya çalıştığı için arama süresi de kısalıyor. • Bu teknik, öğeler eşit olarak dağıtılırsa öğeleri kolayca bulabilir. Arama & Sıralama Diğer Arama Yöntemleri - Enterpolasyon 1. 2. Begin while start <= end AND key >= array[start] AND key <= array[end] do 3. dist := key – array[start] 4. valRange := array[end] – array[start] 5. fraction := dist / valRange 6. indexRange := end – start 7. estimate := start + (fraction * indexRange) 8. if array[estimate] = key then 9. return estimate position 10. if array[estimate] < key then 11. 12. start := estimate + 1 else 13. end = estimate -1 14. done 15. return invalid position 16. End Arama & Sıralama Diğer Arama Yöntemleri – Atlama/Sıçrama (Jump) • Atlamalı arama tekniği, sıralı listeler için de çalışır. • Bir blok oluşturur ve o bloktaki elemanı bulmaya çalışır. • Öğe blokta değilse, tüm bloğu kaydırır. • Blok boyutu, listenin boyutuna bağlıdır. • Listenin boyutu n ise blok boyutu √n olacaktır. • Doğru bir blok bulduktan sonra, öğeyi doğrusal bir arama tekniği kullanarak bulur. • Atlamalı arama, performansına göre doğrusal arama ve ikili arama arasında yer alır. Arama & Sıralama Diğer Arama Yöntemleri - Atlama/Sıçrama (Jump) 1. Begin 2. blockSize := √size 3. start := 0 4. end := blockSize 5. while array[end] <= key AND end < size do 6. start := end 7. end := end + blockSize 8. if end > size – 1 then 9. end := size 10. done 11. for i := start to end -1 do 12. if array[i] = key then 13. return i 14. done 15. return invalid location 16. End Arama & Sıralama Diğer Arama Yöntemleri – Üçlü/Üçerli (Ternary) • İkili arama gibi listeleri de alt listelere ayırır. • Bu prosedür, listeyi iki ara orta değer kullanarak üç parçaya böler. • Listeler daha fazla alt bölüme ayrıldığından, bir anahtar değeri arama süresini azaltır. Arama & Sıralama Diğer Arama Yöntemleri – Üçlü/Üçerli (Ternary) 1. 2. Begin if start <= end then 3. midFirst := start + (end - start) /3 4. midSecond := midFirst + (end - start) / 3 5. if array[midFirst] = key then 6. 7. return midFirst if array[midSecond] = key then 8. 9. return midSecond if key < array[midFirst] then 10. 11. call ternarySearch(array, start, midFirst-1, key) if key > array[midSecond] then 12. 13. call ternarySearch(array, midFirst+1, end, key) else 14. 15. 16. 17. call ternarySearch(array, midFirst+1, midSecond-1, key) else return invalid location End Arama & Sıralama SIRALAMA YÖNTEMLERİ • Quick Sort – Hızlı Sıralama • Bucket Sort – Kova Sıralama • Bubble Sort – Kabarcık Sıralama • Heap Sort – Yığın Sıralama • Merge Sort – Birleştirmeli Sıralama • Counting Sort – Saymalı Sıralama • Selection Sort – Seçmeli Sıralama • Cycle Sort – Döngü Sıralama • Insertion Sort – Eklemeli Sıralama • Comb Sort – Petek Sıralama • Radix Sort – Kök Sıralama • Pigeonhole Sort – Güvercin Deliği Sırlama • Shell Sort – Kabuk Sıralama Veri Yapıları Bandırma 17 Eylül Üniversitesi Mühendislik ve Doğa Bilimleri Fakültesi Dr. Emrah DÖNMEZ Veri Yapıları Arama ve Sıralama Arama & Sıralama SIRALAMA YÖNTEMLERİ • Quick Sort – Hızlı Sıralama • Bucket Sort – Kova Sıralama • Bubble Sort – Kabarcık Sıralama • Heap Sort – Yığın Sıralama • Merge Sort – Birleştirmeli Sıralama • Counting Sort – Saymalı Sıralama • Selection Sort – Seçmeli Sıralama • Cycle Sort – Döngü Sıralama • Insertion Sort – Eklemeli Sıralama • Comb Sort – Petek Sıralama • Radix Sort – Kök Sıralama • Pigeonhole Sort – Güvercin Deliği Sırlama • Shell Sort – Kabuk Sıralama Arama & Sıralama SIRALAMA YÖNTEMLERİ • Quick Sort – Hızlı Sıralama Arama & Sıralama SIRALAMA YÖNTEMLERİ • Bubble Sort – Kabarcık Sıralama Arama & Sıralama SIRALAMA YÖNTEMLERİ • Bubble Sort – Kabarcık Sıralama Arama & Sıralama SIRALAMA YÖNTEMLERİ • Bubble Sort – Kabarcık Sıralama Arama & Sıralama SIRALAMA YÖNTEMLERİ • Merge Sort – Birleştirmeli Sıralama Arama & Sıralama SIRALAMA YÖNTEMLERİ • Selection Sort – Seçmeli Sıralama Arama & Sıralama SIRALAMA YÖNTEMLERİ • Selection Sort – Seçmeli Sıralama Arama & Sıralama SIRALAMA YÖNTEMLERİ • Selection Sort – Seçmeli Sıralama Arama & Sıralama SIRALAMA YÖNTEMLERİ • Insertion Sort – Eklemeli Sıralama Veri Yapıları Bandırma 17 Eylül Üniversitesi Mühendislik ve Doğa Bilimleri Fakültesi Dr. Emrah DÖNMEZ Veri Yapıları Hashing Fonksiyonları Hashing Fonksiyonları Hash Tablosu • Hash tablosu veri yapısı, öğeleri anahtar/değer çiftlerinde saklar. • Anahtar (Key) - değerleri indekslemek için kullanılan benzersiz tamsayı • Değer (Value/Data) - anahtarlarla ilişkili veriler. Hashing Fonksiyonları Neden Hashing yapısına ihtiyaç duyarız? • Birçok uygulama çok sayıda veriyle ilgilenir • Arama motorları ve web sayfaları • Sayısız arama var. • Aramalar zaman açısından kritiktir. • Diziler ve listeler gibi tipik veri yapıları verimli aramaları işlemek için yeterli olmayabilir • Genel olarak: Aramaların neredeyse sabit bir zamanda yapılması gerektiğinde. O(1) Hashing Fonksiyonları Neden Hashing yapısına ihtiyaç duyarız? • İkili aramadan daha iyisini yapabilecek bir şeye ihtiyacımız var, • O(log N). • O(1)'i istiyoruz. • Çözüm: Hashing Aslında, hashing şu durumlarda kullanılır: • • • • • • Web aramaları Yazım denetleyicileri Veri-tabanları Derleyiciler Şifreleri Diğerleri Hashing Fonksiyonları Hashing (Hash Fonksiyonu) • Bir hash tablosunda, anahtarlar kullanılarak yeni bir dizin işlenir. Ve o anahtara karşılık gelen eleman dizinde saklanır. Bu işleme hash denir. • k bir anahtar ve h(x) bir hash fonksiyonu olsun. • Burada h(k), k ile bağlantılı elemanı depolamak için bize yeni bir indeks verecektir. Hashing Fonksiyonları Hashing (Hash Fonksiyonu) Hashing Fonksiyonları Hash Çarpışması • Hashing işlevi birden çok anahtar için aynı dizini oluşturduğunda, bir çakışma olacaktır (bu dizinde hangi değerin saklanacağı). Buna hash çarpışma denir. • Aşağıdaki tekniklerden birini kullanarak hash çarpışmayı çözebiliriz. • Zincirleme ile çarpışma çözümü • Açık Adresleme: Doğrusal/Kuadratik(Karesel) Sondalama ve Çift Hashing Hashing Fonksiyonları 1. Zincirleme ile çarpışma çözümü • Zincirlemede, eğer bir hash fonksiyonu birden fazla eleman için aynı indeksi üretiyorsa, bu elemanlar çift bağlantılı bir liste kullanılarak aynı indekste saklanır. • j, birden çok öğenin yuvasıysa, öğe listesinin başına bir işaretçi içerir. Hiçbir öğe yoksa, j NIL içerir. Arama & Sıralama 1. Zincirleme ile çarpışma çözümü Hashing Fonksiyonları 1. Zincirleme ile çarpışma çözümü – Operasyonlar için sözde kod chainedHashSearch(T, k) return T[h(k)] chainedHashInsert(T, x) T[h(x.key)] = x //insert at the head chainedHashDelete(T, x) T[h(x.key)] = NIL Hashing Fonksiyonları 2. Açık Adresleme • Zincirlemeden farklı olarak, açık adresleme aynı yuvada birden çok öğe depolamaz. Burada, her yuva ya tek bir anahtarla doldurulur ya da NIL bırakılır. • Açık adreslemede kullanılan farklı teknikler şunlardır: 1. Doğrusal Sondalama 2. İkinci Dereceden Sondalama 3. Çifte Hashing Hashing Fonksiyonları 2. Açık Adresleme 2.1. Doğrusal sondalama • Doğrusal sondalamada, çarpışma bir sonraki yuva kontrol edilerek çözülür. • ℎ(𝑘, 𝑖) = (ℎ′(𝑘) + 𝑖) 𝑚𝑜𝑑 𝑚 • nerede • i = {0, 1, ….} • h'(k) yeni bir hash fonksiyondur • h(k, 0)'da bir çarpışma meydana gelirse, h(k, 1) kontrol edilir. Bu şekilde, i'nin değeri doğrusal olarak artırılır. Hashing Fonksiyonları 2. Açık Adresleme 2.1. Doğrusal sondalama • Doğrusal sondalama ile ilgili sorun, bitişik yuvalardan oluşan bir kümenin doldurulmasıdır. • Yeni bir eleman eklerken, tüm kümenin üzerinden geçilmelidir. • Bu, hash tablosundaki işlemleri gerçekleştirmek için gereken süreye eklenir. Hashing Fonksiyonları 2. Açık Adresleme 2.2. İkinci dereceden sondalama • Doğrusal sondalamaya benzer şekilde çalışır, ancak aşağıdaki ilişki kullanılarak yuvalar arasındaki boşluk (birden fazla) artırılır. • ℎ(𝑘, 𝑖) = (ℎ′(𝑘) + 𝑐1 𝑖 + 𝑐2 𝑖 2 ) 𝑚𝑜𝑑 𝑚 • nerede, • c1 ve c2 pozitif yardımcı sabitlerdir, • i = {0, 1, ….} Hashing Fonksiyonları 2. Açık Adresleme 2.3. Çifte Hashing • Bir hashing işlevi h(k) uygulandıktan sonra bir çarpışma meydana gelirse, sonraki yuvayı bulmak için başka bir hashing işlevi hesaplanır. • ℎ(𝑘, 𝑖) = (ℎ1 (𝑘) + 𝑖ℎ2 (𝑘)) 𝑚𝑜𝑑 𝑚 Hashing Fonksiyonları İyi Hash Fonksiyonları • İyi bir hash fonksiyonu çarpışmaları tamamen engellemeyebilir ancak çarpışma sayısını azaltabilir. • İyi bir hash fonksiyonu bulmak için farklı yöntemler: 1. Bölme Yöntemi 2. Çarpma Yöntemi 3. Evrensel Hashing Hashing Fonksiyonları İyi Hash Fonksiyonları 1. Bölme Yöntemi • k bir anahtarsa ve m özet tablosunun boyutuysa, hash işlevi h() şu şekilde hesaplanır: • ℎ(𝑘) = 𝑘 𝑚𝑜𝑑 𝑚 • Örneğin, bir hash tablosunun boyutu 10 ve k = 112 ise h(k) = 112 mod 10 = 2. • m'nin değeri 2'nin kuvvetleri olmamalıdır. Bunun nedeni, ikili formatta 2'nin kuvvetlerinin olmasıdır. • 10, 100, 1000, …. k mod m'yi bulduğumuzda, her zaman daha düşük sıralı p-bitlerini alacağız. Hashing Fonksiyonları İyi Hash Fonksiyonları 1. Bölme Yöntemi m = 22, k = 17 ise, h(k) = 17 mod 22 = 10001 mod 100 = 01 m = 23, k = 17 ise, h(k) = 17 mod 22 = 10001 mod 100 = 001 m = 24, k = 17 ise, h(k) = 17 mod 22 = 10001 mod 100 = 0001 m = 2p ise, h(k) = p m'nin alt bitleri Hashing Fonksiyonları İyi Hash Fonksiyonları 2. Çarpma Yöntemi • ℎ(𝑘) = ⌊𝑚(𝑘𝐴 𝑚𝑜𝑑 1)⌋ • nerede, • kA mod 1, kA kesirli kısmını verir, • ⌊ ⌋ taban değerini verir • A herhangi bir sabittir. A'nın değeri 0 ile 1 arasındadır. Ancak, Knuth tarafından önerilen en uygun seçim ≈ ( 5 − 1)/2 olacaktır. Hashing Fonksiyonları İyi Hash Fonksiyonları 3. Evrensel Hashing • Universal hashing'de hash fonksiyonu anahtarlardan bağımsız olarak rastgele seçilir. Hashing Fonksiyonları Hash Fonksiyonları • Anahtarın dizideki konumunu belirler. • Tablo (dizi) boyutunun N olduğunu varsayın • f(x) işlevi, herhangi bir x anahtarını 0 ile N−1 arasında bir int ile eşler. • Örneğin, N=15 olduğunu, x anahtarının 0 ile MAX_INT arasında negatif olmayan bir tam sayı olduğunu ve karma işlevi f(x) = x % 15 olduğunu varsayalım. Hashing Fonksiyonları Hash Fonksiyonları • f(x) = x % 15 olsun. O halde, Eğer x f(x) = = 25 10 129 9 35 5 2501 11 47 2 36 6 • Anahtarları dizide saklamak basittir: 0 _ 1 _ 2 47 3 _ 4 _ 5 35 6 36 7 _ 8 9 _ 129 10 11 25 2501 12 _ 13 _ • Böylece, silme ve bulma O(1)'de yapılabilir ve ayrıca şunun dışında ekleme yapılabilir… 14 _ Hashing Fonksiyonları Hash Fonksiyonları • x = 65 eklemeye çalıştığınızda ne olur? x = f(x) = 0 _ 1 _ 2 47 3 _ 4 _ • Buna çarpışma denir. 5 6 35 36 65(?) 7 _ 65 5 8 9 _ 129 10 11 25 2501 12 _ 13 _ 14 _ Hashing Fonksiyonları Hashing Çarpışma – Zincirleme çözümü • Her dizi öğesinin bir zincirin başı olmasına izin verin. 0 1 2  47 3 4 5  65  35 6  36 7 8 9  129 • Nerede saklarsınız: 29, 16, 14, 99, 127 ? 10 11   25 2501 12 13 14 Hashing Fonksiyonları Hashing Çarpışma – Zincirleme çözümü • Her dizi öğesinin bir zincirin başı olmasına izin verin: • Nerede saklarsınız: 29, 16, 14, 99, 127 ? 0 1  16 2  47 3 4 5  65  35 6 7   36 127 8 9  99  129 • Yeni anahtarlar ilgili zincirin önüne gider. 10 11   25 2501 12 13 14  14  29 Hashing Fonksiyonları Hashing Çarpışma – Zincirleme çözümü dezavantajları • Dizinin parçaları asla kullanılmayabilir. • Zincirler uzadıkça, arama süresi en kötü durumda O(n) değerine yükselir. • Yeni zincir düğümleri oluşturmak nispeten pahalıdır (hala sabit zaman, ancak sabit yüksektir). • Daha fazla yer açmak için zincir kullanmak yerine dizideki "kullanılmayan" alanı kullanmanın bir yolu var mı? Hashing Fonksiyonları Hashing Çarpışma – Doğrusal Sondalama • x anahtarının dizinin f(x)=t öğesinde saklanmasına izin verin 0 1 2 47 3 4 5 6 35 36 65(?) 7 8 9 129 10 11 25 2501 12 13 • Bir çarpışma durumunda ne yaparsınız? • Hash tablosu dolu değilse, bir sonraki dizi elemanında anahtarı saklamayı deneyin (bu durumda (t+1)%N, (t+2)%N, (t+3)%N …) • Ta ki boş bir yuva bulana kadar. 14 Hashing Fonksiyonları Hashing Çarpışma – Doğrusal Sondalama • 65'i nerede saklıyorsunuz? 0 1 2 47 3 4 5 6 7 35 36 65    denemeler • Nerede saklarsın: 29? 8 9 129 10 11 25 2501 12 13 14 Hashing Fonksiyonları Hashing Çarpışma – Doğrusal Sondalama • Hash tablo dolu değilse, anahtarı (t+1)%N, (t+2)%N, … dizi öğelerinde saklamayı deneyin. 0 1 2 47 3 4 5 35 • Nerede depolarsınız: 16? 6 36 7 65 8 9 129 10 11 25 2501 12 13 14 29  denemeler Hashing Fonksiyonları Hashing Çarpışma – Doğrusal Sondalama • Hash tablo dolu değilse, anahtarı (t+1)%N, (t+2)%N, … dizi öğelerinde saklamayı deneyin. 0 1 16  2 47 3 4 5 35 • Nerede depolarsınız: 14? 6 36 7 65 8 9 129 10 11 25 2501 12 13 14 29 Hashing Fonksiyonları Hashing Çarpışma – Doğrusal Sondalama • Hash tablo dolu değilse, anahtarı (t+1)%N, (t+2)%N, … dizi öğelerinde saklamayı deneyin. 0 14  1 16 2 47 3 4 5 35 • Nerede saklarsın: 99? 6 36 7 65 8 9 129 10 11 25 2501 12 13 14 29  denemeler Hashing Fonksiyonları Hashing Çarpışma – Doğrusal Sondalama • Hash tablo dolu değilse, anahtarı (t+1)%N, (t+2)%N, … dizi öğelerinde saklamayı deneyin. 0 14 1 16 2 47 3 4 5 35 • Nerede saklarsınız: 127 ? 6 36 7 65 8 9 129  10 11 12 25 2501 99    denemeler 13 14 29 Hashing Fonksiyonları Hashing Çarpışma – Doğrusal Sondalama • Hash tablo dolu değilse, anahtarı (t+1)%N, (t+2)%N, … dizi öğelerinde saklamayı deneyin. 0 1 16 2 47 3 4 5 35 6 36 7 8 9 65 127 129   denemeler 10 11 25 2501 12 29 13 99 14 14 Hashing Fonksiyonları Hashing Çarpışma – Doğrusal Sondalama • Ayrı veri yapıları (zincirler) ihtiyacını ve düğüm oluşturma maliyetini ortadan kaldırır. • Kümelenme sorununa yol açar. Öğeler dizide yoğun aralıklarla kümelenme eğilimindedir. ••••••• •••••• ••••••••••• • Arama verimliliği sorunu devam ediyor. • Silme daha zor hale gelir…. ••••••• • Hashing Fonksiyonları Hashing Çarpışma – İkinci dereceden Sondalama • x anahtarının dizinin f(x)=t öğesinde saklanmasına izin verin 0 1 2 47 3 4 5 6 35 36 65(?) 7 8 9 129 10 11 25 2501 • Bir çarpışma durumunda ne yaparsınız? • Hash tablosu dolu değilse, anahtarı dizi öğelerinde; • (𝒕 + 𝟏𝟐 )%𝑵, (𝒕 + 𝟐𝟐 )%𝑵, (𝒕 + 𝟑𝟐 )%𝑵 … • Ta ki boş bir yuva bulana kadar. 12 13 14 Hashing Fonksiyonları Hashing Çarpışma – İkinci dereceden Sondalama • 65'i nerede saklıyorsunuz? f(65)=t=5 0 1 2 47 3 4 5 6 7 35 36   t t+1 denemeler • Nerede saklarsın: 29? 8 9 129  t+4 10 11 25 2501 12 13 14 65  t+9 Hashing Fonksiyonları Hashing Çarpışma – İkinci dereceden Sondalama • Hash tablo dolu değilse, anahtarı dizi öğelerinde (t+12)%N, (t+22)%N … 0 29  t+1 1 2 47 3 4 5 35 • Nerede depolarsınız: 16? 6 36 7 8 9 129 10 11 25 2501 12 13 14 65  t denemeler Hashing Fonksiyonları Hashing Çarpışma – İkinci dereceden Sondalama • Hash tablo dolu değilse, anahtarı dizi öğelerinde (t+12)%N, (t+22)%N … 0 29 1 2 16 47  t denemeler 3 4 5 35 • Nerede depolarsınız: 14? 6 36 7 8 9 129 10 11 25 2501 12 13 14 65 Hashing Fonksiyonları Hashing Çarpışma – İkinci dereceden Sondalama • Hash tablo dolu değilse, anahtarı dizi öğelerinde (t+12)%N, (t+22)%N … 0 1 29 16  t+1 2 47 3 14  t+4 4 5 35 • Nerede depolarsınız: 99? 6 36 7 8 9 129 10 11 25 2501 12 13 14 65  t denemeler Hashing Fonksiyonları Hashing Çarpışma – İkinci dereceden Sondalama • Hash tablo dolu değilse, anahtarı dizi öğelerinde (t+12)%N, (t+22)%N … 0 29 1 16 2 47 3 14 4 5 35 • Nerede depolarsınız: 127? 6 36 7 8 9 10 11 129 25 2501   t t+1 denemeler 12 13 99  t+4 14 65 Hashing Fonksiyonları Hashing Çarpışma – İkinci dereceden Sondalama • Hash tablo dolu değilse, anahtarı dizi öğelerinde (t+12)%N, (t+22)%N … • Nerede depolarsınız: 127? 0 29 1 16 2 47 3 14 4 5 35 6 7 8 9 36 127 129  t denemeler 10 11 25 2501 12 13 99 14 65 Hashing Fonksiyonları Hashing Çarpışma – İkinci dereceden Sondalama • Anahtarları doğrusal sondalamadan daha iyi dağıtma eğilimindedir • Kümeleme sorununu hafifletir • Önlemler alınmadığı sürece, ekleme sırasında sonsuz döngü riski taşır. • Örneğin, anahtar 16'yı 0, 1, 4 ve 9 konumları zaten doluyken 16 boyutlu bir tabloya yerleştirmeyi düşünün. • Bu nedenle, tablo boyutu tekil olmalıdır. Hashing Fonksiyonları Hashing Çarpışma – Çifte Hashing • Azaltma değeri için bir hash işlevi kullanın • Hash(anahtar, i) = H1(anahtar) – (H2(anahtar) * i) • Şimdi azalma, anahtarın bir işlevidir • Hash işlevi tarafından ziyaret edilen yuvalar, ilk yuva aynı olsa bile değişecektir. • Kümelenmeyi önler • Teorik olarak ilginç, ancak ikinci bir hash işlevi değerlendirme ihtiyacı nedeniyle pratikte ikinci dereceden sondalamadan daha yavaş. Hashing Fonksiyonları Hashing Çarpışma – Çifte Hashing • x anahtarının dizinin f(x)=t öğesinde saklanmasına izin verin • Dizi: 0 1 2 3 47 4 5 6 7 35 36 65(?) 8 9 10 129 11 12 25 2501 13 14 • Bir çarpışma durumunda ne yaparsınız? • İkinci bir özet fonksiyonu f2(x)=d tanımlayın. Anahtarı dizi öğelerinde saklama girişimi (t+d)%N, (t+2d)%N, (t+3d)%N … • Ta ki boş bir yuva bulana kadar. Hashing Fonksiyonları Hashing Çarpışma – Çifte Hashing • Tipik ikinci karma işlevi f2(x)=R − ( x % R ) • Burada R bir asal sayıdır, R < N Hashing Fonksiyonları Hashing Çarpışma – Çifte Hashing • 65'i nerede saklıyorsunuz? f(65) = t = 5 • f2(x)= 11 − (x % 11) olsun f2(65) = d = 1 • Not: R=11, N=15 • Anahtarı dizi öğelerinde saklama girişimi (t+d)%N, (t+2d)%N, (t+3d)%N … • Dizi: 0 1 2 3 47 4 5 6 7 8 35 36 65    t t+1 t+2 denemeler 9 10 129 11 12 13 25 2501 14 Hashing Fonksiyonları Hashing Çarpışma – Çifte Hashing • Hash tablo dolu değilse, anahtarı dizi öğelerinde (t+d)%N, (t+2d)%N ... • f2(x)= 11 − (x % 11) olsun f2(29)=d=4 • Nerede saklarsın: 29? • Dizi: 0 1 2 47 3 4 5 35 6 36 7 65 8 9 129 10 11 25 2501 12 13 14 29  t deneme Hashing Fonksiyonları Hashing Çarpışma – Çifte Hashing • Karma tablo dolu değilse, anahtarı dizi öğelerinde (t+d)%N, (t+2d)%N ... • f2(x)= 11 − (x % 11) olsun f2(16)=d=6 • Nerede depolarsınız: 16? • Sıralamak: 0 1 2 16 47  t deneme 3 4 5 35 • Nerede depolarsınız: 14? 6 36 7 65 8 9 129 10 11 25 2501 12 13 14 29 Hashing Fonksiyonları Hashing Çarpışma – Çifte Hashing • Karma tablo dolu değilse, anahtarı dizi öğelerinde (t+d)%N, (t+2d)%N ... • f2(x)= 11 − (x % 11) olsun f2(14)=d=8 • Dizi: 0 1 2 14 16 47  t+16 denemeler 3 4 5 35 • Nerede depolarsınız: 99? 6 36 7 65  t+8 8 9 129 10 11 25 2501 12 13 14 29  t Hashing Fonksiyonları Hashing Çarpışma – Çifte Hashing • Karma tablo dolu değilse, anahtarı dizi öğelerinde (t+d)%N, (t+2d)%N ... • f2(x)= 11 − (x % 11) olsun f2(99)=d=11 • Dizi: 0 14 1 2 16 47  t+22 denemeler 3 4 5 6 35 36  t+11 • Nerede depolarsınız: 127? 7 65 8 9 129  t 10 11 25 2501 12 13 99  t+33 14 29 Hashing Fonksiyonları Hashing Çarpışma – Çifte Hashing • Karma tablo dolu değilse, anahtarı dizi öğelerinde (t+d)%N, (t+2d)%N ... • f2(x)= 11 − (x % 11) olsun f2(127)=d=5 • Dizi: 0 14 1 16 2 3 47  t+10 denemeler • Sonsuz Döngü! 4 5 35 6 36 7 65  t 8 9 129 10 11 25 2501 12 13 99  t+5 14 29 Veri Yapıları Bandırma 17 Eylül Üniversitesi Mühendislik ve Doğa Bilimleri Fakültesi Dr. Emrah DÖNMEZ Çizge Teorisi (Graph Theory) Veri Yapıları Çizge Teorisi Bir Çizge nedir? • Çizge = Bir dizi düğümler ağı • Gayri resmi olarak bir çizge, bir dizi çizgi (edge) veya okla (directed edges) birleştirilen bir dizi düğümdür (nodes). 1 4 2 5 3 6 1 2 3 4 5 6 Çizge Teorisi Çizge tabanlı temsiller • Bir problemi çizge olarak göstermek farklı bir bakış açısı sağlayabilir. • Bir problemi çizge olarak göstermek, problemi çok daha basit hale getirebilir. • Daha doğrusu, sorunu çözmek için uygun araçları sağlayabilir. Çizge Teorisi Bir problemi çizge gibi yapan durum nedir? • Bir çizgenin iki bileşeni vardır • Düğümler ve kenarlar • Çizgeye benzer problemlerde, bu bileşenlerin problem öğeleriyle doğal karşılıkları vardır. • Varlıklar düğümlerdir ve varlıklar arasındaki etkileşimler kenarlardır • En karmaşık sistemler çizge gibidir Çizge Teorisi Arkadaşlık Ağı Çizge Teorisi Bilimsel İşbirliği Ağı Çizge Teorisi Genetik etkileşim ağı Çizge Teorisi Protein-Protein etkileşim ağı Çizge Teorisi Ulaşım Ağları Çizge Teorisi Ulaşım Ağları Çizge Teorisi İnternet Çizge Teorisi Ekolojik Ağlar Çizge Teorisi Çizge Teorisi • Leonhard Euler'in “Königsberg'in Yedi Köprüsü” konulu makalesi, • 1736'da yayınlandı. Çizge Teorisi Çizge Teorisi – Çok-yüzlü Döngüler • Platonik çizgelerde Hamilton döngüleri Çizge Teorisi Elektrik Devrelerinde Ağaçlar Çizge Teorisi Kimyasal İzomerlerin Numaralandırılması Çizge Teorisi Dört Renkli Haritalar Çizge Teorisi Çizge Tanımı • G, sıralı bir üçlü G:=(V, E, f) • V, bir dizi düğüm, nokta veya köşedir. • E, elemanları kenarlar veya çizgiler olarak bilinen bir kümedir. • f bir fonksiyondur • E'nin her bir öğesini eşler • V'deki sırasız bir düğüm (node) / vertices (köşe) çiftine. Çizge Teorisi Çizge Tanımı • Düğüm (Node/Vertex) • Basit eleman • Düğüm veya nokta olarak çizilir. • G'nin düğüm kümesi genellikle V(G) veya V ile gösterilir. • Kenar (Edge) • İki elementten oluşan bir set • Bitiş köşeleri veya bitiş noktaları olarak adlandırılan iki köşeyi birleştiren bir çizgi olarak çizilir. • G'nin kenar kümesi genellikle E(G) veya E ile gösterilir. Çizge Teorisi Çizge Tanımı • V:={1,2,3,4,5,6} • E:={{1,2},{1,5},{2,3},{2,5},{3,4},{4,5},{4,6}} Çizge Teorisi Basit Çizgeler • Basit çizgeler, birden çok kenarı veya kendi kendine döngüleri olmayan çizgelerdir. Çizge Teorisi Basit Çizgeler Çizge Teorisi Yönlü Basit Çizgeler • Düğümler arası kenarların yönlü olduğu çizge türüdür. Çizge Teorisi Yönlü Basit Çizgeler • İki düğüm arasında farklı yönlü olmak üzere iki kenar olabilir, bu durum çizgeyi basit olmaktan çıkarmaz. Bu kenar iki yönlü tek bir kenar gibi ele alınabilir. Çizge Teorisi Basit olmayan Çizgeler • Basit çizgeler, birden çok kenarı (iki aynı düğüm arasında) veya kendi kendine döngüleri (aynı düğümde kenarın iki ucu) olmayan çizgelerdir. Basit çizge Çok kenarlı basit olmayan çizge Döngü içeren basit olmayan çizge Çizge Teorisi Basit olmayan Çizgeler Çizge Teorisi Yönlü basit olmayan Çizgeler • Kenarların yönleri vardır • Kenar, sıralı bir düğüm çiftidir döngü çoklu akış akış düğüm Çizge Teorisi Yönlü basit olmayan Çizgeler Çizge Teorisi Yönlü basit olmayan Çizgeler • genellikle w: E→R ağırlık fonksiyonu ile verilen, her kenarın ilişkili bir ağırlığa sahip olduğu bir çizgedir. 1 1.2 2 2 0.2 0.3 0.5 4 1 1.5 5 0.5 3 6 5 1 4 3 2 5 3 6 Çizge Teorisi Yapılar ve Yapısal Metrikler • Çizge yapıları, bir çizgenin ilginç veya önemli bölümlerini izole etmek için kullanılır. • Yapısal metrikler, bir çizgenin yapısal bir özelliğinin ölçümünü sağlar • Global metrikler bütün bir çizgeye atıfta bulunur • Yerel metrikler, bir çizgedeki tek bir düğüme atıfta bulunur Çizge Teorisi Çizge Yapıları • Bir çizgenin ilginç bölümlerini belirleyin • Etki alanına özgü önemli bir yapı oluşturur veya çizge özelliklerine önemli ölçüde katkıda bulunurlar • Belirli özelliklere sahip olan veya belirli şekillerde birbirleriyle ilişkili olan bir çizgedeki düğümlerin ve kenarların bir alt kümesi Çizge Teorisi Bağlanabilirlik • Bir çizge bağlantılılıdır (connected) eğer; • bir kenar dizisini izleyerek herhangi bir düğümden diğerine geçebiliyorsak VEYA • herhangi iki düğüm bir yolla bağlantılıysa. • Herhangi bir düğümden başka bir düğüme yönlendirilmiş bir yol varsa, yönlendirilmiş bir çizge güçlü şekilde bağlantılıdır. Çizge Teorisi Bileşen • Bağlantısı kesilen her çizge, bir dizi bağlı bileşene bölünebilir. Bağlı bileşenlerin düğüm sayısı: 2, 3 ve 2 Çizge Teorisi Derece (Yönsüz Çizge) • Bir düğüme bağlı kenar sayısıdır. Örn: 5 numaralı düğümün derecesi 3’ tür Çizge Teorisi Derece (Yönlü Çizge) • Derece içi: Giren kenar sayısı • Dış-derece: Ayrılan kenar sayısı • Derece = indeg + outdeg outdeg(1)=2 indeg(1)=0 outdeg(2)=2 indeg(2)=2 outdeg(3)=1 indeg(3)=4 Çizge Teorisi Derece: Basit Bilgiler • G, m kenarlı bir çizgeyse,  deg(v) = 2m = 2 |E| • G bir yönlü çizge ise,  indeg(v) =  outdeg(v) = |E| • Tek dereceli düğümlerin sayısı çifttir Çizge Teorisi Derece Çizge Teorisi Yürüyüş (Walk) • Bir çizgede k uzunluğundaki bir yürüyüş, çizge formundaki k (farklı olması gerekmez) kenarlarının ardışık halidir. • uv,vw,wx,…,yz. • Bu yürüyüş uvwx…xz ile gösterilir ve u ile z arasındaki yürüyüş olarak adlandırılır. 1->2->3->4->2->1->3 Not: Düğümler ve Kenarlar tekrar edilebilir. Çizge Teorisi Yürüyüş (Walk) • Açık yürüyüş - Başlangıç ve bitiş düğümleri farklıysa, • yani başlangıç düğümü ve son varış düğümü farklıysa, yürüyüşün açık yürüyüş olduğu söylenir. • Kapalı yürüyüş - Başlangıç ve bitiş köşeleri aynıysa, • yani bir yürüyüş aynı düğümde başlayıp bitiyorsa, yürüyüşe kapalı yürüyüş denir. 1->2->3->4->5->3 1->2->3->4->5->3->1 açık bir yürüyüştür. kapalı bir yürüyüştür. Çizge Teorisi Patika (Trail) • Patika, hiçbir kenarın tekrarlanmadığı açık bir yürüyüştür. • Düğüm tekrar edilebilir. 1->3->8->6->3->2 patika 1->3->8->6->3->2->1 kapalı bir patikadır Çizge Teorisi Devre (Circuit) • Bir çizgenin, bir kenarın tekrarlanmadığı, ancak varış noktasının tekrarlanabileceği ve kapalı olduğu, yani kapalı bir patika olduğu şekile benzer. • Düğüm tekrar edilebilir. • Kenar tekrarlanamaz. 1->2->4->3->6->8->3->1 bir devredir. Devre kapalı bir yoldur. Sadece tekrarlanan düğümlere sahip olabilir. Çizge Teorisi Yol (Path) • Ne köşelerin ne de kenarların tekrarlanmadığı bir patikadır, yani bir çizgede, bir köşeyi ve/veya kenarı tekrar etmeyeceğimiz şekilde hareket ederiz. Yol aynı zamanda bir patika olduğundan, aynı zamanda açık bir yürüyüştür. • Düğüm tekrarlanmaz • Kenar tekrarlanmaz 6->8->3->1->2->4 bir yoldur. Çizge Teorisi Döngü (Cycle) • Çizgeyi, bir düğümü veya bir kenarı tekrar etmeyeceğimiz şekilde geçip, başlangıç ve bitiş düğümleri aynı olacak şekilde gezmektir, yani ancak başlangıç ve bitiş düğümleri tekrar edilebilir. • Köşe tekrarlanmaz • Kenar tekrarlanmaz 1->2->4->3->1 bir döngüdür. Döngü kapalı bir yoldur. Tekrarı olamaz (ne kenarlar ne de düğümler). Çizge Teorisi (Graph Theory) Veri Yapıları Bandırma 17 Eylül Üniversitesi Mühendislik ve Doğa Bilimleri Fakültesi Dr. Emrah DÖNMEZ Çizge Teorisi (Graph Theory) Veri Yapıları Çizge Teorisi Özel Tip Çizgeler • Boş Çizgeler / Kenarsız çizge • Kenarı olmayan çizgedir • Null Çizge • Düğüm yoktur. • Haliyle kenarda olmaz Çizge Teorisi Ağaçlar • Bağlı Döngü İçermeyen Çizge • İki düğüm arasında tam olarak bir yol vardır Çizge Teorisi Özel Ağaçlar • Yollar • Yıldızlar Çizge Teorisi Düzenli/Düzgün Çizgeler • Bağlı Çizgedir • Tüm düğümler aynı dereceye sahiptir Çizge Teorisi Özel Düzenli/Düzgün Çizgeler: Döngüler C3 C4 C5 Çizge Teorisi İkili / Çift Taraflı Çizgeler • V, (u,v)  E olmak üzere 2 küme/set olacak şekilde V1 ve V2'ye bölünebilir. • ya u  V1 ve v  V2 • VEYA v  V1 ve u  V2. Çizge Teorisi Tam Çizgeler • Her düğüm çifti bitişiktir • n(n-1)/2 kenarı vardır Çizge Teorisi Tam İkili / Çift Taraflı Çizgeler • Tam Çizgenin İki Parçalı Varyasyonu’dur • Bir kümenin her düğümü, diğer kümedeki diğer tüm düğümlere bağlıdır. Çizge Teorisi Düzlemsel Çizgeler • İki kenarı kesişmeyecek şekilde bir düzlemde çizilebilirler. • K4, düzlemsel olan en büyük tam çizgedir Çizge Teorisi Alt Çizgeler • Düğüm ve kenar kümeleri, G'nin alt kümeleridir. • G çzgesinin üst çizgesi (süper çizge), G'yi alt çizge olarak içeren bir çizgedir. Çizge Teorisi Özel Alt Çizgeler: Klikler • Bir klik, maksimum tam bağlı bir alt çizgedir. A B C D E F G H I Çizge Teorisi Kapsayan / Yayılan Alt Çizgeler • Alt çizge H, G ile aynı düğüm setine (kümesine) sahiptir. • Tüm kenarlar olmayabilir • "H, G'yi kapsar". Çizge Teorisi Kapsayan / Yayılan Ağaçlar • G bağlantılı bir çizge olsun. • O zaman G'deki yayılan ağaç, her düğümü içeren ve aynı zamanda bir ağaç olan G'nin bir alt çizgesidir. Çizge Teorisi İzomorfizm / Eşbiçimlilik • Bijeksiyon / Bire bir örten, yani bire bir eşleme: • f : V(G) -> V(H) • G'den u ve v, yalnızca ve ancak f(u) ve f(v) H'de bitişikse bitişiktir. • İki çizge arasında bir izomorfizm / eşbiçimlilik oluşturulabiliyorsa, bu çizgelerin eşbiçimli olduğunu söyleriz. Çizge Teorisi İzomorfizm / Eşbiçimlilik Problemi • İki çizgenin izomorfik olup olmadığını belirleme • Bu çizgeler çok farklı görünse de izomorfiktir; aralarında bir izomorfizm • f(a)=1 f(b)=6 f(c)=8 f(d)=3 • f(g)=5 f(h)=2 f(i)=4 f(j)=7 Çizge Teorisi Temsil (Matris) • İnsidans / Sıklık Matrisi • VxE • [köşe, kenarlar] kenarın verilerini içerir • Komşuluk / Bitişiklik matrisi • VxV • Boole değerleri (bitişik veya değil) • Veya Kenar Ağırlıkları Çizge Teorisi Matrisler 1 2 3 4 5 6 1,2 1,5 2,3 2,5 3,4 4,5 4,6 1 1 0 0 0 0 0 1 0 1 1 0 0 0 0 0 1 0 1 0 0 0 0 0 0 1 1 1 0 1 0 1 0 1 0 0 0 0 0 0 0 1 1 2 3 4 5 6 1 0 1 0 0 1 0 2 1 0 1 0 1 0 3 0 1 0 1 0 0 4 0 0 1 0 1 1 5 1 1 0 1 0 0 6 0 0 0 1 0 0 Çizge Teorisi Temsil (Liste) • Kenar Listesi • düğüm çiftleri (yönlendiriliyorsa sıralanır) • İsteğe bağlı olarak ağırlık ve diğer veriler olabilir. • Komşuluk Listesi (düğüm listesi) Çizge Teorisi Temsil (Liste) • Bitişik liste gösterimi • bir |V| listeler dizisi, V'deki her düğüm için bir atama yapılır. • Her u  V için ADJ [u] tüm bitişik düğümleri gösterir. Çizge Teorisi Kenar ve Düğüm Listeleri Edge List 12 12 23 25 33 43 45 53 54 Node List 122 235 33 435 534 Çizge Teorisi Ağırlıklı Çizgeler için Kenar Listeleri Edge List 1-2 → 1.2 2-4 → 0.2 4-5 → 0.3 4-1 → 0.5 5-4 → 0.5 6-3 → 1.5 Çizge Teorisi Mesafe Matrisi • |V| x |V| matris D = (dij ) öyle ki dij, i ve j arasındaki topolojik uzaklıktır. 1 2 3 4 5 6 1 0 1 2 2 1 3 2 1 0 1 2 1 3 3 2 1 0 1 2 2 4 2 2 1 0 1 1 5 1 1 2 1 0 2 6 3 3 2 1 2 0 Çizge Teorisi (Graph Theory)