পোস্টটি পড়া হয়েছে 9,076 বার

পৃথিবী শাসনকারী ১০ এলগরিদম – ২

Post updated on 28th November, 2016 at 01:48 pm

পৃথিবী শাসনকারী ১০ অ্যালগরিদম – ১ এ উল্লেখ করেছিলাম কিছু সর্টিং আর গ্রাফ এলগরিদম। এই পর্বে জানব আরো কিছু এলগরিদমের নাম।

RSA Algorithm

এটি মূলত একটা Cryptography এর এলগরিদম। কোন একটা তথ্যকে encode-decode করার জন্য এটি ব্যবহৃত হয়। Cryptography এমন একটা পদ্ধতি যেটার সাহায্যে খুব স্পর্শকাতর আর গুরুত্বপূর্ণ তথ্য ডিজিটাল মাধ্যমে এক জায়গা থেকে আরেক জায়গায় পাঠানো যায়। উদাহরণ স্বরূপ বলা যায়, আমরা যখন জিমেইলের মাধ্যমে কোন মেইল কাউকে পাঠাই তখন সেটাকে আমাদের ব্রাউজার encrypt করে সার্ভারে পাঠায়। যেন গ্রাহকের কাছে পৌঁছানোর আগে যদি এটা কোন ভাবে অন্য কারো হাতে পড়ে তাও যেন সে ঐ মেইলের অর্থ উদঘাটন করতে না পারে। গ্রাহক যখন মেইলটি ওপেন করবেন তখন সেই encrypted data তার ব্রাউজারের মাধ্যমে decrypted হয়ে তার পড়ার উপযোগি হবে।

RSA Algorithm এর ক্ষেত্রে public key আর private key হিসেবে চিহ্নিত দুটি key থাকে। কোন একটা ডেটাকে encoded (কোডে রূপান্তরিত) করার জন্য পাবলিক কী ব্যবহৃত হয়। এটি সবাই ব্যবহার করতে পারে। কিন্তু এই রূপান্তরিত ডেটার মর্মোদ্ধার করার জন্য প্রয়োজন হয় প্রাইভেট কী এর। আর এটা থাকে গোপন। অর্থাৎ যারা এই ডেটা পাওয়ার কথা শুধু তারাই এই প্রাইভেট কী-টা জেনে সেটার মাধ্যমে ডেটাকে ডিকোড করেন।

RSA Algorithm এর কাজ হচ্ছে ডেটাকে কোডে রূপান্তর করা এবং সেটাকে পূর্বের অবস্থায় ফেরত আনা। অর্থাৎ  এটা হচ্ছে একটা 2 way পদ্ধতি।

এই এলগরিদমটি আবিষ্কৃত হয় ১৯৭৭ সালে। এটি ডিজাইন করেন Ron Rivest, Adi Shamir,  ও Leonard Adleman. Cryptography এর জন্য এই এলগরিদমটি খুবই কার্যকর ও জনপ্রিয়।

Secure Hash Algorithm (SHA)

Hashing আলাদা কোন এলগরিদম নয়। এটি মূলত কয়েকটি cryptographic hash function এর সমন্বয়ে গঠিত data encoding এর পদ্ধতি। যা ডেভেলপ করেছেন যুক্তরাষ্ট্রের NIST. ১৯৯৩ সালে SHA-0 এলগরিদম প্রকাশিত হলেও হ্যাশিং এলগোরিদম হিসেবে SHA-1 সবচেয়ে প্রচলিত ও জনপ্রিয়।

হ্যাশিং এলগরিদমগুলো অনেকটাই ক্রিপটোগ্রাফির মত। তবে হ্যাশিং আর ক্রিপটোগ্রাফির মাঝে মৌলিক একটা পার্থক্য আছে। সেটা হচ্ছে ক্রিপটোগ্রাফি হয় দ্বিমুখী কিন্তু হ্যাশিং একমুখী। ক্রিপটোগ্রাফিতে ডেটা এনকোড করা হলে পরে প্রাইভেট কী এর মাধ্যমে ডিকোড করে মূল ডেটা ফেরত পাওয়া যায়। অপর পক্ষে হ্যাশিং এর মাধ্যমে encode করা হলে সেই ডেটাকে কোন ভাবেই মূল ডেটায় ফেরত আনা যায় না অর্থাৎ decode করা যায় না।

এর প্রয়োগ হিসেবে উল্লেখ করা যেতে পারে আমাদের ব্যাংক একাউন্টের পাসওয়ার্ড বা ফেসবুকের পাসওয়ার্ড। এই পাসওয়ার্ডগুলো ডাটাবেজে Hashed করে রাখা হয়। যেন কোন ভাবে ডাটাবেজের নিয়ন্ত্রণ অন্য কেউ নিয়ে নিলেও তার পক্ষে মূল পাসওয়ার্ড উদ্ধার করা সম্ভব না হয়। আমরা যখন একটা password সেট করি তখন ডাটাবেজে এই পাসওয়ার্ডকে নির্দিষ্ট এলগরিদম দিয়ে হ্যাশ করে  সেটাকে সংরক্ষণ করে। পরে যখন Log in করার সময় পাসওয়ার্ড ইনপুট দেই তখন সংশ্লিষ্ট ওয়েব সার্ভার আমাদের পাসওয়ার্ডকে একই  এলগরিদমের সাহায্যে হ্যাশ করে। যদি সংরক্ষিত থাকা  hashed value এর সাথে এই ভ্যালুটা মিলে যায় তাহলেই কেবল আমরা লগ ইন করতে পারি।

Data compression algorithms

কম্পিউটারের সাধারণ ব্যবহারকারী হিসেবে আমরা কিন্তু প্রায় প্রতিদিনই বিভিন্ন ধরনের data compress করে থাকি। যেমন কোন একটা ফোল্ডারকে মেইলে পাঠানোর আগে সেটিকে zip file এ কনভার্ট করে এরপর মেইলে এটাচ করি। বা কখনো কোন audio, video বা image কে কনভার্ট করে ছোট ফাইলে রূপান্তর করি। এগুলো সবই ডাটা কম্প্রেশনের উদাহরণ।

ডাটা কম্প্রেসনের জন্য বিভিন্ন সফটওয়্যার বাজারে বিদ্যমান। এই সফটওয়্যারগুলো তৈরি হয়েছে বিভিন্ন ধরণের Data Compression Algorithm এর উপর ভিত্তি করে। একেকটা সফটওয়্যার হয়ত একেকটা এলগরিদম ব্যবহার করেছে। তাই তাদের efficiency-ও একেকটার একেক রকম। ডাটা কম্প্রেশনের কোন এলগরিদমটা সব চেয়ে ভাল সেটা এক কথায় বলা মুশকিল। কারণ এটা নির্ভর করে ডাটার ধরনের উপর। ভিডিও, অডিও বা ছবি; একেকটার জন্য একেকটা এলগরিদম ভাল।

একটা উদাহরণ দিলে খুব সহজে কম্প্রেশনটার পদ্ধতি বোঝা যাবে। ধরা যাক আমরা এই আর্টিকেলটাকে compressed করব। এটার একটা পদ্ধতি হতে পারে এরকম যে যেই শব্দগুলো একাধিকবার ব্যবহৃত হয়েছে সেগুলোকে আমরা ফাইলে বারবার সেভ করে রাখব না। যেমন ‘algorithm’ শব্দটা অনেকবার এসেছে। আমরা একবার এই শব্দটা সেভ করব। আর এটা ট্র্যাক করব যে এই শব্দটা আর কোথায় কোথায় আছে। তাহলে আমাদের মেমরির ব্যবহার অনেক কমে যাবে। যখন ফাইলটাকে extract করব তখন সেই ট্র্যাক থেকে শব্দগুলোকে নির্দিষ্ট জায়গায় বসিয়ে দিব।

কোন ডাটাকে কম্প্রেস করার পর আবার এক্সট্রাক্ট করলে অনেক সময় ডেটা নষ্ট হয়ে যায়। কম্প্রেসন এলগোরিদমের ত্রুটির কারণেই এমনটা হয়। ডেটা ক্ষতিগ্রস্থ হওয়া আর না হওয়ার ভিত্তিতে এই এলগোরিদমগুলোকে Lossy আর Lossless নামক দুইটি ক্যাটাগরিতে ভাগ করা হয়।

ওয়েবসাইট থেকে ডাটা ডাউনলোড করা, ভিডিও গেম, মিউজিক, ডাটাবেজ, cloud computing এর মত জায়গায় ডাটা কম্প্রেশন এলগরিদমের প্রয়োগ রয়েছে। অনলাইনে থাকা প্রচুর রিসোর্স থেকে এলগরিদমগুলো সহজেই শিখে নেয়া সম্ভব।

Random Number Generation

কোন একটা হাসপাতাল নির্মান বা অন্য কোন ব্যাপারে তহবিল সংগ্রহের জন্য ১ লাখ লটারির টিকেট ছাড়া হল। ড্র এর দিন ১০টা টিকেট বাক্স থেকে তোলা হবে। এই দশটা টিকেটের মালিকরাই হবেন বিজয়ী। এটা ম্যানুয়াল্যি করতে চাইলে কি পরিমান ঝামেলা পোহাতে হবে বলাই বাহুল্য। কিন্তু এমন একটা সফটওয়্যার যদি ডিজাইন করা যায় যার মধ্যে একটা রেঞ্জ দিয়ে দিলে সেই রেঞ্জের মধ্যে থেকে সে র‍্যান্ডমলি একটার পর একটা নাম্বার আউটপুট দিতে থাকবে। তাহলে এই সফটওয়্যার ডিজাইন করতে অবশ্যই র‍্যান্ডম নাম্বার জেনারেট করার এলগরিদম ব্যবহার করতে হবে।

র‍্যান্ডম নাম্বারের ক্ষেত্রে কয়েকটা বৈশিষ্ট্য আছে। যেমনঃ এটা এমন হবে যে এর আউটপুট বা ফলাফল সম্পর্কে নিশ্চিত ভাবে কোন ভবিষ্যতবাণী করা সম্ভব হবে না। বারবার ব্যবহার করার ফলে আউটপুটের মাঝে কোনরূপ pattern পাওয়া যাবে না। অন্তত দুইটি সম্ভাব্য আউটপুট থাকতে হবে (যেমনঃ কয়েন দিয়ে টস করার ক্ষেত্রে সর্বনিম্ন সম্ভাব্য আউটপুট হতে পারে দুই রকমের)।

Video game, artificial intelligency, cryptography, hash algorithm, artificial intelligence সহ আরো বিভিন্ন ধরণের কম্পিউটিং এর ক্ষেত্রে random number ব্যবহৃত হয়। তবে এ কথা মানতেই হবে এখন পর্যন্ত বেশ কিছু শক্তিশালী এলগরিদম থাকলেও পুরোপুরি Random Number Generation Algorithm এখনো তৈরি হয় নি।

সকল এলগরিদমই ডিজাইন করা হয়েছে কোন না কোন সমস্যার সমাধানের জন্য। সেই দৃষ্টিকোণ থেকে সকল এলগরিদমই গুরুত্বপূর্ণ। এখানে বহুল ব্যবহৃত কয়েকটি এলগরিদমের নাম দেয়া হয়েছে। এগুলোর সমান গুরুত্ব বহন করে এমন আরো কিছু এলগরিদম হচ্ছেঃ Integer factorization,  Link Analysis, Proportional Integral Derivative Algorithm ইত্যাদি।

[নোটঃ আমি মিডিয়ামের একটা আর্টিকেল অনুবাদ করে আর কিছু ঘাটাঘাটি করে এই পোস্ট তৈরি করেছি। ভাবার কোন কারণ নাই আমি বিদ্যার জাহাজ! তাই “ভাইয়া, অমুক এলগোটা ইমপ্লিমেন্ট করতে গিয়ে মেমরি লিক করতেছে! কী করাম???” এই টাইপের প্রশ্ন করার সুযোগ নাই। 😛 ]

11 thoughts on “পৃথিবী শাসনকারী ১০ এলগরিদম – ২

    1. ধন্যবাদ কষ্ট করে পড়ে মন্তব্য করার জন্য।
      আপনার প্রার্থনায় আমায় রাখবেন। 🙂

  1. “আমি মিডিয়ামের একটা আর্টিকেল অনুবাদ করে আর কিছু ঘাটাঘাটি করে এই পোস্ট তৈরি করেছি। ভাবার কোন কারণ নাই আমি বিদ্যার জাহাজ! তাই “ভাইয়া, অমুক এলগোটা ইমপ্লিমেন্ট করতে গিয়ে মেমরি লিক করতেছে! কী করাম???” এই টাইপের প্রশ্ন করার সুযোগ নাই। ”

    Lol !!! 🙂

  2. ‘জাযাকাল্লাহ খাইর!’ এলগরিদম সম্পর্কে মোটের উপর ক্লিয়ার ধারণা পেলাম। বন্ধুদের শেয়ারও করেছি। এলগরিদম সম্পর্কে নলেজটা আরও কিভাবে ইমপ্রোভ করা যায় সে বিষয়ে একটি আর্টিকেলের আশায় রইলাম। এই বিষয়ের ইংরেজি ভাষায় অনেক লেখালেখি পড়ার চাইতে আপনার প্রিপারেশন রসে থাকা কোনো রাইটারের নাম/লিঙ্কের প্রত্যাশায় রইলাম।

    1. অ্যালগরিদমে ইম্রুভ করার একমাত্র ওয়ে হচ্ছে অ্যালগরিদম বুঝে নিজে নিজে প্র্যাকটিস করা। কোড করা। রিলেটেড প্রবলেম সলভ করা। প্রবলেম সলভিংয়ের জন্য UVa, LightOJ, HackerRank, SPOJ, URI বেশ ভাল। আমার ব্লগে অ্যালগরিদমের একটা ক্যাটাগরি আছে। সেখানে কয়েকটা পোস্ট আছে। এছাড়াও কোনো অ্যালগরিদমের নাম লিখে গুগলে বা ইউটিউবে সার্চ করলে প্রচুর রিসোর্স পাবেন।
      Data structures and algorithms made easy by Narasimha Karumanchi এই বইটা পড়তে পারেন।

Leave a Reply

Your email address will not be published. Required fields are marked *