Sezgisel Algoritmalar

Sezgisel Algoritmalar

Bilgisayar bilimlerinde, sezgisel ya da buluşsal (heuristic) bir problem çözme tekniniğidir. Sonucun doğruluğunun kanıtlanabilir olup olmadığını önemsememektedir fakat genelde iyiye yakın çözüm yolları elde eder. Sezgisel algoritmalar ise geçiş süresinde daha verimli hale gelebilmek için en iyi çözümü aramaktan vaz geçerek çözüm zamanını azaltan algoritmalardır.
Sezgisel algoritmalar en iyi sonucu bulacaklarını garanti etmezler fakat makul bir süre içerisinde bir çözüm elde edeceklerini garanti ederler. Genellikle en iyiye yakın olan çözüm yolununa hızlı ve kolay bir şekilde ulaşırlar.
Sezgisel arama algoritmalarına örnek olarak

• A* araması (A star)
• Demet araması (Beam search)
• Tırmanış Araması (Hill climbing)
• En iyi öncelikli arama (Best first search)
• Açgözlü en iyi öncelikli arama (Greedy best first search)

Heuristic diğer bir anlamıyla; bir düğümden (node) başka bir düğüme olan en kısa yolun maliyetini hesaplayan fonksiyonlar olarak bilinir.

Bilgisayar bilimlerinde en kısa yol bulmak için kullanılan algoritmalardan birisidir. Örneğin seyyar tüccar problemi (travelling salesman problem, TSP) gibi bir problemin çözümünde kullanılabilir. Benzer şekilde oyun programlamada, oyunda bulunan oyuncuların en kısa yolu bularak hedefe gitmeleri için de sıklıkla kullanılan algoritmadır.

Kısaca bir düğümden (node) hedef bir düğüme (target node) en kısa hangi düğümler üzerinden gidileceğini bulmaya yarayan “en iyi yerleştirme (best fit)” algoritmasıdır. Ve işte bazı sezgisel algoritmalara örnekler;

A* algoritması

yapı olarak muteber sezgisel (admissable heuristic) bir algoritma olarak sınıflandırılabilir. Bunun sebebi algoritmasının mesafe hesaplamada kullandığı fonksiyondur:

f(n) = g(n) + h(n)

denklemindeki

f(n) = hesaplama yapan sezgisel (heuristic) fonksiyon.

g(n) = Başlangıç düğümünden mevcut düğüme kadar gelmenin maliyeti

h(n) = Mevcut düğümden hedef düğüme varmak için tahmin edilen mesafe.

Dikkat edileceği üzere f(n) fonksiyonunun sezgisel olma sebebi, bu fonksiyon içerisinde bulunan ve tahmine dayalı olan h(n) sezgisel fonksiyonudur.

Algoritmanın çalışması:

Algoritma yukarıdaki toplama işlemini kullanan oldukça basit bir yapıya sahiptir. Veri yapısı olarak bir öncelik sırası (priority queue) kullanan algoritmada en öncelikli olan düğüm f(n) değeri en düşük olan düğümdür.

1.      Algoritma her adımda en düşük değeri (Ve dolayısıyla en önemli) düğümü alır (yani bu düğüme gider) ve düğümü sıradan (queue) çıkarır.

2.      Gidilen bu düğüme göre komşu olan bütün düğümlerin değerleri güncellenir (artık bu düğüme gelmenin bir maliyeti vardır ve dikkat edilirse f(n) fonksiyonu içerisinde bu değer yer almaktadır.)

3.      Algoritma yukarıdaki adımları hedefe varana kadar (yani hedef düğümü öncelik sırasında (priority queue) en öne gelene kadar) veya sırada (queue) düğüm kalmayana kadar tekrarlar.

4.     Örnek Çalışma:

5.     Algoritmanın çalışması için aşağıdaki örneği ele alalım:

6.     

7.     Yukarıdaki grafikte sol üst köşedeki düğümden, sağ alt köşedeki düğüme gitmek isteyelim. Bu durumda f(n) fonksiyonunu oluşturan mesafe değeri, grafik üzerindeki yol maliyetleri olarak hesaplanbilir. Sezgisel fonksiyon olarak, bir düğümün hedefe olan kuş uçuşu mesafesini alalım. Yani iki düğüm arasındaki mesafeyi çizilen yoldan değil de iki düğüm arasındaki cetvel ile ölçülen değer olarak kabul edelim.

8.     Bu durumda düğümlerin sezgisel mesafelerini (heuristic) gösteren graf aşağıdaki şekildedir:

9.     

10. Yukarıdaki bu grafikte kırmızı renkle gösterilen değerler, o düğümden hedef düğüm olan sağ alt köşedeki düğüme olan kuş uçuşu mesafeyi göstermektedir. Bu değerleri kısaca h(n) olarak kabul edebiliriz.

11. Başlangıç düğümümüz olan sol üst köşedeki düğümden başlayarak iki düğümün değerini hesaplayalım. Başlangıcın altında bulunan düğüm için h(n) = 9 ve g(n) = 4 olmaktadır.

12. Başlangıcın sağında bulunan düğüm için ise h(n) = 8 ve g(n) = 3 olmaktadır. Buna göre:

13. f(aşağı) = 9+4 = 13

14. f(sağa) = 8 +3 = 11

15. olarak bulunmaktadır. Algoritmamız bu seçimler arasından küçük olan (ve önceliği yüksek olan) sağa gitmeyi tercih eder.

16. Bu seçimi aşağıdaki şekilde gösterelim.

17. 

18. Yukarıdaki bu seçimden sonra değerler tekrar hesaplanır. Yukarıda yapılan seçime göre düğümlerin değerleri tekrar f(n) = g(n) + h(n) olarak hesaplanırsa:

19. 

20. Yukarıdaki bu grafikte görüldüğü üzere sıramızda (queue) iki düğüm bulunmakta ve iki düğümün değerleri sırasıyla 13 ve 11 olmaktadır.

21. Bu durumda 11 olan düğümü seçip aşağı doğru hareket ediyoruz.

22. 

23. Yukarıdaki son durumda 13 ve 21 değerleri olan iki düğüm arasında seçim yapıldığında, kısa değer olarak 13 bulunduğu için A* arama algoritmamız bu aşamada geldiği alternatif yoldan vaz geçerek en kısa yolun bu yeni düğüm olabileceğini düşünür ve bu yola gider.

24. 

25. Yukarıdaki şekilde bu yeni seçim yeşil renk ile gösteirlmiştir. Yeni seçim yapıldıktan sonra ulaşılan komşu düğümler 14 ve 21 değerlerine sahiptir. Bu durumda 14 değerine sahip olan daha öncelikli düğüme hareket edilecektir.

26. Yeni halinde değerler hesaplandığında sonuç düğümüne gidilmesi mümkündür ve ulaşım değeri yukarıdaki dolaşmaya göre daha düşüktür.

27. 

28. Yukarıdaki son durumda hedefe ulaşılmış ve aşağıdaki yol kullanılmıştır. Sonuçta ulaşım için harcanan mesafe toplandığında 4+6+4 =14 mesafesi diğer alternatif olan 3+4+6+8 =21 değerine göre daha kısadır.

29. Tabi A* algoritması sezgisel bir algoritma olduğu için bu durumu bilmemektedir.

Demet araması(ışın) algoritması

En iyi ilk arama yaklaşımını kullanan arama algoritmaları, arama yaptıkları şekil (graph) üzerinde bütün çözüm ihtimallerini belirli bir sezgisel fonksiyona göre sıralarlar. Diğer bir deyişle arama işlemi sırasında sezgisel bir fonksiyona göre, aramada bazı kararlara öncelik verirler. Bu sezgisel fonksiyonun amacı, karar anında verilen kararın, sonuç durumuna (goal state) ne kadar yakın olduğunu yargılayabilmektir.
Işın aramasının bir özelliği de, daha önceden belirlenmiş ve sınırlı sayıdaki, yapmış olduğu seçimleri saklamasıdır.
Işın araması, bir arama ağacı (search tree) oluştururken, sığ öncelikli arama (breadth first search) yaklaşımı kullanır. buna göre ağacın herhangi bir seviyesinde, gidilebilecek düğümlerin sezgisel değerlerini hesaplar ve bunlardan sadece belirli sayıdaki düğümü, daha sonra geri dönülmek üzere hafızasında tutar. Bu değere ışın aramasına özgü olarak ışın genişliği (beam width) ismi verilir.
Işın genişliği arttıkça daha fazla düğüme bakılmaktadır. Işın genişliği azaldıkça da daha fazla düğüm budanmaktadır (prunning). Budama işleminin dez avantajı, şanssız bir şekilde en iyi sonucu verecek düğüme giden yolu budama riskidir. Ancak bu riskten dolayı bütün düğümleri tutmak (yani hiçbir düğümü budamamak) gibi bir karar verirsek, bu karar sonucunda da çok daha fazla hafıza ve işlem ihtiyacımız olacaktır. İşte ışın araması, bu iki karar arasında en iyi (optimum) noktayı bulmayı amaçlar.
Bu amaca yönelik olarak, ışın araması sabit ışın genişliği (fixed beam width) veya değişken ışın genişliği (variable beam width) kullanacak şekilde kodlanabilir. Değişken ışın genişliği alan arama algoritmasında, öncelikle ışın genişliği asgari değerde tutularak arama yapılır. Aranan en iyi sonuca ulaşılamazsa, ışın genişliği arttırılarak arama işlemi sürdürülür. Beklenen sonuca ulaşılana kadar da ışın genişliği arttırılır.

Işın aramasının kullanıldığı yerlerden birisi de bilgisayarlar tarafından otomatik olarak yapılan tercüme işlemleridir. Bilindiği üzere bir kelime, bilgisayar tarafından işlendiğinde, birden fazla anlama gelebilmektedir. İnsanlar kelimenin kullanımından (syntax, pragma) kelimenin anlamını kısa sürede doğru olarak anlayabilmekte ancak bilgisayarlar için bu anlama süreci ve doğru anlamın bulunması (semantics), hatırı sayılır bir süre almaktadır.
Çözüm olarak ışın araması algoritması, çok sayıdaki çeviri ihtimallerinden sadece belirli bir kısmını işleyerek doğru tercümeyi yapmak için kullanılabilir.

Tırmanış (Tepe Tırmanma) Algoritması

Bilgisayar bilimlerinde kullanılan arama algoritmalarından birisidir. Arama işleminin yapıldığı grafikteki tepelerden ismini alır. Basitçe bir grafikte bulunan en düşük noktanın aranması sırasında grafikte yapılan hareketin aslında tepe tırmanmaya benzemesinden ismini almaktadır.

Örneğin yukarıdaki şekilde gösterilen ok temsili bir tepe tırmanma işlemidir. Burada arama yapan algoritma aslında bir çukur bulmuş ancak daha iyisi için tepe tırmanmaktadır denilebilir.

Elbette olayı iki boyutlu bir grafik üzerinde yapılan bir arama veya tırmanılan bir tepe olarak görmek, algoritmanın önemini kavramayı engelleyebilir. Aslında burada anlatılmak istenen bilgisayar bilimleri de dahil olmak üzere, çeşitli bilim ve mühendislik alanlarında, birden fazla çözümü olan problemler için en iyi çözümün arandığı iyileştirme (optimization) problemleridir.

Yani şayet bir sistemin ya da bir programın daha iyi hale getirilmesi isteniyorsa, sistemin verdiği sonuçlara göre arama işlemi yapılarak iyileştirme amaçlanabilir. İşte bu noktada tepe tırmanma algoritması (hill climbing algorithm) de dahil olmak üzere çeşitli arama algoritmaları devreye girer. Örneğin literatürde sıkça kullanılan seyyar tüccar problemi (travelling salesman problem) bu problemlerden birisidir. Tepe tırmanma algoritması verilen bir harita için verilen bir sonucu iyileştirmeye çalışır. Elbette amaç bütün ihtimalleri denemeden iyi bir sonuç bulabilmektir.

Tepe tırmanma algoritması, arama algoritmaları arasındaki en iyi sonucu verene algoritma değildir. Ancak kodlanması ve tasarımının basit oluşundan dolayı sıklıkla kullanılır.

Tepe tırmanma algoritması çeşitleri

Algoritmanın üzerinde çeşitli iyileştirmeler yapılarak daha iyi sonuçlar elde edilmeye çalışılmıştır. Literatürde sıkça kullanılan bir iki tepe tırmanma algoritmasını farkları ile birlikte açıklamaya çalışalım.

Klasik tepe tırmanma algoritmasında amaç arama için merkez kabul edilen (veya başlangıç noktamız diyebileceğimiz) noktadan komşu olan noktaları gezerek daha iyi sonuçlar elde etmektir. Temel olarak bir grafikte rastgele seçilen bir nokta için 3 farklı ihtimal bulunmaktadır:

1.     Noktanın bir tarafında problem iyileşirken diğer tarafında kötüleşmektedir. Bu durumda iyi tarafa doğru tırmanma algoritmamız devam eder.

2.     Noktanın iki tarafında da problem sonucu kötüleşmektedir. Bu durumda bulunduğumuz nokta problem için en iyi noktalardan (optimum points) birisidir. Elbette bu en iyi sonuç olmayabilir yani bu sonuçtan daha iyi sonuçlar olabilir ancak klasik tepe tırmanma algoritması bu diğer sonuçları bulamaz ve bu noktada kalır.

3.     Noktanın iki tarafında da problem iyileşiyordur. Yani tesadüfen bulduğumuz nokta aslında problem için ulaşılabilecek en kötü noktalardan birisidir. Bu durumda tepe tırmanma algoritması yönlerden birisini seçerek tırmanmaya devam eder. Farklı bir çeşit olarak iki yöne de tırmanan algoritma bulunmaktadır.

Klasik tepe tırmanma algoritmasından farklı olarak steepest ascent hill climbing algoritmasında, bulunabilen bütün sonuçlar arasından bir seçim yapılır. Bu algoritmada da klasik tepe tırmanma algoritmasında da sorun aynıdır. Şayet arama işlemi sırasında bir yerel çukura (local minimum) rastlanılırsa bu durumdan algoritma kendisini kurtaramayarak en doğru sonucu bulamayabilir.

Buna karşılık olasılıksal tepe tırmanma algoritmasında ( stochastic hill climbing algorithm) bütün komşuların aranması ve komşuların verdiği sonuca göre hareket etmek yerine, rast gele olarak bir komşunun seçilmesi söz konusudur. Şayet gidilen bu komşu beklenen yönde bir iyileştirme sağlıyorsa, bu yönde aramaya (tırmanmaya) devam edilir, şayet beklenen iyileştirme sağlanamıyorsa, bu durumda daha farklı bir komşu denenir.

Yukarıdaki tepe tırmanma algoritmalarının yanında rastgele başlangıç tepe tırmanma algoritması (random restart hill climbing algorithm) şaşırtıcı derecede iyi sonuç veren bir algoritmadır. Bu algoritma basitçe bir x durumunu başlangıç kabul eder ve daha iyi bir durum bulunca başlangıç durumunu bu daha iyi duruma kaydırır. Algoritma iyi durum buldukça başlangıç durumunu kaydıran ancak bulamadığı durumlarda da aramaya devam eden bir yapıya sahiptir. Rastgele başlangıç tepe tırmanma algoritmasına bazı kaynaklarda pompalı tüfek tepe tırmanma algoritması (shotgun hill climbing algorithm) ismi de verilmektedir.

Tepe tırmanma algoritmaları genel olarak yerel bir başarı noktasında (local optimum point) takılmak gibi bir zafiyete sahiptirler. Daha iyi sonuçlar için simulated annealing gibi arama algoritmaları kullanılabilir.

Örneğin yukarıdaki şekilde x ve y noktaları arasında bir düzlük bulunmaktadır. Başlangıç noktası olarak bu aralıktaki herhangi bir noktadan başlanırsa algoritma komşuları aradığında daha iyi veya daha kötü bir sonuç bulamayacağı için hatalı karar verebilir.

Ayrıca tepe tırmanma algoritmaları problem sonuçlarında nadiren de olsa aynı sonucun elde edilmesi durumunda belirsizce hatalı sonuçlar verebilir. Bu şekildeki durumlara algoritmadaki düzlükler ismi verilir ve algoritma hangi yöne gidilirse gidilsin daha iyi bir sonuç çıkaramaz (hep aynı sonucu çıkarır). Elbette doğası gereği tepe tırmanmaya hazırlanmış algoritmamız, tepe bulamayınca hata yapmaktadır.

Algoritmanın kodlanması

Algoritma iki boyutlu bir grafik için rastgele yön seçimi yapılması durumunda aşağıdaki şekilde kodlanabilir:

Yukarıdaki kodda, basitçe başlangıç noktasından başlanarak, daha iyi sonuçlar bulunduğu sürece bir sonraki komşu noktaya hareket öngörülmüştür.

Ancak problemin çok boyutlu olması yani bir noktanın birden fazla komşusu bulunması durumunda bütün komşuların kontrol edilmesi ve en iyisinin bulunması daha sonra bu komşuya doğru hareket edilmesi gerekeceği için algoritmayı aşağıdaki şekilde yazmak mümkündür:

Yukarıdaki yeni kodda, bir noktanın birden çok komşusu olduğu kabul edilmiş ve bütün komşuları dolaşılarak en iyi komşu alınmış, ardından daha iyi komşu bulundukça bu işlem devam ettirilmiştir. Nihayetinde hiçbir komşu, bulunan son komşudan daha iyi olmayınca program sonlandırılmıştır

Zeki Alasya Mason muydu?

Zeki Alasya Mason muydu?

Yaşamını yitiren Zeki Alasya'nın Mason olduğu yönündeki açıklamaları da uzun süre gündemde kalmıştır.

Türk sinema ve tiyatrosunun en ünlü oyuncu ve yönetmenlerinden Zeki Alasya, neden Mason olduğunu açıklamıştı. Star gazetesinden Murat Menteş'e konuşan Alasya, partneri Metin Akpınar'ı Mason yapamamaktan şikayet etmişti.

İşte o röportajın ilgili bölümü...

Masonlukla bir ilginiz var mı?
Ben Masonum.

Masonların dünyayı yönettiği söyleniyor. Siz de yönetiyor musunuz?
Hayır, dünyayı yönetmiyorum. Masonluk bir ahlak ve kardeşlik sistemidir. Bir din değildir kesinlikle. İnsanların kardeş olması gerektiğini öne çıkaran bir yapıdır. Çok kötü tanınıyor. Ben Mason olmaya kalktığım günlerde ailem dehşete kapıldı.

Ne zaman Masonluğa geçtiniz?
15 sene oldu. Metin Akpınar 'Zeki bana Mason olmayı önerdi, kabul etmedim' diye bir açıklama yapmıştı. Öyle mi sahiden?
E tabii, ben Mason olunca, Metin'in de Mason olmasını istedim. Fakat yanaşmadı.

Kimler Mason oluyor?
Mesleğinde ileri gitmiş kişiler kabul ediliyor. Zenginlerin toplandığı bir yer değildir. Ben Mason olduğumda kiralarımı ödemekte zorluk çekiyordum.

Kaç Mason var?
Dünyada 6 milyon, Türkiye'de de 15 bin. Masonluk ulusal bir kuruluştur. Sanıldığı gibi kökü dışarıda, Siyonist filan değildir. Ateistseniz Mason olamazsınız.

Hangi dinden olmak gerekiyor?
Belli bir dinden ziyade, Yaratıcıya inanmak gerekir. Yaratıcı'ya 'Evrenin Ulu Mimarı' diyoruz. Bence çok güzel bir tabir. Masonluğu vahşi ve aşağılık bir şey olarak anlatan kitaplar okumuştum. Halbuki ahilik, Bektaşilik, Mevlevilik gibi bir oluşum.

Masonluk size çok şey kattı mı?
Çok. Sabırlıydım, sabrım arttı. Paylaşmayı severdim, paylaşımcılığım arttı. Üç-beş kişi bir araya gelip saçma sapan şeyler konuşuyorduk. Futbol, para, kadınlar, dedikodu... Bir arayışa girmiştim. Masonlukta karar kıldım. Çok memnunum.

Çok ilginç... Masonlar genellikle Masonluklarını gizler.
Evet. Başlarına bir şey gelecek diye korkuyorlar. Mesela Devlet Tiyatrosu'nda çok Mason var, söylese işinden olacak.

Eklemek istediğiniz bir şey var mı üstadım?
Bu üstat lafını çok severim, biz Masonlar çok kullanırız... Hayatta her şey olur, para gelir, şöhret gelir, bilgi gelir... Hepsinden önemlisi iyi insan olmaktır.

Zeki Alasya: Pişmanım, din düşmanı değilim
CNN Türk'te Cüneyt Özdemir'in hazırlayıp sunduğu "5N 1K" programına konuk olan Zeki Alasya 30. uluslararası İstanbul Film Festivalinde büyük tepki çeken konuşmalarına açıklık getirdi. Alasya namaz kılmanın gerekli ve kutsal bir ibadet olduğuna inanan biri olduğuna kimsenin görmesi için yapılan bir ibadet olmadığını ifade etti.

Talebeler Sahnede Toplu Namaz Kıldı
1967 yılında Milli Talebeler Birliğini dinci örgencilerin ele geçirdiğini oyun oynanan sahnede toplu şekilde namaz kılındığını sahneyi mescide dönüştürüldüğünü amaçları ise birilerine bir şeyler gönderme olduğundan dolayı tepki gösterdiğini belirtti.

Pişmanım - Ben de İnadet Ederim
Namaz kılmanın kutsallığına inan biri olduğunu ve söylediği sözlerden dolayı pişman olduğunu ifade eden Alasya, din düşmanı olmadığını, temiz bir müslüman olduğunu ve kendisinin de ibadet eden biri olduğunu söyledi.

Branch and Bound (Dallanma ve Sınırlandırma Yaklaşımı)

Branch and Bound Algoritması (Dallanma ve Sınırlandırma Yaklaşımı)

 Nedir Peki?

Bu yazının amacı, algoritma analizi konusunda geçen ve algoritmaları sınıflandırmak için kullanılan bir yaklaşımı, dallanma ve sınırlandırma (branch and bound) yaklaşımını açıklamaktır.

Algoritma, basitçe verilen bir fonksiyon için en iyi (optimum) çözümü bulmayı amaçlar. Bu amaca sahip çok sayıdaki yaklaşımdan farkı ise bu amaca ulaşmak için iki çok önemli aracı kullanıyor olmasıdır:

• Parçalama (Splitting) veya Dallandırmda (Branching)
• Sınırlandırmda (Bounding)

Bu iki yaklaşım sırasıyla probleme uygulanır. Parçalama aşamasında, problem alt parçalarına ayrılır (Burası parçala fethet (divide and conquere) yaklaşımına benzemektedir) ardından bu parçalar için alt ve üst sınırlar (upper and lower bounds) belirlenir.

Algoritma özellikle oyun programlamada sıkça kullanılmaktadır. Yapay zeka yaklaşımının kodlandığı ve karar ağacı oluşturulduğu durumlarda, ağacın dallarına bölünmesi ve her dal için limitlerin belirlenmesi şeklinde çalışır.

Ayrıca algoritmanın iyileştirilmesi için alfa-beta budaması (alpha beta prunning) benzeri yöntemler kullanılabilir.

Algoritmanın en önemli özelliklerinden birisi NP-Hard problem grubu için kullanışlı olmasıdır.

Algoritmanın kullanıldığı bazı problem tipleri aşağıda sıralanmıştır:

• Azami Tatmin Problemi (Maximum Satisfaction Problem)
• Torba Problemi (Knapsack Problem)
• Seyyar Satıcı Problemi (Travelling Salesman Problem)

Örnek olarak 0-1 Torba problemini (0-1 Knapsack problem) çözmeye çalışalım. Öncelikle problemi hızlıca hatırlayalım. Amacımız elimizdeki torbayı mümkün olan en değerli şekilde doldurmaktır. 0-1 torba problemi ise klasik torba probleminin özel bir halidir ve bu özel halinde bir eşya, ya tamamen alınır ya da tamamen bırakılır, bir eşyanın bir kısmını almak mümkün değildir.

Örneğin aşağıdaki tabloda verilenleri ele alalım:

Eşya	Ağırlığı (w)	Değeri (v)	Değer/Ağırlık
1	4kg	40 TL	10
2	7kg	42 TL	6
3	5kg	25 TL	5
4	3kg	12 TL	4

Elimizde sadece 10kg alabilecek bir torbamız olduğunu düşünelim. Bu durumda en yüksek doldurma değerimiz, yani en pahalı şekilde bu torbayı nasıl doldurabiliriz?

Yukarıda verilen değerler çerçevesinde bir karar ağacı oluşturacağız. Önce problemin çözümünü verip ardından açıklamak istiyorum:

Şekildeki kök düğümünden başlayarak diğer düğümleri dolaşmak istiyor olalım. Dallanma ve sınırlandırma problemi bizim başlangıç düğümünden başlayarak problemi alt paralara bölmemizi söyler (branching). Buna göre kök düğümünden başlandıktan sonra olası 2 ayrı yolu 2 alt problem olarak görebiliriz ve elbette bu alt problemlerin de alt problemleri bulunmaktadır. Yani problemin çözümüne sol veya sağ düğümünden devam edilmesi alt problemlerdir. Burada problemi parçalara bölerek bir dallanma elde ediyoruz. Genelde problemin bu aşamasında özyineli (recursive) bir yaklaşım izlenir.

Hemen bu noktada önemli bir durumu belirtmek istiyorum. Dallanma ve sınırlandırma (Branch and bound) algoritmalarının çok benzediği bir yaklaşım da geri izleme (bactracking) algoritmalarıdır. Aynen geri izleme algoritmalarında olduğu gibi bir yoldan başlanır başarıya ulaşılamazsa farklı bir yola girilir ve arama işleminin en son başarılı olduğu yerden herşey devam eder. Ancak dallanma ve sınırlandırma algoritmaları, geri izleme algoritmalarında olduğu gibi bize belirli bir yolu dikte etmez. Yani sığ öncelikli arama (breadth first search) veya derin öncelikli arama (depth first search) gibi sistematik olarak nasıl gidileceğini belirten bir yanı yoktur. Bunlardan herhangi birisi kullanılabileceği gibi tamamen başka bir yöntem de seçilebilir.

Gelelim problemin sınırlandırılmasına (bounding). Sınırlandırma sırasında bulunan değer elimizdeki en iyi değerle karşılaştırılır. Şayet daha kötü bir sonuçsa çözüm olma ihtimali yoktur (non-promising) şayet elimizdeki sınırdan iyi bir durumdaysa o zaman çözüm ihtimali olabilir (promising) ve bu şekilde tutulur.

Yukarıda sınırlar için kullanılan ub (upper bound, üst sınır) değerinin hesaplanması aşağıdaki şekildedir:

Buradaki hesaplama işlemi sırasında W, toplam torbanın kapasitesini, w o ana kadar torbadaki eşyaların ağırılğını, vi+1, o anda alınmasına karar verilmeye çalışılan eşyanın değerini ve wi+1 ise o anda alınmasına karar verilmeye çalışılan eşyanın ağırlığını ifade etmektedir.

Diğer bir deyişle elimizdeki torbada, o ana kadar aldığımız eşyaların değerine, yeni eklenen eşyanın kg başına değerini ekliyoruz. Bu yeni eklenen değeri de torbada kalan boş yer ile çarpıyoruz. Bu sayede şayet torbadaki boşyerden daha fazla yer kaplıyorsa eksi değer olarak sisteme etki ediyor. Şayet torbaya sığıyorsa, alınabilecek en değerli eşyanın en fazla yeri kaplamasını istiyoruz.

Örneğin başlangıç durumunu hesaplayalım:

ub = + ( 10 – 0 ) (10TL)= 100 TL

Yani başlangıçta torbamızda elimizde 0 TL değerinde eşya, 0 kg ağırlığında eşya ve en fazla kilogramı 10TL gelebilecek eşya bulunuyor (tablodan görülebilir). Dolayısıyla üst limitimiz 100TL. İddiamız şu an itibariyle 100TL’den daha değerli bir torba doldurma alternatifi olmadığı (üst limit, upper bound) ki bu durum tamamen doğrudur.

Diyelim ki ilk ürünü aldık ve ikinci ürüne karar vermek istiyoruz. Bu durumda formülümüz aşağıdaki şekilde olacak:

40 TL + (10-4) * 6 = 76

Yukarıdaki hesapta, 40 TL ilk ürünün alınmış değeridir. Bu değerin üzerine, ikinci ürün için torbamızda kalan yer ile ikinci ürünün değerinin çarpımı eklenerek 76 sonucu bulunmuştur. Demek ki iki ürünü alırsak torbanın değeri 76 olacak. Peki şimdi de ilk ürünün alınmaması durumunu görelim:

0 + (10 – 0 ) * 6 = 60

Burada ilk ürün alınmayacaksa, zaten elimizdeki torbadaki ürünlerin değeri 0 olacağına göre 10 kg boş yerimizi elimizdeki alınabilecek en yüksek değer ile çarpıyoruz ( bir önceki adımdan farklı olarak ilk ürünü artık alamayacağımız için en yüksek değer 6 olmuştur).

Yukarıdaki hesaplamalar, üst limitleri belirtiyor. Bu üst limitlerin yanında ağacımızda o ana kadar alının ürünlerin toplam değeri ve ağırlığıda tutulmaktadır. Bazı durumlarda toplam ağırlık kapasitemizi aştığı için ve problem 0-1 torba problemi olduğu için mümkün olmayan durumlarla karşılaşılmıştır.

Netice olarak 1 ve 3 numaralı eşyaları alıp 2 ve 4 numaralı eşyaları almazsak en yüksek torba değerine ulaşılmış olunur.

Ağacın oluşturulması sırasında, önce sol tarafı oluşturmaya çalıştım. Bu sırada 8 numaralı düğüme (node) kadar ulaşmış oldum. Bu değere ulaştıktan sonra kökten ayrılan sağ tarafın hesaplanması, daha fazla hesaba gerek kalmadan budama (prunning) yapılmasını sağlıyor çünkü elimizdeki limitten daha kötü bir üst limit elde ediyoruz. Yani 8 numaralı düğümde torba değerimizi 65 olarak hesapladık. 2 numaralı düğümde ise üst limiti (alınabilecek en yüksek değeri) 60 olarak bulduk. Demek ki bu düğümün altında, 60’dan daha büyük bir değer olamaz. O halde bu düğümün altındaki hiçbir düğümün hesaplanmasının anlamı yoktur çünkü bütün ihtimaller daha kötü olacaktır.

İşte yukarıdaki son paragraf dallanma ve sınırlandırma (Branch and bounding) yaklaşımının özünü oluşturur.

ve Videomuz

Brute Force algoritması

Brute force algoritması

PEKİ NEDİR?

Brute force algoritması daha çok şifre kırmaya yarayan temelinde karakterleri tek tek deneyerek
bulan bir algoritmadır.Yani bir karakteri kırmak için 0 -255 karakter aralığını taraması gerekmektedir.
Kırılacak şifrenin uzunluğu artıkça 0-255 karakter permütasyonu da giderek artar ve çok uzun sürebilir.

ÖRNEĞİN ;

Elimizde ”SAMET” stringi olsun ve bunu aşağıdaki stringin içinde arayalım
SAETMSASAMETMTETESE gibi bir stringin içinde varmı yok mu bakalım.İlk olarak yapmamız gereken
ilk karakterden itibaren bizim aradığımız şifreye uyuyor mu yoksa uymuyor mu şimdi bakalım
SAETMSASAMETMTETESE
1.deneme:
İlk karakter S ile başlıyor,bu tutuyor.2. karakter A bu da tutuyor.3. karakter E olduğu için şimdi 2. Karakterden itibaren aramaya başlıyoruz.
2.deneme:İlk A ile başladığı için bunu da geçiyoruz.
3.deneme:İlk karakter E olduğu için burada da yoktur.
4.Deneme: İlk karakter T olduğu için burada da yoktur.
5.Deneme: İlk karakter M olduğu için burada da yoktur.
6. deneme: S ile başlıyor bu tutuyor sonraki karakter A bu da tutuyor fakat bir sonraki karakter S olduğu için bu adımı da geçiyoruz.
7.deneme: İlk karakter A olduğu için burada da yoktur.
8.deneme :ilk karakter S ile başlıyor sonra A ile devam ediyor bunarlın ikisi de tutuyor.3. karakterlerde
tutuyor.4. ve 5. Karakterlerde tuttuğu için şifremizi 8.denemede bulmuş olduk.Fakat işlem devam eder
ancak bundan sonra sizinde göreceğiniz gibi SAMET stringi aranılan string içerisinde yoktur

Ve anlamayanlar için
Videomuz

https://www.youtube.com/watch?v=xRVpT-7c0Rw

C kodumuz

Ve program cıktısı

Java kodumuz ve örneğimiz

 C KODUMUZ

VE PROGRAM CIKTISI 

Java kodumuz ve örneğimiz

Aranan kelimemiz : bilgi

Aranan metin: bilgisayarkavramlari

Olarak veriliyor olsun. Bu durumda algoritma ilk harften başlayarak “bilgi” kelimesini aranan metin içerisinde bulmaya çalışacaktır.

Öncelikle ilk harften başlanarak harfler karşılaştırılıyor. Aranan kelimenin ilk harfi “b” olduğu için bu harf bulunana kadar arama işlemi devam ediyor:

“b” harfi ile başlayan bir yer bulundu. Artık diğer harfler karşılaştırılabilir. Sırasıyla “I”,”L”.. harfleri karşılaştırılıyor ve harfler tuttuğu sürece karşılaştırma işlemi devam ediyor. Şayet harflerden birisi beklenen sırada gelmezse karşılaştırma işlemi kesilip kalınan yerden devam ediliyor.

Aslında bu harflere bakılmış olmasına rağmen yine de aranıyor. Malum kaba kuvvet arama algoritması akıllı bir algoritma değildir ve bütün ihtimalleri dener. Dolayısıyla aslında bakmış olduğumu ve bakılmasının bir anlamı olmayan bu harflere de bu algoritma kapsamında bakılıyor.

Algoritma Nedir? ve Algoritma Çeşitleri

Algoritma genel anlamda matematiksel işlem olan mantık konusuna ait bir terim olarak tanımlanır. Tam olarak amacı ise yapılan bir işin doğru olarak yapılabilmesi için izlenmesi gereken adım sırasıdır. Aslında insanlar yaptıkları tüm işleri bir algoritma sırası ile mantıklı hale getirir. Eğer yapılan bir işte algoritmik sıra yok veya izlenmiyorsa yapılan işin sonu büyük bir ihtimalle iyi bitmeyecektir. Bundan dolayı eğer bir mühendislik veya matematik dalına ait bir meslek seçmişseniz dolaylı yada dolaysız ilk göreceğiniz konulardan biri de algoritma ve algoritma çeşitleridir.Algoritma nedir? sorusunun tam olarak cevaplanması için belkide bir örneği başvurulması en doğrusudur. Bundan dolayı aşağıdaki örneği incelemek sizin açınızdan önemli olacağını düşünmekteyim.

Bir mühendislik çalışmasında yapılacak ilk işlem işin algoritmasını (işlem sırasını) çıkarmak olacaktır. Bu yüzden matematik mühendisliği gibi meslek gurupları ortaya çıkmıştır. Mühendislikte nasıl uygulandığını anlamak için şu örneği inceleyin.

Öyle bir makine yapılacak ki start düğmesine basıldığında çalışacak, stop düğmesine basıldığında duracak ve bir insan makine alanında tehlikeli bir bölgeye girerse kendisini otomatik olarak durduracak.

İşte böyle bir uygulamada ilk önce işlem sırası oluşturulursa makine için gerekli malzemeler, nasıl çalışacağı, nasıl bir yol izlemesi gerekir gibi pek çok sorunu tespit edilir ve doğru işlemleri sırasıyla uygulanabilir. Aksi taktirde makine yapılırken sürekli yeni şeyler eklemek yada çıkarmak durumunda kalınabilir. Hatta bu süreç tüm işin baştan masa üstünde tartışılmasını gerektirebilir. Bu makinenin algoritmasını grafiksel olarak basitçe hazırlayalım.

Yukarıda basit bir algoritma örneği verdikten sonra tekrardan yolumuza devam edelim.Algoritma sistemleri mühendislik alanında en çok yazılımcılar tarafından kullanılır. Eğer bir yazılım uygulamasına algoritma oluşturmadan başlarsanız yaptığınız işlemlerin bir çoğu boşa gidebilir ve saatlerinizi boş boşuna harcamış olursunuz. Artık bu kısımdan sonra algoritma temelleri vealgoritma örnekleri ile devam edeceğiz.

Programlamada Algoritma Temelleri

Eğer bir program geliştirmeye karar verdiyseniz başarılı bir başlangıç ve mutlu bir son için sırayla şu adımları izlemeniz en doğrusu olacaktır.

Değişkenleri Belirleme

Programın akışı için dışarıdan girdi olarak alınacak verilerin tamamını belirlemek gerekir. Bu sayede programın temelleri oluşturulmuş olur. Değişkenler programın çalışmasını etkileyen en temel bileşenlerdir. Bundan dolayı başarılı bir şekilde değişkenleri belirlemek oldukça önemlidir.

Algoritma Oluşturma

Tüm değişkenleri belirledikten sonra yapılması gereken adım tabi ki de onları doğru şekilde sıralamak olmalıdır. Yukarıda zaten algoritmayı uzunca bir şekilde anlattım. Yapılacak olan işlemleri doğru bir şekilde sıralamak algoritma oluşturmak için yeterli olacaktır. Algoritma oluşturulurken basit ve  problemi en kısa yoldan çözüme ulaştırması için çalışılmalıdır.

Akış Diyagramı

Yukarıda verdiğim makine örneğinde zaten bir akış diyagramı oluşturmuştum. Akış diyagramı, yapılacak olan işin algoritması çıkarıldıktan sonra şema gurupları ile gösterilmesidir. Oluşturulan akış diyagramı ile karmaşık algoritmalar görselleştirildiği gibi mühendislikle pek ilişkisi olmayan insanlar içinde anlaşılır hale getirilir.

Akış Diyagramı Sembolleri

Akış diagramı oluşturulurken kullanılan sembollerin standart geometrik şekilleri vardır. Bu şekiller yardımı ile işlemler anlaşılabilir. Aşağıda paylaştığım görselde akış diyagramı oluştururken kullanılan sembolleri görebilirsiniz.

Algoritma Örnekleri

Yazı boyunca belli başlı örnek algoritma işlemleri gösterdim. Bu bölümde ise aşağıda paylaştığım örneğin algoritmasını (işlem sırasını) çıkaracağım ve sonrasında akış diyagramını çizerek yapılması planlanan bir programın nasıl hazırlanacağını göstereceğim. Örnek olarak ise daha önceki yazılarımdan birinde anlattığım C# faktöriyel hesaplama programının algoritmasını hazırlayarak yapacağım.

Soru: K!/L!(K-L)! işleminin kusursuz bir şekilde çalıştıracak bir algoritma hazırladıktan sonra akış diyagramı ile gösterin.

Akış diyagramından önce bir algoritma hazırlamak gerektiğinden yukarıda bahsetmiştim. Bu algoritma sırası hazırlanırken işlemler genellikle A0,A1,A2… gibi yada 1.İşlem, 2.İşlem,3.İşlem… gibi isimlerle sınıflandırılırlar. Ben A0,A1… yapısını genellikle kullanmayı tercih ettiğimden bu yazıda bu şekilde kullanacağım.

Örneğin Algoritma Sırası

A0 → Başla
A1 → K değerini 1 yap
A2 → L değerini 1 yap
A3 → K değeri ne girildi?
A4 → L değeri ne girildi?
A5 → K!/L!(K-L)! işlemini yap
A6 → Pay paydadan büyük mü?
A7 → büyükse uyarı mesajı gönder
A8 → değilse sonucu yaz.
A9 → Dur

Örnek Akış Diyagramı

Akış diyagramının aşağıda çizilmiş resmini görebilirsiniz. Bu çizimi Photoshop, eDraw hatta AutoCad gibi çizim programlarıyla yapabilirsiniz. Eğer çok yetenekli biriyseniz Paint programını bile deneyebilirsiniz  Yada en basitinden bir kağıt ve kalem kullanarak hazırlamayı deneyebilirsiniz.

Algoritma Çeşitleri

Yazının başında belirttiğim gibi son bölümde algoritma çeşitleri hakkında olacak. Gerçek anlamda algoritma çeşitleri aslında her program uygulaması için farklı bir algoritma çeşidi keşfedilebilir. Fakat ihtiyaçlar doğrultusunda geliştirilmiş bazı algoritma çeşitleri vardır ki bunları tekrar tekrar yazmak tam anlamıyla Amerikayı tekrar keşfetme çıkmakla eşdeğerdir.

Algoritma işleri ile en çok uğraşan şirket büyük bir ihtimalle Google diye tahmin ediyorum. Çünkü eğer arama işi benim işim diyorsan algoritma işi de benimdir diyebilmen lazım belkide Google’u bu kadar başarılı kılan faktör de budur. Şuan Google arama motorunda arama faktörünü etkileyen 200 den fazla algoritma olduğu söyleniyor.

Arama Algoritmaları

Adında anlaşılacağı üzere dijital sistemlerde arama yapılmak istendiğinde kullanılabilecek algoritma çeşididir. Listeler, şekiller ve metinleri üzerinde arama yapılmasını sağlar. Yaygın olarak kullanılan arama algoritmaları şunlardır; ikili arama algoritması, enine arama algoritması,derin öncelikli arama algoritmalarıdır.

Genetik Algoritmaları

Yapay zeka sistemlerinde sık kullanılan bir algoritma çeşididir. Genetik bilindiği üzere insanın biyolojik yapısını inceleyen bilim dalıdır. Genetik algoritma ismini genetik bilimine benzer bir yapıda çalıştığından dolayı almıştır. Bu algoritma genellikle yer bulma işlemlerinde kullanılır. Çalışma mantığı ise sanal genler oluşturulur. Sonrasında bu genlerin mutasyonu sonucu en kaliteli sonuçlara ulaşılmasını sağlamaktır. Bu konu ile ilgili yapay zeka algoritmaları adlı yazıyı okumanızı tavsiye ederim.

Kriptografik Algoritmalar

Şifreleme amaçlı kullanılan algoritma çeşitleridir. Bu algoritma tipi sayesiyle dosyaların güvenliği sağlanabilir. Temel çalışma yapısı kullanıcı tarafından şifreleme yapılır ve dosya açılmak istendiği zaman oluşturulan şifre bilinmiyorsa içerideki bilgilere ulaşılamaz.

Kök Bulma Algoritmaları

Matematik konusu olan kök işlemleri üzerine çalışan algoritma türüdür. x olarak tanımlı bilinmeyen denklemleri kök bulma algoritma yardımı ile çözebilirsiniz.

Sıralama Algoritmaları

Alfabatik yada sayısal sıralama yapmak için kullanılan algoritma türüdür. Sürekli geliştirilmeye açık bir algoritma türüdür. Sıralama işleminin başarılı ve düzgün bir şekilde yapılması için oldukça önemlidir. Bu işlemi karşılaştırma yaparak yapmaktadır. Yani 1 ile 2 yi büyüklüğe göre sıralayacak olursak 2>1 şeklinde yaparız. Sıralama algoritması bu mantıkla sıralama yapmakta fakat bu kadar basit amaçlar için kullanılmamaktadır.

Diğer Algoritma Çeşitleri

Konunun başında bahsedildiği gibi algoritma çeşitleri 3 veya 4 türe ayrılabilecek kadar basit değildir. Ben algoritma çeşiti olarak burada en sık kullanılanlara biraz değinmeye çalıştım. Fakat hepsini teker teker bir yazı olarak yazılsa anca yeterli gelirdi. Bundan dolayı burada kısa keserek Wikipedia sitesinde yer alan algoritma başlığı altında diğer algoritma türlerini incelemenizi tavsiye ediyorum.

Bu algoritmaların tercih edilmesindeki sebepleri anlamaya çalışıyorsanız kısaca şunu diyebilirim. Yazının hemen başında dediğim gibi algoritma oluşturmanın temel amacı basit ve problemi en kısa yoldan çözmek olduğunu söylemiştim. Yukarıda verdiğim tüm bu algoritma çeşitleri bu işi en iyi şekilde yapabilen algoritmalar olduğu için bu algoritma çeşitleri kullanılmaktadır.