আমরা বাস্তবে যে সব খেলাধুলা করি সেগুলোতে আমরা খেলার শুরুতেই বলে দিতে পারি না কে খেলাতে জিতবে, আমরা এটাও ধরে নিতে পারি না যে সব খেলোয়াড়ই সবসময় সেরা চাল দিবে। এছাড়া অনেক খেলায় ভাগ্যেরও সহায়তা দরকার হয়। যেমন তাস খেলায় আমরা জানি না প্রতিপক্ষের কাছে কি কি কার্ড আছে, বা লুডু খেলায় আমরা জানি না ছক্কা বা ডাইস এ কখন কোন সংখ্যাটা আসবে। এই সিরিজে সময় আমরা মূলত মাত্র এমন সব গেম নিয়ে কাজ করবো যার নিচের বৈশিষ্ট্যগুলো আছে:
১. গেমের বোর্ড, চাল ইত্যাদি সম্পর্কে পূর্নাঙ্গ তথ্য আমাদের কাছে আছে, প্রতিপক্ষ কি অবস্থায় আছে সেটাও আমরা জানি।
২. খেলায় কোনো ভাগ্যের সহায়তা দরকার হয় না।
৩. খেলা শেষে কেও একজন ...
বিস্তারিত
স্লাইডিং রেঞ্জ মিনিমাম কুয়েরি
মনে করো তোমাকে একটা অ্যারে দেয়া হয়েছে যেখানে $n$ টা সংখ্যা আছে। তোমাকে বলা হলো সেই অ্যারের m=৩ আকারের যতগুলো সাবঅ্যারে আছে সবগুলো থেকে সবথেকে ছোটো সংখ্যাটা বের করতে হবে।
যেমন অ্যারেটা যদি হয় ১০,২,৫,৯,৬,৪ তাহলে m=৩ সাইজের সবগুলো সাবঅ্যারে হলো:
১০,২,৫ , সর্বনিম্ন সংখ্যা ২
২,৫,৯ , সর্বনিম্ন সংখ্যা ২
৫,৯,৬, সর্বনিম্ন সংখ্যা ৫
৯,৬,৪ , সর্বনিম্ন সংখ্যা ৪
তাহলে তোমার আউটপুট হবে [২,৫,৫,৪]।
$m$ এর মান ৩ না হয়ে ১ থেকে $n$ পর্যন্ত যেকোনো সংখ্যা হতে পারে।
$n$ এর মান যদি ছোটো হয় তাহলে আমরা সহজেই প্রতিটা সাবঅ্যারের উপর লুপ চালিয়ে সমস্যাটা সমাধান করতে পারি। নিচের পাইথন কোডটি দে...
বিস্তারিত
বাইনারি সার্চ – ২
আগের লেখায় আমরা বাইনারি সার্চ কিভাবে কাজ করে দেখেছি। এখন একই পদ্ধতি ব্যবহার করে আমরা অন্যরকম কিছু সমস্যা সমাধান করবো। আমরা এখন যেটা শিখবো সেটা বাইসেকশন মেথড নামেই বেশি পরিচিত।
সহজ একটা সমস্যা সমাধান করতে করতে আমরা বাইসেকশন কিভাবে কাজ করে দেখবো। মনে করো তুমি যে ভাষা ব্যবহার করে প্রোগ্রামিং করছ সেখানে বর্গমূল বের করার জন্য কোনো ফাংশন নাই, তোমাকে নিজে ফাংশন লিখে নিতে হবে। আমরা mysqrt(X) নামের একটা ফাংশন লিখবো যেখানে X সংখ্যাটা পাঠালে সংখ্যাটার বর্গমূল রিটার্ন করবে, X সংখ্যাটা দশমিকযুক্ত হতে পারে, তবে শূণ্যের কম হবে না।
আমরা জটিল কোনো গাণিতিক হিসাবে যাবো না বর্গমূল বের করার জন্য,...
বিস্তারিত
বাইনারি সার্চ – ১
তুমি নিশ্চয়ই লক্ষ্য করেছো ডিকশনারিতে লাখ লাখ শব্দ থাকলেও প্রয়োজনীয় শব্দটা খুজে পেতে কখনো খুব বেশি সময় লাগে না। এটার কারণ হলো শব্দগুলো অক্ষর অনুযায়ী সাজানো থাকে। তাই তুমি যদি dynamite শব্দটা ডিকশনারিতে খোজার চেষ্টা করো এবং এলোমেলোভাবে কোনো একটা পাতা খুলে kite শব্দটা খুজে পাও তাহলে তুমি নিশ্চিত হয়ে যেতে পারো যে তুমি যে শব্দটা খোজার চেষ্টা করছো সেটা বাম দিকে কোথাও আছে। আবার যদি তুমি dear শব্দটা খুজে পাও তখন তুমি আর বাম দিকের পাতাগুলোয় খোজার চেষ্টা করবে না। এভাবে অল্প সময়ের মধ্যে ডিকশনারিতে যেকোনো শব্দ খুজে পাওয়া যায়।
বাইনারি সার্চ হলো অনেকটা এরকম একটা পদ্ধতি যেটা ব্যবহার ক...
বিস্তারিত
হাইস্কুল প্রোগ্রামিং প্রতিযোগিতার প্রাথমিক প্রস্তুতি
পৃথিবীতে মানুষ দুই প্রকার, যারা প্রোগ্রামিং পারে এবং যারা প্রোগ্রামিং পারে না! ইংরেজি খুব ভালো না জেনেও জাপানিরা বা রাশিয়ানরা জ্ঞান-বিজ্ঞানে অনেক এগিয়ে আছে, কিন্তু প্রোগ্রামিং না জেনে কোনো জাতি অনেক এগিয়ে গেছে এরকম উদাহরণ সম্ভবত আধুনিক পৃথিবীতে একটিও খুজে পাওয়া যাবে না। জাতীয় হাইস্কুল প্রোগ্রামিং প্রতিযোগিতা(এনএইচপিসি) নিশ্চিতভাবেই বাংলাদেশের ইতিহাসে একটা মাইলফলক হতে চলেছে। গত কয়েক বছর ধরে ইনফরমেটিক্স অলিম্পিয়াড নিয়মিত আয়োজন করা হলেও অনেক সীমাবদ্ধতার কারণে সেটাকে ঢাকঢোল পিটিয়ে আয়োজন করা সম্ভব হয় নি। এবারের প্রতিযোগিতাটার পিছে সে তুলনা প্রস্তুতি অনেক বেশি, প্রচুর ছেলেমেয়ের কাছে এটার...
বিস্তারিত
গ্রাফ থিওরিতে হাতেখড়ি-১২ – ম্যাক্সিমাম ফ্লো (২)
আগের পর্বে আমরা দেখেছি কিভাবে ফোর্ড-ফুলকারসন পদ্ধতি ব্যবহার করে ম্যাক্সিমাম ফ্লো বের করতে হয়। এই পর্বে ম্যাক্সিমাম ফ্লো সমস্যার সহজ কিছু ভ্যারিয়েশন দেখবো।
একাধিক সোর্স/সিংক:
আগের পর্বে একটা প্রশ্ন করেছিলাম এরকম "আমাদের প্রবলেমে সোর্স এবং সিংক ছিলো একটা। কিন্তু গ্রাফে একাধিক নোড দিয়ে পানি প্রবেশ করলে এবং একাধিক নোড দিয়ে পানি বের হয়ে গেলে কিভাবে অ্যালগোরিদমটা পরিবর্তন করবে?" অর্থাৎ একাধিক সোর্স বা সিংক থাকলে কি করতে হবে সেটা জানতে চাওয়া হয়েছে।
চিত্র-১ এ বাম পাশের নীল নোডগুলো হলো সোর্স এবং ডানের সবুজ নোডগুলো হলো সিংক।
চিত্র -১: একাধিক সোর্স এবং সিংক সহ একটি গ্রা...
বিস্তারিত
গ্রাফ থিওরিতে হাতেখড়ি ১২ – ম্যাক্সিমাম ফ্লো (১)
এই লেখায় আমরা গ্রাফে ম্যাক্সিমাম ফ্লো বের করার অ্যালগোরিদম শিখবো। ম্যাক্স ফ্লো এর ধারণাটা ব্যবহার করে বেশ কিছু ইন্টারেস্টিং প্রবলেম সলভ করা যায়, তাই এটা শেখা খুবই গুরুত্বপূর্ণ। এই লেখাটা পড়ার আগে তোমাকে গ্রাফ থিওরির বেসিক অ্যালগোরিদমগুলো, বিশেষ করে শর্টেস্ট পাথ বের করার অ্যালগোরিদমগুলো ভালো করে শিখে নিবে।
প্রথমেই আমরা দেখি একটি খুবই সাধারণ ম্যাক্স ফ্লো প্রবলেম:
চিত্র: ১
তোমাকে চিত্র-১ এর মত একটা গ্রাফ দেয়া আছে। মনে কর গ্রাফের প্রতিটা এজ একটা করে পানির পাইপ। প্রতিটা পাইপ দিয়ে প্রতি সেকেন্ডে কত লিটার পানি প্রবাহিত হতে পারবে সেটার একটা সীমা আছে যেটাকে বলা হয় পাইপের ক্যাপাসিটি...
বিস্তারিত
কোয়ান্টাম কম্পিউটার – ২ (শক্তি এবং সীমাবদ্ধতা)
[আমার বর্তমান (২০১৪ সাল) গবেষণার বিষয় "কোয়ান্টাম কম্পিউটার" নিয়ে ২য় লেখা এটা। কোয়ান্টাম কম্পিউটার কি ধরণের সমস্যা সমাধানে ব্যবহার করা যাবে এবং এর সীমাবদ্ধতা কোথায় সেগুলো নিয়ে আজকে আলোচনা করব]
কোয়ান্টাম কম্পিউটার কী পারে যেটা সাধারণ কম্পিউটার পারে না? কোয়ান্টাম কম্পিউটার কি সত্যি ঝড়ের গতিতে সমস্যা সমাধান করে দিতে পারে? রিচার্ড ফাইনম্যান কোয়ান্টাম মেকানিক্সকে একধাপ এগিয়ে ধারণা দেন কোয়ান্টাম কম্পিউটারের। এখনো কোয়ান্টাম কম্পিউটার ল্যাবে তৈরি করা সম্ভব না হলেও আমরা এরই মধ্যে তাত্ত্বিকভাবে অনেক কিছু জেনে গিয়েছি, হয়তো সেই তত্ত্বগুলো বাস্তবে পরিণত হতে খুব বেশি দেরী নেই। কোয়ান্ট...
বিস্তারিত
কোয়ান্টাম কম্পিউটার – ১ (কোয়ান্টাম কম্পিউটার কী?)
সহজ কথায় কোয়ান্টাম কম্পিউটার হল এমন একটা কম্পিউটার যেটা কোয়ান্টাম মেকানিক্সের বিভিন্ন ধর্মকে সরাসরি কাজে লাগিয়ে সব কাজ করে। আমার বর্তমানের (২০১৪) গবেষণার বিষয়বস্তু কোয়ান্টাম কম্পিউটার, ন্যাশনাল ইউনিভার্সিটি অফ সিঙ্গাপুরের সেন্টার ফর কোয়ান্টাম টেকনোলজিতে ইন্টার্ন রিসার্চার হিসাবে কাজ করছি। কোয়ান্টাম কম্পিউটার নিয়ে পড়ালেখা করতে গিয়ে মনে হল এগুলো সম্পর্কে কিছু লেখা উচিত। কোয়ান্টাম কম্পিউটার নিয়ে অনেক লেখাই ইন্টারনেটে পাওয়া যায়, সেগুলোর কিছু ভাল হলেও বেশিভাগই ভুলে ভরা এবং অবাস্তব সব দাবী করা হয় সেগুলো তে। আমার লেখা রিভিউ করে ভুল-ত্রুটি দূর করতে সাহায্য করেছেন আমার সুপারভাইজর তানভীরুল ই...
বিস্তারিত
গ্রাফ থিওরিতে হাতেখড়ি ১১: বেলম্যান ফোর্ড
বেলম্যান ফোর্ড গ্রাফে শর্টেস্ট পাথ বের করার একটা অ্যালগোরিদম। এই অ্যালগোরিদম একটা নোডকে সোর্স ধরে সেখান থেকে সব নোডের সংক্ষিপ্ততম বা শর্টেস্ট পথ বের করতে পারে। আমরা একদম শুরুতে এই কাজ করার জন্য ব্রেডথ ফার্স্ট সার্চ শিখেছি। কিন্তু বিএফএস(BFS) যেহেতু ওয়েটেড গ্রাফে কাজ করে না তাই এরপর আমরা শিখেছি ডায়াক্সট্রা অ্যালগোরিদম। এখন বেলম্যান ফোর্ড শিখব কারন আগের কোনো অ্যালগোরিদমই নেগেটিভ ওয়েট এর এজ আছে এমন গ্রাফে কাজ করে না।
আমরা ডায়াক্সট্রা শেখার সময় রিল্যাক্সেশন নামের একটা ব্যাপার শিখেছিলাম। তোমার যদি মনে না থাকে বা ডায়াক্সট্রা না শিখে থাকো তাহলে আমরা প্রথমে একটু ঝালাই করে নেই ...
বিস্তারিত
ডাটা স্ট্রাকচার: বাইনারি ইনডেক্সড ট্রি
বাইনারি ইনডেক্স ট্রি খুবই চমৎকার একটা ডাটা স্ট্রাকচার যার সবথেকে ভালো দিক হলো কয়েক মিনিটেই কোড লিখে ফেলা যায়। আর খারাপ দিক হলো ভিতরে কি হচ্ছে বুঝতে একটু কষ্ট হয়, তবে তুমি লেখাটা মনযোগ দিয়ে পড়লে আমি নিশ্চিত কোন সমস্যা হবে না। বাইনারি ইনডেক্সড ট্রি বা BIT এর আরেক নাম হলো ফেনউইক(fenwick) ট্রি। এই লেখাটা পড়ার আগে তোমাকে বিটওয়াইজ অপারেশনগুলো(AND,OR ইত্যাদি) সম্পর্কে ভালো জানতে হবে।
আমরা একটা সহজ সমস্যা সমাধান করতে করতে বাইনারি ইনডেক্স ট্রি সম্পর্কে জানব। এই লেখায় আমরা ধরে নিব অ্যারের ইনডেক্স ১ থেকে শুরু, BIT কিভাবে কাজ করে জানার পরে বুঝতে পারবে এটা কেন গুরুত্বপূর্ণ। তোমাকে একটা অ...
বিস্তারিত
গ্রাফ থিওরিতে হাতেখড়ি ১০: ফ্লয়েড ওয়ার্শল
ফ্লয়েড ওয়ার্শল সম্ভবত সব থেকে ছোট আকারের গ্রাফ অ্যালগোরিদম, মাত্র ৩লাইনে এটা লেখা যায়! তবে ৩ লাইনের এই অ্যালগোরিদমেই বোঝার অনেক কিছু আছে। ফ্লয়েড ওয়ার্শলের কাজ হলো গ্রাফের প্রতিটা নোড থেকে অন্য সবগুলো নোডের সংক্ষিপ্ততম দুরত্ব বের করা। এ ধরণের অ্যালগোরিদমকে বলা হয় "অল-পেয়ার শর্টেস্ট পাথ" অ্যালগোরিদম। এই লেখাটা পড়ার আগে অ্যাডজেসেন্সি ম্যাট্রিক্স সম্পর্কে জানতে হবে।
আমরা একটা গ্রাফের উপর কিছু সিমুলেশন করে সহজেই অ্যালগোরিদমটা বুঝতে পারি। নিচের ছবিটা দেখ:
ছবিতে চার নোডের একটা ওয়েটেড ডিরেক্টেড গ্রাফ দেখা যাচ্ছে। আর উপরে ডান কোনায় একটা ম্যাট্রিক্স। ম্যাট্রিক্সের u,v তম ঘ...
বিস্তারিত
ম্যাট্রিক্স চেইন মাল্টিপ্লিকেশন
[নোটিশ ২৩ এপ্রিল ২০২০: ডাইনামিক প্রোগ্রামিং এর নতুন সিরিজ শুরু করেছি। লেখাটি নতুন ভার্সন এখানে পাওয়া যাবে।
আমরা এবার আরো একটি ক্লাসিক ডাইনামিক প্রোগ্রামিং প্রবলেম দেখবো যেটার নাম ম্যাট্রিক্স চেইন মাল্টিপ্লিকেশন। এটা শেখা খুবই গুরুত্বপূর্ণ কারণ এটার ধারণা ব্যবহার করে অনেক ধরণের সমস্যা সমাধান করে ফেলা যায়। এই লেখাটা পড়ার আগে তোমার ডাইনামিক প্রোগ্রামিং এর ধারণা থাকতে হবে। এছাড়া ম্যাট্রিক্স নিয়েও ধারণা থাকতে হবে।
আমি নিশ্চিত তোমরা সবাই ম্যাট্রিক্স গুণের শর্তগুলো জানো, তাও আমি মনে করিয়ে দিতে চাই। ধরি আমাদের দুটি ম্যাট্রিক্স আছে $A_1, A_2$ এবং তাদের ডিমেনশন $m * n$ আর $p * q$। তা...
বিস্তারিত
ডাইনামিক প্রোগ্রামিং: লংগেস্ট কমন সাবসিকোয়েন্স [পুরানো ভার্সন]
[নোটিস: ডাইনামিক প্রোগ্রামিং নিয়ে আমি নতুন একটা সিরিজ শুরু করেছি। নতুন ভার্সন পড়তে হলে এখানে ক্লিক করো]
ডাইনামিক প্রোগ্রামিং এর সম্ভবত সবথেকে গুরুত্বপূর্ণ দুটি উদাহরণ হলো লংগেস্ট কমন সাবসিকোয়েন্স এবং এডিট ডিসটেন্স বের করা কারণ এদের অনেক প্র্যাক্টিকাল অ্যাপ্লিকেশন আছে। এই লেখাটা পড়ার আগে আমি আশা করবো তোমরা কিছু বেসিক ডাইনামিক প্রোগ্রামিং যেমন কয়েন চেঞ্জ, ন্যাপস্যাক পারো। যদি না পারো তাহলে আমার আগের লেখাগুলো দেখতে পারো। এই লেখায় লংগেস্ট কমন সাবসিকোয়েন্স বের করা, সলিউশন প্রিন্ট করাএবং সবগুলো সম্ভাব্য সলিউশন বের করা দেখবো। তুমি যদি আগেই এসব টপিক নিয়ে জানো তাহলে লেখার শেষে রিলেটেড...
বিস্তারিত