Monthly Archives: March 2010

Greedy algoritmalar …, Böl. 2: Bağlı Bileşen Etiketleme


Önceki bölümde Kruskal Algoritması ile “Minimum Spanning Tree” bulurken;
1. Çözümü oluşturan küçük bileşenleri en iyiden en kötüye sıralamıştık.
2. Çözümü oluşturmak üzere birleştirmeye başlamıştık.

Bu yazıda birleştirme kuralı üzerinde duracağım:
En iyi parçaları alıp en az ağırlıklı ağacı oluştururken, birden fazla küçük ağaçlar(fidanlar 🙂 ) oluşacaktır.

Bu oluşumu takip edebilmek için, graftan aldığımız her yeni kenarı, var olan ağaçlar içinde ait olduğu ağacın etiketiyle etiketlemeliyiz. Yani o ağaca birleştirmeliyiz.

Başlangıçta, ilk aldığımız ağaç, herhangi bir ağaca ait olmayacağı için buna bir etiket verilir. Mesela 1. Ağaç denir. Daha sonra farklı bir ağaç oluştuğunda ona sırayla yeni numaralar verilerek farklı ağaç olduğu etiketlenir. Burada farklı bir ağaçtan kastettiğim şey, yeni eklenen kenarın var olan bir ağacın devamı olmayıp, ayrık olmasıdır.

Oluşan farklı ağaçları birleştirirken, graftan yeni alınan kenarın(ağacın);

  • var olan bir ağacın devamı,
  • iki farklı ağacı birleştirdiği,

kriterlerine bakarız.
Bu durumlar oluştuğunda, ağaçlar birleştirilir. Yani, farklı iki etiket, tek etiketle ifade edilir.

Bu etiketleme işleminin mantığı, aynı özellikte olan ve birbirine bağlı bileşenlerin bir grupta ifade edilmesidir. Bu işleme “Bağlı Bileşen Etiketleme” (Connected Component Labeling) adı verilir.

Bu yöntemin uygulanmasıyla döngü oluşmadan “min. spanning tree” oluşması sağlanır.

Sonuç:

“Greedy” algoritmaları bir anlamda “Recursive” algoritmalara benzetebiliriz.
Bir durma koşulu olması kaydıyla, temel bir işlem tekrar eder.

-- The End --

Copyright © 2010 – Taha Yavuz Bodur

Leave a comment

Filed under Algoritmalar

“Greedy” algoritmalar ve bir örnek: Kruskal Algoritması Böl.1


Elimizde bir problemin çeşitli olası çözümlerini içeren ve parçalayabileceğimiz bir çözüm uzayı olsun. Burada en iyi çözümü arayalım.

Burada ‘Greedy’ algoritma mantığına göre;
en iyi çözüm, bu çözümün büyüklüğünü oluşturacak sayıda iyi küçük parçaların birleşiminden oluşacaktır. Dolayısıyla çözüm kümesi parçalara ayrılır ve parçalar kendi arasında bir büyüklük/önemlilik/iyilik kriterine göre sıralanır. En iyi parçadan başlanarak, çözüm kendiliğinden oluşuncaya kadar iyilik sırasına göre yeni parça seçilir. Burada en iyiden başlayarak çözüm oluşuncaya kadar sürekli iyi parçaları seçtiğimiz için, bulunan çözüm en iyi çözüm olacaktır.

Burada temel prensip aşağıdaki cümlede özetlenmiştir:

A locally optimal choice is globally optimal.

Bu mantığı bir örnek algoritma üzerinde göstererek görselleştirelim.
Kruskal Algoritması, ‘Greedy’ seçim yöntemiyle Min. Spanning Tree bulan bir algoritmadır.

Problem:


Bir G(V,E) ağırlıklı grafı verilsin,
burada V={1,2,3,4} ve E={(1,2),(2,3),(2,4),(1,3),(3,4),(1,4)} olsun.
w=(u,v) olmak üzere, bu kenarların ağırlıkları sırasıyla,
W={5,15,30,20,10,25} olsun.

G(V,E) grafı şu şekildedir.

Bu graftan bir “Spanning Tree” elde etmek isteyelim.
Spanning Tree, bir grafın tüm düğümlerini içeren bir ağaçtır. Yani döngü yoktur ve tüm düğümlerden bir şekilde geçilir.

Eğer bu graftan bir Minimum Spanning Tree bulmak istiyorsak… (bu Spanning Tree’ lerden en az ağırlıklı olanı demektir.)

Bu grafta birden fazla farklı Spanning Tree çıkabilir:
1-2-3-4 ya da 1-2-4-3 gibi…
Bu farklı Spanning Tree’ ler bizim çözüm uzayımızı oluştursun. Buradaki en iyi çözüm min. spanning tree olacaktır.

En iyi çözümden bahsedildiği için ve çözümler parçalanabildiği için Burada Greedy Algoritma yöntemini kullanalım.

Çözüm kümesini yapıtaşlarına ayıralım.
Çözüm Kümesi : Verilen Graftaki Ağaçlar
Burada sorun, “en küçük yapıtaşı ne olarak seçilmeli ?” olacaktır.
Buna şöyle karar verilir:

Aranan çözüm: Bir ağaç.(Çözüm kümesini biraz küçüklttük)
Bir ağaç küçük ağaçlardan oluşur.( Daha da küçüklttük, Ne kadar küçük?)
Problemde Min. diye bahsedilen şey kenar ağırlıklarının min. olması.
O zaman en küçük yapıtaşı en azından bir kenar ağırlığı(iyilik kriteri) olan bir ağaç olmalı.

Dolayısıyla yapıtaşı bir kenar olarak bulunur. Yani,
wi = (ui,vi), i=1,2,3,4 olacaktır.

Min. Spanning Tree(MST) ağırlığı:

Burada n düğüm sayısıdır. Dolayısıyla bir spanning tree de (n-1) kenar vardır.
Burada kenarlar ağırlıklarına göre sıralanmıştır. i, bu sırayı gösterir.

Burada, genel çözüme uğraşmak için bu küçük parçalara bir birleşme kuralı koymalıyız ki ana ağaca oluşabilsin.

Bunu bu yazının 2. Bölümü olan Connected Component Labeling(Bağlı Bileşen Etiketleme) kısmında açıklayacağım.

Not-1: Bazı arkadaşlar, madem ki blogunda teknik konularda ingilizce yazacaktın, neden bunu Türkçe yazdın diyebilir. Bunu diğer bazı arkadaşlar neden teknik konularda İngilizce yazıyorsun dediği için yaptım. Ama, bunun İngilizce halini de farklı bir kategoride yayına koyacağım ;).

Not-2: Copyright © 2010 – Taha Yavuz Bodur

Leave a comment

Filed under Algoritmalar

C kökenli dillerde indisler neden sıfırdan başlar ?


Pascal vb. programlama dilleriyle uzun süre uğraşmış kişiler C kökenli programlama dillerinde dizi indislerinin 0’dan başlamasına anlam veremezler ve bunu gereksizlik olarak görürler. Böyle iki farklı şeklin oluşmasının sebebi şu iki farklı gösterim biçimi kullanılmasından kaynaklanır:

  • Sıraya göre gösterim
  • Konuma göre gösterim

Günlük hayatta kullandığımız sıralı gösterim yönteminde, içerisinde bir hacim olan varlıklar tek bir sayıyla gösterilerek sayılır. Bellekteki herhangi bir tamsayı da bir hacim kaplar.
Eğer bu alana bellekteki 1. alan dersek, bu sıraya göre gösterimdir. Eğer, 1. alanın nereden başladığını soracak olursak, bu da konuma göre gösterimdir.

C dilinde açılmış dizilerde elemanlar 1 birim kabul edilir. Elemanın indisi olarak olarak bu birimin başlangıcı seçilir. Dolayısıyla 1. elemanın konumu 0 kabul edilir. Bu durumda [0-1) birim’lik alan 1. yerdir. Bu 1. yer, [0-1) birim arası tüm uzayın ifade edilme şeklidir.
Yani C’ de konuma göre gösterim yapıyoruz.

Konum gösterimini çoğu zaman farketmeden sıralı gösterime çeviririz.
Bu dönüşümün doğal olarak yapıldığını şuradan farkettim:
Çoğu zaman elimizdeki bir kağıda hızlıca, 5 gözlü bir dizi çizmek istediğimizde;
önce dikdörtgenin dış hatlarını çizip, sonra soldan itibaren belli aralıklara bölerek gidersek, son göz eksik kalabilmekte ya da fazla olabilmektedir. En azından kontrol amaçlı kaç tane göz oluşturduğumuzu sayarız. Bunun sebebi, hızlıca çizerken bazen gözleri bazen de çizgileri saymamızdır.

Bu konu için, matrisleri eşit uzunlukta gruplanmış sayı dizileri olarak düşünelim.
Aşağıdaki matrisler 7’şerli olarak gruplanmış 4 adet sayı dizisi gösterir.

Elimizde eşit uzunlukta gruplanmış sayı dizileri varsa, sayıların yerlerini göstermek için sıralı gösterim yerine konum gösterimi kullanmak bence daha anlaşılır olacaktır.

Şöyle bir senaryo düşünelim
Bir okulda 4 kat var ve her bir katta da 7 tane derslik var.
Her bir dersliğe ilk kattan başlanarak sırayla derslik numarası verilmiş durumdadır.
Yani şu durumda bir dersliğin okulun kaçıncı dersliği olduğu söylenebilir.

Herhangi bir dersliğin,bulunduğu katın kaçıncı dersliği olduğunu bulmak istersek;
Burada katlar eşit uzunluklu sayı grupları olarak düşünülebilir.

i: kat numarası (1,2,…,4)
j: dersliğin bulunduğu katta baştan itibaren kaçıncı derslik olduğu (1,2,…7)
sn: dersliğin genel sıra numarası (1,2,3…,28)

j= (sn-1) MOD 7 // 0,1,2,3,4,5,6
burada sn sıralı gösterimdir.
(sn-1) MOD 7 ile konum gösteren temsil şekline geçildi.

bu ifadeye eklenen +1, ile sayı gösteren temsil şekline geçilir.
j=((sn-1) MOD 7) +1 // 1,2,3,4,5,6,7

Örnek: Yukarıda, soldaki matris için. (Sıralı Gösterim)
28. Eleman:
(28-1) / 7 + 1 = 4. satır (Sıralı gösterim)
(28-1) MOD 7 + 1 = 7. sütun

1. Eleman:
(1-1) / 7 + 1 = 1. Satır
(1-1) MOD 7 + 1 = 1. Sütun

Bu işlem C dilinde kodlanmış olsaydı,
+1 kullanılmayacaktı. Çünkü, burada +1 ile konum gösteriminden sıralı gösterime geçiliyor.
Ayrıca,
sn dizisi de 0 dan başlamış olsaydı -1 kullanılmayacaktı. Burada sıralı gösterimden konum gösterimine geçilmiş olacaktı.

Copyright © 2010 – Taha Yavuz Bodur
Not: Burada sıralı gösterim ve konum gösterimi benim koyduğum tabirlerdir.
Not – 2: Bu yazı herhangi bir kaynağa bakılmadan hazırlanmıştır. Dolayısıyla, bu yazıda yazdıklarımın hiçbirinin doğruluğunu iddia etmiyorum. Bu nedenle yoruma açıktır.

Leave a comment

Filed under Life

Books that influenced me most


Currently it is Thinking Recursively by Eric Roberts.

I have found it at Amazon.com and have tried to buy ,but i couldn’t because of the sellers who say we do not support sending to your country. After that i have tried to find a digital copy. I could find a .djvu format copy, but to view that you must have a djvu viewer which is old-fashioned and not handy, so i am still searching some alternative ways to read this book comfortably.

In this book i have found this quote interesting:

To iterate is human, to recurse is devine.

I think that is truly right, and explains why it’s hard to think recursively.

Others are these books:

Leave a comment

Filed under Inspiration

About the Main Theme of This Blog


What we are talking about is the doctrines of George Polya.

His book How to Solve It (1945) is interesting. It is a small volume describing methods of problem solving.
When i was reading the article about this book at wiki, i read his quotes again and again.
I believe that he knows how to think, so inspired by most of scientists.

Who has influenced by him:

  • His has been translated into several languages and has sold over a million copies, and has been continuously in print since its first publication.
  • Marvin Minsky said in his influential paper Steps Toward Artificial Intelligence that “everyone should know the work of George Pólya on how to solve problems.”
  • Pólya’s book has had a large influence on mathematics textbooks as evidenced by the bibliographies for mathematics education.
  • Russian physicist Zhores I. Alfyorov, (Nobel laureate in 2000) praised it, saying he was very pleased with Pólya’s famous book.
  • Russian inventor Genrich Altshuller developed an elaborate set of methods for problem solving known as TRIZ, which in many aspects reproduces or parallels Pólya’s work.

Here, one person to notice carefully is Marvin Minsky.
Lots of great scientists inspired by him.
For example, Isaac Asimov

described Minsky as one of only two people he would admit were more intelligent than he was, the other being Carl Sagan.

I like one of his conversations very much. That is:

In the days when Sussman was a novice, Minsky once came to him as he sat hacking at the PDP-6.
“What are you doing?” asked Minsky.
“I am training a randomly wired neural net to play Tic-tac-toe,” Sussman replied.
“Why is the net wired randomly?”, asked Minsky.
“I do not want it to have any preconceptions of how to play,” Sussman said.
Minsky then shut his eyes.
“Why do you close your eyes?” Sussman asked his teacher.
“So that the room will be empty.”
At that moment, Sussman was enlightened.

Minsky is the co-founder of MIT Computer Science and Artificial Intelligence Laboratory. This lab had great talents and still has.

Terry Winograd is one of them. He wrote SHRDLU was written as a PhD thesis at MIT in the years from 1968-70. This program is inspired by so many computer scientists.

Starting in 1995, Winograd served as adviser to Stanford PhD student Larry Page, who was working on a research project involving web search. In 1998, Page took a leave of absence from Stanford to co-found Google.

In computer science perspective, there is an exponential increase after Polya.
Especially these scientists i mentioned have one common thing, that is they were related to Marvin Minsky in some way. Marvin Minsky was influenced by Polya. It seems also others. :))

Leave a comment

Filed under Life