3. Классификация параметров проектируемых объектов.


В описаниях проектируемых объектов фигурируют переменные и их параметры. Среди переменных выделяют:

- фазовые переменные - характеризуют физическое или информационное состояние объекта.

Параметры разделяют на ряд групп. К их числу можно отнести следующие:

- внешние параметры - характеризуют свойства внешней по отношению к исследуемому объекту Сравнение нескольких полиномиальных и экспоненциальных функций


Таблица 1 позволяет сравнить скорости роста нескольких типичных среды;


Полиномиальные алгоритмы и труднорешаемые задачи


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

полиномиальный алгоритм;

экспоненциальный алгоритм.

Полиномиальный алгоритм (полиномиальной временной сложности) - это алгоритм, временная сложность которого определяется выражением O[p(n)], где p(n) - полиномиальная функция, n - входная длина.

Алгоритм, временная сложность которого не поддается такой оценке называется экспоненциальным.


Таблица 1.


Функция временной

Размерность, n

сложности 10 20 30 40 50 60

n

10-5 с

2*10-5 с

3*10-5 с

4*10-5 с

5*10-5 с

6*10-5 с

n2

10-4 с

4*10-4 с

9*10-4 с

16*10-4 с

25*10-4 с

36*10-4 с

n3

10-3 с

8*10-3 с

27*10-3 с

64*10-3 с

125*10-3 с

216*10-3 с

n5

0,1 с 3,2 с 24,3 с 1,7 мин 5,2 мин 13,0 мин

2n

0,001 с 1 с 17,9 мин 12,7 дней 35,7 лет 366 столетий

3n

0,059 с 58 мин 6,5 лет 3855 столетий

2*108 столетий

1,3* 1013 столетий


Быстродействие ЭВМ 1000000 операций в секунду.


Таблица 2.

Быстродействие ЭВМ

106

108

109

N1

100*N1

1000*N1

N2

10*N2

31,6*N2

N3

4,64*N3

10*N3

N4

2,5*N4

3,9*N4

N5

N5+6,64

N5+9,97

N6

N6+4,19

N6+6,29


полиномиальных и экспоненциальных функций.

Различие между типичных полиномиальными и экспоненциальными алгоритмами проявляется более убедительно, если проанализировать влияние увеличения быстродействия ЭВМ на время работы алгоритма. Таблица 2 показывает, насколько увеличится размер задач, решаемой за 1 час, если быстродействие возрастет в 100 и 1000 раз. Видно, что для функции 2n увеличение скорости вычислений в 1000 раз приводит лишь к тому, что размер задачи, решаемой на ней за 1 час возрастет на 10.

Функция временной

сложности

n2

n2

n2

n2

2n

3n


NP-задачи


Выделено 2 класса трудно решаемости:


Информация о работе «Системное автоматизированное проектирование»
Раздел: Информатика, программирование
Количество знаков с пробелами: 138248
Количество таблиц: 8
Количество изображений: 0

Похожие работы

Скачать
20657
1
7

... литературе как "рабочая станция" (PC). Рис. 3. Структура рабочей станции проектирования электронных систем. Рис. 4. Структура ПО САПР. 4. Иерархические уровни представления электронных устройств Основным методом проектирования с применением САПР является блочно-иерархический метод или метод декомпозиции сложного объекта на подсистемы (блоки, узлы, компоненты). В этом случае ...

Скачать
90127
1
0

... него среде, знакомой ему по версии "AutoCAD 14. Однако более 400 усовершенствований делают работу конструктора существенно удобней и проще. 2. Технология автоматизированного проектирования в системе AutoCAD   2.1 Основы AutoCAD Чертить в системе AutoCAD — значит, формировать на экране дисплея изображение из отдельных графических элементов (примитивов), которые вводятся при помощи ...

Скачать
47390
3
1

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

Скачать
43314
0
4

... являются Лоцман:PLM компании Аскон, PDM STEP Suite, разработанная под НПО "Прикладная логистика", Party Plus компании Лоция-Софт и т.д. Итак, термин САПР (система автоматизации проектирования) подразумевает комплексный подход к разработке изделия и включает совокупность систем CAD/CAM/CAE. Развитие систем геометрического моделирования, анализа и расчета характеристик изделия сопровождается ...

0 комментариев


Наверх