Введение к работе
Актуальность темы. Современный этап становления общества неотъемлемо связан с развитием информационных технологий, связанным с накопление информации и организация оперативного доступа к ней. Составляющими информационного процесса является обеспечение релевантности поискового процесса и сокращение времени поиска релевантной информации. Оба этих процесса определяются, с одной стороны, аппаратной базой поисковой системы и структурой информационных массивов, а с другой стороны, алгоритмами поиска данных, реализуемыми в конкретных информационно-поисковых системах с конкретно организационной структурой данных. В тех случаях, когда информационный массив представляет собой значительные массы данных, разнообразных по тематике, прикладному назначению, временному показателю, даже в рационально организованных базах данных возникает проблема сокращения времени обработки запроса информационно-поисковой системой. Существуют различные способы сокращения времени поиска, ориентированные на конкретную модель представления данных, что затрудняет их применение с целью разработки оптимальных поисковых процессов в информационных системах. Однако существует универсальный способ ускорения поискового процесса, заключающийся в его распараллеливании и реализации на уже существующих вычислительных сетях учреждений. Задачи распараллеливания поискового процесса требует разработки специализированного алгоритмического программного обеспечения, а также методики оценки времени поисковой процедуры, что в настоящее время развито недостаточно, чем и объясняется необходимость и актуальность исследований, проведенных в данной работе.
Таким образом, объектом исследования диссертационной работы является информационно-поисковая система со значительным объемом массивов данных, реализованная в вычислительной сети предприятия.
В качестве предмета исследования были выбраны методы организации параллельного поискового процесса и временные характеристики поисковых алгоритмов.
Цель работы – повышение временной эффективности поиска за счет распараллеливания поисковых процедур в пределах вычислительной сети.
Для достижения в работе поставленная цель достигается решением следующих задач:
- обеспечивается проведением аналитического обзора типовых моделей данных и поисковых алгоритмов, а также методов моделирования функционирования поисковых систем;
- обоснование применения сетей Петри-Маркова (СПМ) в качестве инструментария для моделирования и оценки временной сложности параллельных поисковых алгоритмов;
- определение способов задания СПМ, позволяющие проводить оценку временной сложности поисковых алгоритмов, а также, обеспечивающих последовательные упрощения СПМ;
-получение зависимостей для расчета временных и вероятностных характеристик для процедур: расщепления позиций, объединения позиций, устранения циклов, объединения последовательных позиций, объединения параллельных переходов;
- разработка метода последовательных упрощений СПМ;
- проведение выбора поискового алгоритма, который может быть реализован в вычислительной сети;
- разработке метода преобразования последовательного поискового алгоритма в параллельный;
- разработке программного продукта и рекомендации по организационной структуре базы данных, реализующий параллельный поиск с использованием сетевых ресурсов.
Методы исследования. Исследования, основаны на аналитических методах теории алгоритмов, теории случайных (марковских) процессов, сетей Петри. Перечисленным выше аналитическим методам исследования посвящены работы отечественных ученых: В.А. Евстигнеева, А.А. Маркова, В.Е.Котова, В.К. Сабельфельда, В.П. Дрибаса, А.А. Шалыто и др., а также зарубежных специалистов: К. Беджа, А. Кофмана, М. Свами, Р. Ульсона и др. Исследования в области алгоритмов сортировки и поиска, а также проектированием и системой управления баз данных посвящены работы специалистов: Д. Кнута, Фостера Дж. Гарсия-Молина Г., Петри К., Питерсон Дж. и др.
Научная новизна исследований заключается в следующем:
- предложено моделирование поисковых алгоритмов с помощью сетей Петри-Маркова, что позволяет оценивать временную сложность выполнения поискового алгоритма с точностью до математических ожиданий, а исход поиска с точностью до вероятностей;
- разработана методика разделения последовательной элементарной сети Петри-Маркова на информационно независимые фрагменты с формированием их фрагментов параллельной СПМ, моделирующей поисковый процесс в локальной вычислительной сети;
- предложен принцип формирования СПМ, по которому элементарные сети Петри-Маркова (ЭСПМ) объединяются в сложную сеть, реализующую параллельный поисковый алгоритм;
- разработан метод последовательных упрощений и получены зависимости для оценки временной сложности сетей Петри-Маркова математически подобных поисковым алгоритмам локальной вычислительной сети, которая может быть использована для оценки временной сложности алгоритмов.
Практическая ценность диссертации состоит в:
реализации основных принципов построения параллельных процессов поиска данных с применением СПМ;
- разработке комбинированного алгоритма, реализующий параллельную процедуру поиска в сети обработки данных;
- разработке алгоритма с применением методов параллельного поиска данных.
Достоверность подтверждается корректным применением теории случайных процессов, теории сетей Петри и практическим применением перечисленных теорий для создания программного продукта, реализующего параллельный поисковый процесс, что подтверждается актами внедрения.
Положения, выносимые на защиту:
1) Модели поисковых алгоритмов, построенные при помощи математического аппарата сетей Петри-Маркова.
2) Методика разделения последовательной элементарной сети Петри-Маркова на информационно независимые фрагменты.
3) Принцип, объединения элементарных подсетей в параллельную сеть Петри-Маркова.
4) Метод и зависимости расчета временной сложности поисковых алгоритмов.
5) Получена зависимость, определяющая эффективность параллельного поиска путем применения методов упрощения СПМ.
Реализация результатов диссертационной работы. Предложенные в диссертации методы реализованы при внедрении в учебный процесс Тульского государственного университета на кафедре «Робототехника и автоматизация производства» в курсе «Специальные главы математики», «Дискретная математика», «Компьютерные технологии» а также в производство в рамках научно-технического сотрудничества с компанией ЗАО «Протек».
Апробация работы. Основные результаты диссертационной работы докладывались на следующих конференциях и семинарах: научно-техническая конференция профессорско-преподавательского состава кафедры РТиАП (Тула, ТулГУ, 2004, 2005, 2006, 2009, 2010, 2011 г.г.); 14-я научно - техническая конференция (Тула, ТАИИ. 2005г.); XXIV Научная сессия, посвященная Дню радио НТО РЭС им. А.С. Попова (Тула, 2006, 2007г.г.); Международная молодежная научная конференция «XXVII Гагаринские чтения» (Москва, МАТИ, 2009);
Публикации. По теме диссертации опубликовано 17 печатных работ: 6 статей в изданиях из перечня ВАК, 6 статей в межвузовских сборниках, 5 докладов на Всероссийских конференциях.
Характеристика работы. Диссертационная работа состоит из введения, четырех глав и заключения, содержит 174 страницы, 68 рисунков, 2 таблицы, список использованной литературы из 120 наименований.
