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

Материал из Алговики
Перейти к навигации Перейти к поиску
Строка 4: Строка 4:
  
 
'''1.2 Математическое описание алгоритма'''
 
'''1.2 Математическое описание алгоритма'''
 +
 +
Пусть <math>Н_N</math> - матрица Адамара порядка <math>N</math> и <math>-Н_N</math> - матрица с противоположными элементами. Тогда матрица <math>H_{2N}</math> получается следующим образом:
 +
<math>H_{2N} =
 +
\begin{pmatrix} H_N & H_N \\ H_N & -H_N \end{pmatrix}
  
 
'''1.3 Вычислительное ядро алгоритма'''
 
'''1.3 Вычислительное ядро алгоритма'''
Строка 17: Строка 21:
 
В описанном  виде алгоритм представляет из себя примитивное дублирование элементов матрицы, полученной на предыдущем этапе, в пустующие блоки новой матрицы.
 
В описанном  виде алгоритм представляет из себя примитивное дублирование элементов матрицы, полученной на предыдущем этапе, в пустующие блоки новой матрицы.
  
−
Сначала заполняется правый верхний блок матрицы <math>h</math>
+
Сначала заполняется правый верхний блок матрицы <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(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}</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>.
+
<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 Последовательная сложность алгоритма'''
 
'''1.6 Последовательная сложность алгоритма'''
  
−
Для заполнения трех пустых блоков равного размера матрицы <math>h</math> размера <math>N\times N</math> необходимо <math>\frac{3N^2}{4}</math>. Из чего можно сделать вывод, что рекурсивный метод построения матрицы Адамара является алгоритмом с ''квадратичной сложностью''.
+
Для заполнения трех пустых блоков равного размера матрицы <math>H</math> размера <math>N\times N</math> необходимо <math>\frac{3N^2}{4}</math>. Из чего можно сделать вывод, что рекурсивный метод построения матрицы Адамара является алгоритмом с ''квадратичной сложностью''.
  
 
'''1.7 Информационный граф'''
 
'''1.7 Информационный граф'''

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

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

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

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

Пусть [math]Н_N[/math] - матрица Адамара порядка [math]N[/math] и [math]-Н_N[/math] - матрица с противоположными элементами. Тогда матрица [math]H_{2N}[/math] получается следующим образом: [math]H_{2N} = \begin{pmatrix} H_N & H_N \\ H_N & -H_N \end{pmatrix} '''1.3 Вычислительное ядро алгоритма''' Вычислительное ядро рекурсивного алгоритма состоит из \lt math\gt \;\frac{N^2}{2}\;[/math] переносов значений в повторяющиеся блоки матрицы и [math]\frac{N^2}{4}[/math] переносов со сменой знака (умножением на [math]-1[/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]\frac{3N^2}{4}[/math]. Из чего можно сделать вывод, что рекурсивный метод построения матрицы Адамара является алгоритмом с квадратичной сложностью.

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

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

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

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

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

Источник — https://algowiki-project.org/w/ru/index.php?title=Участник:Маркова_Екатерина/Построение_матрицы_Адамара&oldid=6203