Файл: Алгоритмы сортировки данных. (ТЕОРЕТИЧЕСКИЕ АСПЕКТЫ АЛГОРИТМА СОРТИРОВКИ ДАННЫХ).pdf

Среднее время работы алгоритма зависит от длины промежутков d. Существует несколько подходов для выбора d. Первоначальная последовательность Шелла — di — N/2, (/_» — rfi/2,..., d^ — 1 дает сложность алгоритма в худшем случае 0(JV²). Последовательности Хиббар- да (^тр- < -j.' fc N), Фибоначчи, а также значения — дают сложность алгоритма Шелла 0(N²).

2.2 Эффективность алгоритма

Сортировка вставками - простой алгоритм сортировки. Несмотря на то, что данный алгоритм уступает в эффективности более сложным алгоритмам, у него имеется ряд преимуществ:

• эффективен на небольших наборах данных. На наборах ДЕННЫХ ДО нескольких десятков может оказаться лучшим;
• эффективен на наборах данных, которые уже частично уже отсортированы;
• это устойчивый алгоритм сортировки, т.е. не изменяет порядок элементов, которые уже отсортированы;
• может сортировать список по мере его получения.

Суть алгоритма вставками заключается в следующем. На каждом шаге алгоритма выбирается один из элементов входных данных и вставляется на нужную позицию в уже отсортированном списке, до тех пор, пока набор входных данных не будет исчерпан. Метод выбора очередного элемента из исходного массива произволен. Обычно., и с целью получения устойчивого алгоритма сортировки, элементы вставляются по порядку их появления во входном массиве. Временная сложность алгоритма сортировки вставками при худшем варианте входных данных 0(iV²).

2 г Рассмотрим тгепеj).ь основныо элементы тсхнолС)гз^ж MPI, MPI (Message Passing Interface, интерфейс передачи сообщений) - программный интерфейс (API) для передачи информации, который позволяет обмениваться сообщениями между процессами, выполняющими одну за- Дачу.

Наиболее распространенной технологией программирования параллельных компьютеров с распределенной памятью в настоящее время является MPI, Основным способом взаимодействия параллельных процессов в таких системах является передача сообщений друг другу. Это и отражено в названии данной технологии ~ Message Passing Interface. Интерфейс поддерживает создание параллельных программ в стиле MIMD, что подразумевает объединение процессов с различными исходными текстами. Однако на практике программисты гораздо чаще используют SPMD-модель, в рамках которой для всех параллельных процессов используется один и тот же код.

Все дополнительные объекты : имена функций, константы, предопределенные типы данных и т.п., используемые в MPI, имеют префикс MPI, Описания интерфейса MPI собраны в файле mpi.h, поэтому в начале MPI-ирограммы должна стоять директива include <mpi.h>.

Все функции передачи сообщений в MPI делятся на две группы. В одну группу входят функции, которые предназначены для взаимодействия двух процессов программы. Такие операции называются индивидуальными или операциями типа точка-точка. Функции другой группы предполагают, что в операцию должны быть вовлечены все процессы некоторого коммуникатора. Такие операции называются коллективными.

MPI-программа - это множество параллельных взаимодействующих процессов. Все процессы порождаются один раз, образуя параллельную часть программы. В ходе выполнения MPI-ирограммы порождение дополнительных процессов или уничтожение существующих не допускается. Каждый процесс работает в своем адресном пространстве, никаких общих переменных или данных в ]V1PI нет. Основным способом взаимодействия между процессами является явная посылка сообщений.

Для локализации взаимодействия параллельных процессов программы можно создавать группы процессов, предоставляя им отдельную среду для общения - коммуникатор. Состав образуемых групп произволен. Группы могут полностью входить одна в другую, не пересекаться или пересекаться частично. При старте программы всегда считается, что все порожденные процессы работают в рамках всеобъемлющего коммуникатора. Этот коммуникатор существует всегда и служит для взаимодействия всех процессов МР1-программы.

Каждый процесс MPI-программы имеет уникальный атрибут номер процесса, который является целым неотрицательным числом. С помощью этого атрибута происходит значительная часть взаимодействия процессов между собой. Ясно, что в одном и том же коммуникаторе все процессы имеют различные номера. Но поскольку процесс может одновременно входить в разные коммуникаторы, то его номер в одном коммуникаторе может отличаться от его номера в другом. Отсюда становятся понятными два основных атрибута процесса: коммуникатор и номер в коммуникаторе. Если группа содержит п. процессов, то номер любого процесса в данной группе лежит в пределах от 0 до п — 1.

Основным способом общения процессов между собой является посылка сообщений. Сообщение - это набор данных некоторого типа. Каждое сообщение имеет не-сколько атрибутов, в частности, номер процесса-отправителя, номер процесса-получателя, идентификатор сообщения и другие. Одним из важных атрибутов сообщения является его идентификатор или тэг. По идентификатору процесс, принимающий сообщение, например, может различить два сообщения, пришедшие к нему от одного и того же процесса. Сам идентификатор сообщения является целым неотрицательным числом, лежащим в диапазоне от 0 до 32767 [3].

2.3 Программная реализация алгоритма

Рассмотрим теперь программные реализации алгоритмов сортировки для их дальнейшего анализа на возможность распараллеливания [1, 4].

Код процедуры, реализующей сортировку пузырьками представлен ниже.

Сортировка вставками реализована в следующем фрагменте программы.

В следующем фрагменте представлена реализация сортировки Шелла,

Как видно из представленных фрагменотов программ итерации основных циклов сортировки данных являются информационно зависимыми (см. комментарии (1), (2), (3)) [2]. Таким образом, непосредственно распараллелитть итерации циклов по процессорам не представляется возможным.

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

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

Для численного моделирования был написан комплекс программ, реализующий алгоритмы сортировки по методу крупноблочного распараллеливания [2]. Результаты эксперимента приведены в таблицах.

Таблица 2.1 - Последовательная сортировка

Таблица 2.2 - Параллельная сортировка

Вычисления из табл- 1 и табл- 2 проводились на параллельной ЭВМ для случая р = 1 и р = 3 процессоров соответствено. Как видно из представ- Л6ННЫХ таблиц ускорение работы параллельной программы в зависимости от метода сортировки в среднем составила более 20 процентов , что свидетельствует о высокой степени параллелизма разработанных алгоритмов.

ЗАКЛЮЧЕНИЕ

Первая глава курсовой работы была посвящена, в основном, алгоритмам сортировки. Было показано, важность, актуальность и просто необходимость алгоритмов сортировки. Исследованы различные методы сортировки, основные характеристики алгоритмов сортировки. Так как рамки курсовой работы не позволяют подробно исследовать весь спектр различных видов алгоритмов поиска и сортировки, в курсовой работе были рассмотрены:

• сортировка вставкой;
• сортировка простым выбором;
• сортировка простым обменом;
• сортировка Шелла.

Из различных методов поиска были изучены и приведены следующие алгоритмы:

• • последовательный поиск;
  • бинарный поиск;
  • поиск подстроки методом грубой силы.

В результате исследования каждого алгоритма были показаны:

• основная идея алгоритм;
• суть алгоритма;
• приведен псевдокод алгоритма;
• приведен пример функционирования алгоритма.

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

СПИСОК ЛИТЕРАТУРЫ

1. Артемов А.В. Информационная безопасность. Курс лекций. - Орел: МАБИВ, 2014.
2. Бармен Скотт. Разработка правил информационной безопасности. - М.: Вильямс, 2012. - С. 208.
3. Гмурман А.И. Информационная безопасность. М.: "БИТ-М", 2014 г.
4. Журнал «Секретарское дело» №1 2010 год
5. Информационная безопасность и защита информации Мельников В. П. и др. / Под ред. Клейменова С. А.- М.: ИЦ «Академия», 2012.336 с.
6. Петров В. А., Пискарев А.С., Шеин А.В. Информационная безопасность. Защита информации от несанкционированного доступа в автоматизированных системах. Учебное пособие. - М.: МИФИ, 2015.
7. Современная компьютерная безопасность. Теоретические основы. Практические аспекты. Щербаков А. Ю. - М.: Книжный мир, 2009.- 352 с.
8. Соляной В.Н., Сухотерин А.И. Взаимодействие человека, техники и природы: проблема информационной безопасности. Научный журнал (КИУЭС) Вопросы региональной экономики. УДК 007.51 №5 (05) Королев. ФТА. - 2010.
9. Справочно-правовая система «Консультант Плюс».
10. Стандарты информационной безопасности Галатенко В. А.- М.: Интернет-университет информационных технологий, 2012. - 264 с.
11. Хачатурова С.С. Информационные технологии в юриспруденции: учебное пособие. // Фундаментальные исследования. - 2015. - № 9. - С. 8-9.
12. Хачатурова С.С. Организация предпринимательской деятельности. Создание собственного дела // Международный журнал экспериментального образования. - 2012. - № 2. - С. 137-138.
13. Шаньгин В.Ф. Защита компьютерной информации. Эффективные методы и средства. - М.: ДМК Пресс, 2008. - С. 544.
14. Шутова Т.В., Старцева Т.Е. Высокотехнологичный комплекс России - платформа для инновационного прорыва. Научный журнал (КИУЭС) Вопросы региональной экономики. УДК 007.51 №2 (11) г. Королев. ФТА. 2012г.
15. http://www. safensoft.ru/security.phtml?c=791.
16. http://www.abc-people.com/typework/economy/e- confl-8.htm.
17. http://www.epam-group.ru/aboutus/news-and-events/ articles/2009/aboutus-ar-gaz-prom-09-01-2009.html.
18. http://www.nestor.minsk.by/sr/2007/07/sr70713.html.
19. Kaspersky.ru. Режим доступа: http://www.kaspersky.ru/ about/news/business/2012/Zaschita_dlya_Titana_Laboratoriya_ Kasperskogo_obespechivaet_bezopasnost_Korporaciya_ VSMPO-AVISMA.