ACMSolver Bangla: Art of Programming Contest in Bangla

Problem solving tactics for the ACM ICPC programming competition: search and optimisation from Evgeni Sergeev on Vimeo.

লেখক: শাফায়েত
লেখকের ওয়েব: http://www.shafaetsplanet.com/planetcoding

লেখকের পরিচিতি- শাফায়েত, ঢাকা বিশ্ববিদ্যালের কম্পিউটার বিজ্ঞান বিভাগের ছাত্র(২০১০-২০১৪)। আগ্রহ: কম্পিউটার বিষয়ক সব কিছুতে(হার্ডওয়্যার ব্যতিত),বিশেষ করে প্রোগ্রামিং আর অ্যালগোরিদমে।

আগের পর্বগুলোতে আমরা দেখেছি কিভাবে ভ্যারিয়েবলে গ্রাফ স্টোর করতে হয়। এবার আমরা প্রবলেম সলভিং এর দিকে যাবো। শুরুতেই আমরা যে অ্যালগোরিদমটা শিখব তার নাম breadth first search বা bfs। এটা ব্যবহার করে আমরা এখন unweighted গ্রাফে ২টি নোডের ভিতর শর্টেস্ট পাথ বের করব,unweighted বলতে বুঝাচ্ছি সবগুলো নোডের মধ্যে দুরত্ব সমান,আমরা ধরে নিব দুরত্ব ১।
এই পর্বে আমি কোনো কোড দিবোনা,শুধুমাত্র আইডিয়া পরিস্কার করবো কারণ সেটাই আসল জিনিস,সামনে কোনো পর্বে হয়তো কোড নিয়ে আলোচনা করবো।
আইডিয়াটি মূলত এরকম:

১. কোনো নোড ১ বারের বেশি visit করা হবেনা।
২. সোর্স নোড ০ নম্বর লেভেলে অবস্থিত।
৩. সোর্স বা ‘লেভেল ০’ থেকে ১ দুরত্বে অবস্থিত সবগুলো নোড লেভেল ১ এ।
৪. ‘লেভেল ১’ থেকে ১ দুরত্বে অবস্থিত সবগুলো নোড লেভেল ২ এ।
৫. ‘লেভেল n’ থেকে ১ দুরত্বে অবস্থিত সবগুলো নোড লেভেল n+1 এ।
৬. যে নোড যত নম্বর লেভেলে,সোর্স থেকে তার শর্টেস্ট পথের দৈর্ঘ্য তত।

উপরে লেখাগুলো পুরোপুরি মাথায় না ঢুকলেও ক্ষতি নেই,মোটামুটি বুঝলেই হলো,এখন আমরা ছবি দেখে বাকিটা পরিস্কার করব।

ধর তুমি ১নম্বর শহর থেকে ১০ নম্বর শহরে যেতে চাও। মাথায় রাখবে,১০ নম্বর শহরে যাবার জন্য মাঝে তোমাকে যেসব শহর ভিজিট করতে হবে সেগুলোও শর্টেস্ট পথে করতে হবে। প্রথমে আমরা সোর্স ধরলাম ১. ১ কে তাহলে visited চিহ্নিত করি।

১ থেকে শর্টেস্ট পথে বা ১দুরত্বে যাওয়া যায় ২,৩,৪ নম্বর নোডে। এবার সেগুলোকে আমরা visited চিহ্নিত করি এবং সেগুলো নিয়ে কাজ করি। নিচের ছবি দেখ:

লালনোডগুলো নিয়ে আমরা এখন কাজ করবো। রঙিন সবগুলো নোড visited,এক নোডে ২বার কখনো যাবোনা। ২,৩,৪ থেকে শর্টেস্ট পথে যাওয়া যায় ৬,৭,৮ এ। সেগুলো visited চিহ্নিত করি:

লক্ষ কর যে নোডকে যত নম্বর লেভেলে পাচ্ছি,সোর্স থেকে তার শর্টেস্ট পথের দৈর্ঘ্য ঠিক তত। যেমন ২নম্বর লেভেলে ৮কে পেয়েছি তাই ৮ এর দুরত্ব ২। ছবিগুলোকে একেকটা লেভেলের একেক রং দেয়া হয়েছে। আর লাল নোড দিয়ে বুঝানো হয়েছে আমরা এখন ওগুলো নিয়ে কাজ করছি। আমরা ১০ এ পৌছাইনি তাই পরের নোডগুলো ভিজিট করে ফেলি:

আমরা দেখতে পাচ্ছে ২টি লেভেল পার হয়ে ৩ নম্বর লেভেলে আমরা ১০ কে পাচ্ছি। তাহলে ১০ এর শর্টেস্ট পথ ৩। লেভেল বাই লেভেল গ্রাফটাকে explore করে আমরা শর্টেস্ট পথ বের করলাম। এটা ঠিক বাইনারি tree এর lever order traversal এর মত। আসলে এখানে আমরা একটা ট্রি তৈরি করে ফেলেছি। যেসব edge গুলো আমরা ব্যবহার করিনি সেগুলোকে বাদ দিয়ে ছবিটিকে একটু ঘুরিয়ে নিচের মত করে আকতে পারি:

লক্ষ্য কর গ্রাফদুটি একই,খালি নোডগুলো ঘুরানো হয়েছে। যেসব edge ব্যবহার করিনি সেগুলো হালকা করে দিয়েছি,এই edge গুলো বাদ দিলে গ্রাফটি একটি tree হয়ে যায়। tree তে দুটি নোডের মধ্য একটি মাত্র পথ থাকে।

লেখাটি আর বড় করবোনা,KolourPaint এ ছবি আকঁতে আকঁতে আমি টায়ার্ড। যেহেতু তুমি এখন adjacency list,matrix এ গ্রাফ স্টোর করতে পারো,নিজে কিছুক্ষন bfs এর কোড লেখার চেষ্টা কর। কোড খুব সহজ,সোর্স থেকে পরের লেভেলের সবগুলো নোডে যাবে,সেখান থেকে তার পরের লেভেলে যাবে,কোনো নোডে ২বার যাবেনা। উপরের গ্রাফটি স্টোর করে কোনো নোডকে সোর্স ধরে শর্টেস্ট পাথ বের কর।

কোডটি যদি লিখে ফেলতে পারো তাহলে প্র্যাকটিসের জন্য নিচের দুটি প্রবলেম ঝটপট সলভ করে ফেলো:
A Node Too Far(শর্টেস্ট পাথ প্রবলেম)
Bicoloring(বাইপারটাইট চেকিং)
আগের পর্ব: http://www.shafaetsplanet.com/planetcoding/?p=211

Reposted from writer’s website, with permission. Original Article link:

http://www.shafaetsplanet.com/planetcoding/?p=604

বিঃ দ্রঃ এই লেখাটি লেখকের অনুমতিক্রমে মুক্তমনা ওয়েব হতে সংগৃহীত।

লেখক: শাফায়েত
লেখকের ওয়েব: http://www.shafaetsplanet.com/planetcoding/

প্রাচীনকাল থেকেই গণিতবিদরা মাথা ঘামাচ্ছেন প্রাইম নাম্বার বা মৌলিক সংখ্যা নিয়ে। প্রাইম নাম্বারগুলো মধ্যে লুকিয়ে আছে বিষ্ময়কর কিছু সৌন্দর্য। যেকোনো কম্পোজিট বা যৌগিক সংখ্যাকে একাধিক প্রাইমের গুণফল হিসাবে মাত্র একভাবে লেখা যায়,ঠিক যেমন সব যৌগিক পদার্থ একাধিক মৌলিক পদার্থের সমন্বয়ে তৈরি। প্রাচীনকাল থেকেই মানুষ প্রাইম নিয়ে গবেষণা করছে,চলছে এখনো। গাউস,ফার্মা,ইউলারের মত কিংবদন্তি গণিতবিদরা কাজ করেছেন প্রাইম নিয়ে।

কিন্তু সব থেকে দ্রুত গতিতে প্রাইম সংখ্যা বের করার পদ্ধতি আবিষ্কার করেন Eratosthenes,২০০ খ্রিস্টপূর্বের একজন গ্রীক গণিতবিদ,বিজ্ঞানি ও কবি। ২২০০ বছরেরও পুরানো সেই পদ্ধতি ব্যবহার করে আমরা আধুনিক কম্পিউটারে প্রাইম জেনারেট করি,কয়েক মিলিসেকেন্ডে বের করা যায় ১০কোটির নিচে সব প্রাইম সংখ্যা। এই অ্যালগোরিদমটি sieve of Eratosthenes নামে পরিচিত,প্রোগ্রামিং এর জগতে সুন্দরতম অ্যালগোরিদমগুলোর মধ্যে এটি একটি।

sieve এর শাব্দিক অর্থ হলো ছাকনি যা অপ্রয়োজনীয় অংশ ছেটে ফেলে (A sieve, or sifter, separates wanted elements from unwanted material using a woven screen such as a mesh or net)। Eratosthenes এর ছাকনি যৌগিক সংখ্যাগুলোকে ছেটে ফেলে দেয়।কাব্যের ভাষায়:

Sift the Twos and sift the Threes,
The Sieve of Eratosthenes.
When the multiples sublime,
The numbers that remain are Prime
(Traditional,collected from wikipedia)

আমরা জানি প্রাইম সংখ্যা হলো সেসব সংখ্যা যাদের ১ এবং সেই সংখ্যটি ব্যতিত কোনো সংখ্যা দিয়ে ভাগ করা যায়না,যেমন ২,৩,৫,৭,২৯ ইত্যাদি। অন্যভাবে বলা যায় সেসব সংখ্যাই প্রাইম যাদেরকে সংখ্যাটির বর্গমূলের সমান বা ছোটো কোনো প্রাইম দিয়ে ভাগ করা যায় না। এই সংজ্ঞাটাই অ্যালগোরিদমের মূল অংশ,তাই আগে আমরা এটা বুঝতে চেষ্টা করব। ফর্মালভাবে প্রমাণ না করে ব্যপারটি বুঝানোর চেষ্টা করি। যেকোনো সংখ্যাকে আমরা কয়েকটি প্রাইমের গুণফল হিসাবে লিখতে পারি যাদের প্রাইম ফ্যাক্টর বলা হয়:

n=p1*p2*p3….*pk।

n যদি নিজেই প্রাইম হয় তাহলে n=p1(=n)। অন্যথায় অবশ্যই একাধিক প্রাইম ফ্যাক্টর থাকতে হবে। এবার চিন্তা করুন কোনো সংখ্যা c কে দুটি সংখ্যার গুণফল c=a*b হিসাবে লিখলে a আর b এর একটি অবশ্যই সংখ্যাটির বর্গমূলের থেকে ছোট,অন্যটি বড়। a,b দুটো সংখ্যাই c এর বর্গমূলের থেকে বড় হলে গুণফল c থেকে বড় হতো (ঠিক যেমন c=a+b হলে a বা b এর একটি c এর অর্ধেকের থেকে ছোট অন্যটি বড়)।

এবার n=p1*p2*p3….*pk তে ফিরে আসি। p1,p2,p3 ইত্যাদির মধ্যে যে কোনো ২টি যদি n এর বর্গমূল থেকে বড় হয় তাহলে তাদের গুণফল n কে ছাড়িয়ে যাবে,তাই নয় কি? সর্বোচ্চ একটি প্রাইম ফ্যাক্টর বর্গমূলের বাইরে যেতে পারে,বাকি গুলো কে অবশ্যই ভিতরে থাকতে হবে।

তাহলে আমরা নিশ্চিত যে যৌগিক সংখ্যা কে তার বর্গমূলের থেকে ছোট কোনো প্রাইম দিয়ে ভাগ করা যাবে। ২য় সংজ্ঞাটি এখন আমাদের কাছে পরিষ্কার: ”সেসব সংখ্যাই প্রাইম যাদেরকে সংখ্যাটির বর্গমূলের সমান বা ছোটো কোনো প্রাইম দিয়ে ভাগ করা যায় না”। বুঝতে না পারলে আরেকবার ভালো করে চিন্তা করে নিচের অংশ পড়ুন।

এবার আমরা আমাদের ছাকনি চালু করি এবং প্রাইম বের করি। ২৫ এর নিচের সব প্রাইম আমরা বের করব। ২ একটি প্রাইম কারণ ২কে তার বর্গমূলের নিচে কোনো সংখ্যা দিয়ে ভাগ করা যায়না। তাহলে ২ এর মাল্টিপলগুলো কেও প্রাইম নয় কারণ তাদের ২ দিয়ে ভাগ করা যায়,সেগুলোকে আমরা কেটে দেই:

২,৪,৬,৮,১০,১২,১৪,১৬,১৮,২০,২২,২৪

২ এর পরের সংখ্যা ৩। ৩ যদি প্রাইম না হতো তাহলে ৩ এর বর্গমূলের নিচের কোনো প্রাইম ৩ কে বাদ দিয়ে দিত,যেহেতু ৩ বাদ পড়েনি তাই সংজ্ঞামতে ৩ প্রাইম। ৩ এর মাল্টিপল গুলো কে বাদ দেই:

৩,৬,৯,১২,১৫,১৮,২১,২৪

পরের সংখ্যা ৪। ৪ বাদ পড়ে গিয়েছে আগেই। তারপর আছে ৫। ৫ যদি প্রাইম না হতো তাহলে আগেই ছাকনিতে কাটা পড়ত, ৫এর মাল্টিপল গুলোকে কেটে দেই:

৫,১০,১৫,২০,২৫

আমাদের আর কাটাকাটি প্রয়োজন নেই। ২৫ এর বর্গমূল ৫, তাই ২৫এর নিচের সব সংখ্যার বর্গমূল ৫ থেকে ছোট। সুতরাং ২৫ এর নিচের সকল যৌগিক সংখ্যা ৫ বা তার নিচের কোনো প্রাইম দিয়ে বিভাজ্য। যেহেতু আমরা ২,৩,৫ এর সব মাল্টিপল কেটে দিয়েছি,বাকি সংখ্যগুলো অবশ্যই প্রাইম। ছাকনির উপর থেকে সেগুলো সংগ্রহ করে নেই:

২,৩,৫,৭,১১,১৩,১৭,১৯,২৩

আমরা প্রাইম জেনারেট করে ফেললাম। গণিত ছেড়ে এবার আমরা কম্পিউটার বিজ্ঞানে আসি। sieve of Eratosthenes এ প্রতিটি সংখ্যা প্রাইম নাকি নন-প্রাইম সেটা আমরা একটি বুলিয়ান অ্যারে দিয়ে চেক করি। যত পর্যন্ত প্রাইম জেনারেট করব তত সাইজের অ্যারে লাগবে। ১০^৮ আকারের অ্যরে অনেক মেমোরি দখল করে। মেমোরি অপটিমাইজ করার জন্য অসাধারণ একটি পদ্ধতি হলো বিট ব্যবহার করা,একে bitwise সিভ বলা হয়। একটি ইন্টিজারে ৩২টি বিট থাকে যার প্রতিটিকে আমরা ফ্ল্যাগ হিসাবে ব্যবহার করতে পারি। কিছুটা এডভান্সড টপিক বলে এটা নিয়ে বিস্তারিত আলোচনা করলামনা।

প্রোগ্রামিং কনটেস্ট যারা করে তাদের জন্য সিভ শেখা খুবই জরুরি,সিভের ধারণাটি দিয়ে আরো অনেক কাজ করা যায়,যেমন totient ফাংশনের মান বের করা ইত্যাদি।

sieve of Eratosthenes আমাদের সামনে অ্যালগোরিদম জানার গুরুত্বকে আরো একবার তুলে ধরে। যে কেও খুব সহজে কোনো সংখ্যাকে তার আগের সব সংখ্যা দিয়ে ভাগ করে দেখে প্রাইম বের করতে পারবে,কিন্তু এটা প্রচুর সময় লাগবে। কিছু গাণিতিক জ্ঞান এবং অ্যলগোরিদম জানা থাকলে প্রচুর সময় এবং রিসোর্স বাচানো যায়। সফটওয়্যার ইঞ্জিনিয়ারিং এ ভালো অ্যলগোরিদম,উন্নত ডাটা স্ট্রাকচার সফটওয়্যারকে করে দিতে পারে অনেক বেশি শক্তিশালী। তাই অনেক সময় সফটওয়্যার ইঞ্জিনিয়াররা অ্যালগোরিম বা গণিতকে গুরুত্ব কম দেন যা মোটেও ঠিক নয়।

আবার এ কথাও ঠিক যে শুধু অ্যলগোরিদম জানলে প্রোগ্রামিং জানা হবেনা,প্রোগ্রামিং ল্যাংগুয়েজ ও আধুনিক প্রযুক্তি,ফ্রেমওয়ার্ক সম্পর্কে ভালো ধারণা লাগবে। প্রোগ্রামিং কনটেস্টগুলোকে অ্যলগোরিদম আর গণিত কে সবথেকে বেশি গুরুত্ব দেয়া হয়,কারণ এগুলো আয়ত্ব করে প্রবলেম সলভ করতে পারলে দক্ষতা বৃদ্ধি পায় এবং বাকি বিষয়গুলো অনেকটা সহজ হয়ে যায়।

অ্যালগোরিদম শুধু জানলে হবেনা,সেটা কিভাবে কাজ করে হবে ভালো মত বুঝতে হবে,অ্যালগোরিদম প্রয়োজনমত পরিবর্তন করতে জানতে হবে। একটি অ্যালগোরিদম শেখার ভালো পদ্ধতি হতে পারে সেই অ্যলগোরিদম সংক্রান্ত বিভিন্ন সমস্যা সমাধান করা।

cpp implementation of sieve of Eratosthenes
(পাঠকের আগ্রহ থাকলে + আমার আলসেমি কমলে চলবে….)

পর্ব ১
পর্ব ২

বিঃ দ্রঃ এই লেখাটি লেখকের অনুমতিক্রমে মুক্তমনা ওয়েব হতে সংগৃহীত।

লেখক: শাফায়েত
লেখকের ওয়েব: http://www.shafaetsplanet.com/planetcoding/

ধরা যাক বাংলাদেশের ১৫কোটি মানুষের নাম নিয়ে একটি তথ্যকেন্দ্র তৈরি করা হলো। নামগুলো বর্ণক্রমানুসারে সাজানো। এখন সেখান থেকে একটি নাম খুজে বের করতে হবে। সাধারণভাবে একটি নামের সাথে মিলিয়ে খুজে বের করতে সাধারণ কম্পিউটারের বেশ সময় লাগবে। কিন্তু আপনি সর্বোচ্চ ২৪বার মিলিয়ে নামটি খুজে বের করতে পারবেন। এখানেই প্রোগ্রামিং এর সৌন্দর্য। দৈনন্দিন জীবনের এমন বহু সমস্যা সমাধান করতে কম্পিউটার বিজ্ঞানী,প্রোগ্রামার,গণিতবিদরা বের করেছেন বুদ্ধিদীপ্ত সব অ্যালগোরিদম যা দিয়ে কম্পিউটারের কাজ সম্পাদনা করার সময়(execution time) বিষ্ময়কর ভাবে কমিয়ে আনা যায়।

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

১ ১০ ২০ ৩০ ৪৫ ৫০ ৬০ ৯০ ১০০

এখন আমাকে খুজে বের করতে হবে ২০ সংখ্যাটি আছে নাকি। প্রথমেই ঠিক মাঝের সংখ্যাটি দেখি। মাঝে আছে ৪৫ যা ২০ থেকে বড়। তাহলে আমরা ৪৫ থেকে পরের সংখ্যা গুলো বাদ দিয়ে দিতে পারি কারণ তারা সবাই ২০ থেকে বড়[যেহেতু ৪৫ থেকে বড়]। তাহলে আমার কাছে থাকল:

১ ১০ ২০ ৩০

এখন মাঝের সংখ্যা ১০ যা ২০ থেকে ছোট।(সংখ্যা ৪টি হলে ২ বা ৩ তম সংখ্যার যেকোনোটাকে mid ধরা যাবে) তাই ১০ ও তার আগের সব সংখ্যা বাদ কারণ তারা সবাই ২০ থেকে ছোট। বাকি থাকল:

২০ ৩০

এবার আমরা মাঝের সংখ্যা হিসাবে ২০ কে পেয়ে যাব। তারমানে যতক্ষননা মাঝে কাঙ্খিত সংখ্যাটিকে মাঝখানে পাচ্ছি ততক্ষণ অর্ধেক করে বাদ দিতে থাকব।

ব্যপারটি অনেকটা এরকম,১০০ জন মানুষকে উচ্চতা অনুযায়ী সাজানো হলো,এখন নির্দিষ্ট উচ্চতার একজন মানুষ “ক” কে খুজতে আমরা প্রথমে মাঝের মানুষটির সাথে মিলিয়ে দেখব। “ক” এর উচ্চতা তার থেকে কম হলে ডানের সবাইকে বাদ দিয়ে দিব কারণ ডানের সবার উচ্চতা বেশি। যতজন মানুষ বাকি থাকল তাদের নিয়ে আবার একই ভাবে খুজব। প্রতিবার মানুষ সংখ্যা অর্ধেক হয়ে যাবে।
উৎসাহীদের জন্য বাইনারি সার্চের একটি c++ কোড দিয়ে দিলাম:

//key is the value we are searching
//low and high are array index
//num is a global array
void search(int low,int high,int key)
{
if(low>high) return;
int mid=(low+high)/2;
if(num[mid]<key)
search(mid+1,high,key); //বামের সব মানুষ বাদ,মাঝের পরের জনই এখন সর্ববামের মানুষ
else if(num[mid]>key)
search(low,mid-1,key); //ডানের সব মানুষ বাদ,মাঝের আগের জনই এখন সর্বডানের মানুষ
else
{cout<<”Found at pos: “<<mid<<endl; return;} //পেয়েছি
}

সংখ্যা ছাড়াও নামের ক্ষেত্রেও(string) এভাবে তুলনা করা যায়। ১০০টি নাম থাকলে প্রথমবার বাদ দেবার পর বাকি থাকবে ৫০টি,এরপর ২৫টি,এরপর ১২টি….। ২^৬৪ টি নাম থাকলে মাত্র ৬৪বার মিলিয়ে কাংখিত সংখ্যা খুজে বের করা যাবে!!!।

বাইনারি সার্চের প্রয়োগের ক্ষেত্র বিশাল। বিশেষ কিছু সমস্যা,এমনকি জ্যামিতির অনেক সমস্যার ফলাফল বাইনারি সার্চ দিয়ে বের করে ফেলা যায়,গাণিতিক ভাষায় একে bisection ও বলা হয়। binary search tree নামক একটি গুরুত্বপূর্ন ডাটা স্ট্রাকচার রয়েছে। কম্পিউটারে তথ্য বিভিন্নভাবে সাজিয়ে রাখা যায়,সহজ ভাষায় তথ্য সাজানো বিভিন্ন উপায়কেই ডাটা স্ট্রাকচার বলে। হাতে-কলমে যে ফলাফল বের করতে অনেক সময় লাগবে,একটি ছোট কোড লিখে সেটা সেকেন্ডের মাঝে করে ফেলা যায়। সামান্য গুতিয়ে প্রমান করা যায় nটি বস্তু থেকে কোনটাকে খুজে বের করতে বাইনারি সার্চে সর্বোচ্চ log2(n) বার মিলিয়ে দেখতে হবে,চাইলে বের করে দেখতে পারেন ।

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

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

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

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

পাঠকদের আগ্রহ থাকলে সামনে বাইনারি সার্চের মত সহজ ও সুন্দর কিছু প্রোগ্রামিং টেকনিক নিয়ে সামনে কিছু লেখা দিতে চেষ্টা করব।(তবে কবে চেষ্টা করব বলতে পারছিনা,লেখালেখির ব্যাপারে আমি খুবই অলস )

১ম পর্ব: http://mukto-mona.com/banga_blog/?p=11547

উৎসাহীরা ডাটা সর্টিং নিয়ে রাগিব হাসানের অসাধারণ একটি লেখা পড়তে পারেন এখানে: http://bongobani.blogspot.com/2010/06/blog-post_1625.html

খুব বেশি ভূমিকার দরকার নেই। সরাসরি ভিডিও দেখতে চলে যান!

হ্যালো প্রোগ্রামারের দল, আজকে রবার্ট স্যাজউইকের অ্যালগোরিদম লেকচার এর সাথে পরিচিত হই। যিনি প্রিন্সটনের একজন বিখ্যাত প্রফেসর।

সব একসাথে  all the slides for Lectures 1-10 (28 MB) আর all the slides for Lectures 12-24 (40 MB)কোর্সের সকল ফাইল  all the slides for the course (66 MB).

কয়েন চেঞ্জ অ্যালগোরিদম এর ভাল টিউটোরিয়াল  পেলাম এইখানে।

“(…) ধরি, আমাদের কাছে ২ টাকা এবং ৪ টাকার কয়েন আছে আর আমরা জানতে চাই, ঠিক কতভাবে ১ থেকে ৮টাকা বানানো যায়, যেমন ৪ টাকা বানানো যায় ২ ভাবেঃ ২টাকার ২ টা কয়েন বা ৪ টাকার  টা কয়েন দিয়ে।

আর আরেকটা কথা, যে কোন কয়েন যে কোন সংখ্যকবার নেয়া যাবে।ধরি, একটা এরে নিলাম nway[], এতে থাকবে কোন টাকা কতভাবে বানানো যায়, মানে nway[1]=কতভাবে ১ টাকা বানানো যায়, nway[2] মানে কতভাবে ২ টাকা বানানো যায়…

nway[0] = 1, .. এখন, ২ টাকার কয়েন দিয়ে কি ৩ টাকা বানাতে পারি?

…(….)”

আর দেরি না করে পুরোটা পড়ে নিনঃ https://sites.google.com/site/programinggconcept/algorithm

কেউ কোন ভুল পেলে বা কোন মতামত থাকলে জানাবেন,এই ই-মেইল আড্রেসঃ concept_right@yahoo.com

অনেক দিন ধরেই ০/১ ন্যাপসাক অ্যালগোরিদম এর একটি ভাল টিউটোরিয়াল খুঁজ ছিলাম। অবশেষে পেলাম এইখানে।

“(…)আলীবাবা চিচিংফাক বলে ঢুকে পড়েছে ডাকাতদের গুহায়, তার সামনে চোখ ধাধানো মনী-মুক্তা,স্বর্ণ,হীরা…
তার চোখ তো ছানাবড়া, সে সব গুলো তার ব্যাগে ঢুকানো শুরু করল,আজ সে সব কিছু নিয়েই ছাড়বে। কিন্তু তখনই তার মনে পড়ল, সে মাত্র ১০ কেজি জিনিস নিতে পারবে।এর বেশি নিলে তার ব্যাগটা ছিঁড়ে যাবে, তাই সে চাইছে সে সব জিনিস নিতে, যেগুলো নিলে তার সবচেয়ে বেশি লাভ হবে।
সব জিনিস ছোট ছোট বাক্সে রাখা আছে, এই বাক্স ভেঙ্গে নেয়ার মত টাইম তার নাই। তাই কোন কিছু নিতে হলে হয় তাকে সম্পুর্ণ্টাই নিতে হবে নতুবা নিতে পারবে না, যেমন স্বর্ণ যে বাক্সে আছে, তার ওজন ৫ কেজি, তাই তাকে স্বর্ণ নিতে হলে ৫ কেজিই নিতে হবে।
তার সব কিছুর মার্কেট প্রাইজ জানা(চুরি করতে এসেছে, দাম না জানলে কি হয়!!)।কিন্তু সে কিছুতেই হিসেব করতে পারছে না, কি কি নিলে তার সবচেয়ে বেশি লাভ হবে। সে একটা চার্ট বানিয়ে ফেললঃ

জিনিসের নাম	ওজন(কেজি)	দাম(একক)
স্বর্ণ	৫	৬
হীরা	৭	১৪
মুক্তা	৪	৪
মুর্তি	২	১

ভাল হত, যদি সে ৭ কেজি হীরা নিয়ে তারপর ৩ কেজি স্বর্ণ নিতে পারত, কিন্তু স্বর্ণ নিতে হলে তাকে পুরো ৫ কেজিই নিতে হবে, তখন ৭+৫=১২,যা তার ব্যাগের ধারণক্ষমতার বাইরে।
এটাই হল ০/১ ন্যাপসাক(0/1 knapsack)
০/১ মানে হল না নিলে কিছুই নেয়া যাবে না, আর নিলে পুরোটাই নিতে হবে।
সোজা কথায় 0/1 knapsack মানে হলঃ আমাকে ব্যাগের সাইজ m দেয়া আছে, আর n সংখ্যক জিনিসের দাম ও ওজন দেয়া আছে, আমাকে এমন ভাবে জিনিস নিতে হবে,যাতে করে তাদের ওজন m এর বেশি না হয় আর দাম সবচেয়ে বেশি হয়।

এবার,কয়েন চেঞ্জ(coin change) এর এলগরিদমটা দেখে আসুন, তারপর নিচের অংশ পড়ুন,এতে বুঝতে সুবিধা হবে algorithm coin change।
কয়েন চেঞ্জ এ একটা কয়েন অনেকবার নিলেও প্রবলেম ছিল না, কিন্তু এখানে একটা জিনিস একাধিকবার নেয়া যাবে না। এজন্য 2d array লাগবে।
ধরি,জিনিসগুলোর দাম আছে values[] array তে, weight আছে weight[] array তে, আর কয়টা জিনিস আছে, তা আছে item variable এ,ব্যাগের ওজন দেয়া আছে knapsack_weight variable এ।
ধরি,যে 2d এরেটা লাগবে, তার নাম profit[][]. Profit[i][j] মানে হল, i তম জিনিস পর্যন্ত j ওজন পর্যন্ত বেস্ট solution কোনটা, মানে মোট কত কেজি জিনিস আলীবাবা তার ব্যাগে নিতে পারব।যেমনঃprofit[2][5] মানে হল, প্রথম ২ টা জিনিস নিয়ে এখন পর্যন্ত চেক করা হয়েছে, আর ব্যাগের ওজন ৫ হলে সে কত কেজি পর্যন্ত নিলে সবচেয়ে বেশি দাম পাবে।তাই profit[item][knapsack_weight] এ থাকবে, আলীবাবা তার ব্যাগে করে সর্বোচ্চ কত ওজনের জিনিস নিতে পারবে,যাতে লাভ সবচেয়ে বেশি হয়।…(….)”

আর দেরি না করে পুরোটা পড়ে নিনঃ https://sites.google.com/site/programinggconcept/0-1-knapsack

কেউ কোন ভুল পেলে বা কোন মতামত থাকলে জানাবেন,এই ই-মেইল আড্রেসঃ concept_right@yahoo.com