Basit bir problem ne kadar zor olabilir ?

Başlık her ne kadar çelişkili görünse de aslında merak ettiğim soru tam olarak başlıktaki soru.
Eğer başlığı "kolay bir problem ne kadar zor olabilir?" şeklinde yazmış olsaydım gerçekten de çelişkili bir durumla karşı karşıya kalabilirdik. O yüzden en azından bu yazı için problemleri şu şekilde sınıflandırmayı tercih ediyorum;

• Basit ve kolay problemler.
• Basit ve zor problemler.
• Karmaşık ve kolay problemler.
• Karmaşık ve zor problemler.

Basitlik yahut karmaşıklık ile problemin anlatılabilirliğini ve anlaşılabilirliğini ifade ediyorum. Zorluk ya da kolaylık ile ise problemin çözümünün kolay yahut zor oluşundan bahsediyorum.
Problemlerin basit yada karmaşık oluşu haliyle göreceli bir kavram olmakla birlikte çoğu kişi tarafından kabul görebilecek sınıflandırmalar yapabiliriz.

Başlıktan da anlaşılacağı gibi ben bu yazıda bahsedeceğim problemin (parti problemi) basit bir problem olduğunu düşünüyorum. Kanımca, matematik ve bilgisayar konusunda bilgi sahibi olmayan birisi bile iyi anlatıldığı takdirde bu problemi çabucak kavrayabilir. Bir tek cümle ile bile yeterince açık bir biçimde örneklenip ifade edilebilinir.

Şimdi bu "basit" problemi yine basit bir yöntem kullanarak çözmenin, kolay mı yoksa zor mu olduğunu inceleyebiliriz.
En basit kabakuvvet yöntemi ile bu problemi çözmeye çalıştığımızı düşünelim. O halde tüm durumları tek tek denememiz gereklidir.
Örneğin 5 kişilik parti probleminin çözümünün bilinen aralığı [43,49]. Yani problemin çözümü 43, 44, 45, 46, 47, 48 ya da 49 sayılarından bir tanesidir. Problem en az davetli sayısını istediğine göre 43 olup olmadığına bakalım.

Basit kabakuvvet yöntemimizle probleme yaklaştığımızda 43 kişilik bir partide kişilerin tüm olası el sıkışma (tanışıklık yada benzeri) durumlarını teker teker inceleriz. Eğer olası tüm durumlarda parti probleminin bize söylediği iki koşuldan:

• her biri diğer 4'ü ile el sıkışmış 5 kişilik bir grup,
  
• her biri diğer 4'ü ile el sıkışmamış 5 kişilik bir grup.

en az biri sağlanıyorsa çözüm = 43, aksi halde çözüm > 43 sonucuna varırız.

Şimdi olası tüm el sıkışma durumlarının kaç tane olduğunu hesaplayalım. El sıkışma olayı iki kişi arasında ya gerçekleşir ya da gerçekleşmez. Ve bu iki kişi 43 kişinin 2 li kombinasyonlarının sayısı kadar farklı biçimde seçilebilinir. O halde;
2^(43*42/2) tane farklı durum söz konusudur. Basit kabakuvvet yöntemimiz 2^903 tane farklı el sıkışma kombinasyonunu incelemek durumundadır. Bu da tam olarak incelenmesi gereken;

67621699985365151533099492469314125634412457732623554832378970755414
25952726078201272540875362012005051832255913691247089694048761634374
87680689892432562658442734955518726507735976342625825844547871018122
51032115730947621472199902571314803042180668990660938354910463787008

adet durum olduğu anlamına gelir. 272 basamaklı bu sayıyı 18 defa katrilyon çarpılarak ifade edilebilecek (katrilyon kere katrilyon kere ... katrilyon) sayıdan daha büyüktür.

Dünyada katrilyon tane ev olsa, her bir evde şu anda dünyada bulunan en hızlı süper bilgisayardan katrilyon kat daha hızlı olan bilgisayarlardan katrilyon tane olsa yine de bu basit kabakuvvet yöntemiyle problemi çözmek dünyanın yaşının katrilyonlar kere katrilyonlarca katından daha uzun zaman alırdı.

Demek ki bu basit problem, basit bir kabakuvvet yöntemiyle çözmek için zor bir problem. Tabii kullandığımız kaba kuvvet yöntemini biraz karmaşıklaştırmak problemi kolaylaştırmada bize yardımcı olabilir. Bir sonraki yazıda aynı problemi 60415263038565101838178326743348811045937215431513389 kat daha "kolay" fakat yine de "zor" :) bir biçimde nasıl çözebileceğimizi anlatmayı düşünüyorum...

bolumle.m

%    Yayıncı     : Şenol Korkmaz < senol.korkmaz@gmail.com >
%    Dosya Adı   : bolumle.m
%    Gerekenler  : partitions.m  < http://www.mathworks.com/matlabcentral/fileexchange/loadFile.do?objectId=12009&objectType=file >
%    Tanım       : Sayı Bölümleme maksatlı MATLAB işlevi
%    Kullanım    : bolumle(n,m,k)
%
%    Girdi       : n --> Bölümlenecek sayı
%                : m --> Bölümlemelerin kaçar sayıdan oluşacağını belirten vektör
%                : k --> Bölümlemede kullanılacak sayıların seçileceği vektör
%
%    Çıktı       : Bu işlev bölümlemeleri döndürür
%                
%    Sürüm       : 1.0
%
%    Lisans      : GNU/GPL v3  <http://www.gnu.org/licenses/>

function bolumler = bolumle(n,m,k) % İşlevi ve girdilerini tanımla

if (nargin==1)       % Eğer sadece bir girdi var (n) ise
    m = 1:n;       % m = 1 den n'ye kadar tamsayıları içeren vektör
    k = m;         % k = 1 den n'ye kadar tamsayıları içeren vektör
end

if (nargin==2)       % Eğer sadece iki girdi var (n & m) ise
    k = 1:n;       % k = 1 den n'ye kadar tamsayıları içeren vektör
end

% k vektöründeki sayıları kullanarak harici partitions fonksiyonu ile n'i bölümle
% hamBolumler, her bölümlemede hangi sayının kaçar defa kullanıldığı bilgisini içerecek
hamBolumler = partitions(n,k);

hamBolumler =  hamBolumler(find(ismember(sum(hamBolumler,2),m)==1),:);   % m vektöründe belirtilenler kadar sayı kullanılmış bölümlemeleri al

bolumler = zeros(size(hamBolumler,1),max(m));  % Çıktı şablonu

for i = 1:size(hamBolumler,1)  % Her bir ham bölüm için döngü

    buSatir = [];  % O an işlenecek satır için boş vektör

    for j = 1 : size(hamBolumler,2) % Her bir ham bölümü oluşturan her bir sayı için döngü
        
        % hamBolumler vektöründe her sayının kaçar defa kullanıldığı bilgisi yer almaktadır
        % bu bilgiyi kullanarak buSatır vektörüne o sayıları kullanıldıkları kadar ( repmat ile)
        % ekler ve onları azalan sıra ile sıralarız
        buSatir = horzcat(buSatir,repmat(k(j),1,hamBolumler(i,j))); 
    end
    
    % buSatır vektörünün boyu max(m) kadar olmalıdır, bu yüzden kalan yerlere 0 doldurulur
    buSatir = horzcat(buSatir,repmat(0,1,size(bolumler,2)-size(buSatir,2)));
    
    % buSatır vektörünü çıktıya ekle 
    bolumler(size(hamBolumler,1)-i+1,:) = sort(buSatir,'descend') ;
end

intpart.m

%    Author      : Senol Korkmaz < senol.korkmaz@gmail.com >
%    Filename    : intpart.m
%    Requires    : partitions.m  < http://www.mathworks.com/matlabcentral/fileexchange/loadFile.do?objectId=12009&objectType=file >
%    Description : A Matlab Function to calculate partitions of an integer
%    Usage       : intpart(n,m,k)
%
%    Input       : n is an integer to find out its partitions
%                : m is a vector which indicates that how many numbers can be used
%                : k is a vector which indicates that which numbers can be used
%
%    Output      : This function returns a matrice that includes partitions of n
%                
%    Version     : 1.0
%
%    License     : GNU/GPL v3
%    This program is free software: you can redistribute it and/or modify
%    it under the terms of the GNU General Public License as published by
%    the Free Software Foundation, either version 3 of the License, or
%    (at your option) any later version.
%    This program is distributed in the hope that it will be useful,
%    but WITHOUT ANY WARRANTY; without even the implied warranty of
%    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
%    GNU General Public License for more details.
%    You should have received a copy of the GNU General Public License
%    along with this program.  If not, see <http://www.gnu.org/licenses/>.

function iparts = intpart(n,m,k) % Declare function and its arguments

if (nargin==1)       % There is only one input (n)
    m = 1:n;     % Consider that m is a vector that contains all integers from 1 to n
    k = m;       % Consider that k is a vector that contains all integers from 1 to n
end

if (nargin==2)       % There are two inputs ( n & m)
    k = 1:n;     % Consider that k is a vector that contains all integers from 1 to n
end

partlist = partitions(n,k);   % Calculate the partitions of n with the numbers whis is in the vector k

% Code explanations will be written as soon as possible

partlist =  partlist(find(ismember(sum(partlist,2),m)==1),:);

iparts = zeros(size(partlist,1),max(m));

for i = 1:size(partlist,1)

    tmpROW = [];

    for j = 1 : size(partlist,2)
        tmpROW = horzcat(tmpROW,repmat(k(j),1,partlist(i,j)));
    end

    tmpROW = horzcat(tmpROW,repmat(0,1,size(iparts,2)-size(tmpROW,2)));
    iparts(i,:) = sort(tmpROW,'descend') ;
end

Ramsey Sayıları

Ramsey sayıları ile ilgili çalışmanın en son haline (01.08.2008)

                          http://docs.google.com/fileview?id=0B_AjGTl8wNS-YzU0MDM1NTItMjhjNy00ZTA2LTgxMTgtYTFkOTBkNTIyM2Qy&hl=tr

adresinden PDF biçeminde erişebilirsiniz.

Belge henüz taslak halindedir, lütfen gördüğünüz eksikleri bana iletiniz.

Sayısal lotoyu garantilemek.

Başlık sizi heyecanladırmasın, bahsedeceğim sayısal loto Milli Piyango İdaresinin 6/49 luk lotosu değil, benim naçizane 4/6 lık sayısal lotom olacak.

Soru : 4/6 lık bir loto çekilişinde en az bir tane 3 tutturmayı en az kaç kolon oynayarak garantileyebiliriz.
Kolonlar rasgele değil bilinçli olarak an az sayıda kolon ile 3 tutturmayı garantileyecek şekilde oynanacaktır.

Yanıt :

3 kolon kâfi gelir.

1 2 3 4
1 2 5 6
3 4 5 6

Bakınız : loto0.m