ইউক্লিডিয়ান অ্যালগরিদম হলো দুটি পূর্ণসংখ্যার মধ্যে গরিষ্ঠ সাধারণ গুণনীয়ক (GCD) বা গসাগু নির্ণয়ের একটি দক্ষ পদ্ধতি। প্রাচীন গ্রীক গণিতবিদ ইউক্লিড এটি উদ্ভাবন করেন, যা পূর্ণসংখ্যাগুলোর বিভাজনমূলক সম্পর্ক নির্ধারণ করতে ব্যবহৃত হয়। এই অ্যালগরিদমটি পুনরাবৃত্তি (recursion) বা পুনরায় গণনার মাধ্যমে কাজ করে এবং দ্রুত গসাগু নির্ণয়ে সহায়ক।
ইউক্লিডিয়ান অ্যালগরিদমের ধাপসমূহ:
- দুটি সংখ্যা \( a \) এবং \( b \) নিন, যেখানে \( a > b \)।
- \( a \) কে \( b \) দ্বারা ভাগ করুন এবং ভাগশেষ বের করুন, অর্থাৎ \( r = a \mod b \)।
- যদি \( r = 0 \) হয়, তাহলে \( b \) হলো \( a \) এবং \( b \)-এর গসাগু (GCD)।
- যদি \( r \neq 0 \) হয়, তাহলে \( a = b \) এবং \( b = r \) হিসেবে পুনরায় প্রক্রিয়া শুরু করুন।
- পুনরাবৃত্তি চালিয়ে যান যতক্ষণ না অবশিষ্টাংশ শূন্য হয়। শূন্য অবশিষ্টাংশ পাওয়ার ঠিক আগের \( b \)-এর মানই গসাগু হবে।
উদাহরণ:
ধরি, \( a = 56 \) এবং \( b = 98 \)।
- \( 98 \mod 56 = 42 \)
- \( 56 \mod 42 = 14 \)
- \( 42 \mod 14 = 0 \)
এখানে শেষ ভাগশেষ ০, তাই \( GCD(56, 98) = 14 \)।
ইউক্লিডিয়ান অ্যালগরিদমটি সংখ্যাতত্ত্ব, ক্রিপ্টোগ্রাফি, এবং গণিতের অন্যান্য শাখায় গসাগু নির্ণয়ে ব্যাপকভাবে ব্যবহৃত হয়।
গসিয়ান এলিমিনেশন (Gaussian Elimination)
গসিয়ান এলিমিনেশন হলো একটি অ্যালগরিদম যা একাধিক চলকের সাথে সমীকরণ সিস্টেম সমাধানের জন্য ব্যবহৃত হয়। এই প্রক্রিয়াটি সমীকরণগুলিকে রো-রিডাকশন (Row Reduction) এর মাধ্যমে সরল করে এবং একটি সমাধান নির্ণয় করে। গসিয়ান এলিমিনেশন, মূলত একটি ম্যাট্রিক্সকে ধাপে ধাপে রিডিউসড রো-একলন ফর্ম (RREF) আকারে নিয়ে আসে, যেখানে প্রতিটি চলক একটি নির্দিষ্ট মান গ্রহণ করতে পারে।
গসিয়ান এলিমিনেশনের ধাপসমূহ:
- সমীকরণগুলোকে একটি ম্যাট্রিক্স আকারে প্রকাশ করুন।
- প্রথম সারির প্রথম উপাদানটিকে পিভট এলিমেন্ট হিসেবে নির্বাচন করুন।
- পিভট এলিমেন্টের নিচের সারিগুলোকে এমনভাবে বদলান যাতে ঐ কলামের সব নিচের উপাদান শূন্য হয়।
- একই প্রক্রিয়া অন্য কলামের পিভট এলিমেন্টের জন্য পুনরাবৃত্তি করুন যতক্ষণ না ম্যাট্রিক্সটি একটি ত্রিভুজ আকারে রূপান্তরিত হয়।
- সব রো-একলন সম্পন্ন হলে রিডিউসড রো-একলন ফর্মে (RREF) ম্যাট্রিক্স রূপান্তরিত হয়, এবং এর ফলে চলকের মান নির্ধারণ করা সম্ভব হয়।
উদাহরণ:
ধরি, নিচের সমীকরণগুলো সমাধান করতে হবে:
\[
x + y + z = 6
\]
\[
2y + 5z = -4
\]
\[
2x + 5y - z = 27
\]
এই সিস্টেমকে একটি ম্যাট্রিক্স আকারে প্রকাশ করে গসিয়ান এলিমিনেশন ব্যবহার করে সমাধান করা সম্ভব। পদ্ধতিটি ধাপে ধাপে কাজ করে প্রতিটি চলকের জন্য নির্দিষ্ট মান নির্ধারণ করে।
গসিয়ান এলিমিনেশন অ্যালজেব্রার জটিল সমস্যা সমাধানে গুরুত্বপূর্ণ ভূমিকা পালন করে, বিশেষত বড় বড় লিনিয়ার সিস্টেমের সমাধানে।
Read more
