Algorithms

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

An algorithm is a finite sequence of precise instructions for performing a computation or for solving a problem.

Describe sequence of steps by using English Language (or your own language)

আমরা এবার একটা সসীম পূর্ণসংখ্যার ধারা থেকে কিভাবে সর্বোচ্চ সংখ্যাটা বের করা যায় তার একটা অ্যালগরিদম বানাবো। অনেকভাবে অ্যালগরিদম লেখা যায়। আমরা প্রথমে সিম্পল ইংরেজি (বা যেকোনো ভাষায়) ভাষায় প্রতিটা স্টেপ লিখবো।

1. Set the temporary maximum equal to the first integer in the sequence. (The temporary maximum will be the largest integer examined at any stage of the procedure.)
2. Compare the next integer in the sequence to the temporary maximum, and if it is larger than the temporary maximum, set the temporary maximum equal to this integer.
3. Repeat the previous step if there are more integers in the sequence.
4. Stop when there are no integers left in the sequence. The temporary maximum at this point is the largest integer in the sequence.

এই চারটা স্টেপ। এবার এগুলোকে আমি বাংলায় ভালভাবে ব্যাখ্যা করছি।

• প্রথমে বলা হয়েছে যে ধারা প্রথম সংখ্যাকে আপাতত সর্বোচ্চ (temporary maximum) বলে ধরে নিতে হবে।
• এরপর দ্বিতীয় সংখ্যার সাথে প্রথম সংখ্যা তুলনা করে দেখা হবে। যদি দ্বিতীয় সংখ্যা temporary maximum এর চেয়ে বড় হয়, তাহলে দ্বিতীয় সংখ্যা temporary maximum হিসেবে পরিগণিত হবে। আর যদি ছোট হয় তাহলে পূর্বেরটাই বহাল থাকবে।
• এভাবে ধারা শেষ না হওয়া পর্যন্ত এই স্টেপ চলতে থাকবে।
• ধারা যখন শেষ হয়ে যাবে তখন temporary maximum এ যে সংখ্যাটি থাকবে সেটিই ঐ ধারার সর্বোচ্চ সংখ্যা হিসেবে বিবেচিত হবে।

Algorithms explanation by Pseudocode

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

procedure max(a1, a2, ..., an: integers)
max := a1
for i := 2 to n
        if ai > max then max := ai
return max{max is the largest number}

এবার এটার সাথে উপরের পদ্ধতি মিলাই আমরা। প্রথমে max = a1 ধরে নেয়া হয়েছে। এরপর for লুপের মাধ্যমে পর্যায়ক্রমিকভাবে লুপ চালিয়ে প্রতিটা সংখ্যাকে পর্যবেক্ষণ করা হয়েছে। যদি কোনো সংখ্যা max এর চেয়ে বড় হয় সেটাকে আমরা max এর মধ্যে অ্যাসাইন করেছি। লুপ শেষে যে সংখ্যাটা max এর মধ্যে থাকবে সেটাই সর্বোচ্চ সংখ্যা।

ধরি আমাদের কাছে একটা ধারা আছে ১, ৫, ৪, ৩, ২১। আমরা প্রথমে max = ১ ধরে নিবো। এরপর এটাকে আমরা ৫ এর সাথে তুলনা করবো। দেখবো ৫, ১ এর চেয়ে বড় নাকি ছোট। এখানে যেহেতু ৫ > ১, সেহেতু max = ৫ হয়ে যাবে। এরপর ৪ এর সাথে তুলনা করে দেখা যাচ্ছে ৪ < ৫। সুতরাং max = ৫ থেকে যাবে। এরপর ৩ এর সাথে তুলনা করেও দেখা যাচ্ছে ৩ < ৫। সুতরাং এক্ষেত্রেও max = ৫ থেকে যাচ্ছে। সবশেষে ২১ এর সাথে তুলনা করে পাওয়া যাচ্ছে ২১ > ৫। সুতরাং এক্ষেত্রে max এর ভ্যালু চেইঞ্জ হয়ে max = ২১ হয়ে যাবে। যেহেতু ২১ এর পর আর কোনো সংখ্যা নেই সুতরাং আমাদের লুপ এখানেই শেষ হয়ে যাবে। এবং আমরা দেখছি max এ সর্বশেষ ২১ অ্যাসাইন হয়েছে। সুতরাং ২১ এই ধারার সর্বোচ্চ সংখ্যা।

Properties of algorithms

প্রতিটা অ্যালগরিদমের কিছু প্রোপার্টি আছে। এই প্রোপার্টিগুলো একটা অ্যালগরিদম ব্যাখ্যা করার ক্ষেত্রে অনেক কাজে লাগে।

• Input - একটা অ্যালগরিদমের কিছু ইনপুট ভ্যালুর সেট থাকবে।
• Output - প্রতিটা ইনপুট ভ্যালুর সেট থেকে একটা অ্যালগরিদম কিছু ভালুর তৈরি করে। সেগুলোই মূলত আমাদের সমস্যার সমাধান।
• Definiteness - একটা অ্যালগরিদমের প্রতিটা স্টেপ অবশ্যই খুব ভালভাবে ডিফাইন্ড হতে হবে।
• Correctness - প্রতিটা ইনপুটের জন্য অ্যালগরিদমকে অবশ্যই নির্ভুল আউটপুট দিতে হবে।
• Finiteness - একটা অ্যালগরিদমকে অবশ্যই একটা নির্দিষ্ট পরিমাণ সসীম স্টেপ শেষে আকাঙ্ক্ষিত আউটপুট দিতে হবে।
• Effectiveness - একটা অ্যালগরিদমের প্রতিটা স্টেপ অবশ্যই একটা নির্দিষ্ট সময়ের মধ্যে সম্পন্ন হতে হবে।
• Generality - একটা অ্যালগরিদম অবশ্যই সেই ফর্মের যেকোনো ইনপুটের জন্য অ্যাপ্লিকেবল হতে হবে। শুধু একটার ক্ষেত্রে কাজ করবে অন্যটার ক্ষেত্রে না তেমন হওয়া চলবে না।

এবার আমরা আমাদের উদাহরণে এসমস্ত প্রোপার্টিজ আছে কিনা সেটা চেক করে দেখি।

• ইনপুট - আমাদের উদাহরণে একটা ইনপুট আছে যেটা হলো কিছু সংখ্যার ধারা।
• আউটপুট - এরপর আমরা শেষে একটা আউটপুট পেয়েছি যেটা হলো ঐ ধারার সর্বোচ্চ নাম্বার।
• ডেফিনিটনেস - অ্যালগরিদমের প্রতিটা স্টেপ খুব ভালভাবে ডিফাইন করা হয়েছে - অ্যাসাইনমেন্ট, একটা finite loop এবং কন্ডিশনাল স্টেটমেন্ট।
• কারেক্টনেস - এই অ্যালগরিদম সঠিক কিনা তা চেক করার জন্য আমাদেরকে দেখাতে হচ্ছে যে যখন অ্যালগরিদম শেষ হবে তখন max ভ্যারিয়েবলের মধ্যে ঐ ধারার সর্বোচ্চ সংখ্যা অ্যাসাইনড আছে কিনা।
• ফাইনাইটনেস - আমাদের অ্যালগরিদম একটা সসীম সংখ্যক স্টেপ পর্যন্ত ব্যবহৃত হচ্ছে, কারণ ঐ ধারার সকল সংখ্যা শেষে অ্যালগরিদম শেষ হয়ে যাচ্ছে।
• ইফেক্টিভনেস - এই অ্যালগরিদম একটা নির্দিষ্ট সময়ের মধ্যে সম্পন্ন হচ্ছে, কারণ এখানে প্রতিটা স্টেপ হয় কম্পারিজন নাহয় অ্যাসাইনমেন্ট। এখানে সসীম সংখ্যক স্টেপ আছে এবং প্রতিটা অপারেশন একটা নির্দিষ্ট সময়ের মধ্যে সংগঠিত হচ্ছে।
• জেনারিলিটি - এই অ্যালগরিদম যেকোনো সসীম সংখ্যার ধারার সর্বোচ্চ সংখ্যা বের করার ক্ষেত্রে ব্যবহার করা যাবে।

Different types of algorithm

অনেক ধরণের অ্যালগরিদম আছে। এদের মধ্যে সার্চিং (Searching), সর্টিং (Sorting), Greedy ইত্যাদি বহুলভাবে ব্যবহৃত হয়। এগুলো সম্পর্কে আমরা বিস্তারিত জানবো পরবর্তী আর্টিকেলগুলোতে।