অ্যালগোরিদম

প্রোবাবিলিটি: এক্সপেক্টেড ভ্যালু

মনে করো তুমি লুডু খেলতে গিয়ে একটা ডাইস বা ছক্কা নিয়ে রোল করছো। এখন তোমার যেকোনো একটা সংখ্যা পাবার প্রোবাবিলিটি কত? বেসিক প্রোবাবিলিটি যদি জেনে থাকো তাহলে তুমি সহজেই বলতে পারবে যে উত্তরটা হলো $\frac{1}{6}$। প্রোবালিটি $\frac{1}{6}$ এর মানেটা কী এখানে? এর মানে হলো, তুমি যদি ছক্কাটা নিয়ে অসীম সংখ্যকব বার খেলতে থাকো তাহলে ছয় ভাগের এক ভাগ বার তুমি $1$ পাবে, অন্য আরেকভাগ বার তুমি $2$ পাবে, অন্য আরেকভাগ বার তুমি $3$ পাবে ইত্যাদি। যেমন তুমি $600$ বার খেললে, $1$ থেকে $6$ পর্যন্ত প্রতিটা সংখ্যা $100$ বার করে পাবে। এটাতো গেলে গাণিতিক হিসাব, বাস্তবে $600$ বার খেলতে গেলে দেখা যাবে প্রতিটা $10...
Read More

অ্যালগোরিদম গেম থিওরি-২ (নিম গেম)

আগের পর্বে গেম থিওরি কিছু বেসিক শিখেছি, এবারের পর্বে আমরা জানবো নিম-গেম নিয়ে। নিম-গেম খুবই গুরুত্বপূর্ণ কারণ অনেক ধরণের গেমকে নিম গেম এ রূপান্তর করে ফেলা যায়। নিম-গেম এ দুইজন খেলোয়ার আর কিছু পাথরের স্তুপ(pile) থাকে। প্রতি চালে একজন খেলোয়াড় যেকোনো একটা স্তুপ থেকে এক বা একাধিক পাথর তুলে নিতে পারে। কেও চাল দিতে ব্যার্থ হলে হেরে যাবে। অর্থাৎ শেষ পাথরটা যে তুলে নিয়েছে সে গেমে জিতবে। উপরের ছবিতে ৩টা পাথরের স্তুপ দেখা যাচ্ছে, প্রথমটায় ৬টা, দ্বিতীয়টায় ৯টা এবং তৃতীয়টায় ৩টা পাথর আছে। আগের গেমগুলার মতো এখানেও প্রত্যেক খেলোয়াড় অপটিমাল পদ্ধতিতে খেলবে, কেও কোনো ভুল চাল দিবে না। তোমাকে...
Read More

অ্যালগোরিদম গেম থিওরি – ১

আমরা বাস্তবে যে সব খেলাধুলা করি সেগুলোতে আমরা খেলার শুরুতেই বলে দিতে পারি না কে খেলাতে জিতবে, আমরা এটাও ধরে নিতে পারি না যে সব খেলোয়াড়ই সবসময় সেরা চাল দিবে। এছাড়া অনেক খেলায় ভাগ্যেরও সহায়তা দরকার হয়। যেমন তাস খেলায় আমরা জানি না প্রতিপক্ষের কাছে কি কি কার্ড আছে, বা লুডু খেলায় আমরা জানি না ছক্কা বা ডাইস এ কখন কোন সংখ্যাটা আসবে। এই সিরিজে সময় আমরা মূলত মাত্র এমন সব গেম নিয়ে কাজ করবো যার নিচের বৈশিষ্ট্যগুলো আছে: ১. গেমের বোর্ড, চাল ইত্যাদি সম্পর্কে পূর্নাঙ্গ তথ্য আমাদের কাছে আছে, প্রতিপক্ষ কি অবস্থায় আছে সেটাও আমরা জানি। ২. খেলায় কোনো ভাগ্যের সহায়তা দরকার হয় না। ৩. খেলা শেষে কেও একজন ...
Read More

কমপ্লেক্সিটি ক্লাস(P-NP, টুরিং মেশিন ইত‍্যাদি)

আমরা যখন প্রবলেম সলভ করতে করতে মাথার চুল ছিড়ে ফেলি তখন প্রায়ই এমন কিছু প্রবলেম সামনে আসে যেগুলো সলভ করতে গেলে সবথেকে শক্তিশালী কম্পিউটারও হাজার হাজার বছর লাগিয়ে দিবে। বড় বড় কম্পিউটার বিজ্ঞানীরা যখন দিন-রাত চিন্তা করেও এগুলো সলভ করতে পারলেননা তখন তারা এই প্রবলেমগুলোকে কিছু ক্যাটাগরিতে ফেলে দিয়ে বললেন “এই ক্যাটাগরির প্রবলেমগুলো সলভ করার সাধ্য এখনো আমাদের হয়নি, তোমরা কেও পারলে সলভ করে দিয়ে ১০ লক্ষ ডলার পুরস্কার নিয়ে যাও”। সেগুলোকেই আমরা NP-complete, NP-hard ইত্যাদি নামে চিনি। NP ক্যাটাগরির প্রবলেমগুলো কম্পিউটার সায়েন্সে খুব বিখ্যাত। যেমন একটা গ্রাফে সবথেকে লম্বা পথ খুজে বের করা, ৩টা রঙ...
Read More

অ্যালগোরিদম কমপ্লেক্সিটি(বিগ “O” নোটেশন)

তুমি যখন একটা অ্যালগোরিদমকে কোডে ইমপ্লিমেন্ট করবে তার আগে তোমার জানা দরকার অ্যালগোরিদমটি কতটা কার্যকর। অ্যালগোরিদম লেখার আগে নিজে নিজে কিছু প্রশ্নের উত্তর দিতে হবে,যেমন: ১. আমার অ্যালগোরিদম কি নির্ধারিত সময়ের মধ্যে ফলাফল এনে দিবে? ২. সর্বোচ্চ কত বড় ইনপুটের জন্য আমার অ্যালগোরিদম কাজ করবে? ৩. আমার অ্যালগোরিদম কতখানি মেমরি ব্যবহার করছে? আমরা অ্যালগোরিদমের কমপ্লেক্সিটি বের করে প্রথম দুটি প্রশ্নের উত্তর দিতে পারি। একটি অ্যালগোরিদম যতগুলো "ইনস্ট্রাকশন" ব্যবহার করে কাজ করে সেটাই সোজা কথাই সেই অ্যালগোরিদমের কমপ্লেক্সিটি। দুটি নম্বর গুণ করা একটি ইনস্ট্রাকশন, আবার একটি লুপ ১০০ বার চললে...
Read More