Anasayfa » Arşiv

Bilgisayar Bilimleri Kategorisindeki Yazılar

Algoritmalar »

[16 Ara 2011 | Yorum Yok | 3.050 kez okundu]
1 Star2 Stars3 Stars4 Stars5 Stars (1 oy,5 üzerinden : 5,00 )
Loading...
Kırmızı – Siyah Ağaç Yapıları ( Red – Black Trees) C Kodu

Merhaba arkadaşlar, bu yazımda daha önceden bahsettiğim red black tree lerin c kaynak kodlarını paylaşacağım.  Eğer red black tree ler ve algoritması hakkında bilgi sahibi olmak istiyorsanız önceki yazımı buradan okuyabilirsiniz.
Red black tree lerin c kaynak kodu şu şekildedir. Kodumuzda binary insert, binary fix up, left rotate, right rotate, inorder print gibi fonksiyonlar bulunmaktadır.
Kodumuzu çalıştırdığımızda iki seçenek sunmaktadır. İster belirlediğimiz sayıları kendimiz girebiliriz, istersek belli bir sayıyı otomatik yerleştirmesini söyleyebiliriz.

?View Code C#include <stdio.h>
#include <math.h>
#include <stdlib.h>
#include <time.h>
struct node
{
struct node *parent;
struct node *left;
struct node *right;
int value;
bool isRed;
};
void yazdir (int * A, int …

Devamını oku...

Algoritmalar »

[14 Ara 2011 | Yorum Yok | 4.449 kez okundu]
1 Star2 Stars3 Stars4 Stars5 Stars (Henüz hiç oy kullanılmadı. İlk oyu siz verin.)
Loading...
Dinamik Programlama (Dynamic Programming) – En Kısa Yol Problemi

Arkadaşlar bu yazımda, matematik ve bilgisayar bilimleri alanlarında karmaşık problemleri çözmek için kullanılan bir metoddan bahsedeceğim. Ardından metodla alakalı bir problem olan en kısa yol probleminin çözümünü  ve ilgili c kodlarını yazacağım.
Dinamik programlama, karmaşık bir problemi daha alt problemlere bölerek çözmeye çalışan yöntemdir. Bu işlem sırasında elde edilen veriler bir yere kaydedilerek. Daha sonra ihtiyaç olduğunda tekrar hesaplamak yerine buradan kullanılır ve zamandan kazanç elde edilir.
Bir problemi dinamik programlama yöntemiyle çözebilmek için bazı şartlar vardır. Şöyle ki:

En iyi çözümün alt çözümleri de en iyi olmak zorundadır.
Var olan karmaşık problemi daha …

Devamını oku...

Algoritmalar, Veri Yapıları »

[2 Ara 2011 | 7 Yorum | 7.253 kez okundu]
1 Star2 Stars3 Stars4 Stars5 Stars (1 oy,5 üzerinden : 5,00 )
Loading...
Kırmızı – Siyah Ağaç Yapıları ( Red – Black Trees)

Bu yazımda sizlere red black tree lerden yani kırmızı siyah diye adlandırılan ağaç yapılarından bahsedeceğim. Red Black Tree ler aslında binary search tree yapısıdır. Binary search treelerden tek farkı, extradan her nodun rengini tutan yapının olmasıdır. Bu renkler isimden de anlaşılacağı gibi kırmızı veya siyahtır.
Red black tree ler dengeli ağaçlardır. Bu yüzden en kötü zamanda bile n elemanlı bir ağaca ekleme, silme arama gibi işlemler O(logn) zamanda yapılabilir.
Her nodun bildiğimiz gibi değeri, sağ çocuğu, sol çocuğu, ebeveyni (parent) ve rengi vardır. Ayrıca red black treelerde yapraklar nill dir.
Red Black Tree lerin …

Devamını oku...

Dosya Organizasyonu, Veri Yapıları »

[4 Haz 2011 | 11 Yorum | 13.144 kez okundu]
1 Star2 Stars3 Stars4 Stars5 Stars (6 oy,5 üzerinden : 3,17 )
Loading...
B Tree (B Ağacı) Insertion Deletion Searching

B tree (B ağacı) binary (ikili) sıralama ağaçlarının genel halidir. Genel olarak arama işleminde daha hızlı sonuç vermesine karşın ekleme ve silme işlemlerinde daha yavaştır. Kayıtların sayısı capacity order la orantılıdır. Capacity order ve diğer sınırlamalar belli bir kurala bağlıdır. “Capacity order = d” dersek;

 d<=keys<=2d  (anahtarlar d ile 2d arasında olmak zorundadır.Yanlız root 1 ile 2d arasında olabilir.)d+1<=pointers<=2d+1 (işaretçiler d+1 ile 2d+1 arasındadır. Yanlız rootun pointerları 2 ile 2d+1 arasında olabilir.)
Bütün leafler (yapraklar) aynı seviyededir.

eleman sayısı 2d yi geçtiği anda düğümü parçalamak gerekir. Aynı şekilde root ve leaf ler hariç …

Devamını oku...

Dosya Organizasyonu »

[24 Nis 2011 | Yorum Yok | 2.449 kez okundu]
1 Star2 Stars3 Stars4 Stars5 Stars (1 oy,5 üzerinden : 5,00 )
Loading...
Computed Chaining (Hesaplanabilen Zincirler) – 2

Bu yazımda computed chaining için farklılıkları (variant), multiple chaining, ve çakışma çözümleme tekniklerinin karşılaştırılmasından bahsedeceğim. Yazımın birinci bölümünü okumadıysanız buradan okuyabilirsiniz.
 Örn: A kaydı için pseuodolink değeri 6 olsun ve fakat offset alanı için 2 bitlik bir alan ayrılsın. Bu durumda2 bit ile ifade edilebilecek en büyük sayı(11)2 olup A kaydının ardından gelen herhangi bir kayda erişmek için 1 probe yeterli olabilecek iken artık 2 probe’un kullanılması gerekecektir.
 
Farklılık (Variant)
 
Computed Chaining yaklaşımının performansınıarttırmak için bazıbir takım düzenlemeler yapılabilir.
Bir kaydıaradığımızda, bu işlemi olabildiğince kısa sürede ve etkili bir şekilde gerçekleştirmek isteriz. Aynıdurum günlük …

Devamını oku...

Dosya Organizasyonu »

[22 Nis 2011 | 2 Yorum | 2.975 kez okundu]
1 Star2 Stars3 Stars4 Stars5 Stars (2 oy,5 üzerinden : 5,00 )
Loading...
Computed Chaining (Hesaplanabilen Zincirler)

Computed Chaining (Hesaplanabilen Zincirler)
Arkadaşlar bu yazımda sizlere computed chaining yani hesaplanabilen zincirlerden bahsedeceğim. Çakışmaları genel olarak 2 farklı yaklaşımla çözüyoruz.
1-Link alanı kullanan çözümleme yaklaşımları (colaesced hashing)
2-Link alanı kullanmayan çözümleme yaklaşımları (progressive overflow, linear quotient, brient’s method ve binary tree)
Link kullanan çözümleme yaklaşımlarında performans genel olarak daha iyi olurken, link için extradan yere ihtiyacımız vardır. Tam tersi link kullanmayanlarda ise yere ihtiyaç azken performans daha düşüktür.
Her iki yaklaşımıda bir çatı altında toplayarak hem performans artışı, hem de yerden tasarruf sağlayabiliriz. Bu yeni yaklaşım computed chainingdir. Bu metodda gerçek link adreslerini kaydetmek …

Devamını oku...