Оглавление:
Главная страница djvu-student.narod.ru
Электрический привод
Математическая логика
Биология
Бжд
История
Психология
Литература
Экономика
Химия
Информатика
Юриспруденция
Высшая математика
Школьная математика
Сопротивление материалов
Теоретическая механика
Теоретические основы электротехники
Физика
Программы, бесплатный софт
Обратная связь
Наша кнопка


Скачать эту страницу
в формате PDF, 177 КБ

Математическая логика, учебник

Учебник, часть 7

АЛГОРИТМЫ И РЕКУРСИВНЫЕ ФУНКЦИИ
Каждый алгоритм имеет входные и выходные данные и состоит из конечного числа инструкций. Например, алгоритм Евклида имеет на входе два положительных числа a и b, на выходе – их наибольший общий делитель. В качестве инструкций можно рассмотреть следующие команды:

1) сравнить a и b;
2) если a равно b, то установить наибольший общий делитель, равным a, и закончить работу;
3) если a > b, то установить a  =  a  –  b и перейти к 1;

если b  >  a, то установить b  =  b  –  a и перейти к 1.

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

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

В данной главе мы будем рассматривать частично рекурсивные функции и функции, значения которых можно вычислить с помощью машин Тьюринга. Эти два класса в действительности совпадают. Чёрч выдвинул гипотезу, что класс частично рекурсивных функций совпадает с классом вычислимых функций. Эта гипотеза называется тезисом Чёрча. Поскольку понятие вычислимой функции точно не определено, то тезис Чёрча доказать нельзя. Мы применим его для доказательства алгоритмической неразрешимости проблемы остановки.

7.1. Частично рекурсивные функции

Под числовыми функциями мы понимаем функции f: Nn  N, где N =  – множество всех натуральных чисел x  0, Nn = {(x1,…,xn): x1N,…,xnN} – его декартова степень. Частичной (числовой) n-местной функцией называется функция f:  D  N, определенная на некотором подмножестве D  Nn декартовой степени. Обозначим D через Dom(f) и будем называть её областью определения частичной функции f. Для частичной n-местной функции f будем применять обозначения f: Nn  N.

Простейшие функции

Функции s: N  N, : N  N и Inm:  Nn  N, принимающие значения s(x)  =  x + 1, (x)  =  0 и Inm(x1,…,xn)  =  xm, для всех x, x1,…,xn    N и n    m    1, называются простейшими. Операции над функциями будут называться операторами.

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

Композиция частичных функций

Частичные функции f: A  B можно определить как функции, заданные на некоторых подмножествах Dom(f)  A и принимающие значения в B. Если Dom(f)  =  A, то f называется определенной всюду. В некоторых случаях частичные функции удобно рассматривать как определенные всюду. С этой целью к каждому множеству добавляется бесконечно удаленная (или отмеченная) точка . Произвольная частичная функция f: A  B расширяется до функции : A  {}  B  {} по формулам (x) = f(x) для x    Dom(f) и по формулам (x) =  для всех остальных x, включая . С другой стороны, каждая функция : A  {}  B  {} определяет частичную функцию g: A  B, принимающую значения g(x)  = (x) для x    -1(B). Ясно, что область Dom(g)  = -1(B) состоит из точек, не отображающихся в бесконечно удаленную. Соответствие, сопоставляющее частичным функциям f функции является взаимно однозначным. Рассматривая частичные функций f как их расширения , легко определить композицию частичных функций f: A  B и g: B  C. Если f и g определены всюду, то композиция совпадает с обычной. В общем случае область определения композиции gf состоит из точек x  A, таких, что g(f(x))  .

Пусть f1,…,fn: Nm  N – частичные функции. Определим частичную функцию (f1,…,fn): Nm  Nn, полагая

(f1,…,fn) (x) = (f1(x),…,fn(x))

для всех x  Dom(f1) …  Dom(fn) Nm.

Пусть f1,…,fn: Nm  N и g: NnN – частичные функции. Оператор суперпозиции (или композиции) Sn+1 сопоставляет им частичную функцию:

Sn+1(g, f1,…,fn) = g  (f1,…,fn).

Областью определения частичной функции g  (f1,…,fn) является подмножество точек x = (x1,…,xm)  Dom(f1) … Dom(fn), для которых (f1(x),…,fn(x))  Dom(g).

Пример 1

Рассмотрим частичные функции g: N2 N, f1: N N, f2: N N, принимающие значения g(x1,x2) = x1 x2, f1(x) = x/2, f2(x) = x/3. Функция f1 определена для четных x; f2 для чисел, кратных 3; g(x1,x2) – для пар чисел x1x2. Следовательно,
Dom(g)  =  {(x1,x2): x1x2}, Dom(f1)  =  {2x:xN} = 2N, Dom(f2)  = 3N. Оператор S3 сопоставляет этим частичным функциям композицию g  (f1,f2): N  N. Область Dom(g  (f1,f2)) состоит из z    6N, удовлетворяющих неравенству z/2    z/3. Поскольку это неравенство выполнено для всех z, то область равна 6N. Если поменять местами f1 и f2, то область определения суперпозиции изменится. Она будет состоять из z    6N, удовлетворяющих z/3    z/2. Следовательно, Dom(S3(g, f2, f1)) = {0}.

Оператор примитивной рекурсии

Пусть заданы частичные функции g: Nn  N и h: Nn+2  N. Оператором примитивной рекурсии называется оператор, сопоставляющий паре (g, h) такую частичную функцию f: Nn+1  N, что для всех x1,…,xn,у    N имеют место равенства:

f(x1,…,xn,0)  =  g(x1,…,xn);

f(x1,…,xn,y+1)  =  h(x1,…,xn,y, f(x1,…,xn,y)).

Поскольку область определения и значения дополняются отмеченной точкой, то равенство частичных функций означает, что для каждого значения аргумента либо левая, либо правая части равенства определены и равны между собой, либо обе его части не определены. Значение оператора примитивной рекурсии обозначается: f  =  R(g,h). Если g и h определены всюду, то f  =  R(g,h) определена всюду.

Если n  =  0, то для любых числа g    N и частичной функции h: N2  N частичная функция f = R(g,h) определяется с помощью равенств:

f(0)  =  g, f(y + 1)  =  h(y,f(y)).


Функция f называется примитивно рекурсивной, если ее можно получить из простейших функций s, o и Inm с помощью операторов суперпозиции и примитивной рекурсии (таким образом, примитивно рекурсивная функция всюду определена.)

Пример 2

Функция оn: Nn  N, все значения которой равны нулю, примитивно рекурсивна, ибо она является композицией о  In1 простейших функций In1: Nn  N и о: N  N. Рассмотрим при k    1 функцию ck: Nn  N, все значения которой равны k. Функция ck равна композиции функций оn: Nn  N и k функций N  N … N, каждая из которых равна s, ck  =  sk on. Стало быть, ck примитивно рекурсивна.

Пример 3

Функция f: N2  N, заданная как f(x,y)  =  x + y, удовлетворяет соотношениям:

f(x,0)  =  x;

f(x,y + 1) =  (x + y) +1  = f(x,y) + 1  = s(f(x,y)).

Положим: g(x)  =  I11(x)  =  x, h(x,y,z)  =  s(z). Так как f(x,0) = g(x) и
f(x,y + 1)  =  h(x,y,f(x,y)), то f  =  R(g,h) = R(I11,s I33). Значит, f – примитивно рекурсивна.

Пример 4

Рассмотрим функцию: f(x,y)  =  xy. Поскольку f(x,0)  =  1, и
f(x,y + 1)  =  xf(x,y)  =  g(x,y,f(x,y)), где g(x,y,z)  =  xz – примитивно рекурсивная функция (как композиция операции умножения и функции (I31, I33): N3  N2), то f(x,y) примитивно рекурсивна.

Пример 5

Пусть (x)  =  max(0,x – 1). Имеют место равенства (0)  =  0 и
(y + 1)  =  y  =  g(y,(y)), где g(y,z)  =  I21(y,z)  = y. Следовательно, (x) – примитивно рекурсивна.

Пример 6

Пусть r(x,y)  =  max(0,x – y). Верны соотношения r(x,0)  =  x и
r(x,y + 1)  =  (r(z,y))  =  g(x,y,r(x,y)), где g(x,y,z)  =  (z) – функция из примера 5. Значит, r(x,y) – примитивно рекурсивна.

Пример 6 показывает, что функция f(x,y)  =x-y= r(x,y)  +  r(y,x) примитивно рекурсивна, как суперпозиция функций x1 + x2 и пары функций (r(x,y),r(y,x)): N2  N2 (примитивная рекурсивность функции r(y,x) получается из разложимости r(y,x)  =  S3(r, I22, I21)).

Оператор минимизации

Пусть g: Nn+1  N – частичная функция. Будем говорить, что частичная функция f: Nn  N получается из неё с помощью оператора минимизации, и писать:

f(x1,…,xn)  =   y [g(x1,…,xn,y)  =  0],

если выполнено следующее условие: f(x1,…,xn) определено и равно y  N тогда и только тогда, когда значение g(x1,…,xn,0),…,g(x1,…,xn,y -1) определены и не равны 0, а g(x1,…,xn,y)  =  0.

Частичная функция f: Nn  N называется частично рекурсивной, если она может быть получена из простейших функций o, s, Inm за конечное число применений операторов суперпозиции, примитивной рекурсии и минимизации.

Пример 7

Рассмотрим примитивно рекурсивную функцию: g(x,y)  =  x – Sg(y), где Sg(y)  =  0, при y  =  0, и Sg(y)  =  1, для y  >  0. Тогда значения:

f(x) =  y[x-Sg(y)=  0]

не определены при x  >  1. Наименьшее среди y    N, удовлетворяющих 0 – Sg(y)  =  0, будет равно 0, а наименьшее среди y, при которых 1 – Sg(y)  = 0, равно 1. Следовательно, f(0)  =  0, f(1)  =  1, и f(x) не определены при x  >  1. Функция x – Sg(y) примитивно рекурсивная, значит, f(x) – частично рекурсивная.

Пусть А – подмножество натуральных чисел. Частичной характеристической функцией множества А называется частичная функция CA: N  N, равная 0 в точках множества А и не определенная вне А. Множество А называется частично рекурсивным, если его частичная характеристическая функция частично рекурсивна. Множество А называется примитивно рекурсивным, если функция N  N, равная 0 на А и равная 1 вне А, является примитивно рекурсивной.

Теорема. Пусть f: N  N – примитивно рекурсивная функция, A   N – примитивно рекурсивное множество. Тогда частичная функция fA: N  N, определенная как fA(x)  =  f(x) для x   A и неопределенная при x   A, является частично рекурсивной.

Доказательство. Легко видеть, что fA(x)  =  f(x) + CA(x). Поэтому fA частично рекурсивна, как сумма частично рекурсивных функций.

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

Тезис Чёрча. Класс алгоритмически (или машинно) вычислимых частичных числовых функций совпадает с классом всех частично рекурсивных функций.

7.2. Машины Тьюринга

Рассмотрим гипотетическую «машину», имеющую конечное множество Q внутренних состояний и одну бесконечную ленту, разделенную на ячейки, по которой перемещается устройство для чтения и записи, именуемое головкой. В каждый из такт времени головка читает содержимое текущей ячейки, затем пишет в эту ячейку новый символ и перемещается влево или вправо, или остается на месте. Текущей ячейкой становится новая ячейка, она будет той, на которую указывает головка. Символы принадлежат конечному алфавиту А.

Пример 1

Алфавит состоит из цифр 0,1,…,9. На ленте написано слово:


2

0

9

3

1


и головка показывает на 9. Тогда в следующий такт времени головка может записать вместо 9 цифру 8 и переместиться влево. После этого она будет показывать на 0.

Перейдем к точным определениям.

Машиной Тьюринга T  =  (A,Q,) называется тройка, состояний из непустых конечных множеств A  =  {a0,a1,…,an}, Q  =  {q0,q1,…,qm} и частичной функции
:  Q  A  Q  A  {L,S,R}.

Здесь {L,S,R} – множество, состоящее из трех элементов. Оно одинаково для всех машин Тьюринга и интерпретируется командами перемещения головки: L – влево, R – вправо, S – стоять на месте.

Множество А называется внешним алфавитом, его элементы – буквами. Буквы a0 и a1 для всех машин Тьюринга одинаковы: a0 = 0, a1 = 1. Элементы q0,…,qm называются внутренними состояниями.

Частичная функция  называется программой и записывается или с помощью прямоугольной таблицы, в которой в клетке (qi,qj) записывается тройка
(qi,qj)    Q  A  {L, S, R}, или с помощью списка команд вида:

  • qiaj  qkae означающей (qk,ae,S) = (qi,aj),

  • qiaj  qkaeR означающей (qk,ae,R) = (qi,aj),

  • qiaj  qkaeL означающей (qk,ae,L) = (qi,aj).

Эти команды обозначим через T(i,j).

Машиным словом, или конфигурацией, называется слово вида: qkae, где
0    k    m, 0    e    n,  и  – слова (возможно, пустые), составленные из букв алфавита А. Для обозначения слова аа…а, в котором буква а повторяется x раз, пишем: ах.

Машинное слово: qkae интерпретируется как положение, при котором головка указывает на символ ae, машина находится во внутреннем состоянии qk, слева от текущей ячейки находятся символы, составляющие слово , а справа – слово . В примере 1 машинное слово равно: 20qi931 для некоторого i.

Пусть задана машина Тьюринга Т и машинное слово M  =  qiaj, где 0    i   m. Обозначим через MT’ слово, которое получается (за один такт) по правилам:

1) для i  =  0 положим MT’ = M;

2) для i  >  0 выполняем одно из следующих трех преобразований:

  • если T(i,j)  =  qiaj  qkae, то MT’ =  qkae;

  • в случае T(i,j)  =  qiaj qkaeR,

если  не пусто, то MT’ =  qkae, иначе MT ’=  qkaea0;

  • в случае T(i,j)  =  qiaj  qkaeL,

если  = 1as для некоторых 1 и as, то MT’ =  1qkasae,

иначе (т.е. если  пусто) MT’= qka0ae (дополнительная инструкция).

Положим: MT0 =  M, MT(n+1) =  (MT(n))’.

Будем говорить, что машина Т перерабатывает машинное слово М в слово М1, если MT(n)  =  M1 для некоторого n    0. Пишем: М  T M1, если Т перерабатывает М в М1, и при этом не используется дополнительная инструкция (из правил образования слова MT’).

Говорим, что машина Т вычисляет частичную функцию f: Nn  N, если выполнены следующие условия:

  • если (x1,…,xn)  Dom(f), то машина Т останавливается, т.е. перерабатывает слово q101x10…1xn0 в некоторое слово q0, и при этом q0 содержит f(x1,…,xn) вхождений символа 1 (здесь символы x1, … , xn обозначены через x1, ..., xn) ;

  • если (x1,…,xn) не принадлежит Dom(f), то машина, начиная со слова
    M  = q101x10…1xn0, работает бесконечно, т.е. q0 не входит в MT(n) ни для каких n    0.

Говорим, что машина Т правильно вычисляет частичную функцию f: Nn  N, если выполнены условия:

  • если (x1,…,xn)  Dom(f), то q101x10…1xn0 Tq001f(x1,…,xn)0…0;

  • в противном случае машина, начиная со слова q101x10…1xn0, работает бесконечно.

Частичная функция f называется (правильно) вычислимой, если существует машина Тьюринга, которая (правильно) вычисляет f.

Пример 2

Пусть машина Тьюринга T  =  {A, Q, }, A  =  {0,1}, Q  =  {q0,q1,q2} задана с помощью таблицы:


q0

q1

q2

0


q20R

q01S

1



q21R

Рассмотрим слово: M  =  q1011…10. На первом шаге выполняется команда q10q20R. Получаем: MT =  0q211…10. Затем, до тех пор, пока слово не превратится в слово 011…1q20, будет выполняться команда q21  q21R. После этого будет выполнена команда q20  q01, и машина остановится, ибо q0 соответствует состоянию остановки. Входное слово, состоящее из x единиц, означает, что аргументом вычисляемой функции является число x. Поскольку на выходе получается x + 1 подряд идущих единиц, то машина вычисляет функцию: s(x)  =  x + 1.

Пример 3

Вычисление функции: s(x)  =  x+1 в примере 2 не является правильным. Построим машину Тьюринга для правильного вычисления:


q0

q1

q2

q3

q4

0


q20R

q31R

q40L

q00L

1



q21R

q41L

q41L

Упражнение

Построить машину Тьюринга, правильно вычисляющую функцию: o(x)  =  0.

Можно построить машины Тьюринга для правильного вычисления функций:

Imn(x1,…,xn), 1   m   n.

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

Теорема 1. Частичная функция правильно вычислима тогда и только тогда, когда она частично рекурсивна.

Тезис Чёрча и алгоритмически неразрешимые проблемы

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

Применим это для доказательства алгоритмической неразрешимости проблемы остановки машины Тьюринга, которая заключается в нахождении алгоритма, определяющего по машине Тьюринга и начальным данным, остановится ли машина через конечное число шагов. Так как машина Тьюринга задается с помощью конечного набора символов и слов, то число машин Тьюринга счетно и может быть выписано в последовательность: T0, T1, … .

Теорема (о проблеме остановки). Пусть T0,T1, T2,… последовательность, перечисляющая все машины Тьюринга, h(n,k) – функция, принимающая значение 1, если машина Tn останавливается, начиная работу с машинного слова q101k0, и принимающая значения h(n,k) = 0 в других случаях. Тогда функция h: N2  N не является частично рекурсивной. Иными словами, нет алгоритма, определяющего, остановится ли машина Тьюринга, если на вход ей подать число k.

Доказательство. От противного. Пусть функция h(n,k) частично рекурсивна. Тогда частичная функция:

f(n)  =  My[h(n,n) + y  =  0]

тоже частично рекурсивна. Существует номер m такой, что f правильно вычисляется с помощью машины Tm. Тогда f(m)  =  0, если и только если h(m,m)  =  0. Согласно определению функции h равенство h(m,m) = 0 имеет место тогда и только тогда, когда машина Tm не останавливается, начиная со слова q101m0. Но f правильно вычисляется с момощью Tm , значит, Tm не остановится, начиная с m, если и только если f(m) не определено. Получаем противоречие: f(m)  =  0, если и только если f(m) не определено, Следовательно, h – не частично рекурсивна.

7.3. Вычислительная сложность

Возможны различные подходы к оценке качества алгоритма, например, оценивается число команд (инструкции), из которых он состоит, число операций, объем используемой памяти. Будем считать, что алгоритм отождествляется с программой, работающей на идеальной ЭВМ, состоящей из процессора, памяти, входной и выходной лент. Ленты и память состоят из ячеек, каждая из которых может хранить двоичную запись одного числа.

Имеется два подхода к оценке времени и памяти, необходимых для выполнения программы: при равномерном весовом критерии считается, что каждая команда программы затрагивает один такт времени, и каждое число занимает одну ячейку памяти. Логарифмический весовой критерий учитывает ограниченность размера реальной ячейки памяти и основывается на предложении, что объем памяти для хранения числа n равен длине его двоичного представления l(n)  =  [log2n] + 1, а время исполнения команды пропорционально длине его операндов.

Временная сложность программы – это функция fmax(n), равная наибольшей из сумм времен, затраченных на каждую выполненную команду при обработке входных данных, состоящих из n чисел. Таким образом, для каждой n-ки (x1,…,xn)  D из области допустимых значений начальных данных (например, области определения частично рекурсивной функции) надо вычислить время t(x1,…,xn), затраченное на выполнение программы. Тогда временная сложность будет равна max{t(x1,…,xn):(x1,…,xn)  D}. Временная сложность в среднем при равномерном критерии равна: , где D – число элементов области D  Nn, а x  =   (x1,…,xn) – элементы из D. Временная сложность в лучшем случае равна: fmin(n)  =  min{t(x):x  D}. Такие же понятия определяются для объема памяти. Вместо времени t(x1,…,xn) рассматривается количество u(x1,…,xn) ячеек памяти, к которым обращалась программа, имеющая на выходе x1,…,xn.

Для описания асимптотического поведения сложностных функций используется следующий формализм: Говорят, что функция f(n) не больше по порядку, чем g(n), и пишут: f(n)  =  O(g(n)), если существует такая константа C  >  0, что почти для всех n (т.е. для всех, кроме конечного множества значений n) справедливо f(n)    Cg(n). Функции одного и того же порядка, если f(n)  =  O(g(n)) и g(n)  =  O(f(n)).

Труднорешаемые и NP-полные задачи

Алгоритм называется полиномиальным (или имеющим полиномиальную временную сложность), если его временная сложность f(n) равна: O(p(n)) для некоторого полинома p(n). Задача называется труднорешаемой, если для ее решения не существует полиномиального алгоритма.

Попытки найти алгоритмы полиномиальной сложности для решения некоторых задач привели к понятию недетерминированной машины Тьюринга для (НДМТ) распознавания свойств, полученной из обычной машины Тьюринга заменой конечного состояния q0 на два заключительных состояния – qY и qN . Машина проверяет, удовлетворяют ли входные данные заданному свойству. Если она заканчивает работу в состоянии qY , то получен ответ «да», если заканчивает в состоянии qN , то получен ответ «нет». Недетерминированная машина Тьюринга, помимо головки чтения/записи имеет дополнительное устройство, которое называется угадывающем модулем. Этот модуль может только записывать на ленту. Угадывающий модуль дает информацию для записи «догадки».

Программа для НДМТ (НДМТ-программа) определяется как и для машины Тьюринга в виде частичной функции : Q x A Q x A x {L,S,R}. Вычисление на НДМТ в отличии от вычисления на машине Тьюринга имеет две различные стадии.

На первой стадии происходит «угадывание». В начальный момент времени входное слово w записывается в ячейках с номерами 1, 2, …, w, головка чтения/записи смотрит на ячейку 0, пишущая головка угадывающего модуля смотрит на ячейку с номером –1. Угадывающий модуль начинает управлять угадывающей головкой, которая делает один шаг в каждый момент времени и либо пишет в находящейся под ней ячейке одну из букв алфавита A и сдвигается влево, либо останавливается. В последнем случае угадывающий модуль заканчивает работу и начинает работать программа .

Начиная с этого момента, вычисление НДМТ-программы осуществляется по тем же правилам, что и вычисление на машине Тьюринга. Вычисление заканчивается тогда, когда управляющее устройство перейдет в одно из заключительных состояний (qY и qN); оно называется принимающим вычислением, если остановка происходит в состоянии qY . Остальные вычисления, в том числе не заканчивающиеся, называются непринимающими.

Любая НДМТ-программа  может иметь бесконечное число возможных вычислений при данном входе w, по одному для каждого слова-догадки из A*. Будем говорить, что НДМТ-программа  принимает w, если по крайней мере одно из ее вычислений, имеющих w на входе, является принимающим. Язык, распознаваемый программой , - это язык L = {w A* :  принимает w}. Временем, требующимся НДМТ-программе  для того, чтобы принять слово w L , называется минимальное число шагов, выполняемых на стадии угадывания и проверки до момента достижения заключительного состояния qY , где минимум берется по всем принимающим вычислениям программы  на входе w. Временной сложностью НДМТ-программы  называется функция T : N+ N+, где N+ = {1, 2, 3, …}, определенная как T (n) = max {{1}{m: существует w L , w = n, такое что время принятия w программой  равно m}}.

Если существует такой полином p(n) , что T (n) p(n) для всех n 1, то НДМТ-программа называется имеющей полиномиальное время работы.

Класс NP – это класс (не обязательно всех) задач распознавания свойств (т.е. задач, решениями которых могут быть либо «да», либо «нет»), которые могут быть решены с помощью НДМТ-программы с полиномиальным временем работы. Большинство практически важных задач, для которых в настоящее время не известны полиномиальные алгоритмы, после переформулировки их в виде задач распознавания свойств, попадают в этот класс.

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


 Вверх...
Заметки:
» Тепловое оборудование, выбор и расчёт мощности
» Электропривод с двигателем постоянного тока приводит в движение лебедку
» Электротехника, решение задач это просто

Обучение за рубежём:
» Учеба в Великобритании
» Образование в Германии
» Образование в США
» Обучение во Франции

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

Hosted by uCoz