Материал: АиСД. Практикум (in dev)

2. Алгоритм Бойера - Мура

Этот алгоритм делает то, что на первый взгляд кажется невозможным: в типичной ситуации он читает лишь небольшую часть всех букв слова, в котором ищется заданный образец. Пусть, например, отыскивается образец abcd. Посмотрим на четвертую букву слова: если, к примеру, это буква e, то нет никакой необходимости читать первые три буквы. (В самом деле, в образце буквы e нет, поэтому он может начаться не раньше пятой буквы.)

Приведем самый простой вариант этого алгоритма, который не гарантирует быстрой работы во всех случаях. Пусть x[1]...х[n] - образец, который надо искать. Для каждого символа s найдем самое правое его вхождение в слово X, то есть наибольшее k, при котором х[k]=s. Эти сведения будем хранить в массиве pos[s]; если символ s вовсе не встречается, то будет удобно предположить pos[s]=0 ..

Решение.

положить все pos[s] равными 0

for i:=1 to n do begin

pos[x[i]]:=i;

end;

В процессе поиска будем хранить в переменной last номер буквы в слове, против которой стоит последняя буква образца. Вначале last=n (длина образца), затем last постепенно увеличивается.

last:=n;

{все предыдущие положения образца уже проверены}

while last<= m do begin {слово не кончилось}

if x[m]<>y[last] then begin {последние буквы разные}

last:=last+(n-pos[y[last]]);

{n - pos[y[last]] - это минимальный сдвиг образца,

при котором напротив y[last] встанет такая же

буква в образце. Если такой буквы нет вообще,

то сдвигаем на всю длину образца}

end else begin

если нынешнее положение подходит, т.е. если

x[i]..х[n]=y[last-n+1]..y[last],

то сообщить о совпадении;

last:=last+1;

end;

end;

3. Алгоритм Рабина

Этот алгоритм основан на простой идее. Представим себе, что в слове длины m ищется образец длины n. Вырежем окошко размера n и будем двигать его по входному слову. При этом проверяем, не совпадает ли слово в окошке с заданным образцом. Сравнивать по буквам долго. Вместо этого фиксируем некоторую функцию, определенную на словах длины n. Если значения этой функции на слове в окошке и на образце различны, то совпадения нет. Только если значения одинаковы, нужно проверять совпадение по буквам.

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

Заменим все буквы в слове и образце их номерами, представляющими собой целые числа. Тогда удобной функцией является сумма цифр. (При сдвиге окошка нужно добавить новое число и вычесть пропавшее.)

Выберем некоторое число p (желательно простое) и некоторый вычет x по модулю p. Каждое слово длины n будем рассматривать как последовательность целых чисел (заменив буквы кодами). Эти числа будем рассматривать как коэффициенты многочлена степени n-1 и вычислим значение этого многочлена по модулю p в точке x. Это и будет одна из функций семейства (для каждой пары p и x получается, таким образом, своя функция). Сдвиг окошка на 1 соответствует вычитанию старшего члена (х^n-1 следует вычислить заранее), умножению на x и добавлению свободного члена.

Следующее соображение говорит в пользу того, что совпадения не слишком вероятны. Пусть число p фиксировано и к тому же простое, а X и Y - два различных слова длины n. Тогда им соответствуют различные многочлены (предполагаем, что коды всех букв различны - это возможно, если p больше числа букв алфавита). Совпадение значений функции означает, что в точке x эти два различных многочлена совпадают, то есть их разность обращается в 0. Разность есть многочлен степени n-1 и имеет не более n-1 корней. Таким образом, если и много меньше p, то случайному x мало шансов попасть в неудачную точку.

Лабораторное задание

Для каждого из перечисленных методов поиска провести анализ временных затрат для списков различной размерности.

20. Методика выполнения лабораторной работы

Для проведения лабораторной работы необходимо выполнить следующие действия.

1. Выполнить тестовый пример поиска

a) выполнить поиск в массиве из N чисел (варианты заданий даны в приложении ; номер варианта соответствует порядковому номеру фамилии студента в списке группы). Результаты занести в таблицу 1.

Таблица1

Метод
Количество элементов массива N	N1	N2	N3
Время поиска t, c	t1	t2	t3

б) оценить сложность рассмотренных методов поиска;

в) провести анализ отклонения полученной в результате эксперимента сложности алгоритма от теоретической;

г) построить графические зависимости времени поиска от количества элементов массива.

2. Исследовать методы поиска

3. Провести исследование метода хеширования

Требования к отчёту

Отчёт должен содержать:

1. конспект лабораторной работы;

2. примеры методов поиска ;

3. результаты выполнения работы;

4. выводы по работе;

Контрольные вопросы

1. Что понимается под поиском?

2. Каковы особенности поиска: последовательного, бинарного, интерполяционного,

Фибоначчиевого, по бинарному дереву , по бору , хешированием ;

3. В чём состоит методика анализа сложности алгоритмов поиска?

Рекомендуемая литература:

1. Кнут Д. Искусство программирования для ЭВМ. Т. 3. Сортировка и поиск.

М. : Мир, 2000.

2. Т. Кормен, Ч. Лейзерсон, Р. Ривест «Алгоритмы: построение и анализ».

М.: МЦНМО, 2000.

3. Вирт Н. Алгоритмы и структуры данных.: Пер. С англ. - М.: Мир, 2001.

4. Хусаинов Б.С. Структуры и алгоритмы обработки данных. Примеры на языке Си.

Учеб. пособие. М : Финансы и статистика, 2004.

Приложение

Варианты заданий

Провести анализ методов поиска для списков различной размерности и построить зависимости времени от числа элементов исходного множества.

2. Лабораторная работа -Итеративные и рекурсивные алгоритмы

Цель работы: изучить рекурсивные алгоритмы и рекурсивные структуры данных; научиться проводить анализ итеративных и рекурсивных процедур; исследовать эффективность итеративных и рекурсивных процедур при реализации на ПЭВМ.

Продолжительность работы: 2 часа.

21. Теоретические сведения

Эффективным средством программирования для некоторого класса задач является рекурсия. С ее помощью можно решать сложные задачи численного анализа, комбинаторики, алгоритмов трансляции, операций над списковыми структурами и т.д. Программы в этом случае имеют небольшие объемы по сравнению с итерацией и требуют меньше времени на отладку.

Под рекурсией понимают способ задания функции через саму себя, например способ задания факториала в виде

N!=(n-1)!*n

В программировании под рекурсивной процедурой (функцией) понимают способ обращения процедуры (функции) к самой себе.

Под итерацией понимают результат многократно повторяемой какой-либо операции, например представление факториала в виде: .

n!=1*2*З... *n.

Среди широкого класса задач удобно представлять с использованием рекурсивных процедур (функций) те задачи, которые сводятся на подзадачи того же типа, но меньшей размерности.

Общая методика анализа рекурсии содержит три этапа:

1. Параметризация задачи, заключающаяся в выделении различных элементов, от которых зависит решение, в частности размерности решаемой задачи. После каждого рекурсивного вызова размерность должна убывать.

2. Поиск тривиального случая и его решение. Как правило, это ключевой этап в рекурсии, размерность задачи при этом часто равна 0 или I.

3. Декомпозиция общего случая, имеющая целью привести задачу к одной или нескольким задачам того же типе, но меньшей размерности.

Рассмотрим понятие итеративного и рекурсивного алгоритмов на примере вычисления факториала.

22. Итеративный алгоритм.

Наиболее простой и естественной формой представления итеративного алгоритма при реализации на ПЭВМ является описание его с использованием цикла. Программа итеративного алгоритма вычисления факториала представлена на рис.1. Программа состоит из процедуры-функции FACTORIAL и основной программы. В основной программе происходит ввод значения N, вызов процедуры-функции и печать результата.

1. Итеративное вычисление факториала

PROGRAM FI;

VAR

FАС: LONGINT;

N: INTEGER;

{ ФУНКЦИЯ ВЫЧИСЛЕНИЯ ФАКТОРИАЛА }

FUNCTION FACTORIAL (N: INTEGER): LONGINT;

VAR F: LONGINT;

I: INTEGER;

BEGIN

IF (N=O) OR (N=1) THEN FACTORIAL:=1 ELSE

BEGIN

F:= 1;

FOR I: = 2 TO N DO

F: = F * I;

FACTORIAL:=F;

END;

END;

{ ОСНОВНАЯ ПРОГРАММA }

BEGIN

WRITELN ('ВВЕДИТЕ ЗНАЧЕНИЕ N')

READLN (N);

FAC:= FACTORIAL(N); { ВЫЗОВ ФУНКЦИИ FACTORIAL }

WRITELN(' ФАКТОРИАЛ =' , FAC) ;

READLN;

END.

Рекурсивный алгоритм. Рекурсивное представление факториала имеет вид: