Так, друзья, ну давайте, наконец, обсудим выравнивание, немножко поучимся работать с этим замечательным прикладным объектом, который мы рассмотрели на последней лекции. Ну для начала что-нибудь совсем элементарное. Давайте вообще во всех задачах, которые мы будем рассматривать впредь в рамках этих семинаров, будем считать, что выравниваются 2 слова русского алфавита, 2 обычных просто русских слова — это слова «суслик» и «хорек». Вот есть слово «суслик», и есть слово «хорек». Это совершенно формально, понятно, что никакого содержательного прикладного смысла в выравнивании слов «суслик» и «хорек» не существует, но для того чтобы уметь работать и с прикладными объектами тоже, нужно научиться работать с какими-то объектами вполне образцово-показательными: вот есть «суслик», есть «хорек». Там, есть «кролик», есть «икра», да? Вот есть «суслик», есть «хорек». Их можно по-разному выравнивать, и я надеюсь, вы помните, что такое выравнивание с точки зрения того определения, которое давалось на лекции, а именно: важным напоминанием является то, что, во-первых, в выравнивании никогда не бывает столбцов вида гэп над гэпом, — пустое множество над пустым множеством: бессмысленно выравнивать ненужные символы между собой, зачем? Вот и кроме того, мы отождествляем выравнивания, в которых есть a – пусто, пусто – b в соседних столбцах, с аналогичными выравниваниями, у которых эти столбцы просто переставлены местами, если в выравнивании эти столбцы записаны вот в таком вот виде. Опять же никакой новой информации такая перестановка нам не дает, поэтому мы отождествляем все выравнивания, которые друг из друга получаются путем последовательных таких вот перестановок столбцов между собой. Вот ну первое, что совсем легко сделать, и вот с этого мы, наверное, и начнем, — это мы спросим себя: а сколько всего существует различных выравниваний вот этих двух слов между собой, коль скоро выполнено и вот это свойство 1, и вот это свойство 2, отождествление? Ну сколько всего выравниваний этих двух слов? Ну на это ответ дает нам слава Богу теорема, просто доказанная на лекции. На лекции это количество обозначалось g(n, m). В данном случае n = 6, а m = 5: мы выравниваем два слова, длина одного из которых — это 6, а другого — это 5. Мы знаем общую формулу C из n + m по m или же по n, — мы ее доказали, это было такое вообще величие и слава нашего комбинаторного метода, что, оказывается, мы можем во вполне прикладных задачах получать окончательные формулы. Ну и дальше мы вместо n, m подставляем в данном случае 6 и 5, получаем C из 11, 6 + 5 — это 11, по 5 или по 6, как хотите. Ну это уже можно сосчитать, а я считать не стану. Все, вот это вот простейшая задачка — просто научиться применять ту формулу, которая на самом деле аккуратно была доказана на лекции. Давайте в этом месте остановимся, а дальше будем решать что-то более интересное.