Оператор минимизации - это очевидное обобщение оператора взятия обратной функции. Обобщение довольно глубокое, так как от функции f не требуется, чтобы она была взаимно однозначной (по переменной xn+1 )
Определение. Функции, которые могут быть получены из простейших о(x)=0, s(x)=x+1, Imn (x1,..., xn ) = xm применением конечного числа раз операторов суперпозиции, примитивной рекурсии и минимизации, называются рекурсивными.
Класс рекурсивных функций шире класса примитивно рекурсивных функций хотя бы по тому, что он содержит не только всюду определённые функции. Докажем, например, что функция
= x − y, если x ≥ y < y
f(x,y) не существует, если x
является рекурсивной. Действительно, f(x,y)=min(z| y+z=x), а ранее было установлено, что функция u(x,y)=x+y примитивно рекурсивна.
Рекурсивные функции отражают наше интуитивное представление о функциях, вычислимых некоторым механическим устройством. В частности, они вычислимы на машинах Тьюринга (см. предыдущий параграф). Наоборот, всякая функция, вычислимая на машине Тьюринга является рекурсивной. Мы не будем проверять этот факт, так как это потребовало бы слишком много времени и места. Полное доказательство можно найти, например, в книге А.И.Мальцева "Алгоритмы и рекурсивные функции".
Отметим, что не всякая функция натуральных аргументов является рекурсивной, даже не всякая функция одного аргумента. Существование нерекурсивных функций и является "математической причиной" наличия алгоритмически неразрешимых задач.
В разных разделах математики встречаются алгоритмически неразрешимые задачи, т.е. задачи, для которых нет алгоритма решения, причём нет не потому что его пока не придумали, а потому что он невозможен в принципе. Разумеется, алгоритм надо понимать в смысле машин Тьюринга и рекурсивных функций.
Сформулируем одну из этих задач
Проблема остановки машины Тьюринга. Машина Тьюринга - это объект, определяемый конечным числом параметров. Все частичные отображения одного конечного множества в другое могут быть эффективным образом перенумерованы. Поэтому каждой машине Тьюринга можно присвоить номер (натуральное число). Пусть T(n) машина Тьюринга с номером n. Некоторые машины, начинающие работать на пустой ленте, в конце концов останавливаются, а некоторые работают бесконечно долго. Возникает задача: по натуральному числу n определить, остановится или нет машина Тьюринга T(n) запущенная на пустой ленте. Эта задача
алгоритмически неразрешима. То есть не существует автоматической процедуры, для каждого n решающей, останавливается или нет машина T(n). Это не исключает того, что для какой-либо конкретной машины мы установим, останавливается она или нет. Не существует метода, решающего это сразу для всех машин.
Если дана задача, как найти для ее решения эффективный алгоритм? А если алгоритм найден, как сравнить его с другими алгоритмами, решающими ту же задачу? Как оценить его качество? Вопросы такого рода интересуют и программистов, и тех, кто занимается теоретическим исследованием вычислений.
Для оценки алгоритмов существует много критериев. Чаще всего нас будет интересовать порядок роста необходимых для решения задачи времени и емкости памяти при увеличении входных данных. Нам хотелось бы связать с каждой конкретной задачей некоторое число, называемое ее размером, которое выражало бы меру количества входных данных. Например, размером задачи умножения матриц может быть наибольший размер матриц-сомножителей.
Время, затрачиваемое алгоритмом, как функция размера задачи, называется временной сложностью этого алгоритма. Поведение этой сложности в пределе при увеличении размера задачи называется асимптотической временной сложностью. Аналогично можно определить емкостную сложность и асимптотическую емкостную сложность.
Именно асимптотическая сложность алгоритма определяет в итоге размер задач, которые можно решить этим алгоритмом. Если алгоритм обрабатывает входы размера n за время cÿn2, где c — некоторая постоянная, то говорят, что временная сложность этого алгоритма есть O(n2) (читается "порядка эн квадрат").
Можно было бы подумать, что колоссальный рост скорости вычислений, вызванный появлением нынешнего поколения цифровых вычислительных машин, уменьшит значение эффективных алгоритмов. Однако происходит противоположное. Так как вычислительные машины работают все быстрее и быстрее, и мы можем решать большие по размеру задачи, именно сложность алгоритма определяет то увеличение размера задачи, которое можно достичь с увеличением скорости машины.
Допустим, у нас есть пять алгоритмов A1,A2,…,A5 со следующими временными сложностями:
| Алгоритм | Временная сложность |
| A1 | n |
| A2 | nÿlog(n) |
| A3 | n2 |
| A4 | n3 |
| A5 | 2n |
Здесь временная сложность — это число единиц времени, требуемого для обработки входа размера n. Пусть единицей времени будет одна миллисекунда (1сек=1000 милисекунд). Тогда алгоритм A1 может обработать за одну секунду вход размера 1000, в то время как A5 — вход размера не более 9. В таб. 6.5.1. приведены размеры задач, которые можно решить за одну секунду, одну минуту и один час каждым из этих пяти алгоритмов.
Таблица 6.5.3.
| Алгоритм | Временная сложность | Максимальный размер задачи | ||
| 1 сек | 1 мин | 1 час | ||
| A1 | n | 1000 | 6?104 | 3,6ÿ106 |
| A2 | nÿlog(n) | 140 | 4893 | 2,0ÿ104 |
| A3 | n2 | 31 | 244 | 1897 |
| A4 | n3 | 10 | 39 | 153 |
| A5 | 2n | 9 | 15 | 21 |
Предположим, что следующее поколение вычислительных машин будет в 10 раз быстрее нынешнего. В таб.6.5.2. показано, как возрастут размеры задач, которые мы сможем решить благодаря этому увеличению скорости. Заметим, что для алгоритма A5 десятикратное увеличение скорости увеличивает размер задачи, которую можно решить, только на три единицы (см. последнюю строку в таб.6.5.2.), тогда как для алгоритма A3 размер задачи более чем утраивается.
Таблица 6.5.4.
| Алгоритм | Временная сложность | Максимальный размер задачи | |
| A1 | n | S1 | 10 S1. |
| A2 | nÿlog(n) | S2 | Примерно 10 S2 для больших S2. |
| A3 | n2 | S3 | 3,1б5 S3 |
| A4 | n3 | S4 | 2,155 S4. |
| A5 | 2n | S5 | S5+3,3 |
Вместо эффекта увеличения скорости рассмотрим теперь эффект применения более действенного алгоритма. Вернемся к таб.6.5.1. Если в качестве основы для сравнения взять 1 мин, то, заменяя алгоритм A4 алгоритмом A3, можно решить задачу, в 6 раз большую, а заменяя A4 на A2, можно решить задачу, большую в 125 раз. Эти результаты производят гораздо большее впечатление, чем двукратное улучшение, достигаемое за счет десятикратного увеличения скорости. Если в качестве основы для сравнения взять 1 ч, то различие оказывается еще значительнее. Отсюда мы заключаем, что асимптотическая сложность алгоритма служит важной мерой качественности алгоритма, причем такой мерой, которая обещает стать еще важнее при последующем увеличении скорости вычислений.
Несмотря на то что основное внимание здесь уделяется порядку роста величин, надо понимать, что большой порядок роста сложности алгоритма может иметь меньшую мультипликативную постоянную (постоянная c в определении О(f(x)) ), чем малый порядок роста сложности другого алгоритма. В таком случае алгоритм с быстро растущей сложностью может оказаться предпочтительнее для задач с малым размером — возможно, даже для всех задач, которые нас интересуют. Например, предположим, что временные сложности алгоритмов A1, A2, A3, A4, A5 в действительности равны соответственно 1000n, 100nÿlog(n), 10n2, n3 и 2 . n Тогда A5 будет наилучшим для задач размера 2§n§9, A2 —для задач размера
10§n§58, A1 — при 59§n§1024, а A1— при n>1024.-
1. Ф.А.Новиков. Дискретная математика для программистов./ Санкт-Петербург: Питер, 2001г., 304С.
2. С.В.Судоплатов, Е.В.Овчинникова. Элементы Дискретной математики./ М., ИНФРА-М, Новосибирск, Изд-во НГТУ,
2002г., 208С.
3. Я.М.Ерусалимский. Дискретная математика/ М., «Вузовская книга», 2001г.,279С.
4. А.Ахо, Дж.Хопкрофт, Дж.Ульман. Построение и анализ вычислительных алгоритмов. / М., Мир, 1979г., 536С.
5. В.Н.Нефедов, В.А.Осипова Курс дискретной математики./ М., Изд-во МАИ, 1992г., 264С.