Алговики - Вклад [ru]

Обсуждение участника:VolkovNikita94

2020-08-10T18:50:30Z

VolkovNikita94: /* Параметрика Пакуля */

<tabs>

<tab name="Специальный_пример_1_n4">
{{#widget:Algoviewer
|url=XML_task_001/Example_001.html
|width=1200
|height=800
|border=1
}}
<br>
<div class="collapser mw-collapsible mw-collapsed" style="width:1200px; overflow:auto;">
C++ реализация:
<div class="mw-collapsible-content">
<source lang = "c++">
for (int i = 1; i <= n; ++i) {
C[i] = C[i - 2];
}
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n; ++j) {
B[i][j] = B[i][j] + C[i];
}
}
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n; ++j) {
for (int k = 1; k <= n; ++k) {
A[i][j][k] = A[i][j][k] + A[i - 1][j][1];
}
}
}
</source>
</div>
</div>
<div class="collapser mw-collapsible mw-collapsed" style="width:1200px; overflow:auto;">
Новая разметка:
<div class="mw-collapsible-content">
<source lang = "xml">
<algo>
<params>
<param name = "N" type = "int"></param>
</params>
<block id = "0" dims = "1">
<arg name = "i" val = "1..N"></arg>
<vertex condition = "" type = "0">
<in src = “i – 2”></in>
</vertex>
</block>
<block id = "1" dims = "2">
<arg name = "i" val = "1..N"></arg>
<arg name = "j" val = "1..N"></arg>
<vertex condition = "" type = "0">
<in bsrc = "0" src = "i"></in>
</vertex>
</block>
<block id = "2" dims = "3">
<arg name = "i" val = "1..N"></arg>
<arg name = "j" val = "1..N"></arg>
<arg name = "k" val = "1..N"></arg>
<vertex condition = "(k == 1) || (i == 1)" type = "0">
</vertex>
<vertex condition = "(k > 1) && (i > 1)" type = "0">
<in src = “1, j, 1”></in>
</vertex>
</block>
</algo>
</source>
</div>
</div>
</tab>

<tab name="Специальный_пример_1_n8">
{{#widget:Algoviewer
|url=XML_task_001_n8/Example_001.html
|width=1200
|height=800
|border=1
}}
<br>
<div class="collapser mw-collapsible mw-collapsed" style="width:1200px; overflow:auto;">
C++ реализация:
<div class="mw-collapsible-content">
<source lang = "c++">
for (int i = 1; i <= n; ++i) {
C[i] = C[i - 2];
}
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n; ++j) {
B[i][j] = B[i][j] + C[i];
}
}
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n; ++j) {
for (int k = 1; k <= n; ++k) {
A[i][j][k] = A[i][j][k] + A[i - 1][j][1];
}
}
}
</source>
</div>
</div>
</tab>

<tab name="Специальный_пример_2_n4">
{{#widget:Algoviewer
|url=XML_task_002/Example_001.html
|width=1200
|height=800
|border=1
}}
<br>
<div class="collapser mw-collapsible mw-collapsed" style="width:1200px; overflow:auto;">
C++ реализация:
<div class="mw-collapsible-content">
<source lang = "c++">
for (int i = 1; i <= n; ++i) {
C[i] = C[i] * e;
}
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n; ++j) {
B[i][j] = B[i - 1][j - 1];
}
}
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n; ++j) {
for (int k = 1; k <= n; ++k) {
A[i][j][k] = A[i][j][k] + A[i][j - 1][k - 2];
}
A[i][j][n] = A[i][j][n] + B[i][j];
}
}
</source>
</div>
</div>
<div class="collapser mw-collapsible mw-collapsed" style="width:1200px; overflow:auto;">
Новая разметка:
<div class="mw-collapsible-content">
<source lang = "xml">
<algo>
<params>
<param name = "N" type = "int"></param>
</params>
<block id = "0" dims = "1">
<arg name = "I" val = "1..N"></arg>
<vertex condition = "" type = "1">
</vertex>
</block>
<block id = "0" dims = "2">
<arg name = "I" val = "1..N"></arg>
<arg name = "J" val = "1..N"></arg>
<vertex condition = "" type = "1">
<in src = "I - 1, J - 1"></in>
</vertex>
</block>
<block id = "2" dims = "3">
<arg name = "I" val = "1..N"></arg>
<arg name = "J" val = "1..N"></arg>
<arg name = "K" val = "1..N"></arg>
<vertex condition = "K == 1" type = "2">
<in bsrc = "1" src = "I, J"></in>
<in src = "I - 1, J, K + 2"></in>
</vertex>
<vertex condition = "K > 1" type = "1">
<in src = "I - 1, J, K + 2"></in>
</vertex>
</block>
</algo>
</source>
</div>
</div>
</tab>

<tab name="Специальный_пример_2_n8">
{{#widget:Algoviewer
|url=XML_task_002_n8/Example_001.html
|width=1200
|height=800
|border=1
}}
<br>
<div class="collapser mw-collapsible mw-collapsed" style="width:1200px; overflow:auto;">
C++ реализация:
<div class="mw-collapsible-content">
<source lang = "c++">
for (int i = 1; i <= n; ++i) {
C[i] = C[i] * e;
}
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n; ++j) {
B[i][j] = B[i - 1][j - 1];
}
}
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n; ++j) {
for (int k = 1; k <= n; ++k) {
A[i][j][k] = A[i][j][k] + A[i][j - 1][k - 2];
}
A[i][j][n] = A[i][j][n] + B[i][j];
}
}
</source>
</div>
</div>
</tab>

<tab name="Преобразование_фурье">
{{#widget:Algoviewer
|url=XML_Fourier/Example_001.html
|width=1200
|height=800
|border=1
}}
<br>
<div class="collapser mw-collapsible mw-collapsed" style="width:1200px; overflow:auto;">
Новая разметка:
<div class="mw-collapsible-content">
<source lang = "xml">
<algo>
<params>
<param name = "N" type = "int" value = "3"></param>
</params>
<block id = "0" dims = "2">
<arg name = "I" val = "1..N"></arg>
<arg name = "J" val = "1..2^N"></arg>
<vertex condition = "(J - 1) % (2^I) < 2^(I - 1)" type = "1">
<in src = "I - 1, J"></in>
<in src = "I - 1, J + 2^(I -1)"></in>
</vertex>
<vertex condition = "(J - 1) % (2^I) >= 2^(I - 1)" type = "2">
<in src = "I - 1, J"></in>
<in src = "I - 1, J - 2^(I - 1)"></in>
</vertex>
</block>
</algo>
</source>
</div>
</div>
</tab>

</tabs>

== Тестовые варианты 2020 ==

<tabs>

<tab name="Вариант_01">
{{#widget:Algoviewer
|url=Variant_01/Variant_01.html
|width=1200
|height=800
|border=1
}}
<br>
<div class="collapser mw-collapsible mw-collapsed" style="width:1200px; overflow:auto;">
Новая разметка:
<div class="mw-collapsible-content">
<source lang = "xml">
<algo>
<params>
<param name = "N" type = "int"></param>
<param name = "M" type = "int"></param>
</params>
<block id = "0" dims = "1">
<arg name = "i" val = "1..N"></arg>
<vertex condition = "" type = "1">
<in src = "i - 2"></in>
</vertex>
</block>
<block id = "1" dims = "2">
<arg name = "i" val = "1..N"></arg>
<arg name = "j" val = "1..M"></arg>
<vertex condition = "" type = "1">
<in src = "i - 1, j - 1"></in>
<in bsrc = "0" src = "i"></in>
</vertex>
</block>
<block id = "2" dims = "3">
<arg name = "i" val = "1..N"></arg>
<arg name = "j" val = "1..M"></arg>
<arg name = "k" val = "1..N-1"></arg>
<vertex condition = "(j == 1) and (k == 1)" type = "1">
<in bsrc = "1" src = "i, M"></in>
</vertex>
<vertex condition = "(j > 1) or (k > 1)" type = "1">
<in src = "i - 1, j, 1"></in>
</vertex>
</block>
</algo>
</source>
</div>
</div>
</tab>

<tab name="Вариант_02">
{{#widget:Algoviewer
|url=Variant_02/Variant_02.html
|width=1200
|height=800
|border=1
}}
<br>
<div class="collapser mw-collapsible mw-collapsed" style="width:1200px; overflow:auto;">
Новая разметка:
<div class="mw-collapsible-content">
<source lang = "xml">
<algo>
<params>
<param name = "N" type = "int"></param>
<param name = "M" type = "int"></param>
</params>
<block id = "0" dims = "1">
<arg name = "i" val = "1..N"></arg>
<vertex condition = "" type = "1">
<in src = "i - 1"></in>
</vertex>
</block>
<block id = "1" dims = "2">
<arg name = "i" val = "1..N"></arg>
<arg name = "j" val = "1..M"></arg>
<vertex condition = "" type = "1">
<in src = "i - 2, j"></in>
</vertex>
</block>
<block id = "2" dims = "3">
<arg name = "i" val = "1..N"></arg>
<arg name = "j" val = "1..M"></arg>
<arg name = "k" val = "1..N-1"></arg>
<vertex condition = "(j == 1) and (k == 1)" type = "1">
<in bsrc = "0" src = "i"></in>
<in bsrc = "1" src = "i, M"></in>
</vertex>
<vertex condition = "(j > 1) or (k > 1)" type = "1">
<in src = "i, j - 1, 1"></in>
</vertex>
</block>
</algo>
</source>
</div>
</div>
</tab>

<tab name="Вариант_03">
{{#widget:Algoviewer
|url=Variant_03/Variant_03.html
|width=1200
|height=800
|border=1
}}
<br>
<div class="collapser mw-collapsible mw-collapsed" style="width:1200px; overflow:auto;">
Новая разметка:
<div class="mw-collapsible-content">
<source lang = "xml">
<algo>
<params>
<param name = "N" type = "int"></param>
<param name = "M" type = "int"></param>
</params>
<block id = "0" dims = "1">
<arg name = "i" val = "1..N"></arg>
<vertex condition = "" type = "1">
</vertex>
</block>
<block id = "1" dims = "2">
<arg name = "i" val = "1..N"></arg>
<arg name = "j" val = "1..M"></arg>
<vertex condition = "" type = "1">
<in src = "i, j - 2"></in>
<in bsrc = "0" src = "i"></in>
</vertex>
</block>
<block id = "2" dims = "3">
<arg name = "i" val = "1..N"></arg>
<arg name = "j" val = "1..M"></arg>
<arg name = "k" val = "1..N-1"></arg>
<vertex condition = "(j == 1) and (k == 1)" type = "1">
<in bsrc = "1" src = "i, M"></in>
</vertex>
<vertex condition = "(j > 1) or (k > 1)" type = "1">
<in src = "i, j - 1, k"></in>
</vertex>
</block>
</algo>

</source>
</div>
</div>
</tab>

<tab name="Вариант_04">
{{#widget:Algoviewer
|url=Variant_04/Variant_04.html
|width=1200
|height=800
|border=1
}}
<br>
<div class="collapser mw-collapsible mw-collapsed" style="width:1200px; overflow:auto;">
Новая разметка:
<div class="mw-collapsible-content">
<source lang = "xml">
<algo>
<params>
<param name = "N" type = "int"></param>
<param name = "M" type = "int"></param>
</params>
<block id = "0" dims = "1">
<arg name = "i" val = "1..N"></arg>
<vertex condition = "" type = "1">
<in src = "i - 1"></in>
</vertex>
</block>
<block id = "1" dims = "2">
<arg name = "i" val = "1..N"></arg>
<arg name = "j" val = "1..M"></arg>
<vertex condition = "" type = "1">
<in src = "i - 1, j - 1"></in>
<in bsrc = "0" src = "i"></in>
</vertex>
</block>
<block id = "2" dims = "3">
<arg name = "i" val = "1..N"></arg>
<arg name = "j" val = "1..M"></arg>
<arg name = "k" val = "1..N-1"></arg>
<vertex condition = "(j == 1) and (k == 1)" type = "1">
<in bsrc = "1" src = "i, M"></in>
</vertex>
<vertex condition = "(j > 1) or (k > 1)" type = "1">
<in src = "i - 1, j, k"></in>
</vertex>
</block>
</algo>
</source>
</div>
</div>
</tab>

</tabs>

== Параметрика Пакуля ==

<tabs>

<tab name="Параметрика">
{{#widget:Algoviewer
|url=Variant_parametric/Variant_par.html
|width=1200
|height=800
|border=1
}}
<br>
<div class="collapser mw-collapsible mw-collapsed" style="width:1200px; overflow:auto;">
Новая разметка:
<div class="mw-collapsible-content">
<source lang = "xml">
<algo>
<params>
<param name = "N" type = "int"></param>
<param name = "M" type = "int"></param>
<aparam name = "p0" type = "int"></aparam>
<aparam name = "p1" type = "int"></aparam>
<aparam name = "p2" type = "int"></aparam>
<aparam name = "p3" type = "int"></aparam>
<aparam name = "p4" type = "int"></aparam>
<aparam name = "p5" type = "int"></aparam>
</params>
<block id = "0" dims = "1">
<arg name = "i" val = "1..N"></arg>
<vertex condition = "" type = "1">
<in src = "i + p0"></in>
</vertex>
</block>
<block id = "1" dims = "2">
<arg name = "i" val = "1..N"></arg>
<arg name = "j" val = "1..M"></arg>
<vertex condition = "p3 == 0" type = "1">
<in src = "i + p1, j + p2"></in>
</vertex>
<vertex condition = "p3 == 1" type = "1">
<in src = "i + p1, j + p2"></in>
<in bsrc = "0" src = "i"></in>
</vertex>
</block>
<block id = "2" dims = "3">
<arg name = "i" val = "1..N"></arg>
<arg name = "j" val = "1..M"></arg>
<arg name = "k" val = "1..N-1"></arg>
<vertex condition = "(j == 1) and (k == 1) and (p3 == 1)" type = "1">
<in bsrc = "1" src = "i, M"></in>
</vertex>
<vertex condition = "(j == 1) and (k == 1) and (p3 == 0)" type = "1">
<in bsrc = "1" src = "i, M"></in>
<in bsrc = "0" src = "i"></in>
</vertex>
<vertex condition = "((j > 1) or (k > 1)) and (p4 == 1)" type = "1">
<in src = "i - 1 * (1 - p5), j - 1 * p5, 1"></in>
</vertex>
<vertex condition = "((j > 1) or (k > 1)) and (p4 == 0)" type = "1">
<in src = "i - 1 * (1 - p5), j - 1 * p5, k"></in>
</vertex>
</block>
</algo>
</source>
</div>
</div>
</tab>

<tab name="Пакулев">
{{#widget:Algoviewer
|url=Variant_pakulev/Variant_pak.html
|width=1200
|height=800
|border=1
}}
<br>
<div class="collapser mw-collapsible mw-collapsed" style="width:1200px; overflow:auto;">
Новая разметка:
<div class="mw-collapsible-content">
<source lang = "xml">
<algo>
<params>
<param name = "N" type = "int"></param>
</params>
<block id = "0" dims = "2">
<arg name = "i" val = "1..N"></arg>
<arg name = "j" val = "1..N"></arg>
<vertex condition = "(2 * i + j) <= (N + 1)" type = "1">
</vertex>
<vertex condition = "((2 * i + j) > (N + 1)) and ((i + j) <= N)" type = "1">
<in src = "i - 1, j + 2 * (N + 1 - i - j)"></in>
</vertex>
<vertex condition = "((i + j) > N) and ((2 * i + j) <= (2 * N))" type = "1">
<in src = "i, j - 1 - 2 * ((i + j) - N - 1)"></in>
</vertex>
<vertex condition = "((2 * i + j) > (2 * N)) and ((i + j) <= (2 * N - 1))" type = "1">
<in src = "i - 1 * (2 * i + j - 2 * N), 1"></in>
</vertex>
<vertex condition = "((i + j) > (2 * N - 1))" type = "1">
</vertex>
</block>
</algo>
</source>
</div>
</div>
</tab>

</tabs>

Обсуждение участника:VolkovNikita94

2020-08-10T18:02:24Z

VolkovNikita94: /* Параметрика Пакуля */

Обсуждение участника:VolkovNikita94

2020-08-10T18:01:38Z

VolkovNikita94: /* Параметрика Пакуля */

<tabs>

<tab name="Специальный_пример_1_n4">
{{#widget:Algoviewer
|url=XML_task_001/Example_001.html
|width=1200
|height=800
|border=1
}}
<br>
<div class="collapser mw-collapsible mw-collapsed" style="width:1200px; overflow:auto;">
C++ реализация:
<div class="mw-collapsible-content">
<source lang = "c++">
for (int i = 1; i <= n; ++i) {
C[i] = C[i - 2];
}
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n; ++j) {
B[i][j] = B[i][j] + C[i];
}
}
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n; ++j) {
for (int k = 1; k <= n; ++k) {
A[i][j][k] = A[i][j][k] + A[i - 1][j][1];
}
}
}
</source>
</div>
</div>
<div class="collapser mw-collapsible mw-collapsed" style="width:1200px; overflow:auto;">
Новая разметка:
<div class="mw-collapsible-content">
<source lang = "xml">
<algo>
<params>
<param name = "N" type = "int"></param>
</params>
<block id = "0" dims = "1">
<arg name = "i" val = "1..N"></arg>
<vertex condition = "" type = "0">
<in src = “i – 2”></in>
</vertex>
</block>
<block id = "1" dims = "2">
<arg name = "i" val = "1..N"></arg>
<arg name = "j" val = "1..N"></arg>
<vertex condition = "" type = "0">
<in bsrc = "0" src = "i"></in>
</vertex>
</block>
<block id = "2" dims = "3">
<arg name = "i" val = "1..N"></arg>
<arg name = "j" val = "1..N"></arg>
<arg name = "k" val = "1..N"></arg>
<vertex condition = "(k == 1) || (i == 1)" type = "0">
</vertex>
<vertex condition = "(k > 1) && (i > 1)" type = "0">
<in src = “1, j, 1”></in>
</vertex>
</block>
</algo>
</source>
</div>
</div>
</tab>

<tab name="Специальный_пример_1_n8">
{{#widget:Algoviewer
|url=XML_task_001_n8/Example_001.html
|width=1200
|height=800
|border=1
}}
<br>
<div class="collapser mw-collapsible mw-collapsed" style="width:1200px; overflow:auto;">
C++ реализация:
<div class="mw-collapsible-content">
<source lang = "c++">
for (int i = 1; i <= n; ++i) {
C[i] = C[i - 2];
}
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n; ++j) {
B[i][j] = B[i][j] + C[i];
}
}
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n; ++j) {
for (int k = 1; k <= n; ++k) {
A[i][j][k] = A[i][j][k] + A[i - 1][j][1];
}
}
}
</source>
</div>
</div>
</tab>

<tab name="Специальный_пример_2_n4">
{{#widget:Algoviewer
|url=XML_task_002/Example_001.html
|width=1200
|height=800
|border=1
}}
<br>
<div class="collapser mw-collapsible mw-collapsed" style="width:1200px; overflow:auto;">
C++ реализация:
<div class="mw-collapsible-content">
<source lang = "c++">
for (int i = 1; i <= n; ++i) {
C[i] = C[i] * e;
}
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n; ++j) {
B[i][j] = B[i - 1][j - 1];
}
}
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n; ++j) {
for (int k = 1; k <= n; ++k) {
A[i][j][k] = A[i][j][k] + A[i][j - 1][k - 2];
}
A[i][j][n] = A[i][j][n] + B[i][j];
}
}
</source>
</div>
</div>
<div class="collapser mw-collapsible mw-collapsed" style="width:1200px; overflow:auto;">
Новая разметка:
<div class="mw-collapsible-content">
<source lang = "xml">
<algo>
<params>
<param name = "N" type = "int"></param>
</params>
<block id = "0" dims = "1">
<arg name = "I" val = "1..N"></arg>
<vertex condition = "" type = "1">
</vertex>
</block>
<block id = "0" dims = "2">
<arg name = "I" val = "1..N"></arg>
<arg name = "J" val = "1..N"></arg>
<vertex condition = "" type = "1">
<in src = "I - 1, J - 1"></in>
</vertex>
</block>
<block id = "2" dims = "3">
<arg name = "I" val = "1..N"></arg>
<arg name = "J" val = "1..N"></arg>
<arg name = "K" val = "1..N"></arg>
<vertex condition = "K == 1" type = "2">
<in bsrc = "1" src = "I, J"></in>
<in src = "I - 1, J, K + 2"></in>
</vertex>
<vertex condition = "K > 1" type = "1">
<in src = "I - 1, J, K + 2"></in>
</vertex>
</block>
</algo>
</source>
</div>
</div>
</tab>

<tab name="Специальный_пример_2_n8">
{{#widget:Algoviewer
|url=XML_task_002_n8/Example_001.html
|width=1200
|height=800
|border=1
}}
<br>
<div class="collapser mw-collapsible mw-collapsed" style="width:1200px; overflow:auto;">
C++ реализация:
<div class="mw-collapsible-content">
<source lang = "c++">
for (int i = 1; i <= n; ++i) {
C[i] = C[i] * e;
}
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n; ++j) {
B[i][j] = B[i - 1][j - 1];
}
}
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n; ++j) {
for (int k = 1; k <= n; ++k) {
A[i][j][k] = A[i][j][k] + A[i][j - 1][k - 2];
}
A[i][j][n] = A[i][j][n] + B[i][j];
}
}
</source>
</div>
</div>
</tab>

<tab name="Преобразование_фурье">
{{#widget:Algoviewer
|url=XML_Fourier/Example_001.html
|width=1200
|height=800
|border=1
}}
<br>
<div class="collapser mw-collapsible mw-collapsed" style="width:1200px; overflow:auto;">
Новая разметка:
<div class="mw-collapsible-content">
<source lang = "xml">
<algo>
<params>
<param name = "N" type = "int" value = "3"></param>
</params>
<block id = "0" dims = "2">
<arg name = "I" val = "1..N"></arg>
<arg name = "J" val = "1..2^N"></arg>
<vertex condition = "(J - 1) % (2^I) < 2^(I - 1)" type = "1">
<in src = "I - 1, J"></in>
<in src = "I - 1, J + 2^(I -1)"></in>
</vertex>
<vertex condition = "(J - 1) % (2^I) >= 2^(I - 1)" type = "2">
<in src = "I - 1, J"></in>
<in src = "I - 1, J - 2^(I - 1)"></in>
</vertex>
</block>
</algo>
</source>
</div>
</div>
</tab>

</tabs>

== Тестовые варианты 2020 ==

<tabs>

<tab name="Вариант_01">
{{#widget:Algoviewer
|url=Variant_01/Variant_01.html
|width=1200
|height=800
|border=1
}}
<br>
<div class="collapser mw-collapsible mw-collapsed" style="width:1200px; overflow:auto;">
Новая разметка:
<div class="mw-collapsible-content">
<source lang = "xml">
<algo>
<params>
<param name = "N" type = "int"></param>
<param name = "M" type = "int"></param>
</params>
<block id = "0" dims = "1">
<arg name = "i" val = "1..N"></arg>
<vertex condition = "" type = "1">
<in src = "i - 2"></in>
</vertex>
</block>
<block id = "1" dims = "2">
<arg name = "i" val = "1..N"></arg>
<arg name = "j" val = "1..M"></arg>
<vertex condition = "" type = "1">
<in src = "i - 1, j - 1"></in>
<in bsrc = "0" src = "i"></in>
</vertex>
</block>
<block id = "2" dims = "3">
<arg name = "i" val = "1..N"></arg>
<arg name = "j" val = "1..M"></arg>
<arg name = "k" val = "1..N-1"></arg>
<vertex condition = "(j == 1) and (k == 1)" type = "1">
<in bsrc = "1" src = "i, M"></in>
</vertex>
<vertex condition = "(j > 1) or (k > 1)" type = "1">
<in src = "i - 1, j, 1"></in>
</vertex>
</block>
</algo>
</source>
</div>
</div>
</tab>

<tab name="Вариант_02">
{{#widget:Algoviewer
|url=Variant_02/Variant_02.html
|width=1200
|height=800
|border=1
}}
<br>
<div class="collapser mw-collapsible mw-collapsed" style="width:1200px; overflow:auto;">
Новая разметка:
<div class="mw-collapsible-content">
<source lang = "xml">
<algo>
<params>
<param name = "N" type = "int"></param>
<param name = "M" type = "int"></param>
</params>
<block id = "0" dims = "1">
<arg name = "i" val = "1..N"></arg>
<vertex condition = "" type = "1">
<in src = "i - 1"></in>
</vertex>
</block>
<block id = "1" dims = "2">
<arg name = "i" val = "1..N"></arg>
<arg name = "j" val = "1..M"></arg>
<vertex condition = "" type = "1">
<in src = "i - 2, j"></in>
</vertex>
</block>
<block id = "2" dims = "3">
<arg name = "i" val = "1..N"></arg>
<arg name = "j" val = "1..M"></arg>
<arg name = "k" val = "1..N-1"></arg>
<vertex condition = "(j == 1) and (k == 1)" type = "1">
<in bsrc = "0" src = "i"></in>
<in bsrc = "1" src = "i, M"></in>
</vertex>
<vertex condition = "(j > 1) or (k > 1)" type = "1">
<in src = "i, j - 1, 1"></in>
</vertex>
</block>
</algo>
</source>
</div>
</div>
</tab>

<tab name="Вариант_03">
{{#widget:Algoviewer
|url=Variant_03/Variant_03.html
|width=1200
|height=800
|border=1
}}
<br>
<div class="collapser mw-collapsible mw-collapsed" style="width:1200px; overflow:auto;">
Новая разметка:
<div class="mw-collapsible-content">
<source lang = "xml">
<algo>
<params>
<param name = "N" type = "int"></param>
<param name = "M" type = "int"></param>
</params>
<block id = "0" dims = "1">
<arg name = "i" val = "1..N"></arg>
<vertex condition = "" type = "1">
</vertex>
</block>
<block id = "1" dims = "2">
<arg name = "i" val = "1..N"></arg>
<arg name = "j" val = "1..M"></arg>
<vertex condition = "" type = "1">
<in src = "i, j - 2"></in>
<in bsrc = "0" src = "i"></in>
</vertex>
</block>
<block id = "2" dims = "3">
<arg name = "i" val = "1..N"></arg>
<arg name = "j" val = "1..M"></arg>
<arg name = "k" val = "1..N-1"></arg>
<vertex condition = "(j == 1) and (k == 1)" type = "1">
<in bsrc = "1" src = "i, M"></in>
</vertex>
<vertex condition = "(j > 1) or (k > 1)" type = "1">
<in src = "i, j - 1, k"></in>
</vertex>
</block>
</algo>

</source>
</div>
</div>
</tab>

<tab name="Вариант_04">
{{#widget:Algoviewer
|url=Variant_04/Variant_04.html
|width=1200
|height=800
|border=1
}}
<br>
<div class="collapser mw-collapsible mw-collapsed" style="width:1200px; overflow:auto;">
Новая разметка:
<div class="mw-collapsible-content">
<source lang = "xml">
<algo>
<params>
<param name = "N" type = "int"></param>
<param name = "M" type = "int"></param>
</params>
<block id = "0" dims = "1">
<arg name = "i" val = "1..N"></arg>
<vertex condition = "" type = "1">
<in src = "i - 1"></in>
</vertex>
</block>
<block id = "1" dims = "2">
<arg name = "i" val = "1..N"></arg>
<arg name = "j" val = "1..M"></arg>
<vertex condition = "" type = "1">
<in src = "i - 1, j - 1"></in>
<in bsrc = "0" src = "i"></in>
</vertex>
</block>
<block id = "2" dims = "3">
<arg name = "i" val = "1..N"></arg>
<arg name = "j" val = "1..M"></arg>
<arg name = "k" val = "1..N-1"></arg>
<vertex condition = "(j == 1) and (k == 1)" type = "1">
<in bsrc = "1" src = "i, M"></in>
</vertex>
<vertex condition = "(j > 1) or (k > 1)" type = "1">
<in src = "i - 1, j, k"></in>
</vertex>
</block>
</algo>
</source>
</div>
</div>
</tab>

</tabs>

== Параметрика Пакуля ==

<tab name="Параметрика">
{{#widget:Algoviewer
|url=Variant_parametric/Variant_par.html
|width=1200
|height=800
|border=1
}}
<br>
<div class="collapser mw-collapsible mw-collapsed" style="width:1200px; overflow:auto;">
Новая разметка:
<div class="mw-collapsible-content">
<algo>
<params>
<param name = "N" type = "int"></param>
<param name = "M" type = "int"></param>
<aparam name = "p0" type = "int"></aparam>
<aparam name = "p1" type = "int"></aparam>
<aparam name = "p2" type = "int"></aparam>
<aparam name = "p3" type = "int"></aparam>
<aparam name = "p4" type = "int"></aparam>
<aparam name = "p5" type = "int"></aparam>
</params>
<block id = "0" dims = "1">
<arg name = "i" val = "1..N"></arg>
<vertex condition = "" type = "1">
<in src = "i + p0"></in>
</vertex>
</block>
<block id = "1" dims = "2">
<arg name = "i" val = "1..N"></arg>
<arg name = "j" val = "1..M"></arg>
<vertex condition = "p3 == 0" type = "1">
<in src = "i + p1, j + p2"></in>
</vertex>
<vertex condition = "p3 == 1" type = "1">
<in src = "i + p1, j + p2"></in>
<in bsrc = "0" src = "i"></in>
</vertex>
</block>
<block id = "2" dims = "3">
<arg name = "i" val = "1..N"></arg>
<arg name = "j" val = "1..M"></arg>
<arg name = "k" val = "1..N-1"></arg>
<vertex condition = "(j == 1) and (k == 1) and (p3 == 1)" type = "1">
<in bsrc = "1" src = "i, M"></in>
</vertex>
<vertex condition = "(j == 1) and (k == 1) and (p3 == 0)" type = "1">
<in bsrc = "1" src = "i, M"></in>
<in bsrc = "0" src = "i"></in>
</vertex>
<vertex condition = "((j > 1) or (k > 1)) and (p4 == 1)" type = "1">
<in src = "i - 1 * (1 - p5), j - 1 * p5, 1"></in>
</vertex>
<vertex condition = "((j > 1) or (k > 1)) and (p4 == 0)" type = "1">
<in src = "i - 1 * (1 - p5), j - 1 * p5, k"></in>
</vertex>
</block>
</algo>
<source lang = "xml">
</source>
</div>
</div>
</tab>

Обсуждение участника:VolkovNikita94

2020-08-10T18:00:52Z

VolkovNikita94: /* Параметрика Пакуля */ новая тема

<tabs>

<tab name="Специальный_пример_1_n4">
{{#widget:Algoviewer
|url=XML_task_001/Example_001.html
|width=1200
|height=800
|border=1
}}
<br>
<div class="collapser mw-collapsible mw-collapsed" style="width:1200px; overflow:auto;">
C++ реализация:
<div class="mw-collapsible-content">
<source lang = "c++">
for (int i = 1; i <= n; ++i) {
C[i] = C[i - 2];
}
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n; ++j) {
B[i][j] = B[i][j] + C[i];
}
}
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n; ++j) {
for (int k = 1; k <= n; ++k) {
A[i][j][k] = A[i][j][k] + A[i - 1][j][1];
}
}
}
</source>
</div>
</div>
<div class="collapser mw-collapsible mw-collapsed" style="width:1200px; overflow:auto;">
Новая разметка:
<div class="mw-collapsible-content">
<source lang = "xml">
<algo>
<params>
<param name = "N" type = "int"></param>
</params>
<block id = "0" dims = "1">
<arg name = "i" val = "1..N"></arg>
<vertex condition = "" type = "0">
<in src = “i – 2”></in>
</vertex>
</block>
<block id = "1" dims = "2">
<arg name = "i" val = "1..N"></arg>
<arg name = "j" val = "1..N"></arg>
<vertex condition = "" type = "0">
<in bsrc = "0" src = "i"></in>
</vertex>
</block>
<block id = "2" dims = "3">
<arg name = "i" val = "1..N"></arg>
<arg name = "j" val = "1..N"></arg>
<arg name = "k" val = "1..N"></arg>
<vertex condition = "(k == 1) || (i == 1)" type = "0">
</vertex>
<vertex condition = "(k > 1) && (i > 1)" type = "0">
<in src = “1, j, 1”></in>
</vertex>
</block>
</algo>
</source>
</div>
</div>
</tab>

<tab name="Специальный_пример_1_n8">
{{#widget:Algoviewer
|url=XML_task_001_n8/Example_001.html
|width=1200
|height=800
|border=1
}}
<br>
<div class="collapser mw-collapsible mw-collapsed" style="width:1200px; overflow:auto;">
C++ реализация:
<div class="mw-collapsible-content">
<source lang = "c++">
for (int i = 1; i <= n; ++i) {
C[i] = C[i - 2];
}
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n; ++j) {
B[i][j] = B[i][j] + C[i];
}
}
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n; ++j) {
for (int k = 1; k <= n; ++k) {
A[i][j][k] = A[i][j][k] + A[i - 1][j][1];
}
}
}
</source>
</div>
</div>
</tab>

<tab name="Специальный_пример_2_n4">
{{#widget:Algoviewer
|url=XML_task_002/Example_001.html
|width=1200
|height=800
|border=1
}}
<br>
<div class="collapser mw-collapsible mw-collapsed" style="width:1200px; overflow:auto;">
C++ реализация:
<div class="mw-collapsible-content">
<source lang = "c++">
for (int i = 1; i <= n; ++i) {
C[i] = C[i] * e;
}
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n; ++j) {
B[i][j] = B[i - 1][j - 1];
}
}
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n; ++j) {
for (int k = 1; k <= n; ++k) {
A[i][j][k] = A[i][j][k] + A[i][j - 1][k - 2];
}
A[i][j][n] = A[i][j][n] + B[i][j];
}
}
</source>
</div>
</div>
<div class="collapser mw-collapsible mw-collapsed" style="width:1200px; overflow:auto;">
Новая разметка:
<div class="mw-collapsible-content">
<source lang = "xml">
<algo>
<params>
<param name = "N" type = "int"></param>
</params>
<block id = "0" dims = "1">
<arg name = "I" val = "1..N"></arg>
<vertex condition = "" type = "1">
</vertex>
</block>
<block id = "0" dims = "2">
<arg name = "I" val = "1..N"></arg>
<arg name = "J" val = "1..N"></arg>
<vertex condition = "" type = "1">
<in src = "I - 1, J - 1"></in>
</vertex>
</block>
<block id = "2" dims = "3">
<arg name = "I" val = "1..N"></arg>
<arg name = "J" val = "1..N"></arg>
<arg name = "K" val = "1..N"></arg>
<vertex condition = "K == 1" type = "2">
<in bsrc = "1" src = "I, J"></in>
<in src = "I - 1, J, K + 2"></in>
</vertex>
<vertex condition = "K > 1" type = "1">
<in src = "I - 1, J, K + 2"></in>
</vertex>
</block>
</algo>
</source>
</div>
</div>
</tab>

<tab name="Специальный_пример_2_n8">
{{#widget:Algoviewer
|url=XML_task_002_n8/Example_001.html
|width=1200
|height=800
|border=1
}}
<br>
<div class="collapser mw-collapsible mw-collapsed" style="width:1200px; overflow:auto;">
C++ реализация:
<div class="mw-collapsible-content">
<source lang = "c++">
for (int i = 1; i <= n; ++i) {
C[i] = C[i] * e;
}
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n; ++j) {
B[i][j] = B[i - 1][j - 1];
}
}
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n; ++j) {
for (int k = 1; k <= n; ++k) {
A[i][j][k] = A[i][j][k] + A[i][j - 1][k - 2];
}
A[i][j][n] = A[i][j][n] + B[i][j];
}
}
</source>
</div>
</div>
</tab>

<tab name="Преобразование_фурье">
{{#widget:Algoviewer
|url=XML_Fourier/Example_001.html
|width=1200
|height=800
|border=1
}}
<br>
<div class="collapser mw-collapsible mw-collapsed" style="width:1200px; overflow:auto;">
Новая разметка:
<div class="mw-collapsible-content">
<source lang = "xml">
<algo>
<params>
<param name = "N" type = "int" value = "3"></param>
</params>
<block id = "0" dims = "2">
<arg name = "I" val = "1..N"></arg>
<arg name = "J" val = "1..2^N"></arg>
<vertex condition = "(J - 1) % (2^I) < 2^(I - 1)" type = "1">
<in src = "I - 1, J"></in>
<in src = "I - 1, J + 2^(I -1)"></in>
</vertex>
<vertex condition = "(J - 1) % (2^I) >= 2^(I - 1)" type = "2">
<in src = "I - 1, J"></in>
<in src = "I - 1, J - 2^(I - 1)"></in>
</vertex>
</block>
</algo>
</source>
</div>
</div>
</tab>

</tabs>

== Тестовые варианты 2020 ==

<tabs>

<tab name="Вариант_01">
{{#widget:Algoviewer
|url=Variant_01/Variant_01.html
|width=1200
|height=800
|border=1
}}
<br>
<div class="collapser mw-collapsible mw-collapsed" style="width:1200px; overflow:auto;">
Новая разметка:
<div class="mw-collapsible-content">
<source lang = "xml">
<algo>
<params>
<param name = "N" type = "int"></param>
<param name = "M" type = "int"></param>
</params>
<block id = "0" dims = "1">
<arg name = "i" val = "1..N"></arg>
<vertex condition = "" type = "1">
<in src = "i - 2"></in>
</vertex>
</block>
<block id = "1" dims = "2">
<arg name = "i" val = "1..N"></arg>
<arg name = "j" val = "1..M"></arg>
<vertex condition = "" type = "1">
<in src = "i - 1, j - 1"></in>
<in bsrc = "0" src = "i"></in>
</vertex>
</block>
<block id = "2" dims = "3">
<arg name = "i" val = "1..N"></arg>
<arg name = "j" val = "1..M"></arg>
<arg name = "k" val = "1..N-1"></arg>
<vertex condition = "(j == 1) and (k == 1)" type = "1">
<in bsrc = "1" src = "i, M"></in>
</vertex>
<vertex condition = "(j > 1) or (k > 1)" type = "1">
<in src = "i - 1, j, 1"></in>
</vertex>
</block>
</algo>
</source>
</div>
</div>
</tab>

<tab name="Вариант_02">
{{#widget:Algoviewer
|url=Variant_02/Variant_02.html
|width=1200
|height=800
|border=1
}}
<br>
<div class="collapser mw-collapsible mw-collapsed" style="width:1200px; overflow:auto;">
Новая разметка:
<div class="mw-collapsible-content">
<source lang = "xml">
<algo>
<params>
<param name = "N" type = "int"></param>
<param name = "M" type = "int"></param>
</params>
<block id = "0" dims = "1">
<arg name = "i" val = "1..N"></arg>
<vertex condition = "" type = "1">
<in src = "i - 1"></in>
</vertex>
</block>
<block id = "1" dims = "2">
<arg name = "i" val = "1..N"></arg>
<arg name = "j" val = "1..M"></arg>
<vertex condition = "" type = "1">
<in src = "i - 2, j"></in>
</vertex>
</block>
<block id = "2" dims = "3">
<arg name = "i" val = "1..N"></arg>
<arg name = "j" val = "1..M"></arg>
<arg name = "k" val = "1..N-1"></arg>
<vertex condition = "(j == 1) and (k == 1)" type = "1">
<in bsrc = "0" src = "i"></in>
<in bsrc = "1" src = "i, M"></in>
</vertex>
<vertex condition = "(j > 1) or (k > 1)" type = "1">
<in src = "i, j - 1, 1"></in>
</vertex>
</block>
</algo>
</source>
</div>
</div>
</tab>

<tab name="Вариант_03">
{{#widget:Algoviewer
|url=Variant_03/Variant_03.html
|width=1200
|height=800
|border=1
}}
<br>
<div class="collapser mw-collapsible mw-collapsed" style="width:1200px; overflow:auto;">
Новая разметка:
<div class="mw-collapsible-content">
<source lang = "xml">
<algo>
<params>
<param name = "N" type = "int"></param>
<param name = "M" type = "int"></param>
</params>
<block id = "0" dims = "1">
<arg name = "i" val = "1..N"></arg>
<vertex condition = "" type = "1">
</vertex>
</block>
<block id = "1" dims = "2">
<arg name = "i" val = "1..N"></arg>
<arg name = "j" val = "1..M"></arg>
<vertex condition = "" type = "1">
<in src = "i, j - 2"></in>
<in bsrc = "0" src = "i"></in>
</vertex>
</block>
<block id = "2" dims = "3">
<arg name = "i" val = "1..N"></arg>
<arg name = "j" val = "1..M"></arg>
<arg name = "k" val = "1..N-1"></arg>
<vertex condition = "(j == 1) and (k == 1)" type = "1">
<in bsrc = "1" src = "i, M"></in>
</vertex>
<vertex condition = "(j > 1) or (k > 1)" type = "1">
<in src = "i, j - 1, k"></in>
</vertex>
</block>
</algo>

</source>
</div>
</div>
</tab>

<tab name="Вариант_04">
{{#widget:Algoviewer
|url=Variant_04/Variant_04.html
|width=1200
|height=800
|border=1
}}
<br>
<div class="collapser mw-collapsible mw-collapsed" style="width:1200px; overflow:auto;">
Новая разметка:
<div class="mw-collapsible-content">
<source lang = "xml">
<algo>
<params>
<param name = "N" type = "int"></param>
<param name = "M" type = "int"></param>
</params>
<block id = "0" dims = "1">
<arg name = "i" val = "1..N"></arg>
<vertex condition = "" type = "1">
<in src = "i - 1"></in>
</vertex>
</block>
<block id = "1" dims = "2">
<arg name = "i" val = "1..N"></arg>
<arg name = "j" val = "1..M"></arg>
<vertex condition = "" type = "1">
<in src = "i - 1, j - 1"></in>
<in bsrc = "0" src = "i"></in>
</vertex>
</block>
<block id = "2" dims = "3">
<arg name = "i" val = "1..N"></arg>
<arg name = "j" val = "1..M"></arg>
<arg name = "k" val = "1..N-1"></arg>
<vertex condition = "(j == 1) and (k == 1)" type = "1">
<in bsrc = "1" src = "i, M"></in>
</vertex>
<vertex condition = "(j > 1) or (k > 1)" type = "1">
<in src = "i - 1, j, k"></in>
</vertex>
</block>
</algo>
</source>
</div>
</div>
</tab>

</tabs>

== Параметрика Пакуля ==

<tabs>

<tab name="Параметрика">
{{#widget:Algoviewer
|url=Variant_parametric/Variant_par.html
|width=1200
|height=800
|border=1
}}
<br>
<div class="collapser mw-collapsible mw-collapsed" style="width:1200px; overflow:auto;">
Новая разметка:
<div class="mw-collapsible-content">
<algo>
<params>
<param name = "N" type = "int"></param>
<param name = "M" type = "int"></param>
<aparam name = "p0" type = "int"></aparam>
<aparam name = "p1" type = "int"></aparam>
<aparam name = "p2" type = "int"></aparam>
<aparam name = "p3" type = "int"></aparam>
<aparam name = "p4" type = "int"></aparam>
<aparam name = "p5" type = "int"></aparam>
</params>
<block id = "0" dims = "1">
<arg name = "i" val = "1..N"></arg>
<vertex condition = "" type = "1">
<in src = "i + p0"></in>
</vertex>
</block>
<block id = "1" dims = "2">
<arg name = "i" val = "1..N"></arg>
<arg name = "j" val = "1..M"></arg>
<vertex condition = "p3 == 0" type = "1">
<in src = "i + p1, j + p2"></in>
</vertex>
<vertex condition = "p3 == 1" type = "1">
<in src = "i + p1, j + p2"></in>
<in bsrc = "0" src = "i"></in>
</vertex>
</block>
<block id = "2" dims = "3">
<arg name = "i" val = "1..N"></arg>
<arg name = "j" val = "1..M"></arg>
<arg name = "k" val = "1..N-1"></arg>
<vertex condition = "(j == 1) and (k == 1) and (p3 == 1)" type = "1">
<in bsrc = "1" src = "i, M"></in>
</vertex>
<vertex condition = "(j == 1) and (k == 1) and (p3 == 0)" type = "1">
<in bsrc = "1" src = "i, M"></in>
<in bsrc = "0" src = "i"></in>
</vertex>
<vertex condition = "((j > 1) or (k > 1)) and (p4 == 1)" type = "1">
<in src = "i - 1 * (1 - p5), j - 1 * p5, 1"></in>
</vertex>
<vertex condition = "((j > 1) or (k > 1)) and (p4 == 0)" type = "1">
<in src = "i - 1 * (1 - p5), j - 1 * p5, k"></in>
</vertex>
</block>
</algo>
<source lang = "xml">
</source>
</div>
</div>
</tab>

Обсуждение участника:VolkovNikita94

2020-07-28T22:16:40Z

VolkovNikita94: /* Тестовые варианты 2017 */

<tabs>

<tab name="Специальный_пример_1_n4">
{{#widget:Algoviewer
|url=XML_task_001/Example_001.html
|width=1200
|height=800
|border=1
}}
<br>
<div class="collapser mw-collapsible mw-collapsed" style="width:1200px; overflow:auto;">
C++ реализация:
<div class="mw-collapsible-content">
<source lang = "c++">
for (int i = 1; i <= n; ++i) {
C[i] = C[i - 2];
}
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n; ++j) {
B[i][j] = B[i][j] + C[i];
}
}
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n; ++j) {
for (int k = 1; k <= n; ++k) {
A[i][j][k] = A[i][j][k] + A[i - 1][j][1];
}
}
}
</source>
</div>
</div>
<div class="collapser mw-collapsible mw-collapsed" style="width:1200px; overflow:auto;">
Новая разметка:
<div class="mw-collapsible-content">
<source lang = "xml">
<algo>
<params>
<param name = "N" type = "int"></param>
</params>
<block id = "0" dims = "1">
<arg name = "i" val = "1..N"></arg>
<vertex condition = "" type = "0">
<in src = “i – 2”></in>
</vertex>
</block>
<block id = "1" dims = "2">
<arg name = "i" val = "1..N"></arg>
<arg name = "j" val = "1..N"></arg>
<vertex condition = "" type = "0">
<in bsrc = "0" src = "i"></in>
</vertex>
</block>
<block id = "2" dims = "3">
<arg name = "i" val = "1..N"></arg>
<arg name = "j" val = "1..N"></arg>
<arg name = "k" val = "1..N"></arg>
<vertex condition = "(k == 1) || (i == 1)" type = "0">
</vertex>
<vertex condition = "(k > 1) && (i > 1)" type = "0">
<in src = “1, j, 1”></in>
</vertex>
</block>
</algo>
</source>
</div>
</div>
</tab>

<tab name="Специальный_пример_1_n8">
{{#widget:Algoviewer
|url=XML_task_001_n8/Example_001.html
|width=1200
|height=800
|border=1
}}
<br>
<div class="collapser mw-collapsible mw-collapsed" style="width:1200px; overflow:auto;">
C++ реализация:
<div class="mw-collapsible-content">
<source lang = "c++">
for (int i = 1; i <= n; ++i) {
C[i] = C[i - 2];
}
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n; ++j) {
B[i][j] = B[i][j] + C[i];
}
}
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n; ++j) {
for (int k = 1; k <= n; ++k) {
A[i][j][k] = A[i][j][k] + A[i - 1][j][1];
}
}
}
</source>
</div>
</div>
</tab>

<tab name="Специальный_пример_2_n4">
{{#widget:Algoviewer
|url=XML_task_002/Example_001.html
|width=1200
|height=800
|border=1
}}
<br>
<div class="collapser mw-collapsible mw-collapsed" style="width:1200px; overflow:auto;">
C++ реализация:
<div class="mw-collapsible-content">
<source lang = "c++">
for (int i = 1; i <= n; ++i) {
C[i] = C[i] * e;
}
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n; ++j) {
B[i][j] = B[i - 1][j - 1];
}
}
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n; ++j) {
for (int k = 1; k <= n; ++k) {
A[i][j][k] = A[i][j][k] + A[i][j - 1][k - 2];
}
A[i][j][n] = A[i][j][n] + B[i][j];
}
}
</source>
</div>
</div>
<div class="collapser mw-collapsible mw-collapsed" style="width:1200px; overflow:auto;">
Новая разметка:
<div class="mw-collapsible-content">
<source lang = "xml">
<algo>
<params>
<param name = "N" type = "int"></param>
</params>
<block id = "0" dims = "1">
<arg name = "I" val = "1..N"></arg>
<vertex condition = "" type = "1">
</vertex>
</block>
<block id = "0" dims = "2">
<arg name = "I" val = "1..N"></arg>
<arg name = "J" val = "1..N"></arg>
<vertex condition = "" type = "1">
<in src = "I - 1, J - 1"></in>
</vertex>
</block>
<block id = "2" dims = "3">
<arg name = "I" val = "1..N"></arg>
<arg name = "J" val = "1..N"></arg>
<arg name = "K" val = "1..N"></arg>
<vertex condition = "K == 1" type = "2">
<in bsrc = "1" src = "I, J"></in>
<in src = "I - 1, J, K + 2"></in>
</vertex>
<vertex condition = "K > 1" type = "1">
<in src = "I - 1, J, K + 2"></in>
</vertex>
</block>
</algo>
</source>
</div>
</div>
</tab>

<tab name="Специальный_пример_2_n8">
{{#widget:Algoviewer
|url=XML_task_002_n8/Example_001.html
|width=1200
|height=800
|border=1
}}
<br>
<div class="collapser mw-collapsible mw-collapsed" style="width:1200px; overflow:auto;">
C++ реализация:
<div class="mw-collapsible-content">
<source lang = "c++">
for (int i = 1; i <= n; ++i) {
C[i] = C[i] * e;
}
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n; ++j) {
B[i][j] = B[i - 1][j - 1];
}
}
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n; ++j) {
for (int k = 1; k <= n; ++k) {
A[i][j][k] = A[i][j][k] + A[i][j - 1][k - 2];
}
A[i][j][n] = A[i][j][n] + B[i][j];
}
}
</source>
</div>
</div>
</tab>

<tab name="Преобразование_фурье">
{{#widget:Algoviewer
|url=XML_Fourier/Example_001.html
|width=1200
|height=800
|border=1
}}
<br>
<div class="collapser mw-collapsible mw-collapsed" style="width:1200px; overflow:auto;">
Новая разметка:
<div class="mw-collapsible-content">
<source lang = "xml">
<algo>
<params>
<param name = "N" type = "int" value = "3"></param>
</params>
<block id = "0" dims = "2">
<arg name = "I" val = "1..N"></arg>
<arg name = "J" val = "1..2^N"></arg>
<vertex condition = "(J - 1) % (2^I) < 2^(I - 1)" type = "1">
<in src = "I - 1, J"></in>
<in src = "I - 1, J + 2^(I -1)"></in>
</vertex>
<vertex condition = "(J - 1) % (2^I) >= 2^(I - 1)" type = "2">
<in src = "I - 1, J"></in>
<in src = "I - 1, J - 2^(I - 1)"></in>
</vertex>
</block>
</algo>
</source>
</div>
</div>
</tab>

</tabs>

== Тестовые варианты 2017 ==

<tabs>

<tab name="Вариант_01">
{{#widget:Algoviewer
|url=Variant_01/Variant_01.html
|width=1200
|height=800
|border=1
}}
<br>
<div class="collapser mw-collapsible mw-collapsed" style="width:1200px; overflow:auto;">
Новая разметка:
<div class="mw-collapsible-content">
<source lang = "xml">
<algo>
<params>
<param name = "N" type = "int"></param>
<param name = "M" type = "int"></param>
</params>
<block id = "0" dims = "1">
<arg name = "i" val = "1..N"></arg>
<vertex condition = "" type = "1">
<in src = "i - 2"></in>
</vertex>
</block>
<block id = "1" dims = "2">
<arg name = "i" val = "1..N"></arg>
<arg name = "j" val = "1..M"></arg>
<vertex condition = "" type = "1">
<in src = "i - 1, j - 1"></in>
<in bsrc = "0" src = "i"></in>
</vertex>
</block>
<block id = "2" dims = "3">
<arg name = "i" val = "1..N"></arg>
<arg name = "j" val = "1..M"></arg>
<arg name = "k" val = "1..N-1"></arg>
<vertex condition = "(j == 1) and (k == 1)" type = "1">
<in bsrc = "1" src = "i, M"></in>
</vertex>
<vertex condition = "(j > 1) or (k > 1)" type = "1">
<in src = "i - 1, j, 1"></in>
</vertex>
</block>
</algo>
</source>
</div>
</div>
</tab>

<tab name="Вариант_02">
{{#widget:Algoviewer
|url=Variant_02/Variant_02.html
|width=1200
|height=800
|border=1
}}
<br>
<div class="collapser mw-collapsible mw-collapsed" style="width:1200px; overflow:auto;">
Новая разметка:
<div class="mw-collapsible-content">
<source lang = "xml">
<algo>
<params>
<param name = "N" type = "int"></param>
<param name = "M" type = "int"></param>
</params>
<block id = "0" dims = "1">
<arg name = "i" val = "1..N"></arg>
<vertex condition = "" type = "1">
<in src = "i - 1"></in>
</vertex>
</block>
<block id = "1" dims = "2">
<arg name = "i" val = "1..N"></arg>
<arg name = "j" val = "1..M"></arg>
<vertex condition = "" type = "1">
<in src = "i - 2, j"></in>
<in bsrc = "0" src = "i"></in>
</vertex>
</block>
<block id = "2" dims = "3">
<arg name = "i" val = "1..N"></arg>
<arg name = "j" val = "1..M"></arg>
<arg name = "k" val = "1..N-1"></arg>
<vertex condition = "(j == 1) and (k == 1)" type = "1">
<in bsrc = "1" src = "i, M"></in>
</vertex>
<vertex condition = "(j > 1) or (k > 1)" type = "1">
<in src = "i, j - 1, 1"></in>
</vertex>
</block>
</algo>
</source>
</div>
</div>
</tab>

<tab name="Вариант_03">
{{#widget:Algoviewer
|url=Variant_03/Variant_03.html
|width=1200
|height=800
|border=1
}}
<br>
<div class="collapser mw-collapsible mw-collapsed" style="width:1200px; overflow:auto;">
Новая разметка:
<div class="mw-collapsible-content">
<source lang = "xml">
<algo>
<params>
<param name = "N" type = "int"></param>
<param name = "M" type = "int"></param>
</params>
<block id = "0" dims = "1">
<arg name = "i" val = "1..N"></arg>
<vertex condition = "" type = "1">
<in src = "i - 1"></in>
</vertex>
</block>
<block id = "1" dims = "2">
<arg name = "i" val = "1..N"></arg>
<arg name = "j" val = "1..M"></arg>
<vertex condition = "" type = "1">
<in src = "i - 2, j"></in>
<in bsrc = "0" src = "i"></in>
</vertex>
</block>
<block id = "2" dims = "3">
<arg name = "i" val = "1..N"></arg>
<arg name = "j" val = "1..M"></arg>
<arg name = "k" val = "1..N-1"></arg>
<vertex condition = "(j == 1) and (k == 1)" type = "1">
<in bsrc = "1" src = "i, M"></in>
</vertex>
<vertex condition = "(j > 1) or (k > 1)" type = "1">
<in src = "i - 1, j, k"></in>
</vertex>
</block>
</algo>

</source>
</div>
</div>
</tab>

<tab name="Вариант_04">
{{#widget:Algoviewer
|url=Variant_04/Variant_04.html
|width=1200
|height=800
|border=1
}}
<br>
<div class="collapser mw-collapsible mw-collapsed" style="width:1200px; overflow:auto;">
Новая разметка:
<div class="mw-collapsible-content">
<source lang = "xml">
<algo>
<params>
<param name = "N" type = "int"></param>
<param name = "M" type = "int"></param>
</params>
<block id = "0" dims = "1">
<arg name = "i" val = "1..N"></arg>
<vertex condition = "" type = "1">
<in src = "i - 2"></in>
</vertex>
</block>
<block id = "1" dims = "2">
<arg name = "i" val = "1..N"></arg>
<arg name = "j" val = "1..M"></arg>
<vertex condition = "" type = "1">
<in src = "i - 1, j - 1"></in>
<in bsrc = "0" src = "i"></in>
</vertex>
</block>
<block id = "2" dims = "3">
<arg name = "i" val = "1..N"></arg>
<arg name = "j" val = "1..M"></arg>
<arg name = "k" val = "1..N-1"></arg>
<vertex condition = "(j == 1) and (k == 1)" type = "1">
<in bsrc = "1" src = "i, M"></in>
</vertex>
<vertex condition = "(j > 1) or (k > 1)" type = "1">
<in src = "i, j - 1, k"></in>
</vertex>
</block>
</algo>
</source>
</div>
</div>
</tab>

</tabs>

Обсуждение участника:VolkovNikita94

2020-07-28T22:10:20Z

VolkovNikita94:

Обсуждение участника:VolkovNikita94

2020-07-28T22:09:00Z

VolkovNikita94:

Обсуждение участника:VolkovNikita94

2020-07-28T17:11:41Z

VolkovNikita94: /* Тестовые варианты 2017 */ - Обновление ссылок

Участник:VolkovNikita94

2020-07-28T17:02:05Z

VolkovNikita94: Удалил разделы, перенесенные в обсуждение.

<tabs>

<tab name="Пример 1">
{{#widget:Algoviewer
|url=XML_example_001/Example_001.html
|width=1200
|height=800
|border=1
}}
<br>
Чисто последовательная структура в 2D-представлении (последовательное суммирование)

<div class="collapser mw-collapsible mw-collapsed" style="width:1200px; overflow:auto;">
C++ реализация:
<div class="mw-collapsible-content">
<source lang = "c++">
int seqSum(const std::vector<int>& _src)
{
int resSum = 0;
for (int srcId = 0; srcId < _src.size(); ++srcId)
{
resSum += _src[srcId];
}
return resSum;
}
</source>
</div>
</div>

<div class="collapser mw-collapsible mw-collapsed" style="width:1200px; overflow:auto;">
Кодировка в XML:
<div class="mw-collapsible-content">
<source lang = "xml">
<?xml version="1.0" encoding="UTF-8"?>
<algograph version="0.0.1">
<algorithm num_ext_params="1" num_groups="2">
<ext_param name="n"/>
<group id="0" num_or_parts="1" num_oper="1">
<or_part id="0" num_and_parts="1">
<and_part id="0"><![CDATA[]]></and_part>
<statement id="0" num_inputs="1">
<input id="0" num_solutions="0"/>
</statement>
</or_part>
</group>
<loop>
<loop>
<group id="1" num_or_parts="1" num_oper="1">
<or_part id="0" num_and_parts="4">
<and_part id="0"><![CDATA[-i1<=-1]]></and_part>
<and_part id="1"><![CDATA[i1<=n]]></and_part>
<and_part id="2"><![CDATA[-i2<=-1]]></and_part>
<and_part id="3"><![CDATA[i2<=n]]></and_part>
<statement id="0" num_inputs="3">
<input id="0" num_solutions="0"/>
<input id="1" num_solutions="3">
<solution num_altareas="1" group_id="1" or_part_id="0" statement_id="0" dimsolut="2">
<altarea num_conditions="5">
<condition><![CDATA[i2-n<=0]]></condition>
<condition><![CDATA[-n+2<=0]]></condition>
<condition><![CDATA[i1-n<=0]]></condition>
<condition><![CDATA[-i1+1<=0]]></condition>
<condition><![CDATA[-i2+2<=0]]></condition>
</altarea>
<dependency>
<coordinate><![CDATA[i1]]></coordinate>
<coordinate><![CDATA[i2-1]]></coordinate>
</dependency>
</solution>
<solution num_altareas="1" group_id="1" or_part_id="0" statement_id="0" dimsolut="2">
<altarea num_conditions="5">
<condition><![CDATA[-i2+1<=0]]></condition>
<condition><![CDATA[-n+2<=0]]></condition>
<condition><![CDATA[i1-n<=0]]></condition>
<condition><![CDATA[-i1+2<=0]]></condition>
<condition><![CDATA[i2-1<=0]]></condition>
</altarea>
<dependency>
<coordinate><![CDATA[i1-1]]></coordinate>
<coordinate><![CDATA[n]]></coordinate>
</dependency>
</solution>
<solution num_altareas="1" group_id="0" or_part_id="0" statement_id="0" dimsolut="0">
<altarea num_conditions="5">
<condition><![CDATA[-n+1<=0]]></condition>
<condition><![CDATA[-i2+1<=0]]></condition>
<condition><![CDATA[-i1+1<=0]]></condition>
<condition><![CDATA[i2-1<=0]]></condition>
<condition><![CDATA[i1-1<=0]]></condition>
</altarea>
</solution>
</input>
<input id="2" num_solutions="0"/>
</statement>
</or_part>
</group>
</loop>
</loop>
</algorithm>
</algograph>
</source>
</div>
</div>
<div class="collapser mw-collapsible mw-collapsed" style="width:1200px; overflow:auto;">
Новая разметка:
<div class="mw-collapsible-content">
<source lang = "xml">
<algo>
<params>
<param name = "N" type = "int"></param>
</params>
<block dims = "2">
<arg name = "i" val = "1..N"></arg>
<arg name = "j" val = "1..N"></arg>

<vertex condition = "(j == 1)" type = "0">
<in src = “i – 1, N”></in>
</vertex>
<vertex condition = "(j > 1)" type = "0">
<in src = “i, j - 1”></in>
</vertex>
</block>
</algo>
</source>
</div>
</div>
</tab>

<tab name="Пример 2">
{{#widget:Algoviewer
|url=XML_example_002/Example_002.html
|width=1200
|height=800
|border=1
}}
<br>
Набор одномерных последовательных структур, независимых между собой - 2D вариант
<div class="collapser mw-collapsible mw-collapsed" style="width:1200px; overflow:auto;">
C++ реализация:
<div class="mw-collapsible-content">
<source lang = "c++">
void seqParSum(const std::vector<std::vector<int> >& _src, std::vector<int>& _res)
{
if (_src.size() != _res.size())
return;

for (int srcGrpId = 0; srcGrpId < _src.size(); ++srcGrpId)
{
for (int srcElId = 0; srcElId < _src[srcGrpId].size(); ++srcElId )
{
_res[srcGrpId] += _src[srcGrpId][srcElId];
}
}
return;
}
</source>
</div>
</div>
<div class="collapser mw-collapsible mw-collapsed" style="width:1200px; overflow:auto;">
Кодировка в XML:
<div class="mw-collapsible-content">
<source lang = "xml">
<?xml version="1.0" encoding="UTF-8"?>
<algograph version="0.0.1">
<algorithm num_ext_params="1" num_groups="2">
<ext_param name="n"/>
<group id="0" num_or_parts="1" num_oper="1">
<or_part id="0" num_and_parts="1">
<and_part id="0"><![CDATA[]]></and_part>
<statement id="0" num_inputs="1">
<input id="0" num_solutions="0"/>
</statement>
</or_part>
</group>
<loop>
<loop>
<group id="1" num_or_parts="1" num_oper="1">
<or_part id="0" num_and_parts="4">
<and_part id="0"><![CDATA[-i1<=-1]]></and_part>
<and_part id="1"><![CDATA[i1<=n]]></and_part>
<and_part id="2"><![CDATA[-i2<=-1]]></and_part>
<and_part id="3"><![CDATA[i2<=n]]></and_part>
<statement id="0" num_inputs="3">
<input id="0" num_solutions="0"/>
<input id="1" num_solutions="3">
<solution num_altareas="1" group_id="1" or_part_id="0" statement_id="0" dimsolut="2">
<altarea num_conditions="5">
<condition><![CDATA[i2-n<=0]]></condition>
<condition><![CDATA[-n+2<=0]]></condition>
<condition><![CDATA[i1-n<=0]]></condition>
<condition><![CDATA[-i1+1<=0]]></condition>
<condition><![CDATA[-i2+2<=0]]></condition>
</altarea>
<dependency>
<coordinate><![CDATA[i1]]></coordinate>
<coordinate><![CDATA[i2-1]]></coordinate>
</dependency>
</solution>
<solution num_altareas="1" group_id="1" or_part_id="0" statement_id="0" dimsolut="0">
<altarea num_conditions="5">
<condition><![CDATA[-i2+1<=0]]></condition>
<condition><![CDATA[-n+2<=0]]></condition>
<condition><![CDATA[i1-n<=0]]></condition>
<condition><![CDATA[-i1+2<=0]]></condition>
<condition><![CDATA[i2-1<=0]]></condition>
</altarea>
</solution>
<solution num_altareas="1" group_id="0" or_part_id="0" statement_id="0" dimsolut="0">
<altarea num_conditions="5">
<condition><![CDATA[-n+1<=0]]></condition>
<condition><![CDATA[-i2+1<=0]]></condition>
<condition><![CDATA[-i1+1<=0]]></condition>
<condition><![CDATA[i2-1<=0]]></condition>
<condition><![CDATA[i1-1<=0]]></condition>
</altarea>
</solution>
</input>
<input id="2" num_solutions="0"/>
</statement>
</or_part>
</group>
</loop>
</loop>
</algorithm>
</algograph>
</source>
</div>
</div>
<div class="collapser mw-collapsible mw-collapsed" style="width:1200px; overflow:auto;">
Новая разметка:
<div class="mw-collapsible-content">
<source lang = "xml">
<algo>
<params>
<param name = "N" type = "int"></param>
</params>
<block dims = "2">
<arg name = "i" val = "1..N"></arg>
<arg name = "j" val = "1..N"></arg>

<vertex condition = "" type = "0">
<in src = “i, j - 1”></in>
</vertex>
</block>
</algo>
</source>
</div>
</div>
</tab>

<tab name="Пример 3">
{{#widget:Algoviewer
|url=XML_example_003/Example_003.html
|width=1200
|height=800
|border=1
}}
<br>
Двумерная структура со скошенным параллелизмом
<div class="collapser mw-collapsible mw-collapsed" style="width:1200px; overflow:auto;">
C++ реализация:
<div class="mw-collapsible-content">
<source lang = "c++">
int accumSum(int** _src, int _nCol, int _nRow)
{
for (int rowId = 0; rowId < _nRow; ++rowId)
{
for (int colId = 0; colId < _nCol; ++colId)
{
_src[rowId][colId] += _src[rowId][colId == 0 ? colId : colId - 1];
_src[rowId][colId] += _src[rowId == 0 ? rowId : rowId - 1][colId];
}
}
return _src[_nRow - 1][_nCol - 1];
}
</source>
</div>
</div>
<div class="collapser mw-collapsible mw-collapsed" style="width:1200px; overflow:auto;">
Кодировка в XML:
<div class="mw-collapsible-content">
<source lang = "xml">
<?xml version="1.0" encoding="UTF-8"?>
<algograph version="0.0.1">
<algorithm num_ext_params="1" num_groups="2">
<ext_param name="n"/>
<group id="0" num_or_parts="1" num_oper="1">
<or_part id="0" num_and_parts="1">
<and_part id="0"><![CDATA[]]></and_part>
<statement id="0" num_inputs="1">
<input id="0" num_solutions="0"/>
</statement>
</or_part>
</group>
<loop>
<loop>
<group id="1" num_or_parts="1" num_oper="1">
<or_part id="0" num_and_parts="4">
<and_part id="0"><![CDATA[-i1<=-1]]></and_part>
<and_part id="1"><![CDATA[i1<=n]]></and_part>
<and_part id="2"><![CDATA[-i2<=-1]]></and_part>
<and_part id="3"><![CDATA[i2<=n]]></and_part>
<statement id="0" num_inputs="3">
<input id="0" num_solutions="0"/>
<input id="1" num_solutions="3">
<solution num_altareas="1" group_id="1" or_part_id="0" statement_id="0" dimsolut="2">
<altarea num_conditions="5">
<condition><![CDATA[i2-n<=0]]></condition>
<condition><![CDATA[-n+2<=0]]></condition>
<condition><![CDATA[i1-n<=0]]></condition>
<condition><![CDATA[-i1+1<=0]]></condition>
<condition><![CDATA[-i2+2<=0]]></condition>
</altarea>
<dependency>
<coordinate><![CDATA[i1]]></coordinate>
<coordinate><![CDATA[i2-1]]></coordinate>
</dependency>
</solution>
<solution num_altareas="1" group_id="1" or_part_id="0" statement_id="0" dimsolut="2">
<altarea num_conditions="5">
<condition><![CDATA[i2-n<=0]]></condition>
<condition><![CDATA[-n+2<=0]]></condition>
<condition><![CDATA[i1-n<=0]]></condition>
<condition><![CDATA[-i1+2<=0]]></condition>
<condition><![CDATA[-i2+1<=0]]></condition>
</altarea>
<dependency>
<coordinate><![CDATA[i1-1]]></coordinate>
<coordinate><![CDATA[i2]]></coordinate>
</dependency>
</solution>
<solution num_altareas="1" group_id="0" or_part_id="0" statement_id="0" dimsolut="0">
<altarea num_conditions="5">
<condition><![CDATA[-n+1<=0]]></condition>
<condition><![CDATA[-i2+1<=0]]></condition>
<condition><![CDATA[-i1+1<=0]]></condition>
<condition><![CDATA[i2-1<=0]]></condition>
<condition><![CDATA[i1-1<=0]]></condition>
</altarea>
</solution>
</input>
<input id="2" num_solutions="0"/>
</statement>
</or_part>
</group>
</loop>
</loop>
</algorithm>
</algograph>
</source>
</div>
</div>
<div class="collapser mw-collapsible mw-collapsed" style="width:1200px; overflow:auto;">
Новая разметка:
<div class="mw-collapsible-content">
<source lang = "xml">
<algo>
<params>
<param name = "N" type = "int"></param>
</params>
<block dims = "2">
<arg name = "i" val = "1..N"></arg>
<arg name = "j" val = "1..N"></arg>

<vertex condition = "" type = "0">
<in src = “i, j - 1”></in>
<in src = “i - 1, j”></in>
</vertex>
</block>
</algo>
</source>
</div>
</div>
</tab>

<tab name="Пример 4">
{{#widget:Algoviewer
|url=XML_example_004/Example_004.html
|width=1200
|height=800
|border=1
}}
<br>
Двумерная структура со скошенным параллелизмом и скошенной передачей данных
<div class="collapser mw-collapsible mw-collapsed" style="width:1200px; overflow:auto;">
C++ реализация:
<div class="mw-collapsible-content">
<source lang = "c++">
int accumSum(int** _src, int _nCol, int _nRow)
{
for (int rowId = 0; rowId < _nRow; ++rowId)
{
for (int colId = 0; colId < _nCol; ++colId)
{
_src[rowId][colId] += _src[(rowId == 0 && colId < 2) ? rowId : rowId - 1][(rowId != 0 && colId > 1) ? colId : colId - 2];
_src[rowId][colId] += _src[rowId == 0 ? rowId : rowId - 1][colId];
}
}
return _src[_nRow - 1][_nCol - 1];
}
</source>
</div>
</div>
<div class="collapser mw-collapsible mw-collapsed" style="width:1200px; overflow:auto;">
Кодировка в XML:
<div class="mw-collapsible-content">
<source lang = "xml">
<?xml version="1.0" encoding="UTF-8"?>
<algograph version="0.0.1">
<algorithm num_ext_params="1" num_groups="2">
<ext_param name="n"/>
<group id="0" num_or_parts="1" num_oper="1">
<or_part id="0" num_and_parts="1">
<and_part id="0"><![CDATA[]]></and_part>
<statement id="0" num_inputs="1">
<input id="0" num_solutions="0"/>
</statement>
</or_part>
</group>
<loop>
<loop>
<group id="1" num_or_parts="1" num_oper="1">
<or_part id="0" num_and_parts="4">
<and_part id="0"><![CDATA[-i1<=-1]]></and_part>
<and_part id="1"><![CDATA[i1<=n]]></and_part>
<and_part id="2"><![CDATA[-i2<=-1]]></and_part>
<and_part id="3"><![CDATA[i2<=n]]></and_part>
<statement id="0" num_inputs="3">
<input id="0" num_solutions="0"/>
<input id="1" num_solutions="3">
<solution num_altareas="1" group_id="1" or_part_id="0" statement_id="0" dimsolut="2">
<altarea num_conditions="5">
<condition><![CDATA[i2-n<=0]]></condition>
<condition><![CDATA[-n+2<=0]]></condition>
<condition><![CDATA[i1-n<=0]]></condition>
<condition><![CDATA[-i1+1<=0]]></condition>
<condition><![CDATA[-i2+2<=0]]></condition>
</altarea>
<dependency>
<coordinate><![CDATA[i1]]></coordinate>
<coordinate><![CDATA[i2-1]]></coordinate>
</dependency>
</solution>
<solution num_altareas="1" group_id="1" or_part_id="0" statement_id="0" dimsolut="2">
<altarea num_conditions="5">
<condition><![CDATA[i2-n<=0]]></condition>
<condition><![CDATA[-n+2<=0]]></condition>
<condition><![CDATA[i1-n<=0]]></condition>
<condition><![CDATA[-i1+3<=0]]></condition>
<condition><![CDATA[-i2+2<=0]]></condition>
</altarea>
<dependency>
<coordinate><![CDATA[i1-2]]></coordinate>
<coordinate><![CDATA[i2-1]]></coordinate>
</dependency>
</solution>
<solution num_altareas="1" group_id="0" or_part_id="0" statement_id="0" dimsolut="0">
<altarea num_conditions="5">
<condition><![CDATA[-n+1<=0]]></condition>
<condition><![CDATA[-i2+1<=0]]></condition>
<condition><![CDATA[-i1+1<=0]]></condition>
<condition><![CDATA[i2-1<=0]]></condition>
<condition><![CDATA[i1-n<=0]]></condition>
</altarea>
</solution>
</input>
<input id="2" num_solutions="0"/>
</statement>
</or_part>
</group>
</loop>
</loop>
</algorithm>
</algograph>
</source>
</div>
</div>
<div class="collapser mw-collapsible mw-collapsed" style="width:1200px; overflow:auto;">
Новая разметка:
<div class="mw-collapsible-content">
<source lang = "xml">
<algo>
<params>
<param name = "N" type = "int"></param>
</params>
<block dims = "2">
<arg name = "i" val = "1..N"></arg>
<arg name = "j" val = "1..N"></arg>

<vertex condition = "" type = "0">
<in src = “i, j - 1”></in>
<in src = “i - 2, j - 1”></in>
</vertex>
</block>
</algo>
</source>
</div>
</div>
</tab>

<tab name="Пример 5">
{{#widget:Algoviewer
|url=XML_example_005/Example_005.html
|width=1200
|height=800
|border=1
}}
<br>
Двумерная структура с квадратным параллелизмом и массовыми рассылками по каждому измерению
<div class="collapser mw-collapsible mw-collapsed" style="width:1200px; overflow:auto;">
C++ реализация:
<div class="mw-collapsible-content">
<source lang = "c++">
int accumSum(int** _src, int _nCol, int _nRow)
{
for (int rowId = 0; rowId < _nRow; ++rowId)
{
for (int colId = 0; colId < _nCol; ++colId)
{
_src[rowId][colId] += _src[rowId][colId == 0 ? colId : colId - 1];
_src[rowId][colId] += _src[rowId == 0 ? rowId : rowId - 1][colId];
_src[rowId][colId] += _src[rowId][0];
_src[rowId][colId] += _src[0][colId];
}
}
return _src[_nRow - 1][_nCol - 1];
}
</source>
</div>
</div>
<div class="collapser mw-collapsible mw-collapsed" style="width:1200px; overflow:auto;">
Кодировка в XML:
<div class="mw-collapsible-content">
<source lang = "xml">
<?xml version="1.0" encoding="UTF-8"?>
<algograph version="0.0.1">
<algorithm num_ext_params="1" num_groups="2">
<ext_param name="n"/>
<group id="0" num_or_parts="1" num_oper="1">
<or_part id="0" num_and_parts="1">
<and_part id="0"><![CDATA[]]></and_part>
<statement id="0" num_inputs="1">
<input id="0" num_solutions="0"/>
</statement>
</or_part>
</group>
<loop>
<loop>
<group id="1" num_or_parts="1" num_oper="1">
<or_part id="0" num_and_parts="4">
<and_part id="0"><![CDATA[-i1<=-1]]></and_part>
<and_part id="1"><![CDATA[i1<=n]]></and_part>
<and_part id="2"><![CDATA[-i2<=-1]]></and_part>
<and_part id="3"><![CDATA[i2<=n]]></and_part>
<statement id="0" num_inputs="3">
<input id="0" num_solutions="0"/>
<input id="1" num_solutions="5">
<solution num_altareas="1" group_id="1" or_part_id="0" statement_id="0" dimsolut="2">
<altarea num_conditions="5">
<condition><![CDATA[i2-n<=0]]></condition>
<condition><![CDATA[-n+2<=0]]></condition>
<condition><![CDATA[i1-n<=0]]></condition>
<condition><![CDATA[-i1+1<=0]]></condition>
<condition><![CDATA[-i2+2<=0]]></condition>
</altarea>
<dependency>
<coordinate><![CDATA[i1]]></coordinate>
<coordinate><![CDATA[i2-1]]></coordinate>
</dependency>
</solution>
<solution num_altareas="1" group_id="1" or_part_id="0" statement_id="0" dimsolut="2">
<altarea num_conditions="5">
<condition><![CDATA[i2-n<=0]]></condition>
<condition><![CDATA[-n+2<=0]]></condition>
<condition><![CDATA[i1-n<=0]]></condition>
<condition><![CDATA[-i2+1<=0]]></condition>
<condition><![CDATA[-i1+2<=0]]></condition>
</altarea>
<dependency>
<coordinate><![CDATA[i1-1]]></coordinate>
<coordinate><![CDATA[i2]]></coordinate>
</dependency>
</solution>
<solution num_altareas="1" group_id="1" or_part_id="0" statement_id="0" dimsolut="2">
<altarea num_conditions="5">
<condition><![CDATA[i2-n<=0]]></condition>
<condition><![CDATA[-n+2<=0]]></condition>
<condition><![CDATA[i1-n<=0]]></condition>
<condition><![CDATA[-i1+1<=0]]></condition>
<condition><![CDATA[-i2+3<=0]]></condition>
</altarea>
<dependency>
<coordinate><![CDATA[i1]]></coordinate>
<coordinate><![CDATA[1]]></coordinate>
</dependency>
</solution>
<solution num_altareas="1" group_id="1" or_part_id="0" statement_id="0" dimsolut="2">
<altarea num_conditions="5">
<condition><![CDATA[i2-n<=0]]></condition>
<condition><![CDATA[-n+2<=0]]></condition>
<condition><![CDATA[i1-n<=0]]></condition>
<condition><![CDATA[-i2+1<=0]]></condition>
<condition><![CDATA[-i1+3<=0]]></condition>
</altarea>
<dependency>
<coordinate><![CDATA[1]]></coordinate>
<coordinate><![CDATA[i2]]></coordinate>
</dependency>
</solution>
<solution num_altareas="1" group_id="0" or_part_id="0" statement_id="0" dimsolut="0">
<altarea num_conditions="5">
<condition><![CDATA[-n+1<=0]]></condition>
<condition><![CDATA[-i2+1<=0]]></condition>
<condition><![CDATA[-i1+1<=0]]></condition>
<condition><![CDATA[i2-1<=0]]></condition>
<condition><![CDATA[i1-n<=0]]></condition>
</altarea>
</solution>
</input>
<input id="2" num_solutions="0"/>
</statement>
</or_part>
</group>
</loop>
</loop>
</algorithm>
</algograph>
</source>
</div>
</div>
<div class="collapser mw-collapsible mw-collapsed" style="width:1200px; overflow:auto;">
Новая разметка:
<div class="mw-collapsible-content">
<source lang = "xml">
<algo>
<params>
<param name = "N" type = "int"></param>
</params>
<block dims = "2">
<arg name = "i" val = "1..N"></arg>
<arg name = "j" val = "1..N"></arg>
<vertex condition = "" type = "0">
<in src = “i, j - 1”></in>
<in src = “i - 1, j”></in>
<in src = “1, j”></in>
<in src = “i, 1”></in>
</vertex>
</block>
</algo>
</source>
</div>
</div>
</tab>

<tab name="Пример 6">
{{#widget:Algoviewer
|url=XML_example_006/Example_006.html
|width=1200
|height=800
|border=1
}}
<br>
Набор независимых последовательно-параллельных 2D-структур с массовой рассылкой данных в каждой
<div class="collapser mw-collapsible mw-collapsed" style="width:1200px; overflow:auto;">
C++ реализация:
<div class="mw-collapsible-content">
<source lang = "c++">
void accumSum(int*** _src, int _nCol, int _nRow, int _nLayer)
{
for (int layerId = 0; layerId < _nLayer; ++layerId)
{
for (int rowId = 0; rowId < _nRow; ++rowId)
{
for (int colId = 0; colId < _nCol; ++colId)
{
_src[layerId][rowId][colId] += _src[layerId][rowId == 0 ? rowId : rowId - 1][colId == 0 ? colId : 0];
_src[layerId][rowId][colId] += _src[layerId][rowId == 0 ? rowId : rowId - 1][colId];
}
}
}
}
</source>
</div>
</div>
<div class="collapser mw-collapsible mw-collapsed" style="width:1200px; overflow:auto;">
Кодировка в XML:
<div class="mw-collapsible-content">
<source lang = "xml">
<?xml version="1.0" encoding="UTF-8"?>
<algograph version="0.0.1">
<algorithm num_ext_params="2" num_groups="2">
<ext_param name="n"/>
<ext_param name="m"/>
<group id="0" num_or_parts="1" num_oper="1">
<or_part id="0" num_and_parts="1">
<and_part id="0"><![CDATA[]]></and_part>
<statement id="0" num_inputs="1">
<input id="0" num_solutions="0"/>
</statement>
</or_part>
</group>
<loop>
<loop>
<loop>
<group id="1" num_or_parts="1" num_oper="1">
<or_part id="0" num_and_parts="6">
<and_part id="0"><![CDATA[-i1<=-1]]></and_part>
<and_part id="1"><![CDATA[i1<=n]]></and_part>
<and_part id="2"><![CDATA[-i2<=-1]]></and_part>
<and_part id="3"><![CDATA[i2<=m]]></and_part>
<and_part id="4"><![CDATA[i3>=0]]></and_part>
<and_part id="5"><![CDATA[i3<=n-1]]></and_part>
<input id="0" num_solutions="0"/>
<input id="1" num_solutions="3">
<solution num_altareas="1" group_id="1" or_part_id="0" statement_id="0" dimsolut="3">
<altarea num_conditions="7">
<condition><![CDATA[-m+2<=0]]></condition>
<condition><![CDATA[i1-n<=0]]></condition>
<condition><![CDATA[i3-n+1<=0]]></condition>
<condition><![CDATA[-i2+2<=0]]></condition>
<condition><![CDATA[i2<=m]]></condition>
<condition><![CDATA[-i1+1<=0]]></condition>
<condition><![CDATA[-i3<=0]]></condition>
</altarea>
<dependency>
<coordinate><![CDATA[i1]]></coordinate>
<coordinate><![CDATA[i2-1]]></coordinate>
<coordinate><![CDATA[i3]]></coordinate>
</dependency>
</solution>
<solution num_altareas="1" group_id="1" or_part_id="0" statement_id="0" dimsolut="3">
<altarea num_conditions="7">
<condition><![CDATA[-m+2<=0]]></condition>
<condition><![CDATA[i1-n<=0]]></condition>
<condition><![CDATA[i3-n+1<=0]]></condition>
<condition><![CDATA[-i2+2<=0]]></condition>
<condition><![CDATA[i2<=m]]></condition>
<condition><![CDATA[-i1+1<=0]]></condition>
<condition><![CDATA[-i3<=0]]></condition>
</altarea>
<dependency>
<coordinate><![CDATA[1]]></coordinate>
<coordinate><![CDATA[i2-1]]></coordinate>
<coordinate><![CDATA[i3]]></coordinate>
</dependency>
</solution>
<solution num_altareas="1" group_id="0" or_part_id="0" statement_id="0" dimsolut="0">
<altarea num_conditions="6">
<condition><![CDATA[i2-1<=0]]></condition>
<condition><![CDATA[i2-1>=0]]></condition>
<condition><![CDATA[-i1+1<=0]]></condition>
<condition><![CDATA[-i3<=0]]></condition>
<condition><![CDATA[i1-n<=0]]></condition>
<condition><![CDATA[i3-n+1<=0]]></condition>
</altarea>
</solution>
</input>
<input id="2" num_solutions="0"/>
</statement>
</or_part>
</group>
</loop>
</loop>
</loop>
</algorithm>
</algograph>
</source>
</div>
</div>
<div class="collapser mw-collapsible mw-collapsed" style="width:1200px; overflow:auto;">
Новая разметка:
<div class="mw-collapsible-content">
<source lang = "xml">
<algo>
<params>
<param name = "N" type = "int"></param>
</params>
<block dims = "3">
<arg name = "i" val = "1..N"></arg>
<arg name = "j" val = "1..N"></arg>
<arg name = "k" val = "1..N"></arg>
<vertex condition = "" type = "0">
<in src = “i, j – 1, k”></in>
<in src = “1, j - 1, k”></in>
</vertex>
</block>
</algo>
</source>
</div>
</div>
</tab>

<tab name="Пример 7">
{{#widget:Algoviewer
|url=XML_example_007/Example_007.html
|width=1200
|height=800
|border=1
}}
<br>
Набор одномерных последовательных структур, независимых между собой - 3D вариант
<div class="collapser mw-collapsible mw-collapsed" style="width:1200px; overflow:auto;">
C++ реализация:
<div class="mw-collapsible-content">
<source lang = "c++">
void accumSum(int*** _src, int _nCol, int _nRow, int _nLayer)
{
for (int layerId = 0; layerId < _nLayer; ++layerId)
{
for (int rowId = 0; rowId < _nRow; ++rowId)
{
for (int colId = 0; colId < _nCol; ++colId)
{
_src[layerId][rowId][colId] += _src[layerId][rowId == 0 ? rowId : rowId - 1][colId];
}
}
}
}
</source>
</div>
</div>
<div class="collapser mw-collapsible mw-collapsed" style="width:1200px; overflow:auto;">
Кодировка в XML:
<div class="mw-collapsible-content">
<source lang = "xml">
<?xml version="1.0" encoding="UTF-8"?>
<algograph version="0.0.1">
<algorithm num_ext_params="2" num_groups="2">
<ext_param name="n"/>
<ext_param name="m"/>
<group id="0" num_or_parts="1" num_oper="1">
<or_part id="0" num_and_parts="1">
<and_part id="0"><![CDATA[]]></and_part>
<statement id="0" num_inputs="1">
<input id="0" num_solutions="0"/>
</statement>
</or_part>
</group>
<loop>
<loop>
<loop>
<group id="1" num_or_parts="1" num_oper="1">
<or_part id="0" num_and_parts="6">
<and_part id="0"><![CDATA[-i1<=-1]]></and_part>
<and_part id="1"><![CDATA[i1<=n]]></and_part>
<and_part id="2"><![CDATA[-i2<=-1]]></and_part>
<and_part id="3"><![CDATA[i2<=m]]></and_part>
<and_part id="4"><![CDATA[i3>=0]]></and_part>
<and_part id="5"><![CDATA[i3<=n-1]]></and_part>
<statement id="0" num_inputs="3">
<input id="0" num_solutions="0"/>
<input id="1" num_solutions="2">
<solution num_altareas="1" group_id="1" or_part_id="0" statement_id="0" dimsolut="3">
<altarea num_conditions="7">
<condition><![CDATA[-m+2<=0]]></condition>
<condition><![CDATA[i1-n<=0]]></condition>
<condition><![CDATA[i3-n+1<=0]]></condition>
<condition><![CDATA[-i2+1<=0]]></condition>
<condition><![CDATA[i2+1<=m]]></condition>
<condition><![CDATA[-i1+1<=0]]></condition>
<condition><![CDATA[-i3<=0]]></condition>
</altarea>
<dependency>
<coordinate><![CDATA[i1]]></coordinate>
<coordinate><![CDATA[i2+1]]></coordinate>
<coordinate><![CDATA[i3]]></coordinate>
</dependency>
</solution>
<solution num_altareas="1" group_id="0" or_part_id="0" statement_id="0" dimsolut="0">
<altarea num_conditions="6">
<condition><![CDATA[i2-m<=0]]></condition>
<condition><![CDATA[i2-m>=0]]></condition>
<condition><![CDATA[-i1+1<=0]]></condition>
<condition><![CDATA[-i3<=0]]></condition>
<condition><![CDATA[i1-n<=0]]></condition>
<condition><![CDATA[i3-n+1<=0]]></condition>
</altarea>
</solution>
</input>
<input id="2" num_solutions="0"/>
</statement>
</or_part>
</group>
</loop>
</loop>
</loop>
</algorithm>
</algograph>
</source>
</div>
</div>
<div class="collapser mw-collapsible mw-collapsed" style="width:1200px; overflow:auto;">
Новая разметка:
<div class="mw-collapsible-content">
<source lang = "xml">
<algo>
<params>
<param name = "N" type = "int"></param>
</params>
<block dims = "3">
<arg name = "i" val = "1..N"></arg>
<arg name = "j" val = "1..N"></arg>
<arg name = "k" val = "1..N"></arg>

<vertex condition = "" type = "0">
<in src = “i, j – 1, k”></in>
</vertex>
</block>
</algo>
</source>
</div>
</div>
</tab>

<tab name="Пример 8">
{{#widget:Algoviewer
|url=XML_example_008/Example_008.html
|width=1200
|height=800
|border=1
}}
<br>
Пример массовой рассылки данных в 2D-структуре
<div class="collapser mw-collapsible mw-collapsed" style="width:1200px; overflow:auto;">
Новая разметка:
<div class="mw-collapsible-content">
<source lang = "xml">
<algo>
<params>
<param name = "N" type = "int"></param>
</params>
<block dims = "2">
<arg name = "i" val = "1..N"></arg>
<arg name = "j" val = "1..2"></arg>

<vertex condition = "(j == 1) && (i == 1)" type = "0">
</vertex>
<vertex condition = "(j > 1)" type = "0">
<in src = “1, 1”></in>
</vertex>
</block>
</algo>
</source>
</div>
</div>
</tab>

<tab name="Пример 10">
{{#widget:Algoviewer
|url=XML_example_010/Example_010.html
|width=1200
|height=800
|border=1
}}
<br>
Последовательный набор 3D-структур, содержащих скошенный параллелизм
<div class="collapser mw-collapsible mw-collapsed" style="width:1200px; overflow:auto;">
Новая разметка:
<div class="mw-collapsible-content">
<source lang = "xml">
<algo>
<params>
<param name = "N" type = "int"></param>
</params>
<block id = "0" dims = "3">
<arg name = "i" val = "1..N"></arg>
<arg name = "j" val = "1..N"></arg>
<arg name = "k" val = "1..N"></arg>
<vertex condition = "" type = "0">
<in src = "i - 1, j, k"></in>
<in src = "i, j – 1, k"></in>
<in src = "i, j, k - 1"></in>
</vertex>
</block>
<block id = "1" dims = "3">
<arg name = "i" val = "1..N"></arg>
<arg name = "j" val = "1..2"></arg>
<arg name = "k" val = "1..N"></arg>
<vertex condition = "" type = "0">
<in bsrc = "0" src = "i, j, k"></in>
<in src = "i - 1, j, k"></in>
<in src = "i, j – 1, k"></in>
<in src = "i, j, k - 1"></in>
</vertex>
</block>
</algo>
</source>
</div>
</div>
</tab>

<tab name="Пример 11">
{{#widget:Algoviewer
|url=XML_example_011/Example_011.html
|width=1200
|height=800
|border=1
}}
<br>
Пример массовой рассылки данных в 3D-структуре
<div class="collapser mw-collapsible mw-collapsed" style="width:1200px; overflow:auto;">
Новая разметка:
<div class="mw-collapsible-content">
<source lang = "xml">
<algo>
<params>
<param name = "N" type = "int"></param>
</params>
<block dims = "3">
<arg name = "i" val = "1..N"></arg>
<arg name = "j" val = "1..N"></arg>
<arg name = "k" val = "1..2"></arg>
<vertex condition = "(i == 1) && (j == 1) && (k == 1)" type = "0">
</vertex>
<vertex condition = "(i > 1) && (j > 1) && (k > 1)" type = "0">
<in src = “1, 1, 1”></in>
</vertex>
</block>
</algo>
</source>
</div>
</div>
</tab>

<tab name="Пример 12">
{{#widget:Algoviewer
|url=XML_example_012/Example_012.html
|width=1200
|height=800
|border=1
}}
<br>
Пример 3D-структуры с различными видами скошенного параллелизма
<div class="collapser mw-collapsible mw-collapsed" style="width:1200px; overflow:auto;">
Новая разметка:
<div class="mw-collapsible-content">
<source lang = "xml">
<algo>
<params>
<param name = "N" type = "int"></param>
</params>
<block dims = "3">
<arg name = "i" val = "1..N"></arg>
<arg name = "j" val = "1..N"></arg>
<arg name = "k" val = "1..2"></arg>
<vertex condition = "k == 1" type = "0">
<in src = “i, j – 1”></in>
<in src = “i - 1, j”></in>
</vertex>
<vertex condition = "k > 1" type = "0">
<in src = “i, j, 1”></in>
<in src = “i, j – 1”></in>
<in src = “i - 1, j - 1”></in>
</vertex>
</block>
</algo>
</source>
</div>
</div>
</tab>

<tab name="Пример 13">
{{#widget:Algoviewer
|url=XML_example_013/Example_013.html
|width=1200
|height=800
|border=1
}}
<br>
Последовательно-параллельное перемножение матриц
<div class="collapser mw-collapsible mw-collapsed" style="width:1200px; overflow:auto;">
Новая разметка:
<div class="mw-collapsible-content">
<source lang = "xml">
<algo>
<params>
<param name = "N" type = "int"></param>
<param name = "P" type = "int"></param>
<param name = "Q" type = "int"></param>
</params>
<block dims = "3">
<arg name = "i" val = "1..N"></arg>
<arg name = "j" val = "1..P"></arg>
<arg name = "k" val = "1..Q"></arg>
<vertex condition = "(i > 1) && (j > 1)" type = "0">
<in src = “i, j – 1”></in>
<in src = “i - 1, j”></in>
<in src = “i, j, k -1”></in>
</vertex>
<vertex condition = "(i > 1) || (j > 1)" type = "0">
<in src = “i, j – 1”></in>
<in src = “i - 1, j”></in>
</vertex>
</block>
</algo>
</source>
</div>
</div>
</tab>

</tabs>

Обсуждение участника:VolkovNikita94

2020-07-28T17:00:51Z

VolkovNikita94: /* Тестовые варианты 2017 */ - чистка лишнего

Обсуждение участника:VolkovNikita94

2020-07-28T16:56:58Z

VolkovNikita94: /* Тестовые варианты 2017 */ новая тема

<tabs>

<tab name="Специальный_пример_1_n4">
{{#widget:Algoviewer
|url=XML_task_001/Example_001.html
|width=1200
|height=800
|border=1
}}
<br>
<div class="collapser mw-collapsible mw-collapsed" style="width:1200px; overflow:auto;">
C++ реализация:
<div class="mw-collapsible-content">
<source lang = "c++">
for (int i = 1; i <= n; ++i) {
C[i] = C[i - 2];
}
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n; ++j) {
B[i][j] = B[i][j] + C[i];
}
}
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n; ++j) {
for (int k = 1; k <= n; ++k) {
A[i][j][k] = A[i][j][k] + A[i - 1][j][1];
}
}
}
</source>
</div>
</div>
<div class="collapser mw-collapsible mw-collapsed" style="width:1200px; overflow:auto;">
Новая разметка:
<div class="mw-collapsible-content">
<source lang = "xml">
<algo>
<params>
<param name = "N" type = "int"></param>
</params>
<block id = "0" dims = "1">
<arg name = "i" val = "1..N"></arg>
<vertex condition = "" type = "0">
<in src = “i – 2”></in>
</vertex>
</block>
<block id = "1" dims = "2">
<arg name = "i" val = "1..N"></arg>
<arg name = "j" val = "1..N"></arg>
<vertex condition = "" type = "0">
<in bsrc = "0" src = "i"></in>
</vertex>
</block>
<block id = "2" dims = "3">
<arg name = "i" val = "1..N"></arg>
<arg name = "j" val = "1..N"></arg>
<arg name = "k" val = "1..N"></arg>
<vertex condition = "(k == 1) || (i == 1)" type = "0">
</vertex>
<vertex condition = "(k > 1) && (i > 1)" type = "0">
<in src = “1, j, 1”></in>
</vertex>
</block>
</algo>
</source>
</div>
</div>
</tab>

<tab name="Специальный_пример_1_n8">
{{#widget:Algoviewer
|url=XML_task_001_n8/Example_001.html
|width=1200
|height=800
|border=1
}}
<br>
<div class="collapser mw-collapsible mw-collapsed" style="width:1200px; overflow:auto;">
C++ реализация:
<div class="mw-collapsible-content">
<source lang = "c++">
for (int i = 1; i <= n; ++i) {
C[i] = C[i - 2];
}
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n; ++j) {
B[i][j] = B[i][j] + C[i];
}
}
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n; ++j) {
for (int k = 1; k <= n; ++k) {
A[i][j][k] = A[i][j][k] + A[i - 1][j][1];
}
}
}
</source>
</div>
</div>
</tab>

<tab name="Специальный_пример_2_n4">
{{#widget:Algoviewer
|url=XML_task_002/Example_001.html
|width=1200
|height=800
|border=1
}}
<br>
<div class="collapser mw-collapsible mw-collapsed" style="width:1200px; overflow:auto;">
C++ реализация:
<div class="mw-collapsible-content">
<source lang = "c++">
for (int i = 1; i <= n; ++i) {
C[i] = C[i] * e;
}
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n; ++j) {
B[i][j] = B[i - 1][j - 1];
}
}
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n; ++j) {
for (int k = 1; k <= n; ++k) {
A[i][j][k] = A[i][j][k] + A[i][j - 1][k - 2];
}
A[i][j][n] = A[i][j][n] + B[i][j];
}
}
</source>
</div>
</div>
<div class="collapser mw-collapsible mw-collapsed" style="width:1200px; overflow:auto;">
Новая разметка:
<div class="mw-collapsible-content">
<source lang = "xml">
<algo>
<params>
<param name = "N" type = "int"></param>
</params>
<block id = "0" dims = "1">
<arg name = "I" val = "1..N"></arg>
<vertex condition = "" type = "1">
</vertex>
</block>
<block id = "0" dims = "2">
<arg name = "I" val = "1..N"></arg>
<arg name = "J" val = "1..N"></arg>
<vertex condition = "" type = "1">
<in src = "I - 1, J - 1"></in>
</vertex>
</block>
<block id = "2" dims = "3">
<arg name = "I" val = "1..N"></arg>
<arg name = "J" val = "1..N"></arg>
<arg name = "K" val = "1..N"></arg>
<vertex condition = "K == 1" type = "2">
<in bsrc = "1" src = "I, J"></in>
<in src = "I - 1, J, K + 2"></in>
</vertex>
<vertex condition = "K > 1" type = "1">
<in src = "I - 1, J, K + 2"></in>
</vertex>
</block>
</algo>
</source>
</div>
</div>
</tab>

<tab name="Специальный_пример_2_n8">
{{#widget:Algoviewer
|url=XML_task_002_n8/Example_001.html
|width=1200
|height=800
|border=1
}}
<br>
<div class="collapser mw-collapsible mw-collapsed" style="width:1200px; overflow:auto;">
C++ реализация:
<div class="mw-collapsible-content">
<source lang = "c++">
for (int i = 1; i <= n; ++i) {
C[i] = C[i] * e;
}
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n; ++j) {
B[i][j] = B[i - 1][j - 1];
}
}
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n; ++j) {
for (int k = 1; k <= n; ++k) {
A[i][j][k] = A[i][j][k] + A[i][j - 1][k - 2];
}
A[i][j][n] = A[i][j][n] + B[i][j];
}
}
</source>
</div>
</tab>

<tab name="Преобразование_фурье">
{{#widget:Algoviewer
|url=XML_Fourier/Example_002.html
|width=1200
|height=800
|border=1
}}
<br>
<div class="collapser mw-collapsible mw-collapsed" style="width:1200px; overflow:auto;">
Новая разметка:
<div class="mw-collapsible-content">
<source lang = "xml">
<algo>
<params>
<param name = "N" type = "int" value = "3"></param>
</params>
<block id = "0" dims = "2">
<arg name = "I" val = "1..N"></arg>
<arg name = "J" val = "1..2^N"></arg>
<vertex condition = "(J - 1) % (2^I) < 2^(I - 1)" type = "1">
<in src = "I - 1, J"></in>
<in src = "I - 1, J + 2^(I -1)"></in>
</vertex>
<vertex condition = "(J - 1) % (2^I) >= 2^(I - 1)" type = "2">
<in src = "I - 1, J"></in>
<in src = "I - 1, J - 2^(I - 1)"></in>
</vertex>
</block>
</algo>
</source>
</div>
</div>
</tab>

</tabs>

== Тестовые варианты 2017 ==

<tabs>

<tab name="Специальный_пример_1_n4">
{{#widget:Algoviewer
|url=XML_task_001/Example_001.html
|width=1200
|height=800
|border=1
}}
<br>
<div class="collapser mw-collapsible mw-collapsed" style="width:1200px; overflow:auto;">
C++ реализация:
<div class="mw-collapsible-content">
<source lang = "c++">
for (int i = 1; i <= n; ++i) {
C[i] = C[i - 2];
}
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n; ++j) {
B[i][j] = B[i][j] + C[i];
}
}
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n; ++j) {
for (int k = 1; k <= n; ++k) {
A[i][j][k] = A[i][j][k] + A[i - 1][j][1];
}
}
}
</source>
</div>
</div>
<div class="collapser mw-collapsible mw-collapsed" style="width:1200px; overflow:auto;">
Новая разметка:
<div class="mw-collapsible-content">
<source lang = "xml">
<algo>
<params>
<param name = "N" type = "int"></param>
</params>
<block id = "0" dims = "1">
<arg name = "i" val = "1..N"></arg>
<vertex condition = "" type = "0">
<in src = “i – 2”></in>
</vertex>
</block>
<block id = "1" dims = "2">
<arg name = "i" val = "1..N"></arg>
<arg name = "j" val = "1..N"></arg>
<vertex condition = "" type = "0">
<in bsrc = "0" src = "i"></in>
</vertex>
</block>
<block id = "2" dims = "3">
<arg name = "i" val = "1..N"></arg>
<arg name = "j" val = "1..N"></arg>
<arg name = "k" val = "1..N"></arg>
<vertex condition = "(k == 1) || (i == 1)" type = "0">
</vertex>
<vertex condition = "(k > 1) && (i > 1)" type = "0">
<in src = “1, j, 1”></in>
</vertex>
</block>
</algo>
</source>
</div>
</div>
</tab>

<tab name="Специальный_пример_1_n8">
{{#widget:Algoviewer
|url=XML_task_001_n8/Example_001.html
|width=1200
|height=800
|border=1
}}
<br>
<div class="collapser mw-collapsible mw-collapsed" style="width:1200px; overflow:auto;">
C++ реализация:
<div class="mw-collapsible-content">
<source lang = "c++">
for (int i = 1; i <= n; ++i) {
C[i] = C[i - 2];
}
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n; ++j) {
B[i][j] = B[i][j] + C[i];
}
}
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n; ++j) {
for (int k = 1; k <= n; ++k) {
A[i][j][k] = A[i][j][k] + A[i - 1][j][1];
}
}
}
</source>
</div>
</div>
</tab>

<tab name="Специальный_пример_2_n4">
{{#widget:Algoviewer
|url=XML_task_002/Example_001.html
|width=1200
|height=800
|border=1
}}
<br>
<div class="collapser mw-collapsible mw-collapsed" style="width:1200px; overflow:auto;">
C++ реализация:
<div class="mw-collapsible-content">
<source lang = "c++">
for (int i = 1; i <= n; ++i) {
C[i] = C[i] * e;
}
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n; ++j) {
B[i][j] = B[i - 1][j - 1];
}
}
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n; ++j) {
for (int k = 1; k <= n; ++k) {
A[i][j][k] = A[i][j][k] + A[i][j - 1][k - 2];
}
A[i][j][n] = A[i][j][n] + B[i][j];
}
}
</source>
</div>
</div>
<div class="collapser mw-collapsible mw-collapsed" style="width:1200px; overflow:auto;">
Новая разметка:
<div class="mw-collapsible-content">
<source lang = "xml">
<algo>
<params>
<param name = "N" type = "int"></param>
</params>
<block id = "0" dims = "1">
<arg name = "I" val = "1..N"></arg>
<vertex condition = "" type = "1">
</vertex>
</block>
<block id = "0" dims = "2">
<arg name = "I" val = "1..N"></arg>
<arg name = "J" val = "1..N"></arg>
<vertex condition = "" type = "1">
<in src = "I - 1, J - 1"></in>
</vertex>
</block>
<block id = "2" dims = "3">
<arg name = "I" val = "1..N"></arg>
<arg name = "J" val = "1..N"></arg>
<arg name = "K" val = "1..N"></arg>
<vertex condition = "K == 1" type = "2">
<in bsrc = "1" src = "I, J"></in>
<in src = "I - 1, J, K + 2"></in>
</vertex>
<vertex condition = "K > 1" type = "1">
<in src = "I - 1, J, K + 2"></in>
</vertex>
</block>
</algo>
</source>
</div>
</div>
</tab>

<tab name="Специальный_пример_2_n8">
{{#widget:Algoviewer
|url=XML_task_002_n8/Example_001.html
|width=1200
|height=800
|border=1
}}
<br>
<div class="collapser mw-collapsible mw-collapsed" style="width:1200px; overflow:auto;">
C++ реализация:
<div class="mw-collapsible-content">
<source lang = "c++">
for (int i = 1; i <= n; ++i) {
C[i] = C[i] * e;
}
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n; ++j) {
B[i][j] = B[i - 1][j - 1];
}
}
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n; ++j) {
for (int k = 1; k <= n; ++k) {
A[i][j][k] = A[i][j][k] + A[i][j - 1][k - 2];
}
A[i][j][n] = A[i][j][n] + B[i][j];
}
}
</source>
</div>
</tab>

<tab name="Преобразование_фурье">
{{#widget:Algoviewer
|url=XML_Fourier/Example_002.html
|width=1200
|height=800
|border=1
}}
<br>
<div class="collapser mw-collapsible mw-collapsed" style="width:1200px; overflow:auto;">
Новая разметка:
<div class="mw-collapsible-content">
<source lang = "xml">
<algo>
<params>
<param name = "N" type = "int" value = "3"></param>
</params>
<block id = "0" dims = "2">
<arg name = "I" val = "1..N"></arg>
<arg name = "J" val = "1..2^N"></arg>
<vertex condition = "(J - 1) % (2^I) < 2^(I - 1)" type = "1">
<in src = "I - 1, J"></in>
<in src = "I - 1, J + 2^(I -1)"></in>
</vertex>
<vertex condition = "(J - 1) % (2^I) >= 2^(I - 1)" type = "2">
<in src = "I - 1, J"></in>
<in src = "I - 1, J - 2^(I - 1)"></in>
</vertex>
</block>
</algo>
</source>
</div>
</div>
</tab>

</tabs>

Обсуждение участника:VolkovNikita94

2020-07-28T16:55:05Z

VolkovNikita94: Информация в обсуждении явно устаревшая, а держать 100500 вкладок на одной страничке становится накладно.

Участник:VolkovNikita94

2020-07-13T21:54:05Z

VolkovNikita94:

Участник:VolkovNikita94

2020-06-23T07:10:38Z

VolkovNikita94:

2019-11-28T10:13:31Z

VolkovNikita94:

Участник:VolkovNikita94

2019-11-05T11:32:53Z

VolkovNikita94:

VolkovNikita94:

<center>
<tabs>

<tab name="Пример 1">
{{#widget:Algoviewer
|url=XML_example_001/Example_001.html
|width=1300
|height=800
|border=1
}}
<br>
<center>
Чисто последовательная структура в 2D-представлении
</center>
</tab>

<tab name="Пример 2">
{{#widget:Algoviewer
|url=XML_example_002/Example_002.html
|width=1300
|height=800
|border=1
}}
<br>
<center>
Набор одномерных последовательных структур, независимых между собой
</center>
</tab>

<tab name="Пример 3">
{{#widget:Algoviewer
|url=XML_example_003/Example_003.html
|width=1300
|height=800
|border=1
}}
<br>
<center>
Двумерная структура со скошенным параллелизмом
</center>
</tab>

<tab name="Пример 4">
{{#widget:Algoviewer
|url=XML_example_004/Example_004.html
|width=1300
|height=800
|border=1
}}
<br>
<center>
Двумерная структура со скошенным параллелизмом и скошенной передачей данных
</center>
</tab>

<tab name="Пример 5">
{{#widget:Algoviewer
|url=XML_example_005/Example_005.html
|width=1300
|height=800
|border=1
}}
<br>
<center>
Двумерная структура с квадратным параллелизмом и массовыми рассылками по каждому измерению
</center>
</tab>

<tab name="Пример 6">
{{#widget:Algoviewer
|url=XML_example_006/Example_006.html
|width=1300
|height=800
|border=1
}}
<br>
<center>
Чисто последовательная структура в 2D-представлении
</center>
</tab>

<tab name="Пример 7">
{{#widget:Algoviewer
|url=XML_example_007/Example_007.html
|width=1300
|height=800
|border=1
}}
<br>
<center>
Чисто последовательная структура в 2D-представлении
</center>
</tab>

<tab name="Пример 8">
{{#widget:Algoviewer
|url=XML_example_008/Example_008.html
|width=1300
|height=800
|border=1
}}
<br>
<center>
Чисто последовательная структура в 2D-представлении
</center>
</tab>

<tab name="Пример 9">
{{#widget:Algoviewer
|url=XML_example_009/Example_009.html
|width=1300
|height=800
|border=1
}}
<br>
<center>
Чисто последовательная структура в 2D-представлении
</center>
</tab>

<tab name="Пример 10">
{{#widget:Algoviewer
|url=XML_example_010/Example_010.html
|width=1300
|height=800
|border=1
}}
<br>
<center>
Чисто последовательная структура в 2D-представлении
</center>
</tab>

<tab name="Пример 11">
{{#widget:Algoviewer
|url=XML_example_011/Example_011.html
|width=1300
|height=800
|border=1
}}
<br>
<center>
Чисто последовательная структура в 2D-представлении
</center>
</tab>

<tab name="Пример 12">
{{#widget:Algoviewer
|url=XML_example_012/Example_012.html
|width=1300
|height=800
|border=1
}}
<br>
<center>
Чисто последовательная структура в 2D-представлении
</center>
</tab>

<tab name="Пример 13">
{{#widget:Algoviewer
|url=XML_example_013/Example_013.html
|width=1300
|height=800
|border=1
}}
<br>
<center>
Чисто последовательная структура в 2D-представлении
</center>
</tab>

</tabs>
</center>

<math>(x, y, z) -> (0, 0, \sqrt{(x^2 + y^2 + z^2)})</math>

Участник:VolkovNikita94

2018-04-22T09:56:47Z

VolkovNikita94:

Участник:VolkovNikita94

2018-04-22T09:54:45Z

VolkovNikita94:

Перемножение плотных неособенных матриц (последовательный вещественный вариант)

2018-04-18T20:10:26Z

VolkovNikita94:

{{level-a}}

Основные авторы описания: [[Участник:Frolov|А.В.Фролов]], [[Участник:VadimVV|Вад.В.Воеводин]] ([[#Описание локальности данных и вычислений|раздел 2.2]]), [[Участник:Teplov|А.М.Теплов]] (раздел [[#Масштабируемость алгоритма и его реализации|2.4]])

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

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

'''Перемножение матриц''' - одна из базовых задач в алгоритмах линейной алгебры, широко применяется в большом количестве разных методов.
Здесь мы рассмотрим умножение <math>C = AB</math>  плотных неособенных матриц (последовательный вещественный вариант), то есть тот вариант, где никак не используются ни специальный вид матрицы, ни ассоциативные свойства операции сложения<ref>В.В.Воеводин, Ю.А.Кузнецов. Матрицы и вычисления. М.: Наука, 1984.</ref>.

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

Исходные данные: плотная матрица <math>A</math> (элементы <math>a_{ij}</math>), плотная матрица <math>B</math> (элементы <math>b_{ij}</math>).

Вычисляемые данные: плотная матрица <math>C</math> (элементы <math>c_{ij}</math>).

Формулы метода:
:<math>
\begin{align}
c_{ij} = \sum_{k = 1}^{n} a_{ik} b_{kj}, \quad i \in [1, m], \quad j \in [1, l].
\end{align}
</math>

Существует также блочная версия метода, однако в данном описании разобран только точечный метод.

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

Вычислительное ядро перемножения плотных неособенных матриц можно составить из множественных (всего их <math>l</math>) вычислений умножения матрицы <math>A</math> на столбцы матрицы <math>B</math>, или (при более детальном рассмотрении), из множественных (всего их <math>ml</math>) скалярных произведений строк матрицы <math>A</math> на столбцы матрицы <math>B</math>:

:<math>\sum_{k = 1}^{n} a_{ik} b_{kj}</math>

в режиме накопления или без него, в зависимости от требований задачи.

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

Как уже записано в [[#Вычислительное ядро алгоритма|описании ядра алгоритма]], основную часть умножения матриц составляют множественные (всего <math>ml</math>) вычисления скалярных произведений строк матрицы <math>A</math> на столбцы матрицы <math>B</math>

:<math>\sum_{k = 1}^{n} a_{ik} b_{kj}</math>

в режиме накопления или без него.

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

Для всех <math>i</math> от <math>1</math> до <math>m</math> и для всех <math>j</math> от <math>1</math> до <math>l</math> выполняются

:<math>c_{ij} = \sum_{k = 1}^{n} a_{ik} b_{kj}</math>

Особо отметим, что вычисления сумм вида <math>\sum_{k = 1}^{n} a_{ik} b_{kj}</math> производят в режиме накопления прибавлением к текущему (временному) значению вычисляемого элемента матрицы <math>c_{ij}</math> произведений <math>a_{ik} b_{kj}</math> для <math>k</math> от <math>1</math> до <math>n</math>, '''c возрастанием''' <math>k</math>, вначале все элементы инициализируются нулями. При суммировании "по убыванию" общая схема принципиально не отличается и потому нами не рассматривается. Другие порядки выполнения суммирования приводят к изменению параллельных свойств алгоритма и будут рассматриваться нами в отдельных описаниях.

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

Для умножения двух квадратных матриц порядка <math>n</math> (т.е. при <math>m=n=l</math>) в последовательном (наиболее быстром) варианте требуется:

* по <math>n^3</math> умножений и сложений.

Для умножения матрицы размером <math>m</math> строк на <math>n</math> столбцов на матрицу размером <math>m</math> строк на <math>n</math> столбцов в последовательном (наиболее быстром) варианте требуется:

* по <math>mnl</math> умножений и сложений.

При этом использование режима накопления требует совершения умножений и сложений в режиме двойной точности (или использования функции вроде DPROD в Фортране), что ещё больше увеличивает затраты во времени, требуемом для выполнения умножения матриц.

При классификации по последовательной сложности, таким образом, алгоритм умножения матриц относится к алгоритмам ''с кубической сложностью'' (в случае неквадратных матриц - с ''трилинейной'').

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

Опишем [[глоссарий#Граф алгоритма|граф алгоритма]] как аналитически, так и в виде рисунка.

Граф алгоритма умножения плотных матриц состоит из одной группы вершин, расположенной в целочисленных узлах трёхмерной области, соответствующая ей операция <math>a+bc</math>.

Естественно введённые координаты области таковы:
* <math>i</math> — меняется в диапазоне от <math>1</math> до <math>m</math>, принимая все целочисленные значения;
* <math>j</math> — меняется в диапазоне от <math>1</math> до <math>l</math>, принимая все целочисленные значения;
* <math>k</math> — меняется в диапазоне от <math>1</math> до <math>n</math>, принимая все целочисленные значения.

Аргументы операции следующие:
*<math>a</math>:
** при <math>k = 1</math> константа <math>0</math>;
** при <math>k > 1</math> — результат срабатывания операции, соответствующей вершине с координатами <math>i, j, k-1</math>;
*<math>b</math> — элемент ''входных данных'', а именно <math>a_{ik}</math>;
*<math>c</math> - элемент ''входных данных'' <math>b_{kj}</math>;

Результат срабатывания операции является:
* при <math>k < n</math> - ''промежуточным данным'' алгоритма;
* при <math>k = n</math> - выходным данным <math>c_{ij}</math>.

[[file:Dense mtrx product.png|thumb|center|800px|Рисунок 1. Умножение плотных матриц с отображением выходных данных]]
<br/>

<center>
Интерактивное изображение графа алгоритма без входных и выходных данных для случая перемножения двух квадратных матриц порядка 3 и 4
</center>

{{#widget:Algoviewer
|url=mat_mul/mat_mul_3/Algo_view_matrix3.html
|width=600
|height=400
|border=1
}}

{{#widget:Algoviewer
|url=mat_mul/mat_mul_4/Algo_view_matrix4.html
|width=600
|height=400
|border=1
}}

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

Для алгоритма умножения квадратных матриц порядка n в параллельном варианте требуется последовательно выполнить следующие ярусы:

* по <math>n</math> ярусов умножений и сложений (в каждом из ярусов — <math>n^2</math> операций).

Для умножения матрицы размером <math>m</math> строк на <math>n</math> столбцов на матрицу размером <math>n</math> строк на <math>l</math> столбцов в последовательном (наиболее быстром) варианте требуется:

* по <math>n</math> ярусов умножений и сложений (в каждом из ярусов — <math>ml</math> операций).

При этом использование режима накопления требует совершения умножений и вычитаний в режиме двойной точности, а в параллельном варианте это означает, что практически все промежуточные вычисления для выполнения алгоритма в режиме накопления должны быть двойной точности. В отличие от последовательного варианта это означает некоторое увеличение требуемой памяти.

При классификации по высоте ЯПФ, таким образом, алгоритм умножения матриц относится к алгоритмам ''с линейной сложностью''. При классификации по ширине ЯПФ его сложность также будет ''квадратичной'' (для квадратных матриц) или ''билинейной'' (для матриц общего вида).

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

'''Входные данные''': матрица <math>A</math> (элементы <math>a_{ij}</math>), матрица <math>B</math> (элементы <math>b_{ij}</math>)).

'''Объём входных данных''': <math>mn+nl</math>

'''Выходные данные''': матрица <math>C</math> (элементы <math>c_{ij}</math>).

'''Объём выходных данных''': <math>ml</math>

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

Соотношение последовательной и параллельной сложности в случае неограниченных ресурсов, как хорошо видно, является ''квадратичным'' или ''билинейным'' (отношение кубической или трилинейной к линейной).

При этом вычислительная мощность алгоритма умножения матриц, как отношение числа операций к суммарному объему входных и выходных данных – ''линейно''.

При этом алгоритм умножения матриц полностью детерминирован. Использование другого порядка выполнения ассоциативных операций в данной версии нами не рассматривается.

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

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

В простейшем варианте алгоритм умножения матриц на Фортране можно записать так:

<source lang="fortran">

DO I = 1, M
DO J = 1, L
S = 0.
DO K = 1, N
S = S + DPROD(A(I,K), B(K,J))
END DO
C(I, J) = S
END DO
END DO
</source>
При этом для реализации режима накопления переменная <math>S</math> должна быть двойной точности.

=== Локальность данных и вычислений ===
==== Локальность реализации алгоритма ====
===== Структура обращений в память и качественная оценка локальности =====

[[file:matrmult 1.PNG|thumb|center|700px|Рисунок 2. Профили обращений для 6 вариантов перемножения матриц]]

На рис.2 представлены 6 профилей обращений для различных вариантов классического перемножения матриц (в зависимости от выбранного порядка циклов). На каждом профиле хорошо выделяются фрагменты профилей для 3-х массивов, используемых в программе. При этом порядок обращений к разным массивам во всех 6 вариантах один и тот же; т.е. взаимодействие между массивами везде устроен одинаково. В этом случае отличия в локальности задаются внутренним строением фрагментов профиля для каждого массива в отдельности.

Исходя из исходного кода, можно увидеть, что всего встречается 6 разных видов фрагментов для отдельных массивов (эти виды выделены на рис.2 зеленым). Стоит сделать два уточнения: 1) профиль для результирующего массива С всегда в 2 раза больше, поскольку к элементам этого массива всегда происходят по два обращения подряд; 2) если во внутреннем цикле используется элементы массива, то обращение к этому элементу выносится за пределы внутреннего цикла (в цикле используется скалярная переменная вместо него).

Также заранее отметим, что рисунки по профилям получаются следующим образом: строится рисунок по общему профилю, после чего из него оставляется только часть для рассматриваемого массива. Доля обращений к одному массиву может меняться, поэтому и частота обращений на каждом рисунке может в значительной степени отличаться.

Рассмотрим подробнее каждый из данных 6 фрагментов на примере массива С.

'''Фрагмент 1.''' На рис.3 показано начало фрагмента 1 (здесь и далее начало фрагмента соответствует выделенной оранжевой области на рис.2). Можно увидеть, что данный фрагмент устроен достаточно просто: выполняется перебор некоторого блока элементов массива, затем данный перебор циклически повторяется. После этого происходит переход к следующему блоку элементов массива, и выполняется тот же перебор в цикле.

Если рассмотреть фрагмент более подробно (рис.4), можно увидеть, что каждый перебор является на самом деле последовательным перебором, при этом к каждому элементу происходит обращение дважды.

В результате можно сделать вывод, что фрагмент 1 обладает высокой пространственной локальностью (из-за последовательного перебора и последовательной смены блоков перебора), а также высокой временно́й локальностью (из-за двойного обращения к элементам, а также сгруппированности всех обращений к одному элементу в рамках одного блока перебора).

[[file:matrmult 2.PNG|thumb|center|700px|Рисунок 3. Начало фрагмента 1]]
[[file:matrmult 3.PNG|thumb|center|700px|Рисунок 4. Начало фрагмента 1, первые 3 итерации]]

'''Фрагмент 2.''' На рис.5 представлено начало фрагмента 2. Видно, что данный фрагмент также представляет собой перебор элементов массива в цикле, однако в данном случае на каждой итерации цикла перебираются сразу все элементы массива, а не только элементы одного блока. При более подробном рассмотрении итерации (рис.6) видно, что здесь также происходит именно последовательный перебор, и также к каждому элементу обращение происходит дважды (поскольку это массив С).

[[file:matrmult 4.PNG|thumb|center|700px|Рисунок 5. Начало фрагмента 2]]
[[file:matrmult 5.PNG|thumb|center|700px|Рисунок 6. Начало фрагмента 2, часть первой итерации]]

Такой фрагмент также обладает высокой пространственной локальностью, однако временна́я локальность несколько ниже, чем во фрагменте 1. Это связано с тем, что на каждой итерации цикла перебираются все элементы массива, а не только отдельный блок, т.е. повторные обращения происходят реже.

'''Фрагмент 3.''' Начало данного фрагмента представлено на рисунке 7. Данный профиль является последовательным перебором всех элементов массива, однако более подробное рассмотрение показывает, что к каждому элементу происходит обращение дважды, при этом между обращениями происходит достаточно много других обращений. Это связано с указанным ранее замечанием касательно вынесения повторяющегося обращения за предел внутреннего цикла.

[[file:matrmult 6.PNG|thumb|center|700px|Рисунок 7. Начало фрагмента 3]]
[[file:matrmult 7.PNG|thumb|center|700px|Рисунок 8. Начало фрагмента 3, первые несколько обращений]]

Такой фрагмент также обладает высокой пространственной локальностью, однако очень низкой временно́й, поскольку к каждому элементу обращение происходит только два раза.

'''Фрагмент 4.''' По началу фрагмента 4 видно, что профиль снова состоит из перебора всех элементов массива, однако на этот раз перебор не последовательный, а с некоторым шагом. Также можно заметить, что на каждой новой итерации перебор с шагом начинается с элемента, индекс которого немного больше, чем на предыдущей итерации. В данном случае нет нужды рассматривать профиль более подробно, поскольку из данного рисунка можно получить всю необходимую информацию.

По сравнению с предыдущим фрагментом, данный профиль обладает более низкой пространственной локальностью, поскольку перебор элементов идет с шагом, и также очень низкой временно́й локальностью, поскольку на каждой итерации происходят обращения к новым элементам.

[[file:matrmult 8.PNG|thumb|center|700px|Рисунок 9. Начало фрагмента 4]]

'''Фрагмент 5.''' В отличие от предыдущих фрагментов, исходя из визуализации начала данного фрагмента (рис.9), сложно сделать выводы относительно структуры обращения в память. Однако более подробное рассмотрение (рис.10) показывает, что данный профиль практически идентичен профилю предыдущего фрагмента. Более того, фрагмент 5 на самом деле состоит из итерационно повторяющихся фрагментов 4.

[[file:matrmult 9.PNG|thumb|center|700px|Рисунок 10. Начало фрагмента 5]]
[[file:matrmult 10.PNG|thumb|center|700px|Рисунок 11. Начало фрагмента 5, первые несколько итераций]]

Данный фрагмент обладает по сравнению с фрагментом 4 практически такой же пространственной локальностью, однако более высокой временной локальностью. Причина в обоих случаях одна – в данном случае тот же набор обращений повторяется несколько раз.

'''Фрагмент 6.''' Данный фрагмент, представленный на рис.12 и рис.13, так же сильно напоминает фрагмент 5, но с одним отличием. Во фрагменте 5 несколько раз повторяется фрагмент 4, в рамках которого выполняется несколько итераций, и на каждой итерации внутри фрагмента 4 используются разные элементы (поскольку первый элемент сдвигается на 1). В случае данного фрагмента выполняются все те же итерации, но в перемешанном виде. Сначала выполняются все итерации, начинающиеся с одного и того же элемента; затем все итерации, который начинаются с элемента, чей индекс идет следующим; и т.д.

Такой фрагмент обладает более высокой и пространственной, и временно́й локальностью по сравнению с фрагментом 5, поскольку обращения в одним и тем же элементам расположены ближе друг к другу в профиле.

[[file:matrmult 11.PNG|thumb|center|700px|Рисунок 12. Начало фрагмента 6]]
[[file:matrmult 12.PNG|thumb|center|700px|Рисунок 13. Начало фрагмента 6, первые несколько итераций]]

В итоге можно сказать, что наиболее низкой локальностью в целом обладают фрагменты 5 и 6. Фрагмент 4 также обладает низкой локальностью, однако содержит значительно меньшее число обращений, а значит, привносит меньший вклад в общий профиль обращений. Это позволяет определить, что наименее эффективными с точки зрения работы с памятью являются варианты kji и jki, поскольку каждый из них содержит фрагменты 5 и 6. Далее идут варианты ijk и jik – в них по одному такому фрагменту. Самые лучшие варианты – ikj и kij.

===== Количественная оценка локальности =====

Основные фрагменты реализации, на основе которых были получены количественные оценки, приведены [http://git.algowiki-project.org/Voevodin/locality/blob/master/benchmarks/matrix_mult/matrix_mult.h здесь] (функция Kernel***, где *** - порядок циклов (напр., KernelIJK) ). Условия запуска описаны [http://git.algowiki-project.org/Voevodin/locality/blob/master/README.md здесь].

Первая оценка выполняется на основе характеристики daps, которая оценивает число выполненных обращений (чтений и записей) в память в секунду. Данная характеристика является аналогом оценки flops применительно к работе с памятью и является в большей степени оценкой производительности взаимодействия с памятью, чем оценкой локальности. Однако она служит хорошим источником информации, в том числе для сравнения с результатами по следующей характеристике cvg.

На рис.14 приведены значения daps для реализаций распространенных алгоритмов, отсортированные по возрастанию (чем больше daps, тем в общем случае выше производительность). Можно увидеть, что, как и предполагалось наиболее эффективными являются варианты kij,ikj. Заметно хуже результат у вариантов jik,ijk, при этом эти варианты практически равны между собой. Самый плохой результат ожидаемо у вариантов jki,kji.

[[file:matrmult daps ru.PNG|thumb|center|700px|Рисунок 14. Сравнение значений оценки daps]]

Вторая характеристика – cvg – предназначена для получения более машинно-независимой оценки локальности. Она определяет, насколько часто в программе необходимо подтягивать данные в кэш-память. Соответственно, чем меньше значение cvg, тем реже это нужно делать, тем лучше локальность.

На рис.15 приведены значения cvg для того же набора реализаций, отсортированные по убыванию (чем меньше cvg, тем в общем случае выше локальность). Относительное сравнение результатов по cvg в целом повторяет результаты daps.

[[file:matrmult cvg.PNG|thumb|center|700px|Рисунок 15. Сравнение значений оценки cvg]]

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

[[file:Масштабируемость перемножения матриц производительность.png|thumb|center|700px|Рисунок 16. Параллельная реализация произведения матриц Максимальная производительность. ]]
[[file:Масштабируемость параллельной реализации перемножения матриц Эффективность.png|thumb|center|700px|Рисунок 17. Параллельная реализация произведения матриц Максимальная эффективность. ]]
Набор изменяемых параметров запуска реализации алгоритма и границы значений параметров алгоритма:
* число процессоров [4 : 1024]
* размерность матрицы [1024 : 20480]
Эффективность выполнения реализации алгоритма
* Минимальная эффективность 4,71%
* Максимальная эффективность 31,72%
Оценка масштабируемости
* По числу процессов: -0.0436 – при увеличении числа процессов эффективность убывает достаточно интенсивно на всей рассмотренной области изменений параметров запуска. Уменьшение эффективности на рассмотренной области работы параллельной программы звязано с увеличением числа пересылок с ростом числа процессов и как следствие ростом накладных расходов на организацию вычислений. Присутствует область, на которой при увеличении числа процессов эффективность возрастает, но при дальнейшем росте продолжает снижаться. Это объясняется декомпозицей данных, при которой наступает момент, когда размер матрицы позволяет блокам укладываться в КЭШ-память. Так же это подтверждает проявление этого явления, но со смещением по числу процессов, и при увеличении вычислительной сложности задачи.
* По размеру задачи: -0.0255 – при увеличении размера задачи эффективность в целом уменьшается по рассматриваемой области, хотя и менее интенсивно, чем при увеличении числа процессов. Снижение эффективности объясняется тем, что при росте вычислительной сложности существенно возрастают объемы передаваемых данных. Присутствует область возрастания эффективности, на всех рассмотренных размерах матрицы. Это объясняется тем, что при малом размере задачи данные хорошо укладываются в КЭШ память, что приводит к высокой эффективности работы приложения при малом размере задачи. При дальнейшем увеличении размера эффективность уменьшается при выходе за границы КЭШ-памяти.
* По двум направлениям: -0.000968 – при рассмотрении увеличения, как вычислительной сложности, так и числа процессов по всей рассмотренной области значений уменьшается, интенсивность уменьшения эффективности не очень высока. В совокупности с тем фактом, что разница между максимальной и минимальной эффективностью на рассмотренной области значений параметров составляет почти 25% говорит о том, что уменьшение эффективности по всей области довольно равномерное, но интенсивно лишь в не очень больших участках по площади. На остальной области значений параметров изменения эффективности не столь значительны и находятся на приблизительно одном и том же уровне.

[http://git.algowiki-project.org/Teplov/Scalability/blob/master/matrixmult/matrixmult.c Реализация алгоритма на языке C].

=== Динамические характеристики и эффективность реализации алгоритма ===
=== Выводы для классов архитектур ===
=== Существующие реализации алгоритма ===

== Литература ==
<references />

[[Категория:Законченные статьи]]
[[Категория:Матричные операции]]

[[En:Dense matrix multiplication (serial version for real matrices)]]

2017-12-02T19:09:25Z

VolkovNikita94: Отмена правки 24858, сделанной участником VolkovNikita94 (обс.)

<center>
<tabs>
<tab name="Пример 1">
{{#widget:Algoviewer
|url=XML_example_001/Example_001.html
|width=1300
|height=800
|border=1
}}
</tab>
</tabs>
</center>

<center>
<tabs>
<tab name="Пример 2">
{{#widget:Algoviewer
|url=XML_example_002/Example_002.html
|width=1300
|height=800
|border=1
}}
</tab>
</tabs>
</center>

<center>
<tabs>
<tab name="Пример 3">
{{#widget:Algoviewer
|url=XML_example_003/Example_003.html
|width=1300
|height=800
|border=1
}}
</tab>
</tabs>
</center>

<center>
<tabs>
<tab name="Пример 4">
{{#widget:Algoviewer
|url=XML_example_004/Example_004.html
|width=1300
|height=800
|border=1
}}
</tab>
</tabs>
</center>

<center>
<tabs>
<tab name="Пример 5">
{{#widget:Algoviewer
|url=XML_example_005/Example_005.html
|width=1300
|height=800
|border=1
}}
</tabs>
</center>

<center>
<tabs>
<tab name="Пример 6">
{{#widget:Algoviewer
|url=XML_example_006/Example_006.html
|width=1300
|height=800
|border=1
}}
</tab>
</tabs>
</center>

<center>
<tabs>
<tab name="Пример 7">
{{#widget:Algoviewer
|url=XML_example_007/Example_007.html
|width=1300
|height=800
|border=1
}}
</tab>
</tabs>
</center>

<center>
<tabs>
<tab name="Пример 8">
{{#widget:Algoviewer
|url=XML_example_008/Example_008.html
|width=1300
|height=800
|border=1
}}
</tab>
</tabs>
</center>

<center>
<tabs>
<tab name="Пример 9">
{{#widget:Algoviewer
|url=XML_example_009/Example_009.html
|width=1300
|height=800
|border=1
}}
</tab>
</tabs>
</center>

<center>
<tabs>
<tab name="Пример 10">
{{#widget:Algoviewer
|url=XML_example_010/Example_010.html
|width=1300
|height=800
|border=1
}}
</tab>
</tabs>
</center>

<center>
<tabs>
<tab name="Пример 11">
{{#widget:Algoviewer
|url=XML_example_011/Example_011.html
|width=1300
|height=800
|border=1
}}
</tab>
</tabs>
</center>

<center>
<tabs>
<tab name="Пример 12">
{{#widget:Algoviewer
|url=XML_example_012/Example_012.html
|width=1300
|height=800
|border=1
}}
</tab>
</tabs>
</center>

<center>
<tabs>
<tab name="Пример 13">
{{#widget:Algoviewer
|url=XML_example_013/Example_013.html
|width=1300
|height=800
|border=1
}}
</tab>
</tabs>
</center>