Участник:Маркова Екатерина/Построение матрицы Адамара: различия между версиями

Материал из Алговики
Перейти к навигации Перейти к поиску
Строка 1: Строка 1:
 
Основной автор статьи: Маркова Е.А. 615 гр.
 
Основной автор статьи: Маркова Е.А. 615 гр.
 
== Свойства и структура алгоритма ==
 
== Свойства и структура алгоритма ==
===1.1 Общее описание алгоритма===
+
=== Общее описание алгоритма===
  
 
Матрица Адамара <math>H</math> - это квадратная матрица размера <math>N\times N</math>, составленная из чисел <math>1</math> и <math>-1</math>, столбцы которой ортогональны, так что справедливо соотношение:
 
Матрица Адамара <math>H</math> - это квадратная матрица размера <math>N\times N</math>, составленная из чисел <math>1</math> и <math>-1</math>, столбцы которой ортогональны, так что справедливо соотношение:
Строка 9: Строка 9:
 
где <math>E_n</math> - это единичная матрица размера <math>n</math>. Матрицы Адамара применяются в различных областях, включая комбинаторику, численный анализ, обработку сигналов.
 
где <math>E_n</math> - это единичная матрица размера <math>n</math>. Матрицы Адамара применяются в различных областях, включая комбинаторику, численный анализ, обработку сигналов.
  
===1.2 Математическое описание алгоритма ===
+
=== Математическое описание алгоритма ===
  
 
Пусть <math>H_N</math> <math>-</math> матрица Адамара порядка <math>N</math> и <math>-H_N</math> <math>-</math> матрица с противоположными элементами. Тогда матрица <math>H_{2N}</math> получается следующим образом:
 
Пусть <math>H_N</math> <math>-</math> матрица Адамара порядка <math>N</math> и <math>-H_N</math> <math>-</math> матрица с противоположными элементами. Тогда матрица <math>H_{2N}</math> получается следующим образом:
Строка 18: Строка 18:
 
</math>
 
</math>
  
=== 1.3 Вычислительное ядро алгоритма ===
+
=== Вычислительное ядро алгоритма ===
  
 
Вычислительное ядро рекурсивного алгоритма состоит из  <math>\;N^2\;</math>  присвоений значений и .
 
Вычислительное ядро рекурсивного алгоритма состоит из  <math>\;N^2\;</math>  присвоений значений и .
  
=== 1.4 Макроструктура алгоритма ===
+
=== Макроструктура алгоритма ===
  
 
Алгоритм не использует в качестве составных частей другие алгоритмы. Как это было описано в вычислительном ядре, в пустые блоки дублируются со сменой или без смены знака значения первого блока матрицы.  
 
Алгоритм не использует в качестве составных частей другие алгоритмы. Как это было описано в вычислительном ядре, в пустые блоки дублируются со сменой или без смены знака значения первого блока матрицы.  
  
===1.5 Схема реализации последовательного алгоритма===
+
=== Схема реализации последовательного алгоритма===
  
 
В описанном  виде алгоритм представляет из себя примитивное дублирование элементов матрицы, полученной на предыдущем этапе, в пустующие блоки новой матрицы.
 
В описанном  виде алгоритм представляет из себя примитивное дублирование элементов матрицы, полученной на предыдущем этапе, в пустующие блоки новой матрицы.
Строка 43: Строка 43:
  
  
===1.6 Последовательная сложность алгоритма===
+
=== Последовательная сложность алгоритма===
  
 
Для заполнения  матрицы <math>H</math> размера <math>N\times N</math> необходимо <math>\;N^2\;</math>  присвоений значений. Из чего можно сделать вывод, что рекурсивный метод построения матрицы Адамара является алгоритмом с ''квадратичной сложностью''.
 
Для заполнения  матрицы <math>H</math> размера <math>N\times N</math> необходимо <math>\;N^2\;</math>  присвоений значений. Из чего можно сделать вывод, что рекурсивный метод построения матрицы Адамара является алгоритмом с ''квадратичной сложностью''.
  
===1.7 Информационный граф===
+
===Информационный граф===
  
 
Зависимость данных для матрицы размерностью <math>4*4</math> можно увидеть на рис.1.
 
Зависимость данных для матрицы размерностью <math>4*4</math> можно увидеть на рис.1.
Строка 53: Строка 53:
 
[[Файл:Pic_hadamard.png|border|500px|Some text]]
 
[[Файл:Pic_hadamard.png|border|500px|Some text]]
  
===1.8 Ресурс параллелизма алгоритма===
+
=== Ресурс параллелизма алгоритма===
  
 
Логически алгоритм можно разделить на три части, которые на каждом шаге выполняются независимо.
 
Логически алгоритм можно разделить на три части, которые на каждом шаге выполняются независимо.
 
Внутри каждой части происходит <math>2^{2N}-2^{2(N-1)}</math> независимых присвоений, где <math>N</math> - номер шага алгоритма, причем размерность матрицы на шаге <math>N</math> равна <math>2^N</math>. При этом необходимо ждать завершения предыдущего шага, то есть необходимы синхронизирующие блокировки.
 
Внутри каждой части происходит <math>2^{2N}-2^{2(N-1)}</math> независимых присвоений, где <math>N</math> - номер шага алгоритма, причем размерность матрицы на шаге <math>N</math> равна <math>2^N</math>. При этом необходимо ждать завершения предыдущего шага, то есть необходимы синхронизирующие блокировки.
  
===1.9 Входные и выходные данные алгоритма===
+
===Входные и выходные данные алгоритма===
  
 
Входные данные: <math>N</math> - размерность матрицы.
 
Входные данные: <math>N</math> - размерность матрицы.
Строка 66: Строка 66:
 
Объем выходных данных: <math> N^2</math>.
 
Объем выходных данных: <math> N^2</math>.
  
===1.10 Свойства алгоритма===
+
===Свойства алгоритма===
  
 
Алгоритм полностью детерминирован.
 
Алгоритм полностью детерминирован.
Строка 72: Строка 72:
 
== Программная реализация алгоритма ==
 
== Программная реализация алгоритма ==
  
===2.7 Существующие реализации алгоритма===
+
=== Существующие реализации алгоритма===
  
 
Реализация ''MATLAB''
 
Реализация ''MATLAB''

Версия 16:01, 28 октября 2016

Основной автор статьи: Маркова Е.А. 615 гр.

1 Свойства и структура алгоритма

1.1 Общее описание алгоритма

Матрица Адамара [math]H[/math] - это квадратная матрица размера [math]N\times N[/math], составленная из чисел [math]1[/math] и [math]-1[/math], столбцы которой ортогональны, так что справедливо соотношение:

[math]H*H^T = N*E_N[/math],

где [math]E_n[/math] - это единичная матрица размера [math]n[/math]. Матрицы Адамара применяются в различных областях, включая комбинаторику, численный анализ, обработку сигналов.

1.2 Математическое описание алгоритма

Пусть [math]H_N[/math] [math]-[/math] матрица Адамара порядка [math]N[/math] и [math]-H_N[/math] [math]-[/math] матрица с противоположными элементами. Тогда матрица [math]H_{2N}[/math] получается следующим образом: [math]H_{2N} = \begin{bmatrix} H_N & H_N \\ H_N & -H_N \end{bmatrix} [/math]

1.3 Вычислительное ядро алгоритма

Вычислительное ядро рекурсивного алгоритма состоит из [math]\;N^2\;[/math] присвоений значений и .

1.4 Макроструктура алгоритма

Алгоритм не использует в качестве составных частей другие алгоритмы. Как это было описано в вычислительном ядре, в пустые блоки дублируются со сменой или без смены знака значения первого блока матрицы.

1.5 Схема реализации последовательного алгоритма

В описанном виде алгоритм представляет из себя примитивное дублирование элементов матрицы, полученной на предыдущем этапе, в пустующие блоки новой матрицы.

Сначала заполняется правый верхний блок матрицы [math]H[/math]

[math]H_{ij} = H_{i(j - \frac{N}{2})}[/math], где [math]i = 1..\frac{N}{2}[/math], [math]j = \frac{N}{2}+1..N[/math];

затем левый нижний блок

[math]H_{ij} = H_{(i-\frac{N}{2})j}[/math], где [math]i = \frac{N}{2}+1..N[/math], [math]j = 1.. \frac{N}{2}[/math].

Последним заполняется нижний правый блок матрицы

[math]H_{ij} = H_{(i-\frac{N}{2})(j-\frac{N}{2})}[/math], где [math]i = \frac{N}{2}+1..N [/math], [math]j = \frac{N}{2}+1..N[/math].


1.6 Последовательная сложность алгоритма

Для заполнения матрицы [math]H[/math] размера [math]N\times N[/math] необходимо [math]\;N^2\;[/math] присвоений значений. Из чего можно сделать вывод, что рекурсивный метод построения матрицы Адамара является алгоритмом с квадратичной сложностью.

1.7 Информационный граф

Зависимость данных для матрицы размерностью [math]4*4[/math] можно увидеть на рис.1.

Some text

1.8 Ресурс параллелизма алгоритма

Логически алгоритм можно разделить на три части, которые на каждом шаге выполняются независимо. Внутри каждой части происходит [math]2^{2N}-2^{2(N-1)}[/math] независимых присвоений, где [math]N[/math] - номер шага алгоритма, причем размерность матрицы на шаге [math]N[/math] равна [math]2^N[/math]. При этом необходимо ждать завершения предыдущего шага, то есть необходимы синхронизирующие блокировки.

1.9 Входные и выходные данные алгоритма

Входные данные: [math]N[/math] - размерность матрицы.

Выходные данные: матрица размером [math]N\times N[/math].

Объем выходных данных: [math] N^2[/math].

1.10 Свойства алгоритма

Алгоритм полностью детерминирован.

2 Программная реализация алгоритма

2.1 Существующие реализации алгоритма

Реализация MATLAB [1]

Реализация PYTHON [2]

Реализация WOLFRAM [3]

На языке Java реализован класс Hadamard не входящий в стандарт языка. С кодом можно ознакомиться по ссылке[4].

3 Литература

1. Мак-Вильямс Ф., Слоэн Н. — "Теория кодов, исправляющих ошибки" (1979)

2. Кронберг, Ю.И. Ожигов, А.Ю. Чернявский — "Алгебраический аппарат квантовой информатики 2"

3. М. Н. Аршинов, Л. Е. Садовский — "Коды и математика" (1983)