Xreferat.com » Рефераты по информатике и программированию » Блочно-симметричные модели и методы проектирования систем обработки данных

Блочно-симметричные модели и методы проектирования систем обработки данных

обработки данных.

Сформулированы задачи диссертационного исследования.


2. БЛОЧНО-СИММЕТРИЧНЫЕ МОДЕЛИ И МЕТОДЫ ПРОЕКТИРОВАНИЯ СИСТЕМ ОБРАБОТКИ ДАННЫХ


В данном разделе рассматриваются общая постановка блочно-симметричной задачи дискретного программирования, её особенности и свойства. Разработан общий подход решения задач данного класса.

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

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

Сформулирован также частные задачи проектирования модульных блок-схем обработки данных [142]


2.1 Общая постановка блочно-симметричных задач дискретного программирования


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

Рассмотрим общую постановку блочно-симметричных задач дискретного программирования [126, 127].

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


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


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

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

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

Блочно-симметричная задача дискретного программирования формулируется следующим образом:

Блочно-симметричные модели и методы проектирования систем обработки данных,(2.1.1)


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


Блочно-симметричные модели и методы проектирования систем обработки данных(2.1.2)

Блочно-симметричные модели и методы проектирования систем обработки данных(2.1.3)


В множестве ограничений (2.1.2) и (2.1.3) в зависимости от постановок задач знаки неравенств могут меняться на противоположеные.

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

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


Блочно-симметричные модели и методы проектирования систем обработки данных(2.1.4)


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

В задаче (2.1.1) -(2.1.3) можно выделить множество ограничений вида (2.1.2), которые зависят от переменной Блочно-симметричные модели и методы проектирования систем обработки данных, и множество ограничений вида (2.1.3), которые зависят от переменной Блочно-симметричные модели и методы проектирования систем обработки данных.

Функционал вида Блочно-симметричные модели и методы проектирования систем обработки данных можно представить следующим образом:


Блочно-симметричные модели и методы проектирования систем обработки данных(2.1.5)

Блочно-симметричные модели и методы проектирования систем обработки данных(2.1.6)

Блочно-симметричные модели и методы проектирования систем обработки данных(2.1.7)

Блочно-симметричные модели и методы проектирования систем обработки данных(2.1.8)

Блочно-симметричные модели и методы проектирования систем обработки данных(2.1.9)


В постановке задачи (2.1.5) - (2.1.9) выделим блок функции (2.1.6), (2.1.7), зависящий только от переменной Блочно-симметричные модели и методы проектирования систем обработки данных, и блок функций (2.1.8), (2.1.9), зависящий только от переменной Блочно-симметричные модели и методы проектирования систем обработки данных, объединенных единым функционалом вида (2.1.5). Заметим, что в ряде постановок задач может быть блок ограничений вида


Блочно-симметричные модели и методы проектирования систем обработки данных(2.1.10)


зависящий от переменных Блочно-симметричные модели и методы проектирования систем обработки данных и Блочно-симметричные модели и методы проектирования систем обработки данных.

В этом случае можно выделить блок функционала цели вида (2.1.5), (2.1.10).

Отсюда следует.

Определение 2.1. Блочно-симметричной задачей дискретного программирования назовем задачу вида (2.1.5) - (2.1.9), где переменные Блочно-симметричные модели и методы проектирования систем обработки данных и Блочно-симметричные модели и методы проектирования систем обработки данных и значения функций Блочно-симметричные модели и методы проектирования систем обработки данных, Блочно-симметричные модели и методы проектирования систем обработки данных, Блочно-симметричные модели и методы проектирования систем обработки данных - целые, либо булевые

Рассмотрим выражение (2.1.4). из него следует что переменные Блочно-симметричные модели и методы проектирования систем обработки данных и Блочно-симметричные модели и методы проектирования систем обработки данных симметричны относительно заданной матрицы Блочно-симметричные модели и методы проектирования систем обработки данныхи функция (2.1.4) может быть определена как слева направо, так и наоборот, т.е.


Блочно-симметричные модели и методы проектирования систем обработки данных(2.1.11)


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

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

В общем случае переменных может быть и больше в зависимости от постановок задач.

Свойство 2. Блочность задачи заключается в выделении в постановке отдельных блоков функций вида (2.1.5), (2.1.10); (2.1.6), (2.1.7) и (2.1.8), (2.1.9), которые соответственно зависят от переменных Блочно-симметричные модели и методы проектирования систем обработки данных и Блочно-симметричные модели и методы проектирования систем обработки данных.

Как видно из указанных соотношении каждый из блоков имеет свою целевую функцию и координируется общим функционалом вида (2.1.5).

Свойство 3. Блочно-симметричную задачу в большинстве случаев можно представить в матричной форме вида (2.1.11).

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

Свойство 4. Симметричность задачи заключается в возможности вычисления (2.1.11) как слева направо, так и обратном направлении.

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

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

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

Утверждение. Распределение элементов множества Блочно-симметричные модели и методы проектирования систем обработки данных по непересекающим подмножествам Блочно-симметричные модели и методы проектирования систем обработки данных соответствует логическому сложению строк матриц Блочно-симметричные модели и методы проектирования систем обработки данных, а распределение элементов множества Блочно-симметричные модели и методы проектирования систем обработки данных по непересекающимся подмножествам Блочно-симметричные модели и методы проектирования систем обработки данных - логическому сложению столбцов матрицы Блочно-симметричные модели и методы проектирования систем обработки данных. [132, 133] Результаты данного утверждения позволяют просто вычислить оценки и направления поиска решения для разработки эффективных алгоритмов.

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

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

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

В булевой матрице Блочно-симметричные модели и методы проектирования систем обработки данныхвыделим подматрицу Блочно-симметричные модели и методы проектирования систем обработки данных, Блочно-симметричные модели и методы проектирования систем обработки данных, Блочно-симметричные модели и методы проектирования систем обработки данных и определим её как базис решения задачи.

Определим матрицу Блочно-симметричные модели и методы проектирования систем обработки данных, Блочно-симметричные модели и методы проектирования систем обработки данных, Блочно-симметричные модели и методы проектирования систем обработки данныхнаправления поиска решения Блочно-симметричные модели и методы проектирования систем обработки данных путем логического сложения небазисных строк матрицы Блочно-симметричные модели и методы проектирования систем обработки данных со строками базиса и вычислим значения оценок только

Если Вам нужна помощь с академической работой (курсовая, контрольная, диплом, реферат и т.д.), обратитесь к нашим специалистам. Более 90000 специалистов готовы Вам помочь.
Бесплатные корректировки и доработки. Бесплатная оценка стоимости работы.

Поможем написать работу на аналогичную тему

Получить выполненную работу или консультацию специалиста по вашему учебному проекту
Нужна помощь в написании работы?
Мы - биржа профессиональных авторов (преподавателей и доцентов вузов). Пишем статьи РИНЦ, ВАК, Scopus. Помогаем в публикации. Правки вносим бесплатно.

Похожие рефераты: