Искусственный интеллект в САПР

КО(НЕ x) = -КО(x).

                                          Приложение

    Задачами в нечисловой форме занимается дискретная математика. Вам должны быть знакомы ее основные понятия и объекты: множества, графы, грамматики и т.п. Сейчас же остановимся на понятии сложности решения задач дискретной математики (а это, как правило, комбинаторные задачи).  

   Алгоритм - эффективная процедура, однозначно приводящая к результату. С точки зрения практики алгоритм - это программа, критерий алгоритмичности процесса - возможность его запрограммировать.

 Требования к  алгоритмам (рассмотрим неформально)  перечислены ниже.

    Алгоритм работает с данными (входными, выходными, промежуточными), он применяется к исходным данным и выдает результаты. Данные - это объекты, которые четко определены и отличимы (как друг от друга, так и от "необъектов"). Нам понятны такие данные, как числа, вектора, матрицы, формулы. Сложнее с рисунком (хотя бы того же графа). Но такие объекты, как "хорошая книга" или "симпатичная девушка" должны быть описаны (переведены) как данные с помощью других, более подходящих объектов. Заметим, что человек легко справляется с этими понятиями.

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

    Алгоритм состоит из отдельных элементарных шагов или действий. Каждый шаг может иметь дело с данными фиксированной длины (это удобно для оценки времени работы алгоритма) или переменной.

    Последовательность шагов детерминирована (после каждого шага указывается, что делать дальше).

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

   Следует различать:

 а) описание  алгоритма (текст программы, например).

 б) механизм  реализации алгоритма (например, ЭВМ).

 в) процесс  реализации алгоритма, т.е. последовательность  шагов. 

 а), б), в) конечны, кроме памяти, которая входит в механизм.

    Для теоретического исследования свойств алгоритмов принято использовать абстрактное устройство, называемое машиной Тьюринга. Различают два типа таких устройств: детерминированная машина Тьюринга (ДТМ) и недетерминированная машина Тьюринга (НДТМ).

   ДТМ умеет выполнять "обычные" операции: +, -, *, /, ИЛИ, ЧИТАТЬ, ПИСАТЬ, ЕСЛИ, ПОВТОРЯТЬ. В конкретный момент времени ДТМ может выполнять только одно действие и находится в строго определенном состоянии. НДТМ имеет кроме операций ДТМ еще операцию ВЫБОР{M}, которая создает столько копий текущего состояния, сколько элементов в множестве М. НДТМ останавливается, когда одна из копий достигнет инструкции КОНЕЦ. Например, задача разрешимости логического выражения Е(q1, q2, q3, ..., qn) может быть решена на НДТМ с помощью следующего простого алгоритма

for (i=1; i<(n+1); i++) {

  qi = ВЫБОР {0, 1};

  };

if ( Е(q1, q2, q3, ..., qn) ) {

  успех; КОНЕЦ;

  }

 else {

  неудача;

  };

 НДТМ позволяет  легко записывать алгоритмы перебора.

   Сложность алгоритма - выраженная в виде функции от размерности входных данных верхняя граница числа шагов, необходимых для получения результата. Сложность алгоритмов принято обозначать как O(f(n)), где n - размерность входных данных например, запись вида O(1) или O(c) говорит о том, что количество шагов алгоритма не зависит от размерности данных и постоянно. Такими алгоритмами являются следующие:

1+2+3+...+n = (n*(n+1))/2 ,

12+22+32...+n2 = (n*(n+1)*(2n+1))/6 .

   Сложность задачи - сложность наилучшего алгоритма, известного для ее решения.

    Самые лучшие - линейные алгоритмы [O(n)] и линейные задачи. Примерами таких задач являются проверка планарности графов, поиск Эйлерова цикла на графе из n ребер.

Задачи класса P имеют полиномиальную сложность. Например:

 сортировка множество  из n чисел - O(n·logn);

 построение покрывающего  дерева минимальной стоимости  - O(n·logn), где n - число ребер графа;

 в) кратчайший  путь на графе из n вершин и m ребер - О(m·n).

 Но таких задач,  к сожалению, мало.

   Задачи класса E - задачи, экспоненциальные по природе: О(fn) - где f - const или полином. В этот класс попадают задачи, для которых число ожидаемых ответов уже само по себе экспоненциально, например: найти все подмножества некоторого множества.

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

   Задачи класса NP (недетерминированные полиномиальные задачи) - задачи, которые можно решить за полиномиальное время на НДТМ.

 Оказывается,  что различные задачи класса  NP на самом деле эквивалентны.

 Определение 1. Задача Q сводится к задаче R тогда и только тогда, когда для всякого решения s задачи R существует функция g(s), которую можно вычислить полиномиально и которая является решением задачи Q.

 Определение 2. Если одновременно задача Q сводится к задаче R, и R сводится к Q, то Q и R - эквивалентны.

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

NP-полная задача - задача, являющаяся NP-сложной и попадающая в класс NP. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

                                                     Литература:  

1. http://www.studfiles.ru
2. http://www.intuit.ru
3. http://ru.wikipedia.org