2. Декомпозиция

Принцип декомпозиции (децентрализации) состоит в разбиении системы на подсистемы обладающие требуемыми свойствами.

Рассмотрим некоторые наиболее часто применяемые стратегии декомпозиции.

Функциональная декомпозиция базируется на анализе функций системы.

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

Декомпозиция по жизненному циклу. Признак выделения подсистем -

изменение закона функционирования подсистем на разных этапах цикла существования системы «от рождения до гибели».

Декомпозиция по физическому процессу. Признак выделения подсистем - шаги выполнения алгоритма функционирования подсистемы, стадии смены состояний.

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

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

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

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

Процесс корректировки указаний и предложений повторяется до полного согласования.

Математическое исследование описанного процесса получило развитие в методах Данцига-Вульфа и Корнаи-Липтака.

Декомпазиционный метод Данцига-Вульфа был разработан Дж. Данцигом и Ф. Вульфом (США) в 1960 г. В этом методе центр спускает информацию в виде цен, а получает них в виде предполагаемых объемах затрат и выпусков.

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

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

3. Агрегация

Является одним из методов синтеза сложных систем, т.е. процесса построения отдельных подсистем с известными характеристиками. Таким образом агрегация может рассматриваться как противоположность декомпозиции.

Пример. Управляющее устройство УУ получает от системы высшего уровня некоторое количество ресурсов A,B,…,P и распределяет их между объектами управления  ,

З десь

- ресурс объекта  ,

- продукция объекта  .

Задача состоит в определении таких значений  переменных , , которые максимизируют суммарный выход

при соблюдении условий

;  ; …

,  , …

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

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

9. Классификация вычислительных задач по степени сложности. Классы сложности задач P и NP. NP сложные и NP трудные задачи

   1. По книге Системы искусственного интеллекта

2. По интернетам

   1. Классы задач в зависимости от их трудности

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

2. Труднорешаемые задачи (вероятно, сложные задачи). Это задачи, для решения которых, по-видимому, не существует полиномиального алгоритма. Иными словами, для их решения, скорее всего, существуют только экспоненциальные алгоритмы.

3. NP-задачи (NP — аббревиатура для «недетерминированные полиномиальные»). Это класс задач, которые мы можем решить за полиномиальное время, если угадаем, какой путь вычислений необходимо выполнить. Грубо говоря, этот класс включает в себя все задачи, которые имеют экспоненциальный алгоритм, но не доказано, что они не могут иметь полиномиального алгоритма.

4. Р-задачи (Р — аббревиатура для «полиномиальный»). Этот класс включает в себя задачи, которые имеют полиномиальные алгоритмы. Большинство людей считают, что этот класс является собственным подклассом класса 3.

3. По википедии

   1. Классы сложности

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

2. Класс P

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

3. Класс NP

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