Теория алгоритмов и вычислительных процессов

 

3.  Случайные и псевдослучайные числа

Случайные и псевдослучайные  числа, числа, которые могут рассматриваться  в качестве реализации некоторой  случайной величины. Как правило, имеются в виду реализации случайной величины, равномерно распределенной на промежутке (0,1), или приближения к таким реализациям, имеющие конечное число цифр в своём представлении. При такой узкой трактовке случайное число (с. ч.) можно определить как число, составленное из случайных цифр (с. ц.). С. ц. в р-ичной системе счисления является результатом эксперимента с р равновероятными исходами (каждому из исходов соответствует одна из р цифр). Эксперименты по получению каждой с. ц. предполагаются независимыми.

  Источником с. ц.  первоначально служили результаты переписи населения и др. таблицы чисел, полученных экспериментальным путём. Первые таблицы с. ц. были составлены в 1927 в связи с нуждами математической статистики (необходимостью случайного выбора при планировании эксперимента). В дальнейшем в связи с возникновением статистических испытаний метода были созданы специальные экспериментальные устройства — датчики или генераторы с. ч., основанные в большинстве случаев на использовании шумов радиоэлектронных приборов (см. Случайных чисел датчик).

С развитием метода статистических испытаний также связано возникновение  понятия псевдослучайных чисел (п. ч.). Последние можно получить путём  вычислений по некоторой заданной формуле (алгоритму), но их свойства должны быть близки к свойствам с. ч. Наиболее распространены алгоритмы, в которых каждое следующее число вычисляется по предыдущему. Получаемые таким образом последовательности п. ч. имеют период, что существенно отличает их от последовательностей с. ч. Алгоритмы получения п. ч. ещё недостаточно исследованы, но при вычислениях по методу статистических испытаний отдаётся предпочтение п. ч., т. к. свойства последовательности п. ч. можно исследовать путём пробных вычислений, а экспериментальные устройства дают новые последовательности с. ч. при каждом их использовании.

 

 

 

 

 

 

 

 

3.  Алгоритм работы программы

Программа предназначена  для программу моделирования автономной матричной линейной последовательности (АМЛПМ) над полем GF(p), описываемой матричным рекуррентным уравнением над полем GF(p) вида:

S(I+1)=A*S(I)*B, где A и B – квадратные характеристические матрицы АМЛПМ размера nxn и mxm;

I={0,1,2,3…}

S(1);S(I) и S(I+1) – векторы начального, предыдущего и последующего состояний АМЛПМ nxm.

 Значит нам необходимо  составить блок-схему алгоритма  основного тела программы, которую потом разобьем на модули.

Значит, нам необходимо составить блок-схему алгоритма основного тела программы, которую потом разобьем на модули.

Схема алгоритма основного  модуля

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Описание схемы алгоритма основного  модуля:

1. Ввод матриц. Матрица A и B: выбирается полином из заданного множества полиномов и записывается в нулевую строку, элементы на диагонали ниже главной диагонали получают значение 1, остальные элементы нулевые.

Вектор S[0]  задан по умолчанию.

2. Значению S[I] присваиваем значение заданного исходного вектора. Переменная Н необходима для вычисления весовой функции Хэмминга. На данном шаге она сбрасывается в 0.

3. Нахождение периода  матриц A, B, S по формуле.

4-5. На каждой итерации осуществляется последовательное умножение матрицы на матрицу в соответствии с формулой: S[I+1] = A*S[I]*B, где S[0], S[I], S[I+1]– векторы начального, предыдущего и последующего состояний АМЛПМ размера nxm, а A и B – квадратные характеристические матрицы размера nxn и mxm. Количество проходов цикла, которые нужно сделать – пока текущий вектор не станет равным исходному или шаг цикла не будет равен периоду в (3).

6-7. Проверка равенства заранее определенного разряда матрицы S[I] единице (в приведенном алгоритме 1-го: S[I,0]). Если равен, то переменная H увеличивается на единицу (весовая функция Хэмминга).

8-9. Вывод результатов и выход.

 

 

 

 

 

 

 

 

 

 

 

 

 

Схема функции умножения  матриц

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Описание схемы  функции умножения матрицы на матрицу

 

5. Присвоение переменной Sum сумму произведения соответствующих элементов.

6. Присвоение полученного  значения соответствующему элементу.

 

 

 

 

 

 

4.  Описание программы

Программный продукт  является платформенно-независимым  продуктом, поэтому на любой ОС пользовательский интерфейс будет выглядеть следующим образом:

- выбор степени полинома;

- выбор показательно степени  полинома;

Период матрицы(A, B, S)- подсчитанный период матриц A,B,S;

Вес Хемминга- подсчитанный вес Хемминга;

 - кнопка для расчёта состояния АМЛПМ и ВКФ;

 – кнопка, по нажатии на которую строится график вычисленной ВКФ.

 

 

 

 

 

 

 

 

Окно с графиком выглядит следующим образом:

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

5. Описание и обоснование выбора состава технических средств

В данном проекте используется язык программирования Delphi (Object Pascal). Конечный продукт, написанный на этом языке, является платформенно-независимым. Кроме этого, данный язык программирования обладает большим количеством различных технологий, что немаловажно при проектировании сложных систем.

Delphi является одним из самых популярных языков программирования. Наиболее существенный отрыв Delphi от ближайших аналогов состоит в действительно быстрой разработке приложений, обладающих сложным пользовательским интерфейсом, особенно имеющим сильные взаимосвязи между элементами управления, расположенными в окнах программы. Также Delphi предлагает довольно мощный набор компонентов для работы с базами данных.. Существует несколько реализаций языка Delphi — как бесплатных, так и коммерческих. Их производят Проект GNU, Microsoft и Embarcadero (Borland).

 

 

 

 

 

 

 

 

 

 

 

 

 

6.  Результаты работы программы

Входными данными в работе являются квадратные характеристические матрицы заданного размера (Рисунок 6.1.) и матрица начального состояния(Рисунок 6.2.).

Рисунок 6.1. Квадратная характеристическая матрица А

 

Рисунок 6.2. Матрица начального состояния S

 

Рисунок 6.3. Результат работы программы

Для последовательностей  от двух взаимно-простых полиномов, график ВКФ выглядит следующим образом:

Рисунок 6.4. График ВКФ

 

 

7. Выводы

В процессе выполнения курсового  проекта была спроектирована и реализована  программа моделирования АМЛПМ над полем GF(2). Программа осуществляет вычисление последовательности состояний АМЛПМ, периода матриц A,B и S, формирует последовательности состояний каждого заданного разряда матрицы S, а также вычисляет весовые функции Хэмминга этих последовательностей. При проверке модели на тестовых примерах, все работало корректно.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

8. Литература

1. Иванов М.А., Чугунков И.В. Теория, применение и оценка качества генераторов псевдослучайных последовательностей / М.: КУДИЦ-ОБРАЗ, 2003, 204с.
2. Ковтун В.Ю. Генераторы  случайных  и псевдослучайных последовательностей. Статистические  тесты. Криптографически  безопасные генераторы  псевдослучайных последовательностей. Курс лекций. 27.09.2009 – Версия 0.1
3. Лифшиц Ю. Псевдослучайные генераторы - лекция 9.
4. Сухинин Б.М. - Разработка генераторов псевдослучайных двоичных последовательностей на основе клеточных автоматов. Статья. 2010.
5. http://ru.wikipedia.org/wiki/Псевдослучайная_последовательность.
6. http://ru.wikipedia.org/wiki/Псевдослучайная_двоичная_последовательность.
7. http://www.osp.ru/text/print/302/141475.html.
8. http://cryptolog.ru/?Psevdosluchainye_posledovatelmznosti.

 

Приложение  А

База данных неприводимых полиномов

 

<n=5>

1 45E

3 75G

5 67H

</n=5>

 

<n=6>

1 103F

3 127B

5 147H

7 111A

9 013

11 155E

21 007

</n=6>

 

<n=7>

1 211E

3 217E

5 235E

7 367H

9 277E

11 325G

13 203F

19 313H

21 345G

</n=7>

 

<n=8>

1 433E

3 567B

5 763D

7 551E

9 675C

11 747H

13 453F

15 727D

17 023

19 545E

21 613D

23 543F

25 433B

27 477B

37 537F

43 703H

45 471A

51 037

85 007

</n=8>

 

<n=9>

1 1021E

3 1131E

5 1461G

7 1321A

9 1423G

</n=9>

 

<n=10>

1 2011E

3 2017B

5 2415E

7 3771G

9 2257B

</n=10>

 

<n=11>

1 4005E

3 4445E

5 4215E

7 4055E

9 6015G

</n=11>

 

 

<n=12>

1 10123F

3 12133B

5 10113A

7 12153B

9 11765A

</n=12>

 

<n=13>

1 20033F

3 23261E

5 24623F

7 23517F

9 30741G

</n=13>

 

<n=14>

1 42103F

3 40547B

5 43333E

7 51761E

9 54055A

11 40503F

13 77141G

</n=14>

 

 

 

 

 

 

 

 

 

 

Приложение Б

Текст программы

unit fm_kursovoy;

 

interface

 

uses

  Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,

  Dialogs, ExtCtrls, DBGridEhGrouping, GridsEh, DBGridEh, DBGridEhVk, polinom, Generics.Collections, StdCtrls,

  MemTableDataEh, Db, MemTableEh, DateVk, Matrixes, VirtualTrees, fm_chart, math;

 

type

  TFmKursovoy = class(TForm)

    Panel1: TPanel;

    Panel2: TPanel;

    Splitter2: TSplitter;

    ComboBoxDegreeN: TComboBox;

    ComboBoxPN: TComboBox;

    ComboBoxDegreeM: TComboBox;

    ComboBoxPM: TComboBox;

    Label1: TLabel;

    Label2: TLabel;

    Label3: TLabel;

    Label4: TLabel;

    Button1: TButton;

    GroupBox1: TGroupBox;

    GroupBox2: TGroupBox;

    Splitter1: TSplitter;

    GroupBox3: TGroupBox;

    VirtualStringTree1: TVirtualStringTree;

    VirtualStringTree2: TVirtualStringTree;

    VirtualStringTree3: TVirtualStringTree;

    GroupBox4: TGroupBox;

    Memo1: TMemo;

    Button2: TButton;

    procedure FormCreate(Sender: TObject);

    procedure ComboBoxDegreeNChange(Sender: TObject);

    procedure ComboBoxDegreeMChange(Sender: TObject);

    procedure Button1Click(Sender: TObject);

   procedure FormResize(Sender: TObject);

    procedure VirtualStringTree1GetText(Sender: TBaseVirtualTree; Node: PVirtualNode; Column: TColumnIndex;

      TextType: TVSTTextType; var CellText: string);

    procedure FormDestroy(Sender: TObject);

    procedure Button2Click(Sender: TObject);

    procedure ComboBoxPNChange(Sender: TObject);

    procedure ComboBoxPMChange(Sender: TObject);

  private

    { Private declarations }

    FPolinomList: TList<TPolinom>;

    FMatList: TList<TMatrix>;

    MatA, MatB, MatS: TMatrix;

    Buf1, Buf2: TMatrix;

    Mat2: TMatrix;

    Fnok: Int64;

    afv: TList<Double> ;

    procedure CalcList;

    function CalcHeming(aMat:tMatrix):Integer;

    procedure CreateMat2;

    procedure Create_AFX(var amat:TMatrix;anok: Integer);

    procedure CreateAfv;

    function GetPeriodA(n,j, nType: Integer):Integer;

    function GetTypeA(const s:String):Integer;

    procedure InitComboBox;

    procedure InitMatr(aType: Integer);

    procedure LoadPolinoms;

    function Nod(a,b:Integer):Integer;

    function FuncNok(a,b:Integer):Int64;

    procedure ReInit;

    procedure ShowMatrix(aVt:TVirtualStringTree; aMatrix:TMatrix);

    procedure WriteMatrix(amatrix:tMatrix);

    procedure WriteMemo;

  public

    { Public declarations }

    property PolinomList: TList<TPolinom>read FPolinomList;

  end;

 

var

  FmKursovoy: TFmKursovoy;

 

implementation

 

{$R *.dfm}

 

procedure TFmKursovoy.Button1Click(Sender: TObject);

begin

//  ReInit;

  Memo1.Clear;

  Application.ProcessMessages;

  CalcList;

end;

 

procedure TFmKursovoy.ComboBoxDegreeNChange(Sender: TObject);