Pages

Wednesday, September 30, 2015

සහානුයාතයෙන් අනන්තය වෙත නොයමු!

සහානුයාත ක්‍රමය මුලින්ම මට හමුවෙන්නේ උසස් පෙළ ශුද්ධ ගණිතයේදී.
කොහොමත් මට ව්‍යවහාරික ගණිතය ගැන තිබුණු ඇල්මැරුණු ස්වභාවය ට වඩා උනන්දුවක් ශුද්ධ ගණිතය ගැන තිබුණා.

මම සහානුයාත ක්‍රමය ට ගැටළුවක් විසඳනු බලා සිටි ගුරුතුමී 'ඔයාට හරියන්නේ ප්‍රෝග්‍රැමිං' යැයි පැවසුවත්, ඒ වෙන විට නම් පරිගණක ක්‍රමලේකනයේ සහ සහානුයාතයේ  සම්බන්ධය දැන සිටියේ නැහැ.

සහානුයාත ය නැත්නම් recursion පැහැදිලි කර ගන්න සරල උදාහරණ කිහිපයක් කිව්වොත්:

1) කතන්දරේ - එකමත් එක රටක පොඩි බබෙක්ට නින්ද යන්නේ නැති නිසා එයා නිදි කරවන්න අම්මා ගෙඹි පැටියගේ කතාව කිව්වා.
      ....එකමත් එක රටක ගෙඹි පැටියෙක් හිටියා. ගෙඹි පැටියට නින්ද  යන්නේ නැති නිසා එයා නිදි කරවන්න ගෙඹි අම්මා වලස් පැටියගේ කතාව කිව්වා.
            ... එකමත් එක රටක වලස් පැටියෙක් හිටියා. වලස් පැටියට නින්ද  යන්නේ නැති නිසා එයා නිදි කරවන්න වලස් අම්මා මුගටි පැටියගේ කතාව කිව්වා.
                  ...මුගටි පැටියට නින්ද ගියා.
       ....ඉතින් වලස් පැටියට නින්ද ගියා.
     .....ඉතින් ගෙඹි පැටියට නින්ද ගියා.
ඉතින් බබාට නින්ද ගියා.

2 ) රුසියන් බෝනික්කෝ සෙට් -  මේ පහතින් තියෙන පින්තුරේ තියෙන්නේ රුසියන් බෝනික්කෝ සෙට් එකේ එකක් ඇතුලේ එකක් බෝනික්කෝ තියෙනවා.
පලවෙනි බෝනික්කා ඇතුලේ ඊට පොඩි එකෙක්.
       ඒ බෝනික්කා ඇතුලේ ඊට පොඩි එකෙක්.
            ඒ බෝනික්කා ඇතුලේ ඊට පොඩි එකෙක්.
                ඒ බෝනික්කා ඇතුලේ ඊට පොඩි එකෙක්.....
ඔහොම ගිහින් බෝනික්කෝ 'ස්තර' කීපයක් ගිහින් අතට අහු වෙන නොවෙන ගානේ චූටි ම චූටි බෝනික්කෙක්ගෙන් ඉවර වෙනවා.



රුසියන් බෝනික්කෝ

ඔය උඩ උදාහරණ දෙකේ තියෙන pattern එක ගැන හිතුවොත් තේරේවි සහානුයාත ක්‍රමය කියන්නේ යළි යළිත් ස්වයං අනුරූපීව එකම ක්‍රියාවලියක් (සුත්‍රයක්) සිදු කිරීම කියලා.

මේ 'ස්වයං අනුරූපී' සිංහල වචනය කොච්චර නිවැරදිද කියල දන්නේ නැහැ. අදාළ ඉංග්‍රීසි වචනය self-similarity.


Self similarity

මේක පරිගණක  ක්‍රමලේඛනයේ ගොඩක් ගැටළු විසඳන්න පාවිච්චි කරන්න පුළුවන්.

සහානුයාතයකට තියෙන්න ඕනැ මේ නීති දෙක :
1) පාදම් අවස්තාව : base case එක කියල ඉංග්‍රීසියෙන් හඳුන්වනවා. ඒ කියන්නේ මේ ක්‍රියාවලිය නවතින කොන්දේසියක් නැත්නම් සීමා වක්. මේ කොන්දේසිය නැති උනොත් අනන්ත වාරයක් ක්‍රියාවලිය සිදු වෙමින් පවතීවි. උදාහරනෙකට අර උඩ තියෙන රුසියානු බෝනික්කොන්ගේ පාදම් අවස්තාව තමයි අතට අහු වෙන නොවෙන ගානේ චූටි ම චූටි බෝනික්කා.
2) පාදම් අවස්තාව දක්වා පරිවර්තනය/ඌනනය කෙරෙන නීති: රුසියානු බෝනික්කො උදාහරෙනම බැලුවොත්, එහිදී ලොකුම බෝනික්කා පුංචිම බෝනික්කා වෙන කම් ප්‍රමාණය අඩු වීම තමයි එහි ඌනන නීතිය.

මේ තියෙන්නේ සරලම උදාහරණයක්:
යම් පූර්ණ සංඛ්යාවකක ක්‍රමාරෝපිත අගය හොයන එකයි මෙයින් කෙරෙන්නේ.
(n නම් පූර්ණ සංඛ්‍යවේ ක්‍රමාරෝපිත අගය අපි ලියන්නේ මෙහෙම : n! = n x (n-1) x (n-2) x (n-3) ... x 1
එතකොට අපි හිතමු n = 7 කියලා. එතකොට
7! = 7 x 6 x 5 x 4 x 3 x 2 x 1

ඒක ගණිත සුත්‍රයක් විදියට ලිව්වොත්:


දැන් මේක පරිගණක ක්‍රමලේඛනයක් විදියට ලිව්වොත්...

private int factorial(int n) {
// base case/පාදම් අවස්තාව
if (n == 0) {
return 1;
}
// recursive case/ඌනන අවස්තාව
return (n * factorial(n - 1));
}


සහානුයාත ක්‍රමය වෙනුවට ලූප් එකක් යොදන්නත් පුළුවන්. සහානුයාතය යොදා ගන්නේ විසඳන්න වගේම තේරුම් ගැනීමේ පහසුව තකා. කොහොම උනත් සහානුයාතය නොගැලපෙන තැනුත් තියෙනවා. අදාළ ගැටලුව මත එය රඳා පවතින්නේ.


පින්තුර ගත්තේ විකිපීඩියා වෙන් : https://en.wikipedia.org

30 comments:

  1. මං හිතන්නෙ මේවට තමා සුපිරි ග්‍රීක් කියන්නෙ
    හැබැයි දෙයක් කියන්න ඕන ශ්‍රද්ධ ගණිතය ගැන කිසි දෙයක් නොදන්න මට වුණත් අර උඩිං කරල තියෙ පැහැදිලි කිරීම නං හිතට ඇල්ලුව විතරක් නෙවී මං හිතනව දෙයක් ඔළුවට වැටුණ කියල
    ඒත් වැඩක්යැ. ග්‍රීක් කියන්නෙ ග්‍රික් වලටම තමා
    නැද්ද හා

    ReplyDelete
    Replies
    1. අයියෝ... ග්‍රීක් වගේද? එහෙම උනා නම් ඇත්තටම ඒක මගේ පැහැදිලි කිරීමේ අඩු පාඩුවක්...
      උදාහරණ දෙක හරි පොඩ්ඩක් තේරුනා නම් සතුටුයි. අග හරියේ තියෙන ටික ඉතින් ඇත්තටම ගණිතය/ක්රමාලේඛනය ට අදාළ දේවල්.

      Delete
    2. https://en.wikipedia.org/wiki/Greek_mathematic

      Delete
    3. https://en.wikipedia.org/wiki/Niro_(rapper)

      Delete
  2. පෞද්ගලිකව මම නම් පුළුවන් තරම් recursive functions මඟ අරින්ට තමා බලන්නෙ.. simple loop එකක් දැම්මහම debug කරන්ට ලේසියි.. :-)

    ReplyDelete
    Replies
    1. ඔව් බුරා හරි.
      recursive functions ඩීබග් කරන්න ගියාම විකාර වගේනේ. මාත් app development වලදී නම් ගොඩක් වෙලාවට ලූප් එකක් තමයි දාන්නේ. හැබැයි සහානුයාතය ඕනේ වෙන තැනුත් තියෙනවා graph එක්ක වැඩ කරද්දී එහෙම. හැබැයි memory ගැනත් හිතන්න ඕනේ.

      Delete
  3. මුල පැහැදිලි කිරිම නම් තේරුණා... හම්මේ අනිත් ටික නං ඔලුවට පොල්ලෙන් ගැහුවා වගේ තමා.

    ReplyDelete
    Replies
    1. වැඩිය ගණන් ගන්න එපා නලීන්...මුල ටිකේ තමයි idea එක තියෙන්නේ.

      Delete
  4. මටනම් හොඳට තේරුණා. ගෙඹි පැටියට වලස් පැටියෙක් හම්බුවෙලා දෙන්න බඳිනව. ඒ දෙන්නට මාස දහයෙන් බෝනික්කෙක් හම්බුවෙනවා. එතකොට ගෙඹි පැටියගෙ අම්මට නින්ද ගිහිල්ලා. හොඳ වෙලාවට AL මැත්ස් කළේ නැත්තේ. ඒ උනාට මම බයෝ කරල ඇත්ත ගෙඹි පැටව් සීයක් විතරකටයි කැරපොත්තො සීයක් විතරකටයි වගකියල, දැන් මෙලෝ සම්බන්දයක් නැති දෙයක් කරනව.

    ReplyDelete
    Replies
    1. //ගෙඹි පැටියට වලස් පැටියෙක් හම්බුවෙලා දෙන්න බඳිනව. ඒ දෙන්නට මාස දහයෙන් බෝනික්කෙක් හම්බුවෙනවා//
      බුදු අම්මෝ හොඳ වෙලාවට ඔයා බයෝ වලට සම්බන්ධ නැති දෙයක් කරන්නේ. නැත්නම් එක එක ජාතියේ 'ගෙඹිලස්' ජීවියෝ හදල අපිට මේ ඉන්න ගෙම්බෝ වලස්සු කැරපොත්තෝ මදිවට!!

      Delete
    2. ඕක මෙහෙම වෙන්නත් තිබ්බනෙ. මම ජාන විද්‍යාව පැත්තෙන් පරීක්ශණ කරල මෙලහකටත් ලෝකේ වායු දූශණය සහ අධික ජනගහණය කියන ප්‍රශ්ණ දෙකම එක පාරෙන් විසඳල. නොබෙල් තෑග්ග කෙසේ වෙතත් ගොබෙල්ස් තෑග්ගත් දිනල. දෙමුහුන් පිරිමි ගෙම්බො වගේ පැන පැන යන නිසා වාහන පාවිච්චිය අඩුවෙලා. ගෑණු කට්ටිය ඔක්කොම වැලහින්නියො වගේ නිසා පිරිමි පන එපා කියල දුවන නිසා ජනගහණය අඩුවෙලා.

      වෙලාවක් තියෙන විටක ඉයන්ගේ අඩවිය පැත්තට ඇවිත් යන්න

      Delete
  5. Linear Recursion දන්නෙම නැති කෙනෙකුට උනත් තේරුම් කරල දෙන්න ලේසිම එක තමයි ෆැක්ටෝරියල් එක.
    Binary, Tail, Mutual,Nested Recursion වගේ එව්ව ගැන කියන්න ගියොත් ඔබ තුමීට ගුටි කන්න තමයි වෙන්නෙ.

    ReplyDelete
    Replies
    1. අනේ ගුටි කන්න බෑ මං අහිංසකයි... :D

      Delete
  6. සංකරන සහ සංයෝජන වලින් පසුව ප්‍රෝග්‍රමින් පැත්තට නොහැරුණු නිසා , ප්‍රෝග්‍රමින් ගැන නොතේරේ .

    සෛද්ධාන්තිකව නම් පාදම් අවස්තාව කියන්නේ අනන්තයේ හො ශුන්‍යයේ සීමාවට ලඟා වීම නේද?

    ReplyDelete
    Replies
    1. ඔව් මොකක් හරි සීමාවක් තමයි...ශුන්‍යය මනින්න පුළුවනි නේ. ඒ කියන්නේ යමක් ශුන්‍යය වුනාම අපි දන්නවා දැන් ශුන්‍ය යි කියලා. ඒ නිසා ශුන්‍ය ය පාදම ට නැත්නම් boundary condition එකට ගන්න පුළුවනි. එතකොට ඒක කෙළවර වෙනවා.
      හැබැයි අනන්තය ගන්න බෑ, මොකද අපිට අනන්තය මනින්න බෑනේ. කෙළවරක් නෑනෙ. අනන්තය ට යන්නේ නැති වෙන්න තමයි අපි පාදම දාන්නේ. ඒ කියන්නේ කවදා හරි ඉවර කරන්න ඕනේ. හැබැයි ක්‍රම ලේඛනයේත් කෙළවර නොවන ශ්‍රිත දුවන්න ඕනේ නම් 'අනන්තය දක්වා දිවෙන' ලූප් පාවිච්චි කරනවා. මෙහෙම :
      while(true){
      //
      }

      Delete
  7. 5 වෙනි සෙමෙස්ටර් එකෙන් පස්සේ මැත ඉවර උණා. දෙයියනේ කියලා එදායින් පස්සේ අමතක කරලා දැම්මා. මෙහෙම දෙයක් තිබ්බා වෙන්ටෑති කියලා හිත හදා ගමුකො

    ReplyDelete
    Replies
    1. මැත්ස් කෑල්ල ඉතින් පුංචියි මෙතන. ප්‍රෝග්‍රෑමින් තමයි වැඩිපුර. මොනවා උනත් මම විශ්වාස කරන්නේ:
      ප්‍රෝග්‍රෑමින් වල පදනම -> පරිගණක විද්‍යාව
      පරිගණක විද්‍යාවේ පදනම -> ගණිතය

      Delete
    2. නැහැ නේද නිරෝ?

      පරිගණක විද්‍යාව කිවුවහම ඒක සමබන්ධ වෙන්නෙ වැඩිපුරම ඉලෙක්ට්‍රොනික්ස් පැත්තට නේද? නමුත් ප්‍රෝග්‍රෑමින් කියන්නෙ ඇල්ගොරිත්ම්ස්. ඒ කියන්නෙ කෙලින්ම සම්බන්ධ වෙන්නෙ ගණිතයට. ඒ කියන්නෙ ප්‍රෝග්‍රෑමින් වල පදනම -> ගණිතය

      අපට පරිගණකයක් නැතුවත් ප්‍රෝග්‍රෑම්ස් ලියන්ට පුළුවන්. ඇඩා ඔගස්ටා එයාගෙ මුල්ම කම්පියුටින් ප්‍රෝග්‍රෑම්ස් ලියද්දි චාල්ස් බැබේජ්ගෙ ඇනලිටිකල් එන්ජින් එක තිබුනෙ තියරිටිකල් මට්ටමේ.

      ගණිතය = සියළු විද්‍යාවන් ගේ රැජිණ ඈ

      Delete
    3. @ බුරා
      පරිගණක විද්‍යාවේ ඉලෙක්ට්‍රොනික්ස් තියෙන්නේ පුංචිම පුංචිම පුංචිම කෑල්ලක් බුරෝ. මගේ අවුරුදු 4 පරිගණක විද්‍යා උපාධියේ ඉලෙක්ට්‍රොනික්ස් එකම එක විෂයයි තිබුනේ..(හොඳ වෙලාවට- මොකද මට ඉලෙක්ට්‍රොනික්ස් පේන්න බැහැ :D)
      ඔව් අල්ගොරිත්ම්ස් තමයි පරිගණක විද්‍යාවේ හරය :)
      ඔයා ඔය ඉලෙක්ට්‍රොනික්ස් පැත්ත ගැන කියන්නේ computer engineering ගැන හරි IT හිතමින් වෙන්න ඕනේ. මම කියන්නේ computer science ගැන.
      computer science උපාධියක තියෙන විෂය මාලාවක් computer engineering සහ IT එක්ක සංසන්දනය කරලා බලන්න කෝ...

      //අපට පරිගණකයක් නැතුවත් ප්‍රෝග්‍රෑම්ස් ලියන්ට පුළුවන්//
      ඔව්...ඉතින් පරිගණක විද්‍යාවේ හරය ඉගෙන ගන්න පරිගණක ඕනේ නැහැනේ. දැන් අපි ගත්තොත් Data structures & Algorithms කියන්නේ ඕනෑම පරිගණක විද්‍යා උපාධියක මුලික විෂයක්. ඕක ඉගෙන ගන්න ඕනේ කළු ලැල්ලක්, චෝක් කෑල්ලක්, පොතක් සහ පැන්සලක් විතරයි. අපි ඉගෙන ගත්තෙත් ඉතින් එහෙමයි. Charles Leiserson ඕක උගන්නන්නේ ත් එහෙමයි :)

      //ගණිතය = සියළු විද්‍යාවන් ගේ රැජිණ ඈ
      අනිවා!
      'Pure mathematics is the queen of all sciences'
      මගේ උසස් පෙළ ශුද්ධ ගණිතය පොත උඩ ලියාගෙන තිබුනේ ඔහොම.

      ඒ වගේම ගණිතය තමයි විශ්ව භාෂාව වෙන්නෙත්!

      Delete
  8. මට නම් තේරුනේ මෙහෙමයි. දහයක් හදනවා. එක්කෙනෙක් ලොකුයි. අනෙක් එක්කෙනා ඊට වඩා පොඩියි. ඊලඟ එක්කෙනා තවත් පොඩියි. ඒ විදියට. ඕක ඉතින් නිරෝ ප්‍රායෝගිකව කරලා පෙන්නුවා නම් තමා නියම... :P :D

    ReplyDelete
    Replies
    1. පොකු ට තමා හොඳටම තේරුම් ගිහින් තියෙන්නේ..හැබැයි base case එක 10 ට වඩා අඩු කරමු නේද? මොකද දැන් ගෝලීය උණුසුම, ජනගහන අර්බුදය එහෙම දේවල් තියෙනවා නේ...:D

      Delete
    2. පොකු ට තමා හොඳටම තේරුම් ගිහින් තියෙන්නේ..හැබැයි base case එක 10 ට වඩා අඩු කරමු නේද? මොකද දැන් ගෝලීය උණුසුම, ජනගහන අර්බුදය එහෙම දේවල් තියෙනවා නේ...:D

      Delete
  9. අවුරුදු බර ගානකට පස්සෙ ඔය ගණන් ආයෙම කරන්න වුනා මේ ඊයෙ පෙරෙයිද පොඩි වැඩිදුර අධ්‍යාපන කටයුත්තකට පිටපොට ගහගෙන බැස්ස හින්ද...හෙහ්,හෙහ්,

    සහානුයාත ක්‍රමයට වඩා මම කැමති සහාධිපත්‍යය ක්‍රමයට...:)

    ReplyDelete
    Replies
    1. සහාධිපත්‍යය ක්‍රමය කියන්නේ මොකද්ද රවී?
      ගූගල් පරිවර්තකය බැලුවා - කියන්නේ 'condominium' කියලා...රවීගේ විහිළුවක්ද ? :)

      Delete
  10. මම මේ තේරුම් ගන්න උත්සාහ කරනවා තාම..

    ReplyDelete
    Replies
    1. ලොකුවට හිතන්න එපා...ඔයා අහල තියෙනවද අර පොඩි කාලේ සින්දුවක් තිබුනේ 'There's a Hole in My Bucket' කියලා...ඔය හෙන්රි සහ ලයිසා දෙන්න එක්ක කියන්නේ...ඉස්කෝලේ විවිධ ප්‍රසංග වල කියන සින්දුවක් ඒ දවස්වල. ඒකෙ concept එක ත් recursion තමයි.

      Delete
  11. බයෝ කරපු මටත් මේ පියෝ මැත්ස් පාඩම දිරෙව්වා කියන්නෙ ඉතින්, නිරෝ අක්කා සුපිරියටම කියල දීල තියෙනවා.

    මේ වගේ තව 'ලස්සන මැත්ස් පාඩම්' ටිකක් කියල දෙන්නකො.

    ReplyDelete
    Replies
    1. බස්සිට කොහොමත් නොතේරෙන දෙයක් නැහැනෙ. ඔය මොලෙන් කෑල්ලක් ගන්න පුළුවන් නම් මරු

      Delete
    2. එහෙනම් ගොඩක් සතුටුයි බස්සි :)
      බොරු කියන්නේ මොකටද...උසස් පෙළ ගණිතය දැන් බාගයක්වත් මතක නෑ. BSc එකට ඉගෙන ගත් පරිගණක විද්‍යාවට අදාළ ගණිතය ත් එහෙන් මෙහෙන් තමයි මතක... ඔය ශ්‍රේණි, boolean algebra, matrices,සංඛ්‍යානය වගේ කෑලි. ඉඩ තියෙන විදියට ඔය මතක කෑලි ලියන්න තමයි ඉන්නේ...

      Delete