Kategori arşivi: Veri Yapıları ve Algoritmalar

Kuyruk Teorisi ve Sistemleri

Kuyruk teorisi ve sistemlerini anlamak için öncelikle kuyruk (queue) ne demek ona bakmalıyız. Kuyruk hizmet kapasitesinin aşılması durumunda ortaya çıkan bekleme durumudur. Süper market kuyruğu gerçek hayattan verilebilecek en güzel örneklerden biridir. Banka sıramatiklerinden sıra alarak sırasını bekleyen müşteriler de güzel bir örnek olabilir. Bilgisayar sistemlerinden örnek olarak da yazıcı kuyruğu verilebilir. Bilindiği üzere ortak bir yazıcıya çıktı gönderen kişilerden çıktıyı ilk alacak olan ilk gönderen kişidir. Verilen örneklerdeki esas olan konu herkesin sırasını beklemesidir. İdeal olan ve istenilen beklemenin olmamasıdır, fakat bu mümkün görünmemektedir. Bu durumda yapılacak olan şey bu süreyi minimize etmektir. Çünkü kuyruğa farklı bir açıdan bakıldığında kuyruğun başlama sebebi hizmet kapasitesinin aşılması durumunda ortaya çıkmaktadır.

Şu ana kadar verdiğimiz örneklerin tarzı ilk giren ilk çıkar (first in first out) mantığı ile çalışan sistemlerdi. Bunun dışında restoran örneğine bakacak olursak, yoğun çalışan bir restoranda her zaman ilk gelen ilk çıkmadığı gibi bekleme süresi de değişebilmektedir. Ayrıca yemek tercihine göre servis süresi de değişken olacaktır. Yani burada durum biraz daha karışıktır. Bu durumda restoran sahibi hizmet maliyeti ve müşteri bekleme süresinin az, kalitenin ise fazla olmasını amaçlar. Müşteri için ise zaman ve hizmet kalitesi önemlidir. Bu durumda müşteri ve işletme sahibinin isteklerini dengeleyen bir yapının modeli kuyruk analizi ile çıkarılabilir. Kuyruk teorisi bekleyen sıra ya da kuyrukların matematiksel analizinin yapılarak bekleme süresini minimize edilmesine çalışılmasıdır. Kuyruk ya da sıralı sistemlerde temel elemanlar müşteri ve hizmet verendir.

Kuyruk teorisinin temel kavramları şunlardır;

  • Kuyruk: Bekleyen müşteri sayısı
  • Servis Kanalı: Hizmet sunulan sistem
  • Geliş Debisi (λ): Birim zamanda kuyruğa gelen müşteri sayısı
  • Servis Debisi (μ): Birim zamanda hizmet verilen müşteri sayısı
  • Kuyruk Disiplini: Müşterilerin seçilme düzeni. (Yazıcı ya da süper market kuyruğunda ilk gelen ilk çıkar mantığı olduğu gibi farklı sistemlerde ilk gelen son çıkar ya da rasgele seçilim gibi farklı disiplinler kullanılabilir.)
  • Servis Olanaklarının Yapısı: Tek kanallı ya da çok kanallı bir yapı olabilir.

Tek kuyruk – tek servis düzeni, tek kuyruk – seri şekilde birden fazla servis, tek kuyruk – paralel şekilde servis, çoklu kuyruk – paralel şekilde çoklu servisi sistemleri kullanılabilecek olan kuyruk sistemlerindendir.

Daha önce de bahsedildiği üzere farklı kuyruk yapıları mevcuttur. Bunlardan M/M/1 Servis zamanının üstel olasılık dağılımına sahip olduğu, FIFO yapısı kullanılan, kuyruk kapasitesi sonsuz, matematiksel çözümü olan bir modeldir. Müşterilerin geliş sırası net olarak bilinemediği için buralarda poisson ve üstel olasılık dağılımları kullanılabilir. Modelleme için kullanılan değişkenlere ve bunların denklemlerine bakalım;

  • Sistemin meşguliyet faktörü: ρ
  • Verilen bir zamanda sistemde n sayıda müşteri bulunma olasılığı: Pn = (1 – ρ) ρn
  • Hizmet verenin boş kalma oranı: Po = 1- ρ
  • Sistemde n veya daha fazla birimin bulunma olasılığı: ρn
  • Sistemdeki ortalama müşteri sayısı: L = ρ / (1- ρ)
  • Müşterinin harcadığı süre: W = 1 / ( μ- λ )
  • Ortalama Kuyruk Uzunluğu: Lq = λ2 / μ ( μ- λ )
  • Müşterilerin kuyrukta geçirdiği ortalama süre: Wq = ρ / ( μ- λ ) (FIFO)

Farklı kuyruk yapıları gelişlerin dağılımının, hizmet süresinin dağılımının, kuyruk boyutunun, müşteri sayısının vb. kavramların farklı kombinasyonlarıyla hazırlanmıştır. Buna göre M/M/1’in dışında M/M/k, M/M/3, M/G/1 modelleri bulunmaktadır.

Farklı kuyruk yapıları gelişlerin dağılımının, hizmet süresinin dağılımının, kuyruk boyutunun, müşteri sayısının vb. kavramların farklı kombinasyonlarıyla hazırlanmıştır. Buna göre M/M/1’in dışında M/M/k, M/M/3, M/G/1 modelleri bulunmaktadır.

Kaynaklar

  1. http://tr.wikipedia.org
  2. http://www.ozyazilim.com
  3. gazi.edu.tr
  4. http://acikders.ankara.edu.tr/
  5. baskent.edu.tr
  6. trakya.edu.tr https://www.google.com.tr/url?sa=t&rct=j&q=&esrc=s&source=web&cd=2&ved=0CDEQFjAB&url=http%3A%2F%2Fozlemaydin.trakya.edu.tr%2FMod_2012_5.pptx&ei=hFOnUeraMci0PPaQgbgF&usg=AFQjCNENwsCS7NFd-TqaBi63LYljMP6b1g&sig2=PtYiOayQjBJAS0j9J0A-Fw&bvm=bv.47244034,d.ZWU&cad=rja

Fikstür Oluşturma Algoritması – Fikstür Hazırlama (tek ve çift sayıda takım ile)

Lisans döneminde algoritma ödevlerimizden bir tanesi girilen takım sayısına göre fikstür oluşturan bir programdı. Aklıma gelince paylaşayım istedim.

ÇİFT SAYIDA TAKIM İLE FİKSTÜR OLUŞTURMA

Fikstür algoritmalarında mantık; n adet takım varsa, ligde n-1 adet hafta müsabaka olmalıdır. (Rövanşlar hesaba katılırsa hafta sayısı 2 x (n-1) olacaktır.) İlk haftanın fikstürü çekilir, diğer haftalar ise ilk hafta referans alınarak belirlenir. Bizim kullandığımız algoritmayı örnekle açıklayayım. Örneğin 6 takımlı bir lig oluşturalım. Bu takımları 1, 2, 3, 4, 5, 6 şeklinde ifade edelim. İlk hafta maçları şu şekilde olsun;

image2

Birinci haftayı oluşturduktan sonra ilk takımı sabit tutarak diğer takımları saat yönünün tersinde ilerletelim. Bu durumda ikinci hafta aşağıdaki şekilde olacaktır;

image3

İlk takımı sabit tutup diğer haftaları bu şekilde hesaplamaya devam ettiğimiz taktirde 6 takımlı ligin 5 hafta sürecek müsabakalarının fikstürü aşağıdaki gibi olacaktır.

image

Fikstür bu şekilde belirlendikten sonra ev – deplasman ayarları da yapılabilir.

TEK SAYIDA TAKIM İLE FİKSTÜR OLUŞTURMA

Farklı bir durum da tek sayıda takım olması durumudur. Bu durumda ilk hafta oluşturulurken bir takımın karşısına X yazılabilir. Böylelikle fikstür çekimi sonucunda karşısına X gelen takım o haftayı bay geçecektir.

Her iki durum için de fikstür ayarlaması yukarıdaki gibi yapıldıktan sonra rasgele her takım için bir sayı çekilir. Örneğin Galatasaray geldi kura çekti ve 2 çıktı, Fenerbahçe’ye 3 çıktı vs. Bu durumda her sayıya karşılık gelen takım belirlenmiş olur.

ALGORİTMA

Bazı talepler üzerine algoritmanın kabakoduyla alakalı biraz daha bilgi vermek istedim.

N adet takım olsun. Öncelikle takımları bir diziye attım. N-1 hafta maç olmalı (deplasmanları saymazsak, sayacaksak eğer fikstürün tam tersi olacak zaten).
Örnekte olduğu gibi 6 tane takım olsun (mantığını kavrayınca istenirse 500 olsun sorun yok). Tüm takımları bir diziye atalım. Daha sonra random olarak bir indis seçip sabit tutacağımız takımı belirleyelim ve o indisi diziden silelim. Bu durumda bir takım seçtik ve 5 adet takım dizide kaldı. Takım isimleri de 1, 2, 3, 4, 5 ve 6 olsun. Biz 1’i sabit seçmiş olalım. Bu durumda;
sabit takım – 1
takım_dizisi = [2, 3, 5, 6, 4]
sabit takım ile dizinin ilk elemanı eşleşecek, kalan takımlar ise dışarıdan içeriye doğru eşleşecekler (bu örnek için dizinin ikinci elemanı (3) ile beşinci (6), üçüncü elemanı (4) ile dördüncü elemanı (5)). Yani;
1-2, 3-4, 5-6
Sonra dizideki elemanları bir kaydırıyoruz. Yeni dizimiz şöyle olacak;
takım_dizisi = [4, 2, 3, 5, 6]
kural yine aynı sabit ile dizinin ilk elemanı eşleşecek, kalan takımlar ise dışarıdan içeriye doğru eşleşecekler. Yani;
1-4, 2-6, 3,5
Sonra dizideki elemanları bir kaydırıyoruz. Yeni dizimiş şöyle olacak;
takım_dizisi = [6, 4, 2, 3, 5]
kural yine aynı sabit ile dizinin ilk elemanı eşleşecek, kalan takımlar ise dışarıdan içeriye doğru eşleşecekler. Yani;
1-6, 4-5, 2-3
Sonra dizideki elemanları bir kaydırıyoruz. Yeni dizimiş şöyle olacak;
takım_dizisi = [5, 6, 4, 2, 3]
kural yine aynı sabit ile dizinin ilk elemanı eşleşecek, kalan takımlar ise dışarıdan içeriye doğru eşleşecekler. Yani;
1-5, 6-3, 4-2
Sonra dizideki elemanları bir kaydırıyoruz. Yeni dizimiş şöyle olacak;
takım_dizisi = [3, 5, 6, 4, 2]
kural yine aynı sabit ile dizinin ilk elemanı eşleşecek, kalan takımlar ise dışarıdan içeriye doğru eşleşecekler. Yani;
1-3, 5-2, 6-4
Böylelikle 6 takım olduğu için 5 haftalık fikstür tamamlanmış oluyor.
Kısaca algoritma şu;
n tane takım için takımların hepsini diziye at. Bir tane random takım belirle ve sabit takım olarak seç. Bu takımı diziden sil.
indis = random (1,n)
sabit_takim = dizi(indis)
dizi.pop(indis)
 
for i = 1 to (n-1)
          i. hafta fikstur = 
          1. maç = sabit_takim:dizi(0)
          for j=1 to (n-2)/2:
                 j. maç = dizi(j+1):dizi(n-j)

 


Fikstür çekme ile ilgili sorunuz olursa bu yazıya yorum yazarak sorabilir veya mail atabilirsiniz. Bu yazı işinize yaramışsa veya hoşunuza gitmişse sayfadaki reklamlara tıklayarak teşekkür edebilirsiniz. 🙂

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.