GARBAGE COLLECTOR ( ÇÖP TOPLAYICI )

 Merhaba arkadaşlar, bu yazı Java’ da çöp toplayıcı kavramını anlatmak için yazılmıştır. Umarım yararlı olur.

ÇÖP TOPLAYICI NEDİR?

Öncelikle ” Çöp toplayıcı nedir? ” sorusuyla başlayalım; Programda bazı nesnelerin kullanımı bittiğinde bellekten silinmeleri gerekir, nesneye yönelik programlama dillerinde bu işlem otomatik olarak gerçekleşir. Yani programcının müdahalesi gerekmeden hafıza yönetimi gerçekleşir. İşte bunu gerçekleştiren yapı ise çöp toplayıcıdır.  Çöp toplayıcısının temel görevi, kullanılmayan nesneleri bulmak ve hafızadan silmektir.


  • Ancak çöp toplayıcısının ne zaman çöpleri temizleyeceği belli değildir !
  •  Java belirli aralıklarla programı kontrol edip , işi bitmiş ve işaretlenmemiş nesneleri siler. Bu şekilde biriken nesneler programda OutOfMemoryException hatası verir.
  • Eğer bir nesne new anahtar kelimesi ile oluşturup belleğe yerleşmek ister ve bellekte de yer kalmamış olursa; çöp toplayıcı hemen bellekteki gereksiz nesneleri silerek yer ayırır.
  • Nesneler, belleğin heap alanında toplandığı için çöp toplayıcı bu alanda işlem yapar.
  • Çöp toplama isteğini JVM ( Java Virtual Machine ) gönderir.
  • Kullanılmayan nesneleri temizleyerek o alanı belleğe tekrar iade eden çöp toplayıcı otomatik olarak çalışır.

Çöp Toplayıcı Hakkında Bilinmesi Gerekenler

  • Çöp toplayıcının temel görevi , kullanılmayan nesneleri bulmak ve hafızadan silmektir. Ancak çöp toplayıcının ne zaman çöpleri temizleyeceği belli değildir. Bu belirsizlik nedeniyle bazı durumlarda çöp toplama aracını biz programcılar olarak çalıştırmak isteyebiliriz. 
  • Bu araç tetiklense bile, özellikle tetiklenen anda çalışması garanti değildir. Çünkü bu aracın çalışması için bazı durumların olmuş olması gerekiyor. Bu durumların en önemlisi ve ilki ; sanal makine için ayrılan hafızanın  azalmış olması gerekiyor. İkinci durum ise kullanılmayan nesnelerin çoğalmış olması gerekiyor. Bu iki durumun oluşması çöp toplama sistemini otomatik devreye sokacaktır.

Çöp Toplayıcı İşleyişi

  • Çöp toplama yöntemi çeşitlidir. Eski yöntem ve yeni yöntem olarak 2 gruba ayrılabilir.
  • Eski yöntem referans sayma yöntemiyle yapılırdı. Bu yöntemde, bir nesne oluşturulduğunda kendisine ait bir sayaç çalışmaya başlardı. İlgili nesne her kullanıldığında bu sayaç arttırılır, nesnenin yoğun kullanıldığını temsil ederdi. Ve nesneyi kullanan diğer parçalar nesneyle ilişkisini kestiğinde, bu sayaç değeri azalırdı. Bu sayaç değeri ne zaman sıfırlanırsa çöp toplama sistemi tarafından hedef seçilirdi. Çünkü sayacı sıfırlanan nesne kullanılmayan nesnedir.
  • İkinci yöntem ise JVM içinde HOTSPOT ( sıcak bölge ) teknolojisi vardır. Bu teknoloji sayesinde hafızadaki nesneler eski ve yeni grup olarak ikiye ayrılır. Şayet bir nesne zaman içerisinde bir çöp toplayıcı tarafından temizlenmişse , hafıza bölgesindeki eski grup alanına kopyalanır. Çöp toplama aracı genel olarak eski nesnelerin bulunduğu bölümle ilgilendiği için , eski grup alanına kopyalanan çöp nesne temizlenir.
  • Ayrıca çöp toplayıcı referansa bağlı olmayan nesneleri hafızadan siler.
  • new Personel( );   //referans yoktur  
  • Ancak bir nesne referansa bağlı ise çöp toplayıcı bunlara dokunamaz!

System.gc( ) Komutu

Bazı durumlarda çöp toplayıcıyı çağırmamız gerekebilir. Bu durumda System. gc() komut ile istediğimiz zaman çöp toplama aracını tetikleyebiliriz. Tekrar belirtmek gerekirse, bu komut bile çöp toplayıcısının hemen çalışacağını garanti etmez. Ayrıca bu komut yerine Runtime.getRuntime.gc( ) komutunu da kullanabiliriz. Aşağıda bu konuyla ilgili örnek oluşturulmuştur. Örneğimizde Personel adında bir sınıfımız vardır ve bu sınıftan üretilen iki adet nesnemiz vardır. Aynı örnek üzerinden değerlendirme tekrar yapılacaktır.

Örnek:


public static void main( String[] args) {

Personel personel = new Personel();    //nesne oluşturuldu

new Personel();                                        //isimsiz bir nesne oluşturuldu

System.gc();                                             //çöp toplama aracı tetiklendi

}


Örnek Değerlendirme

  • İlk oluşturduğumuz personel nesnesi hafızada yer alacak, kullanılmadığı taktirde hafızadan silinecektir.
  • İkinci oluşturduğumuz personel nesnesi ise isimsizdir yani bir referansa bağlı değildir. Dolayısıyla çöp toplayıcının ilk hedeflerindendir çöp toplayıcı bunu derhal yok edecektir.

Örnek Şekillendirme

 

Çöp toplayıcı devreye girdikten sonra:

 

 

 

Finalize Metodu

  • Biz javada çöp toplayıcının çalışmaya başlayacağı esnada bazı komutlar işletmek isteriz, bunu finalize metodunu kullanarak yaparız.​
  • Finalize metodunun çalışması için sadece çöp toplama aracının devreye girmesi gerekiyor. Yani bizim bu metodu ayrıca çağırmamız gerekmiyor. Çöp toplama aracı devreye girince otomatik olarak bu metot çağrılacaktır ve bloktaki komutlar işleyecektir.

Aşağıda kullanımına ilişkin bir örnek verilmiştir.


public static void main( String[] args) {

Personel personel = new Personel();    //nesne oluşturuldu

new Personel();                                        //isimsiz bir nesne oluşturuldu

System.gc();                                             //çöp toplama aracı tetiklendi

}

public void finalize() {                          //finalize metodu 

System.out.print(“Isimsiz nesne hafızadan siliniyor”);

}


Programda çöp toplama aracı çağrılıyor. Ancak çöp toplama aracı devreye girerse, sınıf içerisinde yazdığınız finalize metodu çalışacaktır. Özellikle System.gc komutu ile tetiklediğimiz halde, uygulamalarda finalize çıktısı oluşmayabilir. Biz çöp toplama aracını çağırmasak da, Personel sınıfına ait nesne silindiğinde finalize metodu çalışacaktır. Tüm anlatılan konuların içinde bulunduğu bir örnekle yazımızı sonlandırıyorum.

Örnek:

[crayon-5c3f4148bdd08671632361/]

Örneğin Ekran Çıktıları:

 

SUNUM

 

HAZIRLAYAN:

Beyza Nur Kılıç

Kaynakça: Kodlab – Java 8

  [contact-form][contact-field label=’İsim’ type=’name’ required=’1’/][contact-field label=’E-Posta’ type=’email’ required=’1’/][contact-field label=’Web Sitesi’ type=’url’/][contact-field label=’Yorum’ type=’textarea’ required=’1’/][/contact-form]

 

 




Naive Bayes Sınıflandırıcısı

Basit haliyle bir sınıflandırma-kategorilendirme algoritmasıdır. İsmini 17.yy’da yaşamış Thomas Bayes adında bir matematikçiden alır. Verilerin sınıflandırılmasından daha çok nasıl sınıflandırıldığı önemlidir bu algoritmada. En sade hali ile bir olayın herhangi bir kategoriye ait olmasinin olasılığını hesaplamada kullanilir.

En önemli kuralı niteliklerin birbirinden bağımsız olduğudur çünkü nitelikler birbirini etkiliyorsa burada olasılık hesabı zordur.Niteliklerinin hepsinin aynı derecede önemli olduğu kabul edilir. Sonucun çıkma olasılığı o sonuca etkiyen tüm niteliklerin olasılıklarının çarpımıdır.

Koşullu Olasılık ve Naive Bayes Olasılık Gösterimi

Naive Bayes teoremine girmeden önce koşullu olasılık kavramını anlamak gerekir. Koşullu olasılık ise daha önce olmuş bir olaya bakarak bir sonraki olayın gerçekleşme olasılığını bulur. Örneğin bir demokrat senatörün kadın olma olasılığını hesaplayalım. Bir senatör ya demokrat ya da cumhuriyetçi olabiliyor. Yani demokrat olma olasılığı 1/2. Bir insan da erkek veya kadın olabildiğine göre 1/2 olasılığımızda buradan gelir. Sonuçları çarptığımızda da cevabımız olan 1/4’ü elde etmiş oluruz.

Naive Bayes için kullanacağımız formül ise  P ( A | B )= P ( B | A ) x P(A) / P(B) yani B olayı gerçekleştiğinde A’nın olma olasılığı demektir. Açıklamalı hali ise :

(Kategorinin olma olasılığı * elimizdeki niteliklerin olma olasılığı) / küme sayısı).

Naive Bayes’in tam olarak nasıl kullanıldığına bir örnekle bakalım.

 

Günler Hava Durumu Sıcaklık Nem Oranı Rüzgar Şiddeti Tenis oynanıyor mu ?
1.Gün Güneşli Sıcak Yüksek Zayıf Hayır
2.Gün Güneşli Sıcak Yüksek Güçlü Hayır
3.Gün Bulutlu Sıcak Yüksek Zayıf Evet
4.Gün Yağmurlu Ilık Yüksek Zayıf Evet
5.Gün Yağmurlu Soğuk Normal Zayıf Evet
6.Gün Yağmurlu Soğuk Normal Güçlü Hayır
7.Gün Bulutlu Soğuk Normal Güçlü Evet
8.Gün Güneşli Ilık Yüksek Zayıf Hayır
9.Gün Güneşli Soğuk Normal Zayıf Evet
10.Gün Yağmurlu Ilık Normal Zayıf Evet
11.Gün Güneşli Ilık Normal Güçlü Evet
12.Gün Bulutlu Ilık Yüksek Güçlü Evet
13.Gün Bulutlu Sıcak Normal Zayıf Evet
14.Gün Yağmurlu Ilık Yüksek Güçlü Hayır

 

Bizden istenen koşullar şunlar : 15.günde ;

‘Hava durumu : Güneşli’

‘Sıcaklık : Soğuk’

‘Nem : Yüksek’

‘Rüzgar : Güçlü’

‘Tenis oynanıyor mu : Evet’

İşlemleri yaparken her niteliğin kendi olasılık kümesinin büyüklüğüne bölündüğüne dikkat etmeliyiz. Önce toplam sayılarımızı yazalım.

Toplam veri sayısı : 14

Toplam Evet sayısı : 9

Toplam Hayır sayısı : 5

Evet çıkma olasılığı P(y) = 9/14 x 2/9 x 3/9 x 3/9 x 3/9 = 0,0053

Hayır çıkma olasılığı P(n) = 5/14 x 3/5 x 1/5 x 4/5 x 3/5 = 0,0205

Yani tenis oynanmama olasılığı daha yüksek.

Örneğin Weka Üzerinde Gösterimi

Şekil 1. Datasetimiz

 

 

 

 

Ve sonucumuz karşımıza çıkıyor.

Sıfır-Frekans (Zero Frequency) Nedir ?

Yani kayıtlarımız arasında 0 olsaydı ? Burada Laplace Correction yöntemini kullanarak sorunu çözeriz. Her değere 0-1 arasında bir değer eklenerek bu sorun çözülüyor ve bu sorunun sonucuna pek etki etmeyecektir yani çok değiştirmeyecektir. Bununla ilgili Sadi Evren Şeker’in videosunda bahsettiği kısmı buraya tıklayarak izleyebilirsiniz.

Naive Bayes günlük yaşantımızda nerelerde kullanılıyor ?

Makine öğrenmesindeki temel sınıflandırıcılardandır. Spam filtrelemede çoğunlukla kullanılır. Robotik çalışmalar,Görüntü işleme,Veri Madenciliği,Metin ayrıştırılması ve Ürün sınıflandırma gibi alanlarda kullanılır.

Naive Bayes’in Avantajları ve Dezavantajları

Avantajları

  • Nispeten de olsa kolay anlaşılabilir ve yapılandırılabilir.
  • Küçük bir veri kümesiyle bile kolayca eğitilir yapıdadır.
  • Rakiplerine göre hızlı çalışır.

Dezavantajları

  • Her niteliğin birbirinden bağımsız olduğunu kabul eder ama bu her durum karşısında geçerli değildir.
  • Değişkenler arası ilişki gösterilemiyor.

Referanslar :

  1. http://bilgisayarkavramlari.sadievrenseker.com/2013/02/08/naif-bayes-siniflandiricisi-naive-bayes/
  2. https://kodedu.com/2014/05/naive-bayes-siniflandirma-algoritmasi/
  3. https://www.e-adys.com/post/2016/01/19/naive-bayes
  4. https://www.youtube.com/watch?v=BHmpDK9PoDs
  5. https://www.youtube.com/watch?v=QiLsuwtbw28https://
  6. http://www.mademir.com/2011/01/naive-bayes-snflandrma-algoritmas.html
  7. http://yudkowsky.net/rational/bayes
  8. yazilimcorbasi.blogspot.com.tr/2012/02/naive-bayes-classifier.html
  9. https://stackoverflow.com/questions/10059594/a-simple-explanation-of-naive-bayes-classification
  10. Veri Madenciliği Yöntemleri  by Dr. Yalçın Özkan sf. 173
  11. https://monkeylearn.com/blog/practical-explanation-naive-bayes-classifier/
  12. https://ipfs.io/ipfs/QmR1gzPYUwxEUWHbeRggZzfYy5Fxsd8Qc7hXUUnJQwxrZq/wiki/Naive_Bayes_sınıflandırıcı.html
  13. https://www.slideshare.net/ashrafmath/naive-bayes-15644818
  14. http://blog.aylien.com/naive-bayes-for-dummies-a-simple-explanation/

 




Yazılım Tasarımı(Software Design)

Yazılım Nedir ? Hem bilgisayar sistemini oluşturan donanım parçalarının yönetimini hem de kullanıcıların işlerini yapmak için gerekli olan konular topluluğuna yazılım denir.

Tasarım ise herhangi bir mühendislik ürünü geliştirme sürecindeki ilk adım sayılabilir.

Bir kodlayıcı , ne kadar iyi olursa olsun , bir tasarım yapıp onu yeterli bir şekilde yazılı hale getirmedikten sonra verimli bir geliştirme yapamaz .

Yazılım tasarımı , Bir binanın temeline benzetilebilir yeteri kadar sağlam olmayan bir  temel üzerine plansızca inşa edilen katlardan inşa edilen katlardan oluşan bir binanın depreme dayanıklı olması da beklenemez. Ayrıca üzerine başka katlarda çıkmak da mümkün olmayabilir.

Tasarımın temel amacı, ziyaretçi ile içerik arasında gerçekleşen iletişimi kolaylaştırmaktır. Ziyaretçilerin içeriği özgürce keşfedebilecekleri arayüz çalışmasını geliştirmek öncelikli prensip olmalıdır.

 Tasarım Aşaması (Design stage)

Tasarım, yazılımın testine kadar her şeyi etkilediğinden nitelik unsurunun öne çıktığı  ilk aşama olma özelliğini taşımaktadır. Yazılım geliştirme sürecinin ana aşamalarından ilki olan isterler çözümlemesi daha kuramsal iken , tasarım, kodlama ve test daha tekniktir.

Tasarım aşaması bir tür süreç şeklindedir. Aşamalar halinde sürdürülen bu süreç sonunda ortaya çıkan tasarım , kodlamanın ve testin temelini oluşturduğu için  mutlaka yeterli dikkat ve zaman ayrılmalıdır.

Tasarımcılar , sistem tasarımının yapılması , sisteminin yazılım öğelerinin tasarlanması , öğeler de yer alacak standart yazılım birimlerinin belirlemesi ve bu uygulama için hazırlanması , iç yapılarının tasarlarken sıfırdan başlamak zorunda değildir. Daha önce benzer bir iş yapılmış ve başarılı olduğu görülmüş bir tasarım tekrar kullanılabilir.

Tasarımın birinci amacı her zaman basitlik olmalıdır. Çünkü anlaşılır ve basit bir tasarım hem kodlamada hem de sonraki değişikliklerde kolaylık sağlar . Sistem öyle tasarlanmalıdır ki bir dizi değişiklik yapılsa bile sistem hala basit kalabilmelidir. Bunun için veri yapılarında esneklik sağlanmalı, Programlama dilinin sağladığı kolaylıklar göz önüne alınmalıdır.

Basit tasarım , yetenekleri ve özellikleri kısıtlı tasarım olarak algılanmamalıdır.

 

Tasarım Nitelikleri(Design Attributes)

  • İşlevselliği , başarımı ve güvenilirliği yüksek , nitelikli bir ürün oluşturmak ana hedef olmalıdır.
  • Öğrenim ve kullanım kolaylığı göz önünde tutulmalıdır.
  • Tasarımın isterler ile izlenebilirliği olmalıdır.
  • Geliştirilen birimin kodu ve testleri ile izlenebilirliği olmalıdır.
  • Tasarım programlama dilinden olabildiğince bağımsız , kolay anlaşılabilir kolay değiştirilebilir Ve tekrar kullanılabilir olmalıdır.
  • Yazılım projelerinde tasarım , projenin büyüklüğüne göre yazılım tasarım uzmanları veya yazılım mimarları tarafından kullanılır.

 

 

Yazılım Tasarım  Süreci(Software Design Process)

Genelde bir bütün olarak düşünülmesine rağmen yazılım tasarım aşaması da adımlar halinde gerçekleştirilir. En önemli adımlardan biri veri tasarımı olup , çözümleme sırasında toplanan bilgilerin ve bilgi yapılarının yazılımda kullanılacak veri yapılarına dönüştürülmesini içerir.

Tasarım sırasında isterlerin yazılım geliştirmede kullanılacak ifadelere dönüştürülmesi ana amaçtır. Teknik olarak, süreç başında , bu ifadeler ve gösterim tarzı ile yazılımın genel görünüşünü oluşturulurken , süreç sonunda tasarım kaynak koda yakın bir hale gelir.

 

Veri Tasarımı(Data Design)

Veri , Bilgilerin işlenmemiş halidir. Örnek Verecek olursak Öğrenci bilgi Sistemindeki(Obis) öğrencininAdi , ÖğrenciniSoyadi, ÖğrencininNumarasi  Veya şirkette çalışan personelAdı, PersonelSoyadi,PersonelCalistigi Departman bunların hepsi veriye örnektir.

Veri yapısı , Bilgisayar ortamında verilerin ,etkin olarak saklanması ve işlenmesi için kullanılan yapıya denir.

 

Veri modelleme, bir işletmenin, kurumun hatırlamaya değer bulduğu verilerin şekil ve metin olarak ifade edilmesidir.

Veri Yapıları ve veri modelleri , Birbirleriyle mantıksal olarak ilişkili olan verileri yönetilebilir  şekilde bir arada tutmaya yararlar.  Bu yapı ve modeller,  veriler arasındaki sıradüzensel ilişkileri ve erişim yöntemlerini de belirler. Yapıların düzenlemesi ve karmaşıklık düzeyi tamamen tasarımcı belirler.

Tasarımcı, veriye erişim yöntemi, hız, etkinlik, büyüklük, işlev bakımından çözümlenmesini yaparak en uygun veri türlerini ve yapılarını belirler.

Veri yapısı ile veri modeli, iç içe geçmiş iki ayrı kavramdır. Birisi verinin bellekte tutulması veya saklanmasıyla ilgilenirken diğeri veriler arasındaki ilişki ve bağıntılar konusuyla ilgilenir.

İşlevsel çözümlemeye verilen önem kadar veri çözümlemesi ve tasarımı da önem verilmelidir.

 

İyi Bir Veri Tasarımı Nasıl Olmalı ?(How to Design a  Good  Data)

 

Veri Yapıları  ve modelleri  yanında bu yapılar üzerinde yapılacak işlemlerin de tanımlanması gereklidir. Bu tanımlama , nesneye  yönelik tasarımda doğal olarak yapılır . Ancak tasarımda ayrı dikkat edilmelidir.

Kullanılacak veri yapılarını oluşturan birimlerin türleri , sınırları ve birbirleri ile olan ilişkileri bir Veri Sözlüğü içinde toplanmalıdır. Bu sözlükte kullanılacak karmaşık yapıların ve algoritmaların tasarımında kolaylık sağlanır.

Veri yapıları yalnızca kullanan modüllere görünür olmalıdır . Bu şekilde ‘Bilgi Gizleme’ ilkesine uyulmuş olur.

Çok kullanılacak veri yapıların soyut veri türleri şeklinde önceden geliştirilerek bir kütüphane haline getirilirse , tasarım sırasında bunlarla ilişkilendirilir ve kodlama test için zaman ayrılmasına gerek kalmaz . C, C++ dillerindeki kütüphaneler örnek verilebilir.

Tasarım sırasında, kodlamada kullanılacak programlama dilinin özellikleri dikkate alınarak veri yapıları tanımlanır.

Karmaşık veri yapılarının kullanımı gerekiyorsa kullanılacak programlama dili soyut veri türlerini(abstract data types) destekleyecek şekilde seçilmelidir.

Mimari Tasarım(Architectural Design)

Mimari Tasarım, Sistemin tüm yapısının tasarımı ve sistemin nasıl kurulduğunu anlamayla ilgili aşamadır. Daha net olarak ifade edecek olursak, bu aşamada, sistemin nasıl bir yapı üzerine oturması gerektiği hakkında karar verilir.

Uygulama yazılımı bir problemin çözümünü çeşitli parçalara bölerek sağlayabilir. Bu parçaların yazılımdaki karşılığı modüllerdir. Modüllerin sıradüzensel ilişkilerini gösteren yapıya uygulama yazılımı mimarisi  denir.

 

Yazılım içindeki modüller birer nesne olabileceği gibi, tasarım veya gerçekleştirme yönteminin özelliğine göre, birer programi birer paket, birer nesne veya birer yordam olabilirler. Yapının çıkış yelpazesi, genişliği ve derinliği modüler yapı hakkındaki önemli ölçütlerdir.

 

Uygulama Yazılım Tasarımı

Uygulama alanının özellikleri

Yazılımın kullanılacağı alanın gereksinimine göre yazılım birimlerini fiziksel olarak belirli donanım ögeleri üzerinde çalıştırmak gerekebilir. Sistemin merkezi yada dağınık olması, açık sistem olması, belirli bir amaçla kullanmak üzere tahsis edilmesi veya gömülü sistem olması mimari seçimine etki eder.

Uygulama yazılımının karmaşıklık derecesi

Basit uygulamalar, tek program içinde, her türlü arayüz ve bilgi işlemeyi kapsayacak şekilde geliştirilebilirler. Daha karmaşık uygulamalarda, hem geliştirme hem de yürütme bakımından yazılımı ögelere, ögeleri bileşenlere, onları da birimlere bölmek, daha kolay şekilde geliştirme, test ve bakım olanağı sağlar.

Kullanıcı arayüz kısıtlamaları

Geliştirilen yazılımın sonradan başka işletim sistemi veya donanım ile kullanılmak üzere farklı ortamlara taşınması gerekiyorsa, katmanlı bir yaklaşımla, asıl yazılımı olası taşıma işinden etkilenmeyecek şekilde tasarlamak gerekir. Bu nedenle, yazılım mimarisi içine uygun katmanlar yerleştirilebileceği gibi iletişimin zorluklarını gidermek üzere bir ara katman mantığı da kullanılabilir.

 

Yordamsal Tasarım(Procedural Design)

Yordam(procedure, function) , bilgi işlemeyi gerçekleştirmek üzere yazılım modülünün iç yapısında bulunan ve belirli işlevleri olan kod parçalarıdır.

Bir yordam , veri yapıları , döngüler , karşılaştırmalar , dallanmalar yardımıyla tüm bilgi işleme özelliklerini tanımlamalıdır.

Veri ve program yapılarının tasarımı tamamlandıktan sonra yordamsal tasarım başlar. Yordamsal tasarım , modüllerin iç yapılarındaki algoritmik ayrıntıların tanımlanmasıdır.Tasarım ,konuşma diline yakın bir anlatımla yapılabileceği gibi çeşitli şekilsel gösterimlelr de yapılabilir.

Yordamsal Tasarım Nasıl Yapılır?(How to Do Procedural  Design)

A-)Yapısal Programlama Gösterimi:  Yazılım tarihinin en eski tasarım yöntemlerinden biri işlevleri metinsel bir şekilde anlatmaktır. Bu anlatım için genellikle ingilizce kullanılmaktadır.

Program tasarım  dili(programming design language) adı verilen bir dil de tasarım için tanımlanmıştır. Sözde Kod(Psodue) adı verilen yöntem , Gerçek programlama dili yapılarına benzer şekilde ,ancak daha serbest bir sözdilimiyle her yapı ve her yordam tanımlanır.

Program tasarım dilleri genellikle ADA veya Pascal gibi yüksek düzey bir dili andırırlar. Özel bir yazılım paketi getirmeksizin normal bir metin yazıcı kullanılabilir. Tasarım dili ile yazılmış metin dosyalarını grafiksel bir tasarım yöntemine dönüştürülebilen araçlar da bulunmaktadır.

Yordamsal Tasarım Dillerinin Sahip Olduğu Ortak Özellikler
  • Her türlü yapıyı destekleyebilen sabit bir anahtar sözcük listesi
  • Veri yapıları ve veri tipleri tanımlama yeteneği
  • Alt program tanımlama ve çağırma düzeneği
  • Bilgi işlemeyi serbest bir dille anlatabilme yeteneği
  • Arayüz tanımlama yeteneği
  • Giriş/Çıkış yapıları
  • Zaman belirtimleri

Bilinen yapıların kullanımı nedeniyle okunması ve takibi kolaydır. Programlama diline yakın olduğu için kodlayıcının işi daha kolaydır. Ancak , bu anlatımda aşırıya kaçılır . ve gereksiz ayrıntıya girilirse tasarım uzar (örneğin anlaşılır olmasına rağmen bir veri yapısının tüm alanlarına tek tek veri atamayı göstermek gibi), ayrıntıya boğulur ve amacı dışına çıkılır.

B-) Grafiksel Gösterimi: Bazen bir resim birçok satırdan oluşan bir anlatımın yerine geçebilir. Bu gerçekten hareketle , çeşitli grafiksel gösterim yöntemleri bulunmuş ,bu yöntemleri kullanan yazılım tasarım araçları geliştirilmiştir.Ancak bir şeklin eksik yada yanlış çizilmesi okuyucunun gösterim simgelerini iyi bilmemesi sınucu tasarımı yanlış anlaması hatalı kodlamaya neden olabilir. Bu nedenle grafiksel gösterimlerinin iyi öğrenilmesi ve iyi anlaşılması gereklidir.

Yapısal çözümleme ve tasarım yapmak için veri akış diyagramları ve durum geçiş diyagramları kullanılır.

Unified Modelling Language(UML) : Nesneye yönelik çözümleme ve tasarımın hem metinsel hem de grafiksel olarak yapılanilmesine yardımcı olan uluslararası çevrelerce kabul edilmiş , Standart ve yaygın bir tanımlama dilidir.

 

UML Diyagram Türleri (Tr)

 

UML Diyagram Türleri (ENG)

 

 

Akış Diyagramları (Flow Charts):En Eski ve en yaygın program tasarım yöntemlerinden biri akış diyagramları(Flow Chart) kullanılmaktadır. Günümüzde bir program çok sayıda modülden veya yordamdan oluştuğundan , çok sayıda akış diyagramı kullanmak   gerekebilir.

Basit Flow Chart Kullanımı (Eng)

 

 

Basit Flow Chart Kullanımı (Tr)

Arayüz Tasarımı(interface design)

Arayüz tasarımı, kullanıcının faydalanması amacıyla sunmuş olduğunuz çeşitli yazılımsal ürünlerde onların işini kolaylaştırmak ve dilediklerini yapabilmelerini sağlamak amacıyla gerçekleştirilir. Arayüz tasarımlarının genel prensibi kullanıcı odaklı olmalarıdır.
Kullanıcı odaklı arayüzün mutlaka sahip olması gereken üç nitelik bulunmaktadır. Etkileşimli arayüz, görsel tasarım ve bilgi mimarisi bu üç niteliği oluşturmaktadır.

Kullanıcı odaklı arayüzün mutlaka sahip olması gereken üç nitelik bulunmaktadır. Etkileşimli arayüz, görsel tasarım ve bilgi mimarisi bu üç niteliği oluşturmaktadır.

   Bileşen Arayüz Tasarımı

Büyük Yazılımlar birkaç ana ögeden , her bir öge birkaç bileşenlerden ya da birimden oluşabilir. Bu bileşenler arasında mutlaka tanımlı bir arayüz vardır. Bileşenler ya da birimler birer yürütülebilir program olabilecekleri gibi , bir program grubu da olabilirler.

   Sistem- Altsistem Arayüz Yazılım Tasarımı

Bilgi sistemlerinin bazıları , başka sistemleri , altsistem veya aygıtları tümleştirerek daha büyük sistemler elde etmek üzere tasarlanırlar .Tümleştirme için özel olarak tasarlanan altsistem arayüz yazılımları kullanılır.
Kullanıcı Arayüz Tasarımı

Bilgi Sistemleri , insanların denetiminde çalıştıkların için kullanımı kolay , etkin ve açık arayüzlere sahip olmalıdırlar. Arayüz tasarımı gerçekleştirmek istiyorsanız öncelikli olarak kullanıcıyı merkeze yerleştirmelisiniz. Kullanıcının beklentilerini karşılayabilmeli, ihtiyaçlarına cevap verebilmeli ve onların eğilimlerini tahmin edebilmelisiniz.

Referanslar(Kaynakçalar)

  • Erhan SARIDOĞAN Yazılım Mühendisliği Kitabı Papatya Yayıncılık,
  • http://baskaisler.com/arayuz-tasarimi
  • http://www.ihs.com.tr/blog/10-arayuz-tasarim-kurali
  • https://www.slideshare.net/TurulCanll/cb-yazlm-mimarisi-ve-tasarm
  • https://sherpa.blog/5-adimda-veri-bilgi-data-gorsellestirme#.We-EY2i0PIU

 

 

Hazırlayan:Necmi Altuk  – Rifai Kuçi




The Big O Notation

The Big O Notation


Yazdığımız bir algoritmanın doğru çalıştığından emin olmakla birlikte bu algoritmayı, daha önce yazılmış ve aynı sonucu veren başka algoritmalarla karşılaştırmak isteyebilirsiniz. Burada teknik olarak değerlendirilecek başlıca iki başlık söz konusudur. Birincisi algoritmaların bellek kullanım miktarı, ikincisi ise algoritmaların hesaplama yapmak için harcadığı süredir. Mesela yazdığınız bir algoritma aynı işi yapan diğer bir algoritmadan daha hızlı çalışmasına rağmen çoğu bilgisayar için bellek aşımı gerçekleştiriyorsa bu pek uygun olmayacaktır.
 
Elbette diğer algoritmalarla karşılaştırma yapmak yerine,  yazdığınız bir algoritmanın tek başına analizini yapmak da isteyebilirsiniz. Bunun için yazdığınız algoritmaları ve varsa karşılaştıracağınız algoritmaları tek tek çalıştırıp hız ve bellek testi yapabilirsiniz. Ama bu tahmin edebileceğiniz gibi hem zaman açısından sıkıntı yaratır hem de elde edeceğiniz veriler donanımsal ve sistemsel değişikliklerden dolayı bilimsel olmaz.(Bu gibi işlemleri performans testi olarak da düşünebiliriz) . Bu durumda matematiksel olarak ifade edebileceğimiz, donanımsal ve sistemsel bağımlılığı olmayan bir yönteme ihtiyacımız olacaktır. Bu yöntemle algoritmamıza girdi olarak verilen verilerin miktarına bağlı olarak sonuçlar üretiriz.  İşte elde edilen bu sonuçlar ilgili algoritmanın karmaşıklığı olarak tanımlanır. Bir algoritmanın karmaşıklığı performansını etkiler ama karmaşıklık ile performans farklı kavramlardır görüldüğü gibi. Karmaşıklık hesabı yapacağımız asimptotik notasyonlardan en çok kullanılanını açıklamaya çalışayım.


Big O notasyonu, programlama dünyasında, algoritma ve program parçalarının kıyaslanması amacıyla tanımlanan bir zaman kompleksliği açıklama biçimidir. O notasyonu ilk olarak 1894 yılında Alman matematikçi Bachmann tarafından kullanılmış ve Landau tarafından da yaygınlaştırılmıştır. Bu yüzden adına Landau notasyonu veya  Bachmann–Landau notasyonu da denmektedir. Algoritmanın en kötü durum analizini yapmak için kullanılan notasyondur. Matematiksel olarak şöyle tanımlanır:

(x) ve g(x) reel sayılarda tanımlı iki fonksiyon olmak üzere, x > k olacak şekilde bir k vardır öyle ki,
|f(x)| < C*|g(x)| dir ve f(x) ∈ O(g(x))  şeklinde gösterilir. Burada C ve k sabit sayılardır ve x’ten bağımsızdırlar.

Bu tanımı bir örnekle daha açık hale getirmeye çalışayım:

Burada k = 1 (x’in 1’den büyük olduğu tüm durumlarda) ve C = 10 olarak alınmıştır. 
 

Aşağıda O fonksiyonu ile karmaşıklık hesaplamadaki bazı ana konuları madde madde açıklamaya çalışayım:

  • Sabit zamanlı ifadeler O(1) ile gösterilirler. Örnek, atama işlemleri.
  •     if – else  ifadelerinde, ifadenin if veya else bloğundaki hangi ifade karmaşıklık olarak daha büyükse O fonksiyonu o değeri döndürür. (Çünkü biliyorsunuz ki O fonksiyonu her zaman en kötü durumu analiz eder) Yani bunu şöyle ifade edebiliriz:

 Maks (if ifadesinin çalışma zamanı, else ifadesinin çalışma zamanı)

Örneğin if bloğu içi O(1) else bloğunun içi O(n) ise if – else bloğu O(n) olarak ele alınır.

[crayon-5c3f4148becbe503037114/]

  • Bir döngü ifadesinin içindeki bir ifade, döngünün dönme sayısı kadar çalışacağı için, eğer döngü N kez dönüyorsa ve döngü içindeki ifadenin çalışma zamanı C ise, toplam çalışma zamanı N*C’dır.

[crayon-5c3f4148becca043121432/]

  •  İç içe döngülerde içteki döngü N kez, dıştaki döngü ise K kez dönüyorsa ve iç döngünün içindeki ifadenin çalışma zamanı C ise, toplam çalışma zamanı N*K*C’dir.

[crayon-5c3f4148beccf526588596/]
 

O(1) : Sabit zaman / Constant time

Girdi sayısına yani “n” ‘ e bağlı olmayan işlerdir. Sabit zamanlı gösterim izah edilirken genel olarak atama operasyonları ile örneklenmektedir.
[crayon-5c3f4148becd4052994991/]
Yukarıdaki atama operasyonu örneğin, Big O çerçevesinde O(1) olarak değerlendirilir. O(1) Big O çerçevesinde olası en iyi kıyas birimidir. Çünkü en az zamanı o alır.

 

O(n) : Lineer

Koşturulacak operasyonun alacağı zaman eğer girdi sayısına bağlı olarak lineer olarak değişecekse, bu O(n) olarak değerlendirilir. Bunun meali, operasyonun alacağı zaman n’e bağlıdır olacaktır. O(n) değerlendirmesine örnek için, döngü yapısı biçilmiş kaftandır.
[crayon-5c3f4148becd8226461275/]
Burada döngü içerisindeki atama operasyonun alacağı zaman O(1) dir. Fakat bu operasyon döngüdeki girdi sayısına bağlı olarak n kere tekrar edeceği için, alacağı zaman n’e bağlıdır denir. Bu yüzden zaman kompleksliği burada O(n) dir. O(n) > O(1) dir çünkü girdi boyutuna bağlı olduğu için daha fazla zaman alacağı kabul edilir.

 

O(log n): Logaritmik

Burada girdi ve alacağı zaman logaritmik olarak ilerler. O(n)’e göre daha az zaman alacağı kabul edilir. Örnek olarak girdi sayısı olarak n = 100 düşünülürse, O(n) için zaman kompleksliği 100’e bağlı olacaktır.  log 100 = 2 olacağı için , O (log n) burada 2’ye bağlı olacaktır. Bu sebeple O(n) > O(log n) > O(1)’ dir.

O(log n) için ideal örnek binary search algoritmasıdır. binary search algoritmasında dizi elemanları sıralı olduğu için, arama operasyonu her denemede kalan eleman sayısının yarısı kadar elenecektir. Bu sebeple binary search için O (log n) denilebilir.

 

O(n log n) : Doğrusal Logaritmik

Bir önceki örnek üzerinden girdi sayısı olarak n = 100 düşünülürse, O(n) için zaman kompleksliği 100’e bağlı olacaktır.  log 100 = 2 olacağı için , O (n log n) burada 100* 2 = 200’e bağlı olacaktır. Bu sebeple O(n log n) > O (n) > O(log n) > O(1) dir.

 

O(n2) : Karesel

Operasyon/ algoritma’ nın zaman kompleksliği n*n’e bağlı olan durumlarda geçerlidir. Örneğin iç içe iki döngü operasyonun alacağı zaman n kere n kadardır. yani n*n’e bağlıdır. Bu yüzden O(n2) sonucuna varılır. Yine, iç içe üç döngü için zaman kompleksitesi  O(n3) olacaktır, çünkü n*n*n’ bağlıdır, gibi..

Yeni kıyaslama şu biçimdedir. O(n2) > O(n log n) > O(n) > O(log n) > O(1)

O(n2) ‘den daha ağır durumlar da olabilir, O(n!) ve O(cn) gibi.

 

Big O ve Eleme

Bir kod parçasının Big O analizi yapılırken tek tek Big O çıktıları hesaplanır ve en son sadeleştirmeye gidilir. Çünkü Big O çerçevesinde zaman kompleksliği olarak en büyük çıktı sonuç olarak kabul edilir. Katsayılardan ve diğer küçük Big O çıktılarından feragat edilir.

 

Analizini Yapalım

Aşağıda yer alan kod parçasının Big O gösterimi ise, O(n)’dir. Ara sonuçlar matematiksel olarak birbirine eklenir ve eleme yapılarak sonuca ulaşılır.
[crayon-5c3f4148becde486998404/]
Bilgisayar bilimlerinde bir algoritmanın incelenmesi sırasında sıkça kullanılan bu terim çalışmakta olan algoritmanın en kötü ihtimalle ne kadar başarılı olacağını incelemeye yarar.

Bilindiği üzere bilgisayar bilimlerinde yargılamalar kesin ve net olmak zorundadır. Tahmini ve belirsiz karar verilmesi istenmeyen bir durumdur. Bir algoritmanın ne kadar başarılı olacağının belirlenmesi de bu kararların daha kesin olmasını sağlar. Algoritmanın başarısını ise çalıştığı en iyi duruma göre ölçmek yanıltıcı olabilir çünkü her zaman en iyi durumla karşılaşılmaz.
 
Algoritma analizinde kullanılan en önemli iki ölçü hafıza ve zaman kavramlarıdır. Yani bir algoritmanın ne kadar hızlı çalıştığı ve çalışırken ne kadar hafıza ihtiyacı olduğu, bu algoritmanın performansını belirleyen iki farklı boyuttur.
 
En iyi algoritma en hızlı ve en az hafıza ihtiyacı ile çalışan algoritmadır. İşte en kötü durum analizi olayın bu iki boyutu için de kullanılabilir. Yani en kötü durumdaki hafıza ihtiyacı ve en kötü durumdaki hızı şeklinde algoritma analiz edilebilir.
 
 
Limit teorisindeki master teoremde büyük O ile gösterilen (big-oh) değer de bu en kötü durumu analiz etmektedir. Bu yüzden en kötü durum analizine, büyük O gösterimi (Big-O notation) veya algoritmanın sonsuza giderken nasıl değiştiğini anlatmak amacıyla büyüme oranı (growth rate) isimleri verilmektedir.
 
 
Big O’ya neden ihtiyaç duyarız ?
 
Hemen hemen her programlama dilinde çeşitli veri yapıları yer almaktadır. Bu veri yapıları üzerindeki operasyonlarda Big O ile yapılan kıyaslamaları incelemek, hangi durumda hangi veri yapısının tercih edileceği hususunda geliştiricilere fayda sağlamaktadır.
 
Yazar: Oğuzhan Yılmaz (notation3)



BUBLESORT ALGORİTMASI

Bublesort Algoritması (Kabarcık Sıralama Algoritması)

 

C Programlama Dili Bubble Sort Algoritması ile kullanıcının girdiği sayıları küçükten büyüğe sıralayan program kodu. Sıralama algoritmaları arasında en çok bilinen Bubble Sort (Kabarcık Sıralama) algoritmasını bulabilirsiniz.

  1. Kullanıcıdan gireceği sayı adedi öğrenilir.
  2. Kullanıcıdan sayılar alınır.
  3. Girilen sayılar ekrana yazdırılır.
  4. Bubble Sort algoritması ise sayılar küçükten büyüğe sıralandırılır ve dizinin yeni hali ekrana yazdırılır.

 

Sıralama algoritmalarının anlaşılması en kolay olanı Bubble Sorttur.
Bubble Sort sayı dizisindeki ilk sayıyı alır ve kendisinden sonra gelen sayıyla karşılaştırır. İkinci sayı büyükse başa alır. Küçükse değişiklik yapmaz.

Örnek : 6, 4, 8, 12, 7 sayı dizisi veriliyor ve bu sayıları büyükten küçüğe doğru sıralamamız isteniyor.

1adım : 6’yı 4 ile karşılaştırırz. 4 < 6 olduğu için sıralamada değişiklik olmaz.

2.adım : 4 ile 8 karşılaştırılır. 8 > 4 olduğundan 6, 8, 4, 12, 7 yeni sayı dizimiz olur.

3.adım : 4 ile 12 karşılaştırılır. 12 > 4 olduğundan 6, 8, 12, 4, 7 yeni sayı dizimiz olur.

4.adım : 4 ile 7 karşılaştırılır. 7 > 4 olduğundan 6, 8, 12, 7, 4 yeni sayı dizimiz olur.

5.adım : Başa dönüyoruz. 8 > 6 olduğundan 8, 6, 12, 7, 4 yeni sayı dizimiz olur.

6.adım : 12 > 6 olduğundan 8, 12, 6, 7, 4 yeni sayı dizimiz olur.

7.adım : 7 > 6 olduğundan 8, 12, 7, 6, 4 yeni sayı dizimiz olur.

8.adım : 4 < 6 olduğundan sayı dizimiz değişmez.

9.adım : Tekrar başa dönüyoruz. 12 > 8 olduğundan 12, 8, 7, 6, 4 yeni sayı dizimiz olur.

9.adımda sıralamamız sonra erer.

 

                                                       Bubble Sort C Kodu

Kaynak Kod:

#include  
int main()
{
        static int k,dizi[100],i,x,boyut,temp;
        printf(“Dizinin boyutunu giriniz :”); scanf(“%d”,&amp;boyut);
        for(i=0;i&lt;boyut;i++)
        {
              printf(“Dizinin %d. elemanini giriniz :”,i+1); scanf(“%d”,&amp;dizi[i]);
        }
        for(i=0;i&lt;boyut;i++)
        {
              printf(“%d\t”,dizi[i]);
        }
        while(x&lt;boyut)
        {
              for(i=0;i&lt;boyut1;i++)
              {
                    if(dizi[i]&lt;dizi[i+1])
                    {
                          temp=dizi[i];
                          dizi[i]=dizi[i+1];
                          dizi[i+1]=temp;
                           x=0;
                    }
                    else
                    {
                            x++;
                    }
              }
              printf(“\n\n”);
              for(k=0;k&lt;boyut;k++)
              {
                      printf(“%d\t”,dizi[k]);
              }  
        }
        return 0;
}  

 

Kod Analiz:

 

– İlk olarak kullanıcıdan dizinin boyutunu ve dizinin elemanlarını teker teker aldık.
– Daha sonra aldığımız diziyi 1 sefer ekrana yazdırdık.
– While döngüsünün içerisindeki for döngüsünde dizinin her bir elemanını bir sonraki elemanla karşılaştırıp duruma göre yer değiştirdik.
– Karşılaştırma işleminde en son olarak son eleman ve ondan bir önceki karşılaştırılacağından for döngüsü dizinin boyutunun bir eksiği kadar döner.
– Büyükten küçüğe sıraladığımızı varsayalım. Eğer baktığımız eleman bir sonraki elemandan büyükse o zaman değişme işlemi yapılmayacak ve else kısmında x değişkeni 1 artacak. Eğer değişme olursa x değişkeni 0 olacak.
– Burada dikkat edilmesi gereken yer, eğer hiç bir değişme işlemi yapılmazsa x değişkeni boyut değişkenine eşit olacak ve while döngüsünden çıkılacak.
– Yani hiç bir yer değiştirme işleminin yapılmaması demek dizi zaten sıralı halde demektir. Bu durumda dizi sıralı olduğu durumda while döngüsünden çıkılacak.

 

Ekran Görüntüsü:

C Dilinde Bubble Sort Algoritma Kodlaması

 




Sayarak Sıralama (Counting Sort) algoritması

Verinin hafızada sıralı tutulması için geliştirilen sıralama algoritmalarından (sorting algorithms) bir tanesidir. Basitçe sıralanacak olan dizideki her sayının kaç tane olduğunu farklı bir dizide sayar. Daha sonra bu sayıların bulunduğu dizinin üzerinde bir işlemle sıralanmış olan diziyi elde eder.

Sıralanmak istenen verimiz:

5,7,2,9,6,1,3,7
olsun. Bu verilerin bir oluşumun(composition) belirleyici alanları olduğunu düşünebiliriz. Yani örneğin vatandaşlık numarası veya öğrenci numarası gibi. Dolayısıyla örneğin öğrencilerin numaralarına göre sıralanması durumunda kullanılabilir.

Bu dizi üzerinden bir kere geçilerek aşağıdaki sayma dizisi elde edilir:

Dizi indisi: 0 1 2 3 4 5 6 7 8 9
Değeri (sayma): 0 1 1 1 0 1 1 2 0 1
Yukarıdaki tabloda da gösterildiği üzere dizide bulunan en büyük eleman sayısı kadar eleman içeren bir sayma dizisi oluşturulmuş ve bu dizinin her elemanına, sıralanmak istenen dizideki her elemanın sayısı girilmiştir.

Bu sayma işleminden sonra sıralı dizinin üretilmesi yapılabilir. Bu işlem de dizinin üzerinden tek bir geçişle her eleman için kaç tekrar olduğu yazılarak yapılabilir. buna göre örneğin sıralanmış dizide 0 hiç olmayacak 1’den 1 tane, 2’den 1 tane olacak şeklinde devam eder ve sonuç:

1,2,3,5,6,7,7,9

şeklinde elde edilir.

Bu sıralama algoritmasının JAVA dilindeki kodu aşağıda verilmiştir:

public static void countingsort(int[]A, int[]B, int k)
{
int C[]=new int[k]; // sayma dizisi oluşturuluyor
int i;
int j;

for(i=0; i<k; i++)
{
C[i]=0;
}
for(j=0; j<A.length; j++)
{
C[A[j]]=C[A[j]]+1 ;
}
for(i=1; i<k; i++)
{
C[i]=C[i]+C[i-1];
}
for(j=0; j<A.length; j++)
{
B[C[A[j]]]=A[j];
C[A[j]]=C[A[j]]-1;
}
}
Yukarıdaki fonksiyon bir adet sıralanacak dizi, bir adet sıralanmış hali geri döndürecek atıf ile çağırma (call by reference ile) boş dizi ve dizideki en büyük sayının değerini alır. Sonuç ikinci parametre olan boş diziye döner.

Bu sıralama algoritmasının karmaşıklığı (complexity) hesaplarnısa. Dizideki her elemanın üzerinden bir kere geçilerek sayıları hesaplanır. Bu geçiş n elemanlı dizi için n zaman alır. Ayrıca dizideki en büyük elemanlı sayı kadar (bu örnekte k diyelim) büyük olan ikinci bir sayma dizisinin üzerinden de bir kere geçilir bu işlem de k zaman alır. Dolayısıyla toplam zaman n+k kadardır. Bu durumda zaman karmaşıklığı O(n) olur.

Hafıza karmaşıklığına baklırsa (memory complexity) hafızada mevcut verilerin saklandığı bir dizi (yukarıdaki örnek kodda A dizisi). Sonuçların saklandığı ikinci bir dizi (yukarıdaki örnekte B dizisi) ve her elemanın kaçar tane olduğunun durduğu bir dizi (yukarıdaki örnekte C dizisi) tutulmaktadır. Bu durumda A ve B dizileri n, C dizisi ise k boyutundadır ve toplam hafıza ihtiyacı 2n+k kadardır.

HAZIRLAYAN: CANSU KARAKUŞ
KAYNAK:http://bilgisayarkavramlari.sadievrenseker.com




QUICK SORT (HIZLI SIRALAMA) ALGORİTMASI

Quick sort algoritması türkçe adıyla hızlı sıralama algoritması, günümüzde hala sıklıkla kullanılan bir algoritmadır. Sıralanması istenen dizi, dizi içerisinden belirlenen bir nokta (pivot noktası) yardımıyla iki alt diziye ayrılır. Pivot noktasından küçük olan elemanlar soldaki birinci alt diziye, büyük olan elemanlar ise sağdaki ikinci alt diziye taşınır. Daha sonra, yine aynı algoritma rekürsif olarak çağrılarak bu alt dizilerin sıralanması istenir. Bu işlem diziler parçalanamayacak duruma gelene kadar sürdürülür.

Örneğin sıralanacak dizi A={9,5,12,7,3,21} olsun. Şimdi bir pivot noktası belirleyelim. Pivot noktası seçimi algoritmanın çalışma prensibini etkilemese de, dizinin ortanca değerini pivot noktası olarak belirlemekte fayda var. Dizinin ilk indisi 0 ve son indisi 5’i toplayıp int türünde bir değişkene attığımızda, 2. indis numaralı dizi elemanını yani 12 değerini pivot noktası olarak belirleriz. Bu noktayı baz alarak 12 değerinden küçük sayıları soldaki diziye, büyük sayıları ise sağdaki diziye atalım. Alt dizilerimizin son durumu A1={9,5,3,7} ve A2={12,21} şeklinde oluştu. Pivot noktasını da sağdaki yada soldaki diziye dahil edebilirsiniz. Daha sonra sıralama algoritması rekürsif olarak tekrar çağrılır ve yukarıdaki işlemler tekrarlanır. Böylece dizinin öğeleri küçükten-büyüğe doğru sıralanmış olur.
Aşağıda quick sort sıralama algoritmasının java ile yazılmış örnek kodlarını inceleyebilirsiniz.

public class HizliSiralama {

public static void main(String[] args) {
int []dizi={9,5,12,7,3,21};
hizliSirala(dizi, 0, dizi.length-1);
for (inti = 0; i < dizi.length; i++)
System.out.print(dizi[i]);
}

public static int[] hizliSirala(intdizi[], intsol, intsag)
{
intpivot, gecici, i,j;
i=sol;
j=sag;
pivot=dizi[(sol+sag)/2];
do {
while(dizi[i]<pivot&& i<sag)
i++;
while(pivotsol)
j–;
if(i<=j){
gecici=dizi[i];
dizi[i]=dizi[j];
dizi[j]=gecici;
i++;
j–;
}
} while (i<=j);

if (sol<j) hizliSirala(dizi, sol, j);
if (i<sag) hizliSirala(dizi, i, sag);

returndizi;
}
}
Yukarıda java kodları verilen hızlı sıralama algoritmasına üç adet parametre gelmektedir; biri dizi, diğer ikisi de dizinin sıralamaya koyulacak parçasının sol ve sağ taraflarının indis değerleridir. Algoritma ilk çağrıldığında, n elemanlı bir dizi için sol=0, sağ=n-1 olur. Rekürsif çağırmalar sırasında sol değeri büyürken sağ değeri küçülecektir; ne zaman ki, sol değeri sağdan büyük olursa dizide bölünecek eleman kalmadığı anlaşılır ve rekürsif çağırmaların geri dönüşü başlar.

Hızlı sıralama algoritmasının ortalama zaman karmaşıklı O(nlog2n), en kötü durumda ki zaman karmaşıklığı ise O(n2) olarak çıkmaktadır.
HAZIRLAYAN: CANSU KARAKUŞ
KAYNAK;http://www.kodlamamerkezi.com/




MERGE SORT(birleştirme sıralaması)algoritması

Merge Sort (Bileştirme Sıralaması) Algoritması

Merge Sort (Birleştirme Sıralaması), diziyi ardışık olarak en küçük alt dizilerine kadar yarılayan sonra da onları sıraya koyarak bireştiren özyineli bir algoritmadır. Yarılama işlemi en büyük alt dizi en çok iki öğeli olana kadar sürer. Sonra “Merge (Birleştirme)” işlemiyle altdiziler ikişer ikişer bölünüş sırasıyla sıralı olarak bir üst dizide bireşir. Süreç sonunda en üstte sıralı diziye ulaşılır.

Algoritmanın çalışması kavramsal olarak şöyledir:

Sıralı olmayan diziyi ortadan eşit olarak iki alt diziye ayırır.
Bu ayırma işlemi, alt diziler en çok iki elemanlı olana kadar devam eder.
Alt dizileri kendi içinde sıralar.
Sıralı iki alt diziyi tek bir sıralı dizi olacak şekilde birleştirir.

Merge Sort algoritması ile Heap Sort algoritması aynı zaman aralığına sahip olmalarına rağmen Heap Sort algoritması bellekte Merge Sort algoritmasına göre daha az yer tutar ve bu algoritmalar gerçeklendiğinde Heap Sort algoritması daha hızlı çalışır. Quick Sort algoritması da bellek tabanlı dizilerde Merge Sort’a göre daha hızlı çalışmaktadır. Ancak bağlı liste sıralamasında seçilebilecek en performanslı algoritma Merge Sort algoritmasıdır. Çünkü bağlı listelerin yapısı gereği mergesort bellekte fazladan sadece 1 birim yer tutar ve bağlı listelerin yavaş ve rastgele erişim performansı nedeniyle quicksort gibi diğer algoritmaların çalışma performansı düşer, Heap Sort gibi algoritmalar için ise imkansızdır.

Algoritmanın C# Programlama Diliyle Gerçeklenmesi

Aşağıdaki “Sırala” metodu ASP sayfasındaki “Sırala” düğmesine tıklandığı zaman çalıştırılacak kodları içermektedir. Bu metodda ilk olarak metin kutusuna girilen sayı kadar eleman alabilecek int türünden bir dizi tanımlanmıştır. Dizinin elemanları ise 1’den metin kutusuna girilen sayıya kadar olacak şekilde rastgele verilmiştir.

protected void Sırala(object sender, EventArgs e)
{
int n = Convert.ToInt32(tb.Text);
int[] A = new int[n];

Random r = new Random();
Stopwatch stopwatch = new Stopwatch();

for (int i = 0; i < n; i++)
A[i] = r.Next(1, int.Parse(tb.Text.Trim()));

stopwatch.Start();
MergeSort(A, 0, n – 1);
stopwatch.Stop();

TimeSpan timespan = stopwatch.Elapsed;
string elapsedTime = String.Format("{0:00}.{1:000}",
timespan.Seconds, timespan.Milliseconds);
Response.Write("Gecen Zaman: " + elapsedTime);
}

Aşağıdaki "Merge Sort" metodu tanımlanan diziyi, sadece iki elemanlı altkümeleri kalacak şekilde rekürsif olarak ayırır ve "Merge" metodu çağrılır.

static void MergeSort(int[] A, int p, int r)
{
if (p < r)
{
int q = (p + r) / 2;
MergeSort(A, p, q)
MergeSort(A, q + 1, r);
Merge(A, p, q, r);
}
}

Aşağıdaki "Merge" metodu sıralama işlemini gerçekleştiren metoddur. "MergeSort" metodu ile ayrılan dizi parçalarının elemanlarını, iki elemanlı en küçük dizilerden başlayarak sıralama işlemini gerçekleştirir. Daha sonra bir yanındaki iki elemanlı dizi ile birleştirerek sıralama işlemine devam eder ve sonunda tanımlanan dizi sıralanmış olur.

static void Merge(int[] A, int p, int q, int r)
{
int n1 = q – p + 1;
int n2 = r – q;
int[] L = new int[n1 + 1];
int[] R = new int[n2 + 1];

for (int i = 0; i < n1; i++)
L[i] = A[p + i];

for (int j = 0; j < n2; j++)
R[j] = A[q + j + 1];

L[n1] = Int32.MaxValue;
R[n2] = Int32.MaxValue;

int x = 0, y = 0;

for (int k = p; k <= r; k++)
{
if (L[x] <= R[y])
{
A[k] = L[x];
x++;
}
else
{
A[k] = R[y];
y++;
}
}
}

Bu uygulamanın çıktısı aşağıdaki gibi olacaktır.

HAZIRLAYAN;atiye nur özpınar
KAYNAK:http://bidb.itu.edu.tr




shell sort(kabuk sıralama)

Bilgisayar bilimlerinde kullanılan sıralama algoritmalarından birisi de kabuk sıralamadır (shell sort).  İsmi Türkçeye kabuk sıralaması olarak çevrilsede aslında Donald Shell isimli algoritmayı ilk bulan kişinin isminden gelmektedir. Algoritma performansı O(n2)’dir. Çalışması aşağıdaki örnek üzerinde anlatılmıştır:

Sıralayacağımız sayılar:
[crayon-5c3f4148bf351235120882/]
olarak verilmiş olsun. Sıralama işlemi için öncelikle bir atlama miktarı belirlenir. Atlama miktarının belirlenmesi için çok çeşitli yollar bulunmasına karşılık en basit yöntem elimizdeki sayıların yarısından başlamaktır. Yani yukarıdaki örnekte elimizde 7 sayı olduğuna göre 3 atlama miktarı ile başlanabilir.

Sırasıyla her sayı kendinden 3 sonraki sayı ile karşılaştırılır ve bu sayılar kendi aralarında sıralanır. Bu sıralamayı daha rahat göstermek için aşağıdaki kolon gösterimi kullanılabilir:

5,7,2

9,6,1

3*****

Her kolon kendi içinde sıralanınca aşağıdaki sayılar elde edilir:

3,6,1

5,7,2

9

Yukarkıdaki örnekte de görüldüğü üzere sayıları sıralama işleminin 3te biri bitirilmiştir. Ardından atlama miktarı yarıya indirilir (bu örnek için 3/2 = 1 olur)

Bu durumda bütün sayılar tek bir doğrultuda sıralanır.

3,6,1,5,7,2,9

1,2,3,5,6,7,9

Yukarıdaki sıralamada örneğin kabarcık sıralaması (bubble sort) kullanılırsa dizinin orjinal haline göre (yani kabuk sıralamasının 3 atlamalı sıralama işlemi yapılmamış haline göre) çok daha başarılı olduğu görülür.
[crayon-5c3f4148bf35b486774231/]
Yukarıdaki örnek kodda bir dizinin (p) içerisindeki sayıları kabuk sıralamasına göre sıralayan fonksiyon verilmiştir. Fonksiyon girilen sayıları 5/11 oranında küçülen atlama miktarları ile kabarcık sıralaması kullanarak sıralamaktadır. Okuyucu döngünün içerisinde yapılan ve temp değişkeni kullanılan işlemin bir yer değiştirme (swap) işlemi olduğuna dikkat edebilir.

HAZIRLAYAN:ATİYE NUR ÖZPINAR

KAYNAK :http://bilgisayarkavramlari.sadievrenseker.com




Tarak Sıralama Algoritması(Comb Sort)

Comb Sort yani “Tarak Sıralaması” adından da anlaşılacağı gibi karşılaştırmalı bir sıralama algoritmasıdır. Aslına bakarsak kabarcık sıralaması ile hızlı sıralama karışımı diyebiliriz.Nisan 1991’de Stephen Lacey ve Richard Box tarafından duyurulmuştur. Tarak sıralaması tıpkı kendisi gibi karşılaştırmalı bir sıralama algoritması olan Kabarcık sıralamasından daha iyidir. Kabarcık sıralamasında sayılar bir yanındaki sayı ile karşılaştırılır ve ona göre yer değişimi yapılır.Karşılaştırma mesafesi 1’dir. Tarak sıralaması da aynı bu mantıkla çalışır ama yer değişimi yanındaki sayılar ile değilde daha uzaktaki sayılar ile yapılır.Bu uzaklık büyük bir sayı ile başlar ve her seferinde “shrink factor” dediğimiz 1.247330950103979 -çoğunlukla daha kolay olsun diye 1.3’e yuvarlanır- sayısı oranınca ta ki algoritma basitçe kabarcık sıralamadaki uzaklığa yani 1 olana kadar küçültülür. Tarak sıralamasının bu şekilde olmasının ana fikri ise listenin sonundaki küçük değerli öğeleri önce bularak listeden çıkarıp daha hızlı çalışmaktır. Kabarcık sıralamanın en büyük sorunu listenin sonunda olan küçük sayıları bulması için çok zaman harcamasıdır. Tarak sıralaması ile daha hızlı sonuç elde edilir.
Aşağıdaki gibi bir dizimiz olduğunu varsayalım ve küçükten büyüğe doğru sıralamaya çalışalım. İşte başlıyoruz…


İlk önce dizinin boyutunun “shrink factor” dediğimiz 1.247330950103979 sayısına bölünmesi gerekir biz yuvarlayıp 1.3 sayısına böleceğiz. Bölümün tam kısmını alırız. 5/1,3 = 3,8. Tam kısmı 3.
İlk elemanı seçeriz ve 3 fazlası olan eleman ile karşılaştırırız.

Sonra ikinci elemanı seçeriz ve +3 fazlası olan eleman ile karşılaştırırız.

Ardından üçüncü elemanı seçeriz. +3 fazlası dizinin uzunluğunu aştığı için işlem yapılamaz. Boşluk sayısını tekrar 1,3’e böler ve tam kısmını alırız. 3 / 1,3 = 2,3 Tam kısmı 2 olarak alırız. Birinci elemanı seçer ve +2 fazlası olan elemanla karşılaştırırız.

İkinci elemanı seçeriz ve +2 fazlası olan elemanla karşılaştırırız. Sonra diğer elemanları seçer +2 fazlası olan elemanlar ile dizinin sonuna kadar karşılaştırırız.

Dizinin sonuna geldiğimizde tekrar boşluk sayısını 1,3’e böleriz.. 2 / 1,3 = 1,5 tam kısmı alırız. 1. elemanı seçer ve 1 fazlası olan yani bir sonraki elemanla karşılaştırırız.Sonra ikinci elemanı sonraki elemanla. Diğer elemanları da bir sonraki elemanlarla karşılaştırırız.


Ve nihayetinde dizimiz sıralanmış olur.
[crayon-5c3f4148bf770370182786/]

Hazırlayan: Ömer Koyuncu

Kaynakça:

  1. http://www.ibasoglu.com/
  2. http://bilgisayarkavramlari.sadievrenseker.com/
  3. https://en.wikipedia.org/