‘kaynak kod’ etiketli içerik

Paylaşılamayan ortak kaynakları graf boyama yöntemi ile kaynağı kullanmak isteyen birimlere atayabiliriz. Bu çalışmada bir graf boyama örneği olan çakışmayan ders programı oluşturma gerçeklenmiştir. Aynı dersi alan öğrencilerin bulunduğu derslerin ders programında aynı zaman dilimine konması önlenmiş ve zaman mümkün olan en efektif biçimde kullanılmıştır.

Kaynak Kodlar:
Devamını Oku »

Bu çalışmada ilk giren ilk çıkar (FIFO) mantığı ile çalışan kuyruk veri yapısının basit bir uygulaması yer almaktadır. Bankada kuyruklar bulunmaktadır ve sıranın en önündekine her birim zamanda hizmet edilir. Hizmet süresi sıfır olan eleman sıradan çıkar. Yeni gelen müşteriler bekleme süresi en kısa olan kuyruğa eklenir.

Kaynak Kodlar:
Devamını Oku »

Shell sort algoritması insertion sort’un üzerine kurulu bir algoritmadır. Neredeyse sıralı olan dizileri sıralamada tercih edilir. Eleman sayısının yarısı kadar bir ofset değeri atanır ve elemanlar ofset aralıklarıyla insertion sort ile sıralanır ve bu işlem artan adım değerleri için yapılır. Daha sonra ofset yarılanır. Ofset değeri 1 den küçük olduğunda algoritma durur.

Kaynak Kodlar:
Devamını Oku »

Huffman algoritması ayrık durumları bulunma yüzdelerine göre değişken uzunlukta kodlama esasına dayanır. Gerçek hayattaki veriler çoğunlukla heterojen yapıdadır, ayrık durumların bulunma oranlarının birbirine yakın olmadığı durumlarda bu algoritma ile ortalama kod uzunluğu kısalarak yerden kazanç sağlanabilir.
Bu çalışmada yapılan Huffman algoritmasının basit bir simülasyonu olmakla birlikte herhangi bir sıkıştırma veya ağaç oluşturma söz konusu değildir. Verilen Huffman ağacına bakılarak girilen kod çözümlenmiştir.

Akış Diyagramı:

Verilen bir grafın minimum spanning tree’sinin bulunması en düşük maliyet ile bütün noktaların kapsanması açısından özellikle istasyonlar arasında ağ kurulumunda önem taşır. Bu çalışmada Kruskal’ın algoritmasını kullanarak basit bir minimum spanning tree implementasyonu yapılmıştır. Kaynaktaki graf n tane edge’den(u,v ve ağırlık değeri içeren bir struct) oluşan bir dizi şeklinde gösterilmiştir. MST bulma aşamasında hangi noktaların hangi alt graflara bağlandığını takip edebilmek için label[] adlı bir dizi kullanılmıştır. Derste de gördüğümüz bu algoritma ile graf üzerindeki bir MST’yi kolaylıkla bulabilmekteyiz.

Akış Diyagramı:

Bağlı liste yapısını kullandığımızda eleman aramak başarım açısından oldukça maliyetli oluyordu. N tane eleman olması durumunda teorik olarak N tane elemanı kontrol etmek durumunda kalıyorduk. Binary search tree yapısı bize arama yapma ve eleman eklemede oldukça hızlı bir çözüm sağlıyor. log2(N+1)-1 tane karşılaştırma işlemi ile sonuca ulaşabiliyoruz.

Bu çalışmada ağaç yapısını gerçeklerken elemanların indislerinin daha kolay gözlenebilmesi ve algoritma takibinin daha kolay olması için dizi gösterimi kullanıldı. Dengeli olmayan ağaçlarda dizi yapısını kullanmak hafıza alanı açısından maliyetli olabilir. Bu yüzden bu örnekler oluşturma aşamasında uygun sıra ile dengeli olarak yerleştirildi. Ancak kullandığımız yapı self-balancing olmadığından zaman içerisinde yapılacak modifikasyonların bu dengeyi bozması olasıdır. Ayrıca elemanları sıralamak da bize ek işlem yükü getiriyor.

Daha geniş kapsamlı uygulamalarda struct yapısı kullanılarak işaretçiler yardımıyla yapılacak bir gerçekleme hafıza alanını daha etkili kullanma adına daha mantıklı olacaktır. Eğer bizim için en önemli ölçüt arama hızı ise self balancing tree yapısı alternatif olarak düşünülebilir.

Akış Diyagramları:

Kaynak Kodlar:
Devamını Oku »

Bağlı listeler genelde dinamik yapılar kullanılarak gerçeklenir ancak bu örnekte kolay anlaşılır olması açısından dizi gösterimi kullanılmıştır.

Kaynak Kodlar:

Devamını Oku »

Videolardan alınan örneklerden oluşan görüntü dizilerinin birleştirilerek özet kare elde edilmesi basit bir işlem olmakla birlikte çeşitli ileri uygulamaların temeli olabilir. Fizikte bir eylemin özetlenmesi, örneğin belirli açılarla fırlatılan bir topun bu eğik atış hareketindeki yörüngesinin gözlenmesi görüntü dizisi birleştirme ile sağlanabilir. Daha sonraki aşamalarda görüntü dizilerinden hareket vektörleri çıkarılarak trafik yönünün ve akış hızının belirlenmesi gibi benzer uygulamalar yapılabilir. Ancak proje konumuz kapsamında olmadığı için bu uygulama ile ilgilenmedik.

Geliştirme Aşaması

Proje kapsamında bir videodan alınan 50 karenin C ile yazılmış program ile birleştirilmesi gerekiyordu. Görüntü dosyaları üzerinde işlem yapabilmek için öncelikle yardımcı c kütüphanelerini araştırdık. Sonrasında bitmap dosyasının yapısını incelediğimizde bu işlemi yardımcı görüntü işleme kütüphaneleri olmadan da kolaylıkla yapabileceğimizi gördük. Gri tonlamalı bir bitmap dosyası 14 byte dosya başlık bilgisi, 40 byte görüntü başlık bilgisi ve her biri bir byte olan piksel değerlerinden oluşuyordu. Görüntülerin tutulacağı 2 boyutlu dizinin boyutunu dinamik olarak belirlerken bu başlık bilgisinden faydalandık. Programda kullandığımız değişkenleri çoğunlukla unsigned char türünde tanımladık. Bir byte boyutunda olan bu değişken tipi, görüntü üzerinde byte bazında yapılan işlemlerde kolaylık sağladı.

Örneklenen karelerin belirgin olması için videoları saniyede yaklaşık 8 kare çekebilen bir fotoğraf makinesiyle timelapse yöntemini kullanarak çektik. Birleştirilmiş görüntüyü elde etmede kullanılan fotoğraf sayısı arttıkça görüntünün netliğini yitirdiğini gördük. Örneğin 50 kare ile çalıştığımızda en açık beyaz piksel olan 255 bile örnek sayısı olan 50 ye bölündüğünde 5 e düşüyor ve elde edilecek görüntüde aynı konumdaki pikselle toplandığında sonuca etkisi çok büyük olmuyor. Çalıştırma örnekleri bölümünde de örnekleri bulunan elde ettiğimiz görüntüler bu durumu destekler nitelikte.

Devamını Oku »

Çalışma hakkında bilgi ve çalıştırma örneklerine aşağıdaki linkten ulaşabilirsiniz:
Hareket Özetleme

Kaynak kodlar için:

Devamını Oku »

Işık Üniversitesi Data Structures and Algorithms dersi ödevlerinden basit bir kuyruk yapısı örneği:

Devamını Oku »