Предыдущая страница реферата | 1  2  3  4  5  6  7  8  9  10  11 | Следующая страница реферата

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

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

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

Таблица 1.

|Функция |Размерность, ( |
|временной| |
|сложности|10 |20 |30 |40 |50 |60 |
|( |10-5 с |2*10-5 с |3*10-5 с |4*10-5 с |5*10-5 с |6*10-5 с |
|(2 |10-4 с |4*10-4 с |9*10-4 с |16*10-4 с|25*10-4 с|36*10-4 с|
|(3 |10-3 с |8*10-3 с |27*10-3 с|64*10-3 с|125*10-3 |216*10-3 |
| | | | | |с |с |
|(5 |0,1 с |3,2 с |24,3 с |1,7 мин |5,2 мин |13,0 мин |
|2( |0,001 с |1 с |17,9 мин |12,7 дней|35,7 лет |366 |
| | | | | | |столетий |
|3( |0,059 с |58 мин |6,5 лет |3855 |2*108 |1,3* 1013|
| | | | |столетий |столетий |столетий |

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

Таблица 2.
|Быстродействие ЭВМ |
|106 |108 |109 |
|(1 |100*(1 |1000*(1 |
|(2 |10*(2 |31,6*(2 |
|(3 |4,64*(3 |10*(3 |
|(4 |2,5*(4 |3,9*(4 |
|(5 |(5+6,64 |(5+9,97 |
|(6 |(6+4,19 |(6+6,29 |

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

((-задачи

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

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

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

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

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

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

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

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

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

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

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

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

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

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

ПРИМЕР 3.

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

Рекомендуем скачать другие рефераты по теме: доклад по географии, правильный реферат.





Предыдущая страница реферата | 1  2  3  4  5  6  7  8  9  10  11 | Следующая страница реферата