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

[ виправити ] текст може містити помилки, будь ласка перевіряйте перш ніж використовувати.

скачати

Казахський Національний Технічний Університет імені К. І. Сатпаєва

УДК 658.512 519.87 004.83на правах рукопису

Набієв ГУЛНАЗ СОЦІАЛЕВНА

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

Республіки Казахстан

Алмати, 2010

ЗМІСТ

ПОЗНАЧЕННЯ І СКОРОЧЕННЯ

ВЕДЕННЯ

1. МОДЕЛІ І МЕТОДИ ПРОЕКТУВАННЯ модульну систему ОБРОБКИ ДАНИХ

1.1 Огляд моделей аналізу і синтезу модульних систем обробки даних

1.2 Моделі і методи розв'язання задач дискретного програмування при проектуванні систем обробки даних

Постановка завдання дослідження

Висновки по розділу

2. Блочно-симетрична модель І МЕТОДИ ПРОЕКТУВАННЯ СИСТЕМ ОБРОБКИ ДАНИХ

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

програмування

2.2 Декомпозиція прикладних завдань і вихідних документів систем обробки даних на етапі технічного проектування

2.3 Проектування модульних блок-схем систем обробки даних

2.4 Приватні завдання проектування модульних блок-схем систем обробки даних

Висновки по розділу 2

3. МЕТОДИ І АЛГОРИТМИ розв'язання блочних-симетричні

ЗАВДАНЬ ПРОЕКТУВАННЯ СИСТЕМ ОБРОБКИ ДАНИХ. Багатокритеріальна задача СИНТЕЗУ Модульний блок-СХЕМ ОБРОБКИ ДАНИХ

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

3.2 Постановка і рішення багатокритеріальних задач розробки модульних блок-схем обробки даних

3.3 Програмне забезпечення двухкрітеріальной задачі проектування модульних систем обробки даних

3.3.1 Опис програмного забезпечення вирішення завдань проектування модульної блок-схеми обробки даних

3.3.2 Опис логічної структури розробленої програми призначеної для вирішення двухкрітеріальной завдання проектування модульної блок-схеми обробки даних

3.3.4 Виклик і завантаження програми

Висновки по розділу 3

ВИСНОВОК

СПИСОК ВИКОРИСТАНИХ ДЖЕРЕЛ

ПОЗНАЧЕННЯ І СКОРОЧЕННЯ

АІО - алгоритм ітеративних відображень

БД - база даних

ВЗП - зовнішня запам'ятовуюча пристрої

ВТ - обчислювальна техніка

ВС - обчислювальна мережа

ВЦФ - векторна цільова функція

ГЛС - граф локального сценарію діалогу

ДС - діалогових систем

ДП - дискретного програмування

КТС - комплексу технічних засобів

МА - множинами альтернатив

ЛЗ - локальних сценаріїв

ТР - таблиць рішень

ПМ - паретовское безліч

ПМА - повної множини альтернатив

РБД - розподілених баз даних

РБнД - розподілених банків даних

СУБД - система управління базами даних

СОД - система обробки даних

СОД РВ - системах обробки даних реального часу

ТР --таблиць рішень

ЦЛП - завдань цілочисельного лінійного програмування

ЦП - цілочисельного програмування

ЧЦП - часткового цілочисельного програмування

ЕОМ - електронно-обчислювальна машина

ВСТУП

Повсюдне розробка та впровадження нових інформаційних та інноваційні технологій в усі сфери і галузі життєдіяльності і зростання потреб у комплексної автоматизації організацій, підприємстві і фірм обумовлює різке зростання обсягів робіт по створенню і впровадженню систем обробки даних (СОД) до якості та ефективності яких пред'являються все більш високі вимоги. Тому необхідна високоефективна технологія проектування, що дозволяє створювати системи різної складності, рівня та призначення в стислі терміни за мінімальних затрат праці [1].

Традиційні технології проектування систем орієнтовані на послідовну розробку, тобто спочатку проводиться вивчення та системний аналіз організації, для якої створюється СОД, формуються вимоги до автоматизованої системи, здійснюється її декомпозиція, розробляється технічний проект системи в цілому і окремих її підсистем, потім виконується робоче проектування, тобто розробка програмного та інформаційного забезпечення, проводиться його налагодження, дослідна експлуатація модифікація створеної системи.

Дотримуючись такої технології, розробники СОД в останні роки починають стикатися з проблемами, що виникають із за динамізму існуючого суспільства. Поки створюється СОД, організація пристосовується до умов мінливого ділового світу, та розроблена для неї система надає застарілою. Тому створення сучасних СОД повинно базуватися на нових положеннях, при реалізації яких замість одного тривалого циклу розробки всієї системи буде існувати кілька коротких циклів розробки для системи в цілому і для її підсистем. При цьому повинні бути отримані не унікальні промислові, а споживчі вироби швидко і за помірною ціною.

Теоретичною базою такого підходу є парадигма модульності, типізації та клонування, а технічною основою - сучасні технології та системи автоматизованого проектування СОД.

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

Створення типових модульних СОД визначає якісно новий етап у проектуванні складних систем. Складність розробки типових модульних систем обробки даних обумовлюється необхідністю вибору раціонального рівня типізації, багатопараметричного аналізу об'єктів автоматизації, синтезу систем типових програмних модулів по заданим критеріям ефективності, адекватно відображає організаційні та економічні умови розробки СОД.

При використанні сучасних технологій та методів розробки модульних СОД і автоматизації цієї розробки процес проектування, по суті справи, замінюється процесам клонування, тобто створенням «генетично» подібної системи. При цьому створюються функціонально і структурно подібні СОД деякого класу, відповідні заданої предметної області та адаптовані на конкретний об'єкт управління.

Загальний час і витрати на розробку з використанням методів і засобів аналізу та синтезу модульних і типових модульних СОД скорочуються в 10 - 100 разів залежно від особливостей створюваних систем.

Проблеми аналізу та синтезу модульних і типових модульних систем дуже різноманітні, в повному обсязі не вирішені і в даний час інтенсивно розробляються багатьма дослідниками. Існуючі методи синтезу модульних систем можна розділити на два класи. До першого відноситься методи [3-12], що дозволяють по деяким евристичним правилами проектувати раціональні модульні системи та оцінювати ефективність отриманих систем за деякими якісними показниками, до другого - методи синтезу оптимальних модульних систем за заданими кількісними критеріями ефективності.

У рамках методів синтезу другого класу розробляється теоретичні основи, формалізовані моделі і прикладні методи аналізу і синтезу оптимальних і модульних СОД широкого класу і призначення, починаючи з систем пакетної обробки і закінчуючи системами реального часу і типовими інформаційними системами загального призначення [13-33].

Актуальність роботи. Повсюдна розробка та впровадження нових інформаційних та інноваційних технологій у різні сфери і галузі життєдіяльності і зростання потреб у комплексної автоматизації організацій, підприємстві і фірм обумовлює різке зростання обсягів робіт по створенню і впровадженню систем обробки даних (СОД), до якості та ефективності яких пред'являються все більш високі вимоги. Тому необхідна високоефективна технологія проектування, що дозволяє створювати системи різної складності, рівня та призначення в стислі строки при мінімальних затратах праці.

Традиційні технології проектування систем орієнтовані на послідовну розробку, тобто спочатку проводиться вивчення та системний аналіз організації, для якої створюється СОД; формуються вимоги до автоматизованої системи; здійснюється її декомпозиція, розробляється технічний проект системи в цілому і окремих її підсистем. Потім приступають до робочого проектування системи, тобто розробка програмного та інформаційного забезпечень, проводиться налагодження програмного забезпечення, а також досвідчена експлуатація і модифікація створеної системи.

Дотримуючись такої технології, розробники СОД в останні роки стикаються з проблемами, що виникають із за динамізму існуючого суспільства. Поки створюється СОД, організація пристосовується до умов мінливого ділового світу, та розроблена для нього система виявляється застарілою. Тому створення сучасних СОД повинно базуватися на нових положеннях, при реалізації яких замість одного тривалого циклу розробки всієї системи буде існувати кілька коротких циклів розробки для системи в цілому і для її підсистем. При цьому повинні бути отримані не унікальні промислові, а споживчі вироби швидко і за помірною ціною.

Одним з полхода проектування ефективних та якісних систем обробки даних є розробка формалізованих моделей і методів оптимального синтезу програмного та інформаційного забезпечення модульних систем обробки даних. Автоматизація технічного проектування оптимальних за заданим критеріям систем обробки даних значно підвищує ефективність і якість створюваних систем, скорочує терміни розробки та впровадження систем в експлуатацію на 30 - 50% в порівнянні з традиційним індивідуальним проектуванням.

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

Мета досліджень. Метою дисертаційної роботи є розробка і дослідження блочно-симетричних моделей, методів і алгоритмів проектування ефективних систем обробки даних, які забезпечують створення систем на етапі технічного і робочого проектування.

Методи дослідження. У процесі постановки та вирішення завдань дослідження використано методи системного аналізу, теорії графів, теорії матриць, дискретного програмування.

Наукова новизна результатів дослідження полягає:

  • розроблений комплекс взаємопов'язаних моделей і методів проектування систем обробки даних, сформульованих, на відміну від відомих, як завдання нового класу - блочно-симетричні завдання;

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

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

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

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

  • розроблено ефективний алгоритм ітеративних відображень рішення блочно-симетричних завдань.

Достовірність отриманих результатів. Наукові положення, висновки і рекомендації обгрунтовані строгими математичними методами, результатами обчислювальних експериментів і впроваджені на підприємствах і в організаціях.

Практична цінність. Розроблені в дисертації комплекс моделей і методів, алгоритмів і програмних засобів використані при проектуванні систем обробки даних на Усть-Каменогорському свинцево-цинковій комбінаті, у комітеті з інформатизації та зв'язку, а також впроваджені в навчальний процес.

Положення, що виносяться на захист.

На захист виносяться наступні положення:

  1. Новий підхід і загальна постановка блочно-симетричною дискретної задачі проектування систем обробки даних.

  2. Постановка завдання декомпозиції систем обробки даних на кластери функціональних завдань та інформаційних ресурсів.

  3. Постановка задачі синтезу модульних блок-схем обробки даних, а також постановки приватних задач проектування модульних блок-схем.

  4. Постановка багатокритеріальної блочно-симетричної задачі розробки модульної блок-схеми обробки даних.

  5. Нові ефективні алгоритми розв'язання дискретних блочно-симетричних завдань проектування систем обробки даних.

Впровадження результатів дисертаційного дослідження. Дослідження, проведені в роботі, проводилися відповідно до плану держбюджетних робіт кафедри «Обчислювальна техніка» КазНТУ ім. К. І. Сатпаєва, м. Алмати, - грантом програми фундаментальних досліджень МОН РК: за темою 0100РК00633 - «Розробка і дослідження блочно-симетричних моделей і методів проектування модульних систем обробки» і по темі 0101РК00696 - «Розробка технічного завдання інформаційної системи« Вступ державного реєстру інформаційно-телекомунікаційних систем »в частині визначення функціональних вимог, складу даних і їх класифікацій необхідні для ведення реєстру».

Результати роботи впроваджено в процесі проектірванія систем обробки даних у підрозділах Усть-Каменогорськ свинцево-цинкового комбінату і в Комітеті зв'язку та інформатизації, а так само використані при розробці лабораторних робіт і лекційних занять у КазНТУ імені К. І. Сатпаєва.

Акти впровадження наведено у додатку.

Апробація роботи. Основні положення та результати дисертаційної роботи були докладені та обговорені на міжнародних конференціях і конференціях Республіки Казахстан: наукова конференція магістрантів та аспірантів «Наука і творчість молодих: досвід, проблеми, перспективи» (Усть-Каменогорськ, 2001р), міжнародна конференція «Обчислювальні та інформаційні технології в науці, техніці та освіті »(Алмати, 2003, частина II, IV), міжнародна науково-практична конференція« Стан, проблеми та завдання інформатизації в Казахстані »(Алмати, 2004), республіканська науково-практична конференція« Молодь і інформаційні технології »(Актау, 2009), міжнародна науково-методична конференція« Актуальні проблеми природничо-наукових дисциплін »(Алмати, 2010), а також наукових семінарах кафедр« Технічна кібернетика »і« Обчислювальна техніка ».

Публікації. Наукові результати досліджень опубліковані в 12 друкованих роботах, в тому числі у виданнях, рекомендованих для публікації положень дисертації - 4 роботи. У наукових журналах опубліковано 4 роботи, в матеріалах наукових конференцій - 8 робіт.

Структура та обсяг дисертації. Дисертаційна робота складається з вступу, трьох розділів, висновків, списку використаних джерел 147 найменувань, 13 малюнків, 2 таблиць та двох додатків.

  1. МОДЕЛІ І МЕТОДИ ПРОЕКТУВАННЯ модульну систему ОБРОБКИ ДАНИХ

У даному розділі проведено аналіз формалізованих моделей і методів проектування модульних систем обробки даних (МСОД). Розглянуто завдання передпроектного аналізу предметної області, формування вихідних даних для проектування систем обробки даних. Як правило, поставлені задачі зведено до завдань дискретного програмування, які складні і не часто дозволяють вирішувати задачі великої розмірності. У розділі наведено короткий огляд методів рішення задач дискретного програмування (ДП) [146].

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

1.1 Огляд моделей аналізу і синтезу модульних систем обробки даних

Системи обробки даних (СОД) різного класу і призначення представляє собою сукупність прикладного програмного забезпечення, бази даних, загальносистемного програмного забезпечення, що реалізуються на основі обчислювальної системи, з метою вирішення деякого прикладного програми з обробки даних чи управлінню. Основними завданнями проектування системи обробки даних є синтез прикладного програмного забезпечення та бази даних, при цьому останні, до теперішнього часу, розробляються часто використовуючи досвід і знання конкретних розробників.

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

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

У зв'язку з цим виникає необхідність розробки принципово нових підходів, постановок і методів рішення, що забезпечують ефективне вирішення завдань проектування інформаційного і прикладного програмного забезпечення.

Разом з тим при розробці складних інформаційних систем ці інструментарії не завжди забезпечують якість і скорочення тривалості розробки проектів.

Тому виникає необхідність розробки формалізованих моделей і методів проектування прикладного програмного забезпечення та бази даних систем обробки даних. Одним з напрямків такого підходу є розробка моделей і методів аналізу і синтезу модульних і типових модульних систем обробки даних.

У рамках цього напряму розглянемо відомі підходи аналізу та проектування систем обробки даних.

Для розробки формалізованих методів необхідно провести аналіз предметної області, для якої розробляються системи обробки даних.

У результаті аналізу систем обробки даних виділяються безліч функціональних завдань і процедур обробки даних, безліч інформаційних елементів, необхідних і достатніх для вирішення безлічі завдань системи, а так само взаємозв'язку між інформаційними елементами і процедурами обробки даних у процесі вирішення завдань з обробки даних. У ряді випадків у процесі аналізу оцінюються і виділяються такі кількісні характеристики, як розміри інформаційних елементів і процедур, частоти функціонування програмних модулів і функціональних завдань, середні часи звернення до масивів бази даних та інші [14, 16, 18, ​​21, 24].

Уточнимо деякі поняття.

Під функціональним завданням розуміється послідовність процедур обробки даних і використовуваних ними вхідної інформації (інформації елементів) для вирішення програми, необхідного для управління або прийняття рішення.

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

Інформаційним елементом (атрибут) називається найменування мінімальної неподільної інформації, значення якої використовується як вихідних даних процедурами обробки або є результатом їх обробки.

Розглянемо методи аналізу систем обробки даних реального часу (СОД РВ), які можуть бути використані при аналізі систем інших класів.

Процедури обслуговування заявок у системах обробки даних реального часу (СОД РВ) неоднозначно визначаються необхідним безліччю вихідних інформаційних елементів і детермінованої технологією їх отримання, а залежать від часу надходження заявки на обробку, складу і взаємозв'язків необхідних для її обслуговування завдань і від поточного стану інформаційної бази, визначального альтернативні можливості обробки даних. Для дослідження цих можливостей необхідний спільний аналіз безліч вимог, що пред'являються які надходять на обробку заявками, використовуваних для їх обслуговування задач обробки даних, алгоритмів їх вирішення і використовуваних масивів. Для аналізу структур інформаційних потоків і технології обробки даних в СОД РВ використовується сукупність взаємопов'язаних матричних і графових моделей, що забезпечують формальний аналіз технологій обробки даних як окремого завдання СОД РВ, так і безлічі завдань в цілому [25-30, 33,38]

Узагальненої формою представлення взаємозв'язків інформаційних систем, процедур та інформаційних елементів при вирішенні завдань є технологічні матриці складності і досяжності, які потім перетворюються в інтегрований граф обробки даних. Побудова єдиного інтегрованого графа здійснюється шляхом виконання операції «накладання» технологічних графів і полягає в поєднанні ідентичних рівнів кожного графа і ідентичних вершин на кожному рівні. У результаті формується інтегрований граф, якому відповідає матриця, отримана шляхом логічного додавання технологічних матриць.

Розглянемо зазначені процедури аналізу більш докладно, тому що вони є загальними для модульних систем обробки даних будь-якого класу.

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

Нехай задано безліч завдань СОД РВ . Технології вирішення кожного завдання відповідає спрямований граф , Де безліч вершин графа, що відображають інформаційні елементи завдання ; - Безліч відносин між інформаційними елементами . Кожному графу відповідає квадратна бінарна матриця суміжності розміру . Елемент матриці дорівнює 1, якщо елементи і графа пов'язані відносинами , І дорівнює 0 у противному випадку.

Структурований граф взаємозв'язків інформаційних елементів задачі, перетворений до виду, який не містить циклів обробки, називається скелетним графом завдання . Він складається з ряду рівнів або непересічних підмножин вершин, кожна з яких є вихідним результатом обробки попереднього рівня або підмножини інформаційних елементів. З використанням графа визначається безліч процедур обробки даних, необхідних для вирішення завдань . Для кожної впорядкованої пари елементів визначимо підмножини

.

Потім визначимо на безлічі декартово твір . Пара елементів пов'язано з процедурою , Якщо вона належить відношенню . Сукупність процедур завдання утворює безліч . Повне безліч процедур аналізованого безлічі завдань визначається шляхом об'єднання .

Для визначення в задачі вхідних, проміжних та вихідних даних, послідовності їх отримання і контурів зворотного зв'язку, а також аналізу взаємозв'язків в системі введено поняття матриці досяжності.

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

Матриця визначається на основі матриці . При цьому вони пов'язані булевим рівнянням

Аналіз структур обробки даних для кожної завдання СОД і визначення необхідної послідовності отримання інформаційних елементів спрощується, якщо елементи побудованої матриці досяжності порядок рівнями (етапом) їх обробки. Отримання матриці методом згортки циклів дозволяє зменшити її розмірність, полегшити аналіз і синтез структури рішення як окремих завдань системи, так і функціонування всієї СОД РВ.

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

Взаємозв'язок між процедурами обробки даних при обслуговуванні кожної заявки СОД РВ, наборами вхідних і проміжних даних зручно представляти за допомогою таблиці інціденцій обробки множин запитів , Яка представляє собою матрицю виду

У матриці кожен рядок відображає процедуру обробки, а кожен стовпець - використання всіма процедурами при вирішенні завдання розглянутого інформаційного елемента. У рядку міститься інформація про безліч вхідних і вихідних даних, пов'язаних з аналізованої процедурою. Аналіз стовпців дозволяє виявити вхідні і вихідні інформаційні елементи аналізованої завдання . Елементи є вхідними при вирішенні завдання, якщо стовпець матриці містить єдину, відмінну від нуля запис . Якщо -Й стовпець містить запис , То відповідний йому елемент є вихідним. Технологічної матрицею суміжності при вирішенні завдання назвемо квадратну бінарну матрицю, проіндексовану по обох осях множинами . Матриця має чотири підматриці: з розмірами .

Нульові елементи підматриці відповідає елементам, рівним -1 в матриці , А не нульові елементи підматриці відповідає елементам, рівним +1 в транспонованої матриці . Таким чином, елемент матриці дорівнює 1, якщо елемент є вхідним для процедури , І елемент дорівнює 1, якщо елемент є вхідним при вирішенні завдання. В іншому випадку елементи в позиціях і рівні 0. Одиничний елемент в позиції , підматриці відповідає наявності одиничних елементів у позиції підматриці і в позиції підматриці , , Що рівносильно існуванню інформаційного елемента , Який є вхідним для процедури , І вихідним для процедури при вирішенні завдання. Для зручність формального опису буде вважати, що головна діагональ підматриці заповнена одиничними записами.

Використовуючи матрицю , Можна визначити матрицю , Яка містить підматриці , Проіндексовані відповідно: .

Підматриць задовольняє співвідношенню , Де -Ціле позитивне число, не більше числа елементів при вирішенні завдання, тобто . Матриця містить поодинокі елементи в позиції , Якщо процедура входить в послідовність процедур, необхідну для отримання елемента при вирішенні завдання. В іншому випадку запис у позицію підматриці дорівнює нулю. Підматриць визначається співвідношенням і містить одиничний елемент в позиції , Якщо елемент є вхідним для послідовності процедур, до складу в яких входить процедура . В іншому випадку елемент дорівнює 0. Підматриць є матрицею досяжності процедур обробки даних при вирішенні завдання і задовольняє співвідношенню

.

Одинична запис у позиції підматриці відповідає наявності спрямованого шляху в графі технології вирішення завдання від процедури до процедури .

Побудова єдиного інтегрованого графа здійснюється шляхом виконання операції «накладення» графів і полягає в поєднанні ідентичних рівнів кожного графа і ідентичних вершин на кожному рівні. У результаті формується інтегрований граф , Якому відповідає матриця суміжності , , , Отримана шляхом логічного додавання матриць :

.

Аналіз структур отриманого інтегрованого графа дозволяє на заключному етапі аналізу визначити наступні загальносистемні вимоги до обслуговування заявок в СОД РВ: безліч необхідних задач обробки даних для обслуговування одного типу заявок і базові завдання для кожного типу, взаємозв'язку між заявками по важливість справ і між завданнями по використовуваних процедур і даними, раціональну дисципліну обслуговування заявок і оцінку необхідної продуктивності обчислювальної системи для заданої дисципліни обслуговування.

В якості моделей опису та аналізу задач обробки даних при створенні типових модульних СОД також використовується аналогічна сукупність графових та матричних моделей. Методика аналізу та структуризація вихідної для синтезу системи типових модулів СОД інформації базується на послідовному перетворенні матричних і графових моделей алгоритмів розв'язання задач обробки даних, що містять всю необхідну інформацію про взаємозв'язках і відношеннях між різними елементами окремих завдань. При формуванні повного структурованого графа технології вирішення задачі враховується наявність в алгоритмах розв'язання задач обробки даних циклічних ділянок та альтернативних варіантів обробки, процедур оновлення інформаційних елементів і процедур прийняття рішень. Повний структурований граф і відповідні йому матриці суміжності і досяжності дозволяють описувати алгоритми розв'язання задач обробки даних в цілому та окремі їх частини із заданим ступенем деталізації [31,32,34,39,40]

Зростання числа вирішуваних і діалозі завдань у складі модульних СОД їх складності, підвищення вимог до своєчасності, достовірності та повноти інформації, що представляється обумовлює необхідність подальшого удосконалення методології проектування СОД яка повинна враховувати не тільки особливості "людського фактора", а й вимога щодо забезпечення максимальної ефективності використання технічного , програмного та інформаційного забезпечення діалогових систем (ДС) та їх типізації.

На стадії передпроектного аналізу ДС необхідно виконати комплекс робіт, основною з яких також є аналіз розв'язуваних користувачами завдань, технології їх розв'язання, визначення вимог користувачів до ефективності і якості вирішення завдань [40]. На цій стадії визначається необхідний набір процедур реалізації комплексу діалогових завдань і необхідної для їх рішення інформації.

Для представлення результатів вивчення та аналізу задач користувачів і технології їх розв'язання використовується модифікації описаних вище формалізованих методів подання результатів цього вивчення.

Визначення процедур обробки даних, аналіз та структуризацію кожної діалогової завдання доцільно здійснювати з використанням додаткової сукупності матричних і графових моделей, що забезпечують підготовку локальних сценаріїв (ЛЗ) діалогу та інших вихідних даних, необхідних для технічного проектування оптимальних ДС [41].

Локальні сценарії діалогу будуються на основі описаних користувачами (засобами мови опису задач - ЯОЗ) схем їх вирішення, які доповнюють формами представлення результатів проектування систем. Схема рішення кожної задачі представляється у вигляді сукупності взаємопов'язаних таблиць рішень (ТР), що описують послідовність і зміст кроків діалогу користувача з ДС при вирішенні завдання, що використовується при цьому інформацію, а також вимоги користувача до характеристик процесу обробки запитів, які видаються на кожному кроці діалогу. Сукупність таблиць рішень однозначним чином відображається в граф локального сценарію діалогу (ГЛЗ). Кожна вершина ГЛС відповідає одній ТР, а спрямовані дуги - взаємозв'язкам між таблицями. Кожному ГЛС ставляться у відповідність матриця суміжності і матриця досяжності, що відображають структуру і взаємозв'язок вузлів графа.

За допомогою матриць для полегшення подальшого аналізу локальних сценаріїв діалогу проводитися впорядкування ГЛС, в ході якого вузли графа розподіляються за рівнями їх проходження і процесі вирішення завдання. При наявності контурів на рівнях ГЛС осущестіляется їх згортка, що призводить до скорочення розмірності та спрощення матриць суміжності і досяжності графа. На основі впорядкованого таким чином ГЛС за допомогою мови ГЕРТІ мереж можуть бути определно такі характеристики ГЛС діалогу, як умовна ймовірність завершення виконання завдання в заданому сайті графа, яка має властивість адитивності на дугах графа.

З урахуванням результатів аналізу вимог користувачів і локальних сценаріїв діалогу форміруетсся сценарій ДС у цілому шляхом операції «накладення» упорядкованих вузлів на кожному рівні. Для формалізації, упорядкування та аналізу сценарію діалогу всієї системи також використовується сукупність взаємопов'язаних матричних і графових моделей і методи оцінки Герт-мереж.

На цій стадії провадиться перевірка коректності опису схем вирішення завдань і відповідає характеристик функціонування ДС побудованому сценарієм системи та вимогам користувачів до ефективності і якості завдань. Виявлення неточностей та суперечностей в описі схем вирішення завдань і в заданих вимогах до ефективності і якості їх рішення на стадії передпроектного аналізат ДС до реалізації етапів проектування, налагодження і впровадження системи дозволяє звести до мініму витрати на виправлення помилок, тестування і, отже, скоротить загальні витрати на реалізацію ДС.

Якісні зміни в структурі сучасних модульних СОД пов'язані з широким впровадженням комп'ютерних мереж, систем управління локальними і розподіленими базами даних, а також новітніх систем передачі даних.

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

Аналіз в процесі проектування розподілених баз даних (РБД) в модульних системах включає чотири взаємопов'язаних етапи передпроектний аналіз предметних областей користувачів, аналіз предметних областей користувачів і побудова зовнішніх моделей, побудова узагальненої зовнішньої моделі і побудова канонічної структури РБД. Результатом аналізу предметних областей користувачів є побудова канонічної структури РБД, яка відображає найбільш суттєві характеристики і стійкі властивості даних і відносин між ними і є інваріантної стосовно до апаратних і програмних засобів її реалізації [35, 36, 37].

У результаті аналізу визначається також целосообразность застосування методів типізації, забезпечується формування узагальненої зовнішньої моделі (ОВМ), проектування канонічної структури РБД і виділені на ній безлічі типових і специфічних сегментів даних. Виділені сегменти даних та їх характеристики використовуються при синтезі логічної структури РБД, логічних і фізичних структур локальних БД.

Доцільність застосування методів типізації при проектуванні РБД визначається рівнем інформаційної та процедурної спільності зовнішніх моделей предметної області користувачів.

Зовнішня модель предметної області користувача включає опис характеристик інформаційних елементів і відносин між інформаційними елементами і процедурами.

Для уніфікації групових інформаційних елементів, що входять в структуру зовнішньої моделі предметної області окремого користувача, виділене безліч групових інформаційних елементів перевіряється на семантичну зв'язність і можливість видалення дубльованих інформаційних елементів в групах.

Результатом виконання процедур нормалізації зовнішньої моделі предметної області користувача є канонічна структура, тобто структура, яка представляє собою мінімальну концептуальну схему і відображає найбільш суттєві властивості і характерні особливості предметних областей користувачів.

У процесі аналізу модульних СОД широко використовується апарат мереж Петрі [42]. Завдання аналізу систем обробки даних, що вирішуються за допомогою тимчасових мереж Петрі з різнокольоровими маркерами, включають завдання визначення можливості і коректності реалізації будь-якої функціональної задачі користувача або заданої множини таких завдань, можливості багаторазового використання процедур обробки даних виявлення тупикових ситуацій при спільній обробці інформаційних елементів. З використанням мереж Петрі проводітсятакже аналіз механізмів захисту в системах обробки даних [42, 43].

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

Розглянемо методи синтезу модульних систем обробки даних різного призначення.

Інформаційно-довідкові системи. Синтез модульних СОД на етапі технічного проектування включає оптимальної вибір складу модулів програмного забезпечення та інформаційних масивів, змісту міжмодульних інтерфейсу, структури системи обробки даних в цілому, формализуемой у вигляді фунціональної блок-схеми, з урахуванням заданих техніко-економічних характеристик фунционирования розроблюваної системи.

Для оптимізації процесу проектування системи мспользуетя критерій мінімуму складності міжмодульних інтерфейсу. Оптимізація експлуатаційних характеристик може бути здійснена в залежності від конкретних обставин по одному з наступних критеріїв: мінумум часу обміну між оперативною і зовнішньою пам'яттю, зниження технологічної складності алгоритмів обробки даних, що є узагальненням показника «транспортного фактора» при реалізації алгоритмів розв'язання функціональних завдань, запропонованого Лангефорсом . Крім того, для інформаційних систем істотним є максимум інфармаціонной продуктивності і забезпечення достовірності обробки даних [14-21, 30, 31, 44-60].

Поставлені завдання синтезу модульних блок-схем обробки даних сформульовані як задачі нелінійного цілочисельного програмування. Для їх вирішення запропоновані алгоритми, засновані на схемі «гілок і кордонів» і використовують основні особливості модульног проектування.

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

Автоматизовані системи, в яких забезпечується дана вимога, отримали назву автоматірованних систем обробки даних реального часу (СОД РВ).

Розглянемо методи синтезу оптимальних модульних систем обробки даних реального часу [25-30, 38, 54-66].

Основні особливості постановки задачі синтезу програмного та інформаційного забезпечення СОД РВ на етапі їх технічного проектування полягають у необхідності враховувати характеристики і параметри вхідних потоків на видачу повідомлень, характеристики і параметри обробки і обелужіванія заявок різних типів, загальну завантаження різними заявками керуючої ЕОМ і систем передачі даних зовнішніми абонентами, структуру і об'єм пам'яті для заявок різних типів дисципліни розподілу обчислювальних ресурсів і використання пам'яті при прийомі та видачі повідомлень.

Врахування особливостей проектування СОД РВ досягається введенням у розроблені моделі параметрів, що визначають закони надходження заявок на обробку, дисципліни обслуговування та пріоритетність заявок, взаємозв'язку між заявками по решеаемим завданням.

Можна виділити наступні основні завдання модулного побудови програмного та інформаційного забезпечення СОД РВ: синтез оптимальних модульних СОД РВ з беспріорітетним обслуговуванням заявок у режимі поділу часу на однопроцесорних ЕОМ, синтез систем РВ з пріоритетним обслуговуванням заявок в ОС реального часу на однопроцесорних ЕОМ, синтез оптимальних модульних СОД РМ на багатопроцесорних ЕОМ.

Специфічною при вирішенні задач синтезу оптимальних СОД РВ з беспріорітетним обслуговуванням заявок є однорідність вхідного потоку заявок і слабка інформаційна і тимчасова взаємозв'язок між заявками і їх обслуговуванням.

При синтезі СОД РВ з пріоритетним обслуговуванням заявок необхідно враховувати різноманітність вхідних заявок різних типів, що характеризуються різною інтенсивністю надходження, пріоритетністю обслуговування [31, 67]. Вимоги користувачів на час обслуговування заявок значно жорсткіше в порівнянні з завданнями беспріорететного обслуговування, що вимагає розміщення в оперативній пам'яті низки програмних процедур і даних, необхідних для обслуговування окремих заявок. Взаємозв'язки між заявками за складом розв'язуваних завдань в таких системах, як правило, досить суттєві. Підвищення ефективності вирішення даних завдань здійснюється в основному за рахунок скорочення числа і часу обміну між рівнями пам'яті обслуговуванні заявок [55, 67, 68].

Рішення задач синтезу оптимальних СОД РВ з мультипроцесорних обслуговуванням передбачає скорочення не тільки часу обміну між рівнями пам'яті, а й середнього процесорного часу розв'язання задач за рахунок паралельної реалізації процедур, модулів або заявок в цілому [58, 59, 61, 65, 66].

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

Основною вимогою до результатів синтезу системи є максимально високий рівень обслуговування вимог користувачів за рахунок оптимального використання обчислювальних ресурсів.

При синтезі модульних СОД РВ досліджуються різні характиристики продуктивності СОД РВ, коефіцієнт готовності обслуговування заявок користувачів, витрати користувачів при експлутації системи та ін У залежності від змістовної постановки задачі для проектованої системи в якості критерію оптимальності сінтерізіруемой системи використовується одна з пречісленних СОД РВ беспріорітетним обслуговуванням заявок в режимі розділення часу, і з пріоритетним обслуговуванням заявок використовуються критерії максимуму продуктивності СОД РВ і максимум коефіцієнтів готовності системи, а в задачах синтезу оптимальних модульних СОД РВ використовують мультипроцесорні обслуговування, визначальною характеристикою є витрати користувачів в процесі експлуатації системи.

В якості основних обмежень при вирішенні завдань синтезу СОД РВ використовуються обмеження на час обслуговування і на стійкість режиму функціонування системи в цілому. До додаткових обмежень відносяться обмеження на склад процедур і програмних модулів, обсяг оперативної пам'яті, склад і обсяг інформаційних масивів, ступінь дублювання процедур та інформаційних елементів в СОД РВ та ін

Розглянемо задачу синтезу оптимальної структури програмного та інформаційного забезпечення СОД РВ за критерієм максимальної продуктивності системи в режимі розділення часу в процесі обслуговування вхідних потоків на вирішення завдань. Завдання формулюється наступним чином:

,

при обмеженнях на: час обслуговування -Ї заявки для заданого алгоритму організації черги

;

стійкість режиму функціонування системи

;

загальне число дубльованих процедур

;

кількість процедур у складі модуля

;

кількість інформаційних елементів у складі масиву бази даних

,

дублювання інформаційних елементів в масивах

;

однорідність включення процедур в програмні модулі

;

загальне число інформаційних елементів, які використовуються модулями завдань

.

Змінні і позначення в даній постановці визначені наступним чином:

де - Булева матриця взаємозв'язків завдань і процедур обробки даних, і - Матриці взаємозв'язків інформаційних елементів з процедурами обробки даних відповідно при зчитуванні й записи:

Змінні і визначають взаємозв'язку системи розробляються модулів завдання з окремими інформаційними елементами і масивами інформаційної бази відповідно при зчитуванні й запису даних у процесі обміну із зовнішньою пам'яттю ЕОМ, а змінна - Взаємозв'язки завдань з програмними модулями.

Середній час вирішення -Й завдання СОД РВ визначається наступним чином:

,

Де - Середнє процесорний час виконання завдання; - Середній час пошуку і перезапису -Го модуля з зовнішньої пам'яті в оперативну пам'ять; - Середній час зчитування -Го масиву із зовнішньої пам'яті; - Середній час запису результатів обробки даних у -Й масив. Середній час вирішення всіх задач обробки даних в СОД РВ визначається відповідно до співвідношення

.

Середній час обслуговування заявки для алгоритму кругового циклічного обслуговування з послепрібитіем має вигляд

,

де - Середній час знаходження заявок в системі; - Квант часу обслуговування заявки; - Випадкове позитивне число, яке має геометричне розподіл; - Інтенсивність надходження заявок -Го типу; - Інтенсивність потоку заявок.

Поставлено та вирішені наступні завдання розробки оптимальних модульних СОД РВ: визначення системи модулів програмного та інформаційного забезпечення, формализуемой у вигляді блок-схеми обробки даних функціональних завдань, що використовують дисципліни диспетчеризації заявок з відносними, абсолютними і змішаними пріоритетами; визначення оптимальної та допустимої послідовності пріоритетів рівнів і вибір методів організації обчислювального процесу, визначення структур бази даних та її характеристик. В якості основних критеріїв оптимальності розглядаються мінімум міжмодульних інтерфейсу, мінімум число звернень системи програмних модулів до зовнішньої пам'яті, мінімум сумарного часу очікування заявок на вирішення завдань, мінімум сумарного штрафу за очікування заявок на рішення задачі системи.

Завдання синтезу вирішені при ряді технологічних та експлуатаційних обмежень, основними з яких є обмеження на стійкість режиму функціонування системи, на середній час очікування заявок на вирішення завдань, складність інтерфейсу. Поставлені завдання синтезу модульних СОД РВ зведені до моделей цілочисельного нелінійного програмування, для вирішення яких запропоновані алгоритми, засновані на схемі «гілок і меж».

Діалогові системи. Сучасний рівень розвитку обчислювальної техніки і особливо персональних ЕОМ зумовив різке розширення числа і можливостей діалогових систем в модульних СОД, а також кола їх користувачів.

Розробка ефективних діалогових систем являє собою комплексну проблему, що включає в собі аналіз і типізацію інформаційних вимог користувачів, синтез типової моделі діалогу для заданої множини користувачів, інформаційні запити яких належать одній предметної області, синтез інформаційного та модульного програмного забезпечення діалогових систем (ДС) [130] .

При синтезі оптимальних модульних ДС використовується наступні системні та технічні характеристики: витрати на розробку і впровадження системи в цілому і її підсистеми, час розробки і впровадження, експлуатаційні витрати, втрати в системі від несвоєчасного подання інформації користувачу, конфігурація, якість та завантаження технічних засобів, використовуваних при вирішенні задач користувачів, достовірність оброблюваної інформації, інформаційна продуктивність системи, надійність програмного і технічного забезпечення ДС, релевантність виконуваних системою запитів, час реакції ДС при виконанні запитів користувачів за заданими сценаріями, час і зручність формування користувачем запитів, ступінь наближення до роботи в реальному масштабі часу (так режимі формування запиту так і при реалізації інтерфейсу ДС-БД) [131], обсяг оперативної пам'яті для розміщення програмних модулів і інформаційних масивів системи, швидкодія, час звернення до периферійного обладнання, вартість комплексу технічних засобів (КТС) і його комплектація з урахуванням ергономічних вимог, ступінь розподіленості КТС у разі мережевої його архітектури [56-57].

У залежності від постановки задач синтезу ДС, а також від ступеня важливості тієї чи іншої характеристики для проектованої системи в якості критерію оптимальності синтезується ДС приймають одну з перерахованих вище характеристик якості, а інші є обмеженнями.

Найбільш загальною задачею синтезу ДС є визначення за заданим критеріям ефективності сценарії (С), програмного забезпечення (Р), інформаційного забезпечення (I) і комплексу технічних засобів (Г) діалогової системи на основі аналізу характеристик користувачів (П), розв'язуваних ними завдань (Ф ) та вимог користувачів до основних характеристик розв'язуваних завдань.

До приватних завдань синтезу ДС відносяться визначення оптимального сценарію З діалогової системи на основі локальних сценаріїв, вибір КТС з безлічі можливих, синтез Р і I на основі інформації про сценарій С і характеристиках обраного КТС.

Критерії ефективності при синтезі ДС доцільно розбити на кілька рівнів: ДС в цілому, процес діалогу, що забезпечують підсистеми ДС (програмне, інформаційне та технічне забезпечення ДС),

Найбільш характерними критеріями ефективності при синтезу ДС є: мінімум загального часу розробки та впровадження, максимум інформаційної продуктивності ДС, максимальний рівень достовірності при обробці інформації, релевантність заданої множини запитів, максимальний рівень, захисту ДС від несанкціонованого доступу, мінімум завантаження ЕОМ.

Найбільш характерними критеріями ефективності процесу діалогу в ДС є: максимум потужності діалогу, інформаційної продуктивності, мінімум середнього часу, проходження запиту, мінімум числа звернення до зовнішньої пам'яті при проходженні запиту, максимум одночасно працюючих користувачів ДС, мінімум часу, непродуктивно витрачається користувачем на діалог.

При розробці програмного та інформаційного забезпечення ДС витрати і час на їх розробку та впровадження в значній мірі визначаються складністю взаємозв'язків між окремими програмними модулями ДС, а витрати на експлуатацію ДС - часом реалізації окремих запитів, складністю сценаріїв діалогу та технічною складністю алгоритмів їх реалізації, необхідним рівнем достовірності обробки даних. Тому основними показниками якості розроблюваного програмного та інформаційного забезпечення ДС є складність міжмодульних інформаційних зв'язків (інтерфейсу), складність сценаріїв діалогу і технологічна складність алгоритмів їх реалізації. Ці показники і домінують при розробці, налагодженні, впровадженні та модифікації ДС.

До іншого безлічі показників ефективності програмного та інформаційного забезпечення ДС відносяться показники, що визначають ефективність рішення задач обробки запитів у ДС. Показники цієї групи визначаються продуктивністю використовуваних обчислювальних засобів, тимчасово проходження запитів в ДС, яке, у свою чергу, залежить від типу, структури та обсягу використовуваної пам'яті, структури програмних модулів і інформаційних масивів ДС, множини і послідовності реалізуються запитів в ДС.

При виборі технічного забезпечення ДС доцільно використовувати в основному економічні показники.

У рамках синтезу модульних діалогових систем поставлена ​​і вирішена задача оптимального виділення підсистем ДС відповідно до визначеного локальними сценаріями діалогів, розбиття деякого мультіграфе з поміченими або розфарбованими дугами на підграфи, що забезпечує мінімум сумарної ваги дуг різного кольору, що пов'язують підграфи при ряді структурних обмежень.

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

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

Вирішено також задачі синтезу оптимальної модульної структури програмного забезпечення ДС за умови, що запити користувачів обслуговуються у відповідності з різними (беспріорітетнимі і пріоритетними) дисциплінами обслуговування.

Функціонування ДС при цьому моделюється у вигляді СМО з найпростішими входять потоками заявок і довільними потокам обслуговування. Визначено аналітично залежності показників ефективності даної системи і залежності від тривалості обслуговування заявок кожного типу і інтенсивності їх надходження, а також необхідні умови існування сталого режиму в ДС.

Для дисциплін обслуговування з абсолютними і відносними пріоритетами проведено порівняльних аналітичний аналіз ефективності їх використання при організації функціонування ДС, визначено умови переходу від дисципліни обслуговування з відносними пріоритетами до дисципліни обслуговування з абсолютними пріоритетами, що забезпечують виграш у часі очікування.

Завдання синтезу струтуре праграммного забезпечення ДС зведені до задач нелінійного цілочисельного програмування, для вирішення індикатором використовуються метод «гілок і кордонів» та інші методи [72].

Типізація розробки. Під тепізаціей при розробці СОД розуміється процес аналізу вимог і харектерістік заданої множини об'єктів автоматизації і вибору методів відомості різноманіття індивідуальних проектних рішень до огроніченному безлічі рішень, досить ефективно виконують вимоги об'єктів автоматизацій [31, 73, 74].

Можливості вибору типових рішень засновані на існуванні достатньою мірою спільності вимог аналізованих об'єктів автоматизацій. Чим вище ступінь цієї спільності, тим простіше й ефективніше процес вибору, створення і реалізації типових проектних рішень. Використання принципів модульності і типізації при розробці СОД дозволяє звести їх проектування до синтезу систем функціонально незалежних типових модулів, що спільно виконують заданий безліч функцій на безлічі вибраних об'єктів автоматизацій з необхідною ефективністю.

Разом з тим проблема типізації розробки модульних СОД виключно складна, тому що її рішення включає вибір рівня і стратегії типізації, багатопараметричний аналіз об'єктів автоматизацій, синтез систем типових модулів та інформаційного забезпечення за заданими критеріями ефективності.

Можна виділити три основні стратегії типового модульного проектування СОД: синтез типових модульних СОД для вирішення заданого безліч завдань одного класу; комплектація та налаштування програм для вирішення необхідної задачі з огроніченного набору типових програмних модулів, синтез робочих програм на основі наявних прототипів (аналогів) СОД з урахуванням специфіки та змістовного опису канкретние завдання.

Перша стротегія модульного проектування є найбільш універсальною і передбачає синтез типових програмних та інформаційних засобів для множестов досить близьких завдань одного класу. Реалізація даної стратегії пов'язана в першу чергу з процесом аналізу вимог і характеристик заданого безліч завдань чи об'єктів автоматизацій, виявленням загальних специфічних частин аналізованих задач обробки даних.

Друга і третя стратегія вимагають наявності програмних модулів або готового прототипу, Каторі можуть бути прийняті в якості базового варіанту проектування.

Метою оптимального проектування типової модульної системи обробки даних є синтез системи типових модулів і техніко-економічні характеристики, що розробляється. Безліч інформаційних масивів, що забезпечують екстремум критерію ефективності з урахуванням обмежень на допустимих варіантів побудови типової модульної СОД визначається вибраною системою обмежень, а її параметри - оптимізацією критерію ефективності, що є функцією різних техніко-економічних показників, до яких відносяться вартісні і часові витрати на розробку, налагодження і експлуатацію системи, час вирішення задач обробки даних, кількість типових і оригінальних модулів в системі, надмірність системи модулів по відношенню до завдань обробки даних, коефіцієнт готовності до обробки заявок, достовірність обробки даних, напрацювання на відмову.

При синтезі типових модульних СОД можуть бути використані загальносистемні, мінімаксні і складні критерії проектування теорії активних систем. Перші екстремізіруют сумарні показники якості синтезу для безлічі користувачів або задач обробки даних, другі-показники гарантованої якості синтезу для користувачів обробки данних.Крітеріі третього типу використовуються для вибору типових проектних рішень у випадках розбіжності цільових функцій або точок екстремуму центру і елементів системи. До числа загальносистемних критеріїв відносяться: мінімум наведеної вартості розробки налагодження та експлуатації проектованої типової модульної СОД, мінімум загального часу розробки та налагодження типової модульної системи, мінімум середнього значення міжмодульних інтерфейсу, максимум середнього по безлічі показників інформаційної продуктивності проектованої системи, максимум середнього коефіцієнта завантаження технічних засобів . Конкретний вибір ступеня централізації механізму проектування, критерію ефективності та узгодженої системи обмежень, що визначають постановку задачі синтезу типових модульних СОД, базується на використанні результатів аналізу технологій вирішення безлічі завдань обробки даних.

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

Синтез структур баз даних. Створення модульних СОД нового покоління тісно пов'язане з широким впровадженням комп'ютерних мереж, локальних і розподілених баз даних (РБД) і систем передачі інформації [75-81].

Синтез логічної структури РБД розглядається як процес пошуку оптимального варіанту відображення канонічної структури РБД в логічну, яка забезпечує оптимальну значення заданого критерію ефективності функціонування РБД і задовольняє основним вимогам і обмеженням, що накладається на логічну структуру на етапі розробки технічного завдання. Для відображення канонічної структури в логічну використовуються метод об'єднання груп канонічної структури РБД в типи логічних записів з одночасним розподілом їх по вузлах обчислювальної мережі.

Вихідною інформацією для етапу синтезу оптимальних компонент логічного рівня подання інформації в РБД є характеристики канонічної структури, отримані на етапі аналізу і нормалізації зовнішніх моделей предметних областей користувачів.

Основними критеріями синтезу оптимальних логічних структур РБД є мінімум загального часу виконання безлічі запитів і коригувань користувачів, мінімум сумарної вартості зберігання інформації та реалізації процедур обробки даних, мінімум максимального часу (вартості) реалізації безліч запитів і завдань на коригування, ініційованих різними користувачами.

В якості основних обмежень використовується обмеження на тимчасових і вартісні характеристики процесу реалізації запитів і коригувань, на обсяг доступної зовнішньої пам'яті і вузлах обчислювальної мережі (ВС), пропускну здатність каналів зв'язку, надійність доступу до заданого вузла ВС і ін

Рішення задач синтезу оптимальних логічних структур РБД дозволяє визначити склад типів логічних записів, структури і типи відносин між ними, розміщення типів записів по вузлах ЗС, характеристики типів записів, використання типів записів при реалізації процедур обробки.

У процес проектування РБД виділяються наступні взаємопов'язані етапи: синтез оптимальних логічної структури РБД, проектування структури мережевого каталогу й проектування логічних структур локальних баз даних (БД). Синтезовані оптимальна за заданим критерієм ефективності логічна структура РБД, мережевий каталог і логічні структури локальних БД повинні забезпечувати збереження семантичних властивостей інформаційних елементів і зв'язків між ними, зафіксованих у канонічній структурі РБД з урахуванням обмежень, накладених параметрами локальних СУБД і апаратних засобів передачі даних, топологією НД і вимогами різних режимів функціонування розподілених банків даних (РБнД).

Синтез оптимальної логічної структури РБД розглядається як процес пошуку оптимального варіанту відображення канонічної структури РБД в логічну, що забезпечує оптимальне значення заданого критерію ефективності функціонування РБнД і задовольняє основним системним, мережевим і структурним обмеженням. При відображенні канонічної структури в логічну групу канонічної структури РБД об'єднуються у типи логічних записів з одночасним розподілом їх по вузлах НД Складність вирішення завдань синтезу визначається їх великою трудомісткістю, пов'язаної з необхідністю врахування великої кількості параметрів і характеристик зберiгається в РБД інформації, запитів і завдань на коректування.

Результати отримані на етапі синтезу оптимальної логічної структури РБД, є вихідними для проектування структури мережевого каталогу, логічних структур локальних БД, а також для проектування ефективних мережевих протоколів, що забезпечують запобігання взаімоблокіровок і появи тупикових ситуацій при функціонуванні РБнД.

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

У процесі проектування структури мережевого каталогу вирішуються завдання вибору оптимального типу його структури, оптимального розміщення у ЗС головного каталогу (для централізованого типу структури), оптимальних маршрутів доступу користувачів ЗС до мережевим каталогах, оптимальних параметрів організації мережевих каталогів, розміру і складу сторінок обміну між оперативною пам'яттю і зовнішніми запам'ятовуючими пристроями (ВЗУ).

Результатом вирішення завдань даного етапу логічного проектування є оптимальна структура мережевого каталогу забезпечує оптимальну кількість мережевих звернень до нього в процесі реалізацій запитів користувачів і коригувань каталогу з урахуванням географічного розміщення користувачів у ЗС та характеристик запитів а також оптимальну кількість обмінів між оперативною пам'яттю і ВЗП в процесі локального функціонування мережного каталогу в РБіД.

Логічна структура мережевого каталогу фіксована, тому що кількість рівнів ієрархії відповідає кількості рівнів відображення інформації в РБнД та інші параметри логічної організації є детермінованими і не залежать від специфіки предметних областей користувачів. Тому основним завданням проектування мережного каталогу є вибір типу його структури який визначає наявність і характер взаємодії між головними і локальними каталогами в процес реалізації функції управління виконанням процедур обробки інформації в РБнД

Вибір типу структури мережевого каталогу визначається характеристиками запитів, завдань на коригування, топологією ЗС, інтенсивністю внесень змін в логічну структуру РБД, вартісними характеристиками зберігання інформації і т.д.

Поставлено та вирішено завдання синтезу оптимальних за заданим критеріям ефективності логічних і фізичних структур локальних баз даних. При проектуванні оптимальних логічних структур локальних баз даних можливі два підходи, кожен з яких детально досліджено [69, 76, 79, 80].

Перший підхід грунтується на синтезі логічних структур локальних баз даних, ефективність яких визначається єдиним критерієм оптимальності функціонування РБД. Вихідною інформацією, яка використовується в цьому випадку при проектуванні логічних структур локальних БД є характеристики логічної структури РБД і мережевого каталогу. Проектування здійснюється шляхом нормалізації графа логічної структури окремого вузла ВС, що формується в результаті синтезу оптимальної логічної структури РБД та визначення у графі незв'язних і слабо зв'язних підграфів, що є основою логічних структур локальних БД, підтримуваних конкретними СУБД.

Результатом даного етапу є оптимальні логічні структури локальних БД спроектовані з урахуванням характеристик оптимальної логічної структури РБД, обмежень конкретних СУБД і операційного середовища.

Другий підхід дозволяє синтезувати логічні структури баз даних по локальних цільових функцій, що відображає специфічні вимоги користувачів окремих вузлів ПС, з урахуванням єдиного критерію ефективності функціонування РБД, який визначає оптимальний розподіл інформацій по вузлом НД

У цьому випадку синтез логічної структури локальної БД розглядається як пошук оптимального варіанту відображення канонічної структури окремого вузла ВС, отриманої при рішень задачі розподілу інформацій, в таку логічну структуру бази даних, в якій зберігаються семантичні властивості елементів предметної області користувачів і забезпечується ефективність функціонування РБіД для розглянутого безлічі користувачів в умовах заданих вимог обробки даних.

Розроблені моделі та постановки задач синтезу дозволяють врахувати особливості функціонування локальних БД у режимах введення інформацій, оперативного обслуговування запитів користувачів, рішення регламентних задач та задач обробки даних реального часу. Рішення поставлених завдань забезпечує визначення записів обираних і як точки входу в логічну структуру локальної БД.

Основними критеріями ефективності, використовуваними при синтезі логічної структури локальної БД, є мінімум сумарного часу введення інформації та обслуговування заданої множини запитів, мінімум сумарного числа зв'язків між записами, мінімум сумарної довжини шляхів доступу до шуканим інформаційним елементом, а також критерії, що корелюється з достовірністю інформації в локальної БД.

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

Критеріями ефективності, використовуваними при вирішенні комплексу завдань синтезу фізичної структури локальної БД, є мінімум сумарного середнього часу доступу до інформаційних масивів БД, мінімум сумарного числа оброблюваних сторінок пам'яті при обслуговуванні заданої множини запитів в локальній БД, максимум достовірності інформації в БД при реалізації процедур обробки даних . В якості обмежень використовується обмеження на обсяг доступної пам'яті, на середній час доступу до окремих масивів БД, на обсяг на кількість сторінок пам'яті, на допустимий нижній рівень достовірності інформації та ін

Синтез логічної структури локальної БД забезпечує оптимальний розподіл масивів за типами пам'яті та примірників логічних записів по сторінках пам'яті, вибір оптимальних методів організації записів та зв'язків по сторінках пам'яті, вибір оптимальних методів організації записів та зв'язків межах кожного масиву або станиці пам'яті.

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

З використанням одержаних результатів сформульовано принципи побудови і розглянуті основні елементи, структура та алгоритмічне забезпечення автоматизованої системи проектування оптимальних модульних СОД, а також імітаційні моделі для аналізу технології обробки інформації на системному рівні. На цій основі розроблені системи автоматизованого проектування СОД сімейства "Модуль".

Моделі проектування модульних СОД зводяться до задач дискретного програмування, теорії графів і їх модифікаціями. Відомо, що такі завдання дуже складні і часто не вирішують практичні завдання великої розмірності. Нижче розглянемо короткий огляд моделей, методів і алгоритмів розв'язання дискретних задач.

1.2 Моделі і методи розв'язання задач дискретного програмування при проектуванні систем обробки даних

В даний час системи обробки даних різного класу і призначення використовуються у всіх сферах людської діяльності. У процесі створення таких систем використовується сучасні інструментальні засоби програмування, системи управління базами даних, системи автоматизації проектування і керування розробками, елементи штучного інтелекту, сучасна технічна база у вигляді різного рівня обчислювальних мереж.

Разом з тим швидкоплинних умови та вимоги до розробки та експлуатації інформаційних систем, необхідність адаптації до потреб підприємств і організацій, швидке перепрофілювання їх діяльності в умовах ринку зумовлюють необхідність постійного вирішення актуальних завдань створення СОД. Тому завдання аналізу, проектування, експлуатації, модернізації, надійності систем обробки даних є досить актуальними.

Велика кількість вищевказаних прикладних задач, як правило, зводиться до завдань дискретного програмування, постановка і вирішення яких у свою чергу волають значних складності. Насамперед мається на увазі обчислювальна складність (NP-повні задачі), розмірність розв'язуваних прикладних завдань, точність і ефективність розроблених алгоритмів для практичних додатків.

Як показав аналіз проектування модульних системи обробки даних у переважній більшості завдань аналізу і синтезу СОД зводиться до завдань дискретного програмування.

Наведемо короткий огляд моделей і методів задач дискретного програмування (ДП), які у процесі проектування систем обробки даних.

Визначимо завдання дискретного програмування наступним чином. [83]

Завданням дискретного програмування (ДП) будемо називати задачу відшукання екстремуму (max, min) скалярної функції, заданої на дискретному (незв'язною) безлічі, тобто таку задачу математичного програмування (МП), у якої на всі або на частину змінних, що визначають область допустимих рішень, накладено вимога дискретності. Запишемо завдання МП у вигляді:

, (1.2.1)

де - -Мірний вектор; - Скалярний функція; -Деяке безліч в , .

Якщо - Кінцеве (або рахункове) безліч або декартово твір кінцевого (лічильного) множини на безліч потужності континиума, то буде мати місце завдання ДП. У цьому випадку умова приналежності деякому безлічі може бути записано у вигляді:

, ;

, ; ; . (1.2.2)

При - Завдання частково дискретного програмування.

Якщо - Множина всіх цілочисельних векторів, то при - Маємо задачу цілочисельного програмування (ЦП). А при - Завдання часткового цілочисельного програмування (ЧЦП).

Найбільшою мірою вивчені методи вирішення завдань цілочисельного лінійного програмування (ЦЛП):

; (1.2.3)

Тут - Безліч всіх невід'ємних цілих чисел, приватний випадок завдань ЦЛП завдання з булевими змінними, де в (1.2.3):

, ;

У ряді завдань ЦП вимога цілочисельності накладається і на цільову функцію.

При постановці та вирішенні задач дискретного програмування традиційно можна виділити наступні класи: задачі з неподільними, екстремальні комбінаторні задачі, задачі з неординарною розривної цільовою функцією, завдання на некласичних областях, багатоекстремального завдання, дискретні завдання, пов'язані з перебуванням екстремумів на кінцевих множинах.

Прикладні завдання цих класів у свою чергу можуть мати різні математичні постановки та методи їх реалізації. Тому розвиток дискретного програмування здійснюється за наступною схемою: постановка прикладної задачі, розробка математичної моделі дискретного програмування, розробка методу (алгоритму) рішення задачі.

Зазвичай ефективне рішення завдання тісно пов'язане з математичною моделлю задачі, зі структурою моделі і її особливостями.

Розглянемо деякі математичні моделі дискретного програмування та методи їх вирішення.

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

У процесі розвитку теорії дискретного програмування виділився клас комбінаторних моделей. [83]

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

Одним з типових прикладів комбінаторної моделі є задача про комівояжера. [84]

У цьому завданню є найкоротший замкнутий шлях, що проходить по одному разу через усі міста, за умови, що є n міст і задана матриця відстаней між ними.

У комбінаторної постановці необхідно визначити таку перестановку, яка мінімізує величину цільової функції.

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

До булевим моделям зводяться велике число прикладних завдань, що свідчить про перспективність моделей цього класу. [85]

У постановках ряду прикладних задач є деякі особливості, що стосуються цільової функції небудь області обмежень. Наприклад, необхідно визначити, екстремум неординарною розривної функції на опуклому многограннику виду

де

Ці моделі утворюють клас моделей з неоднорідною розривної цільовою функцією.

Моделі знаходження екстремуму на області, що задається не тільки лінійними нерівностям (обмеженнями) але і логічними умовами. Такі області виявляються неопуклих або незв'язними. Ці завдання утворюють моделі на не класичних областях. [84]

Особливий інтерес дослідників викликають багатоекстремального моделі, в яких необхідно визначити оптимальні значення більш однієї цільової функції при наявності (або відсутності) систем обмежень. Як правило, моделі цього класу складні в обчислювальному відношенні. Разом з тим, постановки цілого ряду прикладних задач зводяться до моделей даного класу. Вирішення зазначених завдань є актуальним. [103, 105, 107]

Однією з початкових моделей, безумовно, є модель транспортної задачі з якою пов'язані багато досліджень в області дискретного програмування. Ці дослідження привели до моделей потоків у мережах та іншим модифікаціям зазначених завдань.

Слід зазначити, що розробка моделей тісно пов'язана з методом її реалізації, і навпаки розробка нових методів, у свою чергу, призводить до появи нових моделей для постановки прикладних завдань.

Методи рішення задач дискретного програмування (ДП). У завданнях ДП методи їх вирішення часто пов'язані з їх математичною постановкою та особливостями. Є велика кількість методів для вирішення цих завдань. У зв'язку з цим доцільно виділити наступні методи вирішення завдань ДП: точні й наближені. Серед точних методів найбільш поширені комбінаторні методи і методи відсікання.

Типовим прикладом комбінаторних методів є метод гілок і меж [115]. Суть даного методу полягає в направленому переборі допустимих рішень на основі обчислення оцінок. Основне етапи підходу полягає в наступному:

  1. Початкове безліч рішень розбиваються не підмножини (Процес розгалуження);

  2. Для кожного з підмножин обчислюється значення оцінок (нижні або верхні межі);

  3. На основі цього значення оцінок обчислюються допустимі рішення;

  4. Ітераційний процес розгалуження по заданому правилу і обчислення оцінок продовжується до тих пір, поки не буде отримано оптимальне рішення.

Ідея методу відсікань полягає в наступному. Вирішується вихідна задача. Якщо отримане рішення задовольняє умові цілочисельності, то завдання виконане. В іншому випадку до обмежень вихідної задачі будується нове лінійне обмеження. Далі вирішується завдання з додатково введеним обмеженням. Ітеративний процес повторюється, до тих пір, поки не буде отримано цілочисельне рішення.

Прикладами успішної реалізації методів відсікання є алгоритми Гоморі [83].

Разом з тим, слід зазначити обмежене використання точних методів для вирішення прикладних задач великої розмірності. Незважаючи на використання потужних обчислювальних систем з великою пам'яттю, вдосконалення та розвиток математичного апарату «прокляття дискретності» залишається і на сьогоднішній день.

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

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

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

У ряді випадків при проектуванні систем обробки даних необхідно враховувати вектор критеріїв, які можуть суперечити один одному. Такі постановки завдань зводяться до багатокритеріальним завданням дискретного програмування.

Математична постановка - Критеріальної задачі передбачається, що задано безліч допустимих рішень , На якому визначена векторна цільова функція (ВЦФ) [98,99].

, (1.2.4)

Причому критерії ВЦФ вважаємо мінімізіруемимі:

F v (x) → min, v = 1,2, ..., N. (1.2.5)

Елемент називається Парето-оптимальним, якщо не існує такого допустимого рішення , Що виконуються нерівності , v = 1, 2, ..., N, серед яких хоча б одна є строгим.

Через позначаємо паретовское безліч (ПМ), що складається з усіх Парето-оптимальних елементів розглянутої задачі з ВЦФ (1) на множині . Ця задача називається дискретною, якщо потужність безлічі її допустимих рішень кінцева.

Первісне формулювання проблеми багатокритеріальної (векторної) оптимізації сходить до [98, 99] і полягає в знаходженні одного або всіх елементів ПМ . Зауважимо, що в однокритерійним випадку ( ) ПМ являє собою безліч всіх оптимумів даної оптимізаційної задачі. Для останньої, однак, більш природною є проблема знаходження якогось («першого-ліпшого») оптимуму. Як узагальнення цієї проблеми для багатокритеріального випадку в цій роботі в якості основної розглядаємо проблему знаходження повної множини альтернатив (ПМА). Підмножина назвемо ПМА, якщо воно задовольняє двом умовам: його потужність мінімально і виконується , Де , Де

.

Безліч і будемо називати множинами альтернатив (МА). У літературі поряд з МА вивчається і інші підмножина паретовского множини.

У системному моделюванні, зокрема, в теорій вибору і прийняття рішень найбільш поширеними способами знаходження МА є наступні.

  1. Побудова (визначення) детермінованого формального механізму, що дозволяє генерувати альтернативи за допомогою параметрів алгоритму або за допомогою параметрів формули. [100 - 103]

  2. Представлення МА в неявному вигляді за допомогою системи співвідношень (обмежень). [104-105]

  3. Перерахування всіх елементів МА, тобто уявлення кожного елемента МА в явному вигляді. [1 08, 109]

У роботі [121], саме в контексті алгоритмічної проблеми, що відноситься до останнього з зазначених вище трьох способів, здійснюється обгрунтування оцінок потужності МА для таких багатокритеріальних дискретних завдань, як завдання про вчинені паросполучення, про комівояжера, про ланцюгах між парою вершин та інші при цьому знаходження МА розуміється як перерахування з пред'явленням усіх його елементів [110, 100]. За певних умов нижні оцінки потужності ПМ і ПМА перерахованих завдань виявляється експоненціальним. Останнє означає, що для розглянутих завдань проблема знаходження МА є труднорешаемой [110,111]. Або (у термінології [112,113]) вона має експоненційну обчислювальну складність.

Слідуючи, [112], розглянуту - Критеріальну задачу назвемо індивідуальної, якщо всі її параметри мають фіксовані значення. Говоримо про масову - Критеріальної задачі або, коротко, про завдання, якщо для деяких параметрів задано не фіксовані значення, а діапазони їх зміни.

Аналізуючи програми тієї або іншої задачі, неважко переконатися, що склад критеріїв ВЦФ зазвичай змінюється. Наприклад, в системах автоматизованого проектування електронної техніки [114-118] виникає багатокритеріальні задачі на графах, в яких кістяк (зв'язує мережа) може оцінюється такими критеріями, як вага, «вузьке місце» (мінімаксний критерій), ступінь, діаметр і т. д. [119,120]. При цьому в міру необхідності ці критерії входять до складу ВЦФ в різноманітних комбінаціях, породжуючи різні варіанти задач про остовних деревах. Спільним у цих завдань є лише безліч допустимих рішень , Кожен елемент якого є зв'язковим остовних подграфом даного графа.

Використовуючи поняття «завдання» як змінне, вживаємо для її позначення символ [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), які залежать від змінної .

Функціонал виду можна представити наступним чином:

(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] Результати даного твердження дозволяють просто обчислити оцінки та напрямки пошуку рішення для розробки ефективних алгоритмів.

Введемо поняття базису вирішення завдань. Під базисом розуміється заздалегідь заданий склад елементів підмножин і .

У матриці базис знаходиться як деяка матриця елементи яких визначені. Цю матрицю шляхом перестановки номерів рядка стовпців матриці та їх перенуміровкі завжди можна визначити в лівому верхньому кутку. Таке уявлення спрощує процедуру оцінок і визначення напрямку пошуку рішення.

Для вирішення блочно-симетричної задачі дискретного програмування за умови, коли , і - Булеві матриці, розроблена і запропонована ефективна схема рішення задачі. Схема пошуку рішення складається з наступних основних етапів:

  1. У булевої матриці виділимо підматриць , , і визначимо її як базис рішення задачі.

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

  3. Відповідно з отриманими оцінками здійснимо розподіл елементів множини по множинам . У результаті зафіксуємо рішення і проміжну. Матрицю , , .

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

  5. Відповідно з отриманими оцінками матриці розподілимо елементи множини по множин а м . У результаті фіксуємо рішення і цільову матрицю , На якій визначено значення цільової функції .

  6. Слід зазначити, що пошук рішення задачі може здійснюватися як в прямому напрямку за схемою , Так і в зворотному напрямку за схемою .

При заданому базисі рішення даного класу задач має поліномінальної обчислювальну складність.

2.2 Декомпозиція прикладних завдань і вихідних документів систем про бработкі даних на етапі технічного проектування

При проектуванні систем обробки даних на етапі передпроектного аналізу об'єктів визначається перелік прикладних задач обробки даних, що підлягають автоматизації, послідовність їх вирішення, вихідні документи, що використовуються для вирішення прикладних завдань, характеристики прикладних завдань і документів. Створення масштабних і складних систем пов'язано з великим числом прикладних завдань і документів, які необхідно аналізувати, систематизувати та обробляти з метою скорочення витрат і часу на проектування систем обробки даних. При цьому залежно від складності систем, необхідно розділити її на слабкозв'язаного компоненти (кластери прикладних завдань і документів), щоб надалі передати отримані компоненти різним групам розробників проекту. У процесі декомпозиції (поділу) безліч завдань на окремі компоненти можуть бути враховані кваліфікація і досвід фахівців, а так само витрати і час проектування. Тому декомпозиція прикладних завдань і безлічі вихідних документів є актуальним завданням, що дозволяє розробляти ефективні системи обробки даних. Компоненти системи дозволяють розробникам ретельно провести аналіз та вивчення системи, визначити взаємозв'язки (інтерфейс) із іншими прикладними (функціональними) завданнями, особливості та характеристики розв'язуваних функціональних завдань і документообігу.

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

Розглянемо постановку задачі декомпозиції складних систем обробки даних на етапі технічного проектування.

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

При великому числі прикладних завдань і складному документообігу виникає необхідність декомпозиції системи на кластери.

Під кластером прикладних задач розуміється об'єднання завдань у підмножини, а кластерами документів об'єднання документів в підмножини і встановлення взаємозв'язків між відповідними підмножинами. Таким чином, розробляється система може бути представлена ​​у вигляді дводольних графа, вершинами верхнього рівня якого є функціональні завдання, а вершинами нижнього рівня - документи використовуються при реалізації завдань. Дуги дводольних графа відображають взаємозв'язки між завданнями і документами в процесі вирішення завдань. Результатом декомпозиції системи є також двочастковий граф, вершинами верхнього рівня якого є кластери функціональних завдань, вершинами нижнього рівня кластери вихідних документів. Взаємозв'язки між ними відображають інтегровані связімежду кластерами (рис 2.2.1). Досвід проектування систем обробки даних і проведені дослідження показали, необхідність декомпозиції вихідної системи, яка дозволяє на етапі технічного проектування глибше проаналізувати кластери завдань і документів, распараллеліть обсяги робіт між проектувальниками, виділити процедури обробки даних та інформаційні елементи для розробки прикладного програмного забезпечення та бази даних СОД .

Тому в якості критерію ефективності процесу декомпозиції вихідної системи використовуємо мінімум інформаційних взаємозв'язків між кластерами завдань і документів. Для математичної постановки задачі декомпозиції системи введемо такі змінні і позначення. Нехай, , , - Мінлива відбиває розподілені - ой прикладної задачі в -Ої кластер (групу) завдань. У даному випадку

Аналогічно введемо змінну

, , , Де

У ряді випадків на даному етапі визначаються характеристики завдань і документів.

Введемо - Час розробки -Ої завдання, - Обсяг -Ого документа, - Загальна вартість розробки -Ої завдання і -Го документа, - Час розробки і підготовки -Го документа, -Вартість розробки -Ої завдання, - Вартість підготовки -Го документа.

Нехай, - Безліч прикладних задач обробки даних, що підлягають автоматизації; - Безліч вихідних документів, що використовується для вирішення прикладних завдань. Задано, матриця , , , Де , Якщо -Й вихідний документ використовується для вирішення -Ої прикладної задачі системи і , В іншому випадку.

Необхідно розбити систему на підмножини прикладних задач і використовуваних ними документів таким чином, щоб мінімізувати взаємозв'язку між кластерами прикладних завдань і документів у процесі проектування СОД (рис 2.2.1).

Визначимо додаткові змінні наступним чином:

Дана змінна відображає використання -Го документа для вирішення завдань -Го кластеру.

Мінлива відображає використання в процесі рішення -Ої завдання -Го кластеру документів.

Взаємозв'язки між кластерами прикладних завдань і документів визначається з виразу:

Задачу декомпозиції СОД сформулюємо наступним чином.

Необхідно мінімізувати функцію виду

. (2.2.1)

При обмеженнях на:

  • включення кожної прикладної задачі тільки в один кластер

, ; (2.2.2)

  • включення документа тільки в один кластер документів

, ; (2.2.3)

  • час розробки кожного кластера завдань

, ; (2.2.4)

  • вартість проектування кожного кластера завдань

, ; (2.2.5)

  • число прикладних завдань в кластері

, ; (2.2.6)

  • число вихідних документів в кластері

, . (2.2.7)

Поставлена ​​задача відноситься до блочно-симетричним завданням дискретного програмування. Для її рішення розроблений і запропонований ефективний алгоритм дозволяє вирішувати задачі великої розмірності.

2.3 Проектування модульних блок-схем систем обробки даних

У результатах декомпозиції складних систем обробки даних на кластери на етапі технічного проектування необхідно для кожного кластера розробити модульну блок-схему прикладного програмного забезпечення та бази даних. Кожен кластер СОД і входять до його складу прикладні задачі можуть бути представлені у вигляді напрямку графа процедур обробки даних, а кластер вихідних документів - у вигляді сукупності інформаційних елементів. Ці дані є вихідними для проектування прикладних програм і бази даних. Відомо, що будь-який розгалужений граф відображення прикладної задачі можна представити у вигляді послідовного графа - цілі відображає послідовність реалізації процедур [126]. Тому кожен кластер і завдання можна відобразити у вигляді лінійної послідовності процедур.

Визначення 2.3.1. Модульної блок-схемою обробки даних будемо називати сукупність процедур, об'єднаних в модулі і безліч інформаційних елементів, об'єднаних в масиви (таблиця) даних з відображенням інгрірованних зв'язків між модулями і масивами.

Модульна блок-схема дозволяє автоматизувати процес програмування прикладних задач і створення бази даних та скоротити витрати і тривалість розроблюваних систем.

На етапі робочого проектування найбільш загальним критерієм синтезу оптимальних блок-схем модульних СОД є їх складність, яка на логічному рівні вимірюється числом інформаційних взаємозв'язків між програмними модулями і масивами бази даних. При синтезі блок-схеми повинні бути враховані основні характеристики та обмеження систем управління базами даних і обчислювальних засобів, на яких передбачається експлуатація створюваного програмного та інформаційного забезпечення.

Розглянемо задачу синтезу модульної блок-схеми системи обробки даних, що мінімізує загальне число зв'язків між модулями і масивами бази даних.

Для постановки задачі введемо такі позначення. Нехай, - Безліч процедур обробки даних для вирішення прикладних завдань системи; - Безліч інформаційних елементів, необхідних для реалізації процедур з множин . На безлічі введемо відношення , Що визначається матрицею , Де

Необхідно синтезувати модульну блок-схему СОД шляхом розподілу безлічі процедур по модулях обробки даних, безлічі інформаційних елементів - у логічну структуру бази даних, і встановити оптимальні взаємозв'язку між модулями і логічної структурою бази даних, що мінімізують кількість взаємозв'язків між компонентами блок-схеми.

Введемо наступні змінні:

Введемо допоміжні змінні:

Змінна відображає використання -Го інформаційного елемента -М модулем, тобто якщо хоча б один інформаційний елемент обробляється -Ої процедурою, включений до складу -Го модуля, то даний елемент також обробляється цим модулем.

Змінна відображає використання -Го масиву даних -Ої процедурою, тобто якщо процедура використовує хоча б один інформаційний елемент, включеної до складу -Го масиву даних, то дана процедура використовує цей масив.

Мінливу відображає взаємозв'язок між модулями блок-схеми і масивами бази даних можна визначити наступним чином:

,

або,

Визначення зазначених змінних випливає з властивості симетричності блочно-симетричних завдань.

Завдання проектування модульних блок-схем систем обробки даних (МСОД) формулюється таким чином.

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

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

Математична постановка задачі має вигляд:

(2.3.1)

при обмеженнях:

  • кількість процедур у складі кожного модуля блок-схеми

, , (2.3.2)

де -Допустиму кількість процедур у -Му модулі;

  • включення окремих процедур обработкіданних до складу одного модуля

, , (2.3.3)

для заданих і ;

  • дублювання процедур у модулях блок-схеми

, , (2.3.4)

  • розмір запису масиву бази даних

; , (2.3.5)

де - допустиму кількість інформаційних елементів у записі -Го масиву даних;

  • дублювання інформаційних елементів в масивах бази даних

, ; (2.3.6)

  • кількість інформаційних елементів, що обробляються кожним модулем

, . (2.3.7)

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

Цільову функцію (2.3.1) блочно-симетричної задачі розробки модульної блок-схеми зручно представити в матричній формі.

(2.3.8)

або

. (2.3.9)

Рішенням завдань (2.3.1) - (2.3.7) є ю ться множин а булевих матриць , В якому - Склад модулів блок-схеми, - Склад масивів бази даних блок-схеми, - Взаємозв'язки між модулями і масивами бази даних блок-схеми, а також оптимальні значення цільової функції . Для вирішення даної задачі розроблений і запропонований ефективний алгоритм ітеративних відображень (розділ 3).

2.4 Приватні завдання проектування модульних блок-схем систем обробки даних

Багатоетапний процес розробки бази даних, який включає послідовне створення її концептуальної, логічної і фізичної моделі з подальшою експлуатацією з використанням можливостей обраної системи управління базою даних (СКБД). При цьому найбільш трудомістким етапом є проектування концептуальної та логічної моделі даних в процесі якого необхідно провести аналіз предметної області, визначити сутності (об'єкти) та їх взаємозв'язку, виділити ключові елементи і т.д.

Роботи з проектування бази даних на цьому етапі слабко формалізовані і великою мірою грунтуються на досвіді та інтуїції розробників.

У процесі проектування бази даних необхідно також забезпечити ефективність її аналізу, структуризації та обробки. Тому структуризація проектованої бази даних, тобто виділення масивів і взаємозв'язків між ними та забезпечення її ефективності є актуальною задачею.

У процесі проектування систем обробки даних на різних об'єктах можуть виникнуть ситуації, пов'язані з умовами та особливостями даних об'єктів. Наприклад, визначено склад прикладних задач, які мають модульну структуру програм і для реалізації зазначених завдань необхідно сформулювати базу даних.

Ряд обставин пов'язаний з включенням у систему нових прикладних задач, реорганізацією бази даних, модернізацією системи. У цих умовах розробка методів проектування масивів бази даних для заданої множини програмних модулів є актуальним завданням.

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

Завдання розробки логічної структури бази даних при заданій множині програмних модулів (запитів) формулюється наступним чином [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. Висновок вирішення задачі: матриць , , і значення цільової функції .

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

Необхідні кількість кроків у процесі вирішення задачі з використанням алгоритму ітеративних відображень одно

, (3.1.3)

де , - Кількість ітерацій в процесі формування відповідних рішень і . Число кроків з використанням методу «гілок і меж» для вирішення зазначених завдань визначається за наступною формулою

. (3.1.4)

Порівняння співвідношень (3.1.1), (3.1.2) показує ефективність і поліноміальну складність розроблених алгоритмів для вирішення поставлених задач великої розмірності, на відміну від методу «гілок і меж».

Блок-схема алгоритму ітеративних відображень наведена на рис. 3.1.1.

Розглянемо чисельний приклад вирішення завдання. Необхідно синтезувати блок-схему модульної СОД, що мінімізувала загальне число звернень до логічних масивом бази даних.

Завдання вирішується при наступних умовах: допустиму кількість процедур у складі модуля 3, допустиму кількість інформаційних елементів у складі логічних масивів 4. Кількість модулів і логічних масивів визначається за формулами: і , З округленням у більшу рядок.

У таблиці 3.1.1 представлена ​​вихідна матриця з виділеним базисом у верхньому лівому куті вихідної матриці. У базис увійшли 1, 2, 3, 4, 5 і рядки 1, 2, 3 матриці . На малюнку 3.1.2 показано процес формування рішення з використанням розробленого алгоритму. Матриця визначена з використанням співвідношення (3.1.1).

Процес відображень представлений таблицею, в якій наведено номер ітерації , Мінімальний елемент з , Відповідно до якого відображається номер процедури кімнати модуля . На малюнку представлені матриці і , Зміст яких визначено базисом пошуку рішення , А в правій матриць е і , Отриманий н і з використанням алгоритму ітеративних відображень.

На малюнку 3.1.2 показано процес формування рішення . Матриця визначена з використанням співвідношення (3.1.2) і матриці . Процес відображення представлений таблицею, в якій наведено номер ітерації , Мінімальний елемент з відповідно до якого номер інформаційного елемента відображається в номер файлу . На малюнку 3.1.2 представлена ​​матриця , Яка сформована до пошуку оптимального рішення і визначена базисом, а також матриця, отримана в результаті формування рішення . А також представлені матриця рішення задачі , Отримана з використаним алгоритму ітеративних відображень, і матриця , Отримана в результаті відображення. Матриця відповідає матриці цільової функції , Що відбиває взаємозв'язку програмних модулів і логічних масивів бази даних модульної блок-схеми. Оптимальне значення цільової функції, одержане при цьому базисі і огранічеіях, так само = = 6.

З використанням алгоритму ітеративних відображень вирішуються і приватні задачі виду (2.4.1) - (2.4.4) і (2.4.5) - (2.4.8) як частини блочно-симетричних завдань.

3.2 Постановка і рішення багатокритеріальних задач розробки модульних блок-схем обробки даних

Як показав досвід проектування систем обробки даних у ряді випадків до них пред'являються різні технологічні вимоги, часто суперечливі, які необхідно враховувати. При цьому одні вимоги мають важливе значення в якості критеріїв ефективності, а інші - визначають технологічні обмеження у процесі проектування систем обробки даних.

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

Загальна постановка багатокритеріальної задачі формулюється наступним чином [121-123,135,142,143].

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

Наведемо математичну постановку загальної багатокритеріальної задачі.

Нехай, - Двухіндексная змінна, відбиває розподіл елементів одного типу по групах, а - Змінна, що відображає розподіл елементів іншого типу по соответствущім групам. Задано матриця взаємозв'язку елементів різних типів між собою.

Визначено критерії , ефективності, залежні від змінних і , Що доставляють екстремум функції виду , .

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

, (3.2.1)

при обмеженнях виду

, , (3.2.2)

, . (3.2.3)

Для вирішення однокритерійним блочно-симетричної задачі ( ) Розроблений і запропонований ефективний алгоритм, що дозволяє визначити оптимальні рішення при певних умовах. Використовуючи розроблений алгоритм можна запропонувати наступну схему вирішення багатокритеріальної задачі.

  1. Вирішується однокритерійним завдання при обмеженнях виду (3.2.2) - (3.2.3) з використанням заданого алгоритму. Визначаються змінні і .

  2. Визначаються значення функцій , .

  3. Вирішується однокритерійним завдання при обмеженнях виду (3.2.2) - (3.2.3) з використанням заданого алгоритму. Визначаються змінні і .

  4. Визначаються значення функцій , .

  5. Вирішується однокритерійним завдання при обмеженнях виду (3.2.2) - (3.2.3) з використанням заданого алгоритму. Визначаються змінні і .

  6. Екстремальні значення функцій визначають область знаходження рішення.

Таким чином, у результаті рішення багатокритеріальної задачі визначається область рішення, в якій знаходиться рішення, що задовольняє всім критеріям і відповідати умовам [135].

Розглянемо постановку і рішення двухкрітеріальной завдання розробки модульної блок-схеми системи обробки даних.

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

В якості критерію ефективності використовуємо мінімум взаємозв'язків між модулями блок-схем і масивами бази даних. Цей критерій дозволяє представити структуру блок-схеми у вигляді слабосвязанних компонент модулів і пов'язаних з ними масивів бази даних, зменшити число звернень модулів до масивів у процесі їх обробки. При заданих числових характеристиках: часу обробки процедури інформаційних елементів, часу звернення модулів до масивів бази даних, обсягів процедур та інформаційних елементів, формується критерії мінімуму часу обробки блок-схем, мінімуму пам'яті при обробці блок-схем і т.д.

У матрчной формі даний критерій запишеться у вигляді

. (3.2.4)

У процесі проектування модульних блок-схем часто необхідно, визначити міжмодульних інтерфейс, який являє собою склад і кількість інформаційних елементів між модулями систем обробки даних. Цей критерій дозволяє визначити зміст міжмодульних інтерфейсу і оптимальну структуру всієї модульної блок-схеми.

Критерій мінімуму інформаційних елементів, використовуваних програмними модулями (міжмодульних інтерфейс) блок-схеми обробки даних у матричній формі записується таким чином:

. (3.2.5)

У загальному випадку дані критерії суперечливі, для яких важко визначити точне рішення.

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

(3.2.6)

(3.2.7)

при обмеженнях виду (3.2.2) - (3.2.3).

- Сума одиничних елементів результуючих булевих матриць (3.2.6) і (3.2.3);

, , - Мінлива розподілу процедур обробки даних по модулях блок-схеми;

, , - Мінлива розподілу інформаційних елементів по масивах бази даних;

- Взаємозв'язки між інформаційними елементами і процедурами обробки даних;

- Транспонована матриця.

Для вирішення поставленого завдання розроблений і запропонований алгортм, заснований на вищевказаній схемі вирішення загальної багатокритеріальної задачі.

Розглянемо чисельний приклад вирішення двухкрітеріальной завдання. На таблиці 3.2.1 наведена вихідна матриця. Використовуючи запропонований алгоритм рішення однокритеріальних завдань знаходимо рішення двухкрітеріальной завдання. На рис. 3.2.3 та 3.2.4 наведено чисельний приклад вирішення двухкрітеріальной завдання. Значення цільової функції наведено на рис. 3.2.5. Отримане рішення визначає область, обмежену трикутником АВС (рис. 3.2.6).

Розроблено програмне забезпечення вирішення двухкрітеріальной завдання виду (3.2.6) - (3.2.7) і (3.2.2) - (3.2.3) при будь-якому розмірі вихідної матриці (Розмір вихідної матриці генерується випадковим чином) в середовищі Delphi 7.0. Програмне опеспеченіе описано в розділі 3.3.

3.3 Програмне забезпечення вирішення двухкрітеріальной блочно-симетричної задачі проектування модульних систем обробки даних

3.3.1 Опис програмного забезпечення вирішення завдань проектування модульної блок-схеми обробки даних

Розроблена програма призначена для вирішення двухкрітеріальной завдання проектування модульної блок-схеми обробки даних [139-141,143,146].

Програма дозволяє розробникам СОД швидко і ефективно вирішувати завдання проектування модульної блок-схеми, що задовольняють заданим критеріям.

Основними критеріями вибору програмного середовища для створення даної програми є:

  1. Забезпечення максимальної простоти роботи в системі, для цього розроблено зручний для користувача інтерфейс.

  2. Забезпечення максимальної швидкості роботи програми.

  3. Доступність всіх шрифтів програми

На основі послідовних критеріїв та аналізу сучасних програмних середовищ була обрана візуальна програмне середовище Borland Delphi 7.0. Програма розроблена в середовищі Borland Delphi 9 [145].

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

Процедура Create_Mat c оздаем матрицю W випадковим чином за заданими числах ст ро к і стовпців матриці і записує його на файл. Процедура Rotate транспонирует задану матрицю, використовується для обчислення матриці Y. Процедура Mat_D створює матрицю D (базис). який на кожній ітерацій визначає значення елементів. Процедура New_matrisa. Проміжна матриця створюється за значенням елементів матриці D і формує рішення і Y з використанням алгоритму однокритерійним блочно-симетричної задачі. У програмі використовуються функції SUM і SUM _ UM, які обчислюють елементи проміжної матриці за критеріями (логічне додавання і множення). Значення цільових функції за двома критеріями відповідно записуються на два файли і будується їх область рішення.

3.3.2 Опис логічної структури розробленої програми призначеної для вирішення двухкрітеріальной завдання проектування модульної блок-схеми обробки даних

Логічна структура модуля Unit 1 з прив'язкою до рядків тексту має наступний вигляд:

1 - Присвоєння імені Unit 1 до Unit - у

2 - Відкритий інтерфейс модуля

3 - 5 - Список модулів

6 - 7 - Оголошення класу форми

8 - 13 - Оголошення типів компонентів

14 - 15 - Оголошення процедур

16 - 17 - Закрита частина класу

18 - 19 - Відкрита частина класу

20 - Кінець оголошення описі модуля

21 - 22 - Оголошення типів змінних

23 - 25 - Підключення модулів

26 - 47 - Оголошення типів змінних

48 - 54 - Функція складання

55 - 61 - Функція твори

62 - 120 - Функція створення матриці

121 - 144 - Функція транспонування матриці

145 - 228 - Процедура вирішення Mat _ D

229 - 824 - Процедура створення нової матриці

825 - 828 - Закриття форми Form 1

829 - Кінець модуля

Логічна структура модуля Unit 2 з прив'язкою до рядків тексту має наступний вигляд:

830 - Присвоєння імені Unit 2 до Unit - у

831 - Відкритий інтерфейс модуля

832 - 834 - Список модулів

835 - 836 - Оголошення класу форми

837 - 847 - Оголошення типів компонентів

849 - 851 - Оголошення процедур

852 - 853 - Закрита частина класу

854 - 855 - Відкрита частина класу

856 - Кінець оголошення описі модуля

857 - 858 - Оголошення типів змінних

859 - 861 - Підключення модулів

862 - 867 - Процедура вирішення задачі за критерієм складання

868 - 873 - Процедура вирішення задачі за критерієм множення

874 - 877 - Закриття форми Form 2

878 - Кінець модуля

Логічна структура модуля Unit 3 з прив'язкою до рядків тексту має наступний вигляд:

879 - Присвоєння імені Unit 3 до Unit - у

880 - Відкритий інтерфейс модуля

881 - 883 - Список модулів

884 - 885 - Оголошення класу форми

886 - 889 - Оголошення типів компонентів

890 - Оголошення процедур

891 - 892 - Закрита частина класу

893 - 894 - Відкрита частина класу

895 - Кінець оголошення описі модуля

896 - Оголошення типів змінних

897 - 899 - Підключення модулів

900 - 903 - Закриття форми Form 3

904 - Кінець модуля

Логічна структура модуля Unit 4 із прив'язкою до рядків тексту має наступний вигляд:

905 - Присвоєння імені Unit 4 до Unit - у

906 - Відкритий інтерфейс модуля

907 - 909 - Список модулів

910 - 911 - Оголошення класу форми

912 - 915 - Оголошення типів компонентів

916 - Оголошення процедур

917 - 918 - Закрита частина класу

919 - 920 - Відкрита частина класу

921 - Кінець оголошення описі модуля

922 - 923 - Оголошення типів змінних

924 - 925 - Підключення модулів

926 - 929 - Закриття форми Form 3

930 - Кінець модуля

3.3.3 Виклик і завантаження програми

Для виклику програми необхідно запустити Пуск → Програми → Borland Delphi7 → Delphi7 і з каталогу знайти відповідний. ехе файл.

Для компіляції програми натиснути F 9 або на вкладці Run → Run відповідно.

Вхідні дані. Вхідні дані представлені на малюнку 3.3.2.

Вихідні дані. За допомогою різних процедур і функції отримуємо наступні дані, представлені на малюнках 3.3.3, 3.3.4, 3.3.5.

Висновки по розділу 3

  • Розроблено та запропоновано ефективний алгоритм рішення блочно-симетричних завдань проектування модульних блок-схем обробки даних поліномінальної обчислювальної складності.

  • Поставлена ​​і вирішена багатокритеріальна задача синтезу модульних блок-схем обробки даних з використанням показників ефективності: мінімум взаємозв'язків між модулями і масивами бази даних; мінімум міжмодульних інтерфейсу в проектованих системах.

  • Розроблено програмне забезпечення проектування систем обробки даних.

ВИСНОВОК

У дисертаційній роботі отримані наступні результати:

  1. Розроблено підхід, взаємопов'язаний комплекс моделей, методів, алгоритмів і програмних засобів формалізованого проектування систем обробки даних на основі нового класу завдань - блочно-симетричних задач дискретного програмування.

  2. Запропоновано загальну постановка блочно-симетричних завдань проектування систем обробки даних. Розроблено загальну модель і схема її реалізації, визначено властивості і особливості завдань даного класу.

  3. Сформульована і вирішена задача декомпозиції систем обробки даних на кластери прикладних завдань і вихідних документів, яке вирішується на етапі технічного проектування систем.

  4. Поставлена ​​і вирішена задача синтезу оптимальних модульних блок-схем обробки даних, що забезпечує мінімум загальних інформаційних взаємозв'язків між модулями і масивами бази даних системи. Завдання вирішується на етапі робочого проектування систем обробки даних і дозволяє скоротити витрати і час розробки прикладного програмного забезпечення та бази даних.

  5. Розроблено новий ефективний алгоритм ітеративних відображень рішення блочно-симетричних завдань проектування систем обробки даних поліноміальної обчислювальної складності.

  6. Сформульована і вирішена багатокритеріальна задача проектування модульних блок-схем обробки даних. Розроблено алгоритм розв'язання багатокритеріальної задачі при заданому векторі цільових функції.

  7. Розроблено програмне забезпечення рішення блочно-сімметічних задач проектування систем обробки даних.

Розроблені блочно-симетричні моделі, методи, алгоритми і програмне забезпечення впроваджені в Усть-Каменогорському свинцево-цинковій комбінаті, Комітеті інформатизації та зв'язку, а також у навчальний процес КазНТУ імені К. І. Сатпаєва.

Результати наукових досліджень дозволили скоротити тривалість проектування прикладного програмного та інформаційного забезпечення систем обробки даних у 5-10 разів у порівнянні з традиційними технологіями проектування.

СПИСОК ВИКОРИСТАНИХ ДЖЕРЕЛ

  1. Трапезников В.А. Управління та науково-технічний процес. М: Наука, 1983. C. 8 березня - 9 2.

  2. Boehm B. Software engineering / / IEEE Trans. Computers. Dec. 1976. V.25 № 12 P.1226-1241.

  3. Parnas DL On the criteria to be used in decomposing systems into moduls / / CACM. Dec. 1978.P.1053-1058.

  4. Boehm B. Software and its impact: A guantitative assessment / / Datamation. May 1973. P. 48-59.

  5. Phodes J. Mansgement by m = Moduls. pt. / / Data systems. 1971 V.12. № 8. Pt 2; № 9.

  6. Parnas DL The influence of software structure on reliability / / Proc. Int. conf. Reliable Software. Apr. 1975. P. 358-362.

  7. Липаев В.В., Пилипович В.В., Принципи і правила модульної побудови складних комплексів програм АСУ / / Доп. 1975. № 1. C .43-52.

  8. Куликов М.Я., Погрібний В.К. Про модульних принципах побудови АСУ в умовах автоматизованого проектування / / Прилади і системи управління. 1978. № 11 С. 10-14.

  9. Boehm B. Structured programming: A guantitative assessment / / Computer. June 1975.P. 38-54.

  10. Parisi-Presicce F. A based approach to modular system design / / 12th Int. Conf. Software Eng., Nice. Los Alamitos (Calif), 1990. P. 202-211.

  11. George KM A multilevel programming paradigm / / 9th Annu. Int. Phoenix conf. Comput. And Commun., Seottsdale Ariz, Los Alamitos (Calif), 1990, P.340-346.

  12. Маміконов А.Г., Косяченко С.А., Кульба В.В. Питання модульного побудови складних програм / / Формалізовані методи синтезу складних систем. К.: Ін-т проблем управління. 1976.Випю 13. С.-16-24.

  13. Казіев Г.З., Косяченко С.А., Кульба В.В. Деякі питання модульного проектування АСУ. Науково-технічна пропаганда. М.: ЦНІІТЕІпріборостроенія, 1977.

  14. Кульба В.В., Маміконов А.Г. Методи аналізу і синтезу оптимальних модульних систем обробки даних (огляд) / / Аіт. 1980. № 11 С. 152-179.

  15. Кульба В.В., Маміконов А.Г. Синтез оптимальних модульних СОД.М.: Наука, 1986

  16. Маміконов А.Г., Ашіму А.А., Кульба В.В. Оптимальні модульні системи обробки даних. Алма-ата: Наука, 1981.

  17. Кульба В.В., Маміконов А.Г. Завдання модульної побудови ІДС / / Тез. Докл.і Повідомлень на Всесоюзній конференції з вимірювальним інформаційних систем (ІДС-77). Баку: АзіНЕФТЕХІМ, 1977. С.10-11.

  18. Кульба В.В., Маміконов А.Г., Косяченко С.А., КуКазіев Г.З. Завдання формалізації та автоматизації модульного роектірованія систем обробки даних. К.: Ін-т проблем управління, 1978. Вип. 16. С. 5-18.

  19. Маміконов А.Г., Аміші А.А., Кульба В.В. та ін Синтез інформаційного забезпечення модульних систем обробки / / Тр. 5-го Всесоюз. Наради-семінару з управління великими системами. Алма-ата: КазПТІ, 1978. С. 8-13.

  20. Маміконов А.Г., Аміші А.А., Кульба В.В. та ін Синтез інформаційного забезпечення модульних систем обробки / / Тр. 5-го Всесоюз. Наради-семінару з управління великими системами. Алма-ата: КазПТІ, 1978. С.17-20.

  21. Маміконов А.Г., Аміші А.А., Кульба В.В. та ін Синтез оптімльних функціональних модулів обробки даних в АСУ. Препринт. К.: Ін-т проблем управління, 1979.

  22. Алексєєв О.Г., Бабаєв А.А., Володя І.Ф. Комбінований метод вибору модулів при розробці програм за критерієм швидкодії / / Програмування. 1978. № 3. С. 18-28.

  23. Маміконов А.Г., Ашіму А.А, Кульба В.В. та ін Автоматизація проектування оптимальних модульних систем обробка даних / / Методи аналізу і синтезу автоматизованих систем управління. К.: Ін-т проблем управління, 1981. Вип. 25. С. 5-15.

  24. Маміконов А.Г., Ашіму А.А, Кульба В.В. та ін Моделі і методи автоматизації проектування модульних систем обробка даних / / Автоматизація проектування систем управління. М.: Фінанси і статистика, 1981. С. 23-31.

  25. Кротюк Ю.М., Федюшенко І.В. Імовірнісні моделі синтезу програмного забезпечення модульних систем обробка даних РМ / / Система програмного забезпечення АСУ. Мінськ: ЦНІІТУ, 1976. Вип 4 (38). С. 124-133.

  26. Кротюк Ю.М. Формалізовані моделі та методи синтезу інформаційного та програмного забезпечення модульних СОД РВ / / Тез. Докл. Науково-технічної конференції «Комплексна автоматизація і механізація-основа підвищення ефективності виробництва і якості роботи підприємств радіоелектроніки, зв'язку і телебачення». Мінськ: БелНІІТІ, 1980. С. 19-20

  27. 28. Кротюк Ю.М. Формалізація моделі оптимальної декомпозиції та інформаційного забезпечення модульних СОД РВ / / Автоматизація процесів проектування. Мінськ: Ін-т технічної кібернетики АН УРСР, 1980. Вип. 3. С. 89-92.

  28. Кошелев В.А. Деякі завдання синтезу оптимальних модульних СОД РВ / / Теоретичні та прикладні задачі оптимізації. М.: Наука, 1985. С. 125-131.

  29. Кротюк Ю.М., Кошелев В.А. Синтез оптимальних модульних СОД РВ з відносними пріоритетами / / Питання кібернетика. Автоматизація проектування систем обробки даних. М.: Наукова рада комплексної проблеми «Кібернетика», 1985. С. 45-55.

  30. Кульба В.В., Кротюк Ю.М., Косяченко С.А. Завдання синтезу оптимальних модульних СОД РВ / / Удосконалення технології створення математичного та програмного забезпечення АСУ. Мінськ: ЦНІіПТІ організації і техніки управління, 1982. С. 110-121.

  31. Маміконов А.Г., Кульба В.В., Косяченко С.А. та ін Типізація розробки модульних систем обробки даних. М.: Наука, 1989.

  32. Маміконов А.Г., Кульба В.В., Косяченко С.А. та ін Передпроектний аналіз структури інформаційних потоків і технології обробки даних при розробці модульних СОД. Препринт. К.: Ін-т проблем управління, 1980.

  33. Єфремова В.С., Кошелєва В.А. Основні етапи аналізу систем обробки даних реального масштабу часу / / Всесоюзний семінар по методах синтезу типових модульних СОД (Звенигород, 1985). Тез. Докл.і повідомлень. К.: Ін-т проблем управління, 1985. С. 50.

  34. Косяченко С.А., Сидоров Є.М. Виділення типових задач обробки даних на етапі передпроектного аналізу / / Всесоюзна конференція з автоматизації проектування систем управління. Тез. Докл. М.: ВИНИТИ, 1984. С. 37.

  35. Маміконова А.Г., Кульба В.В., Ашіму А.А. та ін Аналіз інформаційних потоків і побудова канонічної структури бази даних (методичні матеріали та методика). Алма-Ата: КАЗНІІНТІ, 1984.

  36. Маміконова А.Г., Кульба В.В., Косяченко С.А., ужасть І.А. Аналіз предметних облстей користувачів і побудова канонічної структури розподілених баз даних. Препринт. К.: Ін-т проблем управління, 1985.

  37. Маміконов А.Г., Кульба В.В., Лутровскій Ю.П. Аналіз предметної області банків даних та побудова оптимальних структур баз даних з урахуванням вимог до дотоверності інформації. Препрінт.М.: Ін-т проблем управління, 1988.

  38. Бєлов Ю.В., Проценко В.С., Федоров В.В., Хижняк А.А. Індустріальні засоби проектування та оцінки ефективності програмних систем, що працюють у реальному часі / / вирахував. системи та зап. Прийняття рішень. М., 1991. С. 79-100.

  39. Кесс Ю.Ю., Ревека В.М. Типові модулі АСУП. М.: Енергія, 1977.

  40. Маміконов А.Г., Кульба В.В., Косяченко С.А. та ін Аналіз діалогових систем (моделі та методи). Препринт. К.: Ін-т проблем управленія.1986.

  41. Калугін С.Е., Сомов С.К. Упорядкування сценаріїв діалогу користувачів з діалогової системою / / Розробка оптимальних модульних систем обробки даних. К.: Ін-т проблем управління, 1987.С. 24-28.

  42. Маміконов А.Г., Кульба В.В., Кітапбаев Ш.Б., Швецов А.Р. Використання мереж Петрі з різнокольоровими маркерами для аналізу ефективності механізмів захисту даних в базах даних. Препринт. К.: Ін-т проблем управління, 1987.

  43. Кульба В.В., Миронов Д.А., Соколова О.Б. Налагодження систем захисту з використанням мереж Петрі. Препринт. К.: Ін-т проблем управління, 1990.

  44. Маміконов А.Г., Ккульба В.В., Ашіму А.А. Смнтез оптимальних модульних систем обробки даних / / Питання кібернетики. Автоматизація проектування систем обробки даних. М.: Наукова рада з комплексної проблеми «Кібернетика». 1985. С.4-17.

  45. Clemens M., Kaiser KM, Mathony HJ Integration der Module fur den Logiken twurf / / Fortschr. Ber. VDJ. RJ 1987. № 65.S. 99-105.

  • Shafer Hartmut, Meller Klans. Inkrementelle Erweiterung von objektenein Ansatr rur Softwareintegration / / Wiss. Z. Techn. Univ. Karl-Marx-Stadt. Chemitz. 1991. V. 33. № 5. S. 675-685.

  • Floyd Muchael. The evolution of component-based programming / / Dr. Dobb's J. 1991.V. 16. № 1. P. 96S, 96V.

  • Горбунов М.М. Змінні програми і однорідні модулі. Препринт № 202. К.: Ін-т прикладної математики. 1986.

  • Vulinovich Denis. The state transition table / / Autom. And Contr. 1986. V. 17. № 5 P. 16-19.

  • Кулагін В.П. Аналіз і синтез складних структур як перетворення елементів лінійного простору / / Обчислювальна техніка та автоматизованих системах контролю і управління. Пенза: Політехнічний ін-т, 1991. С. 58-65.

  • Smith Brian T. Structured Software design / / 77th Annu. Meet. Techn. Sec. Can. Puep. And Pap. Acsoc. Montreal, 1991. P. 115-120.

  • Лаврищева Є.М., Грищенко В.М. Складальне програмування. Київ: Наук. думка, 1991.

  • Туяхов Л.С., Коваленко В.М. Організація інтерфейсу між модулями в складі ПЗ АСУ / / Доп. 1984. № 2.с. 72-74.

  • Кротюк Ю. М. Постановка і методи розв'язання задач визначення допустимої і оптимальної послідовності пріоритетів при вирішенні задач синтезу оптимальних модульних СОД в системах управління комплексно-автоматизованими ділянками і виробництвами. ЦНІІТУ, 1982. С.87-101.

  • Кротюк Ю.М., Кошелєв В. А. Визначення оптимальної величини блоків обміну між різними рівнями пам'яті в модульних системах обробки даних реального часу / / Аналіз і синтез оптимальних модульних систем обробки даних: М.: Ін-т проблем управління, 1984.C .77-82.

  • Кошелєв В. О. Про одну задачу автоматизації синтезу СОД РВ / / Всесоюз. Коференція з автоматизації проектування систем управління (Евреван, 1984) Тез.докл.М.:.: Ін-т проблем управління, 1984.C.84-86.

  • Кошелев В.А., Мелодії І. Е. Синтез оптимальної модульної СОДРВ для ІАСУ будівництвом тунелів БАМ / / Роль молодих вчених та фахівців у розвитку науково-технічного прогресу на залізничному транспорті. Тез. Докл. галузевої науково-технічної конференціі.М.: Московчскій ін-т залізничного транспорту, 1984.С.73.

  • Доенкін О.Є., Кошелєв В. О. Синтез оптимальних модульних СОД РВ з паралельним обслуговуванням заявок / / Всесоюз. конференція з автоматизації проектування систем планування і управління (Звенигород, 1987) Тез.докл.М.:.: Ін-т проблем управління, 1987.C.46-47.

  • Доенкін О.Є., Кошелєв В. А. Задачі синтезу оптимальної модульної СОД РВ, який використовує мультипроцесорні обслуговування / / Розробка оптимальних модульних систем обробки даних. М.:.: Ін-т проблем управління, 1987.C.37-41.

  • Кошелев В.А., Шарикова М. П. Синтез оптимальних модульних СОД РВ за критерієм максимуму коефіцієнта готовності системи / / Розробка оптимальних модульних систем обробки даних. М.:.: Ін-т проблем управління, 1987.C.41-46.

  • Косяченко С.А., Кошелев В.А., Доенкін О. Є. Синтез оптимальних модульних систем обробки даних, реалізованих на базі однорідних обчислювальних систем обробки даних. М.:.: Ін-т проблем управління, 1989.C22-28.

  • Hoistis Catherine E. Module allocation of real-time applications to distributed systems / / IEEE Trans.Software Eng.1990.V.16. № 7.P.699-709.

  • Гузик В.Ф. , Золотовський В.Є., Туманський С.М., Пухівської В. М. Аналіз продуктивності функціонально розподіленої обчислювальної системи. / / Багатопроцесорні обчислювальні структури. Таганрог, 1990. № 12.С. 11-15.

  • Кальєнте А.А, Сигуров Ю. М. Розподіл завдань в однорідному багатомашинної обчислювальної системі при наявності витрат на міжмашинна обмін / / Мат. Методи і моделі В САПР.Самара: Авіація. Ін-т, 1991.С.11-15.

  • Мамедлі Е.М., Слепченко О.М., Хусідман В.б.Моделі організації диспетчеризації в мнногопроцессорних обчислювальних системах реального часу / / АіТ.1991. № 117-129

  • Денисов С.Г. Турута Є.М. Відновлення обчислювальних процесів у багатопроцесорній системі на основі їх реактівізаціі / / Упр. ресурсами і інтегр мережах. К.: Ін-т проблем передачі інформації, 1991. С. 117-129.

  • Казіев Г.З. Садвакосов Є.С. Структури інформаційного обміну в модульних системах обробки даних / / Тез. Всесоюз.семінара за методом синтезу типових модульних систем обробки даних. К.: Ін-т проблем управління, 1981. с. 49.

  • Казіев Г.З. Садвакосов Є.С. Оптимальне розміщення файлів на зовнішній пам'яті в модульній СОД / / Питання створення АСУТП і АСУП (міжвузівська збірник наукових праць). Алма-Ата: КазПТІ, 1983. с. 16-25.

  • Юрченко В.В. Процедурний і функціональний підхід до опису діалогових систем / / Сб.тр. ВНИИС. М., 1989. № 13. с. 70-80.

  • Алєєв В.Р. Формальна модель діалогу програми з користувачем / / Сб.тр. ВНИИС. М., 1989. № 13. С.65-69.

  • Маміконов А.Г., Кульба В.В., Сомов С.К., Калугін С.Е. Модель синтезу оптимальних модульних діалогових систем / / Автоматизація проектування модульних систем обробки даних. К.: Ін-т проблем управління, 1989.С.5-12.

  • Ємельянов С.В., Ларичев О.І. Багатокритеріальні методи прініятіе рішень. М.: Знання, 1985.

  • Маміконов А.Г., Кульба В.В., Косяченко С.А., Сидоров Є.М. Деякі завдання синтезу типових модульних СОД з урахуванням активної поведінки елементів системи проектування. / / Автоматизація проектування систем обробки даних. К.: Ін-т проблем управління, 1989.С.13-22.

  • Преображенський А.А., Хохлов А.І., Курос Л.В. Завдання аналізу і синтезу типових модулів системи обробки даних / / Тез.докл.Всесоюз.конференции по автомтізаціі проектування систем планування і управління. К.: Ін-т проблем управління, 1987.С.48.

  • Косяченко С.А., Кульба В.В., Маміконов А.Г., ужасть І.А. Моделі та методи проектування розподілених баз даних (огляд) / / АіТ.1989. № 7.С.3-58.

  • Косяченко С.А., Кульба В.В., Маміконов А.Г., ужасть І.А. Оптимізація структур розподілених баз даних в АСУ. М.: Наука, 1990.

  • Голінков Ю.П., Дарко Т.Г., Яструб В.І. Застосування мереж на базі персональних комп'ютерів низовій ланці АСУП / / Аналіз і проектування прогр.обеспеч. і аппарат.средств вичісл.сістем і мереж ЕОМ для ГАП, САПР і АСУ. М.: Моск.ін-т електрон.машіностр., 1991.С.11-14.

  • Прангішвілі І.В. Мікропроцесори і локальні мережі мікро-ЕОМ у розподілених системах управління. М.: Вища школа, 1985.

  • Глушков В.М. та ін Мережі ЕВМ.М.: Наука, 1977.

  • Пєтухова Є.О., Томашевська Т.В. Математична модель синтезу розподіленої бази даних АСУ / / ізв.Ленінгр.електротехн.ін-та.1991. № 438.С.22-25.

  • Гудзенко Н.А., Дрянченко Н.І., Перова В.Б. Система автоматизованого проектування розподіленої бази даних / / Використання мат.методов і ЕОМ в системах управління і проектування. Київ: Ін-т кібернетики, 1991. С.134-144.

  • Казіев Г.З. Блочно-симетричні моделі та методи постановки та вирішення задач дискретного програмування. / / Вісник інженерної академії Республіки Казахстан. № 2 (10). 2003. с. 55-59.

  • Корбут А.А, Фількейнштейн Ю.Ю. Дискретне програмування. - М.: Наука, 1969.

  • Сігал І.Х., Іванова А.П. Введення в прикладне дискретне програмування. М.: Фізматліт, 2002.

  • Малюгін В.Д. Реалізація булевих функцій арифметичними поліномами / / Автоматика і телемеханіка. - 1982. - № 4 .- с.73

  • Дроздов М.О. Алгоритми дискретного програмування. - Тверь.: Наука, 2002.

  • Казіев Г.З. Синтез модульних блок-схем в автоматизованих системах управління / / Автоматика і телемеханіка. 1992. № 11. с. 160-171.

  • Посипкін М.А., Сігал І.Х., Галімьянова М.М. Алгоритми паралельних обчислень для розв'язання деяких класів задач дискретної оптимізації. М.: ВЦ РАН, 2005.

  • Посипкін М.А., Сігал І.Х., Галімьянова М.М. Алгоритми паралельних обчислень для розв'язання деяких класів задач дискретної оптимізації. Повідомлення з прикладної математики. М.: ВЦ РАН, 2005.

  • Сігал І.Х. Параметризація наближених алгоритмів розв'язання деяких класів задач дискретної оптимізації великої розмірності. / / Известия РАН. Теорія і системи управління. 2002. № 6, С. 63-72.

  • Сігал І.Х. Параметризація та дослідження деяких задач дискретного програмування великої розмірності. / / Известия РАН. Теорія і системи управління. 2001. № 2, С. 60-69.

  • Сігал І.Х. Наближені методи та алгоритми в дискретної оптимізації. МГУПС (МІІТ), навчальний посібник, 2000, Москва. 102 с.

  • Сігал І.Х. Алгоритми рішення задач комівояжера великої розмірності. У кн. "Комбінаторні методи та алгоритми розв'язання задач дискретної оптимізації великої розмірності", гл.13. Москва, Наука, 2000, с. 295-317.

  • Сігал І. Х., Іванова О. П. Введення в прикладне дискретне програмування: моделі та обчислювальні алгоритми: 2-е вид., Испр. і доп. - М.: Фізматліт, 2007. - 304 с.

  • Сігал І.Х., (у співавторстві). Комбінаторні методи та алгоритми розв'язання задач дискретної оптимізації великої розмірності: М.: НАУКА, 2000.

  • Меламед І.І., Сігал І.Х. Обчислювальний дослідження трехкрітеріальних завдань про дерева і призначеннях. / / ЖВМ та МФ, 1998, Т.38, № 10, С. 1780-1787.

  • Меламед І.І., Сігал І.Х. Завдання комбінаторної оптимізації з двома і трьома критеріями. / / ДАН, 1999, т.366, № 2, С.170-173.

  • Kuhn HW, T ucher AW Nonlinear Programming / / Proc. Second Berkley Symp. on Math., Stat and Probab. / J. Neyman, Ed. - Berkley: Univ of California Press., 1951. - P. 272-301.

  • Гермейєр Ю.Б. Ігрові принципи в дослідженні систем / / Методи управління великими системами. - Іркутськ: Сиб. енергетич. ін-т СО АН СРСР, 1970. - Т, 1. - С. 4-24.

  • Михалевич BC, Волкович В.Л. Обчислювальні методи дослідження і проектування складних систем. - М.: Наука, 1982. - 287 с.

  • Поспєлов Г.С., Ірік В.А., Курилов А.Є. Процедури та алгоритми формування комплексних програм. - М.: Наука, 1985. - 424 с.

  • Краснощенко А.С., Федоров В.В., Морозов В.В. Декомпозиція в задачах проектування / / Изв. АН СРСР. Технічна кібернетика. - 1979. - № 2. - С. 86-97.

  • Ємельянов С.В., Ларичев О.І. Багатокритеріальні методи прийняття рішень. -М.: Знання, 1985. - 32 с.

  • Мойсеєв М.М. Математичні завдання системного аналізу. - М.: Наука, 1981. - 488 с.

  • Дубов Ю.А., Травкін С.І., Якимця В.М. Багатокритеріальні моделі формування та вибору варіантів систем. - М.: Наука, 1986. - 296 с.

  • Молодцов О.А., Федоров В.В. Стійкість принципів оптимізації / / Сучасний стан теорії дослідження операцій. - М.: Наука, 1979. - С. 236-263.

  • Подіновскій В.В. Парето-оптимальні рішення багатокритеріальних задач. - М.: Наука, 1982. - 256 с.

    1. Сергненко І.В. Математичні моделі і методи розв'язання задач дискретної оптимізації. - Київ: Наукова думка, 1988. - 472 с.

    2. Емелічев В.А., Перепелиця В.О. До обчислювальної складності багатокритеріальних завдань / / Изв. АН СРСР. Техн. кібернетика. - 1988, № 1. - С. 78-85.

    3. Гері М,, Ддонсон Д. Обчислювальні машини і важко вирішити. - М.: Світ, 1982.-416 с.

    4. Ахо А., Xопкрофт Дж., Ульман Дж. Побудова та аналіз обчислювальних алгоритмів. - М.: Світ, 1979. - 536 с.

    5. Пападімітру X., Стайгіц К. Комбінаторна оптимізація. Алгоритми і складність. - М.: Світ, 1985. - 512 с.

    6. Слісенко А.О. Сложностние задачі теорії обчислень / / Успіхи мат. наук. - 1981. - Т. 36, вип. 6 (222). - С. 21-103.

    7. Карапетіян AM Автоматизація оптимального конструювання ЕОМ. - М.: Сов. радіо, 1973.-152 с.

    8. Логічне проектування БІС / Міщенко В.А., гаспид А.І., Вітер В.В и др. - М.: Радіо і зв'язок, 1984. - 322 с.

    9. Меліхов О.М., Берштейн Л.С, Курейчик В.М. Застосування графів для проектування дискретних пристроїв. - М.: Наука, 1974. - 307 с.

    10. В.А. Емелічев, В. А. Перепелиця 20. П е т р е н к о А. І, Основи автоматизованого проектування. - Київ: Техніка, 1982. - 295 с.

    11. Се л ю р і н В. А. Машинне конструювання електронних пристроїв. - М.: Сов. радіо, 1977. - 384 с.

    12. Кристофидес Н. Теорія графів. Алгоритмічний підхід. - М.: Світ, 1978. - 432 с.

    13. Журавльов Ю.І, Дискретне програмування / / матем. енциклопедія. - М.: Сов.енціклопедія, 1979. - Т. 2. - С. 205-206.

    14. Сергієнко І.В., Перепелиця В.О. До проблеми знаходження множин альтернатив у дискретних багатокритеріальних задачах / / Кибернетика. - 1987. - № 5. - С. 85-93.

    15. Емелічев В.А., Перепелиця В.О. Повні задачі багатокритеріальної дискретної оптимізації / / Повідомлення АН ГССР. - 1988. - Т. 131, № 3. - С. 501-504.

    16. Перепелиця В.О. Багатокритеріальні задачі теорії графів. Алгоритмічний підхід: Навчальний посібник. - Київ: УМК ВО, 1989. - 67 с.

    17. Маміконов А.Г., Ашіму А.А., Кульба В.В. Синтез оптимальних функціональних модулів обробки даних в АСУ (препринт). Препринт. - Москва: ІПУ, 1979, с.1-74.

    18. Казіев Г.З., Сиротюк В.О. Формалізовані методи аналізу модульних систем обробки даних. / / Сб. «Питання створення АСУ технологічним процесами і підприємствами», Алма-Ата, КазПТІ, 1980.

    19. Казіев Г.З., Маміконов А.Г., Ашіму А.А., Косяченко С.А. Моделі і методи автоматизації проектування модульних систем обробки даних (стаття). У кн.: Автоматизація проектування систем управління, вип. 3, М.: Фінанси і статистика, 1981, с. 63-79

    20. Казіев Г.З., Маміконов А.Г., Ашіму А.А., Косяченко С.А. Оптимальні модульні системи обробки даних (монографія). Алма-Ата, Наука, КазССР, 1981, с.1-187

    21. Казіев Г.З., Маміконов А.Г., Ашіму А.А., Кульба В.В., Косяченко С.А. Автоматизація проектування оптимальних систем обробки даних (стаття) / / Сб. праць інституту проблем управління, вип.25, М.: Інститут проблем управління, 1981, с.5-15

    22. Казіев Г.З., Сиротюк В.О., Кітапбаев ж.б. Моделі та методи аналізу і синтезу оптимальних структур баз даних у системах паралельної обробки запитів (тези). / / Тези доповідей Всесоюзної школи-семінару «Розпаралелювання обробки інформації», Львів, 1985, с. 114-115.

    23. Казіев Г.З., Горбенко А.С., Касенкова О.А. Діалогова система взаємодії користувачів з базою даних (тези). / / Тези доповідей X Всесоюзного наради з проблем управління. Книга I. ІПУ, М., 1986, с. 444-445.

    24. Казіев Г.З., Полікарпов О.Ю. Про один підхід до аналізу та структуризації проблемної області при розробці діалогових баз даних (тези). / / Тези доповідей IV Всесоюзній конференції «Системи баз даних та знань». Калінін, 1989, с.59-60.

    25. Казіев Г.З. Метод автоматизованого проектування логічних структур баз даних (стаття). / / Сб. праць «Динаміка неоднорідних систем». Вип. 13, ВНИИС. - М., 1990, с.45-52

    26. Казіев Г.З., Кузнєцов М.А., Кульба В.В., Шелков А.Б. Моделі, методи і засоби аналізу і синтезу модульних інформаційно-керуючих систем (стаття). Журнал «Автоматика і телемеханіка», N5, М., 1993, с.3-59.

    27. Казіев Г.З., Айтчанова Ш.К., Мусіна Р.Ж. Блочно-симетричні завдання дискретного програмування (тези). Тези доповідей - 1 З'їзду математиків Казахстан, Шимкент, Гилим, 1996, с. 288-289

    28. Казіев Г.З., Набієва Г.С., Оспанова С.Б. Багатокритеріальні блочно - симетричні завдання дискретного програмування. / / Праці міжнародної науково-практичної конференції «Стан, проблеми та завдання інформатизації в Казахстані», присвяченої до 70-річчя КазНТУ ім.К.І.Сатпаева і 10-річчю Міжнародної Академії Інформатизації (Маїна). - Алмати: РІО, 2004, С. 258-263.

    29. Казіев Г.З., Набієва Г.С. Методи проектування модульного прикладного програмного забезпечення та масивів бази даних в інформаційних системах. / / Спільний випуск наукових журналів «Обчислювальні технології» РАН і «Регіональний вісник Сходу» ВКГУ за підсумками міжнародної конференції «Обчислювальні та інформаційні технології в науці, техніці та освіті», частина VI. - Новосибірськ, Алмати, Усть - Каменогорськ, 2003 р. С. 272-274.

    30. Казіев Г.З. Блочно-симетричні моделі та методи постановки та вирішення задач дискретного програмування. Вісник Інженерної академії РК N2 (10), Алмати, 2003, с. 55-59

    31. Казіев Г.З., Сагімбекова А.О., Набієва Г.С., Оспанова С.Б. Ефективний алгоритм рішення блочно-симетричних завдань / / Вісник КАЗ НТУ імені К.І. Сатпаєва. - Алмати, 3 / 4 (37/38), 2003. С. 310-315.

    32. Казіев Г.З., Набієва Г.С., Шукатаев А. Програмна реалізація багатокритеріальних блочно-симетричних задач дискретного програмування. / / Науковий журнал Міністерства освіти і науки «Пошук», № 4. - Алмати, 2006. с. 191-196.

    33. Туенбаева О.М., Набієва Г.С. Автоматизація додатків / / Тези доповідей наукової конференції магістрантів і аспірантів «Наука і творчість молодих: досвід, проблеми, перспективи»: - Усть-Каменогорськ: ВКГУ; 2001. С. 248-249.

    34. Туенбаева О.М., Набієва Г.С. Чисельне дослідження математичної моделі мереж зв'язку / / Регіональний Вісник ВКГТУ. - Усть-Каменогорськ, 2001р. С. 119-123.

    35. Набієва Г.С. Методи проектування баз даних при заданій множині програмних модулів / / Спільний випуск наукових журналів «Обчислювальні технології» РАН і «Регіональний вісник Сходу» ВКГУ за підсумками міжнародної конференції «Обчислювальні та інформаційні технології в науці, техніці та освіті», частина II. - Новосибірськ, Алмати, Усть - Каменогорськ, 2003 р. С. 270-271.

    36. Набієва Г.С. Берілген деректер базаси кезінде қосимшаларди жобалау әдісі. / / Матеріали Республіканської науково-практичної конференції «Молодь і інформаційні технології». - Актау: КГУТіІ ім.Ш.Есенова, 2009. С. 80-81.

    37. Набієва Г.С., Ескендірова Д.М., Сидибаева М.А. Інформаційна безопосность в сучасних системах управління базами даних. / / Матеріали Республіканської науково-практичної конференції «Молодь і інформаційні технології». - Актау: КГУТіІ ім.Ш.Есенова, 2009. С. 242-249.

    38. Ескендірова Д.М., Набієва Г.С., Тулегенова Б.А. Використання нових технологій у навчальному процесі ВНЗ. / / Збірник матеріалів міжнародної науково-методичної конференції «Актуальні проблеми природничо-наукових дисциплін». - Алмати: КазГАСА, 2010, С.140-142.

    39. Г. С. Набієва. Діскретті программалаудиң модельдері мен әдістерін зерттеу бойинша программалиқ қамтамани өңдеу / / Науковий журнал Міністерства освіти і науки «Пошук», № 3 (1), 2010р. С. 232-238.

    40. Казіев Г.З., Набієва Г.С., Сатмагамбетова Ж.З., Абилхасенова Д.К. Моделі і методи дискретного програмування. Блочно-симетричні моделі - ефективний клас задач дискретного програмування. / / «Вісник КБТУ», № 3, 2010. С.


    Додати в блог або на сайт

    Цей текст може містити помилки.

    Програмування, комп'ютери, інформатика і кібернетика | Дисертація
    486.4кб. | скачати


    Схожі роботи:
    Організація та застосування мікропроцесорних систем обробки даних і управління
    Проектування таблиць для автоматизації обробки економічних даних
    Методи обробки статистичних даних
    Статистичні методи обробки даних
    Методи аналізу та обробки даних
    Технології та методи проектування інформаційних систем
    Моделі систем масового обслуговування Класифікація систем массовог
    Технічні засоби обробки даних
    Системи реєстрації та обробки даних
    © Усі права захищені
    написати до нас