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

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

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

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

ინფორმაციის განახლება მაქვს. NASA-, განაცხადა, რომ Rover-ს, რომელზეც ჩვენ წვდომა გვაქვს, ექნება პროგრამული რენდომული რიცხვების გენერატორი. ამის შემდეგ მათ კიდევ ერთი კომენტარი გააკეთეს. მათ შემახსენეს, რომ უბრალოდ საჭიროა, ჩვენი ალგორითმი პრაქტიკაში მუშაობდეს. ის, რომ რაღაც პრაქტიკაში მუშაობს, ნიშნავს, რომ ყოველთვის არსებობს შეცდომის ალბათობა, მაგრამ ეს ალბათობა იმდენად პატარაა, რომ პრაქტიკაში შეიძლება მხედველობაში არ მივიღოთ, თუ გგონია, რომ ეს სიგიჟეა, უბრალოდ, დაფიქრდი, რომ ფიზიკურ სამყაროში არაფერია სრულიად ზუსტი, ყოველთვის არსებობს შეცდომის ალბათობა. მაგალითად, ჩიპის შეფუთვა, ყოველთვის შეიცავს მცირე ოდენობით რადიოაქტიურ ელემენტებს, და როცა ისინი იშლება, თავისუფლდება ალფა ნაწილაკები, რომლებმაც შეიძლება ამოაბრუნონ მეხსიერების ბიტები და მოულოდნელად შეცვალონ რიცხვი. უფრო საინტერესოა, რომ კოსმოსურმა სხივებმა შეიძლება გამოიწვიოს პროგრამული შეცდომები, შეცდომების შანსის სრულიად გამორიცხვა არ შეგვიძლია. NASA-ს ვკითხე, შეცდომის კონკრეტულად რა ალბათობაა მისაღები. მათ მითხრეს: 'ჩვენ, უბრალოდ, უნდა დავრწმუნდეთ, რომ შეცდომის ალბათობა მოცემული ცდისთვის ნაკლებია, ვიდრე ლატარეაში ორჯერ ზედიზედ გამარჯვების შანსი.' შანსი იმისა, რომ ლატარეაში, ვთვაქთ, '6/49'-ში, გაიმარჯვებ ორჯერ ზედიზედ, არის ექვსი გამრავლებული ათი ხარისხად მინუს 14. მოდით, უსაფრთხოების მიზნით, დავამრგვალოთ და ვთქვათ, რომ ჩვენი შეცდომის ალბათობაა ათი ხარისხად მინუს 15. საკმაოდ უსაფრთხოა. შეცდომის დადგომას არ ველით და შეიძლება გამეორდეს ასობით და ათასობით შემთხვევაში უშეცდომოდ. ჩემი შეკითხვაა, შემთხვევით შერჩევამდე წვდომა დაგვეხმარება, ავაჩქაროთ გადაწყვეტილების ალგორითმი, ისეთ, როგორიცაა ტესტი მარტივობაზე? ეს ღრმა შეკითხვაა და მოდით, უკან დავიხიოთ და სრულ სურათს შევხედოთ. მოცემული გვაქვს 1-დან კონკრეტულ N-მდე მთელი რიცხვების სიმრავლე, ეს იყოს ჩვენი მთელი რიცხვების სამყარო. ყოველთვის შეგვიძლია, ეს სიმრავლე ორ ნაწილად გავყოთ. რეალურად, გადაწყვეტილების პრობლემა შეიძლება განვიხილოთ, როგორც ორ ნაწილად გაყოფის პრობლემა. მაგალითად, თუ გვაქვს, რომ რაღაც N არის N ნაკლები 100-ზე, ის მოგვცემს 'კის' ყველა ინტეგრალისთვის, რომელიც ნაკლებია N-ზე, ანუ, ეს არის ერთი სიმრავლე, და 'არას' ყველა დანარჩენი რიცხვისთვის, რაც სხვა სიმრავლეა. ახლა კი შევჩერდეთ მარტივი რიცხვების ამოცნობის პრობლემაზე. იდეალურ შემთვევაში, გვენდომბებოდა მარტივად გამოსათვლელი კრიტერიუმი რომელსაც აკმაყოფილებს ყველა მარტივი რიცხვი და არც ერთი შედგენილი რიცხვი. თუ გვეცოდინებოდა რაიმე მარტივი შაბლონი, რომელიც აღწერს ყველა მარტივი რიცხვის, და მხოლოდ მათ, მდებარეობას, მაშინ, ნებისმიერი N-ის შემთხვევში შევძლებდით, შეგვემოწმებინა, რამდენად ჯდება ის შაბლონში. პრობლემა ისაა, რომ ჯერჯერობით არ არის ნაპოვნი მარტივი და სრული შაბლონი რომელიც მოერგება ყველა მარტივ რიცხვს და არც ერთ შედგენილ რიცხვს, ან პირიქით, მოერგება ყველა შედგენილ რიცხვს და არცერთ მარტივს. მაგრამ ჩვენ ვიცით სწრაფი ტესტები უმეტესობა შედგენილი რიცხვებისთვის. მაგალითად, მარტივი კრიტერიუმია ტექსტი ლუწობაზე, ყველა ლუწი რიცხვი იყოფა ორზე. ის სწრაფია, რადგან შეგვიძლია ვთქვათ, რიცხვი ლუწია თუ არა მხოლოდ მისი ბოლო ციფრის მიხედვით, და მაშინაც კი, როცა N იზრდება, პრობლემა არ რთულდება, რადგან ისევ ბოლო ციფრით ვამოწმებთ. ამას ჰქვია დაბალი რიგის ბიტი. ლუწობის ტესტი შეგვიძლია გამოვიყენოთ, როგორც დაბალი ხარისხის ტესტი შედგენილობის განსასაზღვრად. შეგვიძlია გვქონდეს რაღაც ალგორითმი, რომელიც შეამოწმებს, არის თუ არა რიცხვი ლუწი. თუ რიცხვი ლუწია და ორზე მეტი, მაშინ 100-პროცენტიანი დარწმუნებით ვიცით, რომ ის შედგენილია, რადგან ამის საბუთი გვაქვს. ორი არის ჩვენი შედგენილობის საბუთი. თუმცა, თუ რიცხვი ორზე არ იყოფა, ვეღარ ვიქნებით დარწმუნდებული. თუ ის კენტია, შეიძლება იყოს მარტივი, რადგან ყველა მარტივი რიცხვი კენტია, ან ის შეიძება იყოს ერთ-ერთი უამრავ კენტ შედგენილ რიცხვთაგან. მაგალითად, როგორიცაა ცხრა ან თხუთმეტი. კენტი შედგენილი რიცხვების დიდი ოდენობა ამ ტესტს ხდის მიუღებელს. უკეთ რომ გავიგოთ, მოდით, დავხატავ. გვაქვს რაღაც N, N შეიძლება იყოს მარტივი ან შედგენილი. თუ N მარტივია, ჩვენი ალგორითმი იტყვის მარტივს ყოველ ჯერზე რადგან არც ერთი მარტივი რიცხვი არ არის ლუწი და მეტი ორზე. ის არასდროს იტყვის კომპოზიტს, როცა მოცმულია მარტივი რიცხვი. თუმცა, თუ N შედგენილია, ჩვენი ალგორითმი იტყვის 'შედგენილს' დაახლოებით ნახევარ შემთხვევაში, და მარტივს დანარჩენ შემთხვევებში. ეს ნიშნავს, რომ თუ ჩვენი ალგორითმი ამოიცნობს შედგენილ რიცხვს, მაშინ მან იპოვა შედგენილობისთვის აუცილებელი დასაბუთება. თუმცა, თუ ჩვენი ალგორითმი მოგვცემს მარტივ რიცხვს, ვიცით, რომ შეცდომის მიუღებლად დიდი შანსი არსებობს. აქამდე ჩვენი სტრატეგია უმკლავდებოდა მიუღებლად დიდ შეცდომას გამეორების მეთდით. მოდით, დავხატოთ ჩვენი მექანიზმი. როცა მას მიცვემთ N-ს, მანქანა ატარებს რამდენიმე ტესტს გაყოფაზე, იწყებს A=2-დან. ის ეკითხება N-ს, იყოფა თუ არა A-ზე. თუ არ იყოფა, მაშინ შეგვიძლია გამოვრიცხოთ რიცხვების ნაწილი. შემდეგ მანქანა სვამს კითხვას: იყოფა თუ არა N 3-ზე? თუ N არ იყოფა 3-ზე, ვაკლებთ ამ სეცქიას. იყოფა თუ არა N ხუთზე, შვიდზე, და ასე შემდეგ. დააკვირდით, ეს არის ქვესიმრავლეები, რომელბიც არ იკვეთება და ნელ-ნელა მოიცავს ყველა შესაძლო შედგენილ რიცხვს. თუ ამ კითხვებიდან რომელიმეს ვუპასუხეთ 'კი', მაშინ გვაქვს საბუთი, რომ N შედგენილია. A, რაც არ უნდა იყოს იმ მომენტში, არის ჩვენი საბუთი. ჩვენი N რიცხვიანი ალგორითმი გვაძლევს შედგენილ რიცხვს, სხვაგვარად, ვაგრძელებთ ცდას, ვიდრე ყველა შესაძლო კომპოზიტს ამოვწურავთ. ვიდრე მივალთ A უდრის კვადრატული ფესვი N-დან. ყველა შედგენილ რიცხვ N-ს უნდა ჰქონდეს ფაქტორი, რომელიც იქნება ნაკლები ან ტოლი N-დან კვადრატულ ფესვზე . ეს არის ჩვენი ალგორითმის საბოლოო შეკითხვა. თუ ვერანაირი საბუთი ვერ ვიპოვეთ და A მეტია, ვიდრე კვადრატული ფესვი N-დან, ჩვენ უეცრად გვაქვს მტკიცებულება და ვიღებთ მარტივ რიცხვს. დაუკვირდი, ალგორითმში ორი გამოსასვლელი გზა გვაქვს. ორივე გამოსასვლელი არის მტიკცებულება, რომ N არის შედგენილი ან მარტივი. როცა N მარტივია, ცვდით ყველა შესაძლო გამყოფს და გამოვრიცხავთ მათ, და ეს არის ჩვენი საბუთი იმისა, რომ N არის მარტივი რიცხვი. ამ სტრატეგიას ის პრობლემა აქვს, რომ ჩვენი A გვაიძულებს, ყოველ ჯერზე თავიდან გავიაროთ მარტივი რიცხვები დაწყებული ორიდან და დამთავრებული N-დან კვადრატული ფესვით. რაც უფრო იზდრება N, მარტივი რიცხვების რაოდენობაც იზრდება, რაც გვაძევს შედეგად ძალიან ბევრ გამეორებას. ეს უარეს შემთხვევაში, ანუ თუ ალგორითმი ამოწმებს მარტივ რიცხვს. თუ დიდ სურათს შევხედავთ, ალორითმი გვაძლევს მტკიცცებულებას, რომ N მარტივია, რაც ჩვენ არ გვჭირდება. არავის უთქვამს, რომ ჩვენ გვჭირდება მტკიცებულება. ჩვენ, უბრალოდ, გვინდა, 99.9999 პროცენტით ვიყოთ დარწმუნებულები. ანუ, უნდა დავფიქრდეთ შედგენილი რიცხვების იმ ტესტზე, რასაც ჩვენი ალგორითმი იყენებს. გაიხსენეთ, აქამდე მარტივი რიცხვების გამოსავლენი ყველაზე სწრაფი ტესტი იყენებდა 6K შაბლონს. ყველა მარტივი რიცხვი არის 6K-ს პლიუს ან მინუს ერთი ფორმის, რათა ალგორითმმა მხოლოდ მარტივ რიცხვებში იტრიალოს და ერთბაშად გამოაკლოს შედგენილი რიცხვების უმეტესობა, დროის დასაზოგად. ასეთ ტესტი შეიძლება გადაკეთდეს შედგენილობის შესამოწმებელ ტესტად. თუ მოცემულია, რომ მთელი რიცხვი N არის 6K-ს პლიუს ან მინუს ერთის ფორმის, შეგვიძლია ვთქვათ, რომ ის სავარაუდოდ არის მარტივი, მაგრამ ჯერ კიდევ დარჩენილია ბევრი შედგენილი რიცხვი რომელიც იმავე შაბლონში ჯდება. ეს ფორმა არ მოიცავს მხოლოდ მარტივ რიცხვებს, არამედ ყველა მარტივ რიცხვს და ზოგიერთ შედგენილს. დარჩენილი შედგენილი რიცხვების ცდომილება შეგვიძლია მოვიაზროთ, როგორც გაჯონვა და ეს გაჟონვა არის ჩვენი შეცდომის წყარო. ახლა კი, თუ შევაბრუნებთ და კვითხავთ, N არ არის 6K-ს პლიუს ან მინუს ერთის ფორმით მაშინ შეგვიძია ვთქვათ 100 პროცენტი უტყუარობით, რომ ეს შედგენილი რიცხვია. ანუ ეს ხვრელი არის შეცდომის წყარო მარტივი რიცხვებისთვის, მაგრამ, ამ შემთხვევაში, ეს არ არის ისეთი შეცდომის ალბათობა, რომელიც მისაღებია. ამ შემთხვევაში ალბათობა გაცილებით მეტია. უნდა ვიპოვოთ ისეთი ტექსტი, პროცედურა, რომელიც შეძლებს, მაქსიმალურად შეამჭიდროვოს ეს სივრცე და შეცდომის ალბათობა უმნიშვნელომდე დაიყვანოს. ეს ნიშნავს, რომ უნდა განვიხილოთ, როგორ შეიძლება ამ შეცდომების უმნიშვნელომდე დაყვანა. ვფიქრობ, კარგი იქნება, თუ თქვენს იდეებს დაწერთ იმის შესახებ, თუ როგორი ტესტი შეიძლება ჩავატაროთ და, რაც უფრო მნიშვნელოვანია, როგორ შეიძლება დაგვეხმაროს რენდომული რიცხვების გენერატორი.