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

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

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

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

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

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

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

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

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

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

ম‍্যাট্রিক্স চেইন মাল্টিপ্লিকেশন

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

কম্পিউটার বিজ্ঞান

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