Реферат: Системное автоматизированное проектирование

1. Для отыскания решения требуется экспоненциальное время.

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

Первые результаты о трудно решаемых задачах были получены Тьюрингом. Он доказал, что некоторые задачи “неразрешимы” в том смысле, что вообще не существует алгоритма их решения. Некоторые задачи по теории автоматов, теории формальных языков и математической логики являются трудно решаемыми.

NP-полная задача - это задача, к которой сводится за полиномиальной время любая задача из класса NP-задач. Фундаментальные исследования и теорию NP-задач разработал С.Кук в 1971 году. Им определено понятие сводимости за полиномиальное время. Если одна задача сводится за полиномиальное время к другой, то любой полиномиальный алгоритм - решение другой задачи может быть превращен в полиномиальный алгоритм первой задачи.

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

Существуют 6 основных классов NP-полных задач:

1. Задачи выполнимости.

2. Трехмерное сочетание.

3. Вершинное покрытие.

4. Поиск клики.

5. Гамильтонов цикл.

6. Разбиение.

- внутренние параметры - характеризуют свойства элементов ;

- выходные параметры - характеризуют свойства систем;

- ограничения выходных параметров.

ПРИМЕР 3.

Применительно к операционному усилителю:

а) переменные

- фазовые переменные - напряжение и токи всех ветвей (рассматриваются как функции времени или частоты);

б) параметры

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

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

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

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

Применительно к вычислительной системе:

а) переменные

- фазовые переменные - состояния отдельных устройств;

б) параметры

- внешние параметры - параметры входных источников заявок;