Алгоритм Кока-Янгера-Касами разбора грамматики в НФХ — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Пример работы)
м (Контекстно-свободная грамматика: тире)
 
(не показано 9 промежуточных версий 3 участников)
Строка 12: Строка 12:
 
* <tex>N</tex> {{---}} множество, элементы которого называют '''нетерминалами''' (англ. ''nonterminals'')
 
* <tex>N</tex> {{---}} множество, элементы которого называют '''нетерминалами''' (англ. ''nonterminals'')
 
* <tex>S</tex> {{---}} начальный символ грамматики (англ. ''start symbol'')
 
* <tex>S</tex> {{---}} начальный символ грамматики (англ. ''start symbol'')
* <tex>P</tex> {{---}} набор правил вывода (англ. ''production rules'' или ''productions'') вида <tex>A \rightarrow B_1 B_2 ... B_n</tex>, где <tex>A \in N</tex>, <tex>B_i \in \Sigma \cup N</tex>, то есть у которых левые части {{---}} одиночные нетерминалы, а правые - последовательности терминалов и нетерминалов.
+
* <tex>P</tex> {{---}} набор правил вывода (англ. ''production rules'' или ''productions'') вида <tex>A \rightarrow B_1 B_2 \ldots B_n</tex>, где <tex>A \in N</tex>, <tex>B_i \in \Sigma \cup N</tex>, то есть у которых левые части {{---}} одиночные нетерминалы, а правые {{---}} последовательности терминалов и нетерминалов.
 
}}
 
}}
 
 
=== Пример ===
 
=== Пример ===
  
Строка 35: Строка 34:
 
== Нормальная форма Хомского ==
 
== Нормальная форма Хомского ==
  
'''[[Нормальная форма Хомского]]''' - нормальная форма КС-грамматик, в которой все продукции имеют вид:
+
'''[[Нормальная форма Хомского]]''' {{---}} нормальная форма КС-грамматик, в которой все продукции имеют вид:
* A &rarr; a, где ''A'' - нетерминал, а ''a'' - терминал
+
* <tex>A \rightarrow a</tex>, где <tex>A</tex> {{---}} нетерминал, а <tex>a</tex> {{---}} терминал
* A &rarr; BC, где ''A'', ''B'', ''C'' - нетерминалы, причем ''B'' и ''C'' не являются начальными нетерминалами
+
* <tex>A \rightarrow BC</tex>, где <tex>A</tex>, <tex>B</tex>, <tex>C</tex> {{---}} нетерминалы, причем <tex>B</tex> и <tex>C</tex> не являются начальными нетерминалами
* S &rarr; ε, где S - начальный нетерминал и ε - пустая строка (данная продукция необходима, если в языке присуствует пустая строка)
+
* <tex>S \rightarrow \varepsilon</tex>, где <tex>S</tex> {{---}} начальный нетерминал и <tex>\varepsilon</tex> {{---}} пустая строка (данная продукция необходима, если в языке присуствует пустая строка)
  
[[Нормальная форма Хомского|Можно показать]], что любую КС-грамматику можно привести к нормальной форме Хомского, поэтому алгоритм является в этом плане универсальным.
+
[[Нормальная форма Хомского|Можно показать]], что любую КС-грамматику можно привести к нормальной форме Хомского.
  
 
== Алгоритм ==
 
== Алгоритм ==
'''Алгоритм Кока-Янгера-Касами''' (англ. ''Cocke-Younger-Kasami algorithm'', англ. ''CYK-алгоритм'') {{---}} универсальный алгоритм, позволяющий по слову узнать, выводимо ли оно в заданной КС-грамматике в нормальной форме Хомского.
+
'''Алгоритм Кока-Янгера-Касами''' (англ. ''Cocke-Younger-Kasami algorithm'', англ. ''CYK-алгоритм'') {{---}} алгоритм, позволяющий по слову узнать, выводимо ли оно в заданной КС-грамматике в нормальной форме Хомского. Любую КС-грамматику можно привести к НФХ, поэтому алгоритм является универсальным для любой КС-грамматики.
Будем решать задачу [[Динамическое_программирование|динамическим программированием]]. Дана строка <tex>w</tex> размером <tex>n</tex>. Заведем для неё трехмерный массив <tex>d</tex> размером <tex>|N| \times n \times n</tex>, состоящий из логических значений, и <tex>d[A][i][j] = true</tex> тогда и только тогда, когда из нетерминала <tex>A</tex> правилами грамматики можно вывести подстроку <tex>w[i \dots j]</tex>.
+
 
 +
Будем решать задачу [[Динамическое_программирование|динамическим программированием]]. Дана строка <tex>w</tex> размером <tex>n</tex>. Заведем для неё трехмерный массив <tex>d</tex> размером <tex>|N| \times n \times n</tex>, состоящий из логических значений, и <tex>d[A][i][j] = true \ </tex> тогда и только тогда, когда из нетерминала <tex>A</tex> правилами грамматики можно вывести подстроку <tex>w[i \ldots j]</tex>.
  
 
Рассмотрим все пары <tex>\lbrace \langle j, i \rangle | j-i=m \rbrace</tex>, где <tex>m</tex> {{---}} константа и <tex>m < n</tex>.
 
Рассмотрим все пары <tex>\lbrace \langle j, i \rangle | j-i=m \rbrace</tex>, где <tex>m</tex> {{---}} константа и <tex>m < n</tex>.
  
* <tex>i = j</tex>. Инициализируем массив для всех нетерминалов, из которых выводится какой-либо символ строки <tex>w</tex>. В таком случае <tex>d[A][i][i] = true</tex>, если в грамматике <tex>\Gamma</tex> присутствует правило <tex>A \rightarrow w[i]</tex>. Иначе <tex>d[A][i][i] = false</tex>.
+
* <tex>i = j</tex>. Инициализируем массив для всех нетерминалов, из которых выводится какой-либо символ строки <tex>w</tex>. В таком случае <tex>d[A][i][i] = true \ </tex>, если в грамматике <tex>\Gamma</tex> присутствует правило <tex>A \rightarrow w[i]</tex>. Иначе <tex>d[A][i][i] = false</tex>.
  
* <tex>i \ne j</tex>. Значения для всех нетерминалов и пар <tex>\lbrace \langle j', i' \rangle | j' - i' < m \rbrace</tex> уже вычислены, поэтому <tex>d[A][i][j] = \bigvee\limits_{A \rightarrow BC}\bigvee\limits_{k = i}^{j-1} d[B][i][k] \wedge d[C][k+1][j]</tex>. То есть, подстроку <tex>w[i \dots j]</tex> можно вывести из нетерминала <tex>A</tex>, если существует продукция вида <tex>A \rightarrow BC</tex> и такое <tex>k</tex>, что подстрока <tex>w[i \dots k]</tex> выводима из <tex>B</tex>, а подстрока <tex>w[k + 1 \dots j]</tex> выводится из <tex>C</tex>.
+
* <tex>i \ne j</tex>. Значения для всех нетерминалов и пар <tex>\lbrace \langle j', i' \rangle | j' - i' < m \rbrace</tex> уже вычислены, поэтому <tex>d[A][i][j] = \bigvee\limits_{A \rightarrow BC}\bigvee\limits_{k = i}^{j-1} d[B][i][k] \wedge d[C][k+1][j] \ \ </tex>. То есть, подстроку <tex>w[i \ldots j]</tex> можно вывести из нетерминала <tex>A</tex>, если существует продукция вида <tex>A \rightarrow BC</tex> и такое <tex>k</tex>, что подстрока <tex>w[i \ldots k]</tex> выводима из <tex>B</tex>, а подстрока <tex>w[k + 1 \ldots j]</tex> выводится из <tex>C</tex>.
 
[[Файл:CYK_rule_2.jpg|400px]]
 
[[Файл:CYK_rule_2.jpg|400px]]
  
Строка 58: Строка 58:
  
 
=== Количество способов вывести слово ===
 
=== Количество способов вывести слово ===
Если массив будет хранить целые числа, а формулу заменить на <tex>d[A][i][j] = \sum\limits_{A \rightarrow BC}\sum\limits_{k = i}^{j-1} d[B][i][k] \cdot d[C][k + 1][j]</tex>, то <tex>d[A][i][j]</tex> {{---}} количество способов получить подстроку <tex>w[i \dots j]</tex> из нетерминала <tex>A</tex>.
+
Если массив будет хранить целые числа, а формулу заменить на <tex>d[A][i][j] = \sum\limits_{A \rightarrow BC}\sum\limits_{k = i}^{j-1} d[B][i][k] \cdot d[C][k + 1][j] \ \ </tex>, то <tex>d[A][i][j]</tex> {{---}} количество способов получить подстроку <tex>w[i \ldots j]</tex> из нетерминала <tex>A</tex>.
  
 
=== Минимальная стоимость вывода слова ===
 
=== Минимальная стоимость вывода слова ===
Пусть <tex>H(A \rightarrow BC)</tex> {{---}} стоимость вывода по правилу <tex>A \rightarrow BC</tex>. Тогда, если использовать формулу <tex>d[A][i][j] = \min\limits_{A \rightarrow BC} \min\limits_{k = i}^{j-1}  ( d[B][i][k] + d[C][k + 1][j] + H(A \rightarrow BC) )</tex>, то <tex>d[A][i][j]</tex> {{---}} минимальная стоимость вывода подстроки <tex>w[i \dots j]</tex> из нетерминала <tex>A</tex>.
+
Пусть <tex>H(A \rightarrow BC)</tex> {{---}} стоимость вывода по правилу <tex>A \rightarrow BC</tex>. Тогда, если использовать формулу <tex>d[A][i][j] = \min\limits_{A \rightarrow BC} \min\limits_{k = i}^{j-1}  ( d[B][i][k] + d[C][k + 1][j] + H(A \rightarrow BC) ) \ \ </tex>, то <tex>d[A][i][j]</tex> {{---}} минимальная стоимость вывода подстроки <tex>w[i \ldots j]</tex> из нетерминала <tex>A</tex>.
  
 
Таким образом, задача о выводе в КС-грамматике в нормальной форме Хомского является частным случаем задачи динамического программирования на подотрезке.
 
Таким образом, задача о выводе в КС-грамматике в нормальной форме Хомского является частным случаем задачи динамического программирования на подотрезке.
Строка 76: Строка 76:
  
 
<tex>\begin{array}{l l}   
 
<tex>\begin{array}{l l}   
  A \rightarrow \varepsilon|BB|CD\\
+
  A \rightarrow \varepsilon\ |\ BB\ |\ CD\\
  B \rightarrow BB|CD\\
+
  B \rightarrow BB\ |\ CD\\
 
  C \rightarrow (\\
 
  C \rightarrow (\\
  D \rightarrow BE|)\\
+
  D \rightarrow BE\ |\ )\\
 
  E \rightarrow )\\
 
  E \rightarrow )\\
 
\end{array}</tex>
 
\end{array}</tex>
  
Дано слово <tex>w = $()(())$</tex>.
+
Дано слово <tex>w = ()(())</tex>.
  
  
 
Инициализация массива <tex>d</tex>.
 
Инициализация массива <tex>d</tex>.
  
 
+
{| border="1" class="wikitable" style="width: 150px; height: 150px; float: left;"  
{| border="1" style="width: 150px; height: 150px; float: left;"  
 
 
! colspan="7" style="background:#ffdead;"|A
 
! colspan="7" style="background:#ffdead;"|A
 
|-
 
|-
! style="background:#efefef;"|
+
!  
! style="background:#efefef;"|1
+
! 1
! style="background:#efefef;"|2
+
! 2
! style="background:#efefef;"|3
+
! 3
! style="background:#efefef;"|4
+
! 4
! style="background:#efefef;"|5
+
! 5
! style="background:#efefef;"|6
+
! 6
 
|-
 
|-
! style="background:#efefef;"|1
+
! 1
 
|  
 
|  
 
|  
 
|  
Строка 108: Строка 107:
 
|  
 
|  
 
|-
 
|-
! style="background:#efefef;"|2
+
! 2
 
|  
 
|  
 
|  
 
|  
Строка 116: Строка 115:
 
|  
 
|  
 
|-
 
|-
! style="background:#efefef;"|3
+
! 3
 
|  
 
|  
 
|  
 
|  
Строка 124: Строка 123:
 
|  
 
|  
 
|-
 
|-
! style="background:#efefef;"|4
+
! 4
 
|  
 
|  
 
|  
 
|  
Строка 132: Строка 131:
 
|  
 
|  
 
|-
 
|-
! style="background:#efefef;"|5
+
! 5
 
|  
 
|  
 
|  
 
|  
Строка 140: Строка 139:
 
|  
 
|  
 
|-
 
|-
! style="background:#efefef;"|6
+
! 6
 
|  
 
|  
 
|  
 
|  
Строка 148: Строка 147:
 
|  
 
|  
 
|}
 
|}
{| border="1" style="width: 150px; height: 150px; float: left;"  
+
{| border="1" class="wikitable" style="width: 150px; height: 150px; float: left;"  
 
! colspan="7" style="background:#ffdead;"|B
 
! colspan="7" style="background:#ffdead;"|B
 
|-
 
|-
! style="background:#efefef;"|
+
!  
! style="background:#efefef;"|1
+
! 1
! style="background:#efefef;"|2
+
! 2
! style="background:#efefef;"|3
+
! 3
! style="background:#efefef;"|4
+
! 4
! style="background:#efefef;"|5
+
! 5
! style="background:#efefef;"|6
+
! 6
 
|-
 
|-
! style="background:#efefef;"|1
+
! 1
 
|  
 
|  
 
|  
 
|  
Строка 167: Строка 166:
 
|  
 
|  
 
|-
 
|-
! style="background:#efefef;"|2
+
! 2
 
|  
 
|  
 
|  
 
|  
Строка 175: Строка 174:
 
|  
 
|  
 
|-
 
|-
! style="background:#efefef;"|3
+
! 3
 
|  
 
|  
 
|  
 
|  
Строка 183: Строка 182:
 
|  
 
|  
 
|-
 
|-
! style="background:#efefef;"|4
+
! 4
 
|  
 
|  
 
|  
 
|  
Строка 191: Строка 190:
 
|  
 
|  
 
|-
 
|-
! style="background:#efefef;"|5
+
! 5
 
|  
 
|  
 
|  
 
|  
Строка 199: Строка 198:
 
|  
 
|  
 
|-
 
|-
! style="background:#efefef;"|6
+
! 6
 
|  
 
|  
 
|  
 
|  
Строка 207: Строка 206:
 
|  
 
|  
 
|}
 
|}
{| border="1" style="width: 150px; height: 150px; float: left;"  
+
{| border="1" class="wikitable" style="width: 150px; height: 150px; float: left;"  
 
! colspan="7" style="background:#ffdead;"|C
 
! colspan="7" style="background:#ffdead;"|C
 
|-
 
|-
! style="background:#efefef;"|
+
!  
! style="background:#efefef;"|1
+
! 1
! style="background:#efefef;"|2
+
! 2
! style="background:#efefef;"|3
+
! 3
! style="background:#efefef;"|4
+
! 4
! style="background:#efefef;"|5
+
! 5
! style="background:#efefef;"|6
+
! 6
 
|-
 
|-
! style="background:#efefef;"|1
+
! 1
 
| align="center"| ●  
 
| align="center"| ●  
 
|  
 
|  
Строка 226: Строка 225:
 
|  
 
|  
 
|-
 
|-
! style="background:#efefef;"|2
+
! 2
 
|  
 
|  
 
|  
 
|  
Строка 234: Строка 233:
 
|  
 
|  
 
|-
 
|-
! style="background:#efefef;"|3
+
! 3
 
|  
 
|  
 
|  
 
|  
Строка 242: Строка 241:
 
|  
 
|  
 
|-
 
|-
! style="background:#efefef;"|4
+
! 4
 
|  
 
|  
 
|  
 
|  
Строка 250: Строка 249:
 
|  
 
|  
 
|-
 
|-
! style="background:#efefef;"|5
+
! 5
 
|  
 
|  
 
|  
 
|  
Строка 258: Строка 257:
 
|  
 
|  
 
|-
 
|-
! style="background:#efefef;"|6
+
! 6
 
|  
 
|  
 
|  
 
|  
Строка 266: Строка 265:
 
|  
 
|  
 
|}
 
|}
{| border="1" style="width: 150px; height: 150px; float: left;"  
+
{| border="1" class="wikitable" style="width: 150px; height: 150px; float: left;"  
 
! colspan="7" style="background:#ffdead;"|D
 
! colspan="7" style="background:#ffdead;"|D
 
|-
 
|-
! style="background:#efefef;"|
+
!  
! style="background:#efefef;"|1
+
! 1
! style="background:#efefef;"|2
+
! 2
! style="background:#efefef;"|3
+
! 3
! style="background:#efefef;"|4
+
! 4
! style="background:#efefef;"|5
+
! 5
! style="background:#efefef;"|6
+
! 6
 
|-
 
|-
! style="background:#efefef;"|1
+
! 1
 
|  
 
|  
 
|  
 
|  
Строка 285: Строка 284:
 
|  
 
|  
 
|-
 
|-
! style="background:#efefef;"|2
+
! 2
 
|  
 
|  
 
| align="center"| ●  
 
| align="center"| ●  
Строка 293: Строка 292:
 
|  
 
|  
 
|-
 
|-
! style="background:#efefef;"|3
+
! 3
 
|  
 
|  
 
|  
 
|  
Строка 301: Строка 300:
 
|  
 
|  
 
|-
 
|-
! style="background:#efefef;"|4
+
! 4
 
|  
 
|  
 
|  
 
|  
Строка 309: Строка 308:
 
|  
 
|  
 
|-
 
|-
! style="background:#efefef;"|5
+
! 5
 
|  
 
|  
 
|  
 
|  
Строка 317: Строка 316:
 
|  
 
|  
 
|-
 
|-
! style="background:#efefef;"|6
+
! 6
 
|  
 
|  
 
|  
 
|  
Строка 325: Строка 324:
 
| align="center"| ●  
 
| align="center"| ●  
 
|}
 
|}
{| border="1" style="width: 150px; height: 150px; "  
+
{| border="1" class="wikitable" style="width: 150px; height: 150px; float: left;"  
 
! colspan="7" style="background:#ffdead;"|E
 
! colspan="7" style="background:#ffdead;"|E
 
|-
 
|-
! style="background:#efefef;"|
+
!  
! style="background:#efefef;"|1
+
! 1
! style="background:#efefef;"|2
+
! 2
! style="background:#efefef;"|3
+
! 3
! style="background:#efefef;"|4
+
! 4
! style="background:#efefef;"|5
+
! 5
! style="background:#efefef;"|6
+
! 6
 
|-
 
|-
! style="background:#efefef;"|1
+
! 1
 
|  
 
|  
 
|  
 
|  
Строка 344: Строка 343:
 
|  
 
|  
 
|-
 
|-
! style="background:#efefef;"|2
+
! 2
 
|  
 
|  
 
| align="center"| ●  
 
| align="center"| ●  
Строка 352: Строка 351:
 
|  
 
|  
 
|-
 
|-
! style="background:#efefef;"|3
+
! 3
 
|  
 
|  
 
|  
 
|  
Строка 360: Строка 359:
 
|  
 
|  
 
|-
 
|-
! style="background:#efefef;"|4
+
! 4
 
|  
 
|  
 
|  
 
|  
Строка 368: Строка 367:
 
|  
 
|  
 
|-
 
|-
! style="background:#efefef;"|5
+
! 5
 
|  
 
|  
 
|  
 
|  
Строка 376: Строка 375:
 
|  
 
|  
 
|-
 
|-
! style="background:#efefef;"|6
+
! 6
 
|  
 
|  
 
|  
 
|  
Строка 384: Строка 383:
 
| align="center"| ●  
 
| align="center"| ●  
 
|}
 
|}
{| clear="both" |}
+
<div style="clear:both;"></div>
  
 
Заполнение массива <tex>d</tex>.
 
Заполнение массива <tex>d</tex>.
  
 
{| clear="both" |}
 
  
 
Итерация <tex>m = 1</tex>.
 
Итерация <tex>m = 1</tex>.
  
 
+
{| border="1" class="wikitable" style="width: 150px; height: 150px; float: left;"  
{| border="1" style="width: 150px; height: 150px; float: left;"  
 
 
! colspan="7" style="background:#ffdead;"|A
 
! colspan="7" style="background:#ffdead;"|A
 
|-
 
|-
! style="background:#efefef;"|
+
!  
! style="background:#efefef;"|1
+
! 1
! style="background:#efefef;"|2
+
! 2
! style="background:#efefef;"|3
+
! 3
! style="background:#efefef;"|4
+
! 4
! style="background:#efefef;"|5
+
! 5
! style="background:#efefef;"|6
+
! 6
 
|-
 
|-
! style="background:#efefef;"|1
+
! 1
 
|  
 
|  
 
| align="center"| ●  
 
| align="center"| ●  
Строка 413: Строка 409:
 
|  
 
|  
 
|-
 
|-
! style="background:#efefef;"|2
+
! 2
 
|  
 
|  
 
|  
 
|  
Строка 421: Строка 417:
 
|  
 
|  
 
|-
 
|-
! style="background:#efefef;"|3
+
! 3
 
|  
 
|  
 
|  
 
|  
Строка 429: Строка 425:
 
|  
 
|  
 
|-
 
|-
! style="background:#efefef;"|4
+
! 4
 
|  
 
|  
 
|  
 
|  
Строка 437: Строка 433:
 
|  
 
|  
 
|-
 
|-
! style="background:#efefef;"|5
+
! 5
 
|  
 
|  
 
|  
 
|  
Строка 445: Строка 441:
 
|  
 
|  
 
|-
 
|-
! style="background:#efefef;"|6
+
! 6
 
|  
 
|  
 
|  
 
|  
Строка 453: Строка 449:
 
|  
 
|  
 
|}
 
|}
{| border="1" style="width: 150px; height: 150px; float: left;"  
+
{| border="1" class="wikitable" style="width: 150px; height: 150px; float: left;"  
 
! colspan="7" style="background:#ffdead;"|B
 
! colspan="7" style="background:#ffdead;"|B
 
|-
 
|-
! style="background:#efefef;"|
+
!  
! style="background:#efefef;"|1
+
! 1
! style="background:#efefef;"|2
+
! 2
! style="background:#efefef;"|3
+
! 3
! style="background:#efefef;"|4
+
! 4
! style="background:#efefef;"|5
+
! 5
! style="background:#efefef;"|6
+
! 6
 
|-
 
|-
! style="background:#efefef;"|1
+
! 1
 
|  
 
|  
 
| align="center"| ●  
 
| align="center"| ●  
Строка 472: Строка 468:
 
|  
 
|  
 
|-
 
|-
! style="background:#efefef;"|2
+
! 2
 
|  
 
|  
 
|  
 
|  
Строка 480: Строка 476:
 
|  
 
|  
 
|-
 
|-
! style="background:#efefef;"|3
+
! 3
 
|  
 
|  
 
|  
 
|  
Строка 488: Строка 484:
 
|  
 
|  
 
|-
 
|-
! style="background:#efefef;"|4
+
! 4
 
|  
 
|  
 
|  
 
|  
Строка 496: Строка 492:
 
|  
 
|  
 
|-
 
|-
! style="background:#efefef;"|5
+
! 5
 
|  
 
|  
 
|  
 
|  
Строка 504: Строка 500:
 
|  
 
|  
 
|-
 
|-
! style="background:#efefef;"|6
+
! 6
 
|  
 
|  
 
|  
 
|  
Строка 512: Строка 508:
 
|  
 
|  
 
|}
 
|}
{| border="1" style="width: 150px; height: 150px; float: left;"  
+
{| border="1" class="wikitable" style="width: 150px; height: 150px; float: left;"  
 
! colspan="7" style="background:#ffdead;"|C
 
! colspan="7" style="background:#ffdead;"|C
 
|-
 
|-
! style="background:#efefef;"|
+
!  
! style="background:#efefef;"|1
+
! 1
! style="background:#efefef;"|2
+
! 2
! style="background:#efefef;"|3
+
! 3
! style="background:#efefef;"|4
+
! 4
! style="background:#efefef;"|5
+
! 5
! style="background:#efefef;"|6
+
! 6
 
|-
 
|-
! style="background:#efefef;"|1
+
! 1
 
| align="center"| ●  
 
| align="center"| ●  
 
|  
 
|  
Строка 531: Строка 527:
 
|  
 
|  
 
|-
 
|-
! style="background:#efefef;"|2
+
! 2
 
|  
 
|  
 
|  
 
|  
Строка 539: Строка 535:
 
|  
 
|  
 
|-
 
|-
! style="background:#efefef;"|3
+
! 3
 
|  
 
|  
 
|  
 
|  
Строка 547: Строка 543:
 
|  
 
|  
 
|-
 
|-
! style="background:#efefef;"|4
+
! 4
 
|  
 
|  
 
|  
 
|  
Строка 555: Строка 551:
 
|  
 
|  
 
|-
 
|-
! style="background:#efefef;"|5
+
! 5
 
|  
 
|  
 
|  
 
|  
Строка 563: Строка 559:
 
|  
 
|  
 
|-
 
|-
! style="background:#efefef;"|6
+
! 6
 
|  
 
|  
 
|  
 
|  
Строка 571: Строка 567:
 
|  
 
|  
 
|}
 
|}
{| border="1" style="width: 150px; height: 150px; float: left;"  
+
{| border="1" class="wikitable" style="width: 150px; height: 150px; float: left;"  
 
! colspan="7" style="background:#ffdead;"|D
 
! colspan="7" style="background:#ffdead;"|D
 
|-
 
|-
! style="background:#efefef;"|
+
!  
! style="background:#efefef;"|1
+
! 1
! style="background:#efefef;"|2
+
! 2
! style="background:#efefef;"|3
+
! 3
! style="background:#efefef;"|4
+
! 4
! style="background:#efefef;"|5
+
! 5
! style="background:#efefef;"|6
+
! 6
 
|-
 
|-
! style="background:#efefef;"|1
+
! 1
 
|  
 
|  
 
|  
 
|  
Строка 590: Строка 586:
 
|  
 
|  
 
|-
 
|-
! style="background:#efefef;"|2
+
! 2
 
|  
 
|  
 
| align="center"| ●  
 
| align="center"| ●  
Строка 598: Строка 594:
 
|  
 
|  
 
|-
 
|-
! style="background:#efefef;"|3
+
! 3
 
|  
 
|  
 
|  
 
|  
Строка 606: Строка 602:
 
|  
 
|  
 
|-
 
|-
! style="background:#efefef;"|4
+
! 4
 
|  
 
|  
 
|  
 
|  
Строка 614: Строка 610:
 
|  
 
|  
 
|-
 
|-
! style="background:#efefef;"|5
+
! 5
 
|  
 
|  
 
|  
 
|  
Строка 622: Строка 618:
 
|  
 
|  
 
|-
 
|-
! style="background:#efefef;"|6
+
! 6
 
|  
 
|  
 
|  
 
|  
Строка 630: Строка 626:
 
| align="center"| ●  
 
| align="center"| ●  
 
|}
 
|}
{| border="1" style="width: 150px; height: 150px; "  
+
{| border="1" class="wikitable" style="width: 150px; height: 150px; float: left;"  
 
! colspan="7" style="background:#ffdead;"|E
 
! colspan="7" style="background:#ffdead;"|E
 
|-
 
|-
! style="background:#efefef;"|
+
!  
! style="background:#efefef;"|1
+
! 1
! style="background:#efefef;"|2
+
! 2
! style="background:#efefef;"|3
+
! 3
! style="background:#efefef;"|4
+
! 4
! style="background:#efefef;"|5
+
! 5
! style="background:#efefef;"|6
+
! 6
 
|-
 
|-
! style="background:#efefef;"|1
+
! 1
 
|  
 
|  
 
|  
 
|  
Строка 649: Строка 645:
 
|  
 
|  
 
|-
 
|-
! style="background:#efefef;"|2
+
! 2
 
|  
 
|  
 
| align="center"| ●  
 
| align="center"| ●  
Строка 657: Строка 653:
 
|  
 
|  
 
|-
 
|-
! style="background:#efefef;"|3
+
! 3
 
|  
 
|  
 
|  
 
|  
Строка 665: Строка 661:
 
|  
 
|  
 
|-
 
|-
! style="background:#efefef;"|4
+
! 4
 
|  
 
|  
 
|  
 
|  
Строка 673: Строка 669:
 
|  
 
|  
 
|-
 
|-
! style="background:#efefef;"|5
+
! 5
 
|  
 
|  
 
|  
 
|  
Строка 681: Строка 677:
 
|  
 
|  
 
|-
 
|-
! style="background:#efefef;"|6
+
! 6
 
|  
 
|  
 
|  
 
|  
Строка 689: Строка 685:
 
| align="center"| ●  
 
| align="center"| ●  
 
|}
 
|}
{| clear="both" |}
+
<div style="clear:both;"></div>
  
 
Итерация <tex>m = 2</tex>.
 
Итерация <tex>m = 2</tex>.
  
 
+
{| border="1" class="wikitable" style="width: 150px; height: 150px; float: left;"  
{| border="1" style="width: 150px; height: 150px; float: left;"  
 
 
! colspan="7" style="background:#ffdead;"|A
 
! colspan="7" style="background:#ffdead;"|A
 
|-
 
|-
! style="background:#efefef;"|
+
!  
! style="background:#efefef;"|1
+
! 1
! style="background:#efefef;"|2
+
! 2
! style="background:#efefef;"|3
+
! 3
! style="background:#efefef;"|4
+
! 4
! style="background:#efefef;"|5
+
! 5
! style="background:#efefef;"|6
+
! 6
 
|-
 
|-
! style="background:#efefef;"|1
+
! 1
 
|  
 
|  
 
| align="center"| ●  
 
| align="center"| ●  
Строка 713: Строка 708:
 
|  
 
|  
 
|-
 
|-
! style="background:#efefef;"|2
+
! 2
 
|  
 
|  
 
|  
 
|  
Строка 721: Строка 716:
 
|  
 
|  
 
|-
 
|-
! style="background:#efefef;"|3
+
! 3
 
|  
 
|  
 
|  
 
|  
Строка 729: Строка 724:
 
|  
 
|  
 
|-
 
|-
! style="background:#efefef;"|4
+
! 4
 
|  
 
|  
 
|  
 
|  
Строка 737: Строка 732:
 
|  
 
|  
 
|-
 
|-
! style="background:#efefef;"|5
+
! 5
 
|  
 
|  
 
|  
 
|  
Строка 745: Строка 740:
 
|  
 
|  
 
|-
 
|-
! style="background:#efefef;"|6
+
! 6
 
|  
 
|  
 
|  
 
|  
Строка 753: Строка 748:
 
|  
 
|  
 
|}
 
|}
{| border="1" style="width: 150px; height: 150px; float: left;"  
+
{| border="1" class="wikitable" style="width: 150px; height: 150px; float: left;"  
 
! colspan="7" style="background:#ffdead;"|B
 
! colspan="7" style="background:#ffdead;"|B
 
|-
 
|-
! style="background:#efefef;"|
+
!  
! style="background:#efefef;"|1
+
! 1
! style="background:#efefef;"|2
+
! 2
! style="background:#efefef;"|3
+
! 3
! style="background:#efefef;"|4
+
! 4
! style="background:#efefef;"|5
+
! 5
! style="background:#efefef;"|6
+
! 6
 
|-
 
|-
! style="background:#efefef;"|1
+
! 1
 
|  
 
|  
 
| align="center"| ●  
 
| align="center"| ●  
Строка 772: Строка 767:
 
|  
 
|  
 
|-
 
|-
! style="background:#efefef;"|2
+
! 2
 
|  
 
|  
 
|  
 
|  
Строка 780: Строка 775:
 
|  
 
|  
 
|-
 
|-
! style="background:#efefef;"|3
+
! 3
 
|  
 
|  
 
|  
 
|  
Строка 788: Строка 783:
 
|  
 
|  
 
|-
 
|-
! style="background:#efefef;"|4
+
! 4
 
|  
 
|  
 
|  
 
|  
Строка 796: Строка 791:
 
|  
 
|  
 
|-
 
|-
! style="background:#efefef;"|5
+
! 5
 
|  
 
|  
 
|  
 
|  
Строка 804: Строка 799:
 
|  
 
|  
 
|-
 
|-
! style="background:#efefef;"|6
+
! 6
 
|  
 
|  
 
|  
 
|  
Строка 812: Строка 807:
 
|  
 
|  
 
|}
 
|}
{| border="1" style="width: 150px; height: 150px; float: left;"  
+
{| border="1" class="wikitable" style="width: 150px; height: 150px; float: left;"  
 
! colspan="7" style="background:#ffdead;"|C
 
! colspan="7" style="background:#ffdead;"|C
 
|-
 
|-
! style="background:#efefef;"|
+
!  
! style="background:#efefef;"|1
+
! 1
! style="background:#efefef;"|2
+
! 2
! style="background:#efefef;"|3
+
! 3
! style="background:#efefef;"|4
+
! 4
! style="background:#efefef;"|5
+
! 5
! style="background:#efefef;"|6
+
! 6
 
|-
 
|-
! style="background:#efefef;"|1
+
! 1
 
| align="center"| ●  
 
| align="center"| ●  
 
|  
 
|  
Строка 831: Строка 826:
 
|  
 
|  
 
|-
 
|-
! style="background:#efefef;"|2
+
! 2
 
|  
 
|  
 
|  
 
|  
Строка 839: Строка 834:
 
|  
 
|  
 
|-
 
|-
! style="background:#efefef;"|3
+
! 3
 
|  
 
|  
 
|  
 
|  
Строка 847: Строка 842:
 
|  
 
|  
 
|-
 
|-
! style="background:#efefef;"|4
+
! 4
 
|  
 
|  
 
|  
 
|  
Строка 855: Строка 850:
 
|  
 
|  
 
|-
 
|-
! style="background:#efefef;"|5
+
! 5
 
|  
 
|  
 
|  
 
|  
Строка 863: Строка 858:
 
|  
 
|  
 
|-
 
|-
! style="background:#efefef;"|6
+
! 6
 
|  
 
|  
 
|  
 
|  
Строка 871: Строка 866:
 
|  
 
|  
 
|}
 
|}
{| border="1" style="width: 150px; height: 150px; float: left;"  
+
{| border="1" class="wikitable" style="width: 150px; height: 150px; float: left;"  
 
! colspan="7" style="background:#ffdead;"|D
 
! colspan="7" style="background:#ffdead;"|D
 
|-
 
|-
! style="background:#efefef;"|
+
!  
! style="background:#efefef;"|1
+
! 1
! style="background:#efefef;"|2
+
! 2
! style="background:#efefef;"|3
+
! 3
! style="background:#efefef;"|4
+
! 4
! style="background:#efefef;"|5
+
! 5
! style="background:#efefef;"|6
+
! 6
 
|-
 
|-
! style="background:#efefef;"|1
+
! 1
 
|  
 
|  
 
|  
 
|  
Строка 890: Строка 885:
 
|  
 
|  
 
|-
 
|-
! style="background:#efefef;"|2
+
! 2
 
|  
 
|  
 
| align="center"| ●  
 
| align="center"| ●  
Строка 898: Строка 893:
 
|  
 
|  
 
|-
 
|-
! style="background:#efefef;"|3
+
! 3
 
|  
 
|  
 
|  
 
|  
Строка 906: Строка 901:
 
|  
 
|  
 
|-
 
|-
! style="background:#efefef;"|4
+
! 4
 
|  
 
|  
 
|  
 
|  
Строка 914: Строка 909:
 
| align="center"| ●  
 
| align="center"| ●  
 
|-
 
|-
! style="background:#efefef;"|5
+
! 5
 
|  
 
|  
 
|  
 
|  
Строка 922: Строка 917:
 
|  
 
|  
 
|-
 
|-
! style="background:#efefef;"|6
+
! 6
 
|  
 
|  
 
|  
 
|  
Строка 930: Строка 925:
 
| align="center"| ●  
 
| align="center"| ●  
 
|}
 
|}
{| border="1" style="width: 150px; height: 150px; "  
+
{| border="1" class="wikitable" style="width: 150px; height: 150px; float: left;"  
 
! colspan="7" style="background:#ffdead;"|E
 
! colspan="7" style="background:#ffdead;"|E
 
|-
 
|-
! style="background:#efefef;"|
+
!  
! style="background:#efefef;"|1
+
! 1
! style="background:#efefef;"|2
+
! 2
! style="background:#efefef;"|3
+
! 3
! style="background:#efefef;"|4
+
! 4
! style="background:#efefef;"|5
+
! 5
! style="background:#efefef;"|6
+
! 6
 
|-
 
|-
! style="background:#efefef;"|1
+
! 1
 
|  
 
|  
 
|  
 
|  
Строка 949: Строка 944:
 
|  
 
|  
 
|-
 
|-
! style="background:#efefef;"|2
+
! 2
 
|  
 
|  
 
| align="center"| ●  
 
| align="center"| ●  
Строка 957: Строка 952:
 
|  
 
|  
 
|-
 
|-
! style="background:#efefef;"|3
+
! 3
 
|  
 
|  
 
|  
 
|  
Строка 965: Строка 960:
 
|  
 
|  
 
|-
 
|-
! style="background:#efefef;"|4
+
! 4
 
|  
 
|  
 
|  
 
|  
Строка 973: Строка 968:
 
|  
 
|  
 
|-
 
|-
! style="background:#efefef;"|5
+
! 5
 
|  
 
|  
 
|  
 
|  
Строка 981: Строка 976:
 
|  
 
|  
 
|-
 
|-
! style="background:#efefef;"|6
+
! 6
 
|  
 
|  
 
|  
 
|  
Строка 989: Строка 984:
 
| align="center"| ●  
 
| align="center"| ●  
 
|}
 
|}
{| clear="both" |}
+
<div style="clear:both;"></div>
  
 
Итерация <tex>m = 3</tex>.
 
Итерация <tex>m = 3</tex>.
  
 
+
{| border="1" class="wikitable" style="width: 150px; height: 150px; float: left;"  
{| border="1" style="width: 150px; height: 150px; float: left;"  
 
 
! colspan="7" style="background:#ffdead;"|A
 
! colspan="7" style="background:#ffdead;"|A
 
|-
 
|-
! style="background:#efefef;"|
+
!  
! style="background:#efefef;"|1
+
! 1
! style="background:#efefef;"|2
+
! 2
! style="background:#efefef;"|3
+
! 3
! style="background:#efefef;"|4
+
! 4
! style="background:#efefef;"|5
+
! 5
! style="background:#efefef;"|6
+
! 6
 
|-
 
|-
! style="background:#efefef;"|1
+
! 1
 
|  
 
|  
 
| align="center"| ●  
 
| align="center"| ●  
Строка 1013: Строка 1007:
 
|  
 
|  
 
|-
 
|-
! style="background:#efefef;"|2
+
! 2
 
|  
 
|  
 
|  
 
|  
Строка 1021: Строка 1015:
 
|  
 
|  
 
|-
 
|-
! style="background:#efefef;"|3
+
! 3
 
|  
 
|  
 
|  
 
|  
Строка 1029: Строка 1023:
 
| align="center"| ●  
 
| align="center"| ●  
 
|-
 
|-
! style="background:#efefef;"|4
+
! 4
 
|  
 
|  
 
|  
 
|  
Строка 1037: Строка 1031:
 
|  
 
|  
 
|-
 
|-
! style="background:#efefef;"|5
+
! 5
 
|  
 
|  
 
|  
 
|  
Строка 1045: Строка 1039:
 
|  
 
|  
 
|-
 
|-
! style="background:#efefef;"|6
+
! 6
 
|  
 
|  
 
|  
 
|  
Строка 1053: Строка 1047:
 
|  
 
|  
 
|}
 
|}
{| border="1" style="width: 150px; height: 150px; float: left;"  
+
{| border="1" class="wikitable" style="width: 150px; height: 150px; float: left;"  
 
! colspan="7" style="background:#ffdead;"|B
 
! colspan="7" style="background:#ffdead;"|B
 
|-
 
|-
! style="background:#efefef;"|
+
!  
! style="background:#efefef;"|1
+
! 1
! style="background:#efefef;"|2
+
! 2
! style="background:#efefef;"|3
+
! 3
! style="background:#efefef;"|4
+
! 4
! style="background:#efefef;"|5
+
! 5
! style="background:#efefef;"|6
+
! 6
 
|-
 
|-
! style="background:#efefef;"|1
+
! 1
 
|  
 
|  
 
| align="center"| ●  
 
| align="center"| ●  
Строка 1072: Строка 1066:
 
|  
 
|  
 
|-
 
|-
! style="background:#efefef;"|2
+
! 2
 
|  
 
|  
 
|  
 
|  
Строка 1080: Строка 1074:
 
|  
 
|  
 
|-
 
|-
! style="background:#efefef;"|3
+
! 3
 
|  
 
|  
 
|  
 
|  
Строка 1088: Строка 1082:
 
| align="center"| ●  
 
| align="center"| ●  
 
|-
 
|-
! style="background:#efefef;"|4
+
! 4
 
|  
 
|  
 
|  
 
|  
Строка 1096: Строка 1090:
 
|  
 
|  
 
|-
 
|-
! style="background:#efefef;"|5
+
! 5
 
|  
 
|  
 
|  
 
|  
Строка 1104: Строка 1098:
 
|  
 
|  
 
|-
 
|-
! style="background:#efefef;"|6
+
! 6
 
|  
 
|  
 
|  
 
|  
Строка 1112: Строка 1106:
 
|  
 
|  
 
|}
 
|}
{| border="1" style="width: 150px; height: 150px; float: left;"  
+
{| border="1" class="wikitable" style="width: 150px; height: 150px; float: left;"  
 
! colspan="7" style="background:#ffdead;"|C
 
! colspan="7" style="background:#ffdead;"|C
 
|-
 
|-
! style="background:#efefef;"|
+
!  
! style="background:#efefef;"|1
+
! 1
! style="background:#efefef;"|2
+
! 2
! style="background:#efefef;"|3
+
! 3
! style="background:#efefef;"|4
+
! 4
! style="background:#efefef;"|5
+
! 5
! style="background:#efefef;"|6
+
! 6
 
|-
 
|-
! style="background:#efefef;"|1
+
! 1
 
| align="center"| ●  
 
| align="center"| ●  
 
|  
 
|  
Строка 1131: Строка 1125:
 
|  
 
|  
 
|-
 
|-
! style="background:#efefef;"|2
+
! 2
 
|  
 
|  
 
|  
 
|  
Строка 1139: Строка 1133:
 
|  
 
|  
 
|-
 
|-
! style="background:#efefef;"|3
+
! 3
 
|  
 
|  
 
|  
 
|  
Строка 1147: Строка 1141:
 
|  
 
|  
 
|-
 
|-
! style="background:#efefef;"|4
+
! 4
 
|  
 
|  
 
|  
 
|  
Строка 1155: Строка 1149:
 
|  
 
|  
 
|-
 
|-
! style="background:#efefef;"|5
+
! 5
 
|  
 
|  
 
|  
 
|  
Строка 1163: Строка 1157:
 
|  
 
|  
 
|-
 
|-
! style="background:#efefef;"|6
+
! 6
 
|  
 
|  
 
|  
 
|  
Строка 1171: Строка 1165:
 
|  
 
|  
 
|}
 
|}
{| border="1" style="width: 150px; height: 150px; float: left;"  
+
{| border="1" class="wikitable" style="width: 150px; height: 150px; float: left;"  
 
! colspan="7" style="background:#ffdead;"|D
 
! colspan="7" style="background:#ffdead;"|D
 
|-
 
|-
! style="background:#efefef;"|
+
!  
! style="background:#efefef;"|1
+
! 1
! style="background:#efefef;"|2
+
! 2
! style="background:#efefef;"|3
+
! 3
! style="background:#efefef;"|4
+
! 4
! style="background:#efefef;"|5
+
! 5
! style="background:#efefef;"|6
+
! 6
 
|-
 
|-
! style="background:#efefef;"|1
+
! 1
 
|  
 
|  
 
|  
 
|  
Строка 1190: Строка 1184:
 
|  
 
|  
 
|-
 
|-
! style="background:#efefef;"|2
+
! 2
 
|  
 
|  
 
| align="center"| ●  
 
| align="center"| ●  
Строка 1198: Строка 1192:
 
|  
 
|  
 
|-
 
|-
! style="background:#efefef;"|3
+
! 3
 
|  
 
|  
 
|  
 
|  
Строка 1206: Строка 1200:
 
|  
 
|  
 
|-
 
|-
! style="background:#efefef;"|4
+
! 4
 
|  
 
|  
 
|  
 
|  
Строка 1214: Строка 1208:
 
| align="center"| ●  
 
| align="center"| ●  
 
|-
 
|-
! style="background:#efefef;"|5
+
! 5
 
|  
 
|  
 
|  
 
|  
Строка 1222: Строка 1216:
 
|  
 
|  
 
|-
 
|-
! style="background:#efefef;"|6
+
! 6
 
|  
 
|  
 
|  
 
|  
Строка 1230: Строка 1224:
 
| align="center"| ●  
 
| align="center"| ●  
 
|}
 
|}
{| border="1" style="width: 150px; height: 150px; "  
+
{| border="1" class="wikitable" style="width: 150px; height: 150px; float: left;"  
 
! colspan="7" style="background:#ffdead;"|E
 
! colspan="7" style="background:#ffdead;"|E
 
|-
 
|-
! style="background:#efefef;"|
+
!  
! style="background:#efefef;"|1
+
! 1
! style="background:#efefef;"|2
+
! 2
! style="background:#efefef;"|3
+
! 3
! style="background:#efefef;"|4
+
! 4
! style="background:#efefef;"|5
+
! 5
! style="background:#efefef;"|6
+
! 6
 
|-
 
|-
! style="background:#efefef;"|1
+
! 1
 
|  
 
|  
 
|  
 
|  
Строка 1249: Строка 1243:
 
|  
 
|  
 
|-
 
|-
! style="background:#efefef;"|2
+
! 2
 
|  
 
|  
 
| align="center"| ●  
 
| align="center"| ●  
Строка 1257: Строка 1251:
 
|  
 
|  
 
|-
 
|-
! style="background:#efefef;"|3
+
! 3
 
|  
 
|  
 
|  
 
|  
Строка 1265: Строка 1259:
 
|  
 
|  
 
|-
 
|-
! style="background:#efefef;"|4
+
! 4
 
|  
 
|  
 
|  
 
|  
Строка 1273: Строка 1267:
 
|  
 
|  
 
|-
 
|-
! style="background:#efefef;"|5
+
! 5
 
|  
 
|  
 
|  
 
|  
Строка 1281: Строка 1275:
 
|  
 
|  
 
|-
 
|-
! style="background:#efefef;"|6
+
! 6
 
|  
 
|  
 
|  
 
|  
Строка 1289: Строка 1283:
 
| align="center"| ●  
 
| align="center"| ●  
 
|}
 
|}
{| clear="both" |}
+
<div style="clear:both;"></div>
  
 
Итерация <tex>m = 4</tex>.
 
Итерация <tex>m = 4</tex>.
  
 
+
{| border="1" class="wikitable" style="width: 150px; height: 150px; float: left;"  
{| border="1" style="width: 150px; height: 150px; float: left;"  
 
 
! colspan="7" style="background:#ffdead;"|A
 
! colspan="7" style="background:#ffdead;"|A
 
|-
 
|-
! style="background:#efefef;"|
+
!  
! style="background:#efefef;"|1
+
! 1
! style="background:#efefef;"|2
+
! 2
! style="background:#efefef;"|3
+
! 3
! style="background:#efefef;"|4
+
! 4
! style="background:#efefef;"|5
+
! 5
! style="background:#efefef;"|6
+
! 6
 
|-
 
|-
! style="background:#efefef;"|1
+
! 1
 
|  
 
|  
 
| align="center"| ●  
 
| align="center"| ●  
Строка 1313: Строка 1306:
 
|  
 
|  
 
|-
 
|-
! style="background:#efefef;"|2
+
! 2
 
|  
 
|  
 
|  
 
|  
Строка 1321: Строка 1314:
 
|  
 
|  
 
|-
 
|-
! style="background:#efefef;"|3
+
! 3
 
|  
 
|  
 
|  
 
|  
Строка 1329: Строка 1322:
 
| align="center"| ●  
 
| align="center"| ●  
 
|-
 
|-
! style="background:#efefef;"|4
+
! 4
 
|  
 
|  
 
|  
 
|  
Строка 1337: Строка 1330:
 
|  
 
|  
 
|-
 
|-
! style="background:#efefef;"|5
+
! 5
 
|  
 
|  
 
|  
 
|  
Строка 1345: Строка 1338:
 
|  
 
|  
 
|-
 
|-
! style="background:#efefef;"|6
+
! 6
 
|  
 
|  
 
|  
 
|  
Строка 1353: Строка 1346:
 
|  
 
|  
 
|}
 
|}
{| border="1" style="width: 150px; height: 150px; float: left;"  
+
{| border="1" class="wikitable" style="width: 150px; height: 150px; float: left;"  
 
! colspan="7" style="background:#ffdead;"|B
 
! colspan="7" style="background:#ffdead;"|B
 
|-
 
|-
! style="background:#efefef;"|
+
!  
! style="background:#efefef;"|1
+
! 1
! style="background:#efefef;"|2
+
! 2
! style="background:#efefef;"|3
+
! 3
! style="background:#efefef;"|4
+
! 4
! style="background:#efefef;"|5
+
! 5
! style="background:#efefef;"|6
+
! 6
 
|-
 
|-
! style="background:#efefef;"|1
+
! 1
 
|  
 
|  
 
| align="center"| ●  
 
| align="center"| ●  
Строка 1372: Строка 1365:
 
|  
 
|  
 
|-
 
|-
! style="background:#efefef;"|2
+
! 2
 
|  
 
|  
 
|  
 
|  
Строка 1380: Строка 1373:
 
|  
 
|  
 
|-
 
|-
! style="background:#efefef;"|3
+
! 3
 
|  
 
|  
 
|  
 
|  
Строка 1388: Строка 1381:
 
| align="center"| ●  
 
| align="center"| ●  
 
|-
 
|-
! style="background:#efefef;"|4
+
! 4
 
|  
 
|  
 
|  
 
|  
Строка 1396: Строка 1389:
 
|  
 
|  
 
|-
 
|-
! style="background:#efefef;"|5
+
! 5
 
|  
 
|  
 
|  
 
|  
Строка 1404: Строка 1397:
 
|  
 
|  
 
|-
 
|-
! style="background:#efefef;"|6
+
! 6
 
|  
 
|  
 
|  
 
|  
Строка 1412: Строка 1405:
 
|  
 
|  
 
|}
 
|}
{| border="1" style="width: 150px; height: 150px; float: left;"  
+
{| border="1" class="wikitable" style="width: 150px; height: 150px; float: left;"  
 
! colspan="7" style="background:#ffdead;"|C
 
! colspan="7" style="background:#ffdead;"|C
 
|-
 
|-
! style="background:#efefef;"|
+
!  
! style="background:#efefef;"|1
+
! 1
! style="background:#efefef;"|2
+
! 2
! style="background:#efefef;"|3
+
! 3
! style="background:#efefef;"|4
+
! 4
! style="background:#efefef;"|5
+
! 5
! style="background:#efefef;"|6
+
! 6
 
|-
 
|-
! style="background:#efefef;"|1
+
! 1
 
| align="center"| ●  
 
| align="center"| ●  
 
|  
 
|  
Строка 1431: Строка 1424:
 
|  
 
|  
 
|-
 
|-
! style="background:#efefef;"|2
+
! 2
 
|  
 
|  
 
|  
 
|  
Строка 1439: Строка 1432:
 
|  
 
|  
 
|-
 
|-
! style="background:#efefef;"|3
+
! 3
 
|  
 
|  
 
|  
 
|  
Строка 1447: Строка 1440:
 
|  
 
|  
 
|-
 
|-
! style="background:#efefef;"|4
+
! 4
 
|  
 
|  
 
|  
 
|  
Строка 1455: Строка 1448:
 
|  
 
|  
 
|-
 
|-
! style="background:#efefef;"|5
+
! 5
 
|  
 
|  
 
|  
 
|  
Строка 1463: Строка 1456:
 
|  
 
|  
 
|-
 
|-
! style="background:#efefef;"|6
+
! 6
 
|  
 
|  
 
|  
 
|  
Строка 1471: Строка 1464:
 
|  
 
|  
 
|}
 
|}
{| border="1" style="width: 150px; height: 150px; float: left;"  
+
{| border="1" class="wikitable" style="width: 150px; height: 150px; float: left;"  
 
! colspan="7" style="background:#ffdead;"|D
 
! colspan="7" style="background:#ffdead;"|D
 
|-
 
|-
! style="background:#efefef;"|
+
!  
! style="background:#efefef;"|1
+
! 1
! style="background:#efefef;"|2
+
! 2
! style="background:#efefef;"|3
+
! 3
! style="background:#efefef;"|4
+
! 4
! style="background:#efefef;"|5
+
! 5
! style="background:#efefef;"|6
+
! 6
 
|-
 
|-
! style="background:#efefef;"|1
+
! 1
 
|  
 
|  
 
|  
 
|  
Строка 1490: Строка 1483:
 
|  
 
|  
 
|-
 
|-
! style="background:#efefef;"|2
+
! 2
 
|  
 
|  
 
| align="center"| ●  
 
| align="center"| ●  
Строка 1498: Строка 1491:
 
|  
 
|  
 
|-
 
|-
! style="background:#efefef;"|3
+
! 3
 
|  
 
|  
 
|  
 
|  
Строка 1506: Строка 1499:
 
|  
 
|  
 
|-
 
|-
! style="background:#efefef;"|4
+
! 4
 
|  
 
|  
 
|  
 
|  
Строка 1514: Строка 1507:
 
| align="center"| ●  
 
| align="center"| ●  
 
|-
 
|-
! style="background:#efefef;"|5
+
! 5
 
|  
 
|  
 
|  
 
|  
Строка 1522: Строка 1515:
 
|  
 
|  
 
|-
 
|-
! style="background:#efefef;"|6
+
! 6
 
|  
 
|  
 
|  
 
|  
Строка 1530: Строка 1523:
 
| align="center"| ●  
 
| align="center"| ●  
 
|}
 
|}
{| border="1" style="width: 150px; height: 150px; "  
+
{| border="1" class="wikitable" style="width: 150px; height: 150px; float: left;"  
 
! colspan="7" style="background:#ffdead;"|E
 
! colspan="7" style="background:#ffdead;"|E
 
|-
 
|-
! style="background:#efefef;"|
+
!  
! style="background:#efefef;"|1
+
! 1
! style="background:#efefef;"|2
+
! 2
! style="background:#efefef;"|3
+
! 3
! style="background:#efefef;"|4
+
! 4
! style="background:#efefef;"|5
+
! 5
! style="background:#efefef;"|6
+
! 6
 
|-
 
|-
! style="background:#efefef;"|1
+
! 1
 
|  
 
|  
 
|  
 
|  
Строка 1549: Строка 1542:
 
|  
 
|  
 
|-
 
|-
! style="background:#efefef;"|2
+
! 2
 
|  
 
|  
 
| align="center"| ●  
 
| align="center"| ●  
Строка 1557: Строка 1550:
 
|  
 
|  
 
|-
 
|-
! style="background:#efefef;"|3
+
! 3
 
|  
 
|  
 
|  
 
|  
Строка 1565: Строка 1558:
 
|  
 
|  
 
|-
 
|-
! style="background:#efefef;"|4
+
! 4
 
|  
 
|  
 
|  
 
|  
Строка 1573: Строка 1566:
 
|  
 
|  
 
|-
 
|-
! style="background:#efefef;"|5
+
! 5
 
|  
 
|  
 
|  
 
|  
Строка 1581: Строка 1574:
 
|  
 
|  
 
|-
 
|-
! style="background:#efefef;"|6
+
! 6
 
|  
 
|  
 
|  
 
|  
Строка 1589: Строка 1582:
 
| align="center"| ●  
 
| align="center"| ●  
 
|}
 
|}
{| clear="both" |}
+
<div style="clear:both;"></div>
  
 
Итерация <tex>m = 5</tex>.
 
Итерация <tex>m = 5</tex>.
  
 
+
{| border="1" class="wikitable" style="width: 150px; height: 150px; float: left;"  
{| border="1" style="width: 150px; height: 150px; float: left;"  
 
 
! colspan="7" style="background:#ffdead;"|A
 
! colspan="7" style="background:#ffdead;"|A
 
|-
 
|-
! style="background:#efefef;"|
+
!  
! style="background:#efefef;"|1
+
! 1
! style="background:#efefef;"|2
+
! 2
! style="background:#efefef;"|3
+
! 3
! style="background:#efefef;"|4
+
! 4
! style="background:#efefef;"|5
+
! 5
! style="background:#efefef;"|6
+
! 6
 
|-
 
|-
! style="background:#efefef;"|1
+
! 1
 
|  
 
|  
 
| align="center"| ●  
 
| align="center"| ●  
Строка 1613: Строка 1605:
 
| align="center"| ●  
 
| align="center"| ●  
 
|-
 
|-
! style="background:#efefef;"|2
+
! 2
 
|  
 
|  
 
|  
 
|  
Строка 1621: Строка 1613:
 
|  
 
|  
 
|-
 
|-
! style="background:#efefef;"|3
+
! 3
 
|  
 
|  
 
|  
 
|  
Строка 1629: Строка 1621:
 
| align="center"| ●  
 
| align="center"| ●  
 
|-
 
|-
! style="background:#efefef;"|4
+
! 4
 
|  
 
|  
 
|  
 
|  
Строка 1637: Строка 1629:
 
|  
 
|  
 
|-
 
|-
! style="background:#efefef;"|5
+
! 5
 
|  
 
|  
 
|  
 
|  
Строка 1645: Строка 1637:
 
|  
 
|  
 
|-
 
|-
! style="background:#efefef;"|6
+
! 6
 
|  
 
|  
 
|  
 
|  
Строка 1653: Строка 1645:
 
|  
 
|  
 
|}
 
|}
{| border="1" style="width: 150px; height: 150px; float: left;"  
+
{| border="1" class="wikitable" style="width: 150px; height: 150px; float: left;"  
 
! colspan="7" style="background:#ffdead;"|B
 
! colspan="7" style="background:#ffdead;"|B
 
|-
 
|-
! style="background:#efefef;"|
+
!  
! style="background:#efefef;"|1
+
! 1
! style="background:#efefef;"|2
+
! 2
! style="background:#efefef;"|3
+
! 3
! style="background:#efefef;"|4
+
! 4
! style="background:#efefef;"|5
+
! 5
! style="background:#efefef;"|6
+
! 6
 
|-
 
|-
! style="background:#efefef;"|1
+
! 1
 
|  
 
|  
 
| align="center"| ●  
 
| align="center"| ●  
Строка 1672: Строка 1664:
 
| align="center"| ●  
 
| align="center"| ●  
 
|-
 
|-
! style="background:#efefef;"|2
+
! 2
 
|  
 
|  
 
|  
 
|  
Строка 1680: Строка 1672:
 
|  
 
|  
 
|-
 
|-
! style="background:#efefef;"|3
+
! 3
 
|  
 
|  
 
|  
 
|  
Строка 1688: Строка 1680:
 
| align="center"| ●  
 
| align="center"| ●  
 
|-
 
|-
! style="background:#efefef;"|4
+
! 4
 
|  
 
|  
 
|  
 
|  
Строка 1696: Строка 1688:
 
|  
 
|  
 
|-
 
|-
! style="background:#efefef;"|5
+
! 5
 
|  
 
|  
 
|  
 
|  
Строка 1704: Строка 1696:
 
|  
 
|  
 
|-
 
|-
! style="background:#efefef;"|6
+
! 6
 
|  
 
|  
 
|  
 
|  
Строка 1712: Строка 1704:
 
|  
 
|  
 
|}
 
|}
{| border="1" style="width: 150px; height: 150px; float: left;"  
+
{| border="1" class="wikitable" style="width: 150px; height: 150px; float: left;"  
 
! colspan="7" style="background:#ffdead;"|C
 
! colspan="7" style="background:#ffdead;"|C
 
|-
 
|-
! style="background:#efefef;"|
+
!  
! style="background:#efefef;"|1
+
! 1
! style="background:#efefef;"|2
+
! 2
! style="background:#efefef;"|3
+
! 3
! style="background:#efefef;"|4
+
! 4
! style="background:#efefef;"|5
+
! 5
! style="background:#efefef;"|6
+
! 6
 
|-
 
|-
! style="background:#efefef;"|1
+
! 1
 
| align="center"| ●  
 
| align="center"| ●  
 
|  
 
|  
Строка 1731: Строка 1723:
 
|  
 
|  
 
|-
 
|-
! style="background:#efefef;"|2
+
! 2
 
|  
 
|  
 
|  
 
|  
Строка 1739: Строка 1731:
 
|  
 
|  
 
|-
 
|-
! style="background:#efefef;"|3
+
! 3
 
|  
 
|  
 
|  
 
|  
Строка 1747: Строка 1739:
 
|  
 
|  
 
|-
 
|-
! style="background:#efefef;"|4
+
! 4
 
|  
 
|  
 
|  
 
|  
Строка 1755: Строка 1747:
 
|  
 
|  
 
|-
 
|-
! style="background:#efefef;"|5
+
! 5
 
|  
 
|  
 
|  
 
|  
Строка 1763: Строка 1755:
 
|  
 
|  
 
|-
 
|-
! style="background:#efefef;"|6
+
! 6
 
|  
 
|  
 
|  
 
|  
Строка 1771: Строка 1763:
 
|  
 
|  
 
|}
 
|}
{| border="1" style="width: 150px; height: 150px; float: left;"  
+
{| border="1" class="wikitable" style="width: 150px; height: 150px; float: left;"  
 
! colspan="7" style="background:#ffdead;"|D
 
! colspan="7" style="background:#ffdead;"|D
 
|-
 
|-
! style="background:#efefef;"|
+
!  
! style="background:#efefef;"|1
+
! 1
! style="background:#efefef;"|2
+
! 2
! style="background:#efefef;"|3
+
! 3
! style="background:#efefef;"|4
+
! 4
! style="background:#efefef;"|5
+
! 5
! style="background:#efefef;"|6
+
! 6
 
|-
 
|-
! style="background:#efefef;"|1
+
! 1
 
|  
 
|  
 
|  
 
|  
Строка 1790: Строка 1782:
 
|  
 
|  
 
|-
 
|-
! style="background:#efefef;"|2
+
! 2
 
|  
 
|  
 
| align="center"| ●  
 
| align="center"| ●  
Строка 1798: Строка 1790:
 
|  
 
|  
 
|-
 
|-
! style="background:#efefef;"|3
+
! 3
 
|  
 
|  
 
|  
 
|  
Строка 1806: Строка 1798:
 
|  
 
|  
 
|-
 
|-
! style="background:#efefef;"|4
+
! 4
 
|  
 
|  
 
|  
 
|  
Строка 1814: Строка 1806:
 
| align="center"| ●  
 
| align="center"| ●  
 
|-
 
|-
! style="background:#efefef;"|5
+
! 5
 
|  
 
|  
 
|  
 
|  
Строка 1822: Строка 1814:
 
|  
 
|  
 
|-
 
|-
! style="background:#efefef;"|6
+
! 6
 
|  
 
|  
 
|  
 
|  
Строка 1830: Строка 1822:
 
| align="center"| ●  
 
| align="center"| ●  
 
|}
 
|}
{| border="1" style="width: 150px; height: 150px; "  
+
{| border="1" class="wikitable" style="width: 150px; height: 150px; float: left;"  
 
! colspan="7" style="background:#ffdead;"|E
 
! colspan="7" style="background:#ffdead;"|E
 
|-
 
|-
! style="background:#efefef;"|
+
!  
! style="background:#efefef;"|1
+
! 1
! style="background:#efefef;"|2
+
! 2
! style="background:#efefef;"|3
+
! 3
! style="background:#efefef;"|4
+
! 4
! style="background:#efefef;"|5
+
! 5
! style="background:#efefef;"|6
+
! 6
 
|-
 
|-
! style="background:#efefef;"|1
+
! 1
 
|  
 
|  
 
|  
 
|  
Строка 1849: Строка 1841:
 
|  
 
|  
 
|-
 
|-
! style="background:#efefef;"|2
+
! 2
 
|  
 
|  
 
| align="center"| ●  
 
| align="center"| ●  
Строка 1857: Строка 1849:
 
|  
 
|  
 
|-
 
|-
! style="background:#efefef;"|3
+
! 3
 
|  
 
|  
 
|  
 
|  
Строка 1865: Строка 1857:
 
|  
 
|  
 
|-
 
|-
! style="background:#efefef;"|4
+
! 4
 
|  
 
|  
 
|  
 
|  
Строка 1873: Строка 1865:
 
|  
 
|  
 
|-
 
|-
! style="background:#efefef;"|5
+
! 5
 
|  
 
|  
 
|  
 
|  
Строка 1881: Строка 1873:
 
|  
 
|  
 
|-
 
|-
! style="background:#efefef;"|6
+
! 6
 
|  
 
|  
 
|  
 
|  
Строка 1889: Строка 1881:
 
| align="center"| ●  
 
| align="center"| ●  
 
|}
 
|}
{| clear="both" |}
+
<div style="clear:both;"></div>
  
 
== См. также ==  
 
== См. также ==  
Строка 1903: Строка 1895:
 
[[Категория: Теория формальных языков]]
 
[[Категория: Теория формальных языков]]
 
[[Категория: Контекстно-свободные грамматики]]
 
[[Категория: Контекстно-свободные грамматики]]
 +
[[Категория: Алгоритмы разбора]]

Текущая версия на 22:51, 23 мая 2019

Задача:
Пусть дана контекстно-свободная грамматика [math]\Gamma[/math] в нормальной форме Хомского и слово [math]w \in \Sigma^{*}[/math]. Требуется выяснить, выводится ли это слово в данной грамматике.


Контекстно-свободная грамматика[править]

Определение:
Контекстно-свободная грамматика (КС-грамматика, бесконтекстная грамматика) — способ описания формального языка, представляющий собой четверку

[math]\Gamma =\langle \Sigma, N, S \in N, P \subset N^{+}\times (\Sigma\cup N)^{*}\rangle[/math], где:

  • [math]\Sigma[/math]алфавит, элементы которого называют терминалами (англ. terminals)
  • [math]N[/math] — множество, элементы которого называют нетерминалами (англ. nonterminals)
  • [math]S[/math] — начальный символ грамматики (англ. start symbol)
  • [math]P[/math] — набор правил вывода (англ. production rules или productions) вида [math]A \rightarrow B_1 B_2 \ldots B_n[/math], где [math]A \in N[/math], [math]B_i \in \Sigma \cup N[/math], то есть у которых левые части — одиночные нетерминалы, а правые — последовательности терминалов и нетерминалов.

Пример[править]

Терминалы [math]\Sigma = \{(, )\}[/math].

Нетерминалы [math]N = \{S\}[/math].

Правила вывода [math]P[/math]:

[math]\begin{array}{l l} S \rightarrow \varepsilon\\ S \rightarrow SS\\ S \rightarrow (S)\\ \end{array}[/math]

Данная грамматика задает язык правильных скобочных последовательностей. Например, последовательность [math](()(()))[/math] может быть выведена следующим образом:

[math] S \Rightarrow (S) \Rightarrow (SS) \Rightarrow (()(S)) \Rightarrow (()(())) [/math]

Нормальная форма Хомского[править]

Нормальная форма Хомского — нормальная форма КС-грамматик, в которой все продукции имеют вид:

  • [math]A \rightarrow a[/math], где [math]A[/math] — нетерминал, а [math]a[/math] — терминал
  • [math]A \rightarrow BC[/math], где [math]A[/math], [math]B[/math], [math]C[/math] — нетерминалы, причем [math]B[/math] и [math]C[/math] не являются начальными нетерминалами
  • [math]S \rightarrow \varepsilon[/math], где [math]S[/math] — начальный нетерминал и [math]\varepsilon[/math] — пустая строка (данная продукция необходима, если в языке присуствует пустая строка)

Можно показать, что любую КС-грамматику можно привести к нормальной форме Хомского.

Алгоритм[править]

Алгоритм Кока-Янгера-Касами (англ. Cocke-Younger-Kasami algorithm, англ. CYK-алгоритм) — алгоритм, позволяющий по слову узнать, выводимо ли оно в заданной КС-грамматике в нормальной форме Хомского. Любую КС-грамматику можно привести к НФХ, поэтому алгоритм является универсальным для любой КС-грамматики.

Будем решать задачу динамическим программированием. Дана строка [math]w[/math] размером [math]n[/math]. Заведем для неё трехмерный массив [math]d[/math] размером [math]|N| \times n \times n[/math], состоящий из логических значений, и [math]d[A][i][j] = true \ [/math] тогда и только тогда, когда из нетерминала [math]A[/math] правилами грамматики можно вывести подстроку [math]w[i \ldots j][/math].

Рассмотрим все пары [math]\lbrace \langle j, i \rangle | j-i=m \rbrace[/math], где [math]m[/math] — константа и [math]m \lt n[/math].

  • [math]i = j[/math]. Инициализируем массив для всех нетерминалов, из которых выводится какой-либо символ строки [math]w[/math]. В таком случае [math]d[A][i][i] = true \ [/math], если в грамматике [math]\Gamma[/math] присутствует правило [math]A \rightarrow w[i][/math]. Иначе [math]d[A][i][i] = false[/math].
  • [math]i \ne j[/math]. Значения для всех нетерминалов и пар [math]\lbrace \langle j', i' \rangle | j' - i' \lt m \rbrace[/math] уже вычислены, поэтому [math]d[A][i][j] = \bigvee\limits_{A \rightarrow BC}\bigvee\limits_{k = i}^{j-1} d[B][i][k] \wedge d[C][k+1][j] \ \ [/math]. То есть, подстроку [math]w[i \ldots j][/math] можно вывести из нетерминала [math]A[/math], если существует продукция вида [math]A \rightarrow BC[/math] и такое [math]k[/math], что подстрока [math]w[i \ldots k][/math] выводима из [math]B[/math], а подстрока [math]w[k + 1 \ldots j][/math] выводится из [math]C[/math].

CYK rule 2.jpg

После окончания работы значение [math]d[S][1][n][/math] содержит ответ на вопрос, выводима ли данная строка в данной грамматике, где [math]S[/math] — начальный символ грамматики.

Модификации[править]

Количество способов вывести слово[править]

Если массив будет хранить целые числа, а формулу заменить на [math]d[A][i][j] = \sum\limits_{A \rightarrow BC}\sum\limits_{k = i}^{j-1} d[B][i][k] \cdot d[C][k + 1][j] \ \ [/math], то [math]d[A][i][j][/math] — количество способов получить подстроку [math]w[i \ldots j][/math] из нетерминала [math]A[/math].

Минимальная стоимость вывода слова[править]

Пусть [math]H(A \rightarrow BC)[/math] — стоимость вывода по правилу [math]A \rightarrow BC[/math]. Тогда, если использовать формулу [math]d[A][i][j] = \min\limits_{A \rightarrow BC} \min\limits_{k = i}^{j-1} ( d[B][i][k] + d[C][k + 1][j] + H(A \rightarrow BC) ) \ \ [/math], то [math]d[A][i][j][/math] — минимальная стоимость вывода подстроки [math]w[i \ldots j][/math] из нетерминала [math]A[/math].

Таким образом, задача о выводе в КС-грамматике в нормальной форме Хомского является частным случаем задачи динамического программирования на подотрезке.

Асимптотика[править]

Обработка правил вида [math]A \rightarrow w[i][/math] выполняется за [math]O(n \cdot |\Gamma|)[/math].

Проход по всем подстрокам выполняется за [math]O(n^2)[/math]. В обработке одной подстроки присутствует цикл по всем правилам вывода и по всем разбиениям на две подстроки, следовательно обработка работает за [math]O(n \cdot |\Gamma|)[/math]. В итоге получаем конечную сложность [math]O(n^3 \cdot |\Gamma|)[/math].

Следовательно, общее время работы алгоритма — [math]O(n^3 \cdot |\Gamma|)[/math]. Кроме того, алгоритму требуется память на массив [math]d[/math] объемом [math]O(n^2 \cdot |N|)[/math], где [math]|N|[/math] — количество нетерминалов грамматики.

Пример работы[править]

Дана грамматика правильных скобочных последовательностей [math]\Gamma[/math] в нормальной форме Хомского.

[math]\begin{array}{l l} A \rightarrow \varepsilon\ |\ BB\ |\ CD\\ B \rightarrow BB\ |\ CD\\ C \rightarrow (\\ D \rightarrow BE\ |\ )\\ E \rightarrow )\\ \end{array}[/math]

Дано слово [math]w = ()(())[/math].


Инициализация массива [math]d[/math].

A
1 2 3 4 5 6
1
2
3
4
5
6
B
1 2 3 4 5 6
1
2
3
4
5
6
C
1 2 3 4 5 6
1
2
3
4
5
6
D
1 2 3 4 5 6
1
2
3
4
5
6
E
1 2 3 4 5 6
1
2
3
4
5
6

Заполнение массива [math]d[/math].


Итерация [math]m = 1[/math].

A
1 2 3 4 5 6
1
2
3
4
5
6
B
1 2 3 4 5 6
1
2
3
4
5
6
C
1 2 3 4 5 6
1
2
3
4
5
6
D
1 2 3 4 5 6
1
2
3
4
5
6
E
1 2 3 4 5 6
1
2
3
4
5
6

Итерация [math]m = 2[/math].

A
1 2 3 4 5 6
1
2
3
4
5
6
B
1 2 3 4 5 6
1
2
3
4
5
6
C
1 2 3 4 5 6
1
2
3
4
5
6
D
1 2 3 4 5 6
1
2
3
4
5
6
E
1 2 3 4 5 6
1
2
3
4
5
6

Итерация [math]m = 3[/math].

A
1 2 3 4 5 6
1
2
3
4
5
6
B
1 2 3 4 5 6
1
2
3
4
5
6
C
1 2 3 4 5 6
1
2
3
4
5
6
D
1 2 3 4 5 6
1
2
3
4
5
6
E
1 2 3 4 5 6
1
2
3
4
5
6

Итерация [math]m = 4[/math].

A
1 2 3 4 5 6
1
2
3
4
5
6
B
1 2 3 4 5 6
1
2
3
4
5
6
C
1 2 3 4 5 6
1
2
3
4
5
6
D
1 2 3 4 5 6
1
2
3
4
5
6
E
1 2 3 4 5 6
1
2
3
4
5
6

Итерация [math]m = 5[/math].

A
1 2 3 4 5 6
1
2
3
4
5
6
B
1 2 3 4 5 6
1
2
3
4
5
6
C
1 2 3 4 5 6
1
2
3
4
5
6
D
1 2 3 4 5 6
1
2
3
4
5
6
E
1 2 3 4 5 6
1
2
3
4
5
6

См. также[править]

Источники информации[править]