Monday 16 December 2013

Christmas කාලේ blog එකට Snows add කරමුද?

වැඩේ හරිම ලේසියි ඔයාගෙ blog එකේ dashboard එකට යන්න

Layout > Add Gadget  > HTML/JavaScript  වලට යන්න

ඒකෙ පහල තියන code වලින් එකක් කරන්න
 code (1):

<script type="text/javascript" src="http://www.skincorner.com/snow.js">
</script>

code (2):

<script type="text/javascript"> 
  //Configure below to change URL path to the snow image 
  var snowsrc="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiZIJVizaeOiLyJGWkacvLMhcTy7XvKysziTm_y63GG8cyY4MKkwt0aI07SoIAPXO4IhF__PFbUpY1A9tuTI1ssqQYzpVoRMbZ5BHvDzt_KnR39_8VTGtwaAkx9MFOg2UZPghp5DUVqrQw/s400/snow.gif" 
  // Configure below to change number of snow to render 
  var no = 20
  // Configure whether snow should disappear after x seconds (0=never): 
  var hidesnowtime = 0; 
  // Configure how much snow should drop down before fading ("windowheight" or "pageheight") 
  var snowdistance = "pageheight"; 
///////////Stop Config////////////////////////////////// 
  var ie4up = (document.all) ? 1 : 0; 
  var ns6up = (document.getElementById&&!document.all) ? 1 : 0; 
    function iecompattest(){ 
    return (document.compatMode && document.compatMode!="BackCompat")? document.documentElement : document.body 
    } 
  var dx, xp, yp;    // coordinate and position variables 
  var am, stx, sty;  // amplitude and step variables 
  var i, doc_width = 800, doc_height = 600; 
  if (ns6up) { 
    doc_width = self.innerWidth; 
    doc_height = self.innerHeight; 
  } else if (ie4up) { 
    doc_width = iecompattest().clientWidth; 
    doc_height = iecompattest().clientHeight; 
  } 
  dx = new Array(); 
  xp = new Array(); 
  yp = new Array(); 
  am = new Array(); 
  stx = new Array(); 
  sty = new Array(); 
  snowsrc=(snowsrc.indexOf("dynamicdrive.com")!=-1)? "http://2.bp.blogspot.com/-MsCdyoGtGdA/UX5gk72qNoI/AAAAAAAAAfQ/LaKTmUG-aJM/s1600/snow+falling+effect.gif" : snowsrc 
  for (i = 0; i < no; ++ i) {  
    dx[i] = 0;                        // set coordinate variables 
    xp[i] = Math.random()*(doc_width-50);  // set position variables 
    yp[i] = Math.random()*doc_height; 
    am[i] = Math.random()*20;         // set amplitude variables 
    stx[i] = 0.02 + Math.random()/10; // set step variables 
    sty[i] = 0.7 + Math.random();     // set step variables 
        if (ie4up||ns6up) { 
      if (i == 0) { 
        document.write("<div id=\"dot"+ i +"\" style=\"POSITION: absolute; Z-INDEX: "+ i +"; VISIBILITY: visible; TOP: 15px; LEFT: 15px;\"><a href=\"http://dynamicdrive.com\"><img src='"+snowsrc+"' border=\"0\"><\/a><\/div>"); 
      } else { 
        document.write("<div id=\"dot"+ i +"\" style=\"POSITION: absolute; Z-INDEX: "+ i +"; VISIBILITY: visible; TOP: 15px; LEFT: 15px;\"><img src='"+snowsrc+"' border=\"0\"><\/div>"); 
      } 
    } 
  } 
  function snowIE_NS6() {  // IE and NS6 main animation function 
    doc_width = ns6up?window.innerWidth-10 : iecompattest().clientWidth-10; 
        doc_height=(window.innerHeight && snowdistance=="windowheight")? window.innerHeight : (ie4up && snowdistance=="windowheight")?  iecompattest().clientHeight : (ie4up && !window.opera && snowdistance=="pageheight")? iecompattest().scrollHeight : iecompattest().offsetHeight; 
    for (i = 0; i < no; ++ i) {  // iterate for every dot 
      yp[i] += sty[i]; 
      if (yp[i] > doc_height-50) { 
        xp[i] = Math.random()*(doc_width-am[i]-30); 
        yp[i] = 0; 
        stx[i] = 0.02 + Math.random()/10; 
        sty[i] = 0.7 + Math.random(); 
      } 
      dx[i] += stx[i]; 
      document.getElementById("dot"+i).style.top=yp[i]+"px"; 
      document.getElementById("dot"+i).style.left=xp[i] + am[i]*Math.sin(dx[i])+"px";  
    } 
    snowtimer=setTimeout("snowIE_NS6()", 10); 
  } 
    function hidesnow(){ 
        if (window.snowtimer) clearTimeout(snowtimer) 
        for (i=0; i<no; i++) document.getElementById("dot"+i).style.visibility="hidden" 
    } 
if (ie4up||ns6up){ 
    snowIE_NS6(); 
        if (hidesnowtime>0) 
        setTimeout("hidesnow()", hidesnowtime*1000) 
        } 
</script>

පලවෙනි code එක බ්ලොග් එකේ පහලින් දානවනම් හොදයි . දෙවනි code එක තියන තැන ඉදන් snows තමයි වැටෙන්න පටන්ගන්නෙ
දෙවනි code එකේ රතු පාටින් highlite කරල තියන number එකට කැමති number එකක් දීලා වැටෙන ප්‍රමාණය වැඩි කරගන්නත් පුලුවන්.

Friday 13 December 2013

Asymptotic analysis/ big O , Omega, Theta notations/(සිංහලෙන්)


ඔයාල algorithms ගැන ඉගනගන්නවනම්  big O , Omega, Theta notations කියන්නෙ ඉතාම වැදගත් වන දේවල් ටිකක්.අපි අද බලමු මොනවද මේ  big O , Omega, Theta කියන්නෙ කියල , ඒ වගේම ඒවගෙන ගණන් දුන්නම හදන්නෙ කොහොමද කියල. 

Running Time

ඕනෑම algorithm එකක හෝ  programme  එකක efficiency එක මනින්නෙ running time  එක මගින්.මේ running time එක කියන එකට හරියටම නිශ්චිතවම එක අගයක් කියන්න අමාරුයි.ඒක input size  එක මත රඳා පවතින ශ්‍රිතයක්. එකම   programme එකේ උනත් input එක වෙනස් වෙනකොට running time එක වෙනස් වෙනව. අපි මේක චූටි උදාහරණයකින් පැහැදිලිකරගනිමු.

                   

මේ array එකේ  items  6 ක් තියනව. අපි හිතමු අපිට මේකෙ 0 වෙනි index එකේ තියන item එක, ඒ කියන්නෙ 5 හොයන්න ඕනෙ කියල, අපි මේ arraynඑකේ තියන item  එක , එක පිළිවෙලට search  කරල බලනව අපිට ඕන එක තියනවද කියල.මේකෙ මුලින්ම තියෙන්නෙ 5 නිසා බලපු ගමන්ම 5 අහු වෙනව එහිදී running time  එක  1ක් වෙනව. අපිට 23 හොයාගන්න ඕන උනොත් අපිට 5 වෙනි එකට වෙනකම් searchකර කර යන්න වෙනව. එහිදී 6ක් searchකරල බලපු නිසා running time  එක 6ක් වෙනව.

          මෙන්න මේ array  එක search කරන එක සැලකුවහම, ඒකට අපිට ගන්න පුළුවන් අඩුම අගය තමයි 1. ඒක මෙකෙ bsest case එක කියල හඳුන්වනව.එන්න පුළුවන් වැඩිම අගය තමයි 6 ඒක මේකෙ worst case එක කියල හඳුන්වනව. මේ අනුව item n ගානක් තියන array  එකක් සැලකුවහම best case  එක 1ත් worst case එක nත් වෙනව. මේ දෙකේ මධ්‍යනය average case  එක කියල හඳුන්වනව ඒක n/2 ක් වෙනව. මේ අනුව running time  එකක එකට best case එක හා worst case එක අතර ඕනෑම අගයක් එන්න පුළුවන්. අපිට ඒක හරියටම කියන්න බැහැ ඒකෙ running time අගය input size එක මත රඳා පවතිනව.

             Best Case ≤ Running Time ≤ Worst Case
මේ best case එක lower bound එක ලෙසත් worst case එක upper bound එක ලෙසත් හඳුන්වනව. එවිට
          Lower Bound ≤ RunningTime≤ Upper Bound

Asymptotic Notations

අපි දැන් බලමු asymptotic notation කියන්නෙ මොකද්ද කියල.අපිට දක්නට ලැබෙන running times ප්‍රධාන වශයෙන් කොටස් තුනකට බෙදනව,
Big O notation (O)
Omega ( Ω)
Theta (θ)
        මෙතනදි අපි input size  එක ශ්‍රිතයක් ආකාරයෙන් වෙනස් කරල ඊට අදාළව running time එක ප්‍රස්ථාරගත කරනව. input size එක n නම්,
      input size එකේ ශ්‍රිතය = g(n), 
      running time එකේ ශ්‍රිතය = f(n),
ලෙස  ගනිමු.
Big O notation (O)(Worste Case)
මෙහිදී c යනු ඕනෑම නියතයක් නම් nයන යම්කිසි input size එකකට ඉහළ තියන ඕනෑම input එකකදි  input size ශ්‍රිතය c වලින් ගුණ කලවිට ලැබෙන අගය[c g(n) ] running time එකේ ශ්‍රිතයට [f(n)]වඩා වැඩි නම්. එනම්,
                f(n) ≤ c g(n)  for all n ≥  n0


මෙවැනි running time එකක්  O(n) ආකාරයේ running time එකක් ලෙස හැඳින්වෙයි. නමුත් running time එකක් රිණ විය නොහැකි නිසා,

              0 ≤ f(n) ≤ c g(n) for all  n ≥ n0






Omega ( Ω) (Best Case)
මෙහිදී c යනු ඕනෑම නියතයක් නම් nයන යම්කිසි input size එකකට ඉහළ තියන ඕනෑම input එකකදි  input size ශ්‍රිතය c වලින් ගුණ කලවිට ලැබෙන අගය[c g(n) ] running time එකේ ශ්‍රිතයට [f(n)]වඩා අඩු නම්. එනම්,
               0  ≤  c g(n)  ≤ f(n)    for all  n ≥ n0
   මෙවැනි running time එකක් Ω(n) ආකාරයේ එකක් ලෙස හඳුන්වයි.

Theta (θ)(Avarage Case)
මෙහිදී අපිට  cහා  cකියන නියතයන් දෙකක් ගන්න වෙනව එවිට,
               0 ≤  c g(n) ≤  f(n) ≤ c2 g(n)  for all  n ≥ n0
වනපරිදි c1  හා c2  නියත දෙකක් තිබේනම් මෙවැනි running time එකක් θ (n)    ආකාරයේ running time   එකක් ලෙස හඳුන්වයි.

මේ අවස්ථා තුන සලකල බැලුවහම O(n) වලදි නිතරම input size එකට වඩා running time එක අඩුවෙන නිසා efficiency එක වැඩියි.  Ω (n) වලදි  input size එකට වඩා running time එක වැඩිවෙන නිසා efficiency  එක අඩුයි. θ(n) වලදි running time එක යම්කිසි අගයන් දෙකක් අතර සාමාන්‍ය මට්ටමක පවත්වාගන්නවා.
Problems
අපි දැන් runnin time function එක දුන්නහම ඒක මොන ආකාරයේද කියල ඔප්පු කරන විදිය බලමු.
(1)Show that 30n+8 is O(n).
මෙවැනි ගණනකදී නිතරම O() එක ඇතුලෙ දෙන function එක input function එක වන අතර එලියෙන් දෙන function එක running time function එකයි.එමනිසා,
  f(n) = 30n + 8
  g(n) = n
අප පෙන්විය යුත්තේ
        30n + 8   ≤  cn    for all  n ≥ n0
මෙහි c ට හා  nට ගැලපෙන අගයන් දෙකක සොයාගත යුතුය.
      30n + 8 ≤  30n + 8n = 38n for all  n ≥ 1
       30n + 8 ≤ 38 n
        c = 38 , n0 = 1
මෙතනදී එක එක අයට වෙනස් පිළිතුරු ලැබිය හැක. නමුත් ඕනෑම එක c අගයක් සඳහා පැවතිය හැක්කේ එක් n0 අගයක් පමණි. ඒ කියන්නෙ c = 38 වෙලා  n=  2 වෙන්න බැහැ කියල. නමුත් c වලට හා n0 වලට ගන්න පුලුවන් අගයන් වෙනස් වෙමින් මෙයට ගැලපෙන පිළිතුරු {c,n0} කුලක කිහිපයක් තිබිය හැක.
         Let c = 31 , 30n + 8 ≤  31n = 30n + n
          then when n ≥ 8
          cn = 31n = 30n + n > 30n+8,
           so 30n+8 ≤  cn when c= 31 , n0  = 8.
මෙම පිළිතුරද නිවැරදි වෙයි.
(2)Prove that 100n + 5 = O(n2)
–100n + 5 ≤ 100n + n = 101n ≤ 101n2
for all n ≥ 5
n0 = 5 and c = 101 is a solution
or
–100n + 5 ≤ 100n + 5n = 105n ≤ 105n2 for all n ≥ 1

n0= 1 and c = 105 is also a solution

(3)5n2 = Ω(n)

 cn ≤ 5n2
 c = 1 and n0 = 1
එමෙන්ම යම්කිසි ශ්‍රිතයක් දුන්විට අදාල notation එකට අසමානයැයි පෙන්වීමටද හැකි විය යුතුය.
(4)100n + 5 ≠ Ω(n2)
ඔප්පු කළ යුත්ත: 0 ≤ cn2 ≤ 100n + 5
මෙය නිවැරදි ලෙස ගෙන ගණන සාදයි.
    100n + 5 ≤ 100n + 5n (for all  n ≥  1) = 105n
    cn2 ≤  105n
    n(cn – 105) ≤ 0
    Since n is positive
     cn – 105 ≤  0
      n ≤  105/c
නමුත් මෙහි n කියන්නේ input size  එක ඒකට අපිට nසිට අනන්තය දක්වා ඕනෑම අගයක් ගතහැකි විය යුතුයි. අපි මෙහිදී  nහි n0 වල සිට අනන්තය  දක්වා ඕනැම අගයකට මෙය සත්‍ය වන බව ඔප්පු කළ යුතුයි.නමුත් මෙතන  n ≤  105/c ලෙස ලැබිල තියනව. n කිසියම් අගයකට වඩා කුඩා වෙන්න බැහැ. එමනිසා මෙය contradiction එකකි.
100n + 5 ≠ Ω(n2)
මන් හිතනව ඔයාලට මේ පාඩම ටිකක් හරි තේරෙන්න ඇති කියල. ඔයාලට මේ post එකෙන් පොඩි හරි උදව්වක් උනානම් comment එකක් දාල යන්න අමතක කරන්න එපා.