Генератор випадкових чисел у системі дистанційного контролю знань
У статті розглянуто питання використання генератора випадкових чисел (ГВЧ) у системах дистанційного навчання та контролю знань. Проаналізовано недоліки застосування для даного типу задач існуючих ГВЧ та запропоновано принципово новий тип генератора на основі описаної у статті -операції. Проведені д...
Збережено в:
| Опубліковано в: : | Математичні машини і системи |
|---|---|
| Дата: | 2004 |
| Автори: | , , |
| Формат: | Стаття |
| Мова: | Українська |
| Опубліковано: |
Інститут проблем математичних машин і систем НАН України
2004
|
| Теми: | |
| Онлайн доступ: | https://nasplib.isofts.kiev.ua/handle/123456789/83932 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Генератор випадкових чисел у системі дистанційного контролю знань / Р.А. Заторський, П.І. Федорук, Н.М. Дяків // Мат. машини і системи. — 2004. — № 4. — С. 98-107. — Бібліогр.: 2 назв. — укр |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1859798337455128576 |
|---|---|
| author | Заторський, Р.А. Федорук, П.І. Дяків, Н.М. |
| author_facet | Заторський, Р.А. Федорук, П.І. Дяків, Н.М. |
| citation_txt | Генератор випадкових чисел у системі дистанційного контролю знань / Р.А. Заторський, П.І. Федорук, Н.М. Дяків // Мат. машини і системи. — 2004. — № 4. — С. 98-107. — Бібліогр.: 2 назв. — укр |
| collection | DSpace DC |
| container_title | Математичні машини і системи |
| description | У статті розглянуто питання використання генератора випадкових чисел (ГВЧ) у системах дистанційного навчання та контролю знань. Проаналізовано недоліки застосування для даного типу задач існуючих ГВЧ та запропоновано принципово новий тип генератора на основі описаної у статті -операції. Проведені дослідження показали, що запропонований нами ГВЧ може досить ефективно застосовуватись не тільки в системах дистанційного навчання і контролю знань, де і було проведено його апробацію, але й в інших областях застосування, які потребують ГВЧ з якомога більш рівномірним розподілом частот попадання виборки по всій заданій множині.
В статье рассматриваются вопросы использования генератора случайных чисел (ГСЧ) в системе дистанционного образования и контроля знаний. Проанализирован недостатки применения для подобного типа задач существующих ГСЧ и предложен принципиально новый тип генератора на базе описанной в статье -операции. Проведенные исследования показывают, что предложенный ГСЧ может достаточно эффективно использоваться не только в системах дистанционного образования и контроля знаний, где и была осуществлена его апробация, но и в других областях применения, которые нуждаются в ГСЧ с наиболее равномерным распределением частот попадания выборки по всему заданному множеству.
Article is dedicated to the problem of random numbers generator (RNG) that may be used in systems of distance education and knowledge control. Weak points of existing RNG applied for typical tasks in this area have been analyzed and a new type of generators based on described -function has been offered. Conducted researches convincingly show that offered RNG can be effectively used not only in systems of distance education and knowledge control where its approbation has been carried out but also in other calculating and mathematical systems requiring RNG with the most uniform frequency distribution on given set.
|
| first_indexed | 2025-12-07T15:11:16Z |
| format | Article |
| fulltext |
ISSN 1028-9763. Математичні машини і системи, 2004, № 4
98
УДК 651.3:518.5
Р.А. ЗАТОРСЬКИЙ, П.І. ФЕДОРУК, Н.М. ДЯКІВ
ГЕНЕРАТОР ВИПАДКОВИХ ЧИСЕЛ У СИСТЕМІ ДИСТАНЦІЙНОГО
КОНТРОЛЮ ЗНАНЬ
Abstract: Article is dedicated to the problem of random numbers generator (RNG) that may be used in systems of
distance education and knowledge control. Weak points of existing RNG applied for typical tasks in this area have
been analyzed and a new type of generators based on described nf -function has been offered. Conducted
researches convincingly show that offered RNG can be effectively used not only in systems of distance education and
knowledge control where its approbation has been carried out but also in other calculating and mathematical systems
requiring RNG with the most uniform frequency distribution on given set.
Key words: random number generator, system of distance knowledge control.
Анотація: У статті розглянуто питання використання генератора випадкових чисел (ГВЧ) у системах
дистанційного навчання та контролю знань. Проаналізовано недоліки застосування для даного типу задач
існуючих ГВЧ та запропоновано принципово новий тип генератора на основі описаної у статті nf -
операції. Проведені дослідження показали, що запропонований нами ГВЧ може досить ефективно
застосовуватись не тільки в системах дистанційного навчання і контролю знань, де і було проведено його
апробацію, але й в інших областях застосування, які потребують ГВЧ з якомога більш рівномірним
розподілом частот попадання виборки по всій заданій множині.
Ключові слова: генератор випадкових чисел, система дистанційного контролю знань.
Аннотация: В статье рассматриваются вопросы использования генератора случайных чисел (ГСЧ) в
системе дистанционного образования и контроля знаний. Проанализировано недостатки применения для
подобного типа задач существующих ГСЧ и предложено принципиально новый тип генератора на базе
описанной в статье nf -операции. Проведенные исследования показывают, что предложенный ГСЧ может
достаточно эффективно использоваться не только в системах дистанционного образования и контроля
знаний, где и была осуществлена его апробация, но и в других областях применения, которые нуждаются
в ГСЧ с наиболее равномерным распределением частот попадания выборки по всему заданному
множеству.
Ключевые слова: генератор случайных чисел, система дистанционного контроля знаний.
1. Вступ
В наш час все ширшого розповсюдження в наш час набувають системи дистанційного навчання та
контролю знань. Розвиток інформаційних та телекомунікаційних технологій постійно відкриває нові
можливості для застосування в освіті систем, які використовують комп’ютерну техніку та
інформаційні мережі. В таких системах на відміну від традиційного навчання використовуються інші
засоби і методи передачі та контролю знань. Особливо велике значення має розробка і створення
ефективних інструментів, які б забезпечили проведення процедури дистанційного контролю знань з
достатньою мірою валідності. Валідність – це сукупність відомостей про те, відносно яких
характеристик особистості можуть виноситись кваліфікаційні судження, а також про міру
обґрунтованості останніх на підставі тестових оцінок або якихось інших засобів оцінювання [1].
В сучасних навчальних системах для контролю знань найчастіше використовуються тести.
З’ясувати валідність тесту означає перевірити, чи дійсно тест вимірює потрібну нам характеристику
і наскільки надійно він це робить. Зрозуміло, що метою розробника є максимально досяжна за
даних умов валідність. Велике значення в забезпеченні валідності відіграє вибір з бази запитань у
випадковому порядку для проведення тестування з рівномірним розподілом такої виборки по всій
множині запитань, щоб випадково генеровані тестові комплекти були валідними з точки зору
різноманітності й повноти охоплення матеріалу, рівень засвоєння якого потрібно визначити. Тому
ISSN 1028-9763. Математичні машини і системи, 2004, № 4
99
0
0,2
0,4
0,6
0,8
1
1,2
0 500 1000 1500 2000 2500
Номер питання в базі
Ч
ас
то
та
п
оя
ви
Рис. 1. Частота вибору з бази питань для тестування
(від 1 до 2000)
використання в системі дистанційного контролю знань генератора випадкових чисел, за допомогою
якого б організовувалась рівномірно розподілена виборка, є важливою і актуальною задачею.
Якщо взяти до уваги генератори випадкових чисел, які найчастіше використовуються в
різних операційних системах як одна з програм з стандартного набору, то в більшості випадків
використовується один і той же ж
алгоритм. Тому на даний момент цей
генератор вважається стандартним при
використанні в різних програмах.
Зокрема, в попередніх версіях
розробленої нами системи дистанційного
навчання і контролю знань
використовувалась функція rand з
операційної системи FreeBSD. Розподіл,
отриманий за допомогою цієї функції,
виглядає таким чином (рис. 1).
Як бачимо, забезпечити
рівномірність вибору питань з бази за
допомогою цієї функції не вдається. Тому нами пропонується застосувати генератор випадкових
чисел на основі nf - операції. Для цього опишемо nf - операцію і її властивості.
2. nf - операція і її властивості
Означення 1. Нехай n – деяке натуральне L – цифрове число, а nΩ – множина пар, де x і y –
цілі невід’ємні числа, що належать відповідно відрізкам
{
L
99,0 K і [ ]1,0 −n . nf - операцією
назвемо операцію, яка парі nxy Ω∈),( ставить у відповідність пару ),( uv , компоненти якої
визначаються рівністю
uvyxn L +⋅=+⋅ 10 , (1)
де Lu 10< . Якщо ),(),( uvxyf n = , то вважатимемо, що
),(),(),( 2 uvfxyfxyff nnnn ==o .
Зауваження. Множина Ω , очевидно, є множиною цілочисельних точок деякого прямокутника, тому
пари ),( xy ми іноді називатимемо його точками.
Властивість 1. (Замкнутість) nf - операція переводить множину nΩ в себе, тобто, якщо
nxy Ω∈),( ),(),( uvxyfn → , то і nuv Ω∈),( .
ISSN 1028-9763. Математичні машини і системи, 2004, № 4
100
Доведення. Те, що 0≥v і
{
∈
L
u 09,0 K випливає з визначення nf - операції. Доведемо, що
1−≤ nv . Якщо
{
L
x 99K= , то
{
ynnyn LL
L
+−+⋅−=+⋅ 1010)1(99K , але оскільки 1−≤ ny , то
{
L
L yn 9910 K≤+− , і максимальне значення v дорівнює 1−n .
Означення 2. Операцію 1−
nf назвемо оберненою до операції nf , якщо ( )1 ( , ) ( , )n nf f y x y x− = .
Властивість 2. (Єдиність) Операції nf і 1−
nf кожному прообразу ставлять у відповідність єдиний
образ.
Доведення. Доведемо справедливість цього твердження для nf -операції. Припустимо, що
виконуються дві рівності
uvyxn L +⋅=+⋅ 10 ;
11 10 uvyxn L +⋅=+⋅ .
Причому 1vv ≠ або 1uu ≠ . Віднімемо від першої рівності другу, одержимо
0)(10)( 11 =−+⋅− uuvv L .
Звідки, в силу нерівностей 1≥L , 1−≤ nu , 11 −≤ nu , випливає рівність, 1uu = , що суперечить
припущенню.
Доведення цього твердження для операції 1−
nf аналогічне.
Властивість 3. (Нерухомі точки) Якщо має місце рівність
{
ynx
L
⋅=−⋅ 99)1( K , (2)
то ),( xy – нерухома точка множини nΩ .
Доведення. Нехай виконується рівність (2), тоді xyynx L +⋅=+ 10 , тобто за визначенням )(nf -
операції маємо ),(),(:)( xyxynf → .
Зауваження 1. З рівності (2) випливає, що всі нерухомі точки )(nf - операції знаходяться в
цілочисельних точках діагоналі прямокутника nΩ , яка з’єднує точки )0,0( і
{
)99,1(
L
n K− .
Приклад 1. Знайдемо всі нерухомі точки 34f - операції. Точка (0,0) є нерухомою точкою будь-якої
nf -операції. Знайдемо всі пари 34),( Ω∈xy , що задовольняють рівності (2), тобто рівності
yx ⋅= 3 .
Ними, очевидно, будуть пари )3,( ii , де 33,1,0 K=i . Отже, 34f - операція має 34
нерухомі точки.
ISSN 1028-9763. Математичні машини і системи, 2004, № 4
101
Оскільки множина Ω складається з рухомих і нерухомих точок, то в результаті скінченності
цієї множини можна стверджувати, що кожній рухомій точці ),( xy відповідає деяка орбіта
{ }),(;),(;),(),(),( 110 xyfxyfxyfxyxyO k
nnnn
−== K ,
де k – якнайменше натуральне число таке, що
),(),( xyxyf k
n = .
Точку ),( xy назвемо твірною цієї орбіти, а число k – її довжиною.
Зауваження 1. Нерухому точку можна вважати орбітою довжини 1.
Зауваження 2. Аналітичного методу знаходження довжини орбіти точки ),( xy , очевидно, не існує.
Тому необхідно обчислювати її або вручну або за допомогою комп'ютера. Так, за допомогою
комп'ютера було встановлено, що 9999999)2000,0(2000 =O .
Визначення 4. Пари ),( xy і
{
)99,1( xyn
L
−−− K назвемо взаємно спряженими парами. Дві орбіти,
що складаються з взаємно спряжених пар, назвемо взаємно спряженими орбітами і позначимо
nO і nO .
Очевидно, що точки прямокутника Ω , які відповідають взаємно спряженим парам,
симетричні відносно точки перетину діагоналей цього прямокутника.
Властивість 4. Довжини орбіт взаємно спряжених пар співпадають.
Доведення. Нехай ),(),( uvxyf n = , тобто uvyxn L +⋅=+⋅ 10 . Доведемо, що
{ {
)99,1()99,1( uvnxynf
LL
n −−−=−−− KK .
Дійсно,
.11010)1(
110101101)99(
uvn
uvnyxnnynxn
LL
LLL
L
−−+⋅−−=
=−−⋅−⋅=−−⋅−⋅=−−+−⋅
321
K
Таким чином, якщо ),(,,),(,),( 21 xyfxyfxyf nT
nnn K представляють різні пари, то і
{ { {
)99,1(,,)99,1(,)99,1( 21 xynfxynfxynf
L
T
n
L
n
L
n
n −−−−−−−−− KKKK теж
представляють різні пари, причому, оскільки ),(),( xyxyf nT
n = , то і
{ {
)99,1()99,1( xynxynf
LL
T
n
n −−−=−−− KK .
Властивість 5. Взаємно спряжені пари належать різним орбітам.
Доведення. Нехай ),( xy , ),( xy – дві спряжені пари, що належать одній орбіті ),( xyOn довжини
0),( >= kxyOn . Тоді існує таке натуральне число kl < , що виконується
рівність ),(),( xyxyf l
n = , а одночасно і рівність
ISSN 1028-9763. Математичні машини і системи, 2004, № 4
102
),(),( xyfxy l
n
−= . (3)
Але оскільки орбіта ),( xyOn має довжину k , то виконується рівність
),(),( xyxyf lk
n =− . (4)
Порівнюючи рівності (3), (4) і враховуючи властивість 2, приходимо до рівності 0=k , яка
суперечить нерівності 0>k .
Зауваження. З властивостей (4) і (5) випливає, що nf -операція розбиває кожну множину nΩ на
парну кількість орбіт однакової довжини. Причому для кожної орбіти в цій множині існує спряжена
орбіта.
Приклад 2. 11f -операція розбиває множину YX ×=Ω , де { } { }99;;1;0,10;;1;0 KK == YX на
28 орбіт, кожна з яких має довжину 39, дві орбіти довжиною 3 і дві нерухомі точки.
3. nf - операція як генератор випадкових чисел
Як вже згадувалось вище, відправляючись від пари )2000,0( , при допомозі 2000f - операції можна
одержати неперіодичну послідовність чисел, яка складається з 9999999 чотирицифрових чисел.
Таким чином, nf -операція при порівняно невеликих значеннях n генерує достатньо великі
неперіодичні масиви L -цифрових чисел. Дослідимо гістограми частот деяких масивів чисел, що
генеруються при допомозі nf -операції.
Приведемо таблицю частот другої компоненти орбіти )90,0(90O , в якій у першому рядку
записано другу компоненту, а в другому рядку – її кількість в масиві (табл.1).
Таблиця 1.Частота повторів другої компоненти
Компонента 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
Кількість
повторів
56 49 54 44 48 52 44 48 55 39 48 47 50 49 41 45 43 53 42 37
Компонента 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39
Кількість
повторів
47 46 46 47 44 52 51 45 49 38 38 45 47 43 52 44 43 44 44 45
Компонента 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59
Кількість
повторів
50 49 52 35 47 44 42 44 41 41 49 49 46 48 46 43 55 38 41 40
Компонента 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79
Кількість
повторів
45 46 46 47 46 38 47 43 45 52 52 41 45 39 38 46 43 44 44 43
ISSN 1028-9763. Математичні машини і системи, 2004, № 4
103
Рис. 2. Приклад емпіричного розподілу
Компонента 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99
Кількість
повторів
53 48 37 47 45 49 41 40 43 42 51 35 42 46 38 42 46 36 41 33
За допомогою ЕОМ знайдено, що довжина орбіти )90,0(90O рівна 4499. Отже, кожне із ста
різних значень в середньому повинне повторюватися 44,99 раз. Як видно з цієї таблиці, частота
появи чисел досить стійко коливається біля числа 45.
4. Оцінка генератора випадкових чисел
Для того, щоб все ж таки визначити, чи буде наш генератор генератором випадкових чисел в
загальноприйнятому розумінні, проведемо дослідження відповідності його певним відомим
критеріям [2]. Розглянемо декілька специфічних критеріїв, які традиційно застосовуються для
перевірки, чи буде послідовність випадковою.
Критерій рівномірності (критерій частот). Найперша вимога, яка висувається до послідовності
випадкових чисел від a до b , полягає в тому, щоб її члени були рівномірно розподілені на відрізку
];[ ba . Застосуємо критерій Колмогорова-Смірнова з xxF =)( для .bxa ≤≤ Було виконано
1000=n випадкових досліджень і отримано випадкові значення nXXX ,,, 21 K ; емпіричну
функцію розподілу )(xFn було побудовано за формулою
n
xXXX
xF n
n
≤
=
вонищотаких,,,кількість
)( 21 K
.
На (рис. 2) зображено графік знайденої
емпіричної функції розподілу (зигзагоподібна лінія) та
накладений на неї графік функції розподілу xxF =)( .
При зростанні n )(xFn більш точно наближає
функцію розподілу.
Критерій Колмогорова-Смірнова базується на
різниці між )(xF та )(xFn . Очевидно, що велика
різниця між ними є неймовірною, і тільки КС-критерій
може показати, наскільки саме.
Щоб побудувати КС-критерій, утворимо такі статистики:
( )
( ).)()(max
;)()(max
xFxFnK
xFxFnK
n
x
n
n
x
n
−=
−=
∞<<∞−
−
∞<<∞−
+
Тут +
nK визначає найбільше з відхилень, коли )(xFn більша, ніж )(xF , а −
nK – )(xFn
менша, ніж )(xF . Для розглядуваного прикладу ці статистики набувають значень: 8136.01000 =+K
ISSN 1028-9763. Математичні машини і системи, 2004, № 4
104
та 3828.01000 =−K . Для порівняння було взято аналогічні результати для а) методу Мак-Лорена-
Марсалья, б) генератора Фібоначчі, в) для стандартного UNIX-генератора. Отримано такі
результати (табл. 2):
Таблиця 2. Порівняння значень характеристик в КС-критерії
Генератор
Статистика
а) б) в)
+
1000K 0,577 2,819 0,949
−
1000K 0,867 0,258 0,141
Як і для −2χ критерію, отримані значення +
nK і −
nK можна порівняти з процентною
таблицею і визначити, чи є вони суттєво більшими, чи меншими. При цьому відмінність від
−2χ критерію полягає в тому, що процентна таблиця містить не просто наближені значення,
справедливі при великих значеннях n , а точні значення (з урахуванням похибки обчислень).
Значення деяких процентних точок для розподілу +
1000K , −
1000K (табл. 3):
Таблиця 3. Деякі процентні точки розподілів +
nK і −
nK
Точка
Степінь
свободи
p=1% p=5% p=25% p=50% p=75% p=95% p=99%
1000=n 0,0656 0,1548 0,3740 0,5834 0,8273 1,2186 1,5121
Отримані значення 8136,01000 =+K та 3828,01000 =−K знаходяться між 25- та 50-
процентною точками, тому розглядувати ці значення як значно більші або значно менші не можна.
Таким чином, проведені спостереження є задовільно випадковими по відношенню до розглянутого
критерію.
Метод інтервалів. Використовується для перевірки довжини ”інтервалів” між появою jU
( bUa j ≤≤ ) на деякому відрізку. Якщо α і β – два цілі числа, то розглядається довжина
підпослідовності rjjj UUU ++ ,,, 1 K , в яких rjU + лежить між α і β , а інші члени не лежать між цими
числами (цю підпослідовність, яка складається з 1+r числа, і називатимемо інтервалом довжиною
r ).
Для дослідження було використано такий алгоритм підрахунку кількості інтервалів
довжиною ( )1,,1,0 −tK та кількості інтервалів довжиною понад t (щоб у підсумку було рівно n
інтервалів) для довільних чисел α і β :
Крок 1. [Ініціалізація] Присвоїти 0,1 ←−← sj і присвоїти COUNT[r] 0← для кожного .0 tr ≤≤
ISSN 1028-9763. Математичні машини і системи, 2004, № 4
105
Крок 2. [Присвоєння r значення 0]. Присвоїти .0←r
Крок 3. Збільшити j на 1. Якщо α≥jU і β<jU , то перейти до кроку 5.
Крок 4. Збільшити r на 1 і повернутись до кроку 3.
Крок 5. (Щойно знайдено інтервал завдовжки r ). Якщо tr ≥ , то збільшити COUNT[t] на 1, в іншому
випадку – збільшити COUNT[r] на 1.
Крок 6. Збільшити s на 1. Якщо ns < , то повернутись до кроку 2.
Критерій інтервалів часто використовується для значень для того, щоб на кроці 3 уникнути
порівняння. Особливі випадки )
2
,(),(
b
a=βα та ),
2
(),( b
b=βα іноді називають „відхиленням
вище середнього” та „відхиленням нижче середнього” відповідно. Тестування здійснювалось для
випадків .80,20;100,50;50,0 ====== βαβαβα Після реалізації даного алгоритму
−2χ критерій застосовувався до значень COUNT[0], COUNT[1], ... , COUNT[t] з такими
ймовірностями:
.)1(;10для)1( t
t
r
r pptrppp −=−≤≤−=
Тут αβ −=p – ймовірність того, що .βα ≤≤ U Значення n і t вибирались так, щоб
очікуване значення COUNT[r] було не меншим 5. В результаті тестування було отримано такі
значення −2χ статистики: для відхилення вище середнього 6,4623282 =χ ; для відхилення нижче
середнього 9,186992 =χ ; для випадку 80,20 == βα значення 12,903512 =χ при ступені
свободи 11. Отримані значення знаходять відповідно між 10- і 25-, 25- і 50- та між 50- і 70-
процентними точками, а тому всі результати вважаються задовільно випадковими відносно
критерію інтервалів.
Покер-критерій (критерій розбиттів). „Класичний” покер-критерій розглядає n груп по п’ять
послідовних цілих чисел },,,,{ 453525155 ++++ jjjjj YYYYY для nj ≤≤0 і перевіряє, які з наступних
семи комбінацій відповідають таким п’ятіркам чисел (порядок не має значення) (табл. 4):
Таблиця 4. Типи категорій для класичного покер-критерію
Тип п’ятірки чисел Схематичне позначення
Всі числа різні: abcde
Одна пара: aabcd
Дві пари: aabbc
Три числа одного виду: aaabc
Повний набір: aaabb
Чотири числа одного виду: aaaab
П’ять чисел одного виду: aaaaa
−2χ критерій базується на підрахунку кількості п’ятірок у кожній категорії.
ISSN 1028-9763. Математичні машини і системи, 2004, № 4
106
Проте для використання покер-критерію при роботі з комп’ютером використовують дещо
спрощену його версію, яка здійснює простіший підрахунок різних значень у множині п’ятірок. У
цьому випадку виділяють п’ять категорій (табл. 5):
Таблиця 5. Типи категорій для модифікованого покер-критерію
Категорія Умова належності п’ятірки чисел до категорії
5 = всі різні
4 = одна пара
3 = дві пари або три числа одного виду
2 = повний набір або 4 числа одного виду
1 = п’ять чисел одного виду
При такій схемі спрощуються підрахунки і критерій залишається практично таким же ефективним.
При цьому ймовірність того, що в групі з k елементів є r різних елементів, становить
,
)1()1(
+−−=
r
k
d
rddd
p
kr
K
де 100=d (для розглядуваного випадку);
r
k
– числа Стірлінга.
При аналізі отриманих послідовностей випадкових чисел було отримано такі результати (табл. 6):
Таблиця 6. Результати застосування модифікованого покер-критерію
Категорія Кількість Ймовірність
5 825 0,90345
4 83 0,09558
3 2 0,00097
Отримане значення −2χ статистики 1,605333 при цьому знаходиться між 50- і 75-
процентними точками, тобто згенеровані числа є досить випадковими.
Критерій „максимум-t”. Позначимо ),,,max( 11 −++= ttjtjtjj UUUV K для .0 nj ≤≤ Після цього
застосуємо критерій Колмогорова-Смірнова до послідовності 110 ,,, −nVVV K , таким чином
перевіривши гіпотезу про те, що функція розподілу jV дорівнює .10,)( ≤≤= xxxF t Оскільки
даний критерій застосовний до чисел, що належать відрізку 10 ≤≤ x , то, щоб використати даний
критерій до випадкової послідовності чисел 990},,,,{ 21 ≤≤= in VVVVV K , було здійснено
перехід до послідовності },,,,{ 21 nAAAA K= де 10 ≤≤ iA за формулою .,...1,0,
99
ni
V
A i
i ==
Значення t було вибрано рівним 10. На (рис. 3) зображено емпіричну функцію розподілу та графік
функції 10)( xxF = .
ISSN 1028-9763. Математичні машини і системи, 2004, № 4
107
Отримані значення
статистик +
nK і −
nK становлять
відповідно 0,177947 та 0,761599,
тим самим знаходячись між 5- та
75-процентними точками. Резуль-
тати не заперечують задовільної
випадковості отриманої послідов-
ності.
5. Висновки
З результатів проведених досліджень можна зробити висновок про відповідність запропонованого у
статті генератора випадкових чисел критеріям рівномірності, інтервалів, „максимуму-t” і покер-
критерію [2]. Більше того, порівняння з результатами, отриманими для стандартних генераторів
випадкових чисел, які застосовуються на даний момент, дозволяє сказати, що результати
тестування побудованого генератора свідчать про задовільну, а часто навіть кращу, випадковість
отриманих послідовностей порівняно з існуючими.
Отже, запропонований нами генератор випадкових чисел на базі nf - операції може досить
ефективно застосовуватись не тільки в системах дистанційного навчання і контролю знань, де і
було проведено його апробацію, але й в інших областях застосування обчислювальних, які
потребують генератора випадкових чисел з якомога більш рівномірним розподілом частот
попадання виборки по всій заданій множині.
СПИСОК ЛІТЕРАТУРИ
1. Федорук П.І. Система дистанційного навчання та контролю знань на базі Internet–технологій (на прикладі
медичних вузів). – Івано-Франківськ: Плай, 2003. –138 с.
2. Кнут Д. Искусство программирования: Учебное пособие: Пер. с англ. – 3-е изд. – М.: Издательский дом
«Вильямс», 2000. – Т. 2: Получисленные алгоритмы. – 832 с.
0
0,2
0,4
0,6
0,8
1
1,2
0 0,2 0,4 0,6 0,8 1 1,2
A
F
(x
),
F
n
(x
)
Емпірична функція Теоретична функція
Рис. 3. Графік емпіричної та теоретичної функцій розподілу
|
| id | nasplib_isofts_kiev_ua-123456789-83932 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 1028-9763 |
| language | Ukrainian |
| last_indexed | 2025-12-07T15:11:16Z |
| publishDate | 2004 |
| publisher | Інститут проблем математичних машин і систем НАН України |
| record_format | dspace |
| spelling | Заторський, Р.А. Федорук, П.І. Дяків, Н.М. 2015-06-28T14:48:13Z 2015-06-28T14:48:13Z 2004 Генератор випадкових чисел у системі дистанційного контролю знань / Р.А. Заторський, П.І. Федорук, Н.М. Дяків // Мат. машини і системи. — 2004. — № 4. — С. 98-107. — Бібліогр.: 2 назв. — укр 1028-9763 https://nasplib.isofts.kiev.ua/handle/123456789/83932 651.3:518.5 У статті розглянуто питання використання генератора випадкових чисел (ГВЧ) у системах дистанційного навчання та контролю знань. Проаналізовано недоліки застосування для даного типу задач існуючих ГВЧ та запропоновано принципово новий тип генератора на основі описаної у статті -операції. Проведені дослідження показали, що запропонований нами ГВЧ може досить ефективно застосовуватись не тільки в системах дистанційного навчання і контролю знань, де і було проведено його апробацію, але й в інших областях застосування, які потребують ГВЧ з якомога більш рівномірним розподілом частот попадання виборки по всій заданій множині. В статье рассматриваются вопросы использования генератора случайных чисел (ГСЧ) в системе дистанционного образования и контроля знаний. Проанализирован недостатки применения для подобного типа задач существующих ГСЧ и предложен принципиально новый тип генератора на базе описанной в статье -операции. Проведенные исследования показывают, что предложенный ГСЧ может достаточно эффективно использоваться не только в системах дистанционного образования и контроля знаний, где и была осуществлена его апробация, но и в других областях применения, которые нуждаются в ГСЧ с наиболее равномерным распределением частот попадания выборки по всему заданному множеству. Article is dedicated to the problem of random numbers generator (RNG) that may be used in systems of distance education and knowledge control. Weak points of existing RNG applied for typical tasks in this area have been analyzed and a new type of generators based on described -function has been offered. Conducted researches convincingly show that offered RNG can be effectively used not only in systems of distance education and knowledge control where its approbation has been carried out but also in other calculating and mathematical systems requiring RNG with the most uniform frequency distribution on given set. uk Інститут проблем математичних машин і систем НАН України Математичні машини і системи Обчислювальні системи Генератор випадкових чисел у системі дистанційного контролю знань Генератор случайных чисел в системе дистанционного контроля знаний Random numbers generator in system of distance knowledge control Article published earlier |
| spellingShingle | Генератор випадкових чисел у системі дистанційного контролю знань Заторський, Р.А. Федорук, П.І. Дяків, Н.М. Обчислювальні системи |
| title | Генератор випадкових чисел у системі дистанційного контролю знань |
| title_alt | Генератор случайных чисел в системе дистанционного контроля знаний Random numbers generator in system of distance knowledge control |
| title_full | Генератор випадкових чисел у системі дистанційного контролю знань |
| title_fullStr | Генератор випадкових чисел у системі дистанційного контролю знань |
| title_full_unstemmed | Генератор випадкових чисел у системі дистанційного контролю знань |
| title_short | Генератор випадкових чисел у системі дистанційного контролю знань |
| title_sort | генератор випадкових чисел у системі дистанційного контролю знань |
| topic | Обчислювальні системи |
| topic_facet | Обчислювальні системи |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/83932 |
| work_keys_str_mv | AT zatorsʹkiira generatorvipadkovihčiselusistemídistancíinogokontrolûznanʹ AT fedorukpí generatorvipadkovihčiselusistemídistancíinogokontrolûznanʹ AT dâkívnm generatorvipadkovihčiselusistemídistancíinogokontrolûznanʹ AT zatorsʹkiira generatorslučainyhčiselvsistemedistancionnogokontrolâznanii AT fedorukpí generatorslučainyhčiselvsistemedistancionnogokontrolâznanii AT dâkívnm generatorslučainyhčiselvsistemedistancionnogokontrolâznanii AT zatorsʹkiira randomnumbersgeneratorinsystemofdistanceknowledgecontrol AT fedorukpí randomnumbersgeneratorinsystemofdistanceknowledgecontrol AT dâkívnm randomnumbersgeneratorinsystemofdistanceknowledgecontrol |