Участник:Маркова Екатерина/Построение матрицы Адамара: различия между версиями
Katemeron (обсуждение | вклад) |
Katemeron (обсуждение | вклад) |
||
| Строка 6: | Строка 6: | ||
Пусть <math>H_N</math> --- матрица Адамара порядка <math>N</math> и <math>-H_N</math> --- матрица с противоположными элементами. Тогда матрица <math>H_{2N}</math> получается следующим образом: | Пусть <math>H_N</math> --- матрица Адамара порядка <math>N</math> и <math>-H_N</math> --- матрица с противоположными элементами. Тогда матрица <math>H_{2N}</math> получается следующим образом: | ||
| − | <math>H_{2N} = | + | <math>H_{2N} = \begin{bmatrix} |
| − | \begin{ | + | 1 & 0 \\ |
| + | 0 & 1 | ||
| + | \end{bmatrix} | ||
| + | </math> | ||
'''1.3 Вычислительное ядро алгоритма''' | '''1.3 Вычислительное ядро алгоритма''' | ||
Версия 01:18, 13 октября 2016
1 Свойства и структура алгоритма
1.1 Общее описание алгоритма
1.2 Математическое описание алгоритма
Пусть [math]H_N[/math] --- матрица Адамара порядка [math]N[/math] и [math]-H_N[/math] --- матрица с противоположными элементами. Тогда матрица [math]H_{2N}[/math] получается следующим образом: [math]H_{2N} = \begin{bmatrix} 1 & 0 \\ 0 & 1 \end{bmatrix} [/math]
1.3 Вычислительное ядро алгоритма
Вычислительное ядро рекурсивного алгоритма состоит из [math]\;\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 Свойства алгоритма
