Готовая курсовая работа

ВВЕДЕНИЕ 2

1 Теория алгебры кортежей 5

2 Технологии распараллеливания программ 11

3.Практическая часть 12

3.1 Параллельные вычисления 12

3.2 Способы синхронизации параллельного взаимодействия 13

3.3 Параллельные вычислительные системы 17

4 Реализация алгоритмов текстового поиска на базе алгебры кортежей 26

4.1 Входные данные 26

4.3 Реализация параллельного алгоритма на базе интерфейса MPI 33

5 Технико-экономическое обоснование 35

5.1 Концепция научно-технического проекта 35

5.2 Расчет полных затрат при разработке программного модуля 36

5.3 Расчет затрат на разработку прототипа 37

Заключение 42

СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ 43

ПРИЛОЖЕНИЕ А 44

Алгоритмы поиска соответствия строк являются разновидностью алгоритмов, которые ищут заданную строку, во входящем строковом потоке.
Эти алгоритмы представляют собой важную область исследований в области компьютерных наук. Их использование может быть использован в широком диапазоне областей от управления базами данных и информационной безопасности до обработки изображений и поиска нуклеотидной последовательности. На практике используются множество алгоритмов поиска соответствия подстроки в строке, а их функциональные возможности и характеристики отличаются друг от друга в различных формах. Данная работа представляет исследование параллельного алгоритма сопоставления строки, которая называется Bitap, и сравнивает ее производительность с последовательным алгоритмом поиска соответствия подстроки. Как тестовые данные были выбран область нуклеотидных последовательностей. Изучение нуклеотидных последовательностей имеют огромное значение в биологических науках, а количество доступных для исследования данных удваивается каждые восемнадцать месяцев. Алгоритм Bitap использует побитовые операторы для того, чтобы найти данные модели во входящем потоке текста, поэтому исследуя внутреннюю механику этого алгоритма сопоставления строки и сравнения и сопоставления его с полезности различных алгоритмов 'в области нуклеотидных последовательностей, может быть привлекательным, из-за экзотичности Bitap.
Объектом исследования является алгоритмы текстового поиска.
Предметом – параллельный алгоритм текстового поиска на базе алгебры кортежей.
Цель данной работы – Написание последовательного и параллельного алгоритмов текстового поиска на базе алгебры кортежей с использованием библиотеки MPICH2. Произвести анализ скоростных характеристик и сравнить с существующими алгоритмами.
Для достижения поставленной цели были решены следующие задачи:анализ существующих решений; разработка последовательного алгоритма текстового поиска; разработка параллельного алгоритма текстового поиска; Проведение экспериментов параллельного и последовательного алгоритмов Сравнение данных алгоритмов с существующими решениями. первом разделе проводится анализ наиболее известных алгоритмов: наивный алгоритм, двоичный алгоритм, алгоритм Бойера-Мура, алгоритм Кнута-Морриса-Пратта, алгоритм Робина-Карпа.
Во втором разделе приводится основные термины алнебры кортежей алгебры кортежей, так же подробно рассматривается алгоритм текстового поиска на базе алгебры кортежей.
В третьем разделе приводятся общие вопросы параллельных вычислений. Рассматриваются подходы распараллеливания алгоритмов.
Рассмотрены наиболее популярны библиотеки четвертом разделе описывается ход написания последовательного алгоритма. Описан параллельный алгоритм, представлена его реализация.

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