Участник:Маркова Екатерина/Построение матрицы Адамара: различия между версиями
Katemeron (обсуждение | вклад) |
Katemeron (обсуждение | вклад) |
||
| Строка 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> | Сначала заполняется правый верхний блок матрицы <math>H</math> | ||
<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> | <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> | <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> | Для заполнения трех пустых блоков равного размера матрицы <math>H</math> размера <math>N\times N</math> необходимо <math>\frac{3N^2}{4}</math>. Из чего можно сделать вывод, что рекурсивный метод построения матрицы Адамара является алгоритмом с ''квадратичной сложностью''. | ||
'''1.7 Информационный граф''' | '''1.7 Информационный граф''' | ||
Версия от 22:13, 12 октября 2016
Свойства и структура алгоритма
1.1 Общее описание алгоритма
1.2 Математическое описание алгоритма
Пусть [math]\displaystyle{ Н_N }[/math] - матрица Адамара порядка [math]\displaystyle{ N }[/math] и [math]\displaystyle{ -Н_N }[/math] - матрица с противоположными элементами. Тогда матрица [math]\displaystyle{ H_{2N} }[/math] получается следующим образом: [math]\displaystyle{ 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]\displaystyle{ \frac{N^2}{4} }[/math] переносов со сменой знака (умножением на [math]\displaystyle{ -1 }[/math]).
1.4 Макроструктура алгоритма
Алгоритм не использует в качестве составных частей другие алгоритмы. Как это было описано в вычислительном ядре, в пустые блоки дублируются со сменой или без смены знака значения первого блока матрицы.
1.5 Схема реализации последовательного алгоритма
В описанном виде алгоритм представляет из себя примитивное дублирование элементов матрицы, полученной на предыдущем этапе, в пустующие блоки новой матрицы.
Сначала заполняется правый верхний блок матрицы [math]\displaystyle{ H }[/math]
[math]\displaystyle{ H_{ij} = H_{i(j - \frac{N}{2})} }[/math], где [math]\displaystyle{ i = 1..\frac{N}{2} }[/math], [math]\displaystyle{ j = \frac{N}{2}+1..N }[/math];
затем левый нижний блок
[math]\displaystyle{ H_{ij} = H_{(i-\frac{N}{2})j} }[/math], где [math]\displaystyle{ i = \frac{N}{2}+1..N }[/math], [math]\displaystyle{ j = 1.. \frac{N}{2} }[/math].
Последним заполняется нижний правый блок матрицы
[math]\displaystyle{ H_{ij} = H_{(i-\frac{N}{2})(j-\frac{N}{2})} }[/math], где [math]\displaystyle{ i = \frac{N}{2}+1..N }[/math], [math]\displaystyle{ j = \frac{N}{2}+1..N }[/math].
1.6 Последовательная сложность алгоритма
Для заполнения трех пустых блоков равного размера матрицы [math]\displaystyle{ H }[/math] размера [math]\displaystyle{ N\times N }[/math] необходимо [math]\displaystyle{ \frac{3N^2}{4} }[/math]. Из чего можно сделать вывод, что рекурсивный метод построения матрицы Адамара является алгоритмом с квадратичной сложностью.
1.7 Информационный граф
1.8 Ресурс параллелизма алгоритма
1.9 Входные и выходные данные алгоритма
1.10 Свойства алгоритма