Bu algoritmanın amacı, bir şekil (graph) üzerindeki, bir kaynaktan (source) bir hedefe(target veya sink) giden en kısa yolu bulmaktır. Algoritma ağırlıklı şekiller (weighted graph) üzerinde çalışır. Kabaca, bütün düğümler için bütün kenarları dolaşır. Dolayısıyla performansı düğüm sayı ile kenar sayısının çarpımı olarak düşünülebilir. O( V E )

Algoritma aşağıdaki şekildedir:

Bütün düğümlere sonsuz mesafesini ata

Her düğüm için

    Her kenar için

        Düğümün üzerindeki mesafeden daha küçük mesafe bulduysan

            Düğüm mesafesini ve düğüme gelinen düğümü güncelle

Yukarıdaki kodda görüldüğü üzere, iç içe iki döngü, kenar ve düğüm sayısı kadar dönmektedir. Ayrıca, bir düğümdeki değerin güncellenmesi sırasında, hangi düğümden gelindiği bilgisi de tutulmaktadır. Bu durum eksi yüklü kenarlar için çözüm oluşturur. Örneğin Dijkstra algoritmasında olan ve negatif değerli kenarlardan kaynaklanan döngüye girilme ihtimali, Bellman-Ford algoritmasında bulunmaz.

Algoritma Dijkstra algoritmasında olduğu gibi en küçük değere sahip olan kenardan gitmek yerine bütün graf üzerindeki kenarları test eder. Bu sayede aç gözlü yaklaşımının (greedy approach) handikabına düşmez ve her düğüme sadece bir kere bakarak en kısa yolu bulmuş olur.

Öncelikle eksi değerde düğüm bulunmayan bir örnek üzerinden algoritmayı çalıştıralım.

Öncelikle düğümlere değer ataması yapılıyor. Bütün düğümlere ¥ sonsuz değeri atanıyor.

Ayrıca başlangıç düğümü olarak A, Hedef düğüm olarak da E düğümünü tanımlayalım. Bu düğümleri algoritmanın sonunda kontrol için kullanacağız.

A başlangıç olduğu için 0 değerine sahip.

Önce dolaşacağımız düğümler için bir sıra oluşturalım. Bu örnekte alfabetik olarak düğümleri dolaşacağız ancak bu durum tamamen rast geledir.

Düğüm sıramız: A,B,C,D,E,F olmuş oluyor.

Şimdi de kenarları sıralayalım:

AB 2

AC 1

BE 2

BF 5

CF 2

CD 1

DF 5

DE 7

Bellman-Ford algoritması işte bu kenarları teker teker dolaşması itibariyle dijkstradan ayrılır. Sırayla yukarıdaki kenarları (Edges) dolaşır ve graftaki değerleri günceller.

Algoritma öncelikli olarak düğümleri dolaşıyor ve her düğüm için kenarları dolaşacak.

A düğümü için kenarları dolaşıyoruz. Kenarlardan sadece AB ve AC kenarları, A düğümü ile ilgili. Aslında bütün kenarlar dolaşılıyor olmasına rağmen, sadece bu iki kenar, graftaki sonucu etkileyecek.

AB 2, min(A,B) = 0 à 0+ 2 = 2

AC 1, min(A,C) = 0 => 0+1 = 1

Ardından B düğümüne geçiyoruz. Ve bu düğüm için bütün kenarları tekrar dolaşmaya başlıyoruz.

Bu durumda etkisi görülecek kenarlar:

AB 2

AC 1

BE 2

BF 5

CF 2

CD 1

Kenarlarıdır çünkü bunlar dışındaki kenarların bağladıkları düğümler sonsuz değerindedir ve güncelleme olmaz. Diğer bir deyişle grafın yukarıdaki şeklinde, A,B,C düğümlerinde sonsuz dışında değerler bulunuyor .O halde sadece bu düğümlere komşu olan kenarları almak yeterlidir.

BE 2, min (B,E ) 2, => 2 + 2 = 4

BF 5, min(B,F) = 2 => 2+5 = 7

CF 2, min (C,F) = 1 => 1+2 = 3, bu değer 7′den küçük olduğu için güncelliyoruz:

CD -1, min(C,D) = 1=> 1+(-1) = 0

Yukarıdaki son halimizde henüz 2 düğüm için işlem yapıldı ( A ve B düğümleri).

Graf 2 düğüm için kararlı hale ulaşmıştır ve diğer düğümler için işlem devam etse bile graftaki değerler değişmez.

İkinci Örnek

Yukarıdaki örnekte, düğümlerin ve kenarların rast gele dizildiğinden bahsetmiştik. Acaba bu dizilim rast gele olarak yukarıdakinden farklı olsaydı Bellman-Ford yine başarılı çalışır mıydı?

Düğüm diziliminin sonuca bir etkisi olmamakla beraber, kenar dizilimi sonucu etkiler:

Yukarıdaki dizilimi tersine çevirelim:

Bu yeni dizilime göre algoritmamızı çalıştırıyoruz:

A düğümü için kenarları dolaşıyoruz. Kenarlardan sadece AB ve AC kenarları, A düğümü ile ilgili. Aslında bütün kenarlar dolaşılıyor olmasına rağmen, sadece bu iki kenar, graftaki sonucu etkileyecek.

AC 1, min(A,C) = 0 => 0+1 = 1

AB 2, min(A,B) = 0 à 0+ 2 = 2

Ardından B düğümüne geçiyoruz. Ve bu düğüm için bütün kenarları tekrar dolaşmaya başlıyoruz.

Bu durumda etkisi görülecek kenarlar:

Kenarlarıdır çünkü bunlar dışındaki kenarların bağladıkları düğümler sonsuz değerindedir ve güncelleme olmaz. Diğer bir deyişle grafın yukarıdaki şeklinde, A,B,C düğümlerinde sonsuz dışında değerler bulunuyor .O halde sadece bu düğümlere komşu olan kenarları almak yeterlidir.

CF 2 için:

CD 1 için

BF 5 için , zaten daha kısa olan 3 değeri bulunmuştur

BE 2 için

AC ve AB kenarları için ise değişiklik olmaz.

Yukarıdaki bu yeni çalışmada dikkat edilirse, bir önceki çalışmadan farklı olarak F düğümü hiç 7 olmadan 3 değerini bulmuştur. Görüldüğü üzere kenar sıralaması, sonucu etkilememekle birlikte çalışma hızını etkileyebilir.

Eksi değerli Şekiller

Gelelim eksi değer olması durumuna.

Yukarıdaki şekilde görüldüğü üzere, BE ve CD kenarları eksi değerlidir. Bu şeklin çalışmasını inceleyelim:

Her şey, normal algoritmada olduğu gibi, başlangıç dışındaki düğümlere sonsuz atayarak başlıyor.

Bu algoritmanın eksi değerlerdeki başarısının anlaşılabilmesi için, şimdiye kadar ihtiyaç duymadığımız ve yazının başında belirtilen, hangi düğümden gelindiği bilgisine ihtiyaç vardır. Yani algoritmamızı çalıştırırken, her düğümdeki değerin güncellenmesi sırasında, hangi düğümden güncellendiği yazılır.

Ardından her düğüm için ve her kenar için işlem yapılıyor. Bu adımları daha önce detaylıca gösterdiğim için aşağıda düğüm bazlı hızlandırılmış olarak anlatıp, sadece eksi değerdeki farkı vurgulayacağım:

Bir sonraki adımda kenar sırasına göre aşağıdaki güncellemeler yapılır:

Bu haliyle, graftaki bütün düğümlere erişilmiştir. Fakat problem bitmez. Yani eksi değerli düğümler, çalışmanın hala devam etmesini gerektirir.

Yukarıdaki son hali, kararlı haldir.

Bu noktada şu soru sorulabilir: Peki neden tekrar eski değerli düğümler işlenerek, D ve E düğümleri güncellemiyor?

Bu soru haklı bir sorudur ancak yazının başında belirtildiği üzere, bellman-ford algoritması, her düğümde, kimden gelindiği bilgisini tutar. Dolayısıyla D düğümünü 0 olarak güncellemeden önce, D düğümüne, C düğümünden gelindiği ve E düğümüne de B düğümünden gelindiği kaydedilmiştir.

Dolayısıyla, eksi değerler tağılan bu döngülerde, tekrar edilip örneğin F düğümüne -4 değeri yazılamaz. Çünkü F düğümü zaten B düğümünden güncellenmiştir.

R project (projesi), daha önceden vâr olan S Lang isimli, ücretli, istatistik diline alternatif olarak ücretsiz olarak çıkarılmıştır.

Bu yazının amacı R Project isimli bu istatistiksel modelleme ve geliştirme aracını tanıtan Türkçe bir yazı yayınlamaktır. Bu yazı kapsamında, R Project 2.11.1 sürümü kullanılacaktır. R Project programını, r-project.org sitesinden indirebilirsiniz.

Giriş

R project programını ilk kez çalıştırdığınızda, aşağıdaki gibi bir ekran ile karşılaşırsınız:

Yukarıdaki ekranda görülen pencere, bizim komutları verdiğimiz ana penceremiz olacak. Bu pencerede R Project içerisinde daha önceden tanımlı olan fonksiyonları kullanabileceğimiz gibi yeni fonksiyon tanımlamaları da yapabiliriz.

Basit işlemler ile programı kullanmayı öğrenelim. En basit ve en önemli ilk komutumuz, programdan nasıl çıkılacağı. Bunun için yukarıdaki resimde görülen ekranda “q()” yazmanız yeterlidir. Elbette R Project, mevcut çalışmaların kaybolmaması için, kaydetmek isteyip istemediğimizi soracaktır.

Sırada ikinci en önemli komutumuz olan “help()” komutu var. Bu komut adı üzerinde R Project’in yardım dosyalarını görüntüler ve herhangi bir komut hakkında bilgi almamıza yarar. Örneğin yeni öğrendiğimiz “q()” komutu hakkında bilgi almak isteyelim. Bu durumda

>help(q)

Yazmamız yeterlidir. Şayet kurulum sırasında, yardım dokümanlarını yüklemeyi seçtiyseniz bilgisayarınızdaki kurulu olan yardım dosyalarından q fonksiyonu hakkında bilgiler bulunarak size internet görüntüleyicinizde gösterilecektir. Şayet bu yardım dosyalarını yüklemediyseniz, internet üzerinden R Project sitesine bağlanılarak yardım dosyaları gösterilecektir.

Alternatif olarak yardım için ? işareti de kullanılabilir. Örneğin q fonksiyonu hakkında yardım almak için help(q) yazmak yerine ?q da yazılabilir. Bu iki kullanım birbirinin aynıdır.

Bazı durumlarda, kullanılmak istenen komut hatırlanamayabilir. Şayet kullanmak istediğiniz komutun bir kısmını hatırlıyorsanız, yardım dosyalarında bu komuta benzeyen bütün komutları ?? işareti ile aratabilirsiniz. Örneğin ??q şeklinde bir komut verirsek, yardım dosyalarında, içinde ne kadar q harfi geçen komut varsa hepsini listeler.

Basit Vektörler

R Project’e giriş yaptıktan sonra vektörler, diziler ve basit işlemleri öğrenebiliriz.

R project için en önemli komutlardan birisi c() komutudur. Bu komut, concatinate (üleştirmek) kelimesinden gelir ve verilen bilgileri üleştirerek bir vektör oluşturur.

Örneğin aşağıdaki ekran görüntüsünü incleyelim:

Ekran görüntüsünde ilk satırda, sadi ismindeki bir değişkene, c fonksiyonu ile bir vektör ataması yapılıyor. Bu değişken ismi daha önceden tanımlı değildir ve ilk defa burada kullanılıyor, otomatik olarak bu isimde bir vektör oluşup, daha sonraki işlemler için hafızada (RAM) saklanıyor.

Nitekim ikinci satırda bu değişkenin ismi tek başına yazıldığında, değişkenin içerisindeki vektör (mavi renkle) görüntüleniyor.

Burada atama işlemi (assignment) yapılmıştır ve c() fonksiyonunda oluşturulan vektör, “sadi” isimli değişkene atanmıştır. Bu atma işlemi için <- sembolleri kullanılmıştır (küçüktüt ve eksi)

Aynı atama işlemi assign() fonksiyonu kullanılarak da yapılabilir. Yalnız assign kullanılırsa, değişkenin ismi çift tırnak içinde yazılmalıdır. Benzer şekilde okun yönü -> sağa doğru (eksi ve büyüktür) şeklinde kullanılırsa, okun solundaki değer, sağındaki değişkene atanır.

Örneğin son satırında, bu şekilde seker değişkenine atama yapılmıştır.

Vektörler, R Project için en basit veri yapılarıdır. Bu veri yapıları kullanılarak çeşitli işlemler yapılabilir.

Örneğin basit 4 işlem için + – * ve / operatörleri kullanılabilir (sırasıyla, toplama, çıkarma, çarpma ve bölme işlemlerinin sembolleri)

Bir önceki örnekte sadi değişkeninin içerisine bir vektör ataması yapıldı. Bu vektör üzerinde, aşağıdaki şekilde işlemler yapılabilir:

Görüldüğü üzere yukarıda, sırasıyla, bölme, toplama, çarpma ve çıkarma işlemleri gösterilmiştir. Örneğin ilk örnekte 1/sadi komutu ile, sadi değişkeni içerisinde bulunan bütün değerlerin 1′e bölümünden çıkan yeni vektör görüntülenmiştir.

Bu vektörü görüntülemek yerine yukarıdaki örnekte olduğu gibi a isimli bir değişkene atama yapılıp, ileride de kullanılabilir.

Yukarıdaki bu dört işlem dışında, R Project içerisinde, vektörler için geniş bir fonksiyon kütüphanesi bulunur. Bunlardan sık kullanılan bazılarını anlatalım.

Bu örneklerden, sum, vektör elemanlarının toplamını, mean ortalamasını ve length eleman sayısını bulmaya yarar.

Vektör değeri üretilmesi sırasında da R Project içerisinde bazı kolay komutlar bulunmaktadır.

Örneğin : operatörü, bir dizi oluştururken, başlangıç ve bitiş değerlerini alır. Bu değerler arasında birer birer artan bir dizi oluşturur. 1:10 dizisi bu şekilde oluşturulmuştur.

Bu iş için seq fonksiyonu da kullanılabilir. Bu fonksiyon iki parametre alabileceği ve : operatörüne denk kullanılabileceği gibi üçüncü bir parametre daha alıp artış miktarını ayarlayabilir. Seq(1,10,by=2) yazımında, by=2, artış miktarının 2şer 2şer olacağını anlatır. Örneğin by=.2 şeklinde 0.2 olarak da arttırılabilirdi. Aynı durum, : operatörü ile bir dizi oluşturup bir sabit ile çarparak da oluşturulabilir.

Ayrıca seq fonksiyonuna parametre olarak from ve length değerleri de verilebilir.

Length, vektörün eleman sayısını, from ise başlangıç değerini belirtir.

Rep fonksiyonu, bir vektörün tekrarlaması (repeat) için kullanılır. Bu tekrar işlemi, aynı vektörün arka arkaya tekrarlanması şeklinde ise times parametresine kaç tekrar istendiği verilerek, şayet vektörün her elamanı tekrarlanacaksa each parametresine sayı verilerek yapılabilir.

Dizgi (String) Vektörleri

Yukarıdaki bölümde anlatıldığı üzere vektörleri sayılardan oluşturmak mümkün olduğu gibi, dizgilerden (string) oluşturmak da mümkündür.

R Project içerisinde, bir dizgiyi (string) belirten sembol çift tırnaktır.

Örnekte görüldüğü üzere, c fonksiyonu kullanılarak bu kez ali isminde bir dizgi vektörü oluşturulmuştur.

Dizgilerde özel sembollerin yazılması için \ sembolü kullanılır. Örneğin zaten tırnak içerisindeki bir dizgiye tırnak sembolü konulmak istenirse \” şeklinde yazılması gerekir. Benzer şekilde \ işaretini bir dizginin içerisine yerleştirmek için \\ şeklinde iki kere tekrar edilmesi gerekir.

Vektör Indisleri (Indexes)

Vektörlerle çalışırken, önemli konulardan birisi de indekslerin doğru kullanılmasıdır. Basitçe bir vektörün içerisindeki bir veya birden çok belirli elemanlara erişmeye yarayan operatördür. [] şeklinde köşeli parantezlerle kullanılır.

Örneğin yukarıdaki ilk kullanımda, a,b şeklindeki bir vektöre indis olarak 1,2,2,1,1 şeklindeki ikinci bir vektör indis olarak veriliyor. Bunun anlamı, ilk vektördeki a,b ikilisindeki elemanların hangi sırayla tekrarlanacağıdır. Yani a elemanı 1. Eleman, b elemanı ise ikinci eleman, o halde 1,2,2,1,1 vektöründeki 1 yerine a ve 2 yerine b konulması istenmiştir.

Yukarıdaki ikinci örnekte, a isimli bir vektör içerisine 1′den 20′ye kadar olan çift sayılar yerleştirilmiştir. İndis olarak verilen vektör ise 3,2,8 olduğuna göre, vektörün bu elemanları sonuçta görüntülenir.

İndis kullanımında, tek bir sayı verilerek, sadece bu elemana doğrudan erişilebileceği gibi, eksi sayılar kullanılarak, vektörden bu elemanlar çıkarılabilir. Örneğin a[-2] kullanımı, vektörden 2. Elemanın çıkarılması anlamındadır. a[1:3*-2] kullanımı ise aslında a[c(-2,-4,-6)] olduğuna göre, 2. 4. Ve 6. Elemanların çıkarılması anlamındadır.

Vektör seviyeleri (levels)

Vektörlerde önemli bir konu da, vektörler üzerinde oluşturulan seviyelerdir. Basitçe bir vektörde birden fazla tekrar eden bir bilgi bulunuyorsa, bu bilgi bir üst seviyede gruplanabilir.

Yukarıdaki örnekte, gorev ve maas isimli iki vektör değişkeni bulunmaktadır. Gorev değişkeninde, bazı görevlerin tekrarlı olduğuna dikkat ediniz.

8 adet görev ve her görevdekilerin maaşının yazılı olduğu 8 adet maaştan oluşan iki ayrı vektör bulunuyor.

Öncelikle factor komutunu kullanarak, gorev vektöründeki seviyeleri çıkarıyoruz. Nitekim, factor komutundan sonra bize Levels: …. Şeklinde ikinci bir satıda, çıkarılan seviyeleri listeliyor. Görüldüğü üzere factors komutu, kümeleme işlemi yapmaktadır. Küme teorisinde (set theory) bir eleman sadece bir kere geçebilir. Dolayısıyla çıkarılan levels listesinde de her eleman tek bir kere geçmektedir. Ayrıca alfabetik olarak sıralamaktadır.

Bu listeye levels() fonksiyonu ile ulaşılabilir.

Tapply fonksiyonu ise iki vektörü bir fonksiyon üzerinden birleştirmeye yarar. Örneğin her gorevin ortalama maaşını hesaplamak için mean, toplamı için de sum fonksiyonu, yukarıdaki örnekte kullanılmıştır.

Bu kullanımı, SQL dilinde bulunan group by kelimesine benzetmek mümkündür. Öncelikle gruplama yapılıp ardından grup fonksiyonu uygulanmaktadır.

Diziler ve Matrisler

R Project içerisinde, çok boyutlu vektörler için dizi (array) kelimesi kullanılır. Buna göre, vektör tek boyutlu bir veri yapısı iken, diziler (array) çok boyutlu olabilir.

Bu anlamda, matrisler (matrix) iki boyutlu diziler olarak kabul edilebilir. Diziler, üç veya daha fazla boyutta da olabilir.

Yukarıdaki örnekte olduğu üzere, 1:18 ile 1′den 18′e kadar sayılar oluşturulmuş ardından bu sayılardan oluşan vektör, 2 boyutlu bir dizinin (array) içerisine döşenmiştir. Bu dizinin boyutları ise dim=c(3,6) komutu ile 3×6 şeklinde verilmiştir.

Yukarıdaki bu kullanımı, indis kullanımı ile birleştirmek de mümkündür.

Dizi[2], kullanımı, dizinin 2. Elemanına erişirken, dizi[2,] kullanımı 2. Satıra, ve dizi[,2] kullanımı da 2. Sütuna işaret etmektedir.

Bu indisler kullanılarak, dizi üzerinde değişiklik yapılması da mümkündür.

İlk örnekte, dizinin 3. Elemanına 111 sayısı konulmuştur. BU işlemden sonra dizinin [3,1] elemanı 111 olarak değişmiştir.

İkinci örnekte ise, dizinin ilk sütunu, 9,9,9 vektörü ile değiştirilmiştir.

Matrislerde İşlemler

Matrislerde lineer cebir (linear algebra) gereği bazı işlemlerin R Project ile kolayca yapılması mümkündür.

Örneğin temel matris işlemlerini ele alalım:

Yukarıda iki adet 2×2 boyutlarındaki (a ve b) matrisin sırasıyla, toplanması, çarpılması, çıkarılması ve bölünmesine örnekler gösterilmiştir.

Benzer şekilde, matrislere özgü bazı işlemlerin yapılması da mümkündür. Örneğin iki matrisin Kartezyen çarpımı için (outer product) %o% şeklinde üç sembolden oluşan bir operatör kullanılması mümkündür:

Görüldüğü üzere sonuç, 4 boyutlu bir matristir.

Matris tersyüzü için (transpose) t() fonksiyonu kullanılabilir:

Görüldüğü üzere a matrisinin tersyüzü alınmıştır.

Matrisin tersini almak için solve() fonksiyonu kullanılabilir.

Görüldüğü üzere a matrisinin, çarpmaya göre tersi alınmıştır.

Listeler (LISTS)

R Project içerisinde kullanılan diğer bir veri tipi de listelerdir. Listelerin vektörlere göre farkı, veriyi sayısal indis yerine istenen bir veri tipinde indisleyebilmesidir.

Yukarıdaki örnekte görüldüğü üzere, eleman isimli bir liste oluşturulmuştur. Bu listenin ilk iki elemanı dizgi (string) yapısında iken 3. Eleman sayı ve son elemanı bir vektördür.

Listenin bir elemanına erişilirken, bu erişim için [[ ]] şeklinde çift köşeli parantez kullanılır.

Yukarıdaki örnekteki son satırda, listenin 4. Elemanına erişilmiş, bu eleman bir vektör olduğu için de bu vektörün ilk elemanına erişilmiştir.

Ayrıca yukarıdaki listenin herhangi bir bilgisi, doğrudan ismi kullanılarak aranabilir.

Listelere eleman eklemek veya değiştirmek için, bu elemanın indis numarası kullanılabilir.

Yukarıdaki örnekte görüldüğü üzere eleman listesine yeni bir değer 5. Sırada eklenmiştir.

Antik yunanda, Polybius ismindeki kişi tarafından bulunan iki boyutlu bir tahtaya dayalı şifreleme sistemidir.

Bu sistemin özelliği, alfabedeki harflerin, iki boyutlu bir tabloya yerleştirilmesi ve ardından bu tablodaki satır ve sütun numaralarına göre okunmasıdır.

Aşağıda ingiliz alfabesindeki harfler için böyle bir tablo gösterilmiştir:

Görüldüğü üzere, ingilizcede bulunan 26 harf, 5×5 = 25 boyutlarında bir tabloya yerleştirilmiş, dolayısıyla da bir hücreye iki harf I/J yerleştirilmesi gerekmiştir.

Aynı tabloyu, örneğin Türkçe için uyarlarsak, aşağıdaki gibi bir tablo olabilir:

Bu tablolardaki hücrelerin, hangilerinde çift harf olacağı tamamen rast gele seçilmiştir.

Şifreleme sisteminin çalışması

Şifreleme sırasında, sistem, basitçe her harf için iki sayıdan oluşan bir sonuç bulur. Örneğin şifreleyeceğimiz bilgi “şadi” kelimesi olsun.

Bu kelimeyi şifrelemek için her harfin satır ve sütun numaralarına bakıyoruz.

ş harfi, 4 satır ve 4 sütun –> 44

a harfi, 1 satır ve 1 sütun –> 11

d harfi, 1 satır ve 4 sütun –> 14

i harfi, 2 satır ve 4 sütun –> 24

olarak değerler bulunur. Sonuçta bu değerler birleştirildiğinde şifreli mesaj elde edilmiş olur.

şadi –> 44111424

Bazı kaynaklarda, şifreli mesaj 44-11-14-24 şeklinde – işareti ile ayrılarak gösterilmektedir. Bunun tek amacı okumayı kolaylaştırmaktır, yoksa sistemimizin her zaman için her harfi 2 haneli bir sayıya çevireceğini biliyoruz. Dolayısıyla bir ayıraca ihtiyaç yoktur.

Sistemin şifreyi açması

Şifrelenmiş mesaj açılırken bu defa tablo, tersten kullanılır.

Açmak istediğimiz mesaj 44111424 olsun. Bu mesajı açarken satır / sütun sırası kullanıyoruz.

ilk sayı 4, dolayısıyla 4. satıra bakıyoruz, ikinci sayı 4 dolayısıyla 4. sütuna bakıyoruz –> ş

üçüncü sayı 1, dolayısıyla 1. satıra bakıyoruz, dördüncü sayı 1 dolayısıyla 1. sütuna bakıyoruz –> a

beşinci sayı 1, dolayısıyal 1. satıra bakıyoruz, altıncaı sayı 4, dolayısıyla 4. sütuna bakıyoruz –> d

yedinci sayı 2 dolayısıyla 2. satıra bakıyoruz, sekizinci sayı 4 dolayısıyla 4. sütuna bakıyoruz –> I/İ

sonuçta açık mesajımız

şadı/i

olarak bulunuyor. yani açık mesaj ya şadı ya da şadi olmuş olur.

Polybius şifrelemsine saldırı

Sistem aslında bir yerine koyma (substitution cipher) özelliği gösterir. Her harf, bir sayı ile değiştirilmiştir. Dolayısıyla yerine koyma (substitution cipher) için geçerli olan bütün saldırı yöntemleri, bu sisteme karşı da kullanılabilir.

Hakan Beyin Sorusu üzerine:

Sayın Hakan Er, aşağıdaki soruyu sormuş:

1) 12-25-63-48-56-85-87 (attım) gibi bir şifre kesin olarak polybius tekniğine göre mi şifrelenmiştir yoksa buna benzer başka tekniklerde var mı?
2)polybius şifrelemesinde 0 yok.ama benim şifremde 0 var ve fazlasıyla.0 ne anlama geliyor?
3)benim şifremde 26 dan yukarı rakam yok.o halde damatahtamı 9×9 yada 5×5 yapmama gerek yok diye düşünüyorum? nasıl yapmalıyım damatahtamı ?

cevabınız için şimdiden teşekkür ederim.sevgiler.

Cevap

Yukarıdaki soruları, sırasıyla cevaplamaya çalışalım.

1) verdiğiniz iki haneli sayılar, herhangi bir şifreleme sisteminin sonucu olabilir. Örneğin affine cipher, hill cipher, viegnere cipher gibi şifreleme yöntemleri bunlara örnek olarak sayılabilir. Elbette sizin verdiğiniz sayıların hepsi 2 haneli olduğu için, örneğin viegnere şifrelemesinde veya hill şifrelemesinde blok boyutu 2 olarak alınmış demektir.

Dolayısıyla cevaben, iki haneli sayılardan oluşan bu şifreli mesaj, kesin olarak poylbius şifrelemesidir denilemez.

2 ve 3) 0 sayısı da bir sayıdır. Polybius şifrelemesi yukarıda anlatıldığı gibidir ama bunun dışında polybius şifrelemesinde değişiklikler yapılabilir.

Örneğin aşağıdaki tabloyu ele alalım:

Yukarıdaki talboda, sayılar 0′dan başlamış ve 6×6 = 36 sembollü bir tablo kullanılmıştır. Bu tablo yine tamamen benim tarafımdan konuyu anlatmak için rastgele üretilmiştir.  Yani polybius şifrelemesi sistemin esaslarını koyar ama, polybius şifrelemesi kullanmak demek illaki sabit bir tablo kullanmak demek değildir. İstenilen bir tablo kullanılabilir. Buradaki şart, sistemi kullanan tarafların, kesin olarak tabloyu bilmeleri gerektiğidir.

Sizin sorunuz burada cevaplanmış oluyor. Yani yukarıdaki tablo kullanılarak örneğin “tabî” kelimesini şifrelersek sonuç aşağıdaki şekilde olur:

t –> 34

a –> 00

b –> 01

î –> 52

şifreli mesaj = 34-00-01-52

görüldüğü üzere kullandığınız tabloya göre hem 0 olabilir hem de 25′ten büyük sayılar olabilir.

Bilgisayar bilimlerinde de sıkça kullanılan ve matematiğin bir parçası olan karmaşıklı teorisi (complexity theory) içerisinde tanımlı olan bir karmaşıklık sınıfıdır (kümesidir, set)

Bu kümenin özelliği, bu kümenin üyesi olan, fonksiyon, denklem veya algoritmaların logaritmik zamanda veya logaritmik hafıza ihtiyacı ile çalışıp çalışamayacağının veya çözülüp çözülemeyeceğinin belirlenememesidir.

Bu kümenin tanım itibariyle tersi olan L (logarithmic) kümesinde bulunan problemler, algoritmalar veya fonksiyonlar ise logaritmik zamanda veya alanda çözülebilmektedir.

Bu tanımlarda geçen “zamanda veya alanda” ibaresi ile, karmaşıklığın zaman (time complexity) veya alan (memory complexity) olabileceği ifade edilmek istenmiştir. Yani, örneğin, bir algoritmanın zamansal çalışma karmaşıklığı (time complexity) NL sınıfından olurken, hafızadaki ihtiyacı (memory complexity) farklı bir sınıfta olabilir.

Logaritmik karmaşıklık konusunda bilinmesi gereken bir diğer konu ise RL sınıfıdır. Bu sınıf, tanım itibariyle olasılığa dayalı bir yapı izler. Randomized Logarithmic kelimelerinin baş harflerinden oluşan bu sınıftaki problemler, algoritmalar veya fonksiyonlar ise olasılıksal Turing Makinesi (Probabilistic Turing Machine) tarafından kabul edilirler.

Olasılıksal Turing makinesi, tanım itibariyle, sadece doğru durumları kabul eden ama yanlış durumları belirlerken hata yapabilen makinedir. Yani bir Klasik Turing makinesinde (Turing Machine) iki sonuçtan biri çıkar:

• Kabul (Accept)
• Red (Reject)

Normal bir Turing makinesi tasarım itibariyle bu iki durumu doğru olarak döndürebilmelidir. Olasılıksal Turing makinesi ilk şart olan kabul durumlarını doğru olarak döndürürken, ikinci ihtimal olan red durumlarında hata yapabilir.

RL sınıfı işte bu tip Turing makinelerinin logaritmik zamanda veya logaritmik alanda çözülebilmesi anlamındadır.

Litartürde, Boolean Satisfiability Problem olarak geçen ve boole cebirindeki denklemlerin doğruluğunun sağlanması olarak özetlenebilecek olan problemdir. Ayrıca çeşitli kaynaklarda bu probleme, problemin İngilizce tanımında geçen Satisfiability kelimesinin kısaltması olan SAT kelimesi olarak da rastlanabilir.

Bu problemi, bilgisayar bilimleri açısından ilginç kılan yanı ise, problemin yapısal olarak bir NP-Tam (NP-Complete) sınıfı problem olmasıdır.

Boole Cebiri, aslında mantıksal bir gösterim ifade etmektedir. Dolayısıyla mantıktaki karşılığı olarak probleme önermeler mantığı (propositional logic, kaziye mantığı) tatmin problemi ismi de verilebilir.

Boole cebirinden alışıldığı üzere mantıksal kurgu için tanımlı olan ve bilgisayar bilimlerinde değişken (variable) olarak isimlendirilebilecek belirticiler (literal, lafziler) bulunmaktadır. Bunlar basit birer sembol ile gösterilir.

Örneğin x ile gösterilen bir sembol çoğu zaman gerçek hayattaki bir kaziyeyi (önerme, proposition) ifade etmektedir.

Bu lafzi gösterimlerin (literal, belirticiler) üzerinde tanımlı ve yine boole cebiri içerisinde kabul edilebilecek işlemler (operators) tanımlanabilir. En sık kullanılan bool cebiri işlemleri ve(and), veya (or), tersi (not) şeklinde sayılabilir. Bu işlemler kullanılarak kurulan bir dizilimin sonucunun yine bir lafzi gösterim (literal) cinsinden elde edilmesi ve ya doğru (true) ya da yanlış (false) olması beklenir.

Bu tanımın üzerine örneğin sadece 3 adet lafzi gösterim (literal)’in ve (and) bağlacı normal şeklinde (conjunction normal form) olması durumuna 3SAT veya 3CNFSAT isimleri verilir. Bu problem NP-TAM (NP-Complete) bir problemdir.

Benzer tanım sadece 2 adet lafzi gösterim’in (literal) ve bağlacı normal şeklinde (conjunction normal form) olması durumuna ise 2SAT veya 2CNFSAT ismi verilir ve bu problem de NL-Tam (NL-Complete) bir problemdir.

Boole tatmin probleminin diğer önemli bir yanı da tarihsel olarak, 3SAT problemlerin, ilk NP-Complete problem olmasıdır. Bu konuda çalışan Stephen Cooke 1971 yılında bu problem grubunun NP-Complete olduğunu göstermiştir.

Ayrıca boole tatmin probleminin birinci derece mantık (First order predicate calculus) içerisindeki çözümünün aranması da ayrıca bir problemdir.

Bilindiği üzere birinci derece mantığın, üzerinde tanımlı olduğu lafzi gösterimler (literals) için bir takın etki alanı tanımlamaları (domain) mümkündür. Bu tanımlamalar ile verilen bir boole cebiri, diziliminin çözümlenmesi bir seviye daha karmaşık hale gelmektedir.

Örneğin aşağıdaki problemin çözümünü bu anlamda değerlendirebiliriz:

∃a (Şadi (a) ∧ Mühendis(a)) → Öyle bazı a’lar vardır ki, bu a’nın ismi Şadi’dir ve bu a mühendistir.

Bu tip birinci derece mantık dizilimlerinin çözüm karmaşıklığı Co-NP problem olarak geçmektedir.

Bu gösterim, bool cebirinde (boolean algebra) kullanılan ve kaziyeleri (önerme, proposition) ve (and) bağlacı ile bağlamanın özel bir şeklidir. Kısaca CNF (conjuction normal form) olarak ifade edilir. Diğer bir normal şekil olan Chomsky Normal Form (CNF) ile ilgili bilgi arıyorsanız buradan ulaşabilirsiniz.

Bu özel şeklin taşıdığı kuralları aşağıdaki şekilde sıralayabiliriz:

Ters (not) işlemi, sadece önermelerin lafzi gösterimlerin (literal) başında bulunacaktır. Bir kaziyenin (önerme, propositon) başında bulunmayacaktır.

Örneğin ¬A şeklindeki tek lafzi gösterim üzerinde olan ters işlemi kabul edilirken ¬(A V B) şekli kabul edilemez.

Ve (and) işlemi, iki operand almaktadır. Yani a ve b şeklindeki bir işlemde a ve b adında iki lafzi gösterim (literal) bulunmaktadır. Bu işlemin herhangi bir operandı, basit bir lafzi gösterim (literal) veya disjunction (veya operatörü (or opeartor) ile oluşturulmuş bir) kaziye (önerme, proposition) olmalıdır.

Örneğin aşağıdaki gösterimler bu kurala uymaktadır:

A Λ B

(A V B ) Λ (C V D)

A Λ (C V D V F)

Ancak aşağıdaki gösterimler bu kurala uymaz

A Λ (B Λ C)

A Λ (B V C Λ D)

(A Λ B) Λ C

Ancak yukarıdaki gösterimler CNF (conjuction normal form) yani ve bağlacı normal şekline çevrilebilir. Bu çevirimler aşağıda gösterilmiştir (yukarıdaki her satır için sırasıyla)

A Λ B Λ C

A Λ ( B V C ) Λ ( B V D)

A Λ B Λ C

Görüldüğü üzere yukarıdaki yeni hallerinde, verilen gösterimler ve bağlacı üzerinde basitleştirilmiştir.

Disjunction Normal Form (DNF, Veya bağlacı normal şekli) ise yukarıdaki ve bağlacı için söylenen her şeyin, veya bağlacı için geçerli olması durumudur.

Kısaca bu şekilde kabul edilemeyecek gösterimleri ve çevrilmiş şekillerini aşağıda verelim:

İki gösterimin doğruluğunun tespiti. Yani verilen bir boole cebiri diziliminin gerçekten CNF veya DNF olduğunun sınanması, veya verilen bir denklemin sonucunun doğru (true) veya yanlış (false) olarak bulunabilmesi, bu denklemdeki lafzi terim (literal) sayısına bağlıdır. Örneğin 3CNF bir denklemin, yani sadece 3 terimin conjunction (ve bağlacı ile bağlanmasından) oluşan bir denklemin karmaşıklığı NP-Complete olurken, bu terim sayısı 2′ye indirildiğinde yani 2CNF bir denklem söz konusu olduğunda, karmaşıklık P zamanda (polinom zamanda) çözülebilmektedir.
Daha detaylı bilgi için ikili tatmin problemleri (boolean satisfaction problem) başlıklı yazıyı okuyabilirsiniz.

Kelime anlamı olarak bir değişkenin geçici, uçucu değere sahip olmasını ifade eder.

Volatile tip tanımlayıcısı (Volatile Type Quantifier) basitçe bir değişken tanımının başında bulunup, bu değişkenin, program dışında bir etki altında bulunabileceğini ifade eder.

Örneğin geliştirdiğimiz bir programda, farklı işlem (process) veya donanımsal etkiler sonucunda değeri değişen bir değişken (variable) kullanıyorsak, bu değişkeni volatile olarak tanımlamamız gerekir. Aksi halde derleyici (compiler) bu değişkeni optimize ederek görevini yerine getiremez bir hale sokabilir.

Bu durumun çok klasik örneklerini IPC (inter process communication, işlemler arası iletişim) konularında görebiliriz.

Klasik bir bariyer kullanılacağını ve işlemin bu bariyere belirli bir amaç için takılacağını düşünelim.

C dilinde böyle bir örneği aşağıdaki şekilde kodlayabiliriz:

int bar = 0;

while(bar == 0);

Yukarıdaki iki satırda görüldüğü üzere “bar” isminde bir değişken tanımlanmış ve bu değişkenin, değeri 0 olduğu sürece sonsuz döngüye girilmiştir. Elbette bu aşamada kod sonsuz döngüye girecek ve ilerlemeyecektir.

Yukarıdaki bu bariyeri kırmak için farklı bir işlem tarafından “bar” değişkeninin değeri değiştirilmek istenirse, bu durumda değişkene müdahale edilememesi söz konusu olabilir. Kullanılan derleyicinin optimize etme seviyesine bağlı olarak, belki de derleyici bu değişken değerini hiç tutmadan ve işletim sistemi üzerinde işlemciye bile uğramadan programı bekletme şekline geçirmiş olabilir.

Derleyicinin bu seviyede bir optimizasyon yapması sonucu değişkene erişmek ve dolayısıyla değişkenin değerini değiştirip, yukarıdaki bariyeri kırmak mümkün olmaz. Bunu engellemek için değişken tanımında volatile kelimesi kullanılır.

volatile int bar= 0;

while(bar==0);

Yeni kodumuzun tek farkı, derleyicinin bu kodda bulunan “bar” değişkenini optimize etmeyecek olmasıdır. Bu sayede kod gerçekten verimsiz bir şekilde çalışacak ancak değişkenin bütün beklentileri karşılaması sağlanacaktır.

Yukarıdaki bu durum, C, C++ dilleri için geçerli ve kullanışlıdır.

JAVA ve C# dilleri için durum biraz farklıdır. Bu dillerde yukarıda anlatılan problemin çözümü için hem volatile hem de synchronized tip tanımlayıcıları (type qunatifiers) bulunur.

Bu dilleri kullanan kişilerin bu iki tip tanımlayıcısı arasındaki farkı bilmesi gerekir.

Synchronized olarak tanımlanmış bir değişken yukarıda anlatılan sorunu çözer ancak JAVA veya C# dillerinin nesne yönelimli programlama özelliğinden dolayı, bu değişkenin tanımlı olduğu sınıftan (class), birden fazla nesne tanımlanması mümkündür.

Örneğin lif (thread) özelliği taşıyan bir java sınıfından tanımlanan bütün nesneler (objects), performans kaygılarından dolayı kendi değişken kopyalarını tutarlar. Dolayısıyla her nesnede kendi değişken bilgisi durur.

Volatile olarak tanımlanan değişkenin farkı ise burada ortaya çıkar. Synchronized tanımlı bir değişkenden farklı olarak, volatile değişken sadece tek bir kopya tutar. Bu kopyaya ana kopya ismi de verilebilir. Tasarıma göre değişmekle birlikte, birden çok kopyanın, tek kopya üzerinden güncellenmesi ve hepsinin aynı olması da aslında tek kopya tutulması olarak düşünülebilir.

Bilgisayar bilimlerine matematikten miras kalan karmaşıklık teorisi (complexity theory) konularından birisidir. Aslında problem veya algoritmaların çözüme ulaşmadaki karmaşıklığını ölçmek için kullanılır.

Bu tanımın ardında, her problem veya algoritmanın bir fonksiyon gibi düşünülebilmesi, ve matematikteki fonksiyonların karmaşıklığını sınıflandırmak için kullanılan karmaşıklık sınıflarının (complexity classes) , algoritmalar için uygulanması yatmaktadır.

Bilgisayar bilimlerinde kullanılan karmaşıklık sınıfları 5 tanedir.

1. Küçük-o (small-o)
2. Büyük-O (big-o, veya big-oh diye de geçer)
3. Teta (Theta Θ, sadece büyük tetadan bahsedebiliz)
4. Büyük omega (big-Ω )
5. Küçük omega(small-ω )

Bu beş sınıf, aynı fonksiyon için uygulanan ve bir fonksiyonun farklı özelliklerini anlatan sınıftır.

Bu sınıflar, bir algoritma hakkında bilgi edinmemizi sağlar. Bu bilgileri aşağıdaki şekilde sıralayabiliriz:

• Bir algoritmanın ölçeği (Scalability)
• Bir algoritmanın zaman ve hafıza ihtiyacı (hızı ve ne kadar yer kaplayacağı) (time and memory efficiency)

Bu sonuçlara, algoritmanın kullanıldığı giriş bilgisine göre ulaşılır. Bir algoritmanın işlediği veri miktarına göre ne kadar zaman ve ne kadar yer gerektiğini gösterir.

Örnek

Örneğin klasik bir arama algoritması olan doğrusal arama (linear search) algoritmasını ele alalım. Bu algoritma verilen bir dizide karışık olarak duran sayılardan bir tanesini bulmayı hedefler.

int a[10] = { 3, 7, 2, 5, 6, 1, 8, -12, 11, 45};

Yukarıdaki dizide bulunan bir sayının kaçıncı sırada olduğunu aramak isteyelim. Örneğin 8 kaçıncı sıradaki sayıdır?

Algoritma, ilk elemandan başlayarak son elemana kadar bütün sayılara bakar ve aranan sayıya rastlarsa sonlanır. Bu durumda aranan 8 sayısını bulmak için sırasıyla 3,7,2,5,6 ve 1 sayılarına bakılacak, nihayet 8 sayısı bulununca 7. Sırada bulunduğu sonucu ile algoritma bitecektir.

Algoritmanın yer ihtiyacı ne kadardır?

Bu algoritmanın üzerinde çalıştığı veri büyüklüğü dizinin büyüklüğüdür ve bu değer 10′dur. Dolayısıyla arama işleminin n sayı içerisinden yapılacağını düşünürsek, n sayıyı hafızada tutmamız gerektiğini görürüz. Demek ki algoritmamızın hafıza karmaşıklığı (memory complexity) n’dir.

Algoritmanın çalışma hızı nedir?

Arama işleminin n adet sayı üzerinde yapıldığını söylersek, aşağıdaki 3 durumu incelememiz gerekir:

1. En kötü ihtimalle kaç adımda bulunur? (worst case)
2. En iyi ihtimalle kaç adımda bulunur? (best case)
3. Ortalama kaç adımda bulunur? (average case)

Bu ihtimal analizini doğrusal arama algoritmamıza uyguladığımızda, karşılaşabileceğimiz en kötü durum aranan sayının dizinin en sonunda bulunması veya dizide hiç bulunmamasıdır. Bu durumda dizideki bütün elemanlara bakılması gerekecektir. Dolayısıyla en kötü durumda karmaşıklığımız n sayı için n olacaktır.

En iyi ihtimal ise, ilk bakılan sayının, aranan sayı olmasıdır. Bu durumda tek bir bakma işlemi yeterlidir. Bu durumdaki karmaşıklığımız ise 1 olacaktır.

Ortalama durum ise bu algoritmanın çok sefer çalışması sonucunda istatistiksel olarak ortalama kaç elemana bakılacağıdır. Bu dizide bulunan sayıların hepsinin aranma oranlarının eşit olduğunu kabul edersek, ortalama durum n/2 olur.

İşte yukarıdaki bu durum analizleri, bizim karmaşıklık sınıflarımızı veren analizlerdir.

O – En kötü durum analizi

Θ – Ortalama durum analizi

Ω- En iyi durum analizi

Aynı zamanda, bir fonksiyon için de o gösterimi üst sınırı (upper bound), gösterimi ise alt sınırı (lower bound) ifade eder.

Örnek olarak aşağıdaki fonksiyonu ele alacak olursak.

f(x) = 3x⁵

Bu fonksiyona bir üst sınır çizmek istenirse, örneğin 7x⁵ fonksiyonu çizilebilir.

Mavi fonksiyon 7x⁵ ve kırmızı fonksiyon ise f(x) fonksiyonudur.

Yukarıdaki şekilde görüldüğü üzere, x=0 noktasından büyük değerler için yani x>0 için, mavi renkle gösterilen fonksiyon, kırmızı fonksiyonun üst sınırını oluşturmaktadır ve denilebilir ki, kırmızı fonksiyon hiçbir zaman mavi fonksiyonun üzerine geçemez.

Bu durumda mavi fonksiyon, kırmızının üst sınırı (upper bound) olmuş olur. Diğer bir deyişle, mavi fonksiyon, kırmızı fonksiyondan daha kötü bir fonksiyondur ve kırmızı fonksiyon en kötü ihtimalle mavi fonksiyon kadar kötü olabilir.

Bu durumu büyük-o ile gösterirsek:

f(x) ∈ O (x⁵)

şeklinde yazmamız yeterlidir. Bu gösterimin açılımı aşağıda verilmiştir:

f(x) ∈ O(g(x)) , öyle bir c değeri bulunursa ki, x₀>0 için, x>x₀ şartıyla, bütün f(x) ≤ c g(x) olsun.

Bu tanım, kısaca, şayet f(x) ∈ O(g(x)) bağlantısı verilirse, herhangi bir x0 noktasından başlanarak sonsuza kadar bütün f(x) ≤ c g(x) koşulunu sağlayan bir c değerinin bulunabileceğini anlatmaktadır.

Yukarıdaki tanımın tam tersi omega için geçerlidir.

f(x) ∈ Ω(g(x)) , öyle bir c değeri bulunursa ki, x₀>0 için, x>x₀ şartıyla, bütün f(x) ≥ c g(x) olsun.

Bu tanım, kısaca, şayet f(x) ∈ Ω(g(x)) bağlantısı verilirse, herhangi bir x0 noktasından başlanarak sonsuza kadar bütün f(x) ≥ c g(x) koşulunu sağlayan bir c değerinin bulunabileceğini anlatmaktadır.

Bu iki tanımda dikkat edilecek bir nokta, f(x) ile c*g(x) arasındaki bağlantının eşitliği de kapsamasıdır. Yani örneğin big-omega için, c*g(x) değeri f(x) fonksiyonundan küçük veya eşit olabilir.

Şayet bu tanımdaki eşitliği kaldırırsak, küçük-o ve küçük-ω tanımını elde ederiz. Yani küçük-o için, c*g(x) değerinin f(x) değerinden sürekli olarak büyük olması gerekir.

Theta gösterimi ise ortalama durum, yani eşitlik durumu içindir. Burada aranan şart f(x) ∈ Θ(g(x)) için c₁*g(x)≥f(x)≥c₂*g(x)’dir. Yani g(x) fonksiyonunun f(x) fonksiyonu ile aynı şekilde hareket ettiğini göstereniki sabit sayı, c₁ ve c₂ bulunabiliyorsa f(x) ∈ Θ(g(x)) denilebilir.

Bu durumda yukarıda listelediğimiz 5 sınıf aşağıdaki şekilde ilişkilendirebiliriz:

Yukarıdaki şekilde anlatılmak istenen, sınıflar arasında, bazı kesişim durumlarının olduğudur. Görüldüğü üzere, en kötü durum (big-o) ile en iyi durum (big-Ω) kesişmesi sadece eşitlik durumunda olur. Bu durum ise teta ile gösterilmektedir. Benzer şekilde küçük-o ve küçük omega hiçbir zaman kesişemez ve büyük-o ile küçük-o arasında ve büyük omega ile küçük omega arasındaki fark alanında eşitlik durumları bulunur.

Karmaşık sayıların (complex numbers) çarpımında kullanılan bu yöntem, çarpma işleminin toplamaya göre maliyetli olduğu bilgisayar uygulamalarında tercih edilir.

Çarpmak istediğimiz iki karmaşık sayıyı (complex number) aşağıdaki şekilde gösterelim:

(x + yi ) = (a + bi) · (c + di)

Yöntemin çalışması aşağıdaki 3 sayının hesaplanması ile başlar:

k₁ = c · (a + b)

k₂ = a · (d − c)

k₃ = b · (c + d)

x = k₁ − k₃

y = k₁ + k₂.

Görüldüğü üzere iki karmaşık sayının çarpımı sırasında 3 adet aritmetik çarpma ve 5 adet toplama / çıkarma kullanılmıştır. Aynı durum klasik karmaşık sayı çarpımı için aşağıdaki şekildedir:

x = a·c – b·d

y = a·d + b·c

Bu klasik yöntemde ise 4 çarpma ve 2 toplama / çıkarma işlemi kullanılmıştır. Kısacası gauss yöntemi, 1 çarpma işlemi yerine 3 adet toplama / çıkarma işlemi kullanır. Özellikle çarpmanın çok maliyetli olduğu yüksek basamaklı sayılarda bu yöntem avantaj sağlar.

Örnek

Yukarıda anlatılan yöntemi bir örnek üzerinden gösterelim. Çarpmak istediğimiz sayılar aşağıdaki gibi olsun:

(3+4i) (2 + 5i)

Bu denklemi gauss yöntemi ile çözersek:

k₁ = 2 · (3 + 4) = 2 · 7 = 14

k₂ = 3 · (5 − 2) = 3 · 3 = 9

k₃ = 4 · (2 + 5) = 4 · 7 = 28

x = k₁ − k₃ = 14 – 28 = -14

y = k₁ + k₂. = 14 + 9 = 23

Sonuçta elde edilen karmaşık sayı:

( -14 + 23i )

Olarak bulunur.

int elemanSayisi(node *tree){

if(tree==null)

return 0;

int sayi = 0;

for(int i =0;i<cocuklar;i++){

sayi += elemanSayisi(cocuk[i]);

}

sayi++;

return sayi;

}

Soru 1) Aşağıdaki şekilde bir adet başlangıç ve bir adet hedef düğümü alarak (Aldığınız bu düğümleri belirtiniz) aşağıdaki sorulara cevap veriniz. (30 puan)

1. BFS (Breadth first search, sığ öncelikli arama) ve DFS( Depth first search, derin öncelikli arama) yöntemleri ile dolaşma sonuçlarını yazınız.
   

Başlangıç A ve bitiş E olarak kabul edilmiştir.

BFS :

ACDFBE

DFS:

ABFDE

2. Kruskal ve Prims algoritmalarına göre asgari tarama ağacı (minimum spanning tree) sonuçlarının nasıl bulunduğunu adım adım gösteriniz.

Kruskal için en kısa düğümden en uzun düğüme doğru ağaç dolaşılır:

Yukarıdaki tabloda sağdaki sütun, o adımda alınan kenarı, soldaki sütun ise o ana kadar alınmış düğümleri gösterir. Soldaki sütunda – işareti ile farklı adalar ayrılmıştır.

Prims algoritması

Sırasıyla alınan kenarlar: A-C, C-D,C-F,A-B,B-E

3. Yukarıdaki sorularda verdiğiniz cevaplar ışığında, bu soru için, hangi algoritmaların daha başarılı olduğunu (DFS / BFS, Kruskal / Prims) açıklayınız.

DFS/BFS için aynıdır. Kontrol edilen komşu düğüm sayıları (adjacency list):

DFS: A 2, C 2, D 2, F 1, B 1 , toplam : 8

BFS: A 2, B 2, F 2, D 2 , toplam : 8

Kruskal / Prims için:

Kruskal algoritması daha hızlıdır.

Kontrol edilen kenarlar.

Kruskal algoritması, 5 kenar kontrol etmiştir.

Prims algoritması 13 kenar kontrol etmiştir. Kontrol edilen kenar sayıları aşağıda sıralanmıştır:

2,3,4,2,2 , toplam : 13

Soru 2) Çalıştığınız firmada, bir kelime işlem programı (örneğin MS Word benzeri bir program düşünebilirsiniz) üzerinde yapılan işlemlerin geri / ileri alınmasını sağlayacak (Undo/Redo) kodu yazmanız isteniyor. Bu programda birden çok kişi, birden çok zamanda metin üzerinde değişiklik yapabiliyor (kullanıcılar aynı anda birbirlerinde bağımsız değişiklikler de yapabilir). Sizden istenen herhangi bir kişinin, herhangi bir zamanda yaptığı herhangi bir işlemi geri alabilmeniz için, programda yapılan işlemlerin tutulduğu uygun bir veri yapısı tasarlamanız. Tasarımınızı çizip kullandığınız veri yapısı modelini açıklayınız. (25 puan)

typedef struct node {

char * kullanici;

char * tarih;

islem * i;

node * next;

node * prev;

};

Yukarıdaki düğüm tasarımının amacı, veri yapımızın her düğümünde yapılan işlemi (ki bu işlemin detayı bizi ilgilendirmediği için bir gösterici olarak bırakılmıştır) kimin yaptığını ve tarihi / saat bilgisini tutmaktır.

Yukarıdaki yapı, ayrıca çift bağlı liste (doubly linked list) olarak tanımlanmıştır. Tek bağlı liste olarak da tasarlanabilir di.

Yukarıdaki liste, bir yığın (stack) olarak kullanılacaktır. İşlemler hem geri, hem de ileri alınabileceği için iki yığın gerekmektedir. İşlemler sadece geri alınsa ve geri alınan işlemler bir daha kullanılmamak üzere silinseydi tek yığın yeterli olurdu.

Şekilde görüldüğü üzere, yen işlemler 1. Yığına girerken herhangi bir geri alma işlemi varsa, işlemler 1. Yığından 2. Yığına taşınmakta. İleri alma işlemi ise, 2. Yığından 1. Yığına geri işlemleri yüklemekte.

Yeni işlem geldiğinde ayrıca 2. Yığındaki bilgiler silinerek artık işlemin tekrarlanması engellenebilir (Bu kısım şart olmamakla birlikte güncel programlardaki undo /redo işlemi bu şekilde çalışır)

Yukarıdaki geri / ileri alma işlemini tasarladıktan sonra kişi ve tarih bazlı geri alma tasarımını yapmamız gerekiyor. Bunun için ilave bir indeks oluşturup yığın üzerine bağlıyoruz:

Yukarıdaki şekilde görüldüğü üzere ilave bir ağaç kodlaması ile, yığın üzerindeki bazı düğümleri (node) bağladık. Bu düğümlere kolay erişimi sağlayan bir indekstir ve bir kişinin yaptığı işleme erişilmek istendiğinde, ağaç üzerinde aranıp ardından, yığın üzerinde, bulunan bu düğüme kadar geri alam işlemi yapılabilir.

Benzer bir ağacın, tarih için oluşturulması yeterlidir.

Soru3) Aşağıda bir dizi içerisinde verilen sayıları yığın ağacı (heap) aracılığı ile sıralayınız. Sıralama işlemi sırasında dizideki değişiklikleri adım adım gösteriniz. (öğrenci numaranızın son rakamı çift ise büyükten küçüğe, tek ise küçükten büyüğe sıralayınız) (25 puan)

int a[6] =  5,12,20,18,4,3

Sor büyükten küçüğe sıralama olarak yapılacaktır. Küçükten büyüğe sıralama için aşağıdaki adımların tersten yapılması yeterlidir.

Sıralamayı büyükten küçüğe göre yaptığımıza göre, min heap yani küçükten büyüğe olacak.

Öncelikle heap inşa edilir. Mevcut durum aşağıdaki şekildedir:

Heap inşa edilişi yukarıdaki şekilde sırasıyla gösterilmiştir. Aynı sıra ile dizideki değişim aşağıda gösterilmiştir:

5,12,20,18,4,3

5,4,20,18,12,3

4,5,20,18,12,3

4,5,3,18,12,20

3,5,4,18,12,20

Yukarıdaki inşa işleminden sonra sıralamaya geçilebilir.

İlk alınan sayı 3, heap’in en sonuna yerleştirilir ve geri kalan sayılar kendi arasında yeniden heap halini alır:

5,4,18,12,20 ,3

4,5,18,12,20 ,3

İkinci sayı alınıp heap yeniden inşa edilir

5,18,12,20 ,3,4

Üçüncü sayı alınır:

18,12,20 ,3,4,5

12,18,20 ,3,4,5

Dördüncü sayı:

18,20 ,3,4,5,12

Beşinci sayı:

20, 3,4,5,12,18

Son sayı:

3,4,5,12,18,20

Görüldüğü üzere dizi sıralanmıştır. Yukarıdaki bu adımlar heap çizimi üzerinde aşağdaki şekilde gösterilmiştir.

“Programcılık %10 bilim, %20 yaratıcılık ve %70, yaratıcılığın bilimle çalışmasına çalışmaktır.”