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

Вы находитесь:
Диссертационные работы России
Технические науки
Теоретические основы информатики

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

Ершова Арина Владимировна. Итерационные методы и алгоритмы решения задачи сильной отделимости: автореферат дис. ... кандидата физико-математических наук: 05.13.17 / Ершова Арина Владимировна;[Место защиты: Южно-Уральский государственный университет].- Челябинск, 2012.- 16 с.

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

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

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

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

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

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

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

  1. Описать общий подход к решению задачи сильной отделимости двух выпуклых многогранников на основе последовательных проектирований.

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

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

4. Спроектировать и реализовать программный комплекс для решения задачи силь-

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

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

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

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

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

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

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

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

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

на Международной конференции «Алгоритмический анализ неустойчивых задач» (1-6 сентября 2008 г., г. Екатеринбург);

на Международной научной конференции «Параллельные вычислительные технологии (ПаВТ'2010)» (29 марта - 2 апреля 2010 г., г. Уфа);

на XVIII Международной конференции «Математика. Экономика. Образование» (25 мая - 1 июня 2010 г., г. Новороссийск);

на Международной научной конференции «Научный сервис в сети Интернет: суперкомпьютерные центры и задачи» (20-25 сентября 2010 г., г. Новороссийск);

на XIV Всероссийской конференции "Математическое программирование и приложения" (28 февраля - 4 марта 2011 г., г. Екатеринбург);

на Международной научной конференции «Научный сервис в сети Интернет: эк-зафлопсное будущее» (19-24 сентября 2011 г., г. Новороссийск);

на Международной научной конференции «Параллельные вычислительные технологии (ПаВТ'2012)» (26-30 марта 2012 г., г. Новосибирск).

Публикации. По теме диссертации опубликовано 10 печатных работ, причем работы [1-4] опубликованы в журналах, включенные ВАК в перечень журналов, в которых должны быть опубликованы основные результаты диссертаций на соискание ученой степени доктора и кандидата наук. Получено 3 свидетельства Роспатента об официальной регистрации программ для ЭВМ. В совместных работах научному руководителю И.М. Соколинской принадлежит постановка задачи, А.В. Ершовой принадлежат все полученные результаты.

Структура и объем работы. Диссертация состоит из введения, четырех глав, заключения и библиографии. Объем диссертации составляет 97 страниц, объем библиографии - 92 наименования.


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