আজকে আমরা কোন একটা লিনিয়ার রিকারেন্স কে কীভাবে ম্যাট্রিক্স এর সাহায্যে সলভ করতে হয় তা দেখব আর কেন করতে হয় তা জানব । এর পরের পর্বে আমরা কিছু উদাহরণ দিয়ে পুরো ব্যাপারটা এপ্লিকেনস দেখব ।

লিনিয়ার রিকারেন্স কি?

reference:Brilliant.org

সোজা বাংলায় যদি আমরা আগের কোন একটা জিনিসের n তম টার্ম কে হিসেব করার জন্য  আগের 1 থেকে শুরু করে (n-1) তম টার্ম গুলোকে ব্যবহার করি । অর্থাৎ ছোট ছোট জিনিস গুলো আরো বড় জিনিসর মানগুলোকে বানাবে এবং যেহেতু আমরা সেম রকমের জিনিস বারবার বানাই আর সেম ভাবে বানাই তাই আমরা রিকার্সনের ব্যবহার করে এরকম প্রবলেম সলভ করি । আর পুরো ব্যাপারটিকে লিনিয়ার বলার কারণ এখানে আমরা যখন আগের টার্মগুলোকে  ব্যবহার করে নতুন টার্মগুলোকে বানাব তখন সেখানে অবশ্যই আগের টার্মগুলোর ঘাত ১ থাকবে । কোনভাবেই ১ এর চাইতে বেশি হবে না ।

recursion এর ব্যাপারে জানার জন্য আপনারা আমাদের সবশিক্ষার এই লিঙ্ক দেখতে পারেন Recursion.

ম্যাট্রিক্স দিয়ে প্রকাশঃ

এখন আমরা আমাদের আলোচনার সবচাইতে গুরতবপূর্ণ অংশে চলে এসেছি । আমরা এখন দেখব কীভাবে দেয়া কোন লিনিয়ার রিকারেন্স কে ম্যাট্রিক্সে নিয়ে আমরা সমাধান করতে পারি । এর জন্য আমরা আমাদের অনেক পরিচিত একটি রিকারেন্স চুজ করব । আর সেটি হলো ফিবোনাকি সিকুয়েন্স । যেখানে এই রিকারেন্স কোন টার্ম তার আগের দুইটি টার্ম এর যোগফলের সমান এবং শুরুর দুইটি মান হল ১ এবং ১ । আমরা এটিকে এভাবে লিখতে পারি ।

f(0) = 1

f(1)=1

f(2)=f(1)+f(0)=2

f(3)=f(2)+f(1)=3

…….

f(n)=f(n-1)+f(n-2)

আচ্ছা তাহলে আমরা আমাদের লিনিয়ার রিকারেনস পেয়ে গিয়েছি । এখন আমরা এই সম্প্ররকটিকে ম্যাট্রিক্স এর সাহায্যে প্রকাশ করব ।

আচ্ছা তাহলে আমাদের n তম টার্ম f(n)=f(n-1)+f(n-2) আর (n-1) তম টার্ম f(n-1)=f(n-2)+f(n-3) এখন আমরা লিখতে পারি,

এইখানে আমরা সমান সাইনের বামপাশে একটা ম্যাট্রিক্স ডিফাইন করেছি যার প্রথম রো আমাকে f(n) এর মান দিবে এবং তারপ্রের রো আমাকে f(n-1) এর মান দিবে । আর ডান পাশে তার ভ্যালু লিখেছি । এখন কি আমরা এটাকে ভেঙ্গে দুইটা ম্যাট্রিক্স এর গুণফল হিসেবে লিখতে পারি না ?

 

আমরা এখন আমাদের ডান সাইডকে দুইটা ম্যাট্রিক্স এর গুণফল হিসেবে প্রকাশ করলাম । এখন প্রশ্ন আসতে পারে এই কাজটা কেন করলাম । আমরা এখন মাঝখানের এই পুরো কন্সট্যান্ট ভ্যালু দিয়ে তৈরী ম্যাট্রিক্সটা একটু খেয়াল করি । আমরা মূলত বাম পাশের ম্যাট্রিক্স টার মান বার করব ডান পাশের দুইটা ম্যাট্রিক্স কে গুন করে । যেখানে একটা কন্সট্যান্ট ম্যাট্রিক্স আরেকটা সমান সাইনের বামপাশের ম্যাট্রিক্স টার মতোই একটা ম্যাট্রিক্স যেটা আগে যেখানে f(n) আর f(n-1) এর মান দিচ্ছিল এখন সেটা এখানে f(n-1) আর f(n-2) এর মান দিবে ।  আমরা কন্সট্যান্ট ম্যাট্রিক্সটার নাম দিলাম A আর অপরটার নাম দিলাম B.  তো যেহেতু এটা একটা লিনিয়ার রিকারেন্স সেহেতু আমরা আবার ডান পাশের B ম্যাট্রিক্সটাকে ও আবার আগের মতো ভেঙ্গে লিখতে পারি ।

তাহলে বাস আমাদের কেল্লা ফতে ! আমাদের কাজ শেষ । এভাবে আমরা আমাদের প্রতিবারে তৈরী নতুন B ম্যাট্রিক্সটাকে ভাঙ্গতে থাকব যতক্ষণ না পর্যন্ত আমরা আমাদের একেবারে রিকারেন্সের শুরুর বেস কেসে না পৌছাই । প্রতি স্টেপে আমাদের B গুলা ভাঙ্গতে থাকবে আর নতুন করে A আগের গুণের সিকুয়েন্সের সাথে নতুন করে গুন হয়ে সিকুয়েন্স বাড়াতে থাকবে । আমরা যখন এই ম্যাট্রিক্সে পৌছাব তখন আমরা তো অলরেডি f(1) আর f(0) এর মান জানি । তাহলে কি তাদের মান বসিয়ে দিতে পারি না? তাহলে আমরা দেখতে পারছি যদি আমরা f(n) আর f(n-1) এর মান বার করতে চাই তাহলে শুধু A কে “কিছু” বার গুণ দেয়া লাগছে আর তারপরে জাস্ট তার সাথে আমাদের f(1) আর f(0) এর ম্যাট্রিক্স টা গুণ করলেই আমরা মানে পেয়ে যাচ্ছি । এখন “এই কিছু” বার বলতে কতোবার গুন দেয়া লাগবে বার করা বেশি কঠিন কিছু না । খুব সহজেই আমরা দেখতে পারি পার স্টেপে একটা করে B ভাঙ্গছে আর A গুন হচ্ছে এরকম বেস এ আসতে স্টেপ লাগছে কয়টা ? শুরুর ম্যাট্রিক্সের প্রথম রো মান বের কর তে চাচ্ছিল f(n) এর আর আমরা শেষ করেছি f(1) এর মান বসিয়ে । মাঝে প্রতি ভাঙ্গাতে একটা করে গুন হয়েছে । তাহলে টোটাল গুণ হলো (n-1) টা । তাহলে আমাদের শুরুর ম্যাট্রিক্স এর মান বের করার উপায় A কে আমরা (n-1) বার গুন দিব আর তারপরে আমরা এর সাথে [f(1) f(0)] এইটা গুন দিব । আর তাতেই আমরা আমাদের শুরুর ম্যাট্রিক্স এর মান পেয়ে যাব ।

 

এটা কেন করলাম ?

আমরা যদি খেয়াল করি তাহলে দেখব একটা লিনিয়ার রিকারেন্সের কোন ভ্যালুর মান যদি আমরা মেমোরাইজ ও করি ( মানে সোজা কথায় যদি স্টেট করে অ্যারেতে সেভ করে রাখি) তাহলে সেটা n তম টার্ম হলে আমার আগের (n-1) টা টার্মের মান হিসেব করে সেভ করে রাখা লাগছে আর সেই সাথে সবগুলা হিসেব ও করে রাখা লাগছে । কিন্তু যদি আমরা এভাবে ম্যাট্রিক্স এর সাহায্যে করি তাহলে প্রথম কথা আমার আগের সবগুলার মান সেভ করা দরকার নেই আর সেই সাথে আমার আগের (n-1) তম টার্ম ও টেকনিকালি বার করা দরকার নেই ! কারণ আমাদের আসলে কি করতে হচ্ছে বার বার শুধু A ম্যাট্রিক্স কে (n-1) বার গুন দেয়া লাগছে আর এর সাথে আমার একদম বেস মান দিয়ে তৈরী যেই ম্যাট্রিক্স টা সেটা একবার গুন দেয়া লাগছে । আমাদের মেমোরি কমপ্লেক্সিটি একেবারে নাই হয়ে যাচ্ছে কাইনড অফ আর আমরা ফাস্ট এক্সপোনেনশিয়ালের মাধ্বজমে ম্যাট্রিক্স অ্যাপ্রোক্সিমেটলি big O of (row size ^3)*log(n) এই কমপ্লেক্সিটিতে বার করতে পারি । যারা জানি না তার আমাদের এই লেখাটা একটু দেখে নিতে পারি http://shoshikkha.com/archives/4356 

এই লেখাটিতে মূলত বড় নাম্বারের গুনের ক্ষেত্রে বলা হয়েছে কিন্তু আমরা সেম কনসেপ্ট ম্যাট্রিক্স এর ক্ষেত্রেও এমপলাই করতে পারি । এখানে প্রতি স্টেপে আমরা পাওয়ার ভাঙ্গি আর তারপরে গুন করে করে মার্জ করি । এখন গুনের ক্ষেত্রে আমরা ম্যাট্রিক্স গুন করব শুধু । আমরা ট্রাই করব এইটা । না পারলেও চিন্তার কোন কারণ নেই । আমরা পরের পর্বে যখন আরো অনেক এক্সামপল দেখাব তখন এমনিতেই আইডিয়া হয়ে যাবে ।

পাদটীকাঃ

আচ্ছা এই পার্ট পুরোপরি আমার ব্যক্তিগত অভিমত । আপনার সাথে নাও মিলতে পারে । আমার একস্যার বলতেন, তোমার নিজের মধ্যে যেই আইডিওলজি আছে তুমি কখনোই সেটা কারও ওপর ফলাবে না । নিজেরটা এক্সপ্রেস করতে পারো । কিন্তু কখনোই চাপিয়ে দিবে না । তো এটা মানা না মানা সম্পূর্ণ আপনার ব্যক্তিগত ব্যাপার । আপনার নিজস্ব একটা জগত আছে চিন্তার । ঐটা লজিকালি যেটা ঠিক বলে সেটাকেই আপনি মানবেন ।

আমি এই লেখাটা যখন লিখি সেদিন ১৬ ডিসেম্বর ছিল, আমাদের প্রাণপ্রিয় বিজয় দিবস । দেশপ্রেম কী ? এই কোশ্চেন এর উতত্রের কোন শেষ নেই,শুরু নেই । আমার কাছে পারসোনালি দেশপ্রেম মনে হয়, অনেক ছোট একটা কিছুকে । সেটা হলো, আপনার নিজের দায়িত্ব পালন করা । আপনি এই দেশের নাগরিক । আপনার কিছু অল্প অল্প কাজ আছে, আপনার এলাকায়,পরিবারে,আপনি যেখানে চাকরি করেন বা পড়েন সেই খানে। আমার মনে হয় দেশ প্রেম যেহেতু অনেক বড় একটা কিছু ,তাই এতো বেশি বেশি জিনিস নিয়ে ভাববার দরকার নেই । আপনি শুধু আপনার দায়তিবটুকু ভালবেসে পালন করুন । অনেক ঝামেলায় পড়বেন । তাও করেন। এভাবে একশটা মানুষ যদি সেমভাবে একা একা চেষ্টা করে দেখবেন দেশ বদলে গেছে । ভাল থাকুন ।