|
|
| Строка 1: |
Строка 1: |
| Всем привет! Здесь Кирилл Хоткин и Михаил Царев делают задание по суперкомпьютерам.
| | ___ |
| {{algorithm
| |
| | name = Сюда тоже запилим
| |
| | serial_complexity = <math>O(n^3)</math>
| |
| | pf_height = <math>O(n)</math>
| |
| | pf_width = <math>O(n^2)</math>
| |
| | input_data = <math>\frac{n (n + 1)}{2}</math>
| |
| | output_data = <math>\frac{n (n + 1)}{2}</math>
| |
| }}
| |
| | |
| Основные авторы описания: [[Участник:Frolov|А.В.Фролов]], [[Участник:VadimVV|Вад.В.Воеводин]] ([[#Описание локальности данных и вычислений|раздел 2.2]]), [[Участник:Teplov|А.М.Теплов]] (разделы [[#Масштабируемость алгоритма и его реализации|2.4]], [[#Динамические характеристики и эффективность реализации алгоритма|2.5]])
| |
| | |
| == Свойства и структура алгоритма ==
| |
| | |
| === Общее описание алгоритма ===
| |
| | |
| '''Матрица Адамара''' <math>H</math> порядка <math>n</math> представляет собой матрицу размера ''n''×''n'' из элементов <math>+1</math> и <math>-1</math>, такую, что: <math>H \cdot H^T = n \cdot E_n,</math>
| |
| где <math>E_n</math> — это единичная матрица размера ''n''×''n''.
| |
| | |
| Матрицы Адамара находят широкое применение в теории кодирования (коды, исправляющие ошибки), теории планирования многофакторных экспериментов (ортогональные блок-схемы), квантовой информатике и прочих областях.
| |
| | |
| Матрица Адамара остаётся матрицей Адамара при следующих преобразованиях:
| |
| * умножение строчки или столбца на −1;
| |
| * перестановка строчек или столбцов местами.
| |
| | |
| Матрицы Адамара, получаемые друг из друга многократным применением указанных выше преобразований называются эквивалентными.
| |
| | |
| Матрица Адамара называется нормализованной, если её первая строка и столбец состоят только из единиц.
| |
| | |
| Под матрицией Адамара <math>H_m</math> подразумевается матрица порядка <math>2^m</math>
| |
| | |
| Примерами матриц Адамара различных размеров являются следующие матрицы:
| |
| | |
| <math>H_0 = (1);</math>
| |
| | |
| <math>H_1 =
| |
| \begin{pmatrix} 1 & 1
| |
| \\1 & -1
| |
| \end{pmatrix};
| |
| </math>
| |
| | |
| <math>H_2 =
| |
| \begin{pmatrix} 1 & 1 & 1 & 1
| |
| \\1 & -1 & 1 & -1
| |
| \\1 & 1 &- 1 & -1
| |
| \\1 & -1 & -1 & 1
| |
| \end{pmatrix}.
| |
| </math>
| |
| | |
| Вообще, если <math>H_m</math> матрица Адамара порядка <math>2^m</math>, то матрица
| |
| <math>H_{m+1} =
| |
| \begin{pmatrix} H_m & H_m
| |
| \\H_m & -H_m
| |
| \end{pmatrix}
| |
| </math>
| |
| является матрицей Адамара порядка <math>2^{m+1}</math>
| |
| | |
| Кроме того, матрицу Адамара порядка <math>2^m</math> можно получить по следующей формуле <math>H^{\otimes m} = H_1 \otimes ... \otimes H_1</math>, где знак <math> \otimes </math> означает тензорное произведение.
| |
| | |
| === Математическое описание алгоритма ===
| |
| === Вычислительное ядро алгоритма ===
| |
| === Макроструктура алгоритма ===
| |
| === Схема реализации последовательного алгоритма ===
| |
| === Последовательная сложность алгоритма ===
| |
| === Информационный граф ===
| |
| === Ресурс параллелизма алгоритма ===
| |
| === Входные и выходные данные алгоритма ===
| |
| === Свойства алгоритма ===
| |
| ==Программная реализация алгоритма==
| |
| ===Особенности реализации последовательного алгоритма===
| |
| === Локальность данных и вычислений ===
| |
| === Возможные способы и особенности параллельной реализации алгоритма ===
| |
| === Масштабируемость алгоритма и его реализации ===
| |
| === Динамические характеристики и эффективность реализации алгоритма ===
| |
| === Выводы для классов архитектур ===
| |
| === Существующие реализации алгоритма ===
| |
| == Литература ==
| |