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

Материал из Алговики
Перейти к навигации Перейти к поиску
Строка 15: Строка 15:
 
'''1.5 Схема реализации последовательного алгоритма'''
 
'''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>
 
'''1.6 Последовательная сложность алгоритма'''
 
'''1.6 Последовательная сложность алгоритма'''
  

Версия 23:20, 12 октября 2016

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

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

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

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] 1.6 Последовательная сложность алгоритма

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

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

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

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

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