Must Known Algorithms By a CS Student
October 29, 2021 | Tharindu Kariyawasam
ගණිතය සහ පරිගණක විද්‍යාව ආශ්‍රිතව මතුවන බොහොමයක් ගැටළුවලට විසඳුම් ගොඩනැගෙන්නේ Algorithm අනුසාරයෙනි. Algorithm එකක් යන්න, යම් ගැටලුවක් විසඳීමට භාවිතා කරන තර්කානුකූලව ගොඩනගන ලද නිශ්චිත ක්‍රියාපටිපාටියක් ලෙස නිර්වචනය කළ හැකිය.
Algorithm නිරූපණය කළ හැකි ආකාර කිහිපයක් පවතී.
1. ස්වාභාවික භාෂා (Natural Languages) භාවිතයෙන්
2. ප්‍රවාහ සටහන් (Flowchart) භාවිතයෙන්
3. ව්‍යාජ කේත (Pseudocode) භාවිතයෙන්
4. ක්‍රමලේඛන භාෂා (Programming Languages) භාවිතයෙන්
ස්වාභාවික භාෂා නොඑසේ නම් Natural languages භාවිතයෙන්, පරිගණක විද්‍යාව පිළිබඳ දැනුමක් ඇති අයට සහ නොමැති අයටද තේරුම් ගත හැකි වන ආකාරයට Algorithm ඉදිරිපත් කිරීමට හැකියි. නමුත් මෙහිදී ප්‍රකාශ වන අදහස පිළිබඳ අවිනිශ්චිතතාවක් ඇති වීමට ඉඩක් පවතී. Flowchart සහ Pseudocode භාවිතයෙන් ඊට සාපේක්ෂව විධිමත් ආකාරයට Algorithm ඉදිරිපත් කළ හැක. මේ නිසා පරිගණක විද්‍යා ක්ෂේත්‍රයේ කටයුතු කරන බොහොමයක් දෙනා Algorithm නිරූපණය කිරීමට Flowchart සහ Pseudocode යොදා ගනිති. Natural languages හෝ Flowchart හෝ Pseudocode හෝ භාවිතයෙන් ගොඩ නගන ලද ඇල්ගොරිතමය Programming Language එකක් යොදා ගනිමින් ක්‍රියාවට නංවයි.
පරිගණක විද්‍යා ක්ෂේත්‍රයේ සිටින සියලු දෙනාටම Algorithm පිළිබඳ දැනුමක් තිබීම අත්‍යවශ්‍ය දෙයකි. මේ ලිපියෙන් පරිගණක විද්‍යා ක්ෂේත්‍රයේදී වැදගත් වන Algorithm කිහිපයක් පිළිබඳව සාකච්ඡා කරමු.
Sorting Algorithms
Sorting Algorithms යනු පරිගණක විද්‍යාවේදී වැඩි අවධානයක් ලබා දෙන Algorithm වර්ගයකි. මෙහිදී මූලිකවම සිදු කරන්නේ ලැයිස්තුවක පවතින අවයව නිශ්චිත පිළිවෙලකට අනුව යළි සැකසීමයි. ඒ ඒ අවස්ථාවන්ට අනුව භාවිතයට ගැනීම සඳහා Sorting Algorithms රාශියක් පවතී. Merge Sort, Quick Sort, Selection Sort, Bubble Sort, Counting Sort, Bucket Sort, Heap Sort ඒ අතරින් කිහිපයක්. අපි දැන් තව දුරටත් Merge Sort සහ Quick Sort පිළිබඳව විමසා බලමු.
Merge Sort
මෙම Algorithm එක Divide and Conquer Algorithms ගණයට අයත් වේ. මෙහිදී සිදු කරන්නේ දී ඇති array එක කොටස් දෙකකට බෙදා එම කොටස් දෙකට නැවතත් Merge Sort Algorithm එක යොදා sort කරන ලද කොටස් දෙක merge function එකක් භාවිතයෙන් එකාබද්ධ කිරීමයි.
Quick Sort
Quick Sort Algorithm එකත් Merge Sort මෙන් Divide and Conquer Algorithms ගණයට අයත් වේ. මෙම Algorithm එකේදී සිදුකරන්නේ දී ඇති array එකෙන් element එකක් pivot element එක ලෙස තෝරා ගෙන එයට වඩා අඩු අගයන් සහිත elements එයට පෙර සහ ඊට වඩා වැඩි අගයන් සහිත elements එයට පසුවත් එන ආකාරයට array එක යළි සැකසීමයි. pivot element එක ලෙස තෝරා ගන්නා ආකාරය අනුව Quick Sort අකාර කිහිපයක් පවතියි.
විද්‍යුත් වාණිජ කටයුතු වලදී අදාළ තොරතුරු සංවිධානාත්මක අකාරයට සැකසීමේදි Sorting Algorithms භාවිත වේ.
Search Algorithms
Search Algorithms නිර්මාණය කර තිබෙන්නේ data structure එකකින් අපට අවශ්‍ය element එක පරීක්ෂා කිරීමට හෝ ලබා ගැනීම සඳහා වේ. එම Algorithms ඒවායේ ක්‍රියාකාරිත්වය අනුව ආකාර දෙකකට වර්ග කළ හැකියි . ඒ Sequential Search සහ Interval Search ලෙසයි. Sequential Search වලදී data structure එකේ අපට අවශ්‍ය element එක හමු වන තුරු සෑම element එකක්ම අනුපිළිවෙලින් පරීක්ෂා කර ගෙන යයි. Interval Search භාවිතා කරන්නේ Sort කරන ලද data structure සඳහා වේ. එහිදී data structure එකේ මධ්‍යයේ පවතින element එක සලකා අපට අවශ්‍ය element එක පවතින කොටස තෝරා එම කොටසට නැවතත් මෙම Algorithm එක යෙදීම සිදුකරයි. අපි දැන් Search Algorithms කිහිපයක් පිළිබඳව විමසා බලමු.
Binary Search
මෙය Interval Search වර්ගයේ Algorithm එකකි. එනම් දී ඇති Sort කරන ලද array එකේ මධ්‍යයේ පවතින අගය සලකා array එක කොටස් දෙකකට බෙදා අපට අවශ්‍ය අගය ලැබෙන තෙක් හෝ array එක තව දුරටත් කොටස් කර නොහැකිවන තෙක් අදාළ අගය පවතින කොටසට නැවත නැවතත් මෙය සිදු කිරීමයි. Git වලදී debug කිරීමේදී යොදා ගන්නා git bisect හි භාවිතා වන්නේ Binary Search Algorithm එකයි.
Depth First Search
Depth First Search Algorithm එක tree සහ graph වල traversing සහ searching සිදුකරන Algorithm එකක් වේ. මෙහිදී සිදු වන්නේ root node එකෙන් ආරම්භ කර වම් කෙලවරේ ඇති ශාඛාව (leftmost branch) ඔස්සේ leaf node එකක් හමුවනතුරු ගමන් කර නැවතත් ආපසු හැරී දකුණුපස ශාඛා (right branches) ඔස්සේ ගමන් කිරීමයි.
දෙන ලද graph එකක cycle පවතීද යන්න තහවුරු කරගැනීමට මෙම Algorithm එක භාවිත වේ. තවද දෙන ලද vertices දෙකක් අතර මාර්ගය සොයා ගැනීමට ද මෙය භාවිත වේ.
Breadth First Search
Breadth First Search Algorithm එකද Depth First Search මෙන් tree සහ graph වල traversing සහ searching සිදුකරන Algorithm එකකි. මෙහිදී root node එකෙන් ආරම්භ කර එකම මට්ටමේ පවතින (neighborhood) node සියල්ල පරීක්ෂා කිරීමෙන් පසු ඊට පහළ මට්ටම වෙත ගමන් කරයි.
Breadth-First Search Algorithm එක search engines වල web-crawling වලදී භාවිත වේ. තවද unweighted graph වල Shortest Path සහ Minimum Spanning Tree ලබා ගැනීමටත් මෙය භාවිතා කරයි
Dynamic Programming
Dynamic Programming වලදී සිදුවන්නේ සංකීර්ණ ගැටලුවක් කුඩා ගැටලු වලට වෙන් කොට එවායේ විසඳුම් මතකයේ ගබඩා කර තබා ඒවා භාවිතයෙන් සංකීර්ණ ගැටලුව විසඳීමයි. මෙය භාවිත කරමින් සාමාන්‍ය recursive functions වල ක්‍රියාකාරිත්වය වඩාත් ප්‍රශස්ථ ආකාරයෙන් සිදු කර හැකි වේ.
මෙම සංකල්පය භාවිතා වන අවස්ථාවන්ට උදාහරණ ලෙස
Ugly Numbers
Fibonacci Numbers
Binomial Coefficient
Permutation Coefficient දැක්විය හැකි වේ.
Data Structures
Data Structures සහ Algorithms යනු එකිනෙකට සම්බන්ධ සංකල්ප දෙකක්. ඉහත සාකච්ඡා කළ Algorithms සියල්ලම වගේ Data Structures වලට අදාළව ගොඩනැගුණු ඒවා. Data Structures යනු පරිගණකවල දත්ත සංවිධානාත්මකව ඇසිරීම සඳහා භාවිතා වන්නකි. Array, Linked List, Stack, Queue, Binary Search Tree, Heap, Hash Table, Graph ඒ අතරින් කිහිපයක්. ඉහත Algorithms වලට අමතරව Data Structures වල සිදුකරන insertion, deletion ආදී වූ operations වලට අදාළවද වෙන වෙනම සැකසුණු ඇල්ගොරිතම් පවතියි. අපි තවදුරටත් Linked List, Hash Table සහ Graph පිළිබඳව විමසා බලමු.
Linked List
මෙහි ඇති elements, nodes ලෙස හැඳින්වේ. සාමාන්‍යයෙන් සෑම node එකක්ම කොටස් දෙකකින් සමන්විත වේ. ඒවා data field එක සහ reference එක ලෙසින් හඳුන්වයි. Linked List යනු linear data structure එකකි. එනම් සෑම node එකක්ම ඊට පෙර සහ පසු node වලට සම්බන්ධ වී පවතියි. නමුත් මේවා ගබඩා වී ඇත්තේ එකිනෙකට යාබද memory locations වල නොවේ. Pointers භාවිතයෙන් ඒවා එකිනෙක සම්බන්ධ වේ. මෙහි පළමු node එක head ලෙසත් අවසාන node එක tail ලෙසත් නම් කරයි.
Hash Table
මෙහිදී Hash function එකක් භාවිතා කරමින් දී ඇති අගයන් Hash Table එකේ index සමග ගැළපීම සිදුකරයි. ඉන්පසු එම index භාවිතයෙන් අදාළ අගයන් ලබාගැනීම සිදුකරයි. මෙම ක්‍රියාවලියේ කාර්යක්ෂමතාව Hash function එක මත රඳා පවතියි.
Graph
Graph යනු vertices සහ edges වලින් සමන්විත වන non-linear data structure එකකි. මෙහි edges මගින් vertices සම්බන්ධ කරයි. නගර අතර මාර්ග, දුරකථන ජාලා, පරිපථ ජාලා ආදී වූ ජාල නිරූපණය කිරීම සඳහා Graph යොදා ගනියි.
සටහන - තරිඳු කාරියවසම්