ძირითადი მასალა

კომპიუტერული პროგრამირება

კურსი: კომპიუტერული პროგრამირება > თემა 5

გაკვეთილი 2: შემთხვევითობა

შემთხვევითი რიცხვების არჩეული გადანაწილება

თქვენს ცხოვრებაში დადგება დრო, როცა არ გენდომებთ შემთხვევითი მნიშვნელობების თანაბარი განაწილება, ან გაუსის განაწილება. წარმოიდგინეთ, რომ ხართ შემთხვევითი მოხეტიალე, რომელიც საკვებს ეძებს. სივრცეში შემთხვევითად ხეტიალი საკვების საპოვნელად ჭკვიანურ სტრატეგიას ჰგავს. ყველაფერს რომ თავი დავანებოთ, თქვენ არ იცით, სად არის საკვები, ამიტომ შემთხვევით ადგილებში ეძებთ მას, სანამ იპოვით. ალბათ უკვე შეამჩნევდით, რომ შემთხვევითად მოხეტიალეების პრობლემა არის ის, რომ ისინი ხშირად უბრუნდებიან უკვე მონახულებულ ადგილს (ამას ჰქვია „ზედმეტი შერჩევა", ინგლ. „oversampling"). ამის თავიდან აცილების ერთ-ერთი სტრატეგიაა შიგადაშიგ ძალიან დიდი ნაბიჯის გადადგმა. ამით მოხეტიალე გარკვეული დროის განმავლობაში შემთხვევითად დადის კონკრეტულ მიდამოში და პერიოდულად გადახტება ძალიან შორს, რათა შეამციროს ზედმეტ შერჩევათა რაოდენობა. შემთხვევითი ხეტიალის ამ ვარიანტს (რომელიც ცნობილია, როგორც „ლევის ფრენა", ინგლ. Lévy flight) ესაჭიროება ალბათობათა მორგებული სიმრავლე. მიუხედავად იმისა, რომ ეს არ არის ლევის ფრენის ზუსტი იმპლემენტაცია, შეგვიძლია, ალბათობის განაწილება შემდეგნაირად ჩამოვაყალიბოთ: რაც უფრო გრძელია ნაბიჯი, მით უფრო ნაკლებ სავარაუდოა, რომ ის აირჩევა; რაც უფრო მოკლეა, - მით უფრო მეტად სავარაუდოა.

ამ სექციაში ვნახეთ, რომ პერსონალიზირებული შემთხვევითი განაწილებების შექმნა შეგვეძლო მასივის მნიშვნელობებით შევსებით (ზოგიერთ მნიშვნელობას ორჯერ ვსვამდით, რათა უფრო ხშირად შერჩეულიყვნენ) ან random()-ის შედეგის დატესტვით. შეგვეძლო ლევის ფრენის იმპლემენტაცია იმის თქმით, რომ მოხეტიალე დიდ ნაბიჯს 1%-იანი ალბათობით დგამს.

var r = random(1);
// დიდი ნაბიჯის გადადგმის 1%-იანი შანსი
if (r < 0{,}01) {
  xstep = random(-100, 100);
  ystep = random(-100, 100);
} else {
  xstep = random(-1, 1);
  ystep = random(-1, 1);
}

მიუხედავად ამისა, ეს ალბათობების მხოლოდ ფიქსირებული რაოდენობით არჩევის საშუალებას გვიტოვებს. რას ვიზამთ იმ შემთხვევაში, თუ უფრო ზოგადი წესით გვინდა ალბათობების არჩევა — რაც უფრო დიდია რიცხვი, არჩევის მით უფრო მეტი შანსი ჰქონდეს? 3,145-ის მოსვლის შანსი უფრო მეტი იქნებოდა, ვიდრე 3,144-ის, მიუხედავად იმისა, რომ ეს ალბათობა სულ ოდნავ მეტია. სხვა სიტყვებით, თუ x შემთხვევითი რიცხვია, შეგვიძლია, ალბათობა y ღერძზე აღვბეჭდოთ y = x-ით.

თუ გავარკვევთ, როგორ უნდა შევქმნათ შემთხვევითი რიცხვების განაწილება ზედა გრაფიკის მიხედვით, მაშინ იგივე მეთოდის გამოყენება შეგვეძლება ნებისმიერი მრუდისთვის, რომლის ფორმულაც გვაქვს.

ერთ-ერთი ამოხსნაა ერთის ნაცვლად ორი შემთხვევითი რიცხვის აღება. პირველი შემთხვევითი რიცხვი მხოლოდ შემთხვევითი რიცხვია. მეორე რიცხვი კი არის ის, რასაც ჩვენ ვეძახით „შემრჩევ შემთხვევით მნიშვნელობას". ის შეგვატყობინებს, გამოვიყენოთ პირველი რიცხვი, თუ გადავაგდოთ ის და მის ნაცვლად ავიღოთ სხვა. რიცხვებს, რომელთაც შერჩევის მეტი შანსი აქვთ, უფრო ხშირად გამოვიყენებთ, ხოლო რიცხვებს, რომელთაც იშვიათად ვირჩევთ, იშვიათად გამოვიყენებთ. აი, ნაბიჯები (ჯერ-ჯერობით განვიხილოთ შემთხვევითი მნიშვნელობები მხოლოდ 0-სა და 1-ს შორის):

აირჩიეთ შემთხვევითი რიცხვი: R1
გამოთვალეთ ალბათობა P იმისა, რომ R1 უნდა შეირჩეს. ვცადოთ: P=R1.
აირჩიეთ სხვა შემთხვევითი რიცხვი: R2
თუ R2 ნაკლებია P-ზე, მაშინ ვიპოვეთ ჩვენი რიცხვი — R1!
თუ R2 არ არის ნაკლები P-ზე, გადადით პირველ ნაბიჯზე და დაიწყეთ ხელახლა.

აქ ვამბობთ, რომ შემთხვევითი მნიშვნელობის მოსვლის ალბათობა თვითონაც შემთხვევითი რიცხვის ტოლია. ვთქვათ, ავირჩიეთ 0,1 R1-ისთვის. ეს ნიშნავს, რომ R1-ს აქვს შერჩევის 10%-იანი შანსი. თუ R1-ისთვის ავირჩევთ 0,83, მაშინ მას შერჩევის 83%-იანი შანსი ექნება. რაც უფრო მეტია რიცხვი, მით უფრო მეტია იმის ალბათობა, რომ მას გამოვიყენებთ.

აი, ფუნქცია (მას სახელი დაარქვეს მონტე კარლოს მეთოდის მიხედვით, ამ უკანასკნელს კი სახელი მონტე კარლოს სამორინეს გამო ეწოდა), რომელიც ზედა ალგორითმის იმპლემენტაციას ახდენს, აბრუნებს შემთხვევით მნიშვნელობას 0-სა და 1-ს შორის. ეს პროგრამა იყენებს მნიშვენლობებს ელიფსებისთვის ზომების მისაცემად, მაგრამ ჩვენ შეგვიძლია, სხვა ბევრი რამისთვის გამოვიყენოთ ეს მნიშვნელობები.

ეს „ბუნებრივი სიმულაციების" კურსი ეფუძნება დანიელ შიფმენის წიგნს "კოდის ბუნებას", ის გამოყენებულია ლიცენზიით Creative Commons Attribution-NonCommercial 3,0 Unported License.

გსურთ, შეუერთდეთ დისკუსიას?

შესვლა

დავალაგოთ:

პოსტები ჯერ არ არის.

გესმით ინგლისური? დააწკაპუნეთ აქ და გაეცანით განხილვას ხანის აკადემიის ინგლისურენოვან გვერდზე.