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

თუ ვებფილტრს იყენებთ, დარწმუნდით, რომ *.kastatic.org და *.kasandbox.org დომენები არ არის დაბლოკილი.

ძირითადი მასალა
მიმდინარე დრო:0:00მთლიანი ხანგრძლივობა:5:06

ვიდეოს აღწერა

თავდაპირველად, მოდი, ავაწყოთ კონცეპტუალური მექანიკა ახალი ტიპის შემთხვევითობის ალგორითმებისთვის, რომელშიც შევიყვანთ რაიმე N-ს. თუ N მარტივია, ალგორითმი გვეტყვის ამას 100% სისწორით. იგი არასოდეს აღიქვამს მარტივ რიცხვს შედგენილად. თუმცა, თუ N შედგენილია, არსებობს ძალიან მცრიე შანსი შეცდომის e, რომ რიცხვი მარიტვად აღიქვან. შესაბამისად, 1-e არის ალბათობა იმის, რომ იგი სწორად იყოს აღქმული შედგენილ რიცხვად. დავიწყოთ მარტივად. მთელ რიცხვთა სიმრავლედან, ჩვენ ვიღებთ რიცხვს და ვარქმევთ N-ს. ჩვენ შეგვყავს N ჩვენს მანქანაში. წინა ვიდეოებში, გაყოფის ცდის მეთოდში, ჩვენ განვიხილავდით ყველა მნიშვნელობას 1-დან N-ის კვადრატულ ფესვამდე და ვამოწმებდით იყოფა თუ არა N-ზე. იდეურად, ჩვენ გვჭირდებოდა მხოლოდ მარტივი რიცხვების შემოწმება დროის დასაზოგად. და თუ N იყოფა a-ზე, ვიცით რომ N შედგენილი რიცხვია, რადგანაც ვიპოვეთ მისი შემადგენელი ნაწილი. თუ არა, მაშინ არ ვართ დაარწმუნებულები. ჩვენ ვბრუნდებით, ვიღებთ რაიმე სხვა a-ს და ახლიდან ვამოწმებთ. როდესაც, შევამოწმებთ ყველა შესაძლო ვარიანტს შეგვიძლი ვთქვათ რომ N მარტივია, თუ ვერ ვიპოვეთ გამყოფები. მოდი, ვიზარმაცოთ. თუ ჩვენ ავიღებთ რამდენიმე შემთხვევთ მთელ რიცხვს და მხოლოდ რამდენჯერმე შევამოწმებთ გაყოფაზე, რომლებიც შეგიძლიათ შემთხვევით კითხვებად განიხილოთ. ჩვენ ვიცით რომ N თუ შედგენილია მას უნდა ჰქონდეს რამდენიმე გამყოფი. როგორც მინიმუმ 1. ზოგიერთ შედგენილ რიცხვს, ბევრი გამყოფი ყავს. ნებისმიერ შემთხვევაში, ჩვენ ვიღებთ შემთხვევით მთელ რიცხვ a-ს 1-სა და N-ის კვადრატულ ფესვს შორის. შემდეგ უბრალოდ ვამოწმებთ იყოფა თუ არა N a-ზე. როგორც წინაზე, თუ N იყოფა a-ზე ზუსტად ვიცით, რომ N შედგენილია, ჩვენ ვიპოვეთ გამყოფი. თუ არა, ჯერ არ გაგვირკვევია მარტივია თუა რა. შეგვიძლია კიდევ, რამდენიმე a-ს დაგენერირება და შემოწმების გაგრძელება. შესაძლოა 100 ან 1000 ცდის მერე შევჩერდეთ და ვთქვათ "შესაძლოა მარტივია", რაღაც დარწმუნებით. ვთქვათ, 99.9%-ით. ეს მსგავსია პირობითი ალბათობის სამაგალითო თამაშის. უმარტივეს ვერსიაში, ჩვენ ვცდილობდით გამოგვეცნო მონეტა სამართლიანი იყო თუ არა. ამ შემთხვევაში საფასური გამყოფის პოვნის მსგავსია. მტკიცებაა სამართლიანი მონეტის. გერბი კი ის ვარიანტია, როცა გვინდა, რომ ახლიდან ავაგდოთ და ისევ შევამოწმოთ. ამ შემთხვევაში 5 გერბის შემდეგ 90%-ზე მეტად დარწმუნებულები ვართ რომ შევჩერდეთ და ვთქვათ "ამ მონეტას ორივე მხარე ერთნაირი აქვს." ეს არის პროგრამა, რომელიც გავაკეთე. ის ადარებს ძველ გამყოფის პოვნის მეთოდს ახალ შემთხვევითი გამყოფის ტესტთან. ახლა ვიყენებ გაყოფის ცდის სიჩქარის ლიდერს, რომელიც Dyno-ს პროგრამაა. ბმული დავპოსტე პროგრამის სათაურში. დასაწყისში, შენიშნეთ ცვლადი რიცხვის ცდა. ეს არის შემთხვევითი გამოცნობების რაოდენობა. დავიწყოთ ისეთი მცირე რიცხვით, როგორიც არის 3. შენიშნეთ, მცირე რიცხვის შეყვანითაც, თუ ის მარტივია, მარტივი გაყოფადობის ალგორითმი ყოველთვის გვიპასუხებს მარტივს. თუ შეყვანილი რიცხვი შედგენილია, ვხედავთ, რომ შემთხვევითმა გაყოფამ შეიძლება შეცდომა დაუშვას, და აღიქვას მარტივად. თუმცა, ამის გამოსწორება ცდების რაოდენობის გაზრდით შეგვიძლია. ამ შემთხვევაში შეცდომის ალბათობა დაბლა იწევს. ახლა ვხედავთ, რომ პასუხი მეტ-ნაკლებად ემთხვევა. თყ შევიყვან უფრო დიდ რიცხვს შეცდომა ისევ იზრდება. შემთხვევითი ცდების რაოდენობაც შესაბამისად უნდა გავზარდო. როდესაც ამას ვაკეთებ, პასუხი უფრო ემთხვევა. ისინი იდენტურები ჩანან. უზარმაზარი რიცხვის შეყვანის შემთხვევაში, ათასობით ცდა დამჭირდება რომ დარწმუნებული ვიყო. რეალურად არ გაგვიუმჯობესებია ნაბიჯების რაოდენობა. ჩვენი გაყოფის მეთოდი უკეთესი ჩანს. იმიტომ რომ შეცდომის ალბათობა უფრო დიდია, მაგრამ უფრო ახლოს ვართ. ჩვენი იდეა სწორია. ჩვენ გვჭირდება სხვა ტესტის ცდა. გვჭირდება ტოლობა, რომელიც საკმარისად სწრაფია გამოსათვლელად. ეს შეგვიძლია გამოვიყენოთ იმის დასამტკიცებლად რიცხვი შედგენილია თუ არა. მან არა მხოლოდ უნდა მიიღოს შეყვანილი მთელი რიცხვი N, ასევე უნდა მიიღოს შემთხვევითი მთელი რიცხვი a და ჩაატაროს შემთხვევითობის ტესტი იმავე გზით.