Topological Sort(Sıralama)

Topological sort bir sıralama algoritmasıdır ve graflar üzerinde gerçeklenir. Topological sort'u uygulamak için gerekli olan en önemli koşul ele alınan grafın "directed acyclic graph" olmasıdır. Yani sıralama yapılacak olan grafın herhangi bir düğümünden başlanıldığında diğer düğümleri ziyaret ettikten sonra  bir döngü üzerinde tekrar kendisine gelememe durumudur. Eğer başlanılan düğüme bir döngü üzerinden tekrar geliniyorsa "directed cyclic graph" olur. Bu şartın sağlanması durumunda topological sort şu şekilde uygulanır:
İlk başta kök,root veya herhangi bir düğümün çoçuğu olmayan düğüm, alınır. (Bunun birden fazla olması problem değildir istenilen düğümden başlanılabilir.) Alınan düğümün değeri yazılır ve o düğümün kendisi ve bağlantıları silinir. Daha sonra yine aynı şekilde varolan düğümler içerisinden yeni bir kök seçilir ,değeri yazılır ve tekrar kendisi ve bağlantıları silinir. Bu işlem bütün düğümler bitene kadar tekrarlanır.

Bu işlemleri sonucunda elde edilen sıralama farklılık gösterebilir. Yukarıda da bahsettiğimiz üzere bunun sebebi birden fazla kök düğümü olabileceğinden o anda seçilen kök düğümüne göre değişiklik göstermesidir.

Bir örnek üzerinde bunun nasıl gerçekleştiğini inceleyelim:

Şekil-1

Şekil-1 den başlangıç düğümü olarak "a"' yı seçeriz ve "a" ve "a" nın bağlantılarını sileriz. 

Sıralama : a

Şekil-2

Şekil-2 de kök olarak hem "b" yi hem de "c" yi seçebiliriz. Biz "b" yi alalım. "b" yi sıralamaya ekledikten sonra kendisini ve bağlantılarını silelim.

Sıralama : a,b

Şekil-3

Şekil-3 de kök olarak hem "c" yi hem de "d" yi seçebiliriz. Biz "c" yi alalım. "c" yi sıralamaya ekledikten sonra kendisini ve bağlantılarını silelim.

Sıralama : a,b,c

Şekil-4

Şekil-4 de kök olarak hem "d" yi hem  "f" yi hem de "e" yi seçebiliriz. Biz "d" yi alalım. "d" yi sıralamaya ekledikten sonra kendisini ve bağlantılarını silelim.

Sıralama : a,b,c,d

Şekil-5

Şekil-5 de kök olarak hem "e" yi hem de "f" yi seçebiliriz. Biz "e" yi alalım. "e" yi sıralamaya ekledikten sonra kendisini ve bağlantılarını silelim.

Sıralama : a,b,c,d,e

Şekil-6

Şekil-6 de kök olarak hem "f" yi hem de "g" yi seçebiliriz. Biz "f" yi alalım. "f" yi sıralamaya ekledikten sonra kendisini ve bağlantılarını silelim.

Sıralama : a,b,c,d,e,f

Şekil-7

Şekil-7 de kök olarak hem "g" yi hem de "h" yi seçebiliriz. Biz "g" yi alalım. "g" yi sıralamaya ekledikten sonra kendisini ve bağlantılarını silelim.

Sıralama : a,b,c,d,e,f,g

Şekil-8

Şekil-8 de kök olarak "h"yi seçeriz. "h" yi sıralamaya ekledikten sonra kendisini ve bağlantılarını silelim.

Sıralama : a,b,c,d,e,f,g,h

Şekil-9

Son olarak şekil-9 da "i" yi sıralamaya ekleriz ve sileriz.

Sıralama : a,b,c,d,e,f,g,h,i şeklinde gerçekleşir.

Tabiki bunun dışında gerçekleşecek sıralamalarda mevcut.

Alternatif sıralamalar :


1 ) a, b, c, d, e, f, g, h, i

2 ) a, c, b, f, e, d, h, g, i

3 ) a, b, d, c, e, g, f, h, i

4 ) a, c, f, b, e, h, d, g, i

 Bu yazı yazılırken faculty.kfupm.edu.sa/ics/jauhar/ics202/Unit24_TopologicalSort.ppt powerpoint sunumundan yararlanılmıştır .

İkili Ağaçlar (Binary Trees)

Veri yapılarında , algoritmalarda kullanılan ikili ağaçların özelliği kendisine bağlanacak elamanların sayısının en fazla iki olmasıdır. Her eleman düğüm(node) olarak ifade edilir.Başlangıç düğümüne(root,kök) eklenen elemanlar daha anlaşılır olması bakımından sol çoçuk ve sağ çoçuk olarak ifade edilir.İkili ağaç yapısı elemanlara erişmekte dizilerde kullanılan indis kavramı yerine bağlı listeleri kullanır.Her öğe kendisinden sonra gelenlerin adreslerini tutarak diğer elemanlara ulaşmayı mümkün kılar.

Bilinmesi gereken kavramlar:
Yol(Path):Kökten ,ulaşılması istenen düğüme giderken geçilen düğüm listesi.
Derinlik(Depth): İstenilen düğümün köke olan uzaklığı. Kökün derinliği sıfırdır.
Yükseklik(Height):Bulunulan düğümden itibaren kendisi altında kalan en son düğümle arasında kalan uzaklık.

İkili ağaç örnekleri:

Örnek-1

Örnek-2

Örnek-3

İkili ağaçlarda tüm elemanları ziyaret etmek için kullanılacak yöntemler:

Preorder : ilk kök ziyaret edilir ,sonra sol çoçuk en sonunda da sağ çoçuk ziyaret edilir.

Inorder :İlk sol çoçuk ,sonra kök en son ise sağ çoçuk ziyaret edilir. 

Postorder : İlk sol çoçuk sonra sağ çoçuk en sonunda ise kök ziyaret edilir.

Daha anlaşılır olması açısından bir örnek üzerinde yukarıdaki ifadelerin uygulanışını gösterelim.

Düğüm(Node)       Derinlik(Depth)      Yükseklik(Height)

    A                                  0                                 3

    B                                  1                                 2

    C                                  1                                 2 

    D                                  2                                 1

    E                                   2                                 0

    F                                   2                                 0

    G                                  2                                 1

    H                                  3                                 0

    K                                  3                                 0

Preorder   : A,B,D,H,E,C,F,G,K

Inorder     : H,D,B,E,A,F,C,G,K

Postorder  : H,D,E,B,F,K,G,C,A

İkili ağaçlar herhangi bir elemanı arama,max ve min elemanı bulma, sıralama vb. işlemlerinde oldukça kullanışlıdır. Yakın zamanda paylaşılacak olan örnek C++ kodu üzerinde bunu inceleyeceğiz.


İkili ağaçlarda ,yukarıda gösterilen örnek ağaç yapılarında olduğu gibi , ekleme ve silme işlemleri esnasında farklı türlerde ikili ağaç yapıları oluşabilir. Bizim için en önemli olan, daha iyi bir performans sağlaması açısından, her zaman ikili ağaçları dengeli olarak tutabilmektir.
Dengeli ikili ağaçlar(Balanced binary trees) :Kökün sağ en alt tarafında kalan düğümün derinliği ile sol en alt tarafında kalan düğümün derinliği arasındaki farkın 1 ve 1 den küçük olması ile gerçekleşir.

Bu durumu Örnek 1 üzerinde açıklayalım.
a)Kökün sağ tarafında kalan düğümler : C,F,G,K
b)Kökün sol tarafında kalan düğümler : B,D,E,H

Buna göre sol en altta kalan H düğümü ile sağ en altta kalan K düğümü arasındaki fark sıfır olduğundan bu dengeli bir ağaçtır.

Örnek 3 de ise
c)Kökün sağ tarafında kalan düğümler : kökün sağ tarafında kalan düğüm olmadığından A'yı alıyoruz.
d)Kökün sol tarafında kalan düğümler : B,C,D,E

A'nın derinliği 0 ,sol en altta kalan E düğümünün derinliği 4 olduğundan bu ağaç dengeli değildir.

Dengeli ağaçlar :

1) Complete Binary Tree
2) AVL Trees
3) Red-Black Trees
4) B-Trees

Toshiba Satellite L serisi, Linux Ubuntu 10.04 ve 10.10 yükleme problemi

     
      Benim gibi Toshiba L serisi bir bilgisayara sahipseniz ve Linux tabanlı bir işletim sistemi kullanmak istiyorsanız yükleyememe ,kilitlenme vb. sorunlarla karşı karşıya kalabilirsiniz.(Özellikle ubuntu 10.04 veya 10.10)
      
      Benim karşılaştığım yükleyememe veya yüklemeye geçerken bilgisayarın kilitlenmesi ve bazı adresler göstermesi bios ile ilgili bir sorunmuş.Geçtiğimiz günlerde Toshiba kendi sitesinde bir "bios update" yayınlayarak bu sorunu çözmüş gibi görünüyor ...
      
http://uk.computers.toshiba-europe.com/innovation/download_bios.jsp?service=UK bağlantısından sizin için gerekli olan update versiyonunu bulup artık yeni ubuntu sürümlerine merhaba diyebilirsiniz...

       Herkese "özgür" günler :))      
     

Merhaba :)

Yeni adım attığım bu dünyaya (Varolanın küçük bir penceresi :]  ) edinmiş olduğum bilgileri ve deneyimlerimi sizlerle paylaşmayı amaçlıyorum :) Daha çok bilgisayar bilimine yönelik olmasını düşündüğüm blog a yeniden merhaba :))