Roma Sapienza Üniversitesi yüksek lisans başvuru süreci

Merhabalar,
Sapienza üniversitesi Bilgisayar Bilimi 2 yıllık İngilizce yüksek lisans programına başvuru yaptım ve kabul aldım. Süreç boyunca yeterli bilgi bulamadım, yeterli desteği ne okuldan ne konsolosluktan göremedim. O sebepten bu blogu yazmaya karar verdim ki başkaları da ruh hastası olmasın :).


BAŞVURU İŞLEMLERİ
Tek yapmanız gereken linkini verdiğim sayfaya kayıt olmak ve online ön başvuru formunu doldurmak.

http://en.uniroma1.it/node/13540

Ön başvuru için neler lazım:
1. Akademik Özgeçmiş
2. Diploma
3. İngilizce belgesi ( Eğer lisansınızı %100 ingilizce okuduysanız Sapienza üniversitesi buna dair bir belgeyi de kabul ediyor.)
4. Kimlik
5. Pasaport
6. Referans mektubu
7. Transkript

Bunların elektronik halleri yeterli oluyor. Yalnız ben sıkıntı olmaması için transkriptimi okuldan onaylı aldım, onu taratıp yükledim siteye. Başvurular bu yıl Nisan ayı sonunda kapandı.

DENKLİK İŞLEMLERİ
Haziran ayında başvurumun kabul edildiğine dair bir mail aldım. Mailin ekinde konsolosluğa başvurmam için okulun kabul mektubu yer alıyordu.

Ön kayıt(denklik olarak da geçiyor) işlemleri için aşağıdaki sayfada belirtilen belgeleri İtalyan Konsolosluğuna teslim etmeniz gerekiyor.
http://www.consistanbul.esteri.it/consolato_istanbul/tr/i_servizi/per_i_cittadini/studi/universita/univ-specialistica.html

Sitede yazan numarayı arayıp randevu almanız gerekiyor. Bana 4 gün sonrasına randevu vermişlerdi. Son günlere bırakmamaya çalışın. Evraklarınız eksik ise sonradan tamamlayabiliyorsunuz panik yapmayın.

Evrak Toplarken Dikkat Edilmesi Gerekenler

1.  DİPLOMANIZA ÖNCE KAYMAKAMLIKTAN APOSTİL YAPTIRIN.
(DİKKAT!! Tercüman ve noterden önce kaymakamlıktan apostil yaptırılacak, aksi durumda çevirilen ve notere onaylatılan belgeler yalan oluyor. Bir dünya para boşa gidiyor. Malesef sitede bu sıranın önemli olduğu belirtilmemiş!! Apostil işlemi ücretsiz.)

2. YEMİNLİ TERCÜMANDAN DİPLOMANIZI (APOSTİL İLE BERABER) İTALYANCA'YA ÇEVİRTİN. 

3. NOTER ONAYI YAPTIRIN. (Bilmeyenler için her yeminli tercüman sadece bir notere bağlıdır. Fiyat isterken noter onayı dahil fiyat isteyin. Tercüme fiyatının ucuz olmasına kanmayın. Özellikle Taksim, Beşiktaş buralardan uzak durun derim. Noter fiyatları noterin yerine göre değişiyor!)

4. İTALYANCA TERCÜMESİNE TEKRARDAN KAYMAKAMLIKTAN APOSTİL YAPTIRIN.

5. TRANSKRİPT İÇİN DE AYNI İŞLEMLERİ AYNI SIRAYLA UYGULAYIN.
(DİKKAT!! Kabul aldığınız bölüm ingilizce ise ve transkriptiniz de ingilizce ise italyaca'ya çevirtmenize gerek yok. Kendisini ingilizce haliyle kabul ediyorlar.)

(Sitede yazan bütün evraklar ve bir kopyaları isteniyor. )


Konsolosluk sayfasındaki Başvuru Formu nasıl doldurulur

Konsolosluğa evrakları teslim etmeye gittiğinizde panoda başvuru formu ve Modello A Formunun nasıl doldurulacağına dair örnek var. İsterseniz formları boş götürüp orada doldurabilirsiniz (İkişer kopya). Ben aklımda kalan kısımları yazdım. Formlara imza atmayın teslim ederken atmanızı istiyorlar. Eksik evrakları dert etmeyin sonra tamamlayabiliyorsunuz. Herkese iyi şanslar :).

KIBRIS

  Bu haftasonu Kıbrıstaydık. İlk defa gördüm. Çok beğendim. Kıbrısta en bilindik 3 nokta: Gazimağosa , Lefkoşa, Girne. Bunun dışında illaki vardır başka gezilecek popüler olmayan yerleri. Detaylı bir araştırma yapmadım açıkçası.

  Uçağımızdan indik. İlk hedefimiz Magosa. Taksicilere fiyat sorduk. 150 lira fiyat verdiler , yardımcı oluruz dediler. Biz Kıbhas'a yöneldik. Saat başı otobüs varmış. Kişi başı 15 lira idi galiba. 1 saatlik bir yolculuğun sonunda vardık. Yolculuğumuz boyunca neler gördük. Dümdüz bir ova. Yer yer müstakil evler mevcut. Uzakta Beş parmak dağları. İndiğimiz yeri tam hatırlamıyorum. Ordan sur içine gitmek için taksiye bindik , 15 lira tuttu. İndiğimiz yerden merkez yaklaşık 2 km. Eşyamız çok olduğu için biz taksiyi tercih ettik ama yürünedebilir. Taksi bizi  Lala Mustafa Paşa Camiinde indirdi. Öncelikle karnımızı doyurmak istedik. Camiden yukarıya doğru yürüdük. Gözümüze kestirdiğimiz bir yere oturduk. Kıbrıs'a pahalı derler ama İstanbul'a göre uygun bile. Meksika soslu tavuk yedim , 20 lira. Salatası, pilavı, patates kızartması yanında. Bir de ayran içtik. Ordaki ayran Türkiyedeki bilindik markalardan değil. Yemekten sonra etrafı gezmeye başladık. İlk gittiğimiz yer: Nazım Hikmet Zindanı. Ben içine girmedim. Zindanın yanında açık hava çok tatlı bir kafe var. Orada bir sıkma portakal suyu için derim. Sonrasında Lala Mustafa Paşa Camisi var, kiliseden bozma bir cami. Çok ihtişamlı görünüyor. Kıbrısta bu şekilde çok cami var. Bu kiliseler benim gözüme çok hoş göründü. İtalya'da gördüğüm kiliseleri bu kadar beğenmemiştim. Camiyi gördükten sonra aşağı inen yol Petek pastanesine ve kaleye çıkıyor. Petek pastanesi uzun yıllardır var olan bir pastane imiş. O yüzden daha popüler ama çok şirin kafeler var. Petek pastanesi dondurma konusunda iddialı. Ben o denli lezzetli bulmadım. Kıbrısta esas dondurması meşhur olan "Mardo" var. Özelliği tamamen doğal olması ,içinde kıvam artırıcı bulunmaması. Çilekli , sade , çikolatalı , muzlusu var. Muzluyu çok beğendim. Magosada gezebileceğiniz bir de Salamis caddesi var. Kafeler , mağazaların olduğu daha çok öğrencilerin takıldığı bir cadde.  Biz çok ara sokakları gezemedik. Bu yazdıklarımı yapmak zaten 4 saatimizi aldı. Akşam Gazimağosa Orduevinde geçtik. Orduevi kurtarılmış bölgenin içinde kalıyor. Taksi ile geçebiliyorsunuz kurtarılmış bölgeden , yaya olarak geçişe izin vermiyorlar. Ama orduevinde indikten sonra birazcık yürüdük gördük binaları. Hepsi terkedilmiş, yıkılmış, camları kırılmış, bazıları inşaat olarak kalmış. Kumarhaneler, oteller , eğlence mekanları... 50 yıldır bu binalar bu şekilde duruyor. Hayalet şehir gibi. Birkaç binayı değerlendirmişler , subay orduevi ve astsubay orduevi yapmışlar.  Biz subay orduevinde kaldık. Onun da şöyle bir hikayesi var: Bir adam otel olarak yaptırmış. Mısırdan özel Kleopatra kumu getirtmiş. Sonrasında adam öğrenmiş ki o bölge Türklerin eline geçti. En üst kata çıkıp intihar etmiş. İnsan gezerken biraz hüzünleniyor.

Namık Kemal Zindanı

Lala Mustafa Paşa Camii

  2. gün Lefkoşa'daydık. Buraya da bayıldım. Burada gezecek daha çok yer var. Şehrin merkezini turlamanızı sağlayan mavi bir şerit var. Onu takip ettiğiniz zaman sizi gezilecek her yere götürüyor. Şehrin ortasından sınır geçiyor. United Nations a ait tampon bölge var. Bazı yerlerde tampon bölge aşırı daralıyor. Direk telin öteki tarafı Rumların. Sınır parkı var. Orda tam sınırın köşesinde ufak bir kafe var. Ordan rum tarafını izleyerek çay içebilirsiniz. Rum tarafının daha gelişmiş olduğunu söylüyorlar. Rumlar Türk tarafına geçebiliyorlar. Türklerden sadece 1974ten önce Kıbrıs vatandaşı olanlar geçebiliyor.  Hep mavi çizgileri takip edin derim. Sokakları da gezdiriyor. Evler birer antika, bayıldım. Sonrasında çarşıya geçtik. Büyük Hanın içine girdik. Çarşı da Mardo nun yeri var. Dondurmasını deneyin. Alışveriş konusuna gelince çoğu şey Türkiye'den geldiği için Türkiye'ye göre pahalıya satın alırsınız. Tabi hatıralık bir kaç bir şey almak gerekir, misal Kıbrıs Tepsisi :) Büyükdere caddesine geçtik. Butikler , restoranlar , kafeler...

Malesef Girne'ye gidemedim. Kıbrıs'ın en güzel yeri olduğunu söylüyorlar. Gelelim ulaşıma.Kıbrısta ulaşım sıkıltılı. Hele ücra yerlere gidecekseniz , illa taksi kullanmak zorunda kalabiliyorsunuz. Girne , Lefkoşa , Gazimağosa arasında giden servisler var. Yarım saatte bir ya da saatte bir , bazen hiç yok. Gününe göre değişiyor. Taksiyle Gazimağosa Lefkoşa arası yaklaşık 130 , 140 fiyat söylüyorlar. Hava alanına gitmek için KıbHas var. Onları da uçak saatlerine göre ayarlamışlar. Biz 3.10 uçağı için Lefkoşa'dan 12.45te bindik. Bir sonraki 14.15te imiş. 12.45 çok erken 14.15 çok geç. Ulaşım gerçekten çok sıkıntılı. Araba kiralamak uygun. Soldan akan trafikte sürebilirseniz tabi.

Perpective Deformable Model Halcon 12.0

Halcon kullanamaya başlayan herkesin sıkıntısı internette yeteri kadar tartışma bulamaması olsa gerek. Dökümanları baya yararlı ama ilk etapta kavramak mümkün olmayabiliyor. O sebepten yazmaya karar verdim. Halconun eşleme için geniş çözüm önerileri var. Benim senaryomda perfpektif bozulmaları mevcut olduğu için bu modeli seçtim. Öncelikle model oluşturmamız gerekiyor. Kullanacağımız fonksiyon "create_planar_uncalib_deformable_model". Bu fonksiyona logonun resmini veriyoruz. Yada logonun bulunduğu kısma indirgediğimiz görüntüyü de verebiliriz. Ben denemelerim sonucu logo resmi ile daha yüksek başarım yakaladım.
Logonun olduğu bölgeye indirgediğimiz resmin şöyle bir güzelliği var . Logonun işaretlendiği bölgeyi arama yaparken kullanıyor. Aramaya o bölgeden başlıyor. Aramayı hızlandırmış oluyorsunuz. Test edeceğiniz görüntülerde logo aşağı yukarı aynı bölgedeyse bunu kullanmak avantajlı.

Ayarlanması gereken parametreler var
NumLevels : Şeklin piramidi oluşturuluyor. En alt basamakta orijinal boyutta logonun şekli , diğer basamaklarda bir önceki basamaktaki logonun yarısı, bu şekilde devam ediyor. Siz çok yüksek bir sayı girsenizde halcon şeklin anlamlı olduğu son basamağa göre girdiğiniz sayıyı değiştiriyor.

AngleStart, AngleExtent, AngleStep : Rotasyon aralığını ve adım büyüklüğünü belirlemeniz için. Dikkat etmeniz gereken AngleExtend aralığın kaç derece olduğu. Yani rotasyon aralığın -10 , 10 arası yapmak istiyorsanız AngleStart : -10 , AngleExtend : 20 derece olacak.

ScaleRMin, ScaleRMax, ScaleRStep : Benim anladığım ve test ettiğim kadarıyla 2 kullanımı var.
1. Eğer model oluşturmak için kullandığınız logo ile test resimlerindeki logolar yatay ve dikey yönde eşit oranda büyüyor ya da küçülüyorsa bu parametreler test resimlerinde logolar model logonun kaç katı aralığında değişiyor.
2. Yatay ve dikey büyüme eşit değilse satır bazında büyüme aralığı

ScaleCMin, ScaleCMax, ScaleCStep : Sütun bazında büyüme aralığı. Büyüme üstteki parametrenin 1. kısmında anlattığım gibiyse bu değerleri 1 olarak girin.

Optimization : Şeklin az sayıda nokta ya da çok sayıda nokta içermesini ayarlayan parametre

Metric : Logonuzun arkaplan ya da önce plan renkleri değişmiyorsa polarity yi kullanabilirsiniz , Değilse polarity i ignore etmeniz gerekir. Bir başka seçenek değişken polarity.

Contrast : Şeklin kenarlarının kontrastı .

MinContrast : Logo aratılırken şeklin kenarlarının olması beklenen kontrast

Parametreleri ayarlayıp modeli oluşturduktan sonra "inspect_shape_model" ile oluşturulan modeli kontrol etmekte fayda var. Sonraki aşama "find_planar_uncalib_deformable_model" fonksiyonu ile arama yapmak.

Aynı isimli parametrelerin anlamı yukarda yazdıklarımla aynı.

MinScore : Modelin gözükürlüğü. Çok düşük tutmak yanlış yerlerle eşlemesine sebep oluyor. Çok yüksek tutmak logoların bulunamaması ile sonuçlanıyor. Değeri yükseltmek işleme süresinin azarltıyor.

MaxOverlap : Logoların üst üste binebilmesi durumu.

Greediness : Algoritmanın ne kadar aç gözlü davranacağı.

HomMat2D : Homografi matrix

Score : Elde edilen skor

Binary KnapSack - BackTracking

ağırlık	değeri	değer/ağırlık
5	10	2
8	12	1.5
3	3	1

Kapasite : 10

Kapasitesi 10 birim olan çantaya parçalanamayan 3 tane obje yerleştireceksin , hangilerini seçesin ki kazancın maksimum olsun ?

Ağacı oluşturalım:

1 _ _ : 1. objeyi alalım

1 1 _ : 1. ve 2. objeyi alalım

1 0 _ : 1. objeyi alalım , 2. objeyi almayalım

Ağacın yaprakları tüm kombinasyonları gösteriyor. Bunların bazıları imkansız : 

1 1 1 : 3 objeyi de alalım

3 objenin toplam ağırlığı 5 + 8 + 3 = 16 kapasiteyi aşıyor!

Peki 1 1 1 in olanaksız olduğunu daha önceden göremiyor muyuz?

1 1 1 in türediği noda bakalım

1 1 _ : 1.ve 2. objeyi alalım.

2 objenin toplam ağırlığı 13 kapasiteyi aşıyor!

O halde 1 1 _ nodundan daha devam etmeye gerek var mıydı? Hayır. Bu eleme yöntemine olanaksızlık ile budama yöntemi deniyor.

Budama hakkında genel bir bilgi verdikten sonra backtracking le ağaçta nasıl gezeceğimizi görelim. DFS(Depth first search) diye adlandırdığımız derinlik öncelikli arama yöntemi ile gezeceğiz. Yani her noda geldiğimizde önce sol çocuk , sonra sağ çocuk. Yaprağa gelindiğinde ya da gidecek daha fazla yer kalmadığında ebeveyn noda dönülür.

Son haliyle gezme sırası numaralanmıştır:

Başka bir budama yöntemi ise bir noddan devam ettiğinde elde edebileceğin maksimum kazanç şimdiye kadar ulaştığın kazançtan daha yüksek değil ise nodu açmanın bir anlamının olmaması.

Diyelimki 5 numaranın bana getirisinin 15 olduğunu saptadım. (Sayısal değerleri atıyorum) , back trackle 2. noda geri döndün , sağ taraftan devam ediyorsun , 6. noda geldin elde edebileceğin maksimum kazancı hesapladın 14 çıktı , o  zaman o nodu daha fazla açmaya gerek yok , zaten elimde kazancımın 15 olduğu bir çözüm var , 15ten daha yüksek birşey bulursam eğer yeni çözümüm o olur.

Öncelikle üst sınır hesaplamalarında Rational Knapsack kullanabiliriz . (Rational Knapsackten elde edeceğim kazanç her zaman binary knapsackten büyük ya da eşit olacaktır)

Bu ağaç üzerinde inceleyelim:

1 numaralı nodda elde edebileceğimiz maksimum kazanç ne olur ?

Değer/ağırlık değeri en yüksek olan obje 1. obje

ağırlık 5 , değer 10 , 5 birimin hepsini koydum kazancım  10

Geriye 5 birim yerim kaldı

2. olarak değer/ağırlık oranı en yüksek olan 2. obje

ağırlık 8 , değer 12 , bunun 5 birimini alabiliyorum , kazancım 7,5

toplam kazancım : 10 + 7,5 = 17,5

Yani 3 objeyle ulaşabileceğimiz maksimum kazanç 17,5 . 1. nodun üst sınırı 17,5 .

2. node : 1. objeyi alalım , zaten 17,5 kazancı 1. objenin tamamını alarak hesaplamıştık , o sebepten bu nod içinde üst sınır 17,5.

3. node : 1. ve 2. objeyi alalım.

Ağırlık : 5 + 8 = 13 .

Kapasiteyi aştığı için bu nodu buduyoruz.(Aşağıdaki şekilde görülüyor.)

Tekrar 2. noda çıktık , ordan sağ çocuğa iniyoruz:

6. nod : 1i alalım , 2yi almayalım.

17,5 kazancını 2. objenin bir kısmını koyarak elde ettik , burda 2. objeyi almıyoruz , o sebepten 3. objeye bakalım : 1. obje 5 birimi doldurdu , 2. obje 3 birim alanı oldurdu:

Toplam kazanç : 10 + 3 = 13

7. nod : İlk olasılığa ulaştık : 1. ve 3. objeleri al , toplam kazanç 13

6. noda çıkıyoruz üst sınır 13 tü , onuda 7. nodla elde ettik , o sebepten 8. noda bakmaya gerek yok , eliyoruz.

Şu ana kadar ağaç şu durumda :

Backtrackle 1. noda çıktık , şimdi 8. noda bakıyoruz.

9. nod: 1. objeyi alma. Kalan objelerden elde edeceğim kazanç:

2. objenin tamamını alırım , 2 birimde 3. objeden alırım

Toplam kazanç 12 + 2 = 14

Şu an elimizde olan çözümün(1 0 1) kazancı 13 , daha yüksek bir kazanç vadediyor, devam edelim.

10. nod : 1. yi almayalım , 2.yi alalım , bir üst nodda hesaplamayı 2. tamamen alarak yapmıştık , maksimum kazanç yine 14

11. nod : 2. ve 3.ü alalım.

Ağırlık : 11 Kapasiteyi aştı buduyoruz.

12. nod : Sadece 2.yi alalım

Ağırlık :8 , Kazanç : 12

Elimizdeki çözümden daha iyi değil.

BackTrackle 9. noda geldik.

13. nod : 1. ve 2.yi alma

Geriye 3. kaldı , maksimum kazancımız 3 , elimizde kazancı 13 olan çözüm var , bu noddan daha fazla devam etmiyoruz.

Daha fazla gezecek node kalmadığı için çözüme ulaştık : (1 , 0 , 1) , Kazanç : 13

Binary Knapsack - Branch & Bound Design

Problem için öncelikle durum uzayı oluşturalım .

Her seviyede o objeyi alıp almama olarak nodumuz ikiye ayrılıyor. Sonunda 2^n farklı kombinasyon oluşuyor. Peki tüm ağacı search etmekten daha iyi ne yapabiliriz?

İki farklı budama yapabiliriz.

1. Branching infeasible nodes

2. Branching with bounding

Bir örnek üzerinde açıklayalım.

4 adet objemiz olsun. Ağırlıkları 2,5, 7, 3 ; kapasite 12 olsun . Öyleyse (1,1,1,0) bir çözüm olabilir mi? Hayır  çünkü 1 . 2. 3. objeyi koyabilmemiz için kapasitemizin en az  2+5+7=14 olması gerekir. Öyleyse bu noddan devam etmeye gerek kalmıyor ve buduyoruz.

Sadece infeasibility ile budamak dışında ne yapabiliriz. Her bir nodda bir üst sınır bulabilirsek , yani o noddan ilerleyerek bulabileceğim çözümün maksimum benefiti o nodun üst sınırı, üst sınırı düşük kalan nodları budayabiliriz. Binary knapsack için nasıl bir üst sınır bulabiliriz: Rational knapsack. Aynı objeler ve aynı kapasiteyle binary knapscakle ulaşabilceğim maksimum benefit her zaman rational knapsackle ulaşabilceğiminkinden küçük veya eşittir.

Bunuda bir örnekle açıklayalım.

benefits: 20  35  21  33

weights:  2    5    7    3

b/w      : 10   7   3    11

capacity: 12

Rational knapsack problemi olsaydı b/w büyüklüğüne göre

33 + 20 + 35 + 21*2/7 = 94 maksimum benefitimiz 94 olurdu.(1. 2. 4. objeyi tamamen alıyoruz , 3.nün 2/7sini)

1. seviyede 1. objeyi alırsak üst sınırımız yine 94 b=20 w=2

                  1. objeyi almazsak kalan objelerle maksimum 33+35+21*4/7=80 benefit elde edebiliyoruz

En gelecek vadedenden devam ediyoruz.

2. seviye 2.objeyi alırsak üst sınır yine 94, weight=7

                           almazsak kalan objelerle üst sınırımız 33+20+21=74 oluyor.

3. seviye 3.objeyi alırsak üst sınır 94 , weight = 14 (infeasible)

                            almazsak üst sınır= 33+20+35=88

4.seviye 4.objeyi alırsak üst sınır 88, weight=10, benefit=88

B(x)=benefit olduğu için öbür nodu açmaya gerek yok zaten bu noddan elde edilebilcek maksimum benefit 88. Açılmamış olan tüm nodlar budanıyor , çünkü bulduğumuz çözümün benefiti hepsinin üst sınırından daha büyük , o sebepten onları açmaya gerek kalmadan çözüme ulaşıyoruz.

Binary Knapsnak Problem - Dynamic Programming

Nedir Sırt Çantası Problemi: Kısıtlı kapasitesi olan sırt çantan var . Boyutları ve değerleri olan parçalanamayan eşyalar var. Çantaya alabileceği kadarını koyduk , değer maksimum kaç olur?

Problemin alt parçasına inelim. W kapasiteli bir çantanın maksimum değeri V.
X eşyası eklendiyse onu çıkardığımız  zaman W- Sx kapasiteli çantada maksimum değeri elde ederiz.
Sx: X eşyasının boyutu
Vx: X eşyasının değeri

Value = max{ Value(W-Sx)+Vx , Value(W) }
Value(0) = 0;

Bir örnek üzerinden gidelim:
1. obje boyutu=4 değeri =10
2. obje boyutu=2 değeri =8
3. obje boyutu=3 değeri =3
Çantanın boyutu=5

 Öncelikle 1 tabloya ihtiyacımız var

 Tablonun boyutu: Çantanın kapasitesi kadar sütun(bizim örneğimizde 5) , obje sayısı kadar satır.
[i,j] hücresi j kapasiteli bir çanta ve ilk i obje varken elde ettiğimiz maksimum kazanç.

Birinci satırı doldurmaya başlıyoruz. 1. objenin boyutu 4 ,değeri 10 . Çantanın kapasitesi 4 olana kadar 1. objeyi ekleyemiyoruz bu yüzden 4e kadar kazancımız hep 0. 4e geldik 1. objeyi ekleyebilirim. 1. objeyi eklediğimizde kazancımız 10 oldu. 5e geldik ekleyeceğimiz başka obje yok yine 1. objeyi ekliyoruz.

2. objede geldik boyutu=2 değeri=8
Kapasite 1 : 2. obje sığmıyor , kazanç 0. Üst satıra bakıyoruz oradaki değer de 0. 0 yazıyoruz.

Kapasite 2:  Obje sığıyor , kazanç=8 , bir üst satıra bakıyoruz kazanç 0 imiş. Eklediğimizde değer artıyor o sebepten ekliyoruz.Hücrenin değeri 8 oluyor.

Kapasite 3: Objenin boyutu 2 , 1 birim yer kaldı , 1 birimlik yerde önceki objelerle neler yapabiliriz? Bir üst satırda 1.sütuna bakıyoruz değeri 0. Toplam kazanç 8+0=8. Bir üst satıra bakıyoruz değeri 0. 8>0 olduğu için objeyi ekliyoruz, kazanç 8 oluyor.

Kapasite 4: Burada iş biraz değişiyor. Objeyi ekleyelim kazanç 8 , 2 birim yer kalıyor . Üst satırdan 2 birim yerin değerine bakıyoruz 0, 8+0 toplam kazanç 8. Üst satırın 4. sütununa bakıyoruz. Peki ne için , önceki objelerle 4 kapasitesinde bir çanta için maksimum ne kadar kazanç elde etmişiz : 10 . 10 > 8 olduğu için 2. objeyi bu sefer eklemek yerine üstteki kazançla devam ediyoruz. Hücrenin değeri 10 oluyor.

Kapasite 5: 2. objeyi koyarsak 3 birim yer kalıyor. Üst satırdan bakıyoruz değeri 0 toplam kazanç 8 oluyor . Üst satırdan 5. sütuna baktık değer 10 daha büyük , 2. objeyi koymuyoruz.

 Buraya kadar genel mantık şu şeklide ilerliyor:

i. obje için
o anki kapasite = K
objenin boyutu = H
objenin değeri=P

K<H
Objeyi ekleyemiyoruz. Value[i][K]=Value[i-1][K],  Value[0][K]=0

K=H
Eklediğimizde elde ettiğimiz kazanç , eski kazançtan daha büyükse objeyi ekliyoruz.
 if (P > Value[i-1][K] )
    Value[i][K]=P
else
   Value[i][K]=Value[i-1][K]

K>H
Bu durumda kalan birimin değerini de eklememiz lazım.Eğer objeyi eklediğimizde elde ettiğimiz değer + kalan birimden gelen değer , önceki değerden büyükse objeyi ekliyoruz.

if (P + Value[i-1][K-H] > Value[i-1][K])
    Value[i][K]=P + Value[i-1][K-H]
else
   Value[i][K]=Value[i-1][K]


Tablonun son hali

Bu 3 objeyle 5 birim kapasiteli bir çantada maksimum bu kazanç elde ediyoruz: Value[2][4] = 11

11 i neleri çantaya ekleyerek elde ettik?
5 birimlik çantada 1 ve 2 objelerle max kazanç (Value[1][4]): 10
5 birimlik çantada 1 2 3 objelerlerle max kazanç (Value[2][4]): 11
3. objeyi eklemişiz ki kazanç değişmiş.

3 objeyi eklemeye nasıl karar veriyorduk:
Boyutu 3 olduğu için 2 birim yer kalıyor , bir üst satırdan 2 birim yerden maksimum ne kadar kazanç elde ettiğimize bakıyoruz : 8 , 8 i nasıl elde ettik aynı sütunun üst satırına bakıyoruz kazanç 0 imiş 2. objeyide hesaba katınca kazanç 8 olmuş ; demekki 2. objeyide eklemişiz. 2. objenin boyutu 2 , başka yerimiz kalmadı.
Demekki 2. ve 3. objeleri eklemişiz.

Two Egg Problem - İki Yumurta Problemi

Önce problemin tanımını yapalım:

n katlı bir binadayız , iki adet yumurtamız var . Yumurtalar x. katın altındaki katlardan atınca kırılmıyor, x ve üzeri katlardan atılınca kırılıyor. Kırılmadığı sürece yumurtayı tekrar tekrar kullanabilirsiniz. Minimum kaç atışta yumurtanın kırılmaya başladığı katı bulursunuz?

Akla gelen ilk çözümler:

• 1. kattan başlarız ilk nerede kırıldıysa x odur.

 En iyi Durum: İlk katta kırıldıysa tek atışla bulduk.
 En kötü Durum: En üst katta kırılıyorsa n -1 atışta bulduk.

•  İlk yumurtayı orta kattan atarız.

kırıldıysa : 2. yumurtayı ilk kattan atmaya başlarız, taki kırılana kadar
kırılmadıysa : n/2 ile n. katlar arasında kırılıyor. Bu katların ortasından atış yapıyoruz( 3* n / 4). Böyle devam ediyoruz.(Binary search mantığı).
En kötü Durum: yumurtanın n/2-1 katta kırılması. (Benim de aklıma gelen çözüm bu olmuştu)

Gelelim ideal çözüme bunu direk bir örnekle açıklayacağım. Diyelim ki binamız 100 katlı iddiamız 14 atışta ben nerede kırıldığını bulurum. Nasıl mı?

14. kattan atalım. İlk atış hakkımı kullandım. Kaldı 13.

Kırıldı: 1 den 13 e kadar tek tek deniyoruz.

Kırılmadı: İlk 14 katta kırılmıyor. 1 atış yaptık , 13 atış hakkımız kaldı . 14 + 13 = 27 .

27. kattan atalım. Kaldı 12.

Kırıldı: 15 ten 26. kata tek tek deniyoruz.

Kırılmadı: İlk 27 katta kırılmıyor. 2 atış yaptık , 12 hakkımız kaldı. 27+12=39.(14+13+12)

39. kattan atalım: Kaldı 11

Kırıldı: 28 den 38. kata tek tek deniyoruz.

Kırılmadı: İlk 39 katta kırılmıyor. 39+11=50.(14+13+12+11)

.
.
.

(14+13+12+11+...+4 = 99)39. kattan atalım: Kaldı 3
Kırıldı : (14+13+12+11+...+5+1 = 96)96. kattan 98. kata tek tek deniyoruz.
Kırılmadı: İlk 99 katta kırılmıyor. 100. kattan atıyoruz. Kırılacaktır.

n katlı bina için q atış garantiler ise

q+(q-1)+(q-2)+.....1 =  q*(q+1)/2 >= n olması gerekir.

Güzel çözüm değil mi ? Tabi bu problemde yumurta sayısı da değiştirilebilir, strateji aynı.