পৃথিবীকে শাসনকারী ১০ অ্যালগরিদম – ১

Post updated on 21st December, 2016 at 09:39 pm

অ্যালগরিদম কি?

Algorithm হচ্ছে কোনো একটা সমস্যা সমাধান করার জন্য প্রয়োজনীয় ও সুনির্দিষ্ট কিছু ধাপের সমষ্টি। সাধারণত computer science এর  ক্ষেত্রে এলগরিদম কথাটি বেশি ব্যবহৃত হলেও শুধু computational কাজের জন্যেই যে আমরা এলগরিদম ব্যবহার করি তা না। বরং আমরা আমাদের ব্যক্তি জীবনেও এর প্রয়োগ করি। বোঝার সুবিধার জন্য ভাত রাঁধার সাথে তুলনা করা যেতে পারে। কয়েকটা নির্দিষ্ট ধাপ সম্পন্ন করার মাধ্যমেই ভাত রান্না হয়ে যায়। আবার একেক জন মানুষের ভাত রান্নার পদ্ধতিতে কিছুটা ভিন্নতা থাকতে পারে। একেকটার একেক বৈশিষ্ট্য বা একেক রন্ধন প্রক্রিয়ার ভাতের গুণাগুণ একেক রকম হতে পারে। একই রকম ভাবে একটা সমস্যার সমাধানে একাধিক এলগরিদম থাকতে পারে। একেকটা এলগরিদমের একেক রকম গুণ বা বৈশিষ্ট্য বিদ্যমান। সমস্যার ধরন অনুযায়ী এলগরিদম নির্বাচন করা হয়।

Computer science বা programming এর ক্ষেত্রে যখন একটা এলগরিদম ব্যবহৃত হয়  তখন তা হয় সুস্পষ্টভাবে বর্ণিত কয়েকটি ধাপ। কোনো একটা নির্দিষ্ট সমস্যার সমাধানের জন্য একটা পদ্ধতি যেটা সমস্যাটার একটা সহজবোধ্য এবং সঠিক সমাধান প্রদান করে সেটাকেই একটা এলগোরিদম বলা যেতে পারে। কোন একটা নির্দিষ্ট সমস্যা সমাধানের জন্য একাধিক এলগরিদম থাকতে পারে। যেমন অনেকগুলো সংখ্যাকে ছোট থেকে বড় বা বড় থেকে ছোট সাজানোর অনেকগুলো পদ্ধতি বা এলগরিদম আছে। প্রতিটার কিছু সুবিধা ও অসুবিধাও আছে।  আর এলগরিদমের অন্যতম একটি বৈশিষ্ট্য হচ্ছে একে হতে হয় well defined. এর ধাপগুলো যেন শেষে একটা ফলাফল নিয়ে আসে। আর এই ফলাফল আনার পদ্ধতিটিও হতে হয় effective!

প্রযুক্তিগত উৎকর্ষের যেটুকু ছোঁয়া আমরা পাচ্ছি সেটা যে কতখানি এলগোরিদমের উপর নির্ভরশীল সেটা স্বাভাবিক আমাদের চিন্তায় আসে না। যদি বলা হয় প্রযুক্তিবিশ্ব পুরোপুরি এলগোরিদমের উপর নির্ভর করে দাঁড়িয়ে আছে সেটাও হয়তো একেবারে ভুল বলা যাবে না। আজ আমরা এমন কয়েকটি এলগরিদমের কথা জানব যেগুলো আমাদের প্রযুক্তি বিশ্ব ও সফটওয়্যার-ইন্টারনেট এর দুনিয়াকে শাসন করে যাচ্ছে।

এই লেখাটি Marcos Otero এর লেখা The real 10 algorithms that dominate our world থেকে ভাবানুবাদ করা হয়েছে। এই অনুবাদ প্রথম প্রকাশিত হয়েছিল Techmorich.com এ। এখানে এর পরিমার্জিত ভার্সনটি পোস্ট করা হচ্ছে।

Merge Sort, Quick Sort and Heap Sort

Sort করার অর্থ হচ্ছে কিছু ডাটাকে নির্দিষ্ট একটা ক্রমানুসারে সাজানো। যেমন কোন একটা ক্লাসের ছাত্রদের নাম ডাকার ক্ষেত্রে তাদের রোলের ছোট থেকে বড়র দিকে ডাকা হয়। আবার যে কোন dictionary-তে Lexicographical order (বর্ণক্রমানুসারে) এ শব্দগুলো সাজানো থাকে। এগুলোকে আমরা বলতে পারি Sorted Data, অর্থাৎ এই তথ্যগুলো Sorting পদ্ধতি প্রয়োগ করে ক্রমানুসারে বিন্যস্ত করা হয়েছে। কম্পিউটার বিজ্ঞান বা কম্পিউটার সম্পর্কিত যে কোন বিষয়ের শিক্ষার্থীদেরকে সর্টিং এর বিভিন্ন এলগোরিদম শেখানো হয়। সবচেয়ে সহজ সর্টিং এলগরিদম হচ্ছে Bubble Sort. এর প্রোগ্রাম লেখা খুব সহজ হলেও অনেক বেশি ডাটাকে এই এলগরিদম দিয়ে সর্ট করতে চাইলে প্রোগ্রামটার performance কমে যাবে। Average case এ এর algorithmic complexity হচ্ছে О(n^2).

অপরপক্ষে Merge sort, Quick sort ও Heap sort এর সাধারণ ক্ষেত্রে complexity হচ্ছে n log(n) যেটা অন্যান্য সর্টিং পদ্ধতি থেকে অনেক fast. Merge sort ও Quick sort কাজ করে divide-and-conquer approach এ, আর Heap sort কাজ করে priority queue এর মাধ্যমে।

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 এর দক্ষতার উপর।

বাংলায় ডায়াক্সট্রা অ্যালগোরিদম সম্পর্কে জানা যাবে শায়াফায়েত ভাইয়ার ব্লগ থেকে।

পরের পোস্টে সমাপ্ত।