лабораторная работа2
.docxМинистерство образования и науки РФ
Федеральное государственное бюджетное образовательное учреждение высшего образования
«Омский государственный технический университет»
Кафедра «Комплексная защита информации»
Отчёт по лабораторной работе № 2
по дисциплине
«Математические модели в информационных системах»
-
Выполнил
Студент гр. ИВТм-192
Козлитин Ю.В. ______________
(подп., дата)
Проверил
Профессор каф. КЗИ
Магазев А.А ______________
(подп., дата)
Омск 2019
Ход работы
Воспользуемся методом критерия для проверки псевдослучайной последовательности, сгенерированной посредством линейного конгруэнтного генератора с параметрами (1 -3).
(1)
(2)
(3)
Формула генератора представлена в (4).
(4)
Алгоритм проверки состоит из следующих шагов:
Генерация достаточно большой (n шт) псевдослучайной последовательности (в рамках данной работы – n = 518266 ед.).
Разбиение отрезка [0, N-1] на k = 100 интервалов (N – модуль генератора).
Подсчет количества элементов, попавших в интервал .
Вычисление статистики по формуле (5), где S – номер интервала, – количество элементов последовательности, попавших в интервал S.
(5)
Сравнение с экспериментального значения V с теоретическим значением .
В пункте 5 возможны три случая. Первый случай: много больше любого в строке — гипотеза о случайности равномерного генератора не выполняется (разброс чисел слишком велик, чтобы быть случайным). Второй случай: много меньше любого в строке — гипотеза о случайности равномерного генератора не выполняется (разброс чисел слишком мал, чтобы быть случайным). Третий случай: лежит между значениями двух рядом стоящих столбцов — гипотеза о случайности равномерного генератора выполняется с вероятностью p (то есть в p случаях из 100). Следует заметить, что чем ближе получается p к значению 50%, тем лучше.
В ходе данной работы был использован генератор, полученный в ходе лабораторной работы 1 и разработана программа на языке программирования C#, удовлетворяющая алгоритму проверки методом критерия (исходный код представлен в приложении А). Результат выполнения программы представлен на рисунке 1.
Рисунок 1 – Результат работы программы
В результате было получено значение V = 0,03281. Его следует сравнить с теоретическим значением критерия, который можно получить в Excel по формуле , где p – это вероятность попадания в интервал (6), а – число степеней свободы (7).
(6)
(7)
Заключение
Исходя из полученных данных, можно сказать, что , потому мы попадаем в случай 2: разброс чисел слишком мал, чтобы быть случайным. Следовательно, гипотеза о случайности генератора не выполняется.
В данной работе был получен практический опыт применения критерия для проверки псевдослучайной последовательности, была реализована программа проверки больших последовательностей.
Приложение А Исходный код программы
using System;
using System.Collections.Generic;
using System.IO;
using System.Text;
namespace GeneratorChecker
{
public class GeneratorChecker
{
public GeneratorChecker(int a, int c, int N, int intervalCount = 100, string resultsFilename = "generated_results.csv")
{
this.N = N;
k = intervalCount;
this.resultsFilename = resultsFilename;
}
public void check()
{
List<int> numbers = getNumbers(resultsFilename);
Dictionary<int, int> amountOfNumberPerInterval = new Dictionary<int, int>();
double numberStep = N / k;
for (double i = 0; i<k; i++)
{
amountOfNumberPerInterval.Add((int)i, 0);
}
foreach(int num in numbers)
{
amountOfNumberPerInterval[(int)Math.Floor(num/numberStep)]++;
}
double cumulativeSum = 0;
int numbersCount = numbers.Count;
foreach (var interval in amountOfNumberPerInterval)
{
Console.WriteLine($"For interval [{interval.Key*numberStep};{(interval.Key+1)*numberStep - 1}] generated {interval.Value} numbers.");
cumulativeSum += Math.Pow(interval.Value - numbers.Count/k, 2)/(numbersCount / k);
}
Console.WriteLine($"V = {cumulativeSum}");
Console.ReadKey();
}
public List<int> getNumbers(string filename)
{
List<int> result = new List<int>();
foreach(string num in File.ReadAllText(filename).Split('\n'))
{
result.Add(int.Parse(num.Trim('\r')));
}
return result;
} }
}
class Program
{
static void Main(string[] args)
{
GeneratorChecker checker = new GeneratorChecker(421, 54773, 259200);
checker.check();
}