Yıllık Arşiv: 2010

Johnson Algoritması–En Kısa Yol Problemi (The Shortest Path Problem)

En Kısa Yol Problemi’nden (The Shortest Path Problem) daha önce bahsetmiştim. Bu yazımda bu problemi çözmek için kullanılan algoritmalardan kısaca bahsedip, Johnson Algoritması’nın üzerinde duracağım. En Kısa Yol Problemi için üretilen algoritmaların bazıları şunlardır;

  • Djikstra Algoritması
  • Bellman Ford Algoritması
  • Floyd – Warshall Algoritması
  • Johnson Algoritması
  • A* Search Algoritması
  • Dinitz Algoritması
  • Tarjan Algoritması
  • GOR Algoritması
  • Dial Algoritması

Algoritmalardan bazılarına kısaca göz atacak olursak;

  • Dijkstra Algoritması: Single Source, Single Pair ve Single Destination problemlerini çözmek için kullanılır. Döngüye girme ihtimalinden dolayı negatif ağırlıklı bağlantıları kabul etmez. Basit bir algoritmadır. Buna karşı performansı yüksektir.
  • Bellman Ford Algoritması: Single Source problemlerini kenar ağırlıkları negatif olduğu durumlarda da çözebilmektedir.
  • A* Search Algoritması: İki nokta arasındaki en kısa yolu aramayı hızlandırmak için sezgisel yöntemler kullanarak çözüm arar.
  • Floyd – Warshall Algoritması : All pairs probleminin çözümünde kullanılır.
  • Johnson Algoritması : Floyd Warshall Algoritması’ndaki gibi all pairs problemini çözmeye yarar. Sparse(dağınık) ve yönlü graflar için kullanılan bir algoritmadır. Sparse graflarda Floyd-Warshall’dan daha hızlı çalışır. Daha yoğun grafiklerde daha hızlı çalışabilir.En önemli özelliği negatif kenarlar içeren graflar için çözüm sunar.

Johnson Algoritması (Johnson’s Algorithm)

1977 yılında Donald B. Johnson tarafından geliştirilmiştir. Bellman Ford, Reweighting ve Dijkstra Algoritması tabanlı, All pairs problemini çözmek için kullanılan bir algoritmadır. Sparse(dağınık) ve directed(yönlü) graflar için kullanılan güzel bir çözüm yoludur. Bağlantıların negatif olmasına izin vermektedir ve bu en önemli özelliğidir. Negatif bağlantıları reweighting yöntemiyle işlem sırasında ağırlıkları yeniden hesaplayarak pozitif ağırlıklara güncellemektedir. Bu yönüyle Floyd Warshall’a benzemektedir fakat O(V3) olan çalışma süresi Johnson Algoritması’nın tercih edilmesine neden olur. Ayrıca Floyd Marshall daha sık graflarda tercih edilirken, Johnson seyrek graflarda daha iyidir. Ağırlıkların pozitif olması durumunda Dijkstra’nın kullanılması daha iyi performans sağlar. Algoritmanın adımlarını aşağıdaki graf üzerinde açıklayalım.

1

  • Adım 1: Öncelikle grafa aşağıda görüldüğü üzere yeni bir düğüm ve bu düğümden grafta bulunan tüm düğümlere bağlantılar eklenir. Bu düğümün ve bağlantılarının ağırlığı sıfır olarak belirlenir.

2

  • Adım 2: Her düğüm için BellmanFord Algoritması bir kez çalıştırılır ve düğümlerin ağırlıkları belirlenir. Aşağıda görüldüğü üzere her düğümün ağırlığı içerisine yazıldı.

image

  • Adım 3 : Adım 4’te Dijkstra Algoritması kullanılacaktır. Bilindiği üzere Dijkstra Algoritması negatif bağlantı uzunluklarını kabul etmemektedir. Bu yüzden bu adımda ağırlıklar tekrar hesaplama yöntemiyle yenilecek ve negatif bağlantı kalmayacaktır. Yeniden hesaplama yöntemi şu şekildedir;  ŵ(u, v) = w(u, v) + d(s, u) – d(s, v)

4 x

Ağırlıkların yeniden hesaplanması Reweighting Teorem ile yapılır. Formülde yeni kenar ağırlığı eski kenar ağırlığı ile düğümün, algoritmanın birinci adımında eklenen yeni düğümüne olan ağırlığı ile toplanır. Bu değerden gidilecek olan düğümün S düğümüne olan ağırlığı çıkarılır ve yeni ağırlık bulunur. Reweightin işlemi sonucunda shortest path değişmezken, ağırlıkların hepsi nonnegative olur. Burada akla şu soru gelebilir; ağırlıkları bu şekilde hesaplayacağımıza tüm düğümlere minimum bağlantı uzunluğunu eklesek olmazmı? Olmaz çünkü bu en kısa yolun değişmesine sebep olabilir. Aşağıda ağırlıkların güncellenmiş hali bulunmaktadır. Kenarların yeni ağırlıklarının bulunma işlemine örnek verecek olursak ; eski ağırlığı 8 olan kenarın yeni ağırlığı yukarıda bahsettiğimiz yöntemle 8 + 0 – (-5) = 13 ‘e olarak hesaplanır.

3

Aşağıdaki grafikta tüm düğümlere minimum düğüm ağırlığının eklenmesi durumunda ortaya çıkacak bozulma görülmektedir. Birinci durumda kısa yol alttaki iken, ikinci durumda üstteki oluyor. Bu metod görüldüğü üzere kısa yolun değişmesine sebep oluyor.
5

  • Adım 4 : Birinci adımda eklenen düğüm graftan silinir ve geri kalan tüm düğümler için Dijkstra Algoritması uygulanır. Tüm çiftler arası en kısa yol bulunur. Aşağıda tüm düğümler için ağırlıkların Dijkstra Algoritması’yla yeniden hesaplanması görülmektedir.

8 9 10

ALGORİTMANIN KARMAŞIKLIĞI

Algoritmanın karmaşıklığına bakalım. Algoritmanın adımlarını kontrol edelim.

  • İlk adımda yeni düğüm ekleniyor ve her düğümün ağırlığı Bellman Ford ile hesaplanıyor. Bu durumun getirdiği karmaşıklık O(VE)’dir.
  • Daha sonra negatif kenarlardan kurtarmak için reweighting işlemi yapılıyor. Bu durumun getirdiği karmaşıklık O(E)’dir.
  • Her düğüm için Djikstra Algoritması’nın getirdiği karmaşıklık O(V2 logV + VE logV )’dir.

Bu durumda Johnson Algoritması’nın karmaşıklığı O(V2 logV + VE logV) olarak hesaplanır.

(V: Düğümler Kümesi , E: Bağlantılar Kümesi )

Kaynaklar

Shortest Path Problem – En Kısa Yol Problemi

Shortest Path Problem yani En Kısa Yol Problemi’nden önce bu konuyla ilgili olan Graph Theory’den bahsetmek istiyorum.

Graph Theory

Graf Teori yani Çizge Kuramı, çizgeleri yani grafları inceleyen matematik dalıdır. Graflar node (yada vertice) yani düğümler ve edge yani bağlantılardan oluşan bir çeşit ağ yapısıdır. Bağlantıların her birinin değeri vardır ve tek yada çift yönlü olabilirler. Bir G grafı, G = (V,E) şeklinde ifade edilir. Burada V düğümler kümesi , E ise bağlantılar kümesini ifade eder.

Shortest Path Problem

Shortest Path Problem, Graph Theory içerisinde önemli bir problemdir. Graf içerisinde belirtilen node’lar arasındaki en kısa yolu bulmayı amaçlar. Bu özelliğiyle Gezgin Satıcı Problemi’ne de (Travelling Salesman) benzer. Ancak Gezgin Satıcı’dan iki noktada ayrılır. Birincisi, hedef düğüme giderken tüm düğümlere uğramak zorunda değiliz. İkincisi de hedefe vardıktan sonra başlangıca dönmüyoruz.

En kısa yollar döngüler içeremez, ancak negatif bağlantı değerleri bulundurabilirler. Bununla birlikte n tane düğümün olduğu bir grafta en kısa yol n-1 kenardan daha fazla kenara sahip olamaz.

Kaynak nodun diğer tüm node’lara olan en kısa yollarını bularak Graph Theory içerisinde yer alan En Kısa Yol Ağacı’nı da (Shortest Path Tree) oluşturabiliriz.

Shortest Path Problemleri

· Single-Source (Single – Destination) : Verilen bir node’dan diğer tüm node’lara olan en kısa yolun bulunması problemidir.

  • Single-Pair: Verilen iki node arası en kısa yolun bulunması problemidir.
  • All-Pairs : Grafta bulunan tüm ikililer arası en kısa yolun bulunması problemidir.

En Kısa Yol Problemi’nin Görüldüğü Yerler

En Kısa Yol Problemi’ni çözen çeşitli algoritmalardan daha sonra bahsedeceğiz, ancak daha önce bu problem nerelerde görülür onlardan bahsetmek istiyorum.

  • Navigasyon cihazlarında güzergah ayarlaması sırasında
  • Dynamic Routing kullanan Network’lerde En ucuz yada hızlı hat ayarlaması yaparken
  • Limancılık, havacılık, postacılık güzergah ayarlaması esnasında
  • Hatta Rubik Cube’ü en az hamlede çözmek için dahi kullanılabilir.
  • Robot hareket planlaması

Kaynaklar

Quad Tree (Dörtlü Ağaç)

Quad dörtlü, tree ağaç demektir. QuadTree adı üstünde bir ağaç yapısıdır. Her nodun (node) dört adet çocuğu (child) vardır. İki boyutlu uzayda kullanılmaktadır. Üzerinde çalışılan bölge dörtlü alanlara bölünerek uygulanır.

Örnek verecek olursak; İlgilendiğimiz alan aşağıdaki gibi olsun. Alanı iki boyutlu bir uzay gibi  düşünelim. Bu bölgeye her hangi bir eleman geldiğinde bölge dörde bölünür. Ağacın şekli üçüncü resimdeki gibi olur. Root’un sadece ilk elemanı doludur.

1  3 2

Bölgeye eleman gelmeye devam etsin. İkinci eleman ilk elemandan farklı bir bölgede olduğu için alan bölme işlemine gerek kalmadı. Ağaçta ise root’un ikinci elemanı B nodu oldu.

quadtree1 5

Yeni elemanımız B ile aynı bölgede olsun. Bu durumda B’nin bulunduğu bölge dörde bölünecek ve ağacın yapısı değişecektir.

6 7

Bölgeye birkaç eleman daha ekleyelim ve ağacın durumuna bakalım.

8 9

E elemanı bölgeye eklendiğinde B’nin bulunduğu alan tekrar dörde bölünür. Ağaçta B bir alta geçerek E ile kardeş olur.

10 11

Bölgeye F elemanı eklendiğinde ise durum aşağıdaki ağaçtaki gibi olur.12 13

Sorularınız olursa yardımcı olmaya çalışırım. Konuyla ilgili buradan da bilgiye ulaşabilirsiniz.

Expression Web 4 çalışmayı durdurdu hatası

expressionweb4Expression Web 4’ü kurup çalıştırdığımda Expression Web 4 çalıştırmayı durdurdu.(Expression Blend 4 has stopped working)hatasıyla karşılaştım. Daha önce kurulu olmasına rağmen .net framework 4.0’ı tekrar kurdum.Ama problem devam ediyordu.İnternette yaptığım araştırma sonucunda sorunun kullandığım antivirüsten kaynaklandığını öğrendim. Kullandığım Kaspersky 2010’da ayarlama yapmak gerekiyormuş. Öncelikle Kaspersky’ı açıyoruz. Sağ üst kısımdan settings’e tıklıyoruz. Daha sonra açılan pencerede web antivirüs sekmesini tıklıyoruz. Yeni gelen ekranda tekrar settings’e tıklıyoruz ve altta görülen Block Dangerous scripts in Microsoft Internet Explorer yazılı checkbox’ı seçilmemiş hâle getiriyoruz. Problem bu şekilde hallolmuş oluyor.

kaspersky

Türkiye’nin ilk bilgi işlem merkezi – IBM Müdürlüğü

Daha önce Türkiye’de kurulan ilk bilgi işlem merkezi olan IBM Müdürlüğü’nden  bahsetmiştim. Buradan önceki yazıma ulaşabilirsiniz. Yaklaşık bir sene sonra bakarlar ki “IBM Müdürlüğü” aslında IBM şirketinin müdürlüğü anlamına gelmektedir. Karayolları’nda IBM Müdürlüğü olması da garip olmaktadır ve etik değildir. Ayrıca hukuka da aykırıdır. Programcılar Orhan Kanpulat’a rahatsızlıklarını bildirirler. Müdür olayın farkındadır ama isim değişikliğinin kolay olmayacağını bilmektedir. Çünkü değişim için Bakanlar Kurulu kararı gerekmektedir. Bu değişimin gerçekleşmesi için 3 sene gerekecektir.Ve bu süre zarfında kurum IBM Müdürlüğü olarak devam edecektir.

Kaynak:Anı ve Fotoğraflarla Bilişim Tarihimiz – Akdoğan Özkan 

Türkiye’deki İlk Bilgisayar: IBM 650

1960 yılında Amerikan ICA fonundan sağlanan teknik yardım ile satın alınan ve Karayolları Genel Müdürlüğü’nde hizmete sunulan IBM 650 Data Processing Machine ,Türkiye’nin ilk bilgisayarı olarak kabul edilir. Bu tarihi sistemin ilginç bazı özellikleri:

  • Birinci nesil,radyo lambalı bir sistem olması,
  • Her biri 10 karakter ve 1 işaretten oluşan 2000 sözcüklük tambur bellek bulunması,
  • Dakikada 78000 toplama-çıkartma, 5000 çarpma ve 138000 mantıksal karar verebilme özelliği,
  • Mantıksal işlem hızı 0,54 ve çarpma işlem hızı 0,77 milisaniyedir.Ortalama bellek erişim hızı 2,448 milisaniye olması,
  • Delikli kart ile bilgi girişi yapılması,
  • Özel kablolarla bağlanan kontrol paneller ile delikli kart irtibatı,
  • Okuma hızı 200 kart/dk. delme/yazma hızı 100kart/dk. olması,
  • Assembler ve Fortran’ın özel programlama dilleri kullanımı (SOAP – FORTRANSIT).

ibm650Programların kartlarla okutularak sisteme intikali ve işleme tabi tutulabilmesi, okuyucu ve yazıcı birimler için hazırlanan,pano üzerinde bulunan ve değişik fonksiyonları olan yuvaların kablolarla bağlandığı “Kontrol paneller” vasıtasıyla gerçekleştirilmekteydi.Neticede, sistemden alınan raporlar  bir satırda alfanümerik 100 karakter yazabilen ve 100 satır/dk. hızındaki yazıcı ile sağlanmaktaydı.

İşin şekline ve ihtiyacına göre bilgilerin birleştirilmesi, ayrılması, tasnifi ve teksiri için de “Sorter”,”Collator”,”Reproducer” gibi kendine özgü kontrol panelleri ile çalışan elektromekanik makinelerden yararlanılmaktaydı.

Kaynak:Anı ve Fotoğraflarla Bilişim Tarihimiz – Akdoğan Özkan

Türkiye’nin ilk bilgi işlem merkezi

Türkiye’de nin ilk  bilgi işlem merkezi Mühendis Orhan Kanpulat liderliğinde 1960 yılında Karayolları’nda kurulur. Türkiye’nin ilk bilgi işlem merkezi (BİM) müdürü de Orhan Kanpulat’tır. Bilgi işlem merkezinin o zamanki adı IBM Müdürlüğü’dür. Aslında bu terimi kullanmak ne kadar doğru tartışılabilir. Ancak o zamanlar IBM demek, bilgisayar demekle hemen hemen aynı şey olduğundan başta pek önemsenmez. IBM Müdürlüğü sürecine gelene kadarki ilk adım TC Karayolları’nda kurulan ‘Delikli Kart Makineleri Şefliği’dir. Bu şeflik daha sonra IBM Şefliği sonra da IBM Müdürlüğüne dönüşmüştür.

Kaynak:Anı ve Fotoğraflarla Bilişim Tarihimiz – Akdoğan Özkan 

Ah Müjgan ah

Semtimizin bir tanesiydi Müjgan, saçları sırtına kadar sırma sırma dökülür.
Elleri ufacık, gözleri dört defa lacivert.
Ve her ne hikmetse o da bana gönüllüydü.
Öyle bir sevdim ki Müjgan’ı dünyamı şaşırdım, haddimi bilemedim,
evleniriz gibi geldi bana.
Evimiz, yuvamız olur, ışığımız yanar, fakir soframız kurulur gibi geldi.
Sahil bahçesinde gazoz içerekten gizli gizli mal-ü hülya kurardık.
Sonrada çarşılara giderdik.
Eşya beğenirdik elden düşme; aynalı konsolumuz topuzlu karyolamız bile olacaktı.

Müjgan’ın her an her bi daim yanında olacaktım ama olmadı gitti.

Nereye mi ? Paraya gitti abicim paraya.
Nasılda sevmiştim yıllarca ben seni.
Her akşam bekledim yollarını.
Elbet bir gün biz yuva kurarız derken,duydum evlenmişsin sen zengin bir gençle.
Zengin olsaydım sensiz kalmazdım.
Her an düşünüp seni hiç ağlamazdım
Param olsaydı aşkım kalırdın.
Seve seve yanımda benimle yaşardın.
Nikah resimlerimizi de çektirdik.
Sonra karpuzcu Raşit ağabeyinin kayınbiraderine borç ederekten nişan yüzüklerimizi de yaptırmıştık.
Ama müjgan takmadı bunu takamadı uçuverdi elimden.
Meğer gizlice altın bir kafes bulmuş kendine.
Müjgan’ın gelinliğini hususi diktirmişler, benim gibi kiralık tel duvak almaya kalkışmamışlar.
Öyle sevindim ki.

Mesut ve bahtiyar olsun diye dualar ettim.
Müjgan gibi bende birbirimize ettiğimiz sözleri,ettiğimiz yeminleri unuttum.
Bir daha mahalleye gelmedi Müjgan, gelemedi.

Bizim dar ve eski sokaklara otomobili sığmıyormuş dediler.
Senede birkaç ay zaten Avrupa’daymış dediler.
Zaman şifalı bir ilaçtır unutursun dediler, unuttum bende.
Hiç aklıma gelmedi.

Hatırlamıyorum bile Müjgan’ı.

Hatırlamıyorum
Öptüğünü düşünüyorum dudak yerine parayı.
Para için açar mı sevişenler arayı.
Madem para mühimdi al koluna parayı.
Çantana da koy aldığın o kocayı.
Zengin olsaydım sensiz kalmazdım.
Her an düşünüp seni hiç ağlamazdım.
Param olsaydı aşkım kalırdın.
Seve seve yanımda benimle yaşardın.

SADRİ ALIŞIK