WWW.DISSERS.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

   Добро пожаловать!

Складні системи і процеси № 2, 2005 ІНФОРМАЦІЙНІ СИСТЕМИ І ТЕХНОЛОГІЇ ІНФОРМАЦІЙНІ СИСТЕМИ І ТЕХНОЛОГІЇ УДК 519.2:519.95:536 ПОРІВНЯЛЬНИЙ АНАЛІЗ АЛГОРИТМІВ ПОБУДОВИ ВИПАДКОВИХ ПОСЛІДОВНОСТЕЙ, ПРИЗНАЧЕНИХ ДЛЯ МОДЕЛЮВАННЯ ВИПАДКОВИХ БЛУКАНЬ МОЛЕКУЛ ІДЕАЛЬНОГО ГАЗУ Бахрушин В.Є.

Гуманітарний університет "Запорізький інститут державного та муніципального управління", вул. Жуковського, 70-б, Запоріжжя, Україна, 69002 Vladimir.Bakhrushin@zhu.edu.ua Вступ У зв’язку з розвитком комп’ютерної техніки при дослідженні складних природних і соціально-економічних систем усе більшого значення набувають методи імітаційного і статистичного моделювання. Їх реалізація зазвичай передбачає побудову випадкових послідовностей з певним законом розподілу. Існує багато алгоритмів побудови рівномірних випадкових послідовностей, а також випадкових послідовностей із заданими законами розподілу. Деякі з них описані у [1–3]. Як правило, всі алгоритми передбачають попередню побудову послідовностей, елементи яких підпорядковуються рівномірному розподілу на відрізку [0, 1]. Існує велика кількість методів їх побудови, що зумовлено суперечливими вимогами до одержуваних послідовностей. З одного боку, алгоритм повинен забезпечувати необхідну якість послідовності. При цьому поняття її якості може істотно залежати від того, де вона буде використовуватися надалі. З іншого боку, враховуючи, що побудова випадкової послідовності є лише попереднім етапом дослідження, застосовуваний алгоритм має бути таким, що не виявляє істотного впливу на потрібні для моделювання ресурси пам’яті ЕОМ, часу тощо. Згідно з [4], у багатьох випадках зазначені властивості поєднує алгоритм, що ґрунтується на використанні трикутного відображення. Це зумовлює необхідність його порівняння з іншими алгоритмами та перевірки в роботі при дослідженні тестових систем з відомою поведінкою.

Метою цієї роботи було проведення порівняльного аналізу алгоритму побудови випадкових послідовностей, що ґрунтується на використанні трикутного відображення, з деякими іншими стандартними алгоритмами генерації таких послідовностей.

Якість алгоритмів перевіряли за допомогою 2-тесту і в роботі при моделюванні випадкових блукань молекули ідеального газу.

Алгоритми побудови випадкових послідовностей Для побудови рівномірних випадкових послідовностей, заданих на відрізку [0, 1], у роботі було використано такі алгоритми.

1. Метод остач [1]. У цьому разі для одержання послідовності використовували рекурентне співвідношення k +1 = Mk, де хвилястими дужками позначено дробову частину { } числа. Як початкове значення 0 брали А·2–32, де 32 є числом двійкових розрядів у мантисі комірки ЕОМ. Число М брали рівним В·513 як число виду 52p+1 з максимальним цілим р, для якого виконується умова 52p+1 < 232. Числа А і В брали близькими до одиниці.

2. Вбудований алгоритм генерації рівномірних випадкових послідовностей, що застосовується в електронних таблицях MS Excel.

Складні системи і процеси № 2, 3. Алгоритм [4], що ґрунтується на використанні рекурентної формули, яка утворює наступний елемент із попереднього за допомогою трикутного відображення:

xn +1 = C 1- 2 0,5 - xn, де С є близьким до одиниці.

() Для імітації броунівського руху необхідно було використовувати також нормальні випадкові послідовності із середнім, рівним нулю, і заданим стандартним відхиленням. Для їх генерації використовували два методи, описані у [1].

1. Метод відбору, що ґрунтується на використанні такої властивості. Нехай 1 та 2 – це чергові числа, які належать до рівномірної випадкової послідовності, заданої на відрізку [0, 1]. Зробимо перетворення:

x' =1 b - a + a; y' =2c. (1) ( ) Випадкові величини x' та y' мають рівномірний розподіл на відрізках [a, b] і [0, c], відповідно. Можна довести, що випадкова величина, яка визначається умовою x = x ', якщо y' < f(x'), має щільність розподілу f(x). Для генерування випадкової послідовності з щільністю розподілу f(x) брали чергові два числа рівномірної випадкової послідовності 2i–1 та 2i. Потім розраховували відповідні значення xi' та yi'. Після цього перевіряли виконання умови yi' < f(xi'). Якщо вона виконувалася, то xk = xi' відбирали як черговий елемент послідовності, що треба побудувати. Якщо умова не виконувалася, поточну пару значень рівномірної випадкової послідовності відкидали і переходили до перевірки наступної пари.

2. Згідно з методом підсумовування величину =, що має нормальний розподіл з параметрами m = 0 та = 1, розраховували за формулою:

n = 2i (2) ( -1, ) n i=у якій n брали рівним 30. Це істотно вище, ніж рекомендується в літературі [1], але при нижчих значеннях n якість одержуваних послідовностей за критерієм 2 не завжди була задовільною.

Для отримання послідовності випадкових чисел, що мали нормальний розподіл з параметром = b, робили перетворення k = bk.

Перевірка якості рівномірних послідовностей за критерієм Як один із методів перевірки якості одержуваних рівномірних випадкових послідовностей було використано 2-тест електронних таблиць MS Excel, який дає імовірність р того, що досліджувана вибірка задовольняє заданому закону розподілу.

Для 100 послідовностей обсягом від 200 до 10000 елементів, отриманих за допомогою вбудованого генератора випадкових послідовностей MS Excel, значення імовірності р варіювали в інтервалі від 0,013 до 0,980 і не залежали від кількості елементів послідовності (рис. 1). Середнє значення імовірності p для кожної з отриманих серій випадкових послідовностей є близьким до 0,5, а її стандартне відхилення – до 0,3.

Для послідовностей обсягом від 200 до 10000 елементів, отриманих методом остач, значення імовірності р також варіювали в інтервалі від 0 до 1 і не залежали від кількості елементів послідовності (рис. 2). Але ці значення істотно й немонотонно залежали від параметрів А, В (рис. 3, 4). Змінюючи їх, можна дещо підвищити середнє значення і зменшити стандартне відхилення для імовірності p. У нашому випадку максимальні значення Складні системи і процеси № 2, імовірності р в серіях із 20 послідовностей дорівнювали 0,7 – 0,75, а мінімальні значення її стандартного відхилення – 0,1 – 0,15.

p 0,n 100 1000 Рис. 1. Залежність значень імовірності Рис. 2. Залежність значень імовірності 2-тесту від обсягу n для послідовностей, 2-тесту від обсягу n для послідовностей, отриманих за допомогою вбудованого ге- отриманих методом остач нератора MS Excel Рис. 3. Залежність середнього значення р Рис. 4. Залежність середнього значення р та стандартного відхилення s імовірності та стандартного відхилення s імовірності 2-тесту від параметра А для послідовнос- 2-тесту від параметра В для послідовностей, отриманих методом остач тей, отриманих методом остач Для послідовностей, отриманих за допомогою трикутного відображення, результат 2-тесту істотно залежить від обрання початкового елемента х1 (рис. 5). Ця залежність є хаотичною, тому придатні для досягнення мети моделювання значення х1 мають бути визначені попередньо.

Перевірка якості випадкових послідовностей за результатами моделювання випадкових блукань молекули ідеального газу При моделюванні випадкових блукань молекули ідеального газу припускали, що зіткнення молекул є центральними й абсолютно пружними, а самі молекули мають однакові маси. У цьому разі під час зіткнення молекули обмінюються своїми швидкостями. З огляду на це застосовували таку схему розрахунку. Спочатку задавали початкові значення координат і проекцій швидкостей молекули, рух якої спостерігався. Вони були взяті рівними нулю.

Крім того, були побудовані три випадкових послідовності, що давали значення проекцій швидкості чергових молекул, з якими вона зіштовхується. Вони були отримані з нормальної послідовності, середнє значення якої дорівнювало нулю, а стандартне відхилення s = kT / m, де k – стала Больцмана, Т – температура, m – маса молекули.

Складні системи і процеси № 2, Рис. 5. Залежність значення 2-тесту від величини х1 при використанні трикутного відображення Цю послідовність будували одним із описаних вище методів, використовуючи рівномірні випадкові послідовності, що містили 30000 елементів і мали значення імовірності р за результатами 2-тесту понад 0,9. Отримана послідовність була нормальною з імовірністю 0,87 і відповідала заданому закону розподілу з імовірністю 0,50. Її було розділено на три рівних частини, які й використовували як проекції швидкостей чергових молекул.

При моделюванні припускали, що відстань, яку молекула проходить між зіткненнями, 0,дорівнює середній довжині вільного пробігу =, де d – діаметр молекули, а n – d2n концентрація молекул. Час між і-м та і+1 зіткненнями розраховували як ti = / v2 + v2 + v2. Як чергові значення проекцій швидкості молекули, за якою велося xi yi zi спостереження, брали значення відповідних проекцій для молекули, що зіштовхується з нею. Чергові значення її координат розраховували за формулами рівномірного руху:

xi = xi-1 + vx i-1ti; yi = yi-1 + vy i-1ti; zi = zi-1 + vz i-1ti. Такий алгоритм можна вважати занадто спрощеним для моделювання випадкових блукань молекули, але він є достатнім для визначення якості вихідних випадкових послідовностей з погляду їх придатності для такого моделювання.

На рис. 6, 7 показано проекції траєкторії руху молекули у площинах xOy та xOz при використанні нормальних послідовностей, отриманих, відповідно, методами 1 та 2 із рівномірних послідовностей, одержаних за допомогою вбудованого генератора MS Excel. З наведених даних видно, що істотний вплив на результати моделювання випадкових блукань виявляє корельованість елементів отримуваних послідовностей, яка призводить до систематичного відхилення модельованого процесу від істинної траєкторії і появи досить довгих ділянок, на котрих виявляється переважний напрямок руху молекули. При цьому результати, отримані при побудові нормальних послідовностей методом відбору, є дещо кращими з погляду відтворення істинного характеру руху молекули при випадкових блуканнях. Тому для інших способів отримання рівномірних послідовностей їх перетворення до нормальних здійснювали саме за методом відбору.

Складні системи і процеси № 2, y x Рис. 6. Проекції траєкторії руху молекули у площинах xOy та xOz при використанні нормальних послідовностей, отриманих методом відбору Рис. 7. Проекції траєкторії руху молекули у площинах xOy та xOz при використанні нормальних послідовностей, отриманих методом підсумовування На рис. 8 наведено траєкторії руху молекули, отримані при застосуванні методу остач для побудови рівномірних послідовностей і методу відбору – для побудови нормальних послідовностей Рис. 8. Проекції траєкторії руху молекули у площинах xOy та xOz при використанні рівномірних послідовностей, отриманих методом остач У цьому разі траєкторія руху є дещо ближчою до очікуваної при випадкових блуканнях. Крім того, на відміну від попередніх випадків, вдалося отримати рівномірні послідовності, для яких значення імовірності р 2-тесту було практично рівним одиниці, а для побудованої нормальної послідовності воно дорівнювало 0,91 при її порівнянні з послідовністю, що мала заданий закон розподілу.

На рис. 9 наведено траєкторії руху молекули, отримані при застосуванні трикутного перетворення для побудови рівномірних послідовностей і методу відбору – для побудови нормальних послідовностей. Для вихідних рівномірних послідовностей значення імовірності р 2-тесту перевищувало 0,97, а побудована нормальна послідовність була нормаль Складні системи і процеси № 2, ною з імовірністю 0,86 і відповідала заданому закону розподілу з імовірністю 0,41. У цьому разі траєкторія руху є більш далекою від очікуваної при випадкових блуканнях, ніж у попередньому випадку.

Рис. 9. Проекції траєкторії руху молекули у площинах xOy та xOz при використанні рівномірних послідовностей, отриманих за допомогою трикутного перетворення Висновки Проведено порівняльний аналіз методів побудови випадкових послідовностей при моделюванні випадкових блукань молекули ідеального газу. Показано, що з розглянутих методів істинний характер траєкторії руху найкраще відтворює алгоритм, який використовує метод остач для побудови рівномірної випадкової послідовності, і метод відбору – для побудови послідовностей з нормальним законом розподілу. При цьому в усіх випадках спостерігаються досить довгі ділянки, на яких рух молекули має постійний напрямок переважного руху, що не відповідає закономірностям руху молекул при їх вільних блуканнях. Це може бути наслідком корельованості елементів одержуваних послідовностей.

Література 1. Бахрушин В.Є. Математичне моделювання. – Запоріжжя: ГУ “ЗІДМУ”, 2004. – 140 с.

2. Гайдышев И. Анализ и обработка данных. – С.Пб.: Питер, 2001. – 752 с.

3. Брандт З. Анализ данных: Статистические и вычислительные методы для научных работников и инженеров. – М.: Мир, 2003. – 686 с.

4. Кириченко Л.О., Гавриш О.Л. Исследование распределений последовательностей псевдослучайных чисел, полученных с помощью хаотических отображений // Дні науки:

Зб. тез доповідей: В 3т. / Гуманітарний університет „ЗІДМУ”, 27-28 жовтня 2005; Ред. кол.

В. М. Огаренко та ін. – Запоріжжя: ГУ "ЗІДМУ", 2005. – Т. 1. – С. 298–299.

Інформація Інформація Новиков О.М., Грайворонський М.В. Захист інформації в комп’ютерних системах і мережах. – Київ: БХВ, 2005.

Викладено сучасні погляди на проблеми захисту інформації у комп’ютерних системах та мережах і запропоновано підходи до їх розв’язання. У підручнику докладно розглянуто питання проектування, побудови й супроводження захищених систем, міжнародні нормативні документи, що регламентують діяльність у цій сфері і діють в Україні та за її межами, а також особливості захисту на рівні операційних систем. Велику увагу приділено питанням захисту інформації в локальних і глобальних комп’ютерних мережах.




© 2011 www.dissers.ru - «Бесплатная электронная библиотека»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.