Электронная библиотека Веда
Цели библиотеки
Скачать бесплатно
Доставка литературы
Доставка диссертаций
Размещение литературы
Контактные данные
Я ищу:
Библиотечный каталог российских и украинских диссертаций

Вы находитесь:
Диссертационные работы России
Технические науки
Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей

Диссертационная работа:

Никитина Галина Николаевна. Применение теории сетей петри-маркова в организации параллельных поисковых процессов: автореферат дис. ... кандидата технических наук: 05.13.11 / Никитина Галина Николаевна;[Место защиты: ФГБОУ ВПО «Тульский государственный университет»].- Тула, 2012.- 16 с.

смотреть введение
Введение к работе:

Актуальность темы. Современный этап становления общества неотъемлемо связан с развитием информационных технологий, связанным с накопление информации и организация оперативного доступа к ней. Составляющими информационного процесса является обеспечение релевантности поискового процесса и сокращение времени поиска релевантной информации. Оба этих процесса определяются, с одной стороны, аппаратной базой поисковой системы и структурой информационных массивов, а с другой стороны, алгоритмами поиска данных, реализуемыми в конкретных информационно-поисковых системах с конкретно организационной структурой данных. В тех случаях, когда информационный массив представляет собой значительные массы данных, разнообразных по тематике, прикладному назначению, временному показателю, даже в рационально организованных базах данных возникает проблема сокращения времени обработки запроса информационно-поисковой системой. Существуют различные способы сокращения времени поиска, ориентированные на конкретную модель представления данных, что затрудняет их применение с целью разработки оптимальных поисковых процессов в информационных системах. Однако существует универсальный способ ускорения поискового процесса, заключающийся в его распараллеливании и реализации на уже существующих вычислительных сетях учреждений. Задачи распараллеливания поискового процесса требует разработки специализированного алгоритмического программного обеспечения, а также методики оценки времени поисковой процедуры, что в настоящее время развито недостаточно, чем и объясняется необходимость и актуальность исследований, проведенных в данной работе.

Таким образом, объектом исследования диссертационной работы является информационно-поисковая система со значительным объемом массивов данных, реализованная в вычислительной сети предприятия.

В качестве предмета исследования были выбраны методы организации параллельного поискового процесса и временные характеристики поисковых алгоритмов.

Цель работы – повышение временной эффективности поиска за счет распараллеливания поисковых процедур в пределах вычислительной сети.

Для достижения в работе поставленная цель достигается решением следующих задач:

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

- обоснование применения сетей Петри-Маркова (СПМ) в качестве инструментария для моделирования и оценки временной сложности параллельных поисковых алгоритмов;

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

-получение зависимостей для расчета временных и вероятностных характеристик для процедур: расщепления позиций, объединения позиций, устранения циклов, объединения последовательных позиций, объединения параллельных переходов;

- разработка метода последовательных упрощений СПМ;

- проведение выбора поискового алгоритма, который может быть реализован в вычислительной сети;

- разработке метода преобразования последовательного поискового алгоритма в параллельный;

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

Методы исследования. Исследования, основаны на аналитических методах теории алгоритмов, теории случайных (марковских) процессов, сетей Петри. Перечисленным выше аналитическим методам исследования посвящены работы отечественных ученых: В.А. Евстигнеева, А.А. Маркова, В.Е.Котова, В.К. Сабельфельда, В.П. Дрибаса, А.А. Шалыто и др., а также зарубежных специалистов: К. Беджа, А. Кофмана, М. Свами, Р. Ульсона и др. Исследования в области алгоритмов сортировки и поиска, а также проектированием и системой управления баз данных посвящены работы специалистов: Д. Кнута, Фостера Дж. Гарсия-Молина Г., Петри К., Питерсон Дж. и др.

Научная новизна исследований заключается в следующем:

- предложено моделирование поисковых алгоритмов с помощью сетей Петри-Маркова, что позволяет оценивать временную сложность выполнения поискового алгоритма с точностью до математических ожиданий, а исход поиска с точностью до вероятностей;

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

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

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

Практическая ценность диссертации состоит в:

реализации основных принципов построения параллельных процессов поиска данных с применением СПМ;

- разработке комбинированного алгоритма, реализующий параллельную процедуру поиска в сети обработки данных;

- разработке алгоритма с применением методов параллельного поиска данных.

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

Положения, выносимые на защиту:

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 наименований.


© Научная электронная библиотека «Веда», 2003-2013.
info@lib.ua-ru.net