4

বাইসেকশন মেথড বেসিক টিউটোরিয়াল

বাইসেকশন মেথড

আচ্ছা তোমাকে যদি বলা হয় একটা কম্পিউটার প্রোগ্রাম লিখ, যেটা যেকোনো একটি সংখ্যা x  (x>=0)এর বর্গমূল বের করবে , যেটা কে ইংরেজী তে বলে square root. যারা প্রোগ্রামিং ল্যাঙ্গুয়েজ জানে, তাদের কাছে ব্যাপার টা সোজা। কারন প্রায় সব প্রোগ্রামিং ল্যাঙ্গুয়েজ এই sqrt() নামে ফাংশন আছে , যা সহজেই বর্গমূল বের করে দিবে। কিন্তু এখন যদি বলা হয় যে, cubic root/ ³√x অথবা 4√x  বের করতে হবে, তখন কি করব? হুম… চিন্তার ব্যাপার। কারন এই রকম কোন built in ফাংশন সাধারন প্রোগ্রামিং ল্যাঙ্গুয়েজ এ নাই! তাইলে উপায় ??

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

২ ৪ ৫ ১১ ১৫ ২০

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

১। যতোগুলা সংখ্যা দেয়া আছে, সবগুলা একটা একটা করে দেখা যে সংখ্যা টি ৪ কিনা।

২। বাইনারী সার্চ করা

প্রথম উপায়ে টা আসলে সবসময়েই কাজ করে, কিন্তু আমাকে যদি ১০০০০০০ টা সংখ্যা দেয়া হয়, তাহলে এই পদ্ধতি টা অনেক ধীর গতির হবে। সবচেয়ে খারাপ ক্ষেত্রে আমাকে পুরো ১০০০০০০ টা সংখ্যাই দেখতে হবে। Big Oh notation এ যদি ব্যাপার টাকে বলা হয়, তাহলে order হবে O(N) [যেখানে N হচ্ছে কতগুলো সংখ্যা দেয়া হল]।

এইতো গেল প্রথম উপায়।

এইবার আসি, দ্বিতীয় উপায়ে…

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

২ ৪ ৫ ১১ ১৫ ২০

এখন আমাকে ৪ খুজতে হবে। আমাকে ৬ টা সংখ্যা দেয়া হয়েছে। এখন প্রথম মধ্যমা টা নির্ধারণ করি। মধ্যমা ১= (১+৬)/২=৩.৫=৩ [স্বাভাবিক সংখ্যায়ে প্রকাশ করা হোল] , প্রথম মধ্যমা টা হচ্ছে ৩য় সংখ্যা টি অর্থাৎ ৫। এখন আমরা চাচ্ছি ৪, পেলাম ৫। হোল না । তাহলে আমাকে আবার সার্চ করতে হবে। কিনতু এখন একটা ব্যাপার দেখ, ৫ > ৪। তাহলে ৫ এর পরে যত সংখ্যা আছে  সবই তাহলে ৪ এর থেকে বড় , কেননা সংখ্যা গুলো ছোট থেকে বড় এভাবে সাজানো। তাহলে আমরা একটা কাজ করতে পারি না! ৫ এর পর যারা আছে তাদের কে আমরা হিশাব থেকে বাদ দিতে পারি না? হুম… অবশ্যই পারি। আমরা এখন দেখব ১ম থেকে ৩য় সংখ্যা এর মাঝে ৪ আছে কিনা। আবার মধ্যমা নির্ধারণ করি। মধ্যমা ২= (১+৩)/২=২। অর্থাৎ ২য় সংখ্যাটি। আর সেটা হচ্ছে ৪। আরি… আমরা ৪ পেয়ে গেছি।

মাত্র ২ ধাপে আমরা ফলাফল পেয়ে গেছি , তাই না? একারনে বাইনারি সার্চ এর অর্ডার O(logn)। উম… ১ম উপায়েও তো ২ ধাপেই ফলাফল পেতাম, তাইলে লাভ টা কি হল? বলছি… তোমাকে যদি ১১ খুজতে দেয়া হয়, তাহলে তুমি কয় ধাপে ফলাফল পাবা ? ৫ ধাপে। কিন্তু বাইনারি সার্চ দিয়ে ২ ধাপেই পেয়ে যাবা। কিভাবে? নিজেই চেষ্টা করে দেখ।

এতক্ষন খালি বাইনারি সার্চ নিয়া বয়ান আর গুনগান ছারলাম। কিন্তু আমার মেইন টপিক তো বাইসেকশন !! সেটার কি হবে? আসছি তাতে……

বাইসেকশন আসলে বাইনারি সার্চ এর ই এক ভাই। বাইনারি সার্চ sorted  sequence এ খুজে বের করে, আর বাইসেকশন সমীকরণ এর মধ্যে খুজে বের করে। তবে এর ও একটা শর্ত আছে, সেটা হচ্ছে সমীকরণ টিকে x এর সাপেক্ষে ঊর্ধ্বমুখী অথবা নিম্নমুখি হতে হবে। যেমনঃ y=x, y=x*x ইত্যাদি। এখানে x এর মান যত বারাচ্ছি y এর মান তত বারতেছে অথবা এর উল্টো টা । এরকম ক্ষেত্রে বাইসেকশন করা যাবে। কারন দেখ যে,  ব্যাপার টা কিন্তু ছোট থেকে বড় ভাবে সাজানো সংখ্যা এর মতোই, তাই না?

আমরা তো বাইনারি সার্চ কি তা জানি, এখন একি ভাবে বাইসেকশন এ কি হয় তা দেখব। ধরো আমরা বের করতে চাই ১৬ এর বর্গ মুল । বর্গমূল এর সাধারন সমীকরণ কি? y=root(x) . এখানে x=16 বসালে আমরা y এর মান ৪ পাবো। এই সমীকরণ টা কিন্তু ঊর্ধ্বমুখী [increasing] । তুমি যথাক্রমে, x=4, x=9, x=16 বসাও । দেখবে y এর মান বেড়ে যাচ্ছে।

যাই হোক, এখন আমরা  এই সমীকরণ টাকে এভাবে লিখতে পারি

y=x*x

কিভাবে, আমি যদি x=4 বসাই তাহলে কি পাচ্ছি y=16. তাহলে ব্যাপার টা একি দাঁড়াচ্ছে। শুধু চলক গুলো [variable] পরিবর্তন করলাম এই যা।

এখন আমরা বাইসেকশন করার জন্য লিমিট ঠিক করব। আগে বাইনারি সার্চ করার জন্য আমাদের লিমিট ছিল ১ থেকে যতোটি সংখ্যা দেয়া হয়েছে। এবার লিমিট হচ্ছে ০ থেকে আমাদের কে যতো সংখ্যা এর বর্গমূল বের করতে হবে।

তো শুরু করা যাক, আগের মত করে মধ্যমা বের করি প্রথমে,

মধ্যমা ১= (০+১৬)/২=৮। এখন ৮ টাকে আমাদের সমীকরণ টাতে বসাই, y=64 পাই যা ১৬ থেকে অনেক বড়। তাহলে আমাদের লিমিট আরেকটু কমাইতে হবে। নতুন লিমিট ০ থেকে ৮। নতুন মধ্যমা বের করি, মধ্যমা ২= (০+৮)/২=৪ ।  সমীকরণ টাতে ৪ বসাই, কি পাচ্ছি ? y=16 তাই না ? যা আমরা যেই সংখ্যা এর বর্গমূল চেয়েছিলাম সেটাই। তাহলে ১৬ এর বর্গমূল ৪। কাজ শেষ। সহজ জিনিশ তাই না ? এখন  বদলে তুমি  যদি x*x*x , x*x*x*x*x বসাও তাহলে কিন্তু তুমি  ও বের করে ফেলতে পারবে। ACM Programming Contest, Programming/ Algorithmic Problem solving এ বাইনারি সার্চ আর বাইসেকশন অনেক কাজে লাগে। পরে সেটা নিয়ে আলোচনা করব আরেক দিন [যদি আপনাদের এই লেখা ভালো লাগে 😉 ]। এবার বাইনারি সার্চ এবং বাইসেকশন এর c++ code দেখবো। নিচের লিঙ্ক গুলোতে ক্লিক করো।

বাইনারি সার্চ : http://ideone.com/iza80 , http://pastie.org/8427581

বাইসেকশন: http://ideone.com/oQEap , http://pastie.org/8427578

প্রব্লেমঃ UVA 10341 (http://uva.onlinejudge.org/external/103/10341.html)

[ নোট : বাইসেকশন কোড এ দশমিক সংখ্যা নিয়ে কাজ করার জন্য কিছু কাজ করা হয়েছে, না বুঝে থাকলে অবশ্যই জিজ্ঞাশা করতে হবে J ]

[ নোট : যদি কোন কিছু বুঝতে সমস্যা হয় তবে, মন্তব্য এর স্থানে জিজ্ঞাসা করুন, অথবা আমাকে মেইল করুনঃ faiyaz26 [at] gmail [dot] com এ ]

0

Finished developing NSUCC’s official Website

After 1 month work , and other CC member’s help finally , development of NSUCC’s [North South University Computer Club] official website is finished. I am the webmaster of NSUCC’s website. Still some works hasn’t implemented yet, like blogging facilty and others, hope will finish those by next month. You can check the website , any comment will be appreciable.

I used WordPress to build this site.

Website Link: www.nsucc.org

0

বাংলাদেশি অনলাইন জাজ- লাইট ওজে [Light OJ]

অনলাইন জাজ কি?
wikipedia বলছে- “An online judge is an online system to test programs in programming contests. They are also used to practice for such contests. Many of these systems organize their own contests. The system can compile and execute codes, and test them with pre-constructed data. Submitted code may be run with restrictions, including time limit, memory limit, security restriction and so on. The output of the code will be captured by the system, and compared with the standard output. The system will then return the result. When mistakes were found in a standard output, rejudgement using the same method must be made.”

যারা প্রোগ্রামিং প্রবলেম সল্ভ করতে পছন্দ করেন , তারা সবাই UVA,SPOJ,TIMUS .. এর নাম জানেন। বিশেষ করে অনেকেই এ প্রবলেম সল্ভিং এ পদধূলি [নাকি হাতধুলি] দেন , UVA দিয়ে।

সময় এসেছে নিজের দেশের OJ দিয়ে প্রবলেম সল্ভিং এ যাত্রা শুরু করা। বাংলাদেশের OJ , LIGHTOJ.
যার লিঙ্ক হচ্ছেঃ http://180.211.224.73/lightoj/index.php

এই OJ এর নির্মাতা জানে আলম জান ভাই। তিনি গুগল এ কর্মরত । তিনি UVA তে ২২০০+ প্রবলেম সল্ভ করেছেন । ২০০৯ সালে ACM Final এ অংশ নিয়েছিলেন।

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

এক নজরে LightOJ:
Number Of Problems: 300+ [Increasing]
Forum: Yes
Chat: Yes
Viewing other’s codes: Yes, after having AC for that problem
Creating Contest: Yes
User Statistics: Yes

এখনো LightOJ এর রেজিস্ট্রেশান On Request এ চলছে।
আপনি যদি LightOJ এর আইডি নিতে চান , তাহলে
এই ঠিকানায় ইমেইল করুন : jan876_du [at] yahoo [dot] com

শুরু করুন বাংলাদেশি OJ তে প্রোগ্রামিং। বাংলাদেশ কে ACM জিতাতে নিজেকে গড়ে তুলুন।

0

NSUCC প্রকাশনা

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

আরিজ ভাই [https://www.facebook.com/areez.khan] . তাকে হাজারো ধন্যবাদ 🙂

This slideshow requires JavaScript.

0

পাই [π] এবং টাউ [τ] সঙ্গীত

কি ভাই নাম শুনে কিঞ্ছিত বিভ্রান্ত? হওয়াটাই স্বাভাবিক। পাই আর টাউ লাগে পদার্থ আর গনিত এ । সঙ্গীত এ এর ব্যবহার আসলো কোত্থেকে !!

Michael Jhon Black নামে এক ভদ্রলোক পাই আর টাউ এর মান নিয়া সংগীত বানাইসেন। কিভাবে তিনি এটা করসেন টা ভিডিও টাতেই আছে। তিনি এই constant গুলো এর মান কে মিউজিক্যাল নোট এ পরিবর্তন করেছেন, এবং বিভিন্ন বাদ্য যন্ত্র দিয়ে সেই নোট গুলো বাজিয়েছেন। নিচে youtube এর লিঙ্ক দেয়া হইছে। শুনিয়া বলিবেন যে কেমন লাগিল …

পাই সঙ্গীত- http://www.youtube.com/watch?v=YOQb_mtkEEE
টাউ সঙ্গীত-http://www.youtube.com/watch?v=3174T-3-59Q

2

একটা অনলাইন বাংলা রেডিও প্লেয়ার বানাইলাম !

১ দিনে ভিসুয়াল বেসিক শিখেই ভাবলাম একটা সফটওয়্যার বানাই যেটা সবাই ব্যাবহার করতে পারবে। এর আগে C,C++ আর Java দিয়ে কিছু সফটওয়্যার বানাইসিলাম, কিন্তু সেগুলা user friendly না। যাই হোক যেই ভাবা সেই কাজ শুরু করা। বানায়ে ফেললাম অনলাইন বাংলা রেডিও প্লেয়ার। খুবি simple কাজ, এবং simple interface । ব্যাবহার করে দেখতে পারেন। এরকম সফটওয়্যার নেট এ অনেক পাওয়া যায়, তারপরেও এটা ব্যাবহার করে  দেখুন, এবং জানান আপনাদের মতামত। আপনাদের যদি ভালো লাগে তবে software টা upgrade  করার try করব।

[বিঃ দ্রঃ সফটওয়্যার টি শুধু মাত্র windows ব্যাবহার কারি দের জন্য। আমি ভিসুয়াল বেসিক এ নতুন, তাই এখনো বুঝতে পারি নাই যে প্লেয়ার টা চালাইতে PC তে কি কি থাকা লাগবে। যদি আপনার PC তে না চলে, তবে দয়া করে আপনার windows এর version এবং .NET framework এর ভার্সন টা জানাইয়েন।

ধন্যবাদ আপনাকে।

নামঃ Bangla Streamer

লিঙ্কঃ http://www.mediafire.com/?du169igzwgdfnqj