Пояснительная записка к курсовой работе по дисциплине «Структуры и алгоритмы обработки данных»

2.2 Краткое теоретическое описание реализуемых объектов

Алгоритм Бойера — Мура поиска строки считается наиболее быстрым среди алгоритмов общего назначения, предназначенных для поиска подстроки в строке. Был разработан Робертом Бойером и Джеем Муром в 1977 году. Преимущество этого алгоритма в том, что ценой некоторого количества предварительных вычислений над шаблоном (но не над строкой, в которой ведётся поиск) шаблон сравнивается с исходным текстом не во всех позициях — часть проверок пропускаются как заведомо не дающие результата.

Алгоритм основан на трёх идеях:

1. Сканирование слева направо, сравнение справа налево.

Совмещается начало текста (строки) и шаблона, проверка начинается с последнего символа шаблона. Если символы совпадают, производится сравнение предпоследнего символа шаблона и т. д. Если все символы шаблона совпали с наложенными символами строки, значит, подстрока найдена, и поиск окончен.

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

Эти «несколько», упомянутые в предыдущем абзаце, вычисляются по двум эвристикам.

2. Эвристика стоп-символа.

В таблице стоп-символов указывается последняя позиция в needle (исключая последнюю букву) каждого из символов алфавита. Для всех символов, не вошедших в needle, пишем 0 (для нумерации с 0 — соответственно, −1).

3. Эвристика совпавшего суффикса.
Если при сравнении строки и шаблона совпало один или больше символов, шаблон сдвигается в зависимости от того, какой суффикс совпал.

Для каждого возможного суффикса S шаблона needle указываем наименьшую величину, на которую нужно сдвинуть вправо шаблон, чтобы он снова совпал с S.

2.3 Анализ результатов

Размер строки в которой будет осуществляться поиск равен 1,958,982 символа. Зависимость скорости выполнения алгоритма(мс) от индекса искомой строки в исходной строке:
Для сравнения диаграммы простого поиска:


Теоретическая оценка сложности алгоритма

O(|haystack|+|needle|+|Σ|)

haystack — строка, в которой выполняется поиск

needle — шаблон поиска

Σ — алфавит, на котором проводится сравнение.
График линейной зависимости времени поиска от размера исходной строки подтверждает теоретическую сложность алгоритма. Исходя из данных исследований можно сказать, что алгоритм Бойера – Мура на несколько порядков быстрей, чем обычный поиск как по временным показаниям так по количеству операций сравнения.

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

Искомая строка	Время поиска, нс	Количество сравнений
Ищем з	17700454	373978
Ищем зарубежных	13885656	162455
Ищем зарубежных партнеров или посредников	12078794	93432
Ищем зарубежных партнеров или посредников, имеющих выход на зарубежный рынок.	12976175	55995

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


Рисунок Пример работы программы

Вывод по разделу

Алгоритм Бойера – Мура является наиболее эффективным методом поиска подстроки в строке, он позволяет достигнуть увеличение скорости поиска до двух порядков по сравнению с простым поиском. Так же для оптимизации поиска следует максимально увеличить длину искомой строки.

3. 
   Исследование эффективности алгоритмов сортировок для различных структур и размерностей данных
   

3.1 Постановка задачи

• 
  Провести экспериментальный сравнительный анализ различных методов сортировки. Для чистоты эксперимента сортировка должна проводиться на одинаковых наборах входных данных, которые генерируются случайным образом. Для более полного анализа методов сортировка должна проводиться для различных размерностей данных
  
• 
  Проследить динамику роста требуемого для сортировки времени.
  
• 
  Проверить, как ведут себя методы на различных входных данных: упорядоченных в прямом порядке, упорядоченных в обратном порядке и случайных.
  
• 
  Сравнить теоретические оценки времени сортировки и числа требуемых операций с экспериментальными.