49743 (588672), страница 11

Файл №588672 49743 (Блочно-симметричные модели и методы проектирования систем обработки данных) 11 страница49743 (588672) страница 112016-07-29СтудИзба
Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 11)

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

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

Задача разработки логической структуры базы данных при заданном множестве программных модулей (запросов) формулируется следующим образом [124-131].

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

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

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

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

Тогда, задача примет вид:

.(2.4.1)

При ограничениях на:

- число информационных элементов в записи массива

, ,(2.4.1)

где -допустимое число информационных элементов в записи массива;

- дублирование информационных элементов в массивах базы данных

, .(2.4.2)

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

.(2.4.3)

При проектировании модульных систем обработки данных возможен случай, когда база данных уже разработана и сформулирована для решения приложений [132,133].

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

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

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

Задача формулируется следующим образом.

.(2.4.5)

при ограничениях на:

- число процедур в составе модуля

, ;(2.4.6)

- дублирования процедур в модуле

, .(2.4.7)

Сформулированная задача также сводится к блочно-симметричной задаче. Матричное представление целевой функции имеет вид:

.(2.4.8)

Таким образом, сформулированные выше задачи (2.4.1)-(2.4.3) и (2.4.5)-(2.4.7) являются частными блочно-симметричными задачами ДП. Для их решения разработан и предложен эффективный алгоритм, приведенный в разделе 3.

Выводы к разделу 2

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

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

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

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

3. МЕТОДЫ И АЛГОРИТМЫ РЕШЕНИЯ БЛОЧНО-СИММЕТРИЧНЫХ ЗАДАЧ ПРОЕКТИРОВАНИЯ СИСТЕМ ОБРАБОТКИ ДАННЫХ. МНОГОКРИТЕРИАЛЬНАЯ ЗАДАЧА СИНТЕЗА МОДУЛЬНЫХ БЛОК-СХЕМ ОБРАБОТКИ ДАННЫХ

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

3.1 Эффективный алгоритм решения блочно-симметричных задач проектирования модульных блок-схем обработки данных

Анализ методов и алгоритмов решения задач дискретного программирования показал, что они, в основном, являются NP-полными и имеют экспоненциальную вычислительную сложность. Следовательно, не могут быть решены задачи большой размерности в различных приложениях [134-137].

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

Рассмотрим алгоритм решения блочно-симметричных задач вида (2.2.1)-(2.2.5), (3.2.1)-(3.2.7), а также частных задач [138].

Для описания алгоритма введем следующие понятия.

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

Определение 3.1.1. Подматрицу , где ; ; ; , определенную на исходной матрице , назовем исходным базисом решения задачи.

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

Определение 3.1.2. Величины

(3.1.1)

и

(3.1.2)

назовём расстоянием между строками (столбцами) не вошедшими в базис и строками (столбцами), которые вошли в базис.

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

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

Алгоритм состоит из ряда итераций. Поэтому определим его как алгоритм итеративных отображений (АИО). Алгоритм состоит из следующих операций:

  1. Ввод матрицы . Выделение базиса в матрице . Переход к 2.

  2. Вычислить величины и составить матрицу . Зафиксировать состояние матрицы . Переход к 3.

  3. -я итерация.

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

    2. Определить элементы матрицы . Проверить ограничения на число процедур в составе каждого модуля. Если оно неудовлетворительно, то перейти к 3.3, иначе к 3.1.

    3. Исключить из рассмотрения элемент . Установить . Переход к 3.1.

    4. Вычислить состояние матрицы . Переход к 3.5.

    5. Исключить из рассмотрения строку с номером . Пересчитать величины относительно столбца с учетом нового состояния . Переход к 3.6.

    6. Проверить условие: все ли процедуры распределены? Если нет, то перейти к следующей итерации, приняв . Иначе переход к 4

  1. Запомнить содержание матриц и . Переход к 5.

  2. Вычислить относительно и составить матрицу . Переход к 6.

  3. -я итерация.

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

    2. Определить элементы матрицы . Проверить ограничения на число информационных элементов в логическом массиве. Если оно неудовлетворительно, то перейти к 6.3.

    3. Исключить из рассмотрения элемент . Установить . Переход к 6.1.

    4. Вычислить состояние матрицы . Переход к 6.5.

    5. Исключить из рассмотрения строку с номером . Пересчитать величины относительно столбца с учетом нового состояния . Переход к 6.6.

    6. Проверить условие: все ли информационные элементы распределены? Если нет, то перейти к следующей итерации, приняв . Иначе переход к 7.

  1. Вывод решения задачи: матриц , , и значение целевой функции .

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

Характеристики

Тип файла
Документ
Размер
8,2 Mb
Учебное заведение
Неизвестно

Список файлов ВКР

Свежие статьи
Популярно сейчас
Зачем заказывать выполнение своего задания, если оно уже было выполнено много много раз? Его можно просто купить или даже скачать бесплатно на СтудИзбе. Найдите нужный учебный материал у нас!
Ответы на популярные вопросы
Да! Наши авторы собирают и выкладывают те работы, которые сдаются в Вашем учебном заведении ежегодно и уже проверены преподавателями.
Да! У нас любой человек может выложить любую учебную работу и зарабатывать на её продажах! Но каждый учебный материал публикуется только после тщательной проверки администрацией.
Вернём деньги! А если быть более точными, то автору даётся немного времени на исправление, а если не исправит или выйдет время, то вернём деньги в полном объёме!
Да! На равне с готовыми студенческими работами у нас продаются услуги. Цены на услуги видны сразу, то есть Вам нужно только указать параметры и сразу можно оплачивать.
Отзывы студентов
Ставлю 10/10
Все нравится, очень удобный сайт, помогает в учебе. Кроме этого, можно заработать самому, выставляя готовые учебные материалы на продажу здесь. Рейтинги и отзывы на преподавателей очень помогают сориентироваться в начале нового семестра. Спасибо за такую функцию. Ставлю максимальную оценку.
Лучшая платформа для успешной сдачи сессии
Познакомился со СтудИзбой благодаря своему другу, очень нравится интерфейс, количество доступных файлов, цена, в общем, все прекрасно. Даже сам продаю какие-то свои работы.
Студизба ван лав ❤
Очень офигенный сайт для студентов. Много полезных учебных материалов. Пользуюсь студизбой с октября 2021 года. Серьёзных нареканий нет. Хотелось бы, что бы ввели подписочную модель и сделали материалы дешевле 300 рублей в рамках подписки бесплатными.
Отличный сайт
Лично меня всё устраивает - и покупка, и продажа; и цены, и возможность предпросмотра куска файла, и обилие бесплатных файлов (в подборках по авторам, читай, ВУЗам и факультетам). Есть определённые баги, но всё решаемо, да и администраторы реагируют в течение суток.
Маленький отзыв о большом помощнике!
Студизба спасает в те моменты, когда сроки горят, а работ накопилось достаточно. Довольно удобный сайт с простой навигацией и огромным количеством материалов.
Студ. Изба как крупнейший сборник работ для студентов
Тут дофига бывает всего полезного. Печально, что бывают предметы по которым даже одного бесплатного решения нет, но это скорее вопрос к студентам. В остальном всё здорово.
Спасательный островок
Если уже не успеваешь разобраться или застрял на каком-то задание поможет тебе быстро и недорого решить твою проблему.
Всё и так отлично
Всё очень удобно. Особенно круто, что есть система бонусов и можно выводить остатки денег. Очень много качественных бесплатных файлов.
Отзыв о системе "Студизба"
Отличная платформа для распространения работ, востребованных студентами. Хорошо налаженная и качественная работа сайта, огромная база заданий и аудитория.
Отличный помощник
Отличный сайт с кучей полезных файлов, позволяющий найти много методичек / учебников / отзывов о вузах и преподователях.
Отлично помогает студентам в любой момент для решения трудных и незамедлительных задач
Хотелось бы больше конкретной информации о преподавателях. А так в принципе хороший сайт, всегда им пользуюсь и ни разу не было желания прекратить. Хороший сайт для помощи студентам, удобный и приятный интерфейс. Из недостатков можно выделить только отсутствия небольшого количества файлов.
Спасибо за шикарный сайт
Великолепный сайт на котором студент за не большие деньги может найти помощь с дз, проектами курсовыми, лабораторными, а также узнать отзывы на преподавателей и бесплатно скачать пособия.
Популярные преподаватели
Добавляйте материалы
и зарабатывайте!
Продажи идут автоматически
6367
Авторов
на СтудИзбе
309
Средний доход
с одного платного файла
Обучение Подробнее