গ্রাফ থিওরিতে হাতেখড়ি-১২ – ম্যাক্সিমাম ফ্লো (২)

আগের পর্বে আমরা দেখেছি কিভাবে ফোর্ড-ফুলকারসন পদ্ধতি ব্যবহার করে ম্যাক্সিমাম ফ্লো বের করতে হয়। এই পর্বে ম্যাক্সিমাম ফ্লো সমস্যার সহজ কিছু ভ্যারিয়েশন দেখবো। একাধিক সোর্স/সিংক: আগের পর্বে একটা প্রশ্ন করেছিলাম এরকম "আমাদের প্রবলেমে সোর্স এবং সিংক ছিলো একটা। কিন্তু গ্রাফে একাধিক নোড দিয়ে পানি প্রবেশ করলে এবং একাধিক নোড দিয়ে পানি বের হয়ে গেলে কিভাবে অ্যালগোরিদমটা পরিবর্তন করবে?" অর্থাৎ একাধিক সোর্স বা সিংক থাকলে কি করতে হবে সেটা জানতে চাওয়া হয়েছে। চিত্র-১ এ বাম পাশের নীল নোডগুলো হলো সোর্স এবং ডানের সবুজ নোডগুলো হলো সিংক। চিত্র -১: একাধিক সোর্স এবং সিংক সহ একটি গ্রা...
বিস্তারিত

গ্রাফ থিওরিতে হাতেখড়ি ১২ – ম্যাক্সিমাম ফ্লো (১)

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

কোয়ান্টাম কম্পিউটার – ২ (শক্তি এবং সীমাবদ্ধতা)

[আমার বর্তমান (২০১৪ সাল) গবেষণার বিষয় "কোয়ান্টাম কম্পিউটার" নিয়ে ২য় লেখা এটা। কোয়ান্টাম কম্পিউটার কি ধরণের সমস‍্যা সমাধানে ব‍্যবহার করা যাবে এবং এর সীমাবদ্ধতা কোথায় সেগুলো নিয়ে আজকে আলোচনা করব] কোয়ান্টাম কম্পিউটার কী পারে যেটা সাধারণ কম্পিউটার পারে না? কোয়ান্টাম কম্পিউটার কি সত‍্যি ঝড়ের গতিতে সমস‍্যা সমাধান করে দিতে পারে? রিচার্ড ফাইনম‍্যান কোয়ান্টাম মেকানিক্সকে একধাপ এগিয়ে ধারণা দেন কোয়ান্টাম কম্পিউটারের। এখনো কোয়ান্টাম কম্পিউটার ল‍্যাবে তৈরি করা সম্ভব না হলেও আমরা এরই মধ‍্যে তাত্ত্বিকভাবে অনেক কিছু জেনে গিয়েছি, হয়তো সেই তত্ত্বগুলো বাস্তবে পরিণত হতে খুব বেশি দেরী নেই। কোয়ান্ট...
বিস্তারিত

কোয়ান্টাম কম্পিউটার – ১ (কোয়ান্টাম কম্পিউটার কী?)

সহজ কথায় কোয়ান্টাম কম্পিউটার হল এমন একটা কম্পিউটার যেটা কোয়ান্টাম মেকানিক্সের বিভিন্ন ধর্মকে সরাসরি কাজে লাগিয়ে সব কাজ করে। আমার বর্তমানের (২০১৪) গবেষণার বিষয়বস্তু কোয়ান্টাম কম্পিউটার, ন‍্যাশনাল ইউনিভার্সিটি অফ সিঙ্গাপুরের সেন্টার ফর কোয়ান্টাম টেকনোলজিতে ইন্টার্ন রিসার্চার হিসাবে কাজ করছি। কোয়ান্টাম কম্পিউটার নিয়ে পড়ালেখা করতে গিয়ে মনে হল এগুলো সম্পর্কে কিছু লেখা উচিত। কোয়ান্টাম কম্পিউটার নিয়ে অনেক লেখাই ইন্টারনেটে পাওয়া যায়, সেগুলোর কিছু ভাল হলেও বেশিভাগই ভুলে ভরা এবং অবাস্তব সব দাবী করা হয় সেগুলো তে। আমার লেখা রিভিউ করে ভুল-ত্রুটি দূর করতে সাহায‍্য করেছেন আমার সুপারভাইজর তানভীরুল ই...
বিস্তারিত

গ্রাফ থিওরিতে হাতেখড়ি ১১: বেলম‍্যান ফোর্ড

বেলম‍্যান ফোর্ড গ্রাফে শর্টেস্ট পাথ বের করার একটা অ‍্যালগোরিদম। এই অ‍্যালগোরিদম একটা নোডকে সোর্স ধরে সেখান থেকে সব নোডের সংক্ষিপ্ততম বা শর্টেস্ট পথ বের করতে পারে। আমরা একদম শুরুতে এই কাজ করার জন‍্য ব্রেডথ ফার্স্ট সার্চ শিখেছি। কিন্তু বিএফএস(BFS) যেহেতু ওয়েটেড গ্রাফে কাজ করে না তাই এরপর আমরা শিখেছি ডায়াক্সট্রা অ‍্যালগোরিদম। এখন বেলম‍্যান ফোর্ড শিখব কারন আগের কোনো অ‍্যালগোরিদমই নেগেটিভ ওয়েট এর এজ আছে এমন গ্রাফে কাজ করে না। আমরা ডায়াক্সট্রা শেখার সময় রিল‍্যাক্সেশন নামের একটা ব‍্যাপার শিখেছিলাম। তোমার যদি মনে না থাকে বা ডায়াক্সট্রা না শিখে থাকো তাহলে আমরা প্রথমে একটু ঝালাই করে নেই ...
বিস্তারিত

ডাটা স্ট্রাকচার: বাইনারি ইনডেক্সড ট্রি

বাইনারি ইনডেক্স ট্রি খুবই চমৎকার একটা ডাটা স্ট্রাকচার যার সবথেকে ভালো দিক হলো কয়েক মিনিটেই কোড লিখে ফেলা যায়। আর খারাপ দিক হলো ভিতরে কি হচ্ছে বুঝতে একটু কষ্ট হয়, তবে তুমি লেখাটা মনযোগ দিয়ে পড়লে আমি নিশ্চিত কোন সমস‍্যা হবে না। বাইনারি ইনডেক্সড ট্রি বা BIT এর আরেক নাম হলো ফেনউইক(fenwick) ট্রি। এই লেখাটা পড়ার আগে তোমাকে বিটওয়াইজ অপারেশনগুলো(AND,OR ইত‍্যাদি) সম্পর্কে ভালো জানতে হবে। আমরা একটা সহজ সমস‍্যা সমাধান করতে করতে বাইনারি ইনডেক্স ট্রি সম্পর্কে জানব। এই লেখায় আমরা ধরে নিব অ‍্যারের ইনডেক্স ১ থেকে শুরু, BIT কিভাবে কাজ করে জানার পরে বুঝতে পারবে এটা কেন গুরুত্বপূর্ণ। তোমাকে একটা অ‍...
বিস্তারিত

গ্রাফ থিওরিতে হাতেখড়ি ১০: ফ্লয়েড ওয়ার্শল

ফ্লয়েড ওয়ার্শল সম্ভবত সব থেকে ছোট আকারের গ্রাফ অ‍্যালগোরিদম, মাত্র ৩লাইনে এটা লেখা যায়! তবে ৩ লাইনের এই অ‍্যালগোরিদমেই বোঝার অনেক কিছু আছে। ফ্লয়েড ওয়ার্শলের কাজ হলো গ্রাফের প্রতিটা নোড থেকে অন‍্য সবগুলো নোডের সংক্ষিপ্ততম দুরত্ব বের করা। এ ধরণের অ‍্যালগোরিদমকে বলা হয় "অল-পেয়ার শর্টেস্ট পাথ" অ‍্যালগোরিদম। এই লেখাটা পড়ার আগে অ‍্যাডজেসেন্সি ম‍্যাট্রিক্স সম্পর্কে জানতে হবে। আমরা একটা গ্রাফের উপর কিছু সিমুলেশন করে সহজেই অ‍্যালগোরিদমটা বুঝতে পারি। নিচের ছবিটা দেখ: ছবিতে চার নোডের একটা ওয়েটেড ডিরেক্টেড গ্রাফ দেখা যাচ্ছে। আর উপরে ডান কোনায় একটা ম‍্যাট্রিক্স। ম‍্যাট্রিক্সের u,v তম ঘ...
বিস্তারিত

ডাইনামিক প্রোগ্রামিং: ম‍্যাট্রিক্স চেইন মাল্টিপ্লিকেশন

আমরা এবার আরো একটি ক্লাসিক ডাইনামিক প্রোগ্রামিং প্রবলেম দেখবো যেটার নাম ম‍্যাট্রিক্স চেইন মাল্টিপ্লিকেশন। এটা শেখা খুবই গুরুত্বপূর্ণ কারণ এটার ধারণা ব‍্যবহার করে অনেক ধরণের সমস‍্যা সমাধান করে ফেলা যায়। এই লেখাটা পড়ার আগে তোমার ডাইনামিক প্রোগ্রামিং এর ধারণা থাকতে হবে। এছাড়া ম‍্যাট্রিক্স নিয়েও ধারণা থাকতে হবে। আমি নিশ্চিত তোমরা সবাই ম‍্যাট্রিক্স গুণের শর্তগুলো জানো, তাও আমি মনে করিয়ে দিতে চাই। ধরি আমাদের দুটি ম‍্যাট্রিক্স আছে $A_1, A_2$ এবং তাদের ডিমেনশন $m * n$ আর $p * q$। তাহলে কয়েকটি প্রোপার্টি আমাদের জন‍্য গুরুত্বপূর্ণ:   ম‍্যাট্রিক্স দুটি গুণ করা যাবে তখনই যদি $n=p$ হয়...
বিস্তারিত

ডাইনামিক প্রোগ্রামিং: লংগেস্ট কমন সাবসিকোয়েন্স

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

লোয়েস্ট কমন অ্যানসেস্টর

লোয়েস্ট কমন অ্যানসেস্টর জিনিসটা শুনতে একটু কঠিন মনে হলেও জিনিসটা সহজ আর খুবই কাজের। বেশ কিছু ধরণের প্রবলেম সলভ করে ফেলা যায় এই অ্যালগোরিদম দিয়ে। আমরা প্রথমে লোয়েস্ট কমন অ্যানসেস্টর বের করার ব্রুটফোর্স অ্যালগোরিদম দেখবো, তারপর স্পার্স টেবিল নামের নতুন একটা ডাটা স্ট্রাকচার শিখে কমপ্লেক্সিটি লগ এ নামিয়ে আনবো। প্রথমেই আমরা জেনে নেই লোয়েস্ট কমন অ্যানসেস্টর বা এল.সি.এ(LCA) কি সেটা। নিচের ছবিটা দেখ:   ছবিতে k আর n নোডের প্যারেন্ট ধরে পিছে যেতে থাকলে তারা i নোডে এসে মিলবে। i হলো k,n এর লোয়েস্ট কমন অ্যানসেস্টর। 'a' ও দুইজনের কমন অ্যানসেস্টর কিন্তু i হলো 'লোয়েস্ট' বা সবথে...
বিস্তারিত

গ্রাফ থিওরিতে হাতেখড়ি-৪(ব্রেডথ ফার্স্ট সার্চ)

আগের পর্বগুলোতে আমরা দেখেছি কিভাবে ম্যাট্রিক্স বা লিস্ট ব্যবহার করে গ্রাফ স্টোর করতে হয়। এবার আমরা প্রথম অ্যালগোরিদম দেখবো এর দিকে যাবো। শুরুতেই আমরা যে অ্যালগোরিদমটা শিখব তার নাম ব্রেডথ ফার্স্ট সার্চ(breadth first search,bfs)। বিএফএস এর কাজ হলো গ্রাফে একটা নোড থেকে আরেকটা নোডে যাবার শর্টেস্ট পাথ বের করা। বিএফএস কাজ করবে শুধুমাত্র আন-ওয়েটেড গ্রাফের ক্ষেত্রে, তারমানে সবগুলো এজের কস্ট হবে ১। বিএফএস অ্যালগোরিদমটা কাজ করে নিচের ধারণারগুলোর উপর ভিত্তি করে: ১. কোনো নোডে ১ বারের বেশি যাওয়া যাবেনা ২. সোর্স নোড অর্থাৎ যে নোড থেকে শুরু করছি সেটা ০ নম্বর লেভেলে অবস্থিত। ৩. সোর...
বিস্তারিত

মিট ইন দ্যা মিডল টেকনিক

মিট ইন দ্যা মিডল খুবই এলিগেন্ট একটা প্রবলেম সলভিং টেকনিক। এটার কাজ হলো প্রবলেমটাকে ঠিক দুইভাগে ভাগ করে ফেলে তারপর সেই দুইভাগকে কোনোভাবে মার্জ করে প্রবলেমটা সলভ করা। তবে ডিভাইড এন্ড কনকোয়ারের সাথে এটার পার্থক্য হলো ডিভাইড এন্ড কনকোয়ারে দুই ভাগে ভাগ করার পর ছোট ভাগগুলোকে বারবার ভাগ করা হয়, মিট ইন দ্যা মিডলে আমরা শুধু একবার ভাগ করবো। আমরা কিছু প্রবলেম দেখবো যেগুলোকে মিট ইন দ্যা মিডলের সাহায্যে সলভ করা সম্ভব। প্রবলেম ১: সাম অফ ফোর (দরকারি নলেজ: বাইনারি সার্চ) তোমাকে ৪টা $n$ সাইজের অ্যারে A,B,C,D দেয়া আছে। প্রতিটা অ্যারে থেকে এক্স্যাক্টলি একটা করে ভ্যালু সিলেক্ট করতে হবে যেন ...
বিস্তারিত

ট্রি ডায়ামিটার

ট্রি হলো এমন একটা আনডিরেক্টেড গ্রাফ যেটার সব নোড থেকে সব নোডে যাওয়া যায় এবং কোনো সাইকেল নেই। এখন আমাদের ট্রি এর সবথেকে দূরের দুটা নোড খুজে বের করতে হবে, একেই বলা হয় ট্রি এর ডায়ামিটার। মনে করো কিছু কম্পিউটারের মধ্যে নেটওয়ার্ক কেবল লাগানো হয়েছে নিচের ছবির মতো করে। এখন তুমি জানতে চাইতেই পারো কোন দুটি কম্পিউটার সবথেকে দূরে আছে। এটা বের করা খুব সহজ, এজন্য তোমার জানতে হবে বিএফএস বা ডিএফএস এর যে কোন একটা। আনডিরেক্টেড ট্রি তে যেকোন নোডকেই রুট ধরা যায়, আমরা মনে করি উপরের ধূসর নোডটা ট্রি এর রুট। আমাদের প্রথম কাজ কাজ হলো রুট হতে সবথেকে দূরের নোডটা খুজে বের করা। সেই নোডটা...
বিস্তারিত

ডাটা স্ট্রাকচার: ট্রাই (প্রিফিক্স ট্রি/রেডিক্স ট্রি)

ট্রাই বা প্রিফিক্স ট্রি ব্যবহার করে ডাটাবেস থেকে খুব সহজে স্ট্রিং খুজে বের করা যায়। ধরো একটা ফোনবুকে একটা শহরের সব মানুষের ফোন নম্বর রাখা আছে। শহরে মানুষ আছে হয়তো কয়েক লক্ষ্য, কিন্তু প্রতিটা মানুষের নাম সর্বোচ্চ ২০টা অক্ষর ব্যবহার করে লেখা যায়। আমরা এমন একটা ডাটা স্ট্রাকচার ব্যবহার করে নাম খুজবো যে নির্ভর করে শুধু মাত্র নামটিতে কয়টি অক্ষর আছে তার উপর। যেমন "Alice" নামটি খুজতে মাত্র ৫টি অপারেশন করা লাগবে ডাটাবেস যত বড়ই হোক না কেন। এই লেখা পড়ার আগে লিংকড লিস্ট এবং রিকার্সন সম্পর্কে ধারণা থাকতে হবে। ধরো তোমাকে একটা ডিকশনারী দেয়া হলো যেখানে নিচের শব্দগুলো আছে: algo algea also ...
বিস্তারিত