Ағылшыншамен салыстырыңыз: абзацты басыңыз — түпнұсқа терезеде ашылады. Абзац астындағы EN түймесі оны мәтін ішінде көрсетеді.
Кіріспе
Компьютерлік ғылымда X және Y екі тізбегінің ең қысқа ортақ супертізбегі – X және Y тізбектерінің кіші тізбектері болатын ең қысқа тізбек. Бұл мәселе ең ұзақ ортақ кіші тізбек мәселесімен тығыз байланысты. Екі тізбек берілген: X = < x1, …, xm > және Y = < y1, …, yn >. U = < u1, …, uk > тізбегі X және Y тізбектерінің ортақ супертізбегі болып есептеледі, егер U тізбегінен элементтерді алып тастау арқылы X және Y тізбектерін алуға болады. Ең қысқа ортақ супертізбек (SCS) – ең аз ұзындығы бар ортақ супертізбек. Ең қысқа ортақ супертізбек мәселесінде екі тізбек X және Y беріледі, және міндет – осы тізбектердің ең қысқа мүмкін ортақ супертізбегін табу. Жалпы алғанда, SCS бірегей емес. Екі кіріс тізбегі үшін ең ұзақ ортақ кіші тізбектен (LCS) SCS-ті оңай құрастыруға болады. Мысалы, егер X және Y тізбектерінің ең ұзақ ортақ кіші тізбегі Z болса, онда түпнұсқалық ретін сақтай отырып LCS-ке жатпайтын символдарды Z-ге енгізу арқылы ең қысқа ортақ супертізбек U алынады. Атап айтқанда, бұл теңдеу кез келген екі кіріс тізбегі үшін орындалады. Ең қысқа ортақ супертізбектер мен үш немесе одан көп кіріс тізбектерінің ең ұзақ ортақ кіші тізбектері арасында мұндай байланыс жоқ. (Атап айтқанда, LCS және SCS – қос проблема емес.) Дегенмен, екі мәселені де динамикалық бағдарламалау арқылы уақыттың ішінде шешуге болады, мұнда – тізбектердің саны және – олардың ең үлкен ұзындығы. Кіріс тізбектерінің кез келген саны үшін бұл мәселе NP-қиын.
In computer science, the shortest common supersequence of two sequences X and Y is the shortest sequence which has X and Y as subsequences. This is a problem closely related to the longest common subsequence problem. Given two sequences X = < x1, ,xm > and Y = < y1, ,yn >, a sequence U = < u1, ,uk > is a common supersequence of X and Y if items can be removed from U to produce X and Y. A shortest common supersequence (SCS) is a common supersequence of minimal length. In the shortest common supersequence problem, two sequences X and Y are given, and the task is to find a shortest possible common supersequence of these sequences. In general, an SCS is not unique. For two input sequences, an SCS can be formed from a longest common subsequence (LCS) easily. For example, the longest common subsequence of X and Y is Z. By inserting the non LCS symbols into Z while preserving their original order, we obtain a shortest common supersequence U. In particular, the equation holds for any two input sequences. There is no similar relationship between shortest common supersequences and longest common subsequences of three or more input sequences. (In particular, LCS and SCS are not dual problems.) However, both problems can be solved in time using dynamic programming, where is the number of sequences, and is their maximum length. For the general case of an arbitrary number of input sequences, the problem is NP hard.
Мысал
= { abc, cde, fab } жиынтығын қарастырайық, ол салмақты жиынтық жабу мысалының ғаламдық жиынына айналады. Бұл жағдайда = { abcde, fabc }. Онда ғаламның кіші жиынтықтары мыналар болады:
Consider the set = { abc, cde, fab }, which becomes the universe of the weighted set cover instance. In this case, = { abcde, fabc }. Then the set of subsets of the universe is
Олардың құндары сәйкесінше 3, 3, 3, 5 және 4-ке тең.