Уровень алгоритма

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

Материал из Алговики
Перейти к навигации Перейти к поиску
Строка 14: Строка 14:
  
 
=== Математическое описание алгоритма ===
 
=== Математическое описание алгоритма ===
 +
 +
Исходные данные - это порядок генерируемой матрицы Адамара <math>n</math>, удовлетворяющее следующим свойствам:
 +
 +
* <math>n>0</math>;
 +
 +
* <math>n</math> делится на 4;
 +
 +
* <math>n-1</math> - простое число.
 +
 +
Вспомогательные данные:
 +
 +
* Число <math>p=n-1</math>;
 +
* Вектор вычетов <math>R</math> (элементы <math>r_i</math>) размера <math>2p</math>. В этом векторе индексация идет от нуля, первые <math>p</math> элементов образуются следующим образом:
 +
** ыфвыв
 +
 +
Вычисляемые данные:
 +
 +
* Матрица Адамара <math>H</math> (элементы <math>h_{ij}</math>) размера <math>n \times n</math>.
 +
  
 
=== Вычислительное ядро алгоритма ===
 
=== Вычислительное ядро алгоритма ===

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


Построение матрицы Адамара
Последовательный алгоритм
Последовательная сложность [math]O(n^2)[/math]
Объём входных данных [math]1[/math]
Объём выходных данных [math]n^2[/math]
Параллельный алгоритм
Высота ярусно-параллельной формы [math]O(1)[/math]
Ширина ярусно-параллельной формы [math]O(n^2)[/math]


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

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

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

Исходные данные - это порядок генерируемой матрицы Адамара [math]n[/math], удовлетворяющее следующим свойствам:

  • [math]n\gt 0[/math];
  • [math]n[/math] делится на 4;
  • [math]n-1[/math] - простое число.

Вспомогательные данные:

  • Число [math]p=n-1[/math];
  • Вектор вычетов [math]R[/math] (элементы [math]r_i[/math]) размера [math]2p[/math]. В этом векторе индексация идет от нуля, первые [math]p[/math] элементов образуются следующим образом:
    • ыфвыв

Вычисляемые данные:

  • Матрица Адамара [math]H[/math] (элементы [math]h_{ij}[/math]) размера [math]n \times n[/math].


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

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

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

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

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

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

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

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

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

2.1 Особенности реализации последовательного алгоритма

2.2 Локальность данных и вычислений

2.3 Возможные способы и особенности параллельной реализации алгоритма

2.4 Масштабируемость алгоритма и его реализации

2.5 Динамические характеристики и эффективность реализации алгоритма

2.6 Выводы для классов архитектур

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

3 Литература