প্রব্যাবিলিটি থিররী (Probability Theory)| সম্ভাবনা থিওরী । সম্ভাবনা তত্ত

সম্ভাবনা থিওরী কি?

1 tk coin 3

মনে কর তুমি একটি কয়েন নিয়ে টস করবে। তুমি কি নির্দিষ্ট করে বলতে পারবে টস এর ফলাফল কি হবে শাপলা নাকি মানুষ?

উত্তর হল পারবেনা। বিজ্ঞানের জগতে এটি নির্দিষ্ট করে বলার মত কোন সুত্র নেই। নির্দিষ্ট করে বলতে পারিনা করান “প্রকৃতি সেই তথ্যটা আমাদের কাছ থেকে আড়াল করে রেখেছে” (বলেছেন মুহম্মদ জাফর ইকবাল @ একটুখানি বিজ্ঞান )।

কিন্তু তুমি যদি বার বার টস করতে থাক তাহলে ফলাফলগুলোর মাঝে একটা প্যাটার্ন বা মিল প্রদর্শন করতে শুরু করবে। যেমন, ১০ বার টস করলে ৫ বার শাপলা বাকি ৫ বার মানুষ হবে। একটু ভুল বললাম। কারন ৫ বার শাপলা ৫ বার মানুষ হবেই এটা বলা যাবে না। কিন্তু বলা যায়, ১০ বার টস করলে ৪ শাপলা ৬ বার মনুষ আসতে পারে। কিংবা ৭ বার শাপলা ৩ বার মানুষ আসতে পারে। কিন্তু উভয় ক্ষেত্রেই মোট শাপলা বা মোট মানুষ হওয়ার ফলাফল ৫ এর কাছাকাছি হবে। ১০০ বার টস করলে আরও ৫০ এর কাছাকাছি হবে।

বোঝাই যাচ্ছে কিছু ব্যাপার আছে যেগুলো সুনির্দিষ্ট করে বলা সম্ভব নয়। কিন্তু এভাবে বলা যায়, যেমন “হতে পারে, আসতে পারে, সম্ভাবনা আছে ইত্যাদি।” কিন্তু কিভাবে বলব কতটুকু সম্ভাবনা আছে। অর্থাত কোন কিছু হওয়ার বা ঘটার সম্ভাবনা কিভাবে পরিমাপ করা যায়। সেই বিষয়গুলোকে একত্রে বলা হয় প্রব্যাবিলিটি থিররী (Probability Theory) বা সম্ভাবনা থিওরী বা সম্ভাবনা তত্ত .

Advertisements

ফাংশন | ক্যালকুলাস

ফাংশন কি?

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

এবার একটু গণিতে ভাষায় আসি।

ধর,  হল একটি ফাংশনের ইনপুট। ফাংশনটি সবসময়  কে বর্গ করে অর্থাত । ধরি, বর্গ করলে সেটি  হয়। তাহলে  হল আউটপুট। এটাকে নিচের মত করে লেখা হয়।

এখানে ইচ্ছেমত ইনপুট দিতে পারি। যেমন 4, 1, -5, 0 এগুলো ইনপুট দিলে আউটপুট আসবে যথাক্রমে 16, 1, 25, 0

ভাব দেখানোর জন্য গনিতবিদরা ইনপুট গুলোকে বলে ডোমেইন আর আউটপুট গুলোকে বলে রেঞ্জ। আচ্ছা উপরের ফাংশনের ডোমেইন কি কি হতে পারে?

দেখতেই পারছ ইনপুট ধনাত্বক সংখ্যাও দেয়া যায়, শুন্যও দেয়া যায় আবার ঋনাত্বক সংখ্যাও দেয়া যায়। তার মানে সব বাস্তব সংখ্যা হল উপরের ফাংশনের ইনপুট। তাই এর ডোমেইন হল সব বাস্তব সংখ্যা। (বাস্তব সংখ্যা হল সেগুলো যেগুলো অবাস্তব নয়। অবাস্তব সংখ্যাও আসবে। পড়তে থাক।)

আচ্ছা নিচের ফাংশনটির ইনপুট কি কি হতে পারে?

এই ফাংশনে ইনপুট ধনাত্বক বা ঋনাত্বক হতে পারে। কিন্তু শুন্য হতে পারে না (  )। কারন শুন্য দিয়ে কোন কিছুকে ভাগ করলে কি হয় আমরা জানিনা। তাহলে বলা যায় এই ফাংশনের ডোমেইন হল শুন্য বাদে সকল বাস্তব সংখ্যা।

এবার একটু আউটপুট এর দিকে নজর দেই।

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

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

আচ্ছা এখন যদি বলি এমন কোন ইনপুট নাম্বার আছে কি যার জন্য ফাংশনটির আউটপুট ঋনাত্বক হবে? ভাব কিছুক্ষন।

 বা   বা  

এগুলো ইনপুট হিসেবে নিলে আউটপুট ঋনাত্বক হবে। কিন্তু এগুলো কি বাস্তব সংখ্যার মত কোন সংখ্যা? না, বরং বাস্তব সংখ্যাগুলোকে একটু পরিবর্তন করে এই ইনপুটগুলো বনানো হয়েছে। এগুলোকেই বলা হয় অবাস্তব সংখ্যা। ইংরেজিতে বলা হয় ইমেজিনারি নাম্বার (Imaginary Number)।

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

ফাংশন লেখার রীতীনিতি

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

 বা   বা 

ইনপুট কিভাবে প্রসেস করবে সেটি জানা জরুরি না হলে শুধু ইনপুটসহ নামটি  লেখা হয়। যেমন  বা 

ডিফারেন্সিয়েশনের চেইন রুল | ক্যালকুলাস

ক্যালকুলাস এ ডিফারেন্সিয়েশনের একটি নিয়ম হল চেইন রুল। চেইন রুলের সাহায্যে কম্পজিট ফাংশনগুলোর ডিফারেন্সিয়েমন করা হয়।

ফাংশন অংশে কম্পজিট ফাংশন সম্পর্কে ধারনা হয়ে গেছে আ্শা করি। তারপরও একবার মনে করিয়ে দেই।

মনে কর,

এবং

দুটি সাধারন ফাংশন। প্রথম ফাংশনে এর ইনপুট  এবং আউটপুট  আর দ্বিতীয় ফাংশনের ইনপুট  এবং আউটপুট 

এখন যদি এমন হয় যে, দ্বিতীয় ফাংশনের আউটপুটাই হল প্রথম ফাংশনের ইনপুট।অর্থাত,

বা,

এটি হল কম্পজিট ফাংশন। অনেকগুলো ফাংশন এক সাথে করে কম্পজিট ফাংশন তৈরি করা হয়। একটা ফাংশনের আউটপুট আর একটি ফাংশনের ইনপুট।

এই ধরনের ফাংশনগুলো চেইন রুল অনুসরন করে করা হয়।

চেইন রুল

ধর,

এটি একটি সাধারণ ফাংশন যার ইনপুট আর আউটপুট । এখানে ইনপুট তাই এর ডিফারেন্সিয়েশন হবে এর সাপেক্ষে।

(ইনপুট এর পরিবর্তনের জন্য আউটপুট এর কত পরিবর্তন হবে এর ডিফারেন্সিয়েশন করলেই পাওয়া যাবে। )

যদি ফাংশনটি এমন হত,

তাহলে এর ডিফারেন্সিয়েশন হত এর সাপেক্ষে।

এক কথায় ইনপুট এর সাপেক্ষে আউটপুটের পরিবর্তন হবে।

তাহলে,

হয় তাহলে আমরা লিখতে পারি,

? এর স্থানে যা থাকবে তার সাপেক্ষেই ডিফারেন্সিয়েশন হবে।

কিন্তু যদি বলে x এর সাপেক্ষে ডিফারেন্সিয়েশন করতে তখন?

তখন যতক্ষন না x এর সাপেক্ষে ডিফারেন্সিয়েশন পাব ততক্ষন ডিফারেন্সিয়েশন করতেই থাকব আর ডিফারেন্সিয়েশনগুলো গুন করতে থাকব।

এটিই হল চেইন রুল। এখন এত বিস্তারিত বাদ দিয়ে লিখলে এমন হবে। ধরি, f, g, h তিনটি ফাংশন।

লজিক গেট

লজিক গেট কি?

নিচের চিত্রে যে জিনিসগুলো দেখতে পাচ্ছ সেগুলোই লজিক গেট। এগুলোকে সাধারণত IC বলা হয়।

এন্ OLYMPUS DIGITAL CAMERA

এগুলো দিয়ে কি করা হয়?

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

Flow Network / Network flow

Flow Network কি?

ফ্লো-নেটওয়ার্ক হল এক ধরনের নেটওয়ার্ক যেখানে একটি উতস থেকে গন্তব্য পর্যন্ত কোন কিছুর স্থানান্তর নির্দেশ করে। যেমন,

পানির ট্যাংক থেকে পানির প্রবাহ। আবার কোন শিল্প কারখানায় উতপাদিত পন্য বিক্রয়যোগ্য স্থানে প্রেরন করা। বিদ্যুত উতপাদন কেন্দ্র থেকে আবাসিক এলাকায় বিদ্যুত পরিবহন করা।

Flow Network এর সাধারণ বৈশিষ্ট:

  • প্রতিটি ফ্লো-নেটওয়ার্কে যেখানে পরিবহনযোগ্য পদার্থ উতপাদন করা হয় তাকে Source বলা হয়। যেমন বিদ্যুত উতপাদন কেন্দ্র, পানির ট্যাংক।
  • পরিবহনযোগ্য পদার্থ যে গন্তব্যে পাঠানো হয় তাকে Sink বলা হয়। এখানে পদার্থগুলো ব্যবহার (Consume) করা হয়।
  • Source থেকে যে পরিমান পদার্থ পাঠানো হয় Sink এ সে পরিমান পদার্থ পাওয়া যায়। অর্থাত পথের মাঝে কোন মারিং-কাটিং হয় না।
  • যে মাধ্যম দিয়ে পরিবহন করা হয় তা বিভিন্ন ক্ষমতার হতে পারে। যেমন,

ধর তোমার কাছে অনেকগুলো পাইপ আছে। কোন পাইপ মোটা অবার কোন পাইপ সরু। ফলে কোনটা দিয়ে বেশি পানি যায় কোনটা দিয়ে কম পানি যায়। এটি হল পাইপের ধারনক্ষমতা বা Capacity.

বিভিন্ন ধারনক্ষমতার এই পাইপগুলো একটির সাথে আরেকটি সংযোগ দেওয়া হল। এবং এই সংযোগ ট্যাংক থেকে বালটি পর্যন্ত দিয়ে দেওয়া হল। এখন বলতে হবে ট্যাংক থেকে সর্বোচ্চ কি হারে (Rate) বালটিতে পানি প্রবাহিত হবে।

এ ধরনের প্রব্রেমকে বলা হয় Max Flow Problem.

Max Flow Problem প্রব্লেমকে প্রোগ্রামিং এর দুনিয়ায় ডিরক্টেড গ্রাফের মাধ্যমে প্রকাশ করা হয়। এজগুলোর Weight হল মাধ্যমের Capacity.

flowNetwork

প্রতিটি গ্রাফের নোডগুলোকে আমরা ইচ্ছামত দুই ভাগে ভাগ করতে পারি। Source এবং Sink. যেমন:

নিচের গ্রাফে শুধু সোর্স কে আলাদা করা হয়েছে আর বাকি সব নোড মিলে হল সিংক। এভাগে ভাগ করাকে বলা হয় s-t cut.

প্রতিটি s-t cut এর Source অংশের Capacity থাকে। আর এই Capacity এই অংশের সবগুলো এজ এর Capacity এর যোগফলের সমান।

এখন এমনভাবে একটি s-t cut source খুজে বের কর যার Capacity সবচেয়ে কম। এ ধরনের প্রব্লেমকে বলা হয় Min Cut Problem.

রেসিডুয়াল নেটওয়ার্ক: ফ্লো নেটওয়ার্কে কিছু অতিরিক্ত এজ যোগ করে এ নেটওয়ার্ক তৈরি করা হয়। এই অতিরিক্ত এজগুলো দিয়ে বোঝানো হয় কিভাবে ফ্লো পরিবর্তন সম্ভব। কিছু কিছু এজ এর ফ্লো কমে যেতে পারে। ফ্লো কমানো যাবে বুঝাতে বিপরীতমূখী এজ বসানো হয়। ফ্লো নেটওয়ার্কে যেসব এজ এর ফ্লো ঐ এজ এর ক্যাপাসিটির সমান সেসব এজ এই নেটওয়ার্কে থাকেনা। রিভার্স এজ এর রেসিডুয়াল ক্যাপাসিটি হল ঐ এজ দিয়ে যে ফ্লো হয় তার সমান। এটাকে এভাবে বলা যায় যা নিয়েছি তা ফেরত দিয়ে দিলাম। এই ফিরিয়ে দেয়াকে বলা হয় Cancellation.

এটিকে   দিয়ে প্রকাশ করা হয়।

যেমন:

নিচের ফ্লো নেটওয়ার্কটিতে মোট ফ্লো হল ৩। দেখেই বুঝতে পারছ এর ফ্লো বাড়ানো সম্ভব। আমরা লজিক্যালি দেখব এর ফ্লো কিভাবে বাড়ানো যায়।

অগমেন্ট পাথ: Augmenting Path হল রেসিডুয়াল নেটওয়ার্কে Source থেকে Sink পর্যন্ত একটি পাথ। এটি বলে দেয় কিভাবে ফ্লো বাড়ানো সম্ভব।

রেসিডুয়াল ক্যাপাসিটি: রেসিডুয়াল পাথের প্রতিটি এজের ফ্লো যে পরিমান বাড়ানো সম্ভব সেটিই হল রেসিডুয়াল ক্যাপাসিটি।

রেসিডুয়াল এর অর্থ হল ব্যবহারের পর যা অবশিষ্ট থাকে।

ম্যাক্স ফ্লো থীওরি: ফ্লো সর্বচ্চো হবে যদি কোন অগমেন্ট পাথ না থাকে।

এই থিওরি ব্যবহার করে ফোর্ড-ফুলকার্সন এলগরিদম

এলগরিদমের ইমপ্লিমেনটেশন:

ইমপ্লিমেনটেশনের টাইম কমপ্লেক্সিটি:

SCC- ডিরক্টেড গ্রাফ – ডিএফএস(DFS)

স্ট্রংলি কানেক্টেড কম্পনেন্টস্ (Strongly Connected Components )

Strongly Connected Components সংক্ষেপে SCC বলা হয়। এটি শুধু ডিরেক্টেড গ্রাফের জন্য প্রযোজ্য।

একটি ডিরেক্টেড গ্রাফের SCC হল গ্রাফটির এমন এক বা একাধিক অংশ যার সব নোড খেকে সব নোডে যাওয়া যায়। যেমন নিচের গ্রাফটি লক্ষ কর,

ssc

উপরের গ্রাফটিতে ৪ টি SCC রয়েছে। প্রতিটি অংশেই সব নোড খেকে সব নোডে যাওয়া যায়। কিন্তু এক SCC থেকে অন্য SCC তে গেলে আর ফির আশা যায়না।

যেমন: প্রথম SCC-১ খেকে SCC-২ এ গেলে আর ফির আসা যাবেনা।

এখন একটু গণিতবিদ ভাব নিয়ে উপরের কথাগুলোকে নিচের মত করে গাণিতিকভাবে বলা যায়।

ধরি,

G = (V, E) একটি ডিরেক্টেড গ্রাফ। যেখানে V হল ভার্টেক্স বা নোডের সেট আর E হল এজ এর সেট। (গ্রাফ সম্পর্কে ধারণা থাকতে হবে)

এখন ধরি, V এর একটি উপসেট হল C অর্খাত

যদি C এর সব নোড খেকে সব নোডে যাওয়ার পখ খাকে তাহলে C হল Strongly Connected Components.