Order Theory (Sıra Teorisi, Nazariyatül Tertib)

Yazan : Yrd. Doç. Dr. Şadi Evren ŞEKER

Bu yazının amacı, eğitimimiz sırasında sürekli olarak okuduğumuz bir teori olan tertip teorisi (sıralama teorisi , order theory) konusunda bulunan kavramları (preorder, postorder gibi) açıklamaktır. Osmanlıda bu konuya nazariyatül tertip ismi verilmektedir.

Nazariyatül tertip, bilgisayar bilimleri de dahil olmak üzere pek çok matematiksel problemin çözümünde kullanılmaktadır. Örneğin sıralama algoritmaları, arama algoritmaları gibi basit algoritmalar, bu nazariye üzerinden çalışmaktadır.

Her şeye en basitten başlayalım ve ilk okulda öğrendiğimiz < veya > işaretlerinin aslında bu nazariyenin en temel işlemleri olduğunu belirtelim. Buna göre biz tam sayılar arasında bir sıralama (tertip) işlemi yaparken aslında bu teorinin bir uygulamasını yapıyoruz.

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

Partially Ordered Sets (kısmi tertipli kümeler)

Bir kümenin aşağıdaki özellikleri taşıması durumunda verilen isimdir:

a ≤ a (yansıma (reflexive) özelliği)

a ≤ b ve b ≤ a ise a = b (ters simetri özelliği (antisymmetry))

a ≤ b ve b ≤ c ise a ≤ c (geçişlilik (transitivity)).

Örneğin yukarıdaki özelliklerin hepsi sayma sayıları kümesi için geçerlidir.

Bu kümeye İngilizcedeki partially ordered sets isminin ilk iki kelimesini birleştirerek poset ismi de verilir.

Preorder (Öntertip)

Bir değerin diğerinden önce gelmesi prensibine dayanır. Öntertip şartının sağlanması için, bir serideki değerler arasında yansıma (reflexive) ve geçişlilik (transitivity) özellikleri bulunmalıdır. Ancak ters simetri (Anti symmetry) bulunmak zorunda değildir.

Buna göre sadece a < b < c şeklindeki bir seri, öntertip olarak kabul edilebilir ve bu bağlantı özelliklerinde anti simetriden gelen eşitlik bulunmak zorunda değildir.

İşlem Tertipleri

Matematiksel olarak bütün gösterimleri bir dil olarak kabul etmek mümkündür. Bu anlamda işlemleri ifade eden matematiksel gösterimler de birer dildir ve bazı kurallara tabidir. Matematiksel işlemlerin gösteriminde kullanılan yazım şekilleri farklılık gösterebilir.

Örneğin klasik olarak kullanılan matematiksel işlemler,  herhangi bir işlem olmak ve a ve b birer fiil (predicate) olmak üzere, işlemler aşağıdaki şekillerde gösterilebilir:

  1. Inorder (iç tertip infix ): a  b
  2. Preorder (Ön tertip, prefix ):  a b
  3. Postorder (Son tertip, postfix): a b 

Yukarıdaki yazılımlardan iç tertip gösterimi, ülkemizde ilk okullardan beri öğretilen gösterimdir. Örneğin ” 5 + 6 ” gösteriminde + işlemi iki değerin arasında yer almaktadır.

“+ 5 6” ön tertbi veya “5 6 +” son tertibi de çeşitli matematiksel gösterimlerde kullanılmaktadır.

Örneğin programlama dillerinde de sıkça kullanılan fonksiyon çağırımı bir ön tertiptir.

F 4 5

Gösteriminde, F fonksiyonuna 4 ve 5 değerleri birer parametre olarak verilmiştir. Benzer bir kullanım komut satırında da programlara parametre verilirken geçerlidir.

cp a.txt b.txt

Yukarıdaki gösterimde a.txt dosyası, b.txt dosyası olarak kopyalanmış bu sırada, işleme (cp) parametreler prefix (öntertip) sırasıyla verilmiştir.

Ağaç Dolaşma Algoritmaları (Tree Traverse Algorithms)

Sıralama teorisinin diğer bir kullanım alanı da ağaçlardır. Herhangi bir ağacın dolaşılması sırasında yukarıda açıklanan sıralamalar kullanılabilir.

Konuyu en çok kullanılan ikili ağaçlar (binary tree) üzerinden açıklamaya çalışalım.

Yukarıdaki ağaç örneği, ikili ağaç olmanın yanında, ikili bir arama ağacı (binary search tree) olma özelliğini de taşır.

Buna göre her düğümün solundaki düğümler, kendisinden küçük ve sağındaki düğümler ise kendinden büyük değerler taşımak zorundadır.

Yukarıdaki herhangi bir düğümü aldığımızda aşağıdaki gibi bir durum ortaya çıkar.

Yukarıdaki gösterim, ikili arama ağacının bütün düğümleri için geçerlidir. Belki yaprak düğümler (leaf nodes, ağacın en altındaki düğümler) için bu durumun geçerli olmadığını düşünebilirsiniz ancak, en sondaki bu düğümlerin de sol ve sağında alt düğümler bulunmakta ancak bu düğümlerin değeri boş (null) olmaktadır. (daha detaylı bilgi için ikili arama ağacının kodlamasına bakabilirsiniz)

İkili arama ağaçlarında 6 farklı dolaşım mümkündür. Zaten bu değer 3!’dir. Bu dolaşımları yukarıda modellediğimi 3 düğümden oluşan ağaç için sıralayalım:

  1. NLR
  2. NRL
  3. LNR
  4. RNL
  5. LRN
  6. RLN

Yukarıdaki gösterimleri, N (ata) düğümün konumuna göre 3 sınıfta toplamak mümkündür.

  1. Infix (iç tertip , inorder) : LNR ve RNL
  2. Prefix ( öntertip , preorder): NLR ve NRL
  3. Postfix (sontertip, postorder): RLN ve LRN

Yukarıdaki bu gösterimleri birer işlem ağacı olarak da düşünmek mümkündür. Örneğimizi aşağıda çizerek anlatmaya çalışalım:

Yukarıdaki ağaçta bulunan değerleri 6 farklı gösterim için okuyalım:

  1. NLR : + 5 7
  2. NRL : + 7 5
  3. LNR : 5 + 7
  4. RNL : 7 + 5
  5. LRN : 5 7 +
  6. RLN : 7 5 +

Bu gösterimlerden örneğin LNR gösterimi bizim klasik olarak ilk okuldan beri gördüğümüz toplama işlemini ifade eder.

Buna karşılık RNL gösterimi ise işlemin tersini ifade etmektedir ve toplama örneği için doğru olmakla birlikte, çıkarma (-) işleminde LNR ve RNL sırası fark etmektedir.

Şimdi örnek olarak aldığımız ilk ağaca dönelim ve 6 farklı dolaşmaya göre sayıları listeleyelim:

  1. NLR : 10 7 3 9 15 13 18
  2. NRL : 10 15 18 13 7 9 3
  3. LNR : 3 7 9 10 13 15 18
  4. RNL : 18 15 13 10 9 7 3
  5. LRN : 3 9 7 13 18 15 10
  6. RLN : 18 13 15 9 3 7 10

Yukarıdaki ağaç dolaşma algoritmalarından, 1. Ve 2. Sırada olanları (ikisi de öntertiptir (preorder)) literatürde, önce düğüme sonra altındaki düğümlere baktığı için sığ öncelikli dolaşma / arama (breadth first search) olarak isimlendirilir.

Buna karşılık diğer 4 dolaşma sıralaması, önce derindeki bir düğüme sonra ataya baktığı için derin öncelikli (depth first search) olarak geçer.

Yine yukarıdaki sıralamalarda dikkat edilecek bir huşu, LNR gösteriminin, ağacı küçükten büyüğe, RNL gösteriminin ise ağacı büyükten küçüğe sıraladığıdır. Bu özellik, ağaç sıralaması (tree sort) olarak geçen sıralama algoritmasının temelini oluşturur.

İşlem Tertiplerinin Dönüşümü

Örneğin elimizde içtertip (infix) bir işlem bulunsun ve biz bu tertibi örneğin son tertip (postfix) olarak çevirmek isteyelim:

(3 + 5) + (7 + 8 )

Öncelikle yukarıdaki işlemin parçalama ağacını (parse tree) oluşturuyoruz.

Yukarıdaki ağaçta, işlem önceliğine göre parçalama yapılmıştır. Örneğin 3 ve 5 sayılarını birleştiren işlem + işlemidir. Benzer şekilde 7 ve 8 sayıları diğer bir toplama işlemi ile birleştirilmiş ve neticede (kökte) her iki işlem toplanmıştır.

Şimdi bu ağacı öğrendiğimiz ön tertip yöntemine göre dolaşalım:

NLR : + + 3 5 + 7 8

Yukarıdaki gösterim, verilen işlemin son tertibe çevrilmiş halidir. Benzer durum son tertip için de geçerlidir:

LRN : 3 5 + 7 8 + +

Şayet örneğimiz aşağıdaki şekilde olsaydı:

3 + 5 + 7 + 8

Bu durumda parçalama ağacında bir belirsizlik oluşacaktı (ambiguity).

Örneğin, yukarıdaki bu yeni işlem, yukarıdaki parçalama ağacı gibi parçalanabilirken aynı zamanda aşağıdaki ağaçlardan birisi olarak da parçalabilir:

Veya

Yukarıdaki her iki gösterim de aslında matematiksel olarak işlemden çıkarılabilecek sonuçlardır.

Örneğin yukarıdaki işlemi şu 3 farklı şekilde parantezlere almak (veya 3 farklı sırada çözmek mümkündür)

(3+5)+(7+8)

3+(5+(7+8))

((3+5)+7)+8

Bu üç yaklaşımda doğrudur. Bu durumda, işlemin ön tertip çevirimi 3 farklı şekilde olabilecektir ve 3ü de doğrudur:

(3+5)+(7+8) → + + 3 5 + 7 8

3+(5+(7+8)) → + + + 7 8 5 3

((3+5)+7)+8 → + + + 3 5 7 8

Benzer durum son tertip için de geçerlidir:

(3+5)+(7+8) → 3 5 + 7 8 + +

3+(5+(7+8)) → 3 5 7 8 + + +

((3+5)+7)+8 → 8 7 3 5 + + +

Yukarıdaki bu dönüşümlerden görüleceği üzere artık belirsizlik durumu kalkmıştır. Yani dönüşümlerden herhangi birisinin tercih edilmesi halinde iç tertip durumundaki belirsizlik kaybedilir. Bu anlamda tam bir dönüşüm olduğunu söylemek mümkün olmaz.

Tagged:

Yorumlar

  1. Reply
    Emre

    Hocam öncelikle Merhaba,

    Bir sorum olacaktı, resimdeki ağaca göre benden inorder sıralamasına göre valueAtPosition(int k) adında tek parametreli bir metodu implement etmem isteniliyor.
    Örnek verecek olursam, k = 0 için 5 ‘i verecek veya k = 3 için ise 13 ü verecektir.Yani k değeri 0 dan başlıyor.
    Teşekkürler şimdiden.
    İyi Çalışmalar.

  2. Reply
    Emre

    Bu arada 2 tane class’ım var.
    IntTree class’ındaki metodum olan public int valueAtPosition(int k) {
    return root.valueAt(root,k);
    }
    olarak Node classımdaki valueAt(root,k) olarak 2 parametreli metot yarattım.

    IntTree deki initialization –> private Node root = null;
    Node deki ” ” –> int elem; Node left = null; Node right = null;

  3. Reply
    Şadi Evren ŞEKER

    Anladığım kadarıyla java dilinde yazıyorsunuz. Öncelikle tanımınız gereği yaprak düğümler (leaf nodes) , yani hem sağ hem sol değeri null olan düğümlerin 0 inorder değerine sahip olması gerekir. Ardından herhangi bir düğümün değeri null olmayan çocukların inorder değerlerinin toplamı +1 şeklinde hesaplanacak. Ancak sizin durumunuda yaprak düğümler 0’dan başladığı için burada bir istisna var ve bu değerlerin 1 kabul edilmesi gerekiyor (aksi halde 3 çıkması mümkün olmaz).

    Son olarak ağaç dolaşılarak aranan inorder değerine sahip bulunan ilk düğüm (birden fazla düğüm bu inorder değerine sahip olduğu için fonksiyonun birden fazla değer döndürmesi beklenir ancak sizin tanımınızdan LNR sırası ile ağaç dolaşılırken ilk bulduğu düğümü döndürdüğünü anlıyorum, işte bu değer) dönecek.

    Kabaca aşağıdaki gibi yapılabilir (kodu çalıştırıp denemedim ama sanırım çalışır veya belki ufak bir iki yazım hatam olabilir):

    public class Node {

private Node right;
private Node left;
private int nodeValue;
private int order;

public Node root;
public Node (  )
{
// constructor
}
public Node(node root){
 this.root = root;
}

public Node leftNode() {return left;}
public Node rightNode() {return right;}
public int getNodeValue() {return nodeValue;}

void inOrder (Node root )
{ 
  if(root == null) return;  
  inOrder( root.leftNode() ); 
  root.printNodeValue(); 
  inOrder( root.rightNode() );   
 }
void constructOrder(Node root){
  if(root == null) return;
  constructOrder(root.leftNode());
  constructOrder(root.rightNode());
  if(root.leftNode() == null && root.rightNode() == null)
        root.order=0; // leaf node
  else if(root.leftNode() == null)
       root.order = root.rightNode().order + 2;
  else if(root.rightNode()==null)
      root.order = root.leftNode().order+2;
  else 
      root.order = root.leftNode().order + root.rightNode().order + 1;
}
public int valueAtPosition(int k){ // wrapper function
  valueAtPosition(root,k);
}
public int valueAtPosition(Node n,int k){
  if (n==null) return;
  if (n.order == k) return nodeValue;
  valueAtPosition(n.leftNode(),k);
  valueAtPosition(n.rightNode(),k);
}
}

Bir cevap yazın

E-posta hesabınız yayımlanmayacak. Gerekli alanlar * ile işaretlenmişlerdir