Levenshtein uzaklığı 2 karakter katarı arasında tanımlanmış, bir katardan diğer katara dönüşümde minimum değişim sayısını verir. dönüşüm işlemlerinde ekleme, silme ve katar içinde karakter değişimleri kabul edilmektedir. Aynı zamanda “değişim uzaklığı (edit distance)” olarak da bilinmektedir. Örn: levenstein_distance(samantha,Sam) = 5 Pseudo kodu int LevenshteinDistance(char s[1..m], char t[1..n]) { declare int d[0..m, 0..n] for i from 0 to m d[i, 0] := i for j from 0 to n d[0, j] := j for j from 1 to n { for i from 1 to m { if s[i] = t[j] then d[i, j] := d[i-1, j-1] else d[i, j] := minimum ( d[i-1, j] + 1, // deletion d[i, j-1] + 1, // insertion d[i-1, j-1] + 1 // substitution ) } } return d[m,n] }       C Kodu: #include <stdlib.h> #include <malloc.h> #include <string.h> int levenshtein_distance(char *s,char*t); int minimum(int a,int b,int c); int levenshtein_distance(char *s,char*t) { int k, i, j, n, m, cost, *d, distance; n = strlen(s); m = strlen(t); if(n!=0 && m!=0) { d = malloc((sizeof(int))*(m+1)*(n+1)); m++; n++; for(k=0;k<n;k++) d[k]=k; for(k=0;k<m;k++) d[k*n]=k; for(i=1;i<n;i++) for(j=1;j<m;j++) { if(s[i-1]==t[j-1]) cost=0; else cost=1; d[j*n+i]=minimum(d[(j-1)*n+i]+1,d[j*n+i-1]+1,d[(j-1)*n+i-1]+cost); } distance=d[n*m-1]; free(d); return distance; } else return -1; } int minimum(int a,int b,int c) { int min=a; if(b<min) min=b; if(c<min) min=c; return min; }   Java Kodu: public static int getLevenshteinDistance (String s, String t) { if (s == null || t == null) { throw new IllegalArgumentException("Strings must not be null"); } int n = s.length(); int m = t.length(); if (n == 0) { return m; } else if (m == 0) { return n; } int p[] = new int[n+1]; int d[] = new int[n+1]; int _d[]; int i; int j; char t_j; int cost; for (i = 0; i<=n; i++) { p[i] = i; } for (j = 1; j<=m; j++) { t_j = t.charAt(j-1); d[0] = j; for (i=1; i<=n; i++) { cost = s.charAt(i-1)==t_j ? 0 : 1; d[i] = Math.min(Math.min(d[i-1]+1, p[i]+1), p[i-1]+cost); } _d = p; p = d; d = _d; } return p[n]; }   Kaynaklar: http://www.merriampark.com/ldc.htm http://www.merriampark.com/ldjava.htm .csharpcode, .csharpcode pre { font-size: small; color: black; font-family: consolas, "Courier New", courier, monospace; background-color: #ffffff; /*white-space: pre;*/ } .csharpcode pre { margin: 0em; } .csharpcode .rem { color: #008000; } .csharpcode .kwrd { color: #0000ff; } .csharpcode .str { color: #006080; } .csharpcode .op { color: #0000c0; } .csharpcode .preproc { color: #cc6633; } .csharpcode .asp { background-color: #ffff00; } .csharpcode .html { color: #800000; } .csharpcode .attr { color: #ff0000; } .csharpcode .alt { background-color: #f4f4f4; width: 100%; margin: 0em; } .csharpcode .lnum { color: #606060; } tweetmeme_source = 'makcura'; tweetmeme_service = 'bit.ly'; Tags: | Categories: C | JAVA | Algoritma
Gale-Shapley uygun evlenme problemine çözüm sağlar. 2 set halinde bulunan elemanları birbiri ile eşleştirir. Uygun evlendirme probleminde bu 2 set eleman kızlar ve erkeklerdir. Ancak Gale-Shapley algoritması başka setler için de uygun çözümdür. Uygulanışı: Setlerimize “Erkek” ve “Bayan” adını verelim. Her setimizde eşit sayıda elaman ve her elemanın karşı setteki elamanları tercih sıralaması var. Bu bir evlilik eşleşmesi olsun.             Sıradan elemanlarımıza bakıyoruz. Xavier 1. olarak Amy’i tercih ediyor. Amy’nin şuanda eşi yok. Xavier – Amy eşleşmesi yapılır. Diğer eleman Yancey’in ilk tercihi Bertha. Bertha’nın şuanda eşi yok. Yancey – Bertha eşleşmesi yapılır. Son eleman Zeus’un ilk tercihi Amy – Xavier eşleşmesi var. Amy, Xavier’i Zeus’a göre daha yüksek öncelikle tercih ediyor. Eş bozulmaz. Eğer daha alçak öncelikle tercih etseydi Xavier – Amy eşleşmesi bozulacak, Zeus – Amy  eşleşmesi kurulacak, işlemlerde geriye gidilip Xavier’e sıradan yeni eşleşme yapılmak durumunda kalınacaktı. Amy’i atlayan Zeus’un sıradaki tercihi Bertha. Bertha – Yancey  eşleşmesi var ve Yancey’in öceliği daha yüksek. Eşlik yine bozulmadı. Zeus’un son tercihi Clare şuanda eşli değil. Zeus – Clare eşlemesi yapıldı.   Yukarıdaki örnekte erkekler kızlara önerdi, kızlar karar verdi. Eğer kızlar erkeklere önerseydi ve kızlar karar verseydi nasıl olurdu ? Bunu da siz bulun. Algoritma: function stableMatching { Initialize all <I>m</I> ∈ M and <I>w</I> ∈ W to <I>free</I> while ∃ <I>free</I> man <I>m</I> who still has a woman w to propose to { w = m's highest ranked such woman who he has not proposed to yet if w is <I>free</I> (m, w) become <I>engaged</I> else some pair (m', w) already exists if w prefers m to m' (m, w) become <I>engaged</I> m' becomes <I>free</I> else (m', w) remain <I>engaged</I> } } Tags: , , | Categories: Algoritma
Huffman kodlaması, girilen veriyi sıkıştırmak amacıyla kullanılan bir sıkıştırma algoritmasıdır. David A. Huffman tarafından 1952 yılında geliştirilmiştir. Günlük hayatta bize gösterilen verilerde her karakterin 8 bitlik ASCII karşılığı vardır. Her bir karakter bellekte 8 bitlik değer ile saklanmaktadır. Ancak bu durum bellek sıkıntısı olan uygulamalar için sıkıntı yaratmaktadır. Huffman’ın geliştirdiği algoritmada, veri içerinde kullanılan her bir karakterin belli bir frekansı (kullanım sıklığı) vardır. Bir karakterin frekansı ne kadar fazla ise bellekte yer aldığı alan o kadar fazladır. Bu sebepten ötürü Huffman, frekansı büyük olan karakterlerin bellekte 8 bit yerine daha az bitle saklanması durumunda yerden kazanılabileceğini düşünmüş ve algoritmasını geliştirmiştir.   Algoritma şu basamakları takip ederek uygulayabiliriz: Karakterler kodlanmadan önce veri içerisindeki her karakter tek tek taranır, frekansları belirlenir. Karakterler frekanslarına göre azalan ya da artan sırada sıralanırlar. (Sıralama için  sıralama algoritmalarından herhangi biri kullanılabilir.   Sıralamanıza göre en küçük 2 frekanslı karakter alınarak ikili ağaç oluşturulur. Frekansları toplamı kök düğüme yazılır. Sonra tekrar sıralama yapılır (ağaçları sıralarken kök düğümdeki değer önemsenir), en küçük 2 birimden tekrar ikili ağaç oluşturulur.  Sıralama işlemi sırada sadece ve sadece tek bir ağaç kalana kadar devam eder. Ağaçta dikkat edilmesi noktalardan biri yaprakların hepsinde harf vardır. Harfler arada dallarda yer almamaktadır. Ağaç oluşturulduktan sonra ağacın kollarına numaralar verilir. Her kök düğümden çıkan sol dala 1, sağ dala 0 ya da sol dala 0, sağ dala 1 verilir. Kök düğümden yapraklara inerken her dal üstündeki karakter okunur, böylece karakterin  yeni değeri ortaya çıkar. Örnek olarak yukarıdaki ağaçta yer alan örneklerin yeni değerleri: 'g'     00 'o'     01 'p'     1110 'h'     1101 'e'     101 'r'      1111 's'     1100 '  '     100 Yukarıdaki gibi kodları elde ettikten sonra veri içerisindeki tüm veriler baştan okunur. Her karaktere karşılık gelen kod yerine yerleştirilir. Böylece veri verimizin boyutunu düşürmüş olduk. Tags: , , , , , | Categories: Algoritma

Haziran 1006

Bipartite Graph

Bipartite graph veya bigraph olarak bilinen bu graf, kendi aralarında bağımsız (bağlantı olmayan) sadece karşısındaki kümedeki düğümlerle bağlantısı olan 2 düğüm kümesinden oluşur. Graflar genelde karşımıza bu şekilde çıkmazlar. Daha karmaşıklardır. Onları bu hale getirmek uğraştırır. Bir grafın bipartite olup olmadığını öğrenmek için başka bir yöntem vardır: Kendimize bir kök (başlangıç) noktası seçeriz ve bu düğümü Mavi boyarız. Bu düğümden çıkan her kenarında sonunda yer alan düğümleri Kırmızı boyarız. Kırmızı düğümlerden ıkan her kenarın sonundaki düğümü de Mavi boyarız. Tüm renklendirme işlemi bittiğinde her kenarın her iki tarafındaki düğümlerin renkleri farklı ise graf Bipartite graph özelliğini taşır. Ancak bir tane bile uçları aynı renkte kenar olması durumunda graf bipartite değildir. En çok kullanıldığı alan eşleme problemleridir (Matching Problems). Aynı zamanda şifreli şekilde gelen verilerin çözülmesinde de kullanılabilir. Tags: , , , | Categories: Algoritma
BFS, kök düğümden başlayarak tüm elemanları tarayan ve komşulukları ortaya çıkaran bir graf arama algoritmasıdır. Çalışması sırasında son düğüme oluşana dek, keşfedilmiş tüm düğümlere komşu henüz keşfedilmemiş düğümleri keşfetme mantığını yürütür. Diklemesine değil, yataylamasına büyümeyi hedefler. Düğümlerin keşfediliş sıralarına göre farklı ağaçlar oluşturulabilir.   Pseudocode: unmark all vertices choose some starting vertex x mark x list L = x tree T = x while L nonempty choose some vertex v from front of list visit v for each unmarked neighbor w     mark w     add it to end of list     add edge (v,w) to T Liste olarak kuyruk tutmalıyız. FIFO kuralı uygulanacak.   Kuyruk kullanmadan da yapılabilir. Aşağıda yer alan C++ kodunda kuyruk kullanılmamıştır. bool Discovered[num]; for (int k = 0; k < num; k++) Discovered[k] = false; Node BFStree[num]; int i = 0; BFStree[i].data = 0; Node *temp; Discovered[i] = true; while ( i < num ) { temp = &BFStree[i]; for( int k = 0 ; k < num ; k++ ) { if ( matris[i][k] == 1 && !Discovered[k] ) { Discovered[k] = true; Node *newNode = new Node(k); temp->next = newNode; temp = newNode; } } i++; BFStree[i].data = i; } Not: Yukarıdaki kodu çalıştırmak için Adjacency matris kullanılmıştır. “num” adındaki değişken ise grafta yer alan eleman sayısını göstermektedir.   Sonuç olarak Adjencency matrisi sol aşağıdaki gibi olan bir grafın bfs algoritması sonucu oluşan spanning ağacı sağ aşağıdaki gibidir. 0 1 1 0 0 0 0 0                               1 2 3 1 0 1 1 1 0 0 0     2 4 5 1 1 0 0 1 0 1 1     3 7 8 0 1 0 0 1 0 0 0                   4     0 1 1 1 0 1 0 0     5 6   0 0 0 0 1 0 0 0     6     0 0 1 0 0 0 0 1     7     0 0 1 0 0 0 1 0     8     Tags: , , , , | Categories: Algoritma | C++
Counting sort veri kümesinde (sayılardan oluşuyor) yer alan elemanların aralığını kullanarak sıralama yapan vir sıralama algoritmasıdır. 1954 yılında Harold H. Seward tarafından yarılmıştır. Counting sort çalışması sırasında giren dizi haricinde 2 tane boş dizi yaratır. A: Sıralanacak elemanların bulunduğu dizi B: Sıralanmış dizi C: A dizisindeki tekrarlanan eleman sayısını tutan dizi   Algoritmanın uygulanışı şu şekildedir: A dizisindeki elemanlar tek tek dolaşılarak B dizisi doldurulur. Mesela; A dizinde 1 elemanında 2 tane bulunmaktadır, 2 elamanından hiç yoktur. C dizisi, en soldaki birimden başlayarak n = n + (n-1) şeklinde artırılacak şekilde yeniden oluşturulur. Bu adımda A dizisinin elemanları sondan başlayarak taranmaya başlanır. Her elemanın içeriği kontrol edilerek C dizisindeki karşılığı bulunur. Bu karşılık A dizinden aldığımız elemanı B dizisinin hangi gözüne yazmamız gerektiğini gösteriyor.   İşlem sonucunda B dizimiz şu şekilde oluşmuştur:     Örnek C kodu: void counting_sort(int *array, int size) { int i, min, max; min = max = array[0]; for(i = 1; i < size; i++) { if (array[i] < min) min = array[i]; else if (array[i] > max) max = array[i]; } int range = max - min + 1; int *count = (int *) malloc(range * sizeof(int)); for(i = 0; i < range; i++) count[i] = 0; for(i = 0; i < size; i++) count[ array[i] - min ]++; int j, z = 0; for(i = min; i <= max; i++) for(j = 0; j < count[ i - min ]; j++) array[z++] = i; free(count); } .csharpcode, .csharpcode pre { font-size: small; color: black; font-family: consolas, "Courier New", courier, monospace; background-color: #ffffff; /*white-space: pre;*/ } .csharpcode pre { margin: 0em; } .csharpcode .rem { color: #008000; } .csharpcode .kwrd { color: #0000ff; } .csharpcode .str { color: #006080; } .csharpcode .op { color: #0000c0; } .csharpcode .preproc { color: #cc6633; } .csharpcode .asp { background-color: #ffff00; } .csharpcode .html { color: #800000; } .csharpcode .attr { color: #ff0000; } .csharpcode .alt { background-color: #f4f4f4; width: 100%; margin: 0em; } .csharpcode .lnum { color: #606060; } Örnek C++ kodu: #include <iostream> #include <vector> using namespace std; void countingSort(vector<int>& Array) { int Min, Max; Min = Max = Array[0]; for(int i = 1; i < Array.size(); i ++) { if(Array[i] < Min) Min = Array[i]; if(Array[i] > Max) Max = Array[i]; } int Range = Max - Min + 1; vector<int> Count; Count.resize(Range); for(int i = 0; i < Range; i ++) Count[i] = 0; for(int i = 0; i < Array.size(); i ++) Count[Array[i] - Min] ++; int Index = 0; for(int i = Min; i <= Max; i ++) for(int j = 0; j < Count[i - Min]; j ++) Array[Index ++] = i; } .csharpcode, .csharpcode pre { font-size: small; color: black; font-family: consolas, "Courier New", courier, monospace; background-color: #ffffff; /*white-space: pre;*/ } .csharpcode pre { margin: 0em; } .csharpcode .rem { color: #008000; } .csharpcode .kwrd { color: #0000ff; } .csharpcode .str { color: #006080; } .csharpcode .op { color: #0000c0; } .csharpcode .preproc { color: #cc6633; } .csharpcode .asp { background-color: #ffff00; } .csharpcode .html { color: #800000; } .csharpcode .attr { color: #ff0000; } .csharpcode .alt { background-color: #f4f4f4; width: 100%; margin: 0em; } .csharpcode .lnum { color: #606060; } Kaynak: en.wikipedia.org net.pku.edu.cn Tags: , | Categories: C | C++ | Algoritma

Şubat 1021

Radix Sort

Radix Sort algoritması, sayıları sıralamaya yarayan bir sıralama algoritmasıdır. Tarihte ilk kullanımı 1887 yılında Herman Hollerith’un 1887 yılındaki kataloglama makinesi çalışmalarına dayanmaktadır. Karakter katarları ve tarihler de sayma sayısı olarak temsil edilebildiklerinden (ASCII), radix sort sayılar yanından karakter katarlarını da sıralayabilir. Sıralama işlemi O(kN) zamanda gerçeklenir. N: Veri kümesinde yer alan eleman sayısı, k: Veri kümesinde yer alan elemanların en büyük basamak sayısı Basamakları kullanarak sıralama işlemi yapılır. İlk olarak en küçük basamağa (en sağ) göre sıralanır. En büyük basamağa doğru ilerlenir. Her basamakta sıralama işlemi tekrarlanır. Böylece elimizde küçükten büyüğe (ya da büyükten küçüğe – isteğe bağlı) sıralanmış veri kümesi kalmış olur.   Örnek C++ kodu: #include <iostream.h> #include <stdlib.h> #include <string.h> void radix (int byte, long N, long *source, long *dest) { long count[256]; long index[256]; memset (count, 0, sizeof (count)); for ( int i=0; i<N; i++ ) count[((source[i])>>(byte*8))&0xff]++; index[0]=0; for ( i=1; i<256; i++ ) index[i]=index[i-1]+count[i-1]; for ( i=0; i<N; i++ ) dest[index[((source[i])>>(byte*8))&0xff]++] = source[i]; } void radixsort (long *source, long *temp, long N) { radix (0, N, source, temp); radix (1, N, temp, source); radix (2, N, source, temp); radix (3, N, temp, source); } void make_random (long *data, long N) { for ( int i=0; i<N; i++ ) data[i]=rand()|(rand()<<16); } long data[100]; long temp[100]; void main (void) { make_random(data, 100); radixsort (data, temp, 100); for ( int i=0; i<100; i++ ) cout << data[i] << '\n'; } .csharpcode, .csharpcode pre { font-size: small; color: black; font-family: consolas, "Courier New", courier, monospace; background-color: #ffffff; /*white-space: pre;*/ } .csharpcode pre { margin: 0em; } .csharpcode .rem { color: #008000; } .csharpcode .kwrd { color: #0000ff; } .csharpcode .str { color: #006080; } .csharpcode .op { color: #0000c0; } .csharpcode .preproc { color: #cc6633; } .csharpcode .asp { background-color: #ffff00; } .csharpcode .html { color: #800000; } .csharpcode .attr { color: #ff0000; } .csharpcode .alt { background-color: #f4f4f4; width: 100%; margin: 0em; } .csharpcode .lnum { color: #606060; } Kaynak: www.brpreiss.com www.cubic.org Tags: , | Categories: Algoritma | C++
Kendini dengeleyen ikili arama ağacı veri yapısıdır. Orijinal yapı 1972 yılında Rudolf Bayer tarafından “Simetrik ikili B-Ağaçları” olarak oluşturuldu. Fakat 1978 yılında Leonidas J. Guibas ve Robert Sedgewick tarafından yayımlanan makalede bugünkü adını almıştır. Red-black ağaçlar yapı bakımından biraz karmaşıktır. Arama, ekleme ve silme işlemlerini           O(log n) zamanda gerçekleştirirler (ağaçtaki eleman sayısı n). Bazı kuralları vardır: Her düğüm siyah veya kırmızıdır. Kök her zaman siyahtır. Tüm yapraklar siyahtır. Kırmızı düğümün çocukları siyah olmak zorundadır. Seçilen herhangi bir düğümden, altındaki tüm yapraklara olan yolda aynı sayıda siyah düğüm olmak sorundadır.   Diğer tüm kurallar, ikili arama ağacındaki gibidir.     Ekleme ve çıkartma işlemlerinde siyah düğüm sayısına dikkat edilmelidir. Tags: , , , | Categories: Algoritma
Quicksort algoritması, yapısındaki basitlik ve çalışmasındaki hızlılığa bağlı olarak günümüz bilgisayar sistemlerinde önemli yer etmiş bir sıralama algoritmasıdır. 1960 yılında küçük bir İngiliz şirketi olan Elliot Brothers'ta çalışan C. A. R. Hoare tarafından geliştirilmiştir. Θ(nlogn) çalışma zamanında çalışan algoritmanın çalışma şekli çok basittir: Sıralanmak istenen veri kümesinden bir sayı pivot olarak seçilir. (Genelde dizinin en son elemanıdır) Veri kümesindeki her eleman tek tek kontrol edilir. Pivotun değerinden küçük elemanlar pivotun sol tarafına, büyük elemanlar pivotun sağ tarafına taşınır. Pivotun sağ ve sol tarafı şeklinde 2 veri kümesine ayrılır ve algoritma tarafından tekrar işlenir. Yukarıdaki basamaklar, fonksiyona giren veri kümesinde 1 eleman kalıncaya kadar devam eder. Sonunda tüm veri kümeleri bir araya getirilir.   Pseudocode: function quicksort(array) var list less, greater if length(array) ≤ 1 return array select and remove a pivot value pivot from array for each x in array if x ≤ pivot then append x to less else append x to greater return concatenate(quicksort(less), pivot, quicksort(greater))   Örnek C++ kodu: void quickSort(int arr[], int left, int right) { int i = left, j = right; int tmp; int pivot = arr[(left + right) / 2]; while (i <= j) { while (arr[i] < pivot) i++; while (arr[j] > pivot) j--; if (i <= j) { tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp; i++; j--; } }; if (left < j) quickSort(arr, left, j); if (i < right) quickSort(arr, i, right); } .csharpcode, .csharpcode pre { font-size: small; color: black; font-family: consolas, "Courier New", courier, monospace; background-color: #ffffff; /*white-space: pre;*/ } .csharpcode pre { margin: 0em; } .csharpcode .rem { color: #008000; } .csharpcode .kwrd { color: #0000ff; } .csharpcode .str { color: #006080; } .csharpcode .op { color: #0000c0; } .csharpcode .preproc { color: #cc6633; } .csharpcode .asp { background-color: #ffff00; } .csharpcode .html { color: #800000; } .csharpcode .attr { color: #ff0000; } .csharpcode .alt { background-color: #f4f4f4; width: 100%; margin: 0em; } .csharpcode .lnum { color: #606060; } Tags: , | Categories: C++ | Algoritma
Bilgisayar bilimlerinde kullanılan bir sıralama algoritmasıdır. Merge Sort algoritması, 1945 yılında John von Neumann tarafından bulunmuştur. Merge Sort, sıralanması istenen veri kümesini 2’ye bölme ve karşılaştırma işlemleri yaparak sıralamayı gerçekler. zamanda gerçeklenen algoritmanın algoritması aslında günlük hayatta çok sık başvurduğumuz bir yöndemdir: Sıralı olmayan listeyi ortadan eşit olarak iki alt listeye ayırır. Alt listeleri kendi içinde sıralar. Sıralı iki alt listeyi tek bir sıralı liste olacak şekilde birleştirir.     Örnek C++ kodu: void mergesort (int *a, int l, int r) { int m; if (l<r) { m = (l+r)/2; mergesort(a,l,m); mergesort(a,m+1,r); merge (a,l,m,r); } } void merge (int *a, int l, int m, int r) { int b[SIZE]; int h,i,j,k; i = l; j = m+1; k = l; while (i<=m && j<=r) { if (a[i] <= a[j]) { b[k] = a[i]; i = i+1; } else if (a[i] > a[j]) { b[k] = a[j]; j = j+1; } k = k+1; } if (i>m) { for (h=j; h<=r; h++) b[k+h-j] = a[h]; } else if (j>r) { for (h=i; h<=m; h++) b[k+h-i] = a[h]; } for (h=l; h<=r; h++) a[h] = b[h]; } .csharpcode, .csharpcode pre { font-size: small; color: black; font-family: consolas, "Courier New", courier, monospace; background-color: #ffffff; /*white-space: pre;*/ } .csharpcode pre { margin: 0em; } .csharpcode .rem { color: #008000; } .csharpcode .kwrd { color: #0000ff; } .csharpcode .str { color: #006080; } .csharpcode .op { color: #0000c0; } .csharpcode .preproc { color: #cc6633; } .csharpcode .asp { background-color: #ffff00; } .csharpcode .html { color: #800000; } .csharpcode .attr { color: #ff0000; } .csharpcode .alt { background-color: #f4f4f4; width: 100%; margin: 0em; } .csharpcode .lnum { color: #606060; } Tags: , | Categories: Algoritma | C++