Bu Blogda Ara

31 Aralık 2013 Salı

Quadtree ile Hızlandırılmış Geometrik Arama

Bir çok problemin çözümünde geometrik çözümlerden istifade edilebilir. Geometrik çözüm, bir meseleyi geometrik perspektif vasıtasıyla çözmektir, velev ki problemimiz doğrudan geometrik olarak tanımlanmış olmasın. Biraz daha açarsak, doğrudan geometrik olarak tanımlanmış problemlere örnek vermek gerekirse, kapalı bir sistemde hareket eden hava moleküllerinin bulunduğu kap yüzeyiyle ve birbirleriyle olan çarpışma testlerinin yapılması olabilir. Doğrudan geometrik olarak tanımlanmayan problemlere ise bir cemiyetteki insanların birbiriyle olan münasebetlerinin mevcut skaler veriler üzerinden geometrik yorumlama vasıtasıyla tespit edilmesi olabilir. İster doğrudan ister yorumlama vasıtasıyla olsun geometrik hale gelen verilerde en büyük problem hızlı bir şekilde arama yapabilmektir. Arama ile kastedilen işlem, belirli bir bölgedeki veyahut belirli bir noktanın belirli bir mesafedeki komşularının tespitidir. Bu işlemi gerçekleştirmek için akla ilk gelen çözüm en ilkel hali ile zorlama yöntemidir (brute-force). Bu yöntemde tahmin edebileceğiniz gibi aranan noktaların bulunması için tüm noktalar sırayla taranır ve referans noktamıza olan uzaklığına bakılır. Bu usul her zaman doğru sonuca kati suretle varacaktır, fakat muhtemelen en uzun yoldan, zira muhtemel olsun olmasın tüm noktaları taradık ve maliyeti azami tuttuk.


İnsan zihni bu problemi çözerken aslında çok da fazla zorlanmaz, zira sezgilerindeki gelişmişlik arama uzayında orta kısımda bulunan bir referans noktası için yapacağımız komşu aramasını gidipte çok uzaklarda aramaz, doğrudan ilgili kısma bakar. Fakat bilgisayar sistemlerinde genelde durum böyle değildir, veriler hafızada karışık bir sırayla tutulmaktadır (genelde üretim sırasına göre). Bu yüzden hangi nokta hangi noktaya ne kadar yakın bunu verinin geliş sırasında anlamak mümkün değildir. İşte hızlandırma tam da bu noktada mümkün olmaktadır. Aslında hızlandırma yöntemlerinde yapılan genel olarak düzensiz veriyi daha düzenli bir hale getirmekten ibarettir. Meseleyi daha iyi idrak etmek için doğrudan kullanacağımız veriyapısını detaylandıralım. Quadtree veri yapısı alsında bir çeşit ağaç yapısıdır. 2 boyutlu uzayda geçerli olmak üzere bir kök düğümden başlayarak her düğüm 4 alt düğüme ayrılmaktadır. Bu bölümleme kapsadığı noktalardan bağımsız olarak 4 eşit parçaya bölme şeklinde gerçekleşir. Nokta ihtiva eden düğümlere yaprak denmektedir. Bizim tasarımımızda bir yaprakta en fazla 1 nokta mevcut olabilir. Tarama işlemi ise, tıpkı ağacı oluşturduğumuz gibi, aradığımız nokta mevcut düğümün sol (alt-üst) ya da sağ (alt-üst) kısımlarından hangisine ait ise o bölgedeki alt ağacı tarayarak devam ediyoruz, böylelikle yakınlık ihtimali olmayan diğer bölgelerdeki noktaları devre dışı bırakmış ve bu yükten kurtulmuş oluyoruz, aynı insanın sezgisel olarak yaptığı gibi. Örnek ağaçlara bir göz atalım:

Veriyapısı ve algoritma hakkında daha detaylı bilgi için: http://en.wikipedia.org/wiki/Quadtree

Amacım algoritmayı tam anlamıyla anlatmak değil, sadece bir gerçekleme örneği sağlamak. Bu sebeple daha fazla detaylandırmak istemiyorum. Gerçekleme için C++ dili ve görselleştirme için OpenGL kütüphanesini kullandım. Performans arttırımı için dar boğaz olan dinamik bellek ayrımı (dynamic memory allocation) için bir iyileştirme gerçekleştirdim, fakat bu iyileştirmenin çalışabilmesi için maksimum nokta sınırının belirlenmesi gerekiyor, bu bilinmiyorsa daha farklı bir usul geliştirilebilir veya bu iyileştirme kaldırılabilir. Eğer kararlılık (stability) sizin için daha önemli ise bu iyileştirmeyi kaldırmanızı veya gözden geçirmenizi tavsiye ederim, zira bazı durumlarda (nokta yoğunlaşması gibi) hatalarla karşılaştım ayrıca aynı anda birden fazla ağaç üretmesine mani oluyor (no multiple instance).

Not: Nokta tanımında açık kaynak kodlu ve ücretsiz temin edilebilen GTL (https://code.google.com/p/geometry/) kütüphanesinden istifade ettim. 

/*
 * Point.h
 *
 *  Created on: Oct 24, 2013
 *      Author: ramazan
 */

#ifndef POINT_H_
#define POINT_H_

#include <gtl/vec2.hpp>
#include <gtl/vec3.hpp>

#include "Utility.h"
#include <algorithm>

using namespace gtl;

class Point {
public:
 Point() {
  color.setValue(0, 0, 1);
  location.setValue(randomFloat() * SCREEN_WIDTH, randomFloat() * SCREEN_HEIGHT);
 }

 void walk() {
  location += Vec2f(randomSignedFloat() * 30, randomSignedFloat() * 30);
  location[0] = std::max(location[0], 0.f);
  location[0] = std::min(location[0], (float)SCREEN_WIDTH);

  location[1] = std::max(location[1], 0.f);
  location[1] = std::min(location[1], (float)SCREEN_HEIGHT);
 }

 Vec2f location;
 Vec3f color;
};


#endif /* POINT_H_ */
/*
 * Utility.h
 *
 *  Created on: Oct 24, 2013
 *      Author: ramazan
 */

#ifndef UTILITY_H_
#define UTILITY_H_

#include <stdlib.h>
#include <stdio.h>

#define SCREEN_WIDTH 800
#define SCREEN_HEIGHT 600

#define THREESHOLD 0.000001
#define PARMEQ(x, y) (fabs(x - y) <= THREESHOLD)

static inline float randomFloat() {
 return (float)rand()/(float)RAND_MAX;
}

static inline float randomSignedFloat() {
 const float r = randomFloat();
 return r - 0.5f;
}


#endif /* UTILITY_H_ */

#ifndef QUADTREE_H_
#define QUADTREE_H_

#include <assert.h>
#include <vector>

#include "Point.h"

// You can remove all optimization lines together. 

#define MAX_POINT_CAPACITY 1000000 // Optimization line!

class QuadNode {
public:
 QuadNode() {
  leaf = true;
  point = NULL;
  children[0] = children[1] = children[2] = children[3] = NULL;
 }

 ~QuadNode() {
  for (int i = 0; i < 4; i++) {
   QuadNode *child = children[i];
   if (child != NULL)
    delete child;
  }
 }

 void insert(const Point &point) {
  if (leaf && this->point == NULL) {
   this->point = &point;
  }
  else {
   makeChild(-1, -1);
   makeChild(-1, 1);
   makeChild(1, -1);
   makeChild(1, 1);

   QuadNode *node = NULL;

   if (leaf) {
    const Point *thisPoint = this->point;
    this->point = NULL;
    node = findChild(*thisPoint);
    node->insert(*thisPoint);
   }

   node = findChild(point);
   node->insert(point);

   leaf = false;
  }
 }

 void query(const Vec2f &center, const float radius, std::vector<const Point *> &points) {
  const float absDX = fabs(center[0] - this->center[0]);
  const float absDY = fabs(center[1] - this->center[1]);

  if (absDX <= (halfSize[0] + radius) && absDY <= (halfSize[1] + radius)) {
   if (point != NULL) {
    Vec2f disn = point->location - center;
    const float dist = disn.length();

    if (dist <= radius)
     points.push_back(point);
   }
   else {
    for (int i = 0; i < 4; i++) {
     QuadNode *child = children[i];
     if (child != NULL)
      child->query(center, radius, points);
    }
   }
  }
 }

 void render() {
  const Vec2f p0 = center + Vec2f(-halfSize[0], halfSize[1]);
  const Vec2f p1 = center + Vec2f(-halfSize[0], -halfSize[1]);
  const Vec2f p2 = center + Vec2f(halfSize[0], -halfSize[1]);
  const Vec2f p3 = center + Vec2f(halfSize[0], halfSize[1]);

  glColor3f(1, 0, 0);
  glBegin(GL_LINES);
  glVertex2fv(p0.getValue());
  glVertex2fv(p1.getValue());

  glVertex2fv(p1.getValue());
  glVertex2fv(p2.getValue());

  glVertex2fv(p2.getValue());
  glVertex2fv(p3.getValue());

  glVertex2fv(p3.getValue());
  glVertex2fv(p0.getValue());
  glEnd();

  for (int i = 0; i < 4; i++) {
   QuadNode *child = children[i];
   if (child != NULL)
    child->render();
  }
 }
private:
 int makeChild(const float dX, const float dY) {
  int index = -1;
  float newX = halfSize[0] / 2;
  float newY = halfSize[1] / 2;
  if (dX < 0) {
   newX = -newX;
   if (dY < 0) {
    index = 1;
    newY = -newY;
   }
   else
    index = 0;
  } else {
   if (dY < 0) {
    index = 2;
    newY = -newY;
   }
   else
    index = 3;
  }

  verifyChild(index, center + Vec2f(newX, newY));

  return index;
 }
 QuadNode *findChild(const Point &point) {
  const float dX = point.location[0] - center[0];
  const float dY = point.location[1] - center[1];

  return children[makeChild(dX, dY)];
 }

 void verifyChild(const int index, const Vec2f newCenter) {
  assert(index >= 0 && index <= 3);

  if (children[index] == NULL) {
   children[index] = new QuadNode();
   assert(children[index] != NULL);
   children[index]->center = newCenter;
   children[index]->halfSize = halfSize / 2;
  }
 }

private:
 static char memory[]; // Optimization line!
 static int memoryIndex; // Optimization line!

public:
 void *operator new(size_t size) { // Optimization line!
  assert(memoryIndex < MAX_POINT_CAPACITY); // Optimization line!
  return &memory[memoryIndex++ * size]; // Optimization line!
 } // Optimization line!

 void operator delete(void *p) { // Optimization line!
  p = NULL; // Optimization line!
 } // Optimization line!

public:

 // 0 3
 // 1 2
 QuadNode *children[4];
 const Point *point;
 Vec2f center;
 Vec2f halfSize;
 bool leaf;
};

int QuadNode::memoryIndex = 0; // Optimization line!
char QuadNode::memory[sizeof(QuadNode) * MAX_POINT_CAPACITY] = { }; // Optimization line!

class Quadtree {
public:
 Quadtree(const Vec2f &center, const float w, const float h) {
  root = new QuadNode();
  root->center = center;
  root->halfSize.setValue(w / 2, h / 2);
 }

 ~Quadtree() {
  if (root != NULL) {
   delete root;
  }
 }

 void insert(const Point &point) {
  assert(root != NULL);

  root->insert(point);
 }

 void render() {
  assert(root != NULL);
  root->render();
 }

 void query(const Vec2f &center, const float radius, std::vector<const Point *> &points) {
  assert(root != NULL);

  root->query(center, radius, points);
 }

 QuadNode *root;
};


#endif /* QUADTREE_H_ */

// main.cpp

#include <iostream>
#include <glut\\glut.h>
#include <time.h>

#include "Quadtree.h"

#define RENDER_WAIT_TIME 25
#define NUMBER_OF_POINTS 30000

using namespace std;

Point *points = NULL;
Quadtree *qt;

Vec2f qCenter(300, 400);
float radius = 100;

void display(void) {
    glClear(GL_COLOR_BUFFER_BIT);
    glLoadIdentity();

    glBegin(GL_POINTS);
    for (int i = 0; i < NUMBER_OF_POINTS; i++) {
     glColor3fv(points[i].color.getValue());
     glVertex2fv(points[i].location.getValue());
    }
    glEnd();

    glColor3f(0, 1, 0);
    glBegin(GL_LINES);
    for (int i = 0; i < 360; i++) {
     Vec2f p1 = qCenter + Vec2f(cos((i * M_PI / 180.f)) * radius, sin((i * M_PI / 180.f)) * radius);
     Vec2f p2 = qCenter + Vec2f(cos(((i + 1) * M_PI / 180.f)) * radius, sin(((i + 1) * M_PI / 180.f)) * radius);
     glVertex2fv(p1.getValue());
     glVertex2fv(p2.getValue());
    }
    glEnd();

    if (qt != NULL)
     qt->render();

    //glFlush();
    glutSwapBuffers();
}

void mouse(int btn, int state, int x, int y) {
    //if(btn==GLUT_LEFT_BUTTON && state == GLUT_DOWN) axis = 0;
}

void search() {
 if (qt == NULL)
  return;
 std::vector<const Point *> qpoints;
    qt->query(qCenter, radius, qpoints);

    std::cout<<qpoints.size()<<std::endl;
    for (int i = 0; i < NUMBER_OF_POINTS; i++) {
  points[i].color.setValue(0, 0, 1);
     for (unsigned int j = 0; j < qpoints.size(); j++) {
      if (&points[i] == qpoints[j])
       points[i].color.setValue(0, 1, 0);
     }
    }
}

void mainLoop(int value) {
    glutPostRedisplay();
    glutTimerFunc(RENDER_WAIT_TIME, mainLoop, 0);
}

void build() {
 qt = new Quadtree(Vec2f(SCREEN_WIDTH / 2, SCREEN_HEIGHT / 2), SCREEN_WIDTH, SCREEN_HEIGHT);
    for (int i = 0; i < NUMBER_OF_POINTS; i++)
     qt->insert(points[i]);
}

void keyPressed(unsigned char key, int x, int y) {
    if (key == 'x')
        exit(0);

 if (key == 'w')
  qCenter += Vec2f(0, 10);

 if (key == 's')
  qCenter += Vec2f(0, -10);

 if (key == 'a')
  qCenter += Vec2f(-10, 0);

 if (key == 'd')
  qCenter += Vec2f(10, 0);

 if (key == 'r') {
  for (int i = 0; i < NUMBER_OF_POINTS; i++)
   points[i].walk();
  build();
 }

 search();
}

void myReshape(int w, int h) {
    glViewport(0, 0, w, h);
    glMatrixMode(GL_PROJECTION);
    glLoadIdentity();
    glOrtho(0.0f, 800, 0, 600, 1.0f, -1.0f);
    glMatrixMode(GL_MODELVIEW);
}

void keySpecial(int key, int x, int y) {
    if (key == GLUT_KEY_F4)
        exit(0);
}

void init() {
    glShadeModel(GL_FLAT);
    glPixelStorei(GL_UNPACK_ALIGNMENT, 1);
    glPointSize(3);

    points = new Point[NUMBER_OF_POINTS];
 //points[0].location.setValue(100, 100);
 //points[1].location.setValue(110, 120);
 //points[2].location.setValue(105, 105);
 build();
 search();
}

int main(int argc, char** argv) {
    srand(time(NULL));
    glutInit(&argc, argv);
    glutInitDisplayMode(GLUT_DOUBLE | GLUT_RGBA);
    glutInitWindowSize(SCREEN_WIDTH, SCREEN_HEIGHT);
    glutCreateWindow("Quadtree");
    glutReshapeFunc(myReshape);
    glutDisplayFunc(display);
    glutKeyboardFunc(keyPressed);
    glutSpecialFunc(keySpecial);
    init();
    glutTimerFunc(RENDER_WAIT_TIME, mainLoop, 0);
    glutMouseFunc(mouse);
    glutMainLoop();
    return 0;
}


Bir kaç deneme yapalım:

10 adet nokta

 100 adet nokta

 5000 adet nokta

 30000 adet nokta
 
Bu bölümde 2 boyutlu düzlem üzerindeki geometrik problemlerin çözümünde kullanılan arama işlemini hızlandıran bir veriyapısını inceledik. Aynı veri yapısı 3 boyutlu uzayda da uygulanabilir (Octree - http://en.wikipedia.org/wiki/Octree). Mantık olarak aynı yalnızca 4 yerine 8 eşit parçaya ayrılmaktadır. Performans değerlendirmesini zaman cinsinden değerleri belirterek yapmak istemiyorum, kullandığım bilgisayar üzerinde brute-force yöntemine göre tahmin edebileceğiniz gibi (beklendiği üzere) çok büyük oranda hızlanma sağladı. Bunu kendi probleminize uygulayarak görebilirsiniz. Basit düzeyde anlatmaya çalıştım, umarım işinize yarar.

24 Kasım 2012 Cumartesi

Yapay Sinir Ağları İleri Besleme & Geri Yayılım Algoritmaları - XOR Örneği




http://scitechdaily.com/ibm-supercomputer-simulates-530-billion-neurons-100-trillion-synapses/


IBM'in yapmış olduğu çalışmanın haberini okuduktan sonra yapay zeka meselesi hakkında küçük bir yazı yazmaya karar verdim. Tabiki haberdeki çalışmaya nazaran bizim yapacağımız örnek çok iptidai kalmaktadır. Lakin buradaki maksadım bir şekilde meseleye giriş yapmak bilahare daha gelişmiş örneklerle konuyu izah etmek şeklinde olacaktır.

Yapay zeka çok geniş bir kavram ve bir çok alt dalları bulunmaktadır (bkz: http://en.wikipedia.org/wiki/List_of_basic_artificial_intelligence_topics). Ben burada giriş mahiyetinde Yapay Sinir Ağları (bkz: http://en.wikipedia.org/wiki/Artificial_neural_network) hususunda ileri besleme (Feed forward bkz: http://en.wikipedia.org/wiki/Feedforward_neural_network) ve geri yayılım (bkz: http://en.wikipedia.org/wiki/Back-propagation) algoritmalarını kullanarak artık klasikleşmiş ve tabiri caizse bıktırmış olan XOR örneğini gerçekleyeceğim. 

Yukarıda verdiğim bağlantılara göz atarsanız algoritmanın nasıl çalıştığını kolayca anlayabilirsiniz. Bu noktada fazla bir teferruat icap etmiyor zira yapacağımız örnekteki XOR problemi 2 neron hidden layer için 1 neron da output layer için kafidir. Mühim bir not; biz bu örnekte BIAS değerini tüm neronlara ayrı ayrı vermek yerine bir kukla neron (dummy neuron, ağırlıkları ve çıktısı değişmeyen) kullanacağız.

Biraz gerçekleme (implementation) detaylarına göz atalım. 

Uygulamayı Java ile yapacağız. Aslınca C gibi bir dil ile çok daha basit ve hızlı bir şekilde gerçeklenebilirdi lakin müstakbel uygulamalarımızda yapacağımız muameleler daha karmaşık olacağından bu yapı ileride bize fayda sağlayacaktır, şu anda aksi gibi görünse dahi.


Temel olarak Object-Oriented yapı:

Neuron (Class)
NN (Class)
IActivation (Interface)
SigmoidActivation (Class) -> IActivation
DummyActivation (Class) -> IActivation


Başlamdan önce belirlenmesi gereken ilk husus neronların ilk ağırlık değerleridir, burada önceden çalıştığı bilinen bir küme de seçilebilir ya da sözde rastgele değerlerde seçilebilir, neticede kötü seçilen değerler sadece sonuca ulaşma süremizi uzatacaktır. Biz rastgele değerler üreteceğiz bu yüzden programı her çalıştırdığınızda farklı bekleme süreleri ile karşılacaksınız. Ayrıca eğitim sürecinde iterasyon sayısını bir hudut koyuyoruz çünkü bazı durumlarda gelen değerler deltaW değeri sıfıra çok yaklaştığı için istenilen değere (desired value) bir türlü yaklaşılamıyor ve çok bekleme yaşanıyor. Bu sebeple azami tekerrür 3.000.000 olarak seçiyoruz, beklenen hata nispetini ise 0.005 olarak seçtim. Bu değerler tamamen keyfi olup siz de istediğiniz gibi değiştirebilirisiniz.

Kaynak kodda herhangi bir dış kütüphane kullanmadım, doğrudan derleyip çalıştırabilisiniz.

Şimdi kaynak kodumuza bir göz atalım:




// Main.java

package ann.xor;

/**
 *
 * @author ramazan
 */
public class Main {

    public static String quantizeResult(float result) {
        return Integer.toString(Math.round(result)) + " (" + Float.toString(result) + ")";
    }
    
    public static void main(String[] args) {
        NN nn = new NN(5E-3f, 1.0f, 0.1f);
        SigmoidActivation sa = new SigmoidActivation();
        DummyActivation da = new DummyActivation();
        float BIAS = -1f;

        Neuron input1 = new Neuron(da, 0);
        Neuron input2 = new Neuron(da, 0);
        Neuron input3 = new Neuron(da, 0); // BIAS.
        Neuron hidden1 = new Neuron(sa, 3);
        Neuron hidden2 = new Neuron(sa, 3);
        Neuron hidden3 = new Neuron(da, 3); // Dummy neuron.
        Neuron output1 = new Neuron(sa, 3);

        nn.addInputNeuron(input1);
        nn.addInputNeuron(input2);
        nn.addInputNeuron(input3);

        nn.addHiddenNeuron(hidden1);
        nn.addHiddenNeuron(hidden2);
        nn.addHiddenNeuron(hidden3);

        nn.addOutNeuron(output1);

        hidden3.setDummy(true);
        input3.setOutput(BIAS);

        System.out.println("All inputs & weights has been set.");
        System.out.println("Training has been started.");
        
        int iteration = 0;
        do {
            iteration++;
            
            input1.setOutput(0);
            input2.setOutput(0);
 
            output1.desired = 0;

            nn.train();

            input1.setOutput(0);
            input2.setOutput(1);

            output1.desired = 1;

            nn.train();

            input1.setOutput(1);
            input2.setOutput(0);

            output1.desired = 1;

            nn.train();

            input1.setOutput(1);
            input2.setOutput(1);

            output1.desired = 0;

            nn.train();
            
            if (iteration % 50000 == 0) {
                System.out.println("-------------------------------");
                System.out.println("Current iteration:" + iteration);
                System.out.println("Current error:" + nn.getE());
                System.out.println("-------------------------------");
            }
        } while(!nn.learnt() && iteration < 3000000);
        
        System.out.println("Training has been completed.");
        System.out.println("Total iteration: " + iteration + ", accepted error: " + nn.getE());
        System.out.println("Test cases are in progress...");
        
        input1.setOutput(1);
        input2.setOutput(0);

        nn.test();

        System.out.println("1 XOR 0 = " + quantizeResult(nn.getOutput(0).getOutput()));

        input1.setOutput(1);
        input2.setOutput(1);

        nn.test();

        System.out.println("1 XOR 1 = " + quantizeResult(nn.getOutput(0).getOutput()));

        input1.setOutput(0);
        input2.setOutput(1);

        nn.test();

        System.out.println("0 XOR 1 = " + quantizeResult(nn.getOutput(0).getOutput()));

        input1.setOutput(0);
        input2.setOutput(0);

        nn.test();

        System.out.println("0 XOR 0 = " + quantizeResult(nn.getOutput(0).getOutput()));
    }
}



// NN.java

package ann.xor;

import java.util.ArrayList;
import java.util.List;

/**
 *
 * @author ramazan
 */
public class NN {
   
    private List<neuron> inputLayer;
    private List<neuron> hiddenLayer;
    private List<neuron> outputLayer;
    private float E;
    private float e;
    private float lambda;
    private float nu;
    
    public NN(float E, float lambda, float nu) {
        inputLayer = new ArrayList<>();
        hiddenLayer = new ArrayList<>();
        outputLayer = new ArrayList<>();
        this.E = E;
        e = 0;
        this.lambda = lambda;
        this.nu = nu;
    }
    
    public void addInputNeuron(Neuron neuron) {
        inputLayer.add(neuron);
    }
    
    public void addHiddenNeuron(Neuron neuron) {
        hiddenLayer.add(neuron);
    }
    
    public void addOutNeuron(Neuron neuron) {
        outputLayer.add(neuron);
    }
    
    public Neuron getOutput(int index) {
        return outputLayer.get(index);
    } 
    
    public void train() {
        feedForward();
        calculateError();
        backPropagation();
        //System.out.println("Error value: " + e);
    }
    
    public void test() {
        feedForward();
    }
    
    protected void feedForward() {
        for (Neuron nH : hiddenLayer) {
            float inputs = 0;
            for (Neuron nI : inputLayer) {
                int i = inputLayer.indexOf(nI);
                inputs += nI.getOutput() * nH.getWeight(i);
            }
            nH.setInput(inputs);
            nH.activate(lambda);
        }
        
        for (Neuron nO : outputLayer) {
            float inputs = 0;
            for (Neuron nH : hiddenLayer) {
                int i = hiddenLayer.indexOf(nH);
                inputs += nH.getOutput() * nO.getWeight(i);
            }
            nO.setInput(inputs);
            nO.activate(lambda);
        }
    }
    
    protected void calculateError() {
        e = 0;
        for (Neuron nO : outputLayer) {
            nO.error = nO.desired - nO.getOutput();
            e += (float) Math.pow(nO.error, 2);
        }
        
        e = (float)Math.sqrt(e); 
    }
    
    protected void backPropagation() {
        for (Neuron nO : outputLayer) {
            nO.calculateDelta(lambda, nO.error);
            for (Neuron nH : hiddenLayer) {
                int i = hiddenLayer.indexOf(nH);
                nH.calculateDelta(lambda, nO.getDelta() * nO.getWeight(i));
                float diff = nu * nO.getDelta() * nH.getOutput();
                nO.setWeight(i, nO.getWeight(i) + diff);
            }
        }
        
        for (Neuron nH : hiddenLayer) {
            for (Neuron nI : inputLayer) {
                int i = inputLayer.indexOf(nI);
                float diff = nu * nH.getDelta() * nI.getOutput();
                nH.setWeight(i, nH.getWeight(i) + diff);
            }
        }
    }

    public float getE() {
        return e;
    }
    
    public boolean learnt() {
        return (e < E);
    }
}



// Neuron.java

package ann.xor;

import java.util.Random;

/**
 *
 * @author ramazan
 */
public class Neuron {

    private float[] weights;
    private float input;
    private float output;
    private IActivation activation;
    private float delta;
    public float desired;
    public float error;
    private boolean dummy;
    private static final Random random = new Random();

    public Neuron(IActivation activation, int weights) {
        this.weights = new float[weights];
        this.activation = activation;
        delta = 0;
        dummy = false;
        error = desired = 0;
        
        for (int i = 0; i < weights; i++) {
            this.weights[i] = getRandomWeight();
        }
    }
    
    protected final float getRandomWeight() {
        final float r = random.nextFloat();
        final float range = 2.4f / weights.length;

        return (r * 2 * range) - range;
    }

    public float getWeight(int index) {
        return weights[index];
    }

    public void setWeight(int index, float weight) {
        if (!dummy) {
            weights[index] = weight;
        }
    }

    public float getInput() {
        return input;
    }

    public void setInput(float input) {
        this.input = input;
    }

    public float getOutput() {
        return output;
    }

    public void setOutput(float output) {
        this.output = output;
    }

    public float getDelta() {
        return delta;
    }

    public boolean isDummy() {
        return dummy;
    }

    public void setDummy(boolean dummy) {
        this.dummy = dummy;
    }
    
    public void activate(float lambda) {
        float value = input;
        if (!dummy) {
            value *= -lambda;
        }
        output = activation.activate(value);
    }

    public void calculateDelta(float lambda, float error) {
        if (!dummy) {
            delta = error * lambda * activation.derivative(output);
        }
    }
}



// IActivation.java

package ann.xor;

/**
 *
 * @author ramazan
 */
public interface IActivation {
    public float activate(float input);
    public float derivative(float input);
}



// SigmoidActivation.java

package ann.xor;

/**
 *
 * @author ramazan
 */
public class SigmoidActivation implements IActivation {

    @Override
    public float activate(float input) {
        return (float) (1. / (1. + Math.exp(input)));
    }

    @Override
    public float derivative(float input) {
        return input * (1 - input);
    }
    
}



// DummyActivation.java

package ann.xor;

/**
 *
 * @author ramazan
 */
public class DummyActivation implements IActivation {

    @Override
    public float activate(float input) {
        return input;
    }

    @Override
    public float derivative(float input) {
        return input;
    }
}



Şimdi örnek bir çıktı üretelim:

run:
All inputs & weights has been set.
Training has been started.
-------------------------------
Current iteration:50000
Current error:0.02354227
-------------------------------
-------------------------------
Current iteration:100000
Current error:0.014160486
-------------------------------
-------------------------------
Current iteration:150000
Current error:0.011045283
-------------------------------
-------------------------------
Current iteration:200000
Current error:0.009226563
-------------------------------
-------------------------------
Current iteration:250000
Current error:0.008103463
-------------------------------
-------------------------------
Current iteration:300000
Current error:0.0073397583
-------------------------------
-------------------------------
Current iteration:350000
Current error:0.006666307
-------------------------------
-------------------------------
Current iteration:400000
Current error:0.00628476
-------------------------------
-------------------------------
Current iteration:450000
Current error:0.0058559924
-------------------------------
-------------------------------
Current iteration:500000
Current error:0.0055325483
-------------------------------
-------------------------------
Current iteration:550000
Current error:0.0051981094
-------------------------------
Training has been completed.
Total iteration: 586265, accepted error: 0.004999997
Test cases are in progress...
1 XOR 0 = 1 (0.9973595)
1 XOR 1 = 0 (0.004999945)
0 XOR 1 = 1 (0.9919734)
0 XOR 0 = 0 (0.0039330246)

BUILD SUCCESSFUL (total time: 4 seconds)


Bu basit örnek ile konuyu teorik olarak okuduktan sonra pratik olarak uygulamasını görerek daha iyi anlaşılacağı kanaatindeyim. Bir sonraki yazıda, yine klasikleşmiş olan tanıma (recognition) uygulamalarından bir örnek yapabilirim veyahut farklı bir anlada mesela Multi-agent systems simulation bir çalışma olabilir. Henüz karar vermedim. :)

Umarım faydalı olmuştur, böylelikle uzunca bir aradan sonra yazı yazabilmenin huzuruyla sizlere veda ediyorum, Allah'a emanet olunuz...

14 Nisan 2011 Perşembe

IREM Oyun Motoru Çalışması - Rapor 1

Herkese merhaba,

bu yazımda bitirme projesi olarak yaptığımız IREM Oyun Motoru projesinden bahsetmek istiyorum. Bu projeyi üniversite lisans bitirme projesi olarak toplam 4 kişilik bir ekip ile yapıyoruz. Profesyonel düzeyde bir proje olduğunu söyleyemem, fakat elimizden geldiğince gelişime açık bir tasarım ve esnek bir kodlama yapmaya çalışıyoruz. Proje henüz sonuçlanmadı fakat dönem sonuna doğru yaklaştıkça zaman kısıtı yüzünden projeyi bir noktada sınırlayıp nihayete erdirmek zorundayız. Gelin şuan ki aşamaya kadar neler yaptığımıza bir göz atalım.

Teknik Alt Yapı ve Sınırlar
C++ programlama dili üzerinden kodlamayı gerçekleştirdik. Grafik arayüzü olarak Microsoft DirectX API kullandık. Proje dahilinde singleton, façade, strategy, abstract factory vb. tasarım desenleri uygulandı. Networking, AI (yapay zeka), 3d sound, shader effects (HLSL) gibi modüllerin yalnızca tanımlaması yapıldı gerçeklenmedi. İleriki aşamalarda mevcut kod değiştirilmeden rahatlıkla bu modüller gerçeklenebilir. Fiziksel etkileşim yalnızca çarpışma testi ve parçacık dinamiği üzerinden gerçeklendi.

Teknik Üst Yapı ve Tasarım
Geliştirdiğimiz oyun motorunun temel fikri; yaklaşık olarak %90 seviyesinde nesne yönelimli, kolay programlanabilir, anlaşılır ve çevik (agile) geliştirmeye açık bir tasarım sağlamaktır. Bu yüzden inceledeğim bir çok modern oyun motorlarından da esinlenerek birbiriyle alakası olmayan tüm işlemleri ayırarak kendi aralarında bir yönetici sınıf atadım. Bu yönetici sınıflar singleton tasarım şablonu ile yalnız ve tek bir adet üretilerek çok başlılık sorununa mahal vermeden işlem yapmaktadır. Bu noktada sizlerle daha projenin ilk aşamalarında şekillendirmek adına çıkarttığım sınıf tasarımını paylaşmak istiyorum. İsterseniz tasarıma bir göz atalım, böylelikle kurgu kafamızda biraz daha somutlaşacaktır, daha sonra detaylı incelemeye devam edelim.



Buradaki bazı sınıfın yapısı değişmiş ve yine burada belirtmediğim bir çok yeni sınıf eklenmiş olsa da sistemin genel mantığını ifade ettiğini düşünüyorum.

Çekirdek uygulamanın yanında ek olarak pencere yöneticisi (window manager) ve arazi üreticisi (terrain generator) gibi araçlar geliştirdik. Bunlar programcıya hız kazandıracak araçlardır.

Son Durum & Karşılaştığımız Sorunlar
Gelelim şuanda projenin ne aşamada olduğu ve ne gibi sorunlarla karşılaştığımız kısmına. Projede şu anda çekirdek sınıf vasıtasıyla bir oyun işlemi başlatıp, sahne yöneticisi sınıfı vasıtasıyla istediğimiz sayıda birbirinden bağımsız sahneler üretebiliyoruz. Bu sahneler arasında gecikme olmaksızın anlık geçişler yapabiliyoruz. Çizdirilebilir nesne sayısı çok fazla olduğundan yavaşlayan bir sahne diğer bir sahneyi etkilememektedir. Sahneye eklediğimiz nesneleri kök düğüme ya da alt düğümlerine bağlayabiliyoruz. Böylelikle nesneleri grup olarak hareket ettirebiliyoruz. Kamera, ışık, model ve sabit nesneler sahneye eklebilmektedir. Uygulama başlatılmadan önce ayar penceresi gösterilerek seçilen ayarlar bir akış üzerinden kaydedilip okunabilmektedir.

Bir kaç model ile oyun motorunun işlevsel sınamalarından bir kare.




Karşılaştığımız başlıca teknik sorun kurduğumuz yapıyı sürekli yeniden değiştirme gereği duymamızdır. Daha önce tecrübe edinmediğimiz için modern yapıları inceledikçe yeni yöntemler keşfedip, kendi projemizdeki eski yapıları atma ihtiyacı duyuyoruz. Sosyal açıdan en büyük sorun ekip çalışmasının getirdiği zorluklar olarak tarif edebilirim.


Geleceğe Dair Planlar
Projeye ileriki aşamalarda yapmak istediğim eklemeleri şu şekilde sıralayabilirim:

- OpenGL desteği ile platform bağımsız tasarıma geçerek MacOS X, Linux, BSD, iPhone OS, PlayStation 3 gibi sistemlerde çalışmasını sağlamak.
- Çok kanallı programlama desteği sağlamak
- Shader desteği
- Gerçek zamanlı 3D model ve sahne düzenleme aracı
vs..


Bir sonraki yazımda da projemizdeki yenilikleri ve gelişmeleri sizlerle paylaşmaya devam edeceğim. Esen kalın efendim...

16 Mart 2011 Çarşamba

Güvenlik ve Güvenilirlik Kavramları

Bilişim dünyasında genellikle karıştırılarak birbiri yerine kullanılan bu iki terimden kısaca bahsetmek istiyorum.

- Güvenlik (Security) Nedir?
Bilişimde güvenlik terimi, bir sistemin ihtiva ettiği bilginin veyahut sahip olduğu yetkilerin sistemin izni olmadan yetkisiz bir kişi ya da sistem tarafından kullanılmasının önüne geçilmesi olarak tarif edilebilir. Bunu sağlayamayan programlarda "Güvenlik açığı vardır" denir.

- Güvenilirlik (Reliability) Nedir?
Bilişimde güvenilirlik terimi, bir sistemin sürekliğinin ve kararlılığının her koşulda ve zamanda mutlak suretle sağlanmasıdır. Bunu sağlayamayan programlarda "güvenilirlik sorunu vardır" denir.

Bu terimleri açıklamak istememin sebebi birbirine çok karıştırılıyor olmasıdır. Bir sistemi geliştirmek sistemli çalıştırmayı gerektirir, sistemli çalışmanın şartı da bireylerin birbirini doğru ve tam olarak anlamasından geçer. En basit örnek olarak bu iki terimi birbirine karıştıran bir programcı, "programda güvenlik sorunu var!" dediği zaman gizli bilgi ihlali olasılığından mı bahsediyor yoksa (beklenmeyen) ölümcül bir hata ile programın sonlanması ihtimali ile istikrar sorunundan mı bahsediyor doğrudan anlamak malesef mümkün değildir.

Son olarak, güvenliği sağlamak için güvenilirliği sağlamak şarttır. Güvenilir olmayan (hata verme olasılığı olan) bir sistemin güvenlikli olması beklenemez. Güvenliğin temel şartı güvenilirliktir. Fakat tam tersini söylemek her zaman doğru değildir. Güvenliği sağlanmamış bir program yıllar boyunca istikrarlı bir şekilde (beklenmeyen) ölümcül bir hata vermeden çalışabilir. Çünkü güvenlik ihlalleri kişi ya da sistemler tarafından bilinçli olarak yapılan ve doğal olmayan eylemlerdir.

Güvenirlir sistemler geliştirip güvenliğini sağlamanız dileğiyle...

19 Şubat 2011 Cumartesi

Şifrelemenin Kanunları - Bölüm 1.2

1.3 Kümeler

Bir küme, herhangi iki elemandan eşsiz bir üçüncü elemanı türetmek için bir ikili işleme (binary operation) sahip bir takım küme elemanlarıdır. Eğer küme işlemini # işareti ile gösterecek olursak, yukarıda söylenen herhangi bir küme elemanı olan a ve b için, a#b tanımlıdır ve hatta bir kümenin elemanıdır. Ayrıca kümeler çağrışımsaldır yani a, b ve c kümenin herhangi birer elemanı olsun, a#(b#c) = (a#b)#c'dir. Kümenin herhangi bir elemanı olan a için bir adet birim (etkisiz) eleman (e) olmalıdır, a#e = e#a = a. Son olarak herhangi bir eleman olan a'nın bir tane tersi (a') olmalıdır, a#a' = a'#a = e.

Kümenin tüm elemanları olabilen a ve b için eğer a#b = b#a ise bu küme değişme özelliğine sahiptir. Aksi halde değişme özelliği yoktur. Şu noktaya dikkat çekelim, değişme özelliğine sahip olmayan bir küme için bazı durumlarda a#b = b#a eşitliği doğru olabilir - örneğin a ya da b birim eleman olursa.

Sınırlı sayıda eleman içeren kümeye sınırlı küme, aski durumda sınırsızdır denir.

Örnekler:
1. Tam sayılar (tüm sayılar, 0 ve negatif sayılar) adi toplama işlemiyle bir küme oluştursunlar. Birim eleman 0 olur ve a'nın tersi -a olur. Bu sınırsız ve değişebilen bir kümedir.
2. Pozitif rasyonel sayılar (tüm pozitif tam sayılar da dahil olmak üzere tüm pozitif kesirler) adi çarpma işlem olarak bir küme oluştursun. Birim eleman 1 sayısı ve r'nin tersi 1/r = r^-1. Bu da diğer bir sınırsız değişebilen kümedir.
3. Tam sayıların n ile modu, n > 0 herhangi bir tam sayı olmak üzere bir küme oluştursun. Bu küme genelde Z(n) (Çevirmenin yorumu: asal belgede n, Z'nin sağ altında gösterilmektedir, bu çeviride parantez içerisinde gösterilecektir.) şeklinde gösterilir. Elemanlar 0, 1, 2, ..., n-1 ve işlem toplamanın n ile bölümünden kalan şeklindedir:



Birim eleman 0 sayısıdır ve a'nın tersi n-a'dır (tersi kendisi olan 0 sayısı hariç).

4. Değişemeyen kümeye örnek olarak, 2'ye 2 tekil olmayan gerçek (reel) sayılardan (ya da rasyonel sayılardan) oluşan matrisler düşünelim, işlem matris çarpmasıdır:



Buradaki a, b, c ve d gerçek sayılardır (ya da rasyonel) ve ad-bc sıfır değildir. İşlem matris çarpmasıdır. Yukarıdaki matrisin tersi



ve birim elemanı



Bu bir sınırsız değişemeyen bir kümedir.

5. Ondalıklı sayıların bir bölümü sınırlı değişemez kümelere ilginç ve faydalı bir örnek olarak verilebilir: on elemanlı dihedral (Çevirmenin yorumu: kelime aslı gibidir, kısaca uçak kanatlarının yatay düzlemle yaptığı açıya denir, detaylı bilgi için bkz: [1] http://en.wikipedia.org/wiki/Dihedral_group, [2] http://tr.wikipedia.org/wiki/Dihedral) kümesi.

KANUN KÜME-1: Şifrecilerin gözde kümesi, tam sayıları n ile mod alandır, Z(n).

n = 10'a özel olarak, Z(10)'da toplama işlemi (x+y) mod 10 şeklinde tanımlanabilir, bu, 10'a böl ve kalanını al demektir. Tablo 1.3 nasıl olduğunu göstermektedir ve ayrıca 10 sayısı ile mod alınan tam sayıların toplama tablosu olarak da kullanılabilir.

1.4 Alanlar

Bir alan içerisinde bir çok yapıyı bulunduran bir nesnedir ki bu bölüm yalnızca bir özet niteliğindedir. Bir alan iki işleme sahiptir, bunları + ve * (adi toplama ve çarpma olmak zorunda olmamasına rağmen) olarak adlandıralım. +'yı kullanırsak, alanın tüm elemanları değişebilen bir küme kuracaktır. Bu kümenin birim elemanını 0 olarak ve a'nın tersini -a olarak gösterelim. *'yı kullanırsak, 0 hariç alanın tüm elemanları, birim elemanı 1 ile ve a'nın tersi a^-1 ile gösterilen başka bir değişebilen küme oluşturacaktır. (0 elemanının * işlemi altında tersi yoktur.) Ayrıca bir de dağılma özelliğine sahiptir, + ya da * ile bağlandığında: a*(b+c) = (a*b) + (a*c), a,b ve c tüm elemanlar için. Son olarak birşeyi hariç tutmalıyız, sıfıra bölünenler, bunlar sıfır üreten sıfır olamayan elemanlardır. Bu aşağıdaki fesih neteliğine eşdeğerdir:
eğer c sıfır değilse ve a*c = b*c ise a = b 'dir.

Örnekler:

1. Rasyonel sayıları (kesirler) Q olarak düşünelim, ya da gerçek sayıları R olarak, ya da karmaşık sayıları C olarak, bunlarda adi toplama ve çarpma işlemi kullanmak ( son durumda karmaşık sayılar dahil edilmiştir). Bunların tümü sınırsız alanlardır.

2. Tam sayıların p ile mod alındığını düşünelim, Z(p) olarak gösterilsin, p bir asal sayı olsun (2, 3, 5, 7, 11, 13, 17, 19, 23, 29, ...). Bunu + kullanan bir küme olarak görelim (adi toplamanın ardından p'ye bölümünden kalandır). 0 olan elemanlar * altıda bulunmadığı bir küme oluşacaktır (p'ye bölümünden kalanın ardıdan yapılan adi çarpmadır). Burada birim eleman belirgin olarak 1'dir, ama sıfır olmayan a elemanının tersi açık değildir. Java'da tersi, (x*a)%p==1 olan bir x elemanı olmalıdır. Sayılar teorisinde genişletilmiş Öklit Algotirması olarak bilinen bir algoritma kullanılarak eşsiz bir x elemanı bulmak her zaman mümkündür. Bir sonraki bölümün bu başlığında, özet olarak: p'nin asal sayı olması ve a'nın sıfırdan farklı olması sebebiyle, p ve a'nın en büyük ortak bölenleri 1'dir. Şimdi genişletilmiş Öklit algoritması, x*a + y*p = 1 ya da x*a = 1 - y*p sağlayan x ve y sıradan tam sayılarını verecektir, ve bu bize eğer x*a'yı p'ye bölersen 1 kalanını alırsın demektedir, böylece bu x, a'nın tersi olur. ( Bir tam sayı olarak, x negatif olabilir, ve bu durumda Z(p)'nin bir elemanını alabilmesi için ona p eklenmelidir.)

KANUN ALAN-1: Şifrecilerin gözde alanı p'nin asal olduğu Z(p) ile gösterilen tamsayıların p ile modunu alandır.

Yukarıdaki alan p elemanlı olarak tektir. Diğer bir değişle, alan elemanlarının yeniden adlandırılmasıyla eşsizdir, yani alanın elemanları her zaman için bir başka işaret takımıyla gösterilebilir, fakat temel olarak aynıdır.

Ayrıca GF(p^n) şeklinde gösterilen, p^n'in elemanlarından herhangi birisi için n>1 geçerli olan eşsiz sınırlı bir alan daha vardır. Bilhassa şifrelemede p=2 özel durumu çok işe yarar. Bu durumda, n>1 olamak üzere 2^n adet eleman vardır. 2^8 = 256 durumu, örnek olarak, yeni Birleşmiş Milletler Gelişmiş Şifreleme Ölçünü'nünde (U.S. Advanced Encryption Standart - AES) kullanılmıştır. Bunu anlatmak Z(p) alanını anlatmaktan daha zordur. AES için çarma işlemi hakkındaki bölüm bu alanı daha detaylı anlatacaktır, fakat burada bazı özelliklerini özetlemek gerekirse: 256 tane elemanı vardır, 8-bitlik olası tüm katarları ifade eder. Bu alanda toplama bitsel özel veya (XOR) ya da yine bitsel olarak toplamanın mod 2 işlemiyle aynıdır. Sıfır elemanı 00000000'dır, ve birim eleman 00000001'dır. Şimdiye kadar iyi gittik, fakat çarma yapmak daha bir sorunlu: bir eleman, Z(p) alanında katsayılar içeren 7. dereceden bir polinomu ifade etmelidir (bir 0 ya da 1)ve bu polinomların özel bir çarpma hali kullanımalıdır. Ayrıntılar AES üzerine olan sonraki bölümde gelecektir.

KANUN ALAN-2: Şifrecilerin diğer bir gözde alanı GF(2^n)'dır.

13 Ocak 2011 Perşembe

Şifrelemenin Kanunları - Bölüm 1

Şifrecilerin Gözdeleri

1.1 Özel Veya (XOR)

Özel veya olarak bilinen bu fonksiyon aynı zamanda xor olarak ya da bir daire içerisindeki artı işareti (+) olarak da gösterilebilir. a (+) b demek a ya da b fakat ikisi birden değil demektir. Matematikte normal veya (or) demek biri ya da diğeri veyahut ikisi birden demektir. Özel veya işlevi (function) C/C++/Java dillerinde mevcut olup şapka karakteri ^ ile ifade edilmektedir. (Dikkatli olun: şapka karakteri sık sık üstel ifadeler için kullanılır, fakat Java, C ve C++ dillerinde herhangi bir üstel operatör yoktur.) Java'da ayrıca özel veya mantıksal değişkenlerde de (boolean) kullanılabilmektedir.

KANUN XOR-1: Şifrecilerin gözde işlevi özel veyadır.

Özel veya şifrelemede devamlı olarak kullanılır. Bu işlev tek-seferlik şifrelemede, akış şifrelemesinde ve Gelişmiş Şifreleme Ölçünü (AES) ve bir çok yerde kullanılmaktadır.

Hatırlayalım, mantıksal sabit doğru (true) genellikle 1 olarak yanlış (false) ise 0 olarak yazılır. Özel veya toplama işlemi sonucunda mod 2 işlemini yapmakla aynıdır, yani sıradan bir toplama işlemini yaptıktan sonra sonucu 2 sayısına bölüp kalanı alma işlemidir. 0 ve 1 bit değerleri için aşağıdaki tabloda özel veya işlemi sonuçları verilmiştir.



Özel veya işlevinin bir çok ilginç özelliği vardır, a,b ve c bit değerlerini ya da dizilerini tutsun:



Yeni başlayan programcılar iki değişkenin değerini değiş tokuş yapmak için üçüncü bir geçici değişkene atama yaparak öğrenirler:

temp = a;
a = b;
b = temp;

Aynı sonucu xor işlevini kullanarak ek olarak üçüncü bir geçici alan ayırmadan gerçekleştirilebilir. a ve b değerlerinin bit dizileri olsun.

a = a xor b;
b = a xor b;
a = a xor b;


Çevirmenin yorumu:




Özel veya işlevinin şifrelemede kullanımına örnek verecek olursak, xor işlevi sözde rastgele bit akışı olan ri ile şifrelenecek mesajımızın bitlerini içeren mi akışını alsın ve şifrelenmiş halinin ci akışı olarak çıkartsın ci = ri (+) mi. Şifrelenmiş veriyi çözümlemek için aynı sözde rastsal bit akışını (yani ri) ci'ye vererek mi akışını elde ederiz. ri (+) ci = ri (+) ri (+) mi = 0 (+) mi = mi, Şekil 1.1 (Figure 1.1) bu işlem gösterilmiştir.

KANUN XOR-2: Şifreciler özel veya işlevini çok sever çünkü ivedi bir şifreleme mekanizması sağlar.


1.2 Logaritma

Tanım olarak, y = logb(x) demek b^y = x (b üssü y eşittir x). Bir başka değişle: "y, b tabanında x'in logaritmasıdır" ya da "y, x'in taban b'deki logaritmasıdır" denir. Aynı zamanda logb(x) (yani y) ifadesinin b üssü şeklinde yazılarak x değeri elde edilebilir, b^(logb(x)) = x. Daha matematiksel bir ifadeyle logaritma, üssel işlevin (exponential) tersi bir işlevdir.

KANUN LOG-1: Şifrecilerin gözde logaritma işlevi 2 tabanında logaritmadır.

Şifrelemede logaritma 2 tabanındanın kullanılmasının bir sebebi de (çoğunlukla bilgisayar biliminde) bu alanda ikili (binary) sayı düzenine yoğunlaşılmış olmasıdır.
Öyle ise y = log2(x) demek 2^y=x demekle aynı ve logaritma 2 tabanında x'in 2 üssü şeklinde yazımından x'i elde ederiz. Şekillerle ifade edersek: eğer y = log2(x) ise o zaman x = 2^y = 2^(log2(x)). Öyle ise 2^10 = 1024 demek log2(1024)=10 demekle aynı. Fark ettiyseniz tüm y değerleri için 2^y>0 ve tersten gidersek log2(x) x<=0 olduğunda tanımsızdır.

Logaritmayı içeren bir kaç formül:

log2(ab) = log2(a) + log2(b), her a,b > 0
log2(a/b) = log2(a) - log2(b), her a,b > 0
log2(1/a) = log2(a^(-1)) = - log2(a), her a > 0
log2(a^r) = r log2(a), her a > 0, r
log2(a+b) = (Ups! Bunun için basit bir formül yok.)
Tablo 1.2 log2 için bir kaç örnek vermektedir.

Bazı hesap makineleri, Java gibi diller de dahil, doğrudan log2 işlevini desteklemiyorlar. Java 10 tabanından logaritmayı da desteklemiyor yalnızca e tabanında logaritmayı destekliyor ki buna "doğal" logaritma diyoruz. Logaritma 2 tabanında a ile logaritma e tabanında a çarpımının sonucu bir sabit olduğu için eğer "sihirli" sabiti biliyorsanuz bu sonucu hesaplamak çok kolay olacaktır. Formül şöyle:

log2(x) = loge(x) / loge(2) (matematik)
= Math.log(x)/Math.log(2.0); (Java)

Sihirli sabit: loge(2) = 0.69314 71805 59945 30941 72321, yada 1/loge(2) = 1.44269 50408 88963 40735 99246. (Benzer şekilde, log2(x) = log10(x)/log10(2) ve log10(2) = 0.30102999566398114.)



Yukarıdaki formülün ispatı şöyle:

2^y = x, ya da y = log2(x) -> her iki tarafında e tabanında logaritmasını alalım
loge(2^y) = loge(x)
y loge(2) = loge(x)
y = loge(x) / loge(2)
log2(x) = loge(x) / loge(2)

KANUN LOG-2: Bir tam sayının 2 tabanında logaritmasını almak, bize o sayıyı ikili düzende (binary) kaç tane bit ile ifade edebileceğimizi söyler.

Buna göre log2(10000) = 13.28771238, yani iki düzende bu sayıyı ifade etmek için 14 tane bit gereklidir. (Gerçektende, 10000(10) = 10011100010000(2).) İkinin tam katlarının özel bir durumu vardır: log2(1024) = 10 fakat bu sayıyı ikili düzende ifade etmek için 11 adet bit gerekmektedir. 10000000000(2).

Benzer şekilde, log10(x) bize onluk sistemde bu sayıyı ifade etmek için kaç tane raka kullanmamız gerektiğini söyleyecektir.

12 Ocak 2011 Çarşamba

The Laws of Cryptography

Hi, this is my first translation project in cryptography. I am very glad to say that I started to translate the masterpiece of Mr. Neal R. Wagner (http://www.cs.utsa.edu/~wagner/) who is Retired as Assoc. Prof. from UTSA ( The University of Texas at San Antonio - http://www.cs.utsa.edu/) which is called The Laws of Cryptography (http://www.cs.utsa.edu/~wagner/lawsbookcolor/laws.pdf) into Turkish. I asked him for the permission to translate his book into Turkish by a personal email conversation. It is an honor for me to do this important job. My purpose is making people who live in Turkey as an computer engineer paying attention to cryptography a little. Although, he emphasized on importance of English in cryptograpy, I would like to translate a part of the book. Because somebody has to trigger it. I hope I will succeed.

Thank you again Mr. Neal R. Wagner.




Merhaba, bu benim şifreleme alanındaki ilk çeviri projem. Şunu söylemekten çok mutluyum ki Texas Üniversitesinde görev almış emekli Profesör Sayın Neal R. Wagner'ın şaheseri diyebileceğimiz Şifrelemenin Kanunları isimli kitabını Türkçe'ye çevirmeye başladım. Kendisinden kişisel bir eposta görüşmesiyle kitabının Türkçe'ye çevirilme iznini istedim. Bu çeviriyi gerçekleştirmek benim için bir onurdur. Amacım Türkiye'de yaşayan bilgisayar mühendisi arkadaşlarımın ilgilisini biraz olsun şifreleme alanına çekebilmektir. Kendisinin bana şifrelemede İngizce'nin önemini vurgulamasına rağmen, kitabının bir kısmını çevirmek istiyorum. Çünkü birileri bu işi başlatmalı. Umarım başarabilirim.

Sayın Neal R. Wagner'a tekrar teşekkür ederim.




Not: Çevirileri ilerleme kaydettikçe bölüm bölüm girdi yapacağım. Kendilerinin de izniyle bazı kısımlarda kendi yorum ve eklemelerim olabilir.