63
правки
Изменения
Новая страница: «{{Определение |definition= Последовательность <tex> Z = \left \langle z_1, z_2, \dots, z_k \right \rangle </tex> является '''...»
{{Определение
|definition=
Последовательность <tex> Z = \left \langle z_1, z_2, \dots, z_k \right \rangle </tex> является '''подпоследовательностью''' (англ. ''subsequence'') последовательности <tex> X = \left \langle x_1, x_2, \dots, x_m \right \rangle </tex>, если существует строго возрастающая последовательность <tex> \left \langle i_1, i_2, \dots, i_k \right \rangle </tex> индексов <tex> X </tex> таких, что для всех <tex> j = 1, 2, \dots, k </tex> выполняется соотношение <tex> x_{i_j} = z_j </tex>.
}}
{{Определение
|definition=
Последовательность <tex> Z </tex> является '''общей суперпоследовательностью''' (англ. ''common supersequence'') последовательностей <tex> X </tex> и <tex> Y </tex>, если <tex> X </tex> и <tex> Y </tex> являются подпоследовательностями <tex> Z </tex>.
}}
{{Задача
|definition=
Пусть имеются последовательности <tex> X = \left \langle x_1, x_2, \dots, x_m \right \rangle </tex> и <tex> Y = \left \langle y_1, y_2, \dots, y_n \right \rangle </tex>. Необходимо найти <tex>SCS(X,Y)</tex>
}}
== Наивное решение ==
Заметим, что если приписать к одной из данной последовательность другую, то полученная последовательность будет их суперпоследовательностью с длиной <tex> n + m </tex>. Запомним все элементы обеих последовательностей и из них построим все возможные последовательности. Тогда искомая <tex>SCS</tex> гарантированно найдётся, однако время работы алгоритма будет экспоненциально зависеть от длины исходных последовательностей.
|definition=
Последовательность <tex> Z = \left \langle z_1, z_2, \dots, z_k \right \rangle </tex> является '''подпоследовательностью''' (англ. ''subsequence'') последовательности <tex> X = \left \langle x_1, x_2, \dots, x_m \right \rangle </tex>, если существует строго возрастающая последовательность <tex> \left \langle i_1, i_2, \dots, i_k \right \rangle </tex> индексов <tex> X </tex> таких, что для всех <tex> j = 1, 2, \dots, k </tex> выполняется соотношение <tex> x_{i_j} = z_j </tex>.
}}
{{Определение
|definition=
Последовательность <tex> Z </tex> является '''общей суперпоследовательностью''' (англ. ''common supersequence'') последовательностей <tex> X </tex> и <tex> Y </tex>, если <tex> X </tex> и <tex> Y </tex> являются подпоследовательностями <tex> Z </tex>.
}}
{{Задача
|definition=
Пусть имеются последовательности <tex> X = \left \langle x_1, x_2, \dots, x_m \right \rangle </tex> и <tex> Y = \left \langle y_1, y_2, \dots, y_n \right \rangle </tex>. Необходимо найти <tex>SCS(X,Y)</tex>
}}
== Наивное решение ==
Заметим, что если приписать к одной из данной последовательность другую, то полученная последовательность будет их суперпоследовательностью с длиной <tex> n + m </tex>. Запомним все элементы обеих последовательностей и из них построим все возможные последовательности. Тогда искомая <tex>SCS</tex> гарантированно найдётся, однако время работы алгоритма будет экспоненциально зависеть от длины исходных последовательностей.
