If you're seeing this message, it means we're having trouble loading external resources on our website.

তোমার যদি কোন ওয়েব ফিল্টার দেওয়া থাকে, তাহলে দয়া করে নিশ্চিত কর যে *.kastatic.org এবং *.kasandbox.org ডোমেইনগুলো উন্মুক্ত।

মূল বিষয়বস্তু

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

কোর্স: কম্পিউটার বিজ্ঞান > অধ্যায় 2

পাঠ 6: মৌলিক সংখ্যা যাচাই

অ্যালগোরিদমিক কর্মক্ষমতা

কীভাবে তুমি একটি মৌলিক সংখ্যা যাচাই পরীক্ষার গতি (নিয়ন্ত্রিতভাবে) বৃদ্ধি করতে পার? এটি তৈরি করেছে ব্রিট ক্রুজ

আলোচনায় অংশ নিতে চাও?

কোন আলাপচারিতা নেই।
ইংরেজি জানো? খান একাডেমির ইংরেজি সাইটে আরো আলোচনা দেখতে এখানে ক্লিক কর।

ভিডিও ট্রান্সক্রিপ্ট

## আগামী ও গ্রামীণফোন এর সহযোগিতায় অনূদিত ## আমার কাছে এখন একটি রিপোর্ট আছে যে তারা মঙ্গল গ্রহে একটি নতুন রোভার পাঠাচ্ছে। এর জন্য আমাদের সংখ্যার মৌলিকতা যাচাই করে এমন একটি এলগরিদম রোভারের ভেতর প্রোগ্রামিং করতে হবে। ধরি, আমাদের রোভার আরএসএ ব্যবহার করে যোগাযোগ করছে। এর ভিতরে একটি এলগরিদম প্রয়োজন যা প্রাইম্যালিটি টেষ্ট করতে পারে। যখন মহাশূন্যে যেতে তুমি একটি রোভার বা অন্য কিছু ডিজাইন করবে, তোমাকে প্রতি ক্ষেত্রে খুব দক্ষ হতে হবে। ব্যবহৃত উপাদানগুলো খুব হালকা হতে হবে। প্রতি সাবসিস্টেমে ব্যবহৃত শক্তির পরিমাণ যৎসামান্য হতে হবে। তোমাকে ডিজাইন পদ্ধতির প্রত্যেক ক্ষেত্রে শক্তি এবং ভর সংরক্ষণ করতে হবে। আমাদের কাজ আমাদের জন্যই সংক্ষিপ্ত করতে হবে। আমরা সংখ্যার এই আকৃতি পর্যন্ত মোকাবেলা করতে সক্ষম হবো। এটা খুব দ্রুত করতে হবে। যদি আমরা এটাকে একটি ছোট ইনপুট দেই, মনে করি ৯০, এটা এই সম্পূর্ণ সংখ্যাটি প্রায় দ্রুত হিসাব করতে সক্ষম হবে। ইনপুট যত বাড়বে, আমরা কোন লক্ষণীয় ধীর গতি দেখতে চাই না। আমি ব্যবহারকারীর প্রশ্ন বা ধারণা বিশ্লেষণ করতে চাই যা গাণিতিক দৃষ্টিকোণ থেকে সত্যিই ভালো। N মৌলিক না কি যৌগিক তা আমরা পরীক্ষা করছি। কোন সংখ্যা N দেয়া আছে, এই স্থানটি N এর সকল সম্ভাব্যতা হিসেবে চিন্তা কর। যদি N ১০০ হয়, এই স্থানটি হল দুই থেকে ১০০। আমাদের এলগরিদম এই স্থান খুঁজতে কী করছে। মনে কর, এলগরিদম একটি স্থান খুঁজছে। প্রত্যেক বিন্দুতে এটা জিজ্ঞেস করছে- মনে কর এটা একটি ধাপ, মৌলিক ধাপ। এটা একটি প্রশ্ন জিজ্ঞেস করছে এবং এটা আসলে একটি যৌগিক পরীক্ষা, প্রশ্নটি। ধরি, A একটি সংখ্যা, পরীক্ষামূলক বণ্টন পদ্ধতি হলো- ‘'N কি A দিয়ে ভাগ যায়?” আমরা এটা চেষ্টা করি, আমরা এখানে A কে নিচে নামাই এবং আমরা N কে A দিয়ে ভাগ করতে চেষ্টা করছি এবং আমরা যদি অবশিষ্ট শূন্য পাই, যার অর্থ A হল N এর বিভাজক, আমরা বলি “ওহ, আমরা ১০০ পারসেন্ট জানি” আমরা পতাকা উঠাই এবং ১০০ ভাগ নিশ্চিত জানি এটা যৌগিক। অন্যথায়, প্রতি ধাপে, আমরা খুব নিশ্চিত নয়। এটা মৌলিক হতে পারে কিন্তু আমরা নিশ্চিত নয়। আমরা শেষ পর্যন্ত খোঁজাখুঁজি চালিয়ে যাবো। মনে রেখো, এক্ষেত্রে আমাদের বাধা হলো N এর বর্গমূল। সবচেয়ে খারাপ অবস্থা ঘটে যখন N মৌলিক থাকে, আমরা সব পদ্ধতিতে N এর বর্গমূল খুঁজি এবং এরপর আমরা “ওহ, এটা মৌলিক সংখ্যা এবং আমরা ১০০ ভাগ নিশ্চিত” বলতে পারি। এই ক্ষেত্রে যেখানে N দুটি মৌলিক সংখ্যার গুণ হয়, সাত গুণ সাত সমান ৪৯ যদি আমরা আমাদের এলগরিদমে ৪৯ দেই, সবচেয়ে খারাপ ঘটনা হবে। আমরা সব পদ্ধতিতে N এর বর্গমূল করি। প্রথম প্রশ্নের সেট, উদাহরণস্বরূপ দ্যা ফোর্থ ডাইমেনশন এর প্রশ্ন- “দুই বিভাজ্য নয় বলে আমরা যদি একে বাদ দেই, এরপর দুইয়ের সকল গুণিতক বাদ দিতে পারি। একই ভাবে তিন, চার, পাঁচ ইত্যাদি।" এটা সত্যিই গুরুত্বপূর্ণ বিষয়। আমাদের পুরাতন এলগরিদম একবারে এক ধাপ করে পরিবর্তন হতো। যৌগিক সংখ্যা সম্পর্কে জানতে আমাদের প্যাটার্ন ব্যবহার করতে হতে পারে, যেমন আমরা নিশ্চিত জানি, যদি একটা সংখ্যা দুই দ্বারা বিভাজ্য হয় তাহলে সেটা যৌগিক সংখ্যা। যদি এটা দুই থেকে বড় হয়, তাহলে দুই মৌলিক সংখ্যা। তাহলে আমরা বলতে পারি চার যৌগিক সংখ্যা। আমি এখানে ভুল করে পাঁচ লিখিনি, সেজন্য দুঃখিত। চার, ছয়, আট, দশ, এবং এর পরিবর্তে আমরা এইভাবে ধাপ লিখতে পারি। তিন, পাঁচ, সাত, নয়। এক ধরনের প্রশ্নে সবাই এই স্থান হ্রাস করার চেষ্টা করছে। যদি আমরা সব জোড় সংখ্যা বাদ দেই, এখন পরীক্ষা, N এর বর্গমূল এর পরিবর্তে N এর বর্গমূল ভাগ দুই হয়। আমরা এটাকে আরো ছোট করার চেষ্টায় যৌগিক সংখ্যার অন্য প্যাটার্ন খুঁজতে পারি। এখানে অন্য ধরনের প্রশ্ন যা বিবেচিত হচ্ছে তা হলো আমরা যৌগিক সাক্ষী কোথায় পাবো। সেটা হল, আমরা A পাই যার ফলে বলতে পারি “ওহ, আমরা জানি N যৌগিক”। লোলা জিজ্ঞেস করেছিল “যখনই মৌলিক যাচাই সমান মিথ্যা হবে "তখন কোন এক সময়ে "লুপ ছাড়া হবে না?" হ্যাঁ, এটা সম্পূর্ণ সঠিক এবং আমরা এমন কিছুই করতে চাই। আমরা যতক্ষন পর্যন্ত কোন ধাপ ব্যবহার করে খুঁজছি, যে প্যাটার্নই আমরা ব্যবহার করি না কেন, আমরা একটি যৌগিক সংখ্যার সাক্ষী পাই। এর মানে এটা আমাদের পরীক্ষায় উত্তীর্ণ হয়েছে এবং আমরা ১০০ ভাগ বিশ্বাসের সাথে বলছি আমাদের তাড়াতাড়ি থামা উচিত। আমরা বন্ধ করে বলি, “ওহ, আমরা শেষ করেছি। আমাদের খোঁজা চালিয়ে যেতে হবে না।” এই তাড়াতাড়ি থামা ভালো, এটি আমাদের খারাপ ঘটনায় সাহায্য করা ছাড়া যদি N মৌলিক সংখ্যা হয় তবে এই তাড়াতাড়ি থামা আমাদের কোন কাজে আসবে না। এখন, আমরা দেখতে পারি যে, কম্পিউটারের উপর নির্ভর করে কম্পিউটারের ভিতরে ঘটে যাওয়া সমসংখ্যক যাচাই প্রতিরোধ করে, কিভাবে এই অগ্রগতি কম সময় নেয়ার মাধ্যমে স্থান কমানোতে আমাদের সাহায্য করছে। এখন আমি তোমাকে নিচের স্থাপিত চিত্রটি দেখাতে পারি যা দুটি এলগরিদম এর সম্পাদন হবার বিভিন্ন ধাপের মধ্যে আমাদের তুলনা করতে দেয়। বাম পাশে এলগরিদম A, যা পরীক্ষামূলক বণ্টন পদ্ধতি যা দুই থেকে N এর বর্গমূলকে যাচাই করে। ডান পাশে এলগরিদম B, যা মনে করি আমাদের উন্নত এলগরিদম। এক্ষেত্রে, এটা দুই দ্বারা ভাগ হয় কিনা তা আমি পরীক্ষা করেছি তাহলে আমাদের শুধু যত ধাপ লাগবে তার অর্ধেক করি। আমি এই এলগরিদম B দ্রুত শেষ করছি। এটা নির্ভুল নয়, আমি শুধু কিছু ব্যবহার পরিবর্তনে প্রয়োগ করেছি যেন আমরা দেখতে পাই কী ঘটছে। এখন, আমি এটা তোমাদের দেখাতে চালু করতে যাচ্ছি। এখানে আমরা দেখতে পাচ্ছি, যখন আমি স্ক্রল করছি, আমরা এলগরিদম A দেখছি। আমাদের ফলাফল আছে, সেটা যৌগিক বা মৌলিক যাই হোক। নিচে তুমি ধাপ এর সংখ্যা দেখতে পাবে। প্রথমে লক্ষ্য কর ডান পাশে প্রত্যেক সংখ্যা শুধু একটি ধাপ নেয়। আমরা জানি সেটা কেন হচ্ছে। যদি এটা একটি জোড় সংখ্যা হয় যেমন এটা, এটা বাদ যাবে। আমাদের পুরনো এলগরিদম ৩১৪ ধাপ নেয়। আমাদের নতুন এলগরিদম শুধু একটি ধাপ নেয় কারণ এটা শুধু দুই দ্বারা বিভাজ্য কিনা যাচাই করে। এটা দেখে মনে হচ্ছে এটা সত্যিই চমৎকার একটি অপ্টিমাইজেশান। যাই হোক, আমরা যখন আমাদের ইনপুট তৈরি করি, তখন তুমি লক্ষ্য কর যে ধাপ বৃদ্ধি পাচ্ছে এবং বার বৃদ্ধি পাচ্ছে এবং লাল রঙে পরিবর্তন হচ্ছে। আমরা একবারে সীমায় পৌঁছায়ই যেখানে আমরা ক্রাশ করছি। লাল রেখা এখানে শেষ সীমা। যদি তোমার বার এখানে হিট করে, আমরা ব্যর্থ হবো, যার মানে আমাদের রোভার ভেঙ্গে যাবে। এক্ষেত্রে, ব্রাউজার আসলে ক্রাশ করবে। আমি তা বন্ধ করার চেষ্টা করবো। আমি এটার খুব কাছে আছি এবং এটা খুব ধীর গতিতে চলছে। আমি অনুভব করতে পারছি যে আমার ব্রাউজার ক্রাশ করার সন্নিকটে এবং আমাকে মুক্তি দাও। লক্ষ্য কর যে উন্নত এলগরিদম মাত্র দুটো ধাপ নেয় এক্ষেত্রে, কিন্তু খারাপ বিষয়টি মনে রেখ। আমি করতে যাচ্ছি-- উদাহরণের জন্য আমার এখানে কিছু বড় মৌলিক সংখ্যা আছে। আমাদের যেকোন পরিস্থিতি সামাল দেয়ার মত সক্ষম হতে হবে। আমরা জানি না আমাদের এলগরিদমে কী দিতে যাচ্ছি। যদি আমি একটি বড় মৌলিক সংখ্যা এটাতে দেই, দেখ কী ঘটে। এলগরিদম B, যেমন আমরা জানি, খারাপ ক্ষেত্রে এটা যত ধাপ লাগে তার অর্ধেক নেয় কিন্তু এটা এখানে এখনও অনেক ধাপ নেয় কারণ এটা খারাপ ক্ষেত্র, ঠিক আছে। আমরা এখানে ক্রাশ হওয়ার কাছাকাছি, এবং এটা খুব দীর্ঘ মৌলিক সংখ্যা নয়। আমরা এখনও ১৫ ডিজিটের নিচে আছি। যখন আমরা আমাদের এলগরিদমে এই ১২ ডিজিটের মৌলিক সংখ্যা রাখি চল দেখি কী ঘটে। এটা ধীরে চলছে, এটা প্রায় ক্রাশ হতে যাচ্ছে। দেখ কী ঘটছে, উভয় এলগরিদম বাদ হয়ে যাচ্ছে। এটা কাজ করবে না। আমাদের উন্নত এলগরিদম এখনও যথেষ্ট ভালো নয়। কিন্তু এখন আমাদের ধারণা আছে আমরা কী উন্নত করতে চাচ্ছি যা হলো খারাপ ক্ষেত্রের ধাপ সংখ্যা। আমাদের এই কার্যকরী যন্ত্র আছে যা আমাদের যন্ত্রের দ্রুত বৃদ্ধি দেখার অনুমোদন দেয়, যার মাধ্যমে আমাদের ইনপুট বৃদ্ধির সাথে সাথে কত দ্রুত ধাপ সংখ্যা বৃদ্ধি পায় তা আমরা দেখতে পাই। নিচে, আমি ব্যাখ্যা করবো কীভাবে আমি এটা স্থাপন করেছি যাতে তুমি তোমার এলগরিদম স্থাপন করতে পারো এবং ভিত্তি এর ক্ষেত্রে এটা তুলনা করতে পারো এবং দেখতে পারো যে তুমি কত ভালো করতে পারো। ## আগামী ও গ্রামীণফোন এর সহযোগিতায় অনূদিত ##