18 (1108017)

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла

Курс «Алгоритмы и алгоритмические языки»1 семестр 2015/2016Лекция 181Сложность алгоритмовРазмер входа: числовая величина, характеризующаяколичество входных данных (например – длина битовой записичисел - параметров алгоритма)Сложность в наихудшем случае: функция размера входа,отражающая максимум затрат на выполнение алгоритма дляданного размеравременнАя сложностьпространственная сложность (затраты памяти)часто оценивают не все затраты, а только самые“дорогие” операцииСложность в среднем: функция размера входа,отражающая средние затраты на выполнение алгоритма длявхода данного размера (учет вероятностей входа)Асимптотические оценки сложности: О-нотация (оценкасверху), точная O-оценка, Θ-оценка.Подробности: С.А.

Абрамов. Лекции о сложности алгоритмов.М.: МЦНМО, 20092Формальная постановка задачи поиска по образцуДаны текст – массив T[N] длины N и образец – массив P[m]длины m ≤ N, где значениями элементов массивов T и Pявляются символы некоторого алфавита A.Говорят, что образец P входит в текст T со сдвигом s,если 0 ≤ s ≤ N – m и для всех i = 1, 2, …, m T [s + i] = P [i].Сдвиг s(T, P) называется допустимым, если P входит в T сосдвигом s = s(T, P), и недопустимым в противном случае.Задача поиска подстрок состоит в нахождении множествадопустимых сдвигов s(T, P) для заданного текста T и образца P.3Формальная постановка задачи поиска по образцуТерминология. Пусть строки x, y, w ∈ A*, ε ∈ A* - пустая строка;|x| - длина строки x;xy – конкатенация строк x и y; |xy| = |x| + |y|;x = wy -> w – префикс (начало) x (обозначение w  x );x = yw -> w – суффикс (конец) x (обозначение w  x );если w – префикс или суффикс x, то |w| ≤ |x|;отношения префикса и суффикса транзитивны.Для любых x, y ∈ A* и любого a ∈ A соотношения x  yи xa  ya равносильны.Если S = S[r] – строка длины r, то ее префикс длины k, k ≤ r будетобозначаться Sk = S[k]; ясно, что S0 = ε, Sr = S.4Лемма (о двух суффиксах)Пусть x, y и z – строки, для которых x  z и y  z .Тогда если |x| ≤ |y|, то x  y , если |x| ≥ |y|, то y  x ,если |x| = |y|, то x = y .xxzxzzyyxyxxy|x| ≤ |y|y|x| ≥ |y|y|x| = |y|5Простой алгоритмПроверка совмещения двух строк: посимвольное сравнениеслева направо, которое прекращается (с отрицательнымрезультатом) при первом же расхождении.Оценка скорости сравнения строк x и y – Θ(t + 1), где t – длинанаибольшего общего префикса строк x и y.for (s = 0; s <= n – m; s++) {for (i = 0; i < m && P[i] == T[s + i]; i++);if (i == m)printf ("%d\n", s);}Время работы в худшем случае Θ((n – m + 1)⋅m) ~ Θ(nm).Причина: информация о тексте T, полученная при проверкеданного сдвига s, никак не используется при проверкеследующих сдвигов.

Например, если для образца dddcсдвиг s = 0 допустим, то сдвиги s = 1, 2, 3, недопустимы,так как T[3] == с.6Алгоритм Кнута – Морриса – Пратта. ИдеяПрефикс-функция, ассоциированная с образцом P, показывает,где в строке P повторно встречаются различные префиксы этойстроки. Если это известно, можно не проверять заведомонедопустимые сдвиги.Пример.

Пусть ищутся вхождения образца P = a b a b a c a втекст T. Пусть для некоторого сдвига s оказалось, что первые qсимволов образца совпадают с символами текста. Значит,символы текста от T[s+1] до T[s+q] известны, что позволяетзаключить, что некоторые сдвиги заведомо недопустимы.7Алгоритм Кнута – Морриса – Пратта. ИдеяПусть P[1..q] = T[s+1..s+q]; каково минимальное значение сдвигаs′ > s, для которого P[1..k] = T[s′+1..s′+k], где s′+k = s+q?Число s′ - минимальное значение сдвига, большего s,которое совместимо с тем, что T[s+1..s+q] = P[1..q].Следовательно, значения сдвигов, меньшие s′ ,проверять не нужно.Лучше всего, когда s′ = s+q, так как в этом случае ненужно рассматривать сдвиги s+q-1, s+q-2, …, s+1.Кроме того, при проверке нового сдвига s′ можно нерассматривать первые его k символов образца: онизаведомо совпадут.Чтобы найти s′, достаточно знать образец P и число q:T[s′+1..s′+k] – суффикс Pq, поэтому k – это наибольшее число,для которого Pk является суффиксом Pq.

Зная k (число символов,заведомо совпадающих при проверке нового сдвига s′), можновычислить s′ по формуле s′ = s + (q – k).8Алгоритм Кнута – Морриса – Пратта. Префикс-функцияОпределение. Префикс-функцией, ассоциированной со строкойP[1..m], называется функция π: {1,2, …, m} → {0,1, …, m – 1},определенная следующим образом:π[q] = max{k: k<q & Pk  Pq }Иными словами, π[q] – длина наибольшего префикса P,являющегося суффиксом Pq.9Алгоритм Кнута – Морриса – Пратта.

Префикс-функцияvoid prefix_func (char *pat, int *pi, int m) {int k, q;/* Считаем, что pat и pi нумеруются от 1 */pi[1] = 0; k = 0;for (q = 2; q <= m; q++) {while (k > 0 && pat[k + 1] != pat[q])k = pi[k];if (pat[k + 1] == pat[q])k++;pi[q] = k;}}10Алгоритм Кнута – Морриса – Пратта. Префикс-функцияЛемма 1. Обозначим π * [ q] = {q, π [ q], π 2 [ q],..., π t [ q]},где π i [q] есть i-я итерация префикс-функции, π t [ q] = 0.Пусть P – строка длины m c префикс-функцией π.Тогда для всех q = 1, 2, ..., m имеем π * [ q] = {k :Pk  Pq }.Лемма показывает, что при помощи итерированияпрефикс-функции можно для данного q найти все такие k, чтоPk является суффиксом Pq.Доказательство.(1)Покажем, что если i принадлежит π*[q], то Pi являетсясуффиксом Pq.Действительно, Pπ [ i ]  Pi по определению префиксфункции, так что каждый следующий членпоследовательности Pi , Pπ [ i ] , Pπ [π [ i ]] ,...

являетсясуффиксом всех предыдущих.11Алгоритм Кнута – Морриса – Пратта. Префикс-функцияДоказательство.(2)Покажем, что наоборот, если Pi является суффиксом Pq,то i принадлежит π*[q].Расположим все Pi , являющиеся суффиксами Pq, впорядке уменьшения i (длины): Pi1, Pi2,…Покажем по индукции, что Pik = πk[q].База индукции (k=1): для максимального префикса Pi ,являющегося суффиксом Pq, по определению i=π[q].Шаг индукции: если Pik = πk[q], то по определениюj = π[πk[q]] соответствует максимальный префикс Pj,который является суффиксом Pik. Обе строки Pj и Pikесть суффиксы Pq по построению.

Таким максимальнымпрефиксом из оставшихся Pik+1, Pik+2,… по построениюявляется префикс Pik+1 ,то есть j = ik+1.(2) можно доказать и от противного: для наибольшегочисла j такого, что Pj  Pq , но j не входит в π*[q],определение префикс-функции нарушается.12Алгоритм Кнута – Морриса – Пратта. Префикс-функцияπ [8] = {8,6,4,2,0}*13Алгоритм Кнута – Морриса – Пратта.

Префикс-функцияЛемма 2. Пусть P – строка длины m c префикс-функцией π.Тогда для всех q = 1, 2, ..., m, для которых π [ q] > 0 ,*имеем π [ q ] − 1 ∈ π [ q − 1] .Доказательство.Если k = π [ q ] > 0 , то Pk является суффиксом Pqпо определению префикс-функции.Следовательно, Pk-1 является суффиксом Pq-1.Тогда по Лемме 1 k − 1 ∈ π * [ q − 1] , т.е.π [q] − 1 ∈ π *[q − 1] .Определим множества Eq-1 какEq −1 = {k : k ∈ π *[ q − 1] и P[k + 1] = P[ q]}.Множество Eq-1 состоит из таких k, что Pk является суффиксомPq-1, и за ними идут одинаковые буквы P[k+1] и P[q].Из определения вытекает, что Pk+1 есть суффикс Pq.14Алгоритм Кнута – Морриса – Пратта.

Префикс-функцияСледствие 1. Пусть P – строка длины m c префикс-функцией π.Тогда для всех q = 2, 3, ..., m0, если Eq −1 пусто;π [q] = 1 + max{k ∈ Eq −1}, если Eq −1 не пусто.Доказательство.Если r = π [ q] ≥ 1 , то P[r] = P[q] и по Лемме 2r − 1 = π [ q] − 1 ∈ π *[ q − 1] .Т.к. P[r] = P[q], то P[(r-1)+1] = P[q].Поэтому r − 1 ∈ Eq −1 по определению Eq-1 и из π [ q] ≥ 1следует непустота Eq-1.Следовательно, если Eq-1 пусто, то π [ q] = 0 (от противного).Если k ∈ Eq −1 , то Pk+1 есть суффикс Pq (из определения),следовательно,π [ q ] ≥ k + 1 и π [ q] ≥ 1 + max{k ∈ Eq −1}.То есть, если Eq-1 не пусто, то префикс-функцияположительна.

Но тогдаπ [ q] − 1 ∈ Eq −1 , π [ q] − 1 не большемаксимума из Eq-1, т.е. π [ q] ≤ 1 + max{k ∈ Eq −1}.15Алгоритм Кнута – Морриса – Пратта. Префикс-функция1 void prefix_func (char *pat, int *pi, int m) {2int k, q;34/* Считаем, что pat и pi нумеруются от 1 */5pi[1] = 0; k = 0;6for (q = 2; q <= m; q++) {7while (k > 0 && pat[k + 1] != pat[q])8k = pi[k];9if (pat[k + 1] == pat[q])10k++;11pi[q] = k;12}13 }16Алгоритм Кнута – Морриса – Пратта. Префикс-функцияТеорема 1.

Функция prefix_func правильно вычисляетпрефикс-функцию π.Доказательство.Покажем, что при входе в цикл функции k = π[q-1].База индукции.При q = 2 k = 0, pi[q-1] = pi[1] = 0.Шаг индукции.Пусть при входе в цикл функции k = π[q-1].Код на строках 7-8while (k > 0 && pat[k + 1] != pat[q])k = pi[k];находит наибольший элемент Eq-1 (т.к. цикл перебираетв порядке убывания элементы из π*[q-1] и для каждогопроверяет равенство pat[k + 1] != pat[q])).17Алгоритм Кнута – Морриса – Пратта. Префикс-функцияТеорема 1. Функция prefix_func правильно вычисляетпрефикс-функцию π.Доказательство.После выхода из цикла на строках 7-8while (k > 0 && pat[k + 1] != pat[q])k = pi[k];1) если pat[k + 1] == pat[q], то выполняется код настроке 10:k++;что из Следствия 1 дает нам π[q].2) если pat[k + 1] != pat[q], то k == 0,множество Eq-1 пусто и π[q] = 0.18Алгоритм Кнута – Морриса – Пратта. Функция kmpvoid kmp (char *text, char *pat, int m, int n) {int q;int pi[m + 1]; /* VLA-массив *//* Через alloca: int *pi = alloca ((m + 1) * sizeof (int)); *//* Считаем, что pat и text нумеруются от 1 */prefix_func (pat, pi, m);q = 0;for (i = 1; i <= n; i++) {while (q > 0 && pat[q + 1] != text[i])q = pi[q];if (pat[q + 1] == text[i])q++;if (q == m) {printf ("образец входит со сдвигом %d\n", i – m);q = pi[q];}19}Алгоритм Кнута – Морриса – Пратта.

Характеристики

Тип файла PDF

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

Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.

Список файлов лекций