Руснаците създадоха „първия в света“ биологичен генератор на случайни числа. Как действа? Сензор за произволни числа Какво показва параметърът на сензора за произволни числа?

Урок 15. Шансът е душата на играта

Вие вече сте научили костенурката на много. Но тя има и други, скрити възможности. Може ли костенурката да направи нещо сама, което да ви изненада?
Оказва се, че да! В списъка със сензори има костенурки сензор за случайни числа:

случаен

Често срещаме произволни числа: когато хвърляме зарове в детска игра, слушаме кукувицата на гадателка в гората или просто „познаваме произволно число“. Сензорът за случайни числа в LogoWorlds може да приеме стойността на всяко положително цяло число от 0 до лимита на стойността, определен като параметър.

Самото число, зададено като параметър на сензора за случайни числа, никога не се появява.

Например произволен сензор 20 може да бъде всяко цяло число от 0 до 19, включително 19, произволен сензор 1000 може да бъде всяко цяло число от 0 до 999, включително 999.
Може би се чудите къде е играта - само числа. Но не забравяйте, че в LogoWorlds можете да използвате числа, за да зададете формата на костенурката, дебелината на писалката, нейния размер, цвят и много други. Основното нещо е да изберете правилната граница на стойностите. Границите на изменение на основните параметри на костенурката са показани в таблицата.
Генераторът на случайни числа може да се използва като параметър на всяка команда, например напред, точнои т.н.

Задача 24.Използване на сензора за произволни числа
Организирайте една от игрите, предложени по-долу, като използвате сензора за произволни числа и стартирайте костенурката.
Игра 1: Цветен екран
1. Поставете костенурката в центъра на екрана.
2. Въведете команди в раницата и задайте режима Много пъти:

new_color случаен 140 боя изчакайте 10

Екип бояизпълнява същите действия като инструмента за запълване в графичния редактор.
3. Озвучете сюжета.
Игра 2: „Веселият художник“ 1. Променете игра №1, като начертаете линии на екрана в произволни области с непрекъснати граници:

2. Изпълнете инструкциите в раницата Turtle с произволни завои и движения:

дясно произволно 360
напред произволно 150

Въпроси за самоконтрол
1. Какво е генератор на произволни числа?
2. Какъв е параметърът на сензора за случайни числа?
3. Какво означава границата на стойността?
4. Излиза ли някога числото, посочено като параметър?

Софтуерът на почти всички компютри има вградена функция за генериране на последователност от псевдослучайни квазиравномерно разпределени числа. За статистическото моделиране обаче се поставят повишени изисквания към генерирането на произволни числа. Качеството на резултатите от такова моделиране пряко зависи от качеството на генератора на равномерно разпределени случайни числа, т.к. тези числа са и източници (първоначални данни) за получаване на др случайни променливис даден закон за разпределение.

За съжаление не съществуват идеални генератори и списъкът с техните известни свойства се допълва със списък с недостатъци. Това води до риск от използване на лош генератор в компютърен експеримент. Следователно, преди провеждането на компютърен експеримент, е необходимо или да се оцени качеството на функцията за генериране на произволни числа, вградена в компютъра, или да се избере подходящ алгоритъм за генериране на произволни числа.

За да бъде използван в изчислителната физика, генераторът трябва да има следните свойства:

Изчислителната ефективност е възможно най-краткото време за изчисление за следващия цикъл и количеството памет за работа на генератора.

Голяма L произволна последователност от числа. Този период трябва да включва поне набора от случайни числа, необходими за статистически експеримент. Освен това дори наближаването на края на L крие опасност, която може да доведе до неправилни резултати от статистически експеримент.

Критерият за достатъчна дължина на псевдослучайна последователност се избира от следните съображения. Методът Монте Карло се състои от повтарящи се изчисления на изходните параметри на симулирана система под въздействието на входни параметри, които се колебаят с дадени закони на разпределение. Основата за прилагане на метода е генерирането на случайни числа с униформаразпределение в интервала, от който се образуват случайни числа със зададени закони на разпределение. След това вероятността от симулираното събитие се изчислява като съотношението на броя на повторенията на моделните експерименти с успешен резултат към броя на общите повторения на експериментите при дадени начални условия (параметри) на модела.

За надеждно, в статистически смисъл, изчисляване на тази вероятност, броят на повторенията на експеримента може да бъде оценен по формулата:

Къде
- функция, обратна функциянормално разпределение, - увереност вероятност за грешка Вероятностни измервания.

Следователно, за да не излезе грешката извън доверителния интервал   с доверителна вероятност, например  =0,95 е необходимо броят на повторенията на експеримента да бъде не по-малък от:

(2.2)

Например, за 10% грешка (  =0,1), получаваме
, и за 3% грешка (  =0,03), вече получаваме
.

За други начални условия на модела трябва да се извърши нова серия от повторения на експерименти върху различна псевдослучайна последователност. Следователно или функцията за генериране на псевдослучайна последователност трябва да има параметър, който я променя (например R 0 ), или дължината му трябва да бъде поне:

Къде К - брой начални условия (точки от кривата, определени по метода Монте Карло), Н - брой повторения на моделния експеримент при дадени начални условия, Л - дължина на псевдослучайната последователност.

След това всяка серия от Н повторенията на всеки експеримент ще се извършват върху негов собствен сегмент от псевдослучайната последователност.

Възпроизводимост. 0 . Както беше посочено по-горе, желателно е да има параметър, който променя генерирането на псевдослучайни числа. Обикновено това е R 0 Затова е много важно промяната

не развали качеството (т.е. статистическите параметри) на генератора на случайни числа. Добри статистически свойства. Това е найважен показател

качество на генератора на случайни числа. Той обаче не може да бъде оценен по нито един критерий или тест, т.к Няма необходими и достатъчни критерии за случайността на крайна последователност от числа.

Може да се каже, че идеята за надеждността на псевдослучайните числа се създава в процеса на тяхното използване, внимателно проверявайки резултатите, когато е възможно.

19.09.2017 г., вторник, 13:18, московско време , Текст: Валерия Шмирова

Компанията Security Code, разработчикът на криптографския комплекс Continent, получи патент за биологичен сензор за случайни числа. Това е точно биологичен сензор, тъй като случайността се основава на реакцията на потребителя към показаното му изображение. Компанията уверява, че подобни технологии не са били патентовани досега в света.

Получаване на патент

Компанията Security Code получи патент за биологична сензорна технология за произволни числа. Според разработчиците при създаването на технологията е използван „нов подход за решаване на проблема с генерирането на произволни числа с помощта на компютър и човек“. Разработката вече се използва в редица продукти, включително Continent-AP, Secret Net Studio, Continent TLS и Jinn, както и в криптографската библиотека SCrypt.

Както обясниха представители на компанията за CNews, работата по сензора продължава вече три години. Състои се от научна, внедрителска и експериментална част. Трима души отговарят за научната част на компанията, целият екип от програмисти е участвал в разработката, а тестовете и експериментите са извършени от целия екип, който възлиза на няколкостотин души.

Технологични възможности

Новият сензор може да генерира произволни последователности на лични устройства - не са необходими допълнителни устройства или хардуерни добавки. Може да се използва при криптиране на данни и във всяка област, където са необходими произволни двоични последователности. Според разработчиците, това помага да се създават ключове за криптиране на мобилни устройства много по-бързо. Това свойство може да се използва за криптиране на данни или генериране електронен подпис.

Както е обяснено Алиса Коренева, системен анализатор на „Код за сигурност“, сензорът на компанията генерира произволни последователности въз основа на скоростта и точността на реакцията на ръката на потребителя към промените в изображението на екрана на компютъра или таблета. За въвеждане се използва мишка или сензорен екран. Изглежда така: кръговете се движат хаотично по екрана, някои от параметрите им се променят с времето. В някои моменти от време потребителят реагира на промените в изображението. Като се вземат предвид особеностите на двигателните му умения, това се отразява в произволната маса от битове.

Можете да генерирате произволни числови последователности въз основа на спонтанни човешки реакции

Извън криптографията сензорът може да се използва за генериране на произволни числа компютърни игриили да изберете победители в конкурса.

Научна новост

Както компанията обясни на CNews, много известни методи за конструиране на сензори за произволни числа се основават или на физически закони и явления, или на детерминистични алгоритми. Последователностите могат да бъдат генерирани с помощта на компютър - в този случай нестабилността на някои части на компютъра и несигурността на хардуерните смущения се приемат като основа за случайност.

Новото в технологията на кода за сигурност се крие във факта, че източникът на случайност е реакцията на човек към променящо се изображение, което се показва на дисплея на устройството. Ето защо името на изобретението съдържа думата „биологичен“. Компанията съобщава, че нито тя, нито Роспатент са намерили патентовани аналози на технологията в Русия или в света. Въпреки това, като цяло такива техники са известни: например, последователност може да бъде генерирана въз основа на потребителски действия като щраквания или движения на мишката или натискане на клавиши на клавиатурата.

Според Коренева екипът за разработка анализира различни начини за генериране на произволни последователности. Както се оказа, в много случаи няма разумни оценки на производителността на генерирането или на статистическите свойства на генерираните последователности, или и двете. Това се дължи на трудността да се оправдае вече изобретена технология. Security Code твърди, че неговото изследване е дало разумни оценки на скоростта на генериране, успяло е да обоснове добри вероятностни характеристики и статистически свойства и е оценило ентропията, допринесла от човешки действия.

Продукти, които използват технология

"Континент" е хардуерен и софтуерен комплекс, предназначен за криптиране на данни. Използва се в руския публичен сектор, например в Министерството на финансите. Състои се от защитна стена и инструменти за създаване на VPN. Създаден е от компанията NIP Informzashita, а сега се разработва от Security Code LLC.

По-конкретно, сървърът за достъп "Континент" и системата за криптографска защита на информацията "Континент-AP" са защитен модул отдалечен достъпизползвайки GOST алгоритми, а “Continent TLS VPN” е система за осигуряване на сигурен отдалечен достъп до уеб приложения, също използвайки GOST алгоритми за криптиране.

Secret Net Studio е цялостно решение за защита на работни станции и сървъри на данни, приложения, мрежа, операционна системаи периферна техника, която разработва и "Код за сигурност". Jinn-Client е предназначен за криптографска защита на информацията за създаване на електронен подпис и надеждна визуализация на документи, а Jinn-Server е софтуерно-хардуерен комплекс за изграждане на правно значими системи за управление на електронни документи.

Криптографска библиотека SCrypt, която също използва нов датчик, е разработен от “Код за сигурност” за по-удобно приложение на криптографски алгоритми в различни продукти. Това е единичен програмен код, проверениза грешки. Библиотеката поддържа криптографско хеширане, електронен подпис и алгоритми за криптиране.

Какво прави „Кодът за сигурност“?

"Код за сигурност" - Руска компания, която разработва софтуер и хардуер. Основана е през 2008 г. Обхватът на продукта е защита на информационните системи и привеждането им в съответствие с международните и индустриални стандарти, включително защита на поверителна информация, включително държавна тайна. "Код за сигурност" има девет лиценза Федерална службаза технически и експортен контрол (FSTEC) на Русия, Федералната служба за сигурност (FSB) на Русия и Министерството на отбраната.

Персоналът на компанията се състои от около 300 специалисти; продуктите се продават от 900 оторизирани партньори във всички региони на Русия и страните от ОНД. Клиентската база на Security Code включва около 32 хиляди държавни и търговски организации.

Обърнете внимание, че в идеалния случай кривата на плътността на разпределението на случайни числа би изглеждала, както е показано на фиг. 22.3. Тоест в идеалния случай всеки интервал съдържа еднакъв брой точки: Н аз = Н/к , Къде Н — общ бройточки, кброй интервали, аз= 1, , к .

Трябва да се помни, че генерирането на произволно произволно число се състои от два етапа:

• генериране на нормализирано произволно число (тоест, равномерно разпределено от 0 до 1);
• нормализирано преобразуване на случайни числа r азна произволни числа х аз, които се разпределят според (произволния) закон за разпределение, изискван от потребителя или в необходимия интервал.

Генераторите на произволни числа според метода за получаване на числа се разделят на:

• физически;
• табличен;
• алгоритмичен.

Физически RNG

Пример за физически RNG може да бъде: монета („глави“ 1, „опашки“ 0); зарове; барабан със стрелка, разделен на сектори с числа; хардуерен генератор на шум (HS), който използва шумно термично устройство, например транзистор (фиг. 22.422.5).

Табличен RNG

Табличните RNG използват специално компилирани таблици, съдържащи проверени некорелирани, т.е. по никакъв начин не зависими едно от друго, числа като източник на произволни числа. В табл Фигура 22.1 показва малък фрагмент от такава таблица. Като обхождате таблицата отляво надясно отгоре надолу, можете да получите произволни числа, равномерно разпределени от 0 до 1 с необходимия брой десетични знаци (в нашия пример използваме три десетични знака за всяко число). Тъй като числата в таблицата не зависят едно от друго, таблицата може да се обхожда по различни начини, например отгоре надолу или отдясно наляво, или, да речем, можете да изберете числа, които са на четни позиции.

Предимството на този метод е, че произвежда наистина произволни числа, тъй като таблицата съдържа проверени некорелирани числа. Недостатъци на метода: за съхранение голямо количествочислата изискват много памет; Има големи трудности при генерирането и проверката на такива таблици; повторенията при използване на таблица вече не гарантират произволност числова последователност, а следователно и надеждността на резултата.

Има таблица, съдържаща 500 абсолютно случайни проверени числа (взети от книгата на И. Г. Венецки, В. И. Венецкая „Основни математически и статистически понятия и формули в икономическия анализ“).

Алгоритмичен RNG

Числата, генерирани от тези RNG, винаги са псевдослучайни (или квазислучайни), т.е. всяко следващо генерирано число зависи от предишното:

r аз + 1 = f(r аз) .

Последователностите, съставени от такива числа, образуват цикли, т.е. задължително има цикъл, който се повтаря безкраен брой пъти. Повтарящите се цикли се наричат ​​периоди.

Предимството на тези RNG е тяхната скорост; генераторите практически не изискват ресурси на паметта и са компактни. Недостатъци: числата не могат да се нарекат напълно случайни, тъй като между тях има зависимост, както и наличието на периоди в последователността от квазислучайни числа.

Нека разгледаме няколко алгоритмични метода за получаване на RNG:

• метод на средните квадрати;
• метод на средните продукти;
• метод на разбъркване;
• линеен конгруентен метод.

Метод на средния квадрат

Има някакво четирицифрено число Р 0 . Това число се повдига на квадрат и се въвежда Р 1. Следваща от Р 1 взема средното (четири средни цифри) ново произволно число и го записва в него Р 0 . След това процедурата се повтаря (виж Фиг. 22.6). Имайте предвид, че всъщност като произволно число трябва да вземете не ghij, А 0.ghijс нула и десетична запетая, написани отляво. Този факт е отразен, както на фиг. 22.6 и в следващите подобни фигури.

Недостатъци на метода: 1) ако при някаква итерация числото Р 0 става равно на нула, тогава генераторът се изражда, така че правилният избор на началната стойност е важен Р 0 ; 2) генераторът ще повтори последователността до М пстъпки (в най-добрия случай), къде пчислова цифра Р 0 , Моснова на бройната система.

Например на фиг. 22.6: ако числото Р 0 ще бъде представена в двоичната бройна система, тогава последователността от псевдослучайни числа ще се повтори на 2 4 = 16 стъпки. Имайте предвид, че повторението на последователността може да се случи по-рано, ако началният номер е избран неправилно.

Методът, описан по-горе, е предложен от Джон фон Нойман и датира от 1946 г. Тъй като този метод се оказа ненадежден, той бързо беше изоставен.

Метод на средния продукт

Номер Р 0 умножено по Р 1, от получения резултат Р 2 средата се извлича Р 2 * (това е друго произволно число) и умножено по Р 1. Всички последващи произволни числа се изчисляват с помощта на тази схема (виж Фиг. 22.7).

Метод на разбъркване

Методът на разбъркване използва операции за циклично изместване на съдържанието на клетка наляво и надясно. Идеята на метода е следната. Нека клетката съхранява първоначалното число Р 0 . Циклично измествайки съдържанието на клетката наляво с 1/4 от дължината на клетката, получаваме ново число Р 0 * . По същия начин, цикъл на съдържанието на клетката Р 0 вдясно с 1/4 от дължината на клетката, получаваме второто число Р 0**. Сума от числа Р 0* и Р 0** дава ново произволно число Р 1. Следваща Р 1 е вписана Р 0 и цялата последователност от операции се повтаря (виж Фиг. 22.8).

Моля, обърнете внимание, че числото, получено от сумирането Р 0* и Р 0 **, може да не се побира напълно в клетката Р 1. В този случай допълнителните цифри трябва да бъдат изхвърлени от полученото число. Нека обясним това на фиг. 22.8, където всички клетки са представени с осем двоични цифри. Нека Р 0 * = 10010001 2 = 145 10 , Р 0 ** = 10100001 2 = 161 10 , Тогава Р 0 * + Р 0 ** = 100110010 2 = 306 10 . Както можете да видите, числото 306 заема 9 цифри (в двоичната бройна система), а клетката Р 1 (същото като Р 0) може да съдържа максимум 8 бита. Следователно, преди да въведете стойността в Р 1 е необходимо да се премахне един „допълнителен“, най-ляв бит от числото 306, което води до Р 1 вече няма да отива към 306, а към 00110010 2 = 50 10 . Също така имайте предвид, че в езици като Pascal, "подрязването" на допълнителни битове, когато клетката препълва, се извършва автоматично в съответствие с определения тип на променливата.

Линеен конгруентен метод

Линейният конгруентен метод е една от най-простите и най-често използвани процедури, които в момента симулират произволни числа. Този метод използва мода( х, г), който връща остатъка, когато първият аргумент е разделен на втория. Всяко следващо случайно число се изчислява на базата на предишното произволно число по следната формула:

r аз+ 1 = mod( к · r аз + b, М) .

Поредицата от произволни числа, получена с помощта на тази формула, се нарича линейна конгруентна последователност. Много автори наричат ​​линейна конгруентна редица, когато b = 0 мултипликативен конгруентен метод, и кога b ≠ 0 — смесен конгруентен метод.

За висококачествен генератор е необходимо да изберете подходящи коефициенти. Необходимо е броят Мбеше доста голям, тъй като периодът не може да има повече Мелементи. От друга страна, разделянето, използвано в този метод, е доста бавна операция, така че за двоичен компютър логичният избор би бил М = 2 Н, тъй като в този случай намирането на остатъка от делението се свежда вътре в компютъра до двоичната логическа операция „И“. Избирането на най-голямото просто число също е обичайно М, по-малко от 2 Н: в специализираната литература е доказано, че в този случай младшите цифри на полученото произволно число r аз+ 1 се държат също толкова произволно, колкото и по-старите, което има положителен ефект върху цялата последователност от случайни числа като цяло. Като пример, един от Числата на Мерсен, равно на 2 31 1, и по този начин, М= 2 31 1 .

Едно от изискванията за линейни конгруентни последователности е дължината на периода да бъде възможно най-дълга. Продължителността на периода зависи от стойностите М , ки b. Теоремата, която представяме по-долу, ни позволява да определим дали е възможно да постигнем периода максимална дължиназа конкретни стойности М , ки b .

Теорема. Линейна конгруентна последователност, дефинирана от числа М , к , bи r 0, има период с дължина Мако и само ако:

• числа bи Мотносително проста;
• к 1 пъти стрза всяко първо число стр, което е делител М ;
• к 1 е кратно на 4, ако Мкратно на 4.

И накрая, нека завършим с няколко примера за използване на линейния конгруентен метод за генериране на произволни числа.

Беше установено, че серия от псевдослучайни числа, генерирани въз основа на данните от пример 1, ще се повтаря всеки М/4 броя. Номер рсе задава произволно преди началото на изчисленията, но трябва да се има предвид, че серията създава впечатление за произволна като цяло к(и следователно р). Резултатът може да се подобри донякъде, ако bстранно и к= 1 + 4 · р в този случай редът ще се повтаря всеки Мчисла. След дълго търсене кизследователите се спират на стойности от 69069 и 71365.

Генератор на случайни числа, използващ данните от Пример 2, ще произведе произволни, неповтарящи се числа с период от 7 милиона.

Мултипликативният метод за генериране на псевдослучайни числа е предложен от D. H. Lehmer през 1949 г.

Проверка на качеството на генератора

Качеството на цялата система и точността на резултатите зависят от качеството на RNG. Следователно произволната последователност, генерирана от RNG, трябва да отговаря на редица критерии.

Извършваните проверки са два вида:

• проверки за равномерност на разпределението;
• тестове за статистическа независимост.

Проверява равномерността на разпределението

1) RNG трябва да произвежда близки до следните стойности на статистически параметри, характерни за единен случаен закон:

2) Честотен тест

Честотният тест ви позволява да разберете колко числа попадат в даден интервал (м r – σ r ; м r + σ r) , което е (0,5 0,2887; 0,5 + 0,2887) или в крайна сметка (0,2113; 0,7887). Тъй като 0,7887 0,2113 = 0,5774, заключаваме, че в добър RNG около 57,7% от всички произволни изтеглени числа трябва да попадат в този интервал (виж Фиг. 22.9).

Необходимо е също така да се вземе предвид, че броят на числата, попадащи в интервала (0; 0,5), трябва да бъде приблизително равен на броя на числата, попадащи в интервала (0,5; 1).

3) Хи-квадрат тест

Тестът хи-квадрат (χ 2 тест) е един от най-известните статистически тестове; това е основният метод, използван в комбинация с други критерии. Тестът хи-квадрат е предложен през 1900 г. от Карл Пиърсън. Неговата забележителна работа се счита за основа на съвременната математическа статистика.

За нашия случай проверката с помощта на критерия хи-квадрат ще ни позволи да разберем колко е истински RNG е близо до референтната стойност на RNG, т.е. дали удовлетворява изискването за равномерно разпределение или не.

Честотна диаграма справка RNG е показан на фиг. 22.10. Тъй като законът за разпределение на референтния RNG е еднакъв, тогава (теоретичната) вероятност стр азвъвеждане на числа азти интервал (всички тези интервали к) е равно на стр аз = 1/к . И по този начин във всяка от кинтервалите ще ударят гладкаот стр аз · Н числа ( Нобщ брой генерирани числа).

Истинският RNG ще произведе числа, разпределени (и не непременно равномерно!) напречно кинтервали и всеки интервал ще съдържа п азчисла (общо п 1 + п 2 + + п к = Н ). Как можем да определим колко добър е тестваният RNG и колко близо е до референтния? Съвсем логично е да се вземат предвид квадратните разлики между получения брой числа п ази "справка" стр аз · Н . Нека ги съберем и резултатът е:

χ 2 експ. = ( п 1 стр 1 · Н) 2 + (п 2 стр 2 · Н) 2 + + ( п к – стр к · Н) 2 .

От тази формула следва, че колкото по-малка е разликата във всеки от членовете (и следователно колкото по-малка е стойността на χ 2 exp.), толкова по-силен е законът за разпределение на случайни числа, генерирани от реален RNG, има тенденция да бъде еднакъв.

В предишния израз на всеки от термините е присвоено едно и също тегло (равно на 1), което всъщност може да не е вярно; следователно за хи-квадрат статистиката е необходимо да се нормализира всеки азти член, разделяйки го на стр аз · Н :

И накрая, нека напишем получения израз по-компактно и го опростим:

Получихме стойността на теста хи-квадрат за експерименталенданни.

В табл 22.2 са дадени теоретиченстойности на хи-квадрат (χ 2 теоретични), където ν = Н 1 е броят на степените на свобода, стртова е зададено от потребителя ниво на достоверност, което показва колко RNG трябва да отговаря на изискванията за равномерно разпределение, или стр — е вероятността експерименталната стойност на χ 2 exp..

1.64 стр 0,674.

Счита се за приемливо строт 10% до 90% Ако χ 2 exp.много повече от χ 2 теорията. п аз(т.е стр аз · Н е голям), тогава генераторът

Дори Д. Кнут в книгата си „Изкуството на програмирането” отбеляза, че имайки χ 2 exp.

за малките като цяло също не е добре, въпреки че това на пръв поглед изглежда прекрасно от гледна точка на еднообразието. Наистина, вземете поредица от числа 0.1, 0.2, 0.3, 0.4, 0.5, 0.6, 0.7, 0.8, 0.9, 0.1, 0.2, 0.3, 0.4, 0.5, 0.6, те са идеални от гледна точка на еднаквост и χ 2 опит стрще бъдат практически нула, но е малко вероятно да ги разпознаете като случайни. Ако χ 2 exp.Ако χ 2 exp. п азмного по-малко от χ 2 теорията. стр аз · Н (т.е

малък), след това генератора стризискването за случайно равномерно разпределение, тъй като наблюдаваните стойности стртвърде близо до теоретичното

и не може да се счита за случаен. стр аз · Н Но ако χ 2 exp.

лежи в определен диапазон между две стойности на χ 2 теор. , които съответстват напр.

= 25% и

= 50%, тогава можем да приемем, че стойностите на случайни числа, генерирани от сензора, са напълно произволни.

Освен това трябва да се има предвид, че всички ценности

трябва да са достатъчно големи, например повече от 5 (установено емпирично). Само тогава (с достатъчно голяма статистическа извадка) експерименталните условия могат да се считат за задоволителни. стр азИ така, процедурата за проверка е следната. азТестове за статистическа независимост

1) Проверка на честотата на срещане на числата в редицата

Нека разгледаме един пример. Случайното число 0.2463389991 се състои от цифрите 2463389991, а числото 0.5467766618 се състои от цифрите 5467766618. Свързвайки последователностите от цифри, получаваме: 24633899915467766618. п ЛЯсно е, че теоретичната вероятност Лзагуба ЛЦифрата (от 0 до 9) е равна на 0,1. м 2) Проверка на появата на серии от еднакви числа мНека означим с

брой поредици от еднакви цифри в ред с дължина п. Всичко трябва да се провери п 3 = 2 .

от 1 до Л, Къде стр Лтова е зададено от потребителя число: максималният срещащ се брой еднакви цифри в серия. Л В примера “24633899915467766618” са открити 2 серии с дължина 2 (33 и 77), т.е. стр 2 = 2 и 2 серии с дължина 3 (999 и 666), т.е стрВероятността за поява на серия с дължина стре равно на:

= 9 10 стр Л= 0,9, тъй като може да има само един символ от 10 и има общо 9 символа (нулата не се брои). А вероятността два еднакви символа “XX” да се появят в един ред е 0,1 · 0,1 · 9, тоест вероятността от 0,1 символът “X” да се появи на първа позиция се умножава по вероятността от 0,1, че същият символ ще се появи на втората позиция „X“ и ще бъде умножен по броя на тези комбинации 9.

Честотата на поява на сериите се изчислява с помощта на формулата хи-квадрат, която обсъдихме по-рано, използвайки стойностите стр Л .

Забележка: Генераторът може да бъде тестван многократно, но тестовете не са пълни и не гарантират, че генераторът произвежда произволни числа. Например, генератор, който произвежда последователността 12345678912345, ще се счита за идеален по време на тестовете, което очевидно не е напълно вярно.

В заключение отбелязваме, че третата глава от Изкуството на програмирането (том 2) на Donald E. Knuth е изцяло посветена на изучаването на случайни числа. То изучава различни методигенериране на случайни числа, статистически тестове за случайност и преобразуване на равномерно разпределени случайни числа в други видове случайни променливи. Повече от двеста страници са посветени на представянето на този материал.

Получаване и преобразуване на случайни числа.

Има два основни начина за получаване на случайни числа:

1) Случайните числа се генерират от специална електронна приставка (сензор за произволни числа), инсталирана на компютъра. Прилагането на този метод не изисква почти никакви допълнителни операции, освен достъп до сензора за случайни числа.

2) Алгоритмичен метод – базира се на генериране на произволни числа в самата машина с помощта на специална програма. Недостатъкът на този метод е допълнителен разходкомпютърно време, тъй като в този случай машината изпълнява операциите на самата електронна приставка.

Програма за генериране на произволни числа, използваща даден закон за разпределение, може да бъде тромава. Следователно случайните числа с даден закон на разпределение обикновено се получават не директно, а чрез трансформиране на случайни числа, които имат някакво стандартно разпределение. Често това стандартно разпределение е равномерното разпределение (лесно за получаване и лесно за конвертиране към други закони).

Най-изгодно е да се получат произволни числа с единен закон с помощта на електронна приставка, която освобождава компютъра от допълнителни разходи за компютърно време. Получаването на чисто равномерно разпределение на компютър е невъзможно поради ограничения характер на битовата мрежа. Следователно, вместо непрекъснат набор от числа на интервала (0, 1), се използва дискретен набор от числа 2 пчисла, къде п– битова дълбочина на машинната дума.

Законът за разпределение на такава популация се нарича квази-униформа . При n³20 разликите между единните и квази-единните закони стават незначителни.

За получаване на квази-еднородни произволни числа се използват 2 метода:

1) генериране на случайни числа с помощта на електронна приставка чрез моделиране на някои случайни процеси;

2) получаване на псевдослучайни числа с помощта на специални алгоритми.

Да получаваш п-цифрено двоично случайно число, първият метод симулира последователност от независими случайни променливи z i, приемайки стойност 0 или 1. Получената последователност е 0 и 1, ако я разглеждаме като дробно число, и представлява случайна променлива с квазиравномерно разпределение в интервала (0, 1). Хардуерните методи за получаване на тези числа се различават само по начина, по който получават изпълнението z i.

Един от методите се основава на преброяване на броя на радиоактивните частици за определен период от време Dt, ако броят на частиците е извън Dtдори тогава z i=1 , и ако е странно, тогава z i=0 .

Друг метод използва шумовия ефект на вакуумна тръба. Чрез записване на стойността на шумовото напрежение в определени моменти от времето t i, получаваме стойностите на независими случайни променливи U(t i), т.е. напрежение (волта).

величина z iопределени от закона:

Къде а– определена стойност на праговото напрежение.

величина аобикновено се избира от условието:

Недостатъкът на хардуерния метод е, че той не позволява използването на метода на двойно изпълнение за контрол на работата на алгоритъма за решаване на всеки проблем, тъй като многократните изпълнения не успяват да получат едни и същи произволни числа.

ПсевдослучайностТе извикват числата, генерирани на компютър с помощта на специални програми, по повтарящ се начин: всяко произволно число се получава от предишното чрез специални трансформации.

Най-простата от тези трансформации е следната. Нека има малко п– битово двоично число от интервала nО (0, 1).Нека го повдигнем на квадрат и получаваме 2 пцифрено число. Нека подчертаем средните стойности пизхвърляния. Получени по този начин п– цифровото число ще бъде новата стойност на произволното число. Отново го поставяме на квадрат и т.н. Тази последователност е псевдослучайна, т.к от теоретична гледна точка не е случаен.

Недостатъкът на повтарящите се алгоритми е, че последователностите от случайни числа могат да се изродят (например ще получим само последователност от нули или последователност от единици или може да се появи периодичност).