মূল বিষয়বস্তু
কম্পিউটার বিজ্ঞান
কোর্স: কম্পিউটার বিজ্ঞান > অধ্যায় 2
পাঠ 7: দৈব অ্যালগোরিদম- দৈব অ্যালগোরিদম (সূচনা)
- শর্তাধীন সম্ভাব্যতা চিত্র ব্যাখ্যা করা হয়েছে
- মুদ্রাটি অনুমান কর
- দৈবভাবে মৌলিক সংখ্যা যাচাই (প্রস্তুতি)
- লেভেল 9: ভাগের প্রচেষ্টা বনাম দৈবভাবে ভাগ
- ফার্মার ছোট তত্ত্ব
- ফার্মার মৌলিক সংখ্যা যাচাই পরীক্ষা
- লেভেল 10: ফার্মার মৌলিক সংখ্যা যাচাই পরীক্ষা
© 2023 Khan Academyব্যবহারের শর্তাদিগোপনীয়তার নীতিমালাকুকি নোটিশ
দৈব অ্যালগোরিদম (সূচনা)
দৈব সংখ্যাগুলো কীভাবে একটি ডিসিশন অ্যালগোরিদমের গতি বৃদ্ধি করতে পারে? এটি তৈরি করেছে ব্রিট ক্রুজ
আলোচনায় অংশ নিতে চাও?
কোন আলাপচারিতা নেই।
ভিডিও ট্রান্সক্রিপ্ট
## আগামী ও গ্রামীণফোন এর সহযোগিতায় অনূদিত ## সাম্প্রতিক তথ্য হল, নাসার মতে রোভারে এলোমেলো হার্ডওয়্যার নাম্বারের ব্যবহার থাকবে যা ব্যবহার করা যাবে। সেই সাথে তারা আমাদের মনে করিয়ে দিয়েছে যে, আমাদের এলগরিদম চর্চা করতে হবে। চর্চা করার সময়, প্রায়ই ভুল (e) হবার সম্ভাবনা থাকে, কিন্তু এই ভুলের সম্ভাবনা এত কম যে আমরা চর্চার সময় প্রায়ই এটি বিবেচনা করি না। বাস্তবে, কোন কিছুই নিশ্চিত নয়, সবসময়ই ভুল হবার একটি সম্ভাবনা থেকে যায়। উদাহরনস্বরূপ, চিপ প্রক্রিয়াকরনের সময় কিছু পরিমানে দূষণকারী তেজস্ক্রিয় বস্তু থাকে এবং যখন এগুলো ক্ষয়ে যায়, এগুলো আলফা থেকে কণা নির্গত হয় যা আসলে স্মৃতিতে অবস্থিত বিট কে মৃদু আঘাত করে এবং হয়ত সংখ্যাকে অপ্রত্যাশিত ভাবে পাল্টে দেয় আরো মজার ব্যাপার হল, মহাজাগতিক রশ্নিও অল্প ক্ষতি করতে সক্ষম তাই কখনোই ভুল হবার সম্ভাবনাকে সম্পুর্ণরূপে নির্মূল করা যায় না। নাসাকে প্রশ্ন করা হয়েছিল যে, ঠিক কতটুকু সম্ভাব্য ভুল গ্রহণযোগ্য? তাদের মতে, ‘আমরা নিশ্চিত হতে চাই যে, কোন পরীক্ষায় সম্ভাব্য ভুল, e-এর পরিমাণ এমন যে একটি লটারীকে পরপর দুইবার আঘাত করার থেকে যেন কম হয়।" লটারীতে আঘাত করা, হল দু'বার ৬৪৯ ৬ গুন ১০ এর ঋণাত্মক সূচক চৌদ্দ এর সমান যা সহজ করে বললে সম্ভাব্য ভুল হল ১০ এর ঋণাত্মক সূচক ১৫, যা যথেষ্ট নিরাপদ; আমরা ভুল দেখতে চাই না এবং এটা একশ কিংবা হাজারবার হতে পারে। এখন প্রশ্ন হল এলোমেলো ভাবে কি আমাদের প্রাইমালিটি পরীক্ষায় অ্যালগরিদমে দ্রুত সিধান্ত নিতে সাহায্য করবে? এটা একটি গুরুত্তপূর্ণ প্রশ্ন, তাহলে পিছনে ফিরে একবার চিন্তা করি। পূর্ণসংখ্যার কিছু সংগ্রহের মধ্য থেকে, ধরি, ১ থেকে N এর মধ্যে সকল পূর্ণ সংখ্যা রয়েছে। সবসময়ই সংগ্রহকে দুটি সেটে বিভক্ত করা যায়। একটি সিদ্ধান্ত গ্রহণকারী সমস্যাকে পূর্ণসংখ্যার কিছু সংগ্রহ থেকে সেটে বিভক্ত করা যায়। যেমন, N নেই যা ১০০ এর থেকে ছোট এর ফলাফল ১০০ এর নিচে সকল পুর্ণসংখ্যার
ক্ষেত্রে ইতিবাচক হবে। এখানে সংগ্রহ আছে কিন্তু বাকিগুলোর ক্ষেত্রে নেই আর এটি হল আরেকটি সংগ্রহ দল। ঠিক আছে, এখন সিদ্ধান্তের মাধ্যমে মৌলিক সংখ্যা মনোযোগ দিয়ে চিনে নেই এক্ষেত্রে সাধারনভাবে গণনা করাই সুবিধাজনক যেখানে সকল মৌলিক সংখ্যা সত্য হবে এবং কোন যৌগিক সংখ্যা সত্য হবে না। এখন যদি এমন কোন সহজ প্যাটার্ন নেয়া হয় যা সকল মৌলিক সংখ্যার স্থান এবং শুধু মৌলিক সংখ্যা। তাহলে প্রদত্ত N এই প্যাটার্ন কে অনুসরণ করে কিনা তা আমরা সহজেই পরীক্ষা করতে পারি। কিন্তু সমস্যা হল, এখন পর্যন্ত, শুধু মৌলিক সংখ্যা এবং যৌগিক সংখ্যা নয় এমন অথবা শুধু যৌগিক সংখ্যা এবং মৌলিক সংখ্যা নয় এমন কিছু নির্ণয়ের জন্য কোন নির্দিষ্ট প্যাটার্ন আবিষ্কার করা সম্ভব হয়নি। কিন্তু যৌগিক সংখ্যার জন্য দ্রুত পরীক্ষার বিষয়টি আমরা জানি। উদাহরনস্বরূপ, গণনার একটি সাধারণ বৈশিষ্ট্য হবে এগুলো জোড় সংখ্যা এবং সকল জোড় সংখ্যা ২ দ্বারা বিভাজ্য। এটি দ্রুত পদ্ধতি কারন শুধু শেষের অঙ্ক দেখেই বলা যায় যে সংখ্যাটি জোড় কি না এবং N বৃদ্ধি পেলেও, সমস্যাটি আরো জটিল হচ্ছে না শুধু শেষের অঙ্ক খেয়াল রাখতে হবে। এখন খেয়াল কর যে, আমরা জোড়ের পরীক্ষাটি যৌগিক সংখ্যার পরীক্ষা হিসেবে ব্যবহার করতে পারি সেখানে আমরা পূর্ণসংখ্যা N বাদে কিছু এলগরিদম পেতে পারি এবং এলগরিদম পরীক্ষা করে দেখবে তা জোড় সংখ্যা কিনা যদি জোড় সংখ্যা এবং ২ এর থেকে বড় হয়, তাহলে আমরা শতভাগ নিশ্চিত যে এটা যৌগিক সংখ্যা হবে কারন আমাদের কাছে এর প্রমান আছে ধরে নেই, দুই যৌগিক সংখ্যার প্রমাণ। কিন্তু, যদি তা না হয়, তাহলে আমরা নিশ্চিত নই। যদি বিজোড় হয় তবে এটি মৌলিক হতে পারে যেহেতু সকল মৌলিক সংখ্যা বিজোড় বা যেসব যৌগিক সংখ্যা বিজোড় তাদের মধ্যে থেকেও হতে পারে, যেমন শুধু ৯ বা ১৫। বিজোড় যৌগিক সংখ্যার এই বিশাল ক্ষেত্র পরীক্ষার জন্য অগ্রহণযোগ্য। বুঝতে, এটি আঁকি। N দেয়া আছে, N মৌলিক বা যৌগিক যেকোন সংখ্যা হতে পারে। যদি N মৌলিক সংখ্যা হয়, আমাদের এলগরিদমও ১০০% নিশ্চয়তায় একে মৌলিক সংখ্যা বলবে যেহেতু ২ থেকে বড় কোন মৌলিক সংখ্যাই জোড় নয়। ফলাফল মৌলিক হলে, এটি কখনোই যৌগিক সংখ্যা দেখাবে না। এখন, N যৌগিক সংখ্যা হলে ৫০% সময়ই এলগরিদম ফলাফলে যৌগিক সংখ্যা দিবে। এবং বাকি ৫০% সময় মৌলিক সংখ্যা। অর্থাৎ, এলগরিদম ফলাফল যৌগিক সংখ্যা দেয় তার মানে এটা যৌগিক সংখ্যার জন্য প্রমাণ খুঁজে পেয়েছে এক্ষেত্রে, এলগরিদমের ফলাফল মৌলিক হলে, ভুল হবার বড় একটি সম্ভাবনা থাকে। এখন পর্যন্ত, আমাদের পরিকল্পনা হল পুনরাবৃত্তির মাধ্যমে এই বড় ভুলের মোকাবেলা করা এবং এসো, এর প্রবাহ চিত্রিত করি। N দেয়া আছে, আমাদের যন্ত্র A, ২ থেকে শুরু করে A-তে অবস্থিত কতগুলো বিভাজ্যতা পরীক্ষার ক্রম সম্পন্ন করছে। এটি প্রশ্ন করে, N কি A দ্বারা বিভাজ্য? যদি এটা N কে ভাগ না করতে পারে, তাহলে আমরা এই পুরো অংশ সরিয়ে ফেলতে পারি তারপর এটি পরের প্রশ্ন করছে, N কে ৩ দ্বারা ভাগ করা যায় কি? যদি না হয় তাহলে আমরা এই অংশটি বাদ দিতে পারি। N কে ৫ দ্বারা, ৭ দ্বারা এবং এমন আরো সংখ্যা দ্বারা ভাগ করা যায় কি? খেয়াল করলে দেখব, এগুলো হল অসংলগ্ন সেট যা ধীরে ধীরে সকল যৌগিক সংখ্যাকে পুরণ করছে। এখন আমরা যদি উত্তর "হ্যাঁ" দেই, তাহলে আমাদের প্রমাণ আছে যে N হল যৌগিক সংখ্যা। A, এই বিন্দুতে এটি যাই হোক না কেন, এটাই আমাদের প্রমাণ। এলগরিদম থেকে N সংখ্যা বিশিষ্ট যৌগিক সংখ্যা পেলাম না হলে, যতক্ষণ পর্যন্ত না আমরা সকল সম্ভাব্য যৌগিক সংখ্যা পাচ্ছি, ততক্ষণ চেষ্টা করে যাব। যতক্ষন না আমরা N এর বর্গমূল পাচ্ছি মনে রেখ, যৌগিক সংখ্যা N এর উৎপাদক থাকতে হবে যা N এর বর্গমূলের উৎপাদক থেকে কম বা সমান হবে। এটি এলগরিদমের শেষ প্রশ্নের দিকে নিয়ে যায়। যদি কোন প্রমাণ পাওয়া না যায়, এবং A যদি N এর বর্গমূল থেকে বড় হয় তাহলে আমাদের প্রমান পাব এবং আমরা ফলাফল হিসেবে মৌলিক সংখ্যায় থেমে যাব এলগরিদমের মাধ্যমে বের হবার দুটি পথ আছে। উভয় রাস্তাই প্রতিনিধিত্ব করছে যে হয় N মৌলিক অথবা যৌগিক সংখ্যা। যখন N মৌলিক, আমরা সকল ভাজক নিয়ে এদেরকে পরীক্ষা করে বাদ দিয়ে দেই, এবং এতে প্রমান হয় যে, N হল মৌলিক সংখ্যা তবে, পদ্ধতির সমস্যা হল, আমাদের পরীক্ষার মান A কে ২ থেকে শুরু করে N এর বর্গমূল পর্যন্ত সকল মৌলিক সংখ্যার মধ্যে পরীক্ষা করতে হয়। যখন N এর সংখ্যা বৃদ্ধি পায়, তখন মৌলিক সংখ্যাও বৃদ্ধি পায় এটা অনেক পুনরাবৃত্তির সৃষ্টি করে যখন আমরা আমাদের এলগরিদমে মৌলিক সংখ্যা দেই। এটি দেখি, খেয়াল কর, N মৌলিক হলে প্রমাণ পাওয়া যায়। আমরা জানি, এটা আমাদের এখন আর প্রয়োজন নেই। কেউ বলছে না এটা প্রমাণ করতে। আমাদের শুধু ৯৯.৯৯৯৯ পনের সুচক ৯ ভাগ নিশ্চিত হতে হবে। তাহলে আমাদেরকে এলগরিদমে ব্যবহৃত যৌগিক সংখ্যা নির্ণয়ের পরীক্ষা সম্পর্কে চিন্তা করতে হবে। মনে করে দেখ যে আমাদের দ্রুততম প্রাইমালিটি পরীক্ষা, যেমন ৬K বা সকল মৌলিক সংখ্যা হল ৬K যোগ বা বিয়োগ ১ এর রুপে, সময় কমিয়ে মৌলিক সংখ্যাকে আলাদা করতে এবং যৌগিক সংখ্যাকে বাদ দিতে ব্যবহার করা হচ্ছে। মনে রাখবে যে, এমন একটি পরীক্ষা যৌগিক পরীক্ষাতেও রুপান্তর করা যায়। তা হল, প্রদত্ত পূর্ণসংখ্যা N কে ৬K যোগ বা বিয়োগ ১ এ রুপান্তর করা আমরা বলতে পারি যে এটি হয়ত মৌলিক কিন্তু এখানে এখনও অনেক যৌগিক সংখ্যা আছে যা এই প্যাটার্নকে অনুসরন করে। এটা শুধু মৌলিক সংখ্যাকেই অন্তর্ভুক্ত করছে না, বরং সকল মৌলিক সংখ্যা এবং আরো কিছু যৌগিক এবং আমরা এই অতিরিক্ত যৌগিক সংখ্যাকে আমরা ভুলের উৎস ধরে নিতে পারি। এখন আমরা যদি একে উল্টিয়ে সম্পন্ন করতে চাই এবং বলি যে, ৬K যোগ বা বিয়োগ ১ রুপে N নেই, তাহলে আমরা শতভাগ নিশ্চয়তার সাথে বলতে পারি যে এটা যৌগিক সংখ্যা তাহলে আমাদের ভুলের উৎস হল মৌলিকের দিকে। কিন্তু এক্ষেত্রে এটি অগ্রহণযোগ্য। এটি হবার অনেক বড় সম্ভাবনা আছে। আমাদের নতুন একটি যৌগিক পরীক্ষা নির্বাচন করতে হবে যেখানে ভুলের পরিমান অতি নগন্য হবে। অর্থাৎ, আমাদেরকে পুনরাবৃত্তির মাধ্যমে ভুলের পরিমাণ কমিয়ে আনতে হবে। আমার মনে হয় আমরা কোন ধরণের পরীক্ষা সম্পন্ন করতে চাই তা বলতে পারব এবং এলোমেলো সংখ্যা ব্যবহার আমাদের কিভাবে সাহায্য করবে তাও আমরা বলতে পারব। ## আগামী ও গ্রামীণফোন এর সহযোগিতায় অনূদিত ##