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

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

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

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

Перечислим рассматриваемые здесь дискретные многокритериальные задачи:

  1. - задача о совершенных паросочетаниях, в которой - совершенное паросочетание графа с четным числом вершин ;

  2. - задача об остовных деревьях, - остовное дерево связного -вершинного графа;

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

  4. - задача о коммивояжере, - гамильтонов цикл в -вершинном графе;

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

  6. - задача о назначениях, т.е. задача о совершенных паросочетаниях на двудольном графе , , - совершенное паросочетание на .

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

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

1.3 Постановка задачи исследования

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

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

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

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

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

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

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

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

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

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

В процессе проектирования СОД возникает необходимость учета вектора критериев оптимизации, которые часто бывают противоречивым.

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

Анализ существующих методов проектирования модульных систем обработки данных (МСОД), алгоритмов реализации этих моделей и проведенные исследования показали необходимость разработки новых подходов и классов моделей и методов проектирования систем обработки данных.

На основе проведенного анализа моделей и методов проектирования СОД сформулированы задачи исследования.

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

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

- сформулировать и решить задачу декомпозиции систем обработки данных на кластеры функциональных задач и исходных документов;

- разработать методы синтеза модульных блок-схем обработки данных;

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

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

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

  • Приведен анализ существующих моделей и методов проектирования модульных систем обработки данных.

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

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

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), которые зависят от переменной .

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

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

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

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

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