#Algorithm_Part :-> 01
গতদিন সবাই আমাকে ডাটা-স্ক্যাকচার আর অ্যালগরিদম নিয়ে পোস্ট করতে বলেছিলেন। তার ধারাবাহিকতায় আমি চেয়েছিলাম একদম বেসিক থেকে শুরু করতে, তাই আজকে আমি অ্যালগরিদম নিয়ে কিছু বেসিক ধারণা দিলাম, নেক্সট পার্ট এ ডাটা স্ক্যাকচার নিয়ে দিব।
#অ্যালগরিদম বলতে আমরা একদম সহজ কথায় একবাক্য যা বুঝবো সেটা হলো, অ্যালগরিদম অর্থ ধাপে ধাপে একটা সমস্যার সমাধান করা। অর্থাৎ একটি সমস্যাকে কয়েকটি ধাপে ভেঙে প্রত্যেকটি ধাপ পর্যায়ক্রমে সমাধান করে সমগ্র সমস্যার সমাধান করাকে আমরা অ্যালগরিদম বলতে পারি। আমরা জানি যে, কম্পিউটার মানুষের ভাষা বোঝে না। কম্পিউটার শুধুমাত্র বাইনারী বা দুই ডিজিট সংখ্যা বুঝে আর সেটা হলো, ০ আর ১। কম্পিউটারের সাথে যোগাযোগের জন্য, প্রোগ্রামার প্রোগ্রামিং ভাষা ব্যবহার করে। মানুষের ভাষা কম্পিউটারকে বুঝানোর জন্য সাধারনত অনেক ধরনের প্রোগ্রামিং ভাষা ব্যবহার করা হয় আর সেই সমস্যা সমাধানের জন্য প্রয়োজন সঠিক দিক-নির্দেশনা এবং পরিকল্পনা আর সেটাই Algorithm। তার মানে আমরা কি বলতে পারি, কোন সমস্যা সমাধানের জন্য সুনির্দিষ্ট ধারাবাহিক নিয়মাবলীকে অ্যালগরিদম বলা হয়। এটি মূলত সমস্যা সমাধানের জন্য ব্যবহার করা হয়। একটা সহজ উদাহরণ দিয়ে আপনাদের এই ব্যাপারে আর একটু স্পষ্ট ধারণা দেই।
ধরো,তোমাকে আমি একটা কাজ দিলাম,কাজটা হলো তুমি আমাকে এক কাপ চা বানিয়ে দিবা।
কাজঃ চা বানাবা।
অ্যালগরিদমঃ ( চা বানানো পদ্ধতি)
১. প্রথমে একটি পাত্রে গরম পানি করা।
২.তার মধ্যে চা পাতা দিয়ে লিকার বানানো।
৩. চায়ের কাপে লিকার, দুধ ও পরিমান মত চিনি দিয়ে ভালোমত মিক্স করা।
৪. সবশেষে চা পরিবেশন করা।
তুমি যে চা বানানোর কাজটা করলা,এটা হচ্ছে একটা সমস্যা। যেটাকে তুমি চারটা ধাপে সমাধান করেছো।
এইযে সুনির্দিষ্ট কোন সমস্যা সমাধানের জন্য সসীম সংখ্যক[ ৪ টি ধাপ] অনুক্রমিক [একটার পর একটা ] নির্দেশের সেটকে অ্যালগরিদম বলে। আশাকরি এবার বুঝে গেছো 
অ্যালগরিদমের বৈশিষ্ট্যঃ অ্যালগরিদমের কিছু বৈশিষ্ট্য আছে, যেগুলো দেখলে আমরা বুঝবো যে এটা একটা অ্যালগরিদম।
১. ইনপুট — শূন্য অথবা তারো বেশি।
২. আউপুট — নূন্যতম একটা আউটপুট থাকবেই।
৩.স্পষ্টতা — প্রত্যেকটি ধাপ স্পষ্ট হতে হবে।
৪. সসীমতা — ১ টা বা ১ কোটি ধাপ হোক, কিন্তু সেটা যেনো এরকম সীমিত হয়, মানে এটার যেনো শেষ থাকে।
৫. কার্যকারিতা — যাই কিছু থাকুক, সেটা যেনো অপ্রয়োজনীয় কিছু না হয়।
কিভাবে একটি অ্যালগরিদম এনালাইসিস করবো?
এখন আমরা শিখবো, কিভাবে একটা অ্যালগরিদম এনালাইসিস অর্থাৎ অ্যালগরিদম কে বিশ্লেষণ করা হয়। এজন্য শুরুতেই যে কথাটা মাথায় আসে,সেটা হলো কেনো একটা অ্যালগরিদমকে এনালাইসিস করবো,কেনো এটা গুরুত্বপূর্ণ?
চা বানানোর উদাহরণটা আবার মনে করা যাক,
১ম পদ্ধতিঃ
১. প্রথমে একটি পাত্রে গরম পানি করা।
২.তার মধ্যে চা পাতা দিয়ে লিকার বানানো।
৩. চায়ের কাপে লিকার, দুধ ও পরিমান মত চিনি দিয়ে ভালোমত মিক্স করা।
৪. সবশেষে চা পরিবেশন করা।
২য় পদ্ধতিঃ
১) একটি টি মেকার মেশিনে পরিমানমত পানি,চিনি,লিকার দেওয়া।
২)ব্যাস! যখন চা হয়ে যাবে। সবশেষে চা পরিবেশন করা।
উপরের, দুটো পদ্ধতি থেকে কোনটি বেশি সহজ ? নিশ্চই তুমি বলবে দ্বিতীয়টি।
কেননা এটা কম সময়ে ও সহজে করা যায়।ঠিক,তেমনি কম্পিউটার প্রোগ্রাম দ্বারা সুনির্দিষ্ট কোন সমস্যা সমাধানের জন্য অনেক অ্যালগরিদম রয়েছে, তার মধ্যে কোনটা সবচেয়ে দ্রুত ও কার্যকরী সেটা বুঝার জন্যই আমাদের অ্যালগরিদম এনালাইসিস জানতে হয়। আমরা কয়েকটা বিষয়ের উপর সাধারণত এনালাইসিস করে থাকি।
যেমন : টাইম, স্পেস, ডাটা ট্রান্সফার, পাওয়ার,সিপিইউ রেজিস্টারস ইত্যাদি।
অ্যালগরিদম এনালাইসিসে মূলত টাইম ও স্পেস এনালাইসিস টা বেশি করে থাকি আমরা। টাইম এনালাইসিস কে আমরা বলি টাইম কমপ্লেক্সিটি , স্পেস এনালাইসিস কে বলি স্পেস কমপ্লেক্সিটি।
টাইম কমপ্লেক্সিটি কি ?
কোন একটি অ্যালগরিদম যে সমস্যা সমাধানের জন্য তৈরি করা হয়েছে তা সমাধান করতে কতটুকু সময় নিচ্ছে,এটাকেই আমরা বলবো টাইম কমপ্লেক্সিটি ।
স্পেস কমপ্লেক্সিটি কি ?
কোন একটি অ্যালগরিদম সমস্যা সমাধানের সময় কতখানি কম্পিউটার মেমরি ব্যাবহার করছে,এটাই হচ্ছে স্পেস কমপ্লেক্সিটি ।
এখন, অ্যালগোরিদম এর কিছু বাস্তবিক উদাহরণ দেই তোমাদের। অনলাইন কেনাকাটার ওয়েবসাইটগুলোতে বিভিন্ন আকর্ষণীয় পণ্যের যে রেকমেন্ডেশন দেখি আমরা সেগুলো সবই অ্যালগরিদমের খেলা। এটা ছাড়াও তোমাদের আজকে আরও কিছু অ্যালগোরিদম সম্পর্কে পরিচয় করিয়ে দেই সেই সাথে বাস্তবিক প্রয়োগ দেখায়, যেটা তোমাদের সারাজীবন কাজে লাগবে।
১. Data compression algorithms :-> কম্পিউটারের সাধারণ ব্যবহারকারী হিসেবে আমরা কিন্তু প্রায় প্রতিদিনই বিভিন্ন ধরনের data compress করে থাকি। যেমন কোন একটা ফোল্ডারকে মেইলে পাঠানোর আগে সেটিকে zip file এ কনভার্ট করে এরপর মেইলে এটাচ করি। বা কখনো কোন audio, video বা image কে কনভার্ট করে ছোট ফাইলে রূপান্তর করি। এগুলো সবই ডাটা কম্প্রেশনের উদাহরণ।
২. Random Number Generation :-> কোন একটা হাসপাতাল নির্মান বা অন্য কোন ব্যাপারে তহবিল সংগ্রহের জন্য ১ লাখ লটারির টিকেট ছাড়া হল। ড্র এর দিন ১০টা টিকেট বাক্স থেকে তোলা হবে। এই দশটা টিকেটের মালিকরাই হবেন বিজয়ী। এটা ম্যানুয়াল্যি করতে চাইলে কি পরিমান ঝামেলা পোহাতে হবে বলাই বাহুল্য। কিন্তু এমন একটা সফটওয়্যার যদি ডিজাইন করা যায় যার মধ্যে একটা রেঞ্জ দিয়ে দিলে সেই রেঞ্জের মধ্যে থেকে সে র্যান্ডমলি একটার পর একটা নাম্বার আউটপুট দিতে থাকবে। তাহলে এই সফটওয়্যার ডিজাইন করতে অবশ্যই র্যান্ডম নাম্বার জেনারেট করার এলগরিদম ব্যবহার করতে হবে। Video game, artificial intelligency, cryptography, hash algorithm, artificial intelligence সহ আরো বিভিন্ন ধরণের কম্পিউটিং এর ক্ষেত্রে random number ব্যবহৃত হয়।
৩. RSA Algorithm :-> এটি মূলত একটা Cryptography এর এলগরিদম। কোন একটা তথ্যকে encode-decode করার জন্য এটি ব্যবহৃত হয়। Cryptography এমন একটা পদ্ধতি যেটার সাহায্যে খুব স্পর্শকাতর আর গুরুত্বপূর্ণ তথ্য ডিজিটাল মাধ্যমে এক জায়গা থেকে আরেক জায়গায় পাঠানো যায়। উদাহরণ স্বরূপ বলা যায়, আমরা যখন জিমেইলের মাধ্যমে কোন মেইল কাউকে পাঠাই তখন সেটাকে আমাদের ব্রাউজার encrypt করে সার্ভারে পাঠায়। যেন গ্রাহকের কাছে পৌঁছানোর আগে যদি এটা কোন ভাবে অন্য কারো হাতে পড়ে তাও যেন সে ঐ মেইলের অর্থ উদঘাটন করতে না পারে। গ্রাহক যখন মেইলটি ওপেন করবেন তখন সেই encrypted data তার ব্রাউজারের মাধ্যমে decrypted হয়ে তার পড়ার উপযোগি হবে। RSA Algorithm এর ক্ষেত্রে public key আর private key হিসেবে চিহ্নিত দুটি key থাকে। কোন একটা ডেটাকে encoded (কোডে রূপান্তরিত) করার জন্য পাবলিক কী ব্যবহৃত হয়। এটি সবাই ব্যবহার করতে পারে। কিন্তু এই রূপান্তরিত ডেটার মর্মোদ্ধার করার জন্য প্রয়োজন হয় প্রাইভেট কী এর। আর এটা থাকে গোপন। অর্থাৎ যারা এই ডেটা পাওয়ার কথা শুধু তারাই এই প্রাইভেট কী-টা জেনে সেটার মাধ্যমে ডেটাকে ডিকোড করেন। RSA Algorithm এর কাজ হচ্ছে ডেটাকে কোডে রূপান্তর করা এবং সেটাকে পূর্বের অবস্থায় ফেরত আনা। অর্থাৎ এটা হচ্ছে একটা 2 way পদ্ধতি।
৪. Secure Hash Algorithm (SHA) :->
Hashing আলাদা কোন এলগরিদম নয়। এটি মূলত কয়েকটি cryptographic hash function এর সমন্বয়ে গঠিত data encoding এর পদ্ধতি। হ্যাশিং এলগরিদমগুলো অনেকটাই ক্রিপটোগ্রাফির মত।
ক্রিপটোগ্রাফি হয় দ্বিমুখী কিন্তু হ্যাশিং একমুখী। ক্রিপটোগ্রাফিতে ডেটা এনকোড করা হলে পরে প্রাইভেট কী এর মাধ্যমে ডিকোড করে মূল ডেটা ফেরত পাওয়া যায়। অপর পক্ষে হ্যাশিং এর মাধ্যমে encode করা হলে সেই ডেটাকে কোন ভাবেই মূল ডেটায় ফেরত আনা যায় না অর্থাৎ decode করা যায় না।
এর প্রয়োগ হিসেবে উল্লেখ করা যেতে পারে আমাদের ব্যাংক একাউন্টের পাসওয়ার্ড বা ফেসবুকের পাসওয়ার্ড। এই পাসওয়ার্ডগুলো ডাটাবেজে Hashed করে রাখা হয়। যেন কোন ভাবে ডাটাবেজের নিয়ন্ত্রণ অন্য কেউ নিয়ে নিলেও তার পক্ষে মূল পাসওয়ার্ড উদ্ধার করা সম্ভব না হয়। আমরা যখন একটা password সেট করি তখন ডাটাবেজে এই পাসওয়ার্ডকে নির্দিষ্ট এলগরিদম দিয়ে হ্যাশ করে সেটাকে সংরক্ষণ করে। পরে যখন Log in করার সময় পাসওয়ার্ড ইনপুট দেই তখন সংশ্লিষ্ট ওয়েব সার্ভার আমাদের পাসওয়ার্ডকে একই এলগরিদমের সাহায্যে হ্যাশ করে। যদি সংরক্ষিত থাকা hashed value এর সাথে এই ভ্যালুটা মিলে যায় তাহলেই কেবল আমরা লগ ইন করতে পারি।
৫. Merge Sort, Quick Sort and Heap Sort
Sort :-> এর অর্থ হচ্ছে কিছু ডাটাকে নির্দিষ্ট একটা ক্রমানুসারে সাজানো। যেমন কোন একটা ক্লাসের ছাত্রদের নাম ডাকার ক্ষেত্রে তাদের রোলের ছোট থেকে বড়র দিকে ডাকা হয়। আবার যে কোন dictionary-তে Lexicographical order (বর্ণক্রমানুসারে) এ শব্দগুলো সাজানো থাকে। এগুলোকে আমরা বলতে পারি Sorted Data, অর্থাৎ এই তথ্যগুলো Sorting পদ্ধতি প্রয়োগ করে ক্রমানুসারে বিন্যস্ত করা হয়েছে। কম্পিউটার বিজ্ঞান বা কম্পিউটার সম্পর্কিত যে কোন বিষয়ের শিক্ষার্থীদেরকে সর্টিং এর বিভিন্ন এলগোরিদম শেখানো হয়। সবচেয়ে সহজ সর্টিং এলগরিদম হচ্ছে Bubble Sort.
৬. Fourier Transform and Fast Fourier Transform :-> আমাদের পুরো ডিজিটাল জগৎটার সব জায়গাতেই এই খুব সাধারণ কিন্তু শক্তিশালী এলগরিদমটির ব্যবহার আছে। এর মাধ্যমে মূলত সিগনালগুলোকে time domain থেকে frequency domain ও frequency domain থেকে time domain এ রূপান্তর করা হয়। এমন কি তুমি যে এই আর্টিকেলটি পড়তে পারছ সে জন্য ধন্যবাদ প্রাপ্য কিন্তু এই এলগরিদমের!
ইন্টারনেটের এই ভার্চুয়াল জগতের জন্য যা যা ব্যবহৃত হয় যেমন internet, Wi-Fi, router, phone, smartphone, computer, satellite প্রায় সব কিছুতেই এই এলগরিদমের প্রয়োগ আছে। CSE, EEE বা IT এর সবাইকেই ফুরিয়ার ট্রান্সফর্ম নিয়ে পড়াশোনা করতে হয়।
৭. Dijkstra’s algorithm :->গুগল ম্যাপে যদি মিরপুর-১ থেকে নিউ মার্কেটের ডিরেকশন জানতে চাওয়া হয় তাহলে মিরপুর-১ থেকে টেকনিক্যাল হয়ে সোজা মিরপুর রোড ধরে নিউ মার্কেটের রাস্তা দেখানো হয়। কারণ কি? এছাড়া কি আর রাস্তা নেই? মিরপুর-১ থেকে মিরপুর-১০, সেখান থেকে মিরপুর-১৪ এর ক্যান্টনমেন্ট হয়ে ঐ সাইডে গাজীপুর থেকে একটু উকি দিয়েও তো নিউ মার্কেটে আসা যায় তাই না? তাহলে এই সোজা সাপটা পথ দেখালো কেন?
হ্যাঁ ঠিক ধরেছো! এটাই সব থেকে কম দূরত্বের পথ। অর্থাৎ মিরপুর-১ থেকে নিউ মার্কেট যাবার shortest path এটাই।
অনেকগুলো পরস্পরের সাথে যুক্ত পয়েন্টের (graph) মাঝে কোন একটা পয়েন্ট (node) থেকে অন্য আরেকটা পয়েন্টে যাওয়ার জন্য সর্বনিম্ন পথ বের করার জন্য ব্যবহৃত হয় এই এলগরিদম। Dijkstra’s algorithm হচ্ছে graph এর shortest path বের করার সবচেয়ে কার্যকরী এলগরিদম।
এই এলগোরিদমের প্রয়োগ ছাড়া এত চমৎকার ইন্টারনেট সুবিধা পাওয়া সম্ভব হত না। কারণ আমাদের নিজেদের ডিভাইসগুলো নিয়ে আমরা ইন্টারনেটের একটা জালের মাঝে আবদ্ধ। ঢাকা থেকে উগান্ডায় কারো কাছে data পাঠালে সেটা কোন পথে যাবে বা কোন পথে (routing) গেলে সব থেকে দ্রুত সেটি পৌঁছবে সেটা নির্ভর করে shortest path algorithm এর দক্ষতার উপর।
আজ এই পর্যন্তই। এই আর্টিকেলটা লেখার জন্য আমি কিছু কিছু জায়গাতে নেট এর সাহায্য নিয়েছি। যায় হোক আজ এই পর্যন্তই দেখা হবে এটার পরবর্তী পার্ট এ।
' xlink:href='%23b'/%3e%3cuse fill='black' filter='url(%23c)' xlink:href='%23b'/%3e%3cpath fill='white' d='M10.473 4C8.275 4 8 5.824 8 5.824S7.726 4 5.528 4c-2.114 0-2.73 2.222-2.472 3.41C3.736 10.55 8 12.75 8 12.75s4.265-2.2 4.945-5.34c.257-1.188-.36-3.41-2.472-3.41'/%3e%3c/g%3e%3c/svg%3e){kind=small}
' xlink:href='%23b'/%3e%3cuse fill='black' filter='url(%23c)' xlink:href='%23b'/%3e%3cpath fill='white' d='M12.162 7.338c.176.123.338.245.338.674 0 .43-.229.604-.474.725a.73.73 0 01.089.546c-.077.344-.392.611-.672.69.121.194.159.385.015.62-.185.295-.346.407-1.058.407H7.5c-.988 0-1.5-.546-1.5-1V7.665c0-1.23 1.467-2.275 1.467-3.13L7.361 3.47c-.005-.065.008-.224.058-.27.08-.079.301-.2.635-.2.218 0 .363.041.534.123.581.277.732.978.732 1.542 0 .271-.414 1.083-.47 1.364 0 0 .867-.192 1.879-.199 1.061-.006 1.749.19 1.749.842 0 .261-.219.523-.316.666zM3.6 7h.8a.6.6 0 01.6.6v3.8a.6.6 0 01-.6.6h-.8a.6.6 0 01-.6-.6V7.6a.6.6 0 01.6-.6z'/%3e%3c/g%3e%3c/svg%3e){kind=small}
Comments
Post a Comment