Исторический обзор

Лекция № 17

ЭЛЕМЕНТЫ ТЕОРИИ АЛГОРИТМОВ

Предмет теории алгоритмов

Теория алгоритмов — это раздел математики, который изучает об­щие свойства алгоритмов. Различают качественную и метрическую теорию алгоритмов.

Основной проблемой качественной теории алгоритмов является проблема построения алгоритма, обладающего заданными свойства­ми. Такую проблему называют алгоритмической.

Метрическая теория алгоритмов исследует алгоритмы с точки зре­ния их сложности. Этот раздел теории алгоритмов известен также как алгоритмическая теория сложности.

Приложения теории алгоритмов имеются практически во всех раз­делах математики, а также во многих прикладных дисциплинах.

Исторический обзор

Первым дошедшим до нас алгоритмом в его интуитивном понимании – конечной последовательности элементарных действий, решающих поставленную задачу, считается предложенный Евклидом в III веке до нашей эры алгоритм нахождения наибольшего общего делителя двух чисел (алгоритм Евклида). Отметим, что в течение длительного времени, вплоть до начала XX века само слово «алгоритм» употреблялось в устойчивом сочетании «алгоритм Евклида». Для описания пошагового решения других математических задач использовалось слово «метод».

Начальной точкой отсчета современной теории алгоритмов можно считать работу немецкого математика Курта Гёделя (1931 год - теорема о неполноте символических логик), в которой было показано, что некоторые математические проблемы не могут быть решены алгоритмами из некоторого класса. Общность результата Геделя связана с тем, совпадает ли использованный им класс алгоритмов с классом всех (в интуитивном смысле) алгоритмов. Эта работа дала толчок к поиску и анализу различных формализаций алгоритма.

Первые фундаментальные работы по теории алгоритмов были опубликованы независимо в 1936 году годы Аланом Тьюрингом, Алоизом Черчем и Эмилем Постом. Предложенные ими машина Тьюринга, машина Поста и лямбда-исчисление Черча были эквивалентными формализмами алгоритма. Сформулированные ими тезисы (Поста и Черча-Тьюринга) постулировали эквивалентность предложенных ими формальных систем и интуитивного понятия алгоритма. Важным развитием этих работ стала формулировка и доказательство алгоритмически неразрешимых проблем.

В 1950-е годы существенный вклад в теории алгоритмов внесли работы Колмогорова и Маркова. К 1960-70-ым годам оформились следующие направления в теории алгоритмов:

- Классическая теории алгоритмов ( формулировка задач в терминах формальных языков, понятие задачи разрешения, введение сложностных классов, формулировка в 1965 году Эдмондсом проблемы P=NP, открытие класса NP-полных задач и его исследование);

- Теория асимптотического анализа алгоритмов (понятие сложности и трудоёмкости алгоритма, критерии оценки алгоритмов, методы получения асимптотических оценок, в частности для рекурсивных алгоритмов, асимптотический анализ трудоемкости или времени выполнения), в развитие которой внесли существенный вклад Кнут, Ахо, Хопкрофт, Ульман, Карп;

- Теория практического анализа вычислительных алгоритмов (получение явных функции трудоёмкости, интервальный анализ функций, практические критерии качества алгоритмов, методика выбора рациональных алгоритмов), основополагающей работой в этом направлении, очевидно, следует считать фундаментальный труд Д. Кнута «Искусство программирования для ЭВМ».

Интуитивное (наивное) определение алгоритма. Алгоритм - это совокупность правил, обладающих свойствами:

- массовости – инвариантность относительно входной информации;

- детерминированности – однозначность применения этих правил на каждом шаге;

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

- элементарности – отсутствует необходимость дальнейшего уточнения правил;

Интуитивное понятие алгоритма

Слово алгоритм происходит от имени узбекского математика и ас­тронома, жившего в IX веке, Мухаммеда бен Мусы аль-Хорезми, кото­рый впервые разработал правила выполнения арифметических опера­ций в позиционной системе счисления. Затем понятие алгоритма стало использоваться в более широком смысле и не только в математике. Как для математиков, так и для практиков понятие алгоритма имеет чрез­вычайно важное значение.

Понятие алгоритм часто интерпретируют как точное предписание, определяющее вычислительный процесс, начинающийся с произволь­ного исходного данного и направленный на получение результата, пол­ностью соответствующего этому исходному данному. Такое определе­ние алгоритма не является строгим с математической точки зрения, так как в нем используются такие понятия, как «точное предписание» и «произвольные исходные данные», которые не определены строго. Приведенное выше определение алгоритма называют интуитивным.

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

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

Для решения этой проблемы было введено понятие вычислимой функции.

Пусть имеется некоторый алгоритм α. Областью применимости алгоритма α называют совокупность тех объектов, к которым он применим.

Говорят, что алгоритм α вычисляет функцию f, если его область применимости совпадает с областью определения функции f, и алго­ритм α перерабатывает всякий элемент х из своей области примени­мости в f(х).

Функция f(х) называется вычислимой, если существует вычисляю­щий ее алгоритм.

Данное определение функции также не является строгим. Амери­канскими математиками Клини, а впоследствии Чёрчем были строго определены математические функции, названные примитивно-рекур­сивными. Чёрч высказал гипотезу о том, что множество всех рекурсив­ных функций совпадает с множеством всех вычислимых функций. Это предположение получило название тезиса Чёрча. Гипотеза Чёрча не может быть доказана, поскольку использует нестрогое понятие вы­числимой функции.

Позже американские математики Пост и впоследствии Тьюринг ввели понятие математической машины, которую называют машиной Поста или машиной Тьюринга. Это абстрактная машина, которая «ме­ханически» выполняет вычисления. Тьюринг высказал гипотезу (из­вестную также как тезис Тьюринга) о том, что для всякой вычислимой функции может быть построена машина Тьюринга. Этот тезис также не может быть доказан, так как включает нестрогое понятие вычисли­мой функции. Доказано, что для всякой рекурсивной функции может быть по­строена машина Тьюринга и, обратно, всякая машина Тьюринга вы­числяет рекурсивную функцию.

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

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

Примитивно-рекурсивные функции

Дадим элементарное представление о рекурсивных функциях.

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

Прежде всего определяют так называемые простейшие, или эле­ментарные рекурсивные функции.

Элементарными называют следующие функции:

1. Функцию следования

s'(x) = х+1.

2. Функцию константы (чаще всего это нуль)

0"(х₁, …, х_п) = 0.

3. Тождественную функцию

Для построения более сложных функций используют различные операции. Важнейшие из них — это операции суперпозиции и при­митивной рекурсии.

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

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

.

Рассмотрим операцию примитивной рекурсии. Эта операция стро­ит функцию от п + 1 аргументов, если имеется две функции: функция и функция (функция от (n + 2) аргументов). Таким образом, если требуется построить функцию от неко­торого числа аргументов, необходимо иметь две функции: одна из них g зависит от числа аргументов, которое на единицу меньше, чем число аргументов в строящейся функции f, а вторая функция h зависит от числа аргументов на единицу большего числа аргументов функции f.

Операция примитивной рекурсии определяется следующим об­разом:

.

В развернутом виде имеем, когда у = 0:

Если у = 1, то .

Если у = 2, то и так далее.

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

Функция называется примитивно-рекурсивной, если она может быть записана с помощью элементарных рекурсивных функций с использо­ванием конечного числа операций суперпозиции и примитивной ре­курсии.

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

Пример 1. Доказать, что функция f(х, у) = х + у является прими­тивно-рекурсивной.

Решение.

Так как заданная функция f(х, у) есть функция двух аргументов, то для использования операции примитивной рекурсии мы должны иметь функцию g, зависящую от одного аргумента, и функцию h, за­висящую от трех аргументов. Определим их.

В функции f(х, у) = х + у положим у = 0. Тогда имеем fix, 0) = х это тождественная функция. Полагая у= 1, получим fix, 1) = х + 1 — это функция следования.

Таким образом, выбираем следующие элементарные функции: то­ждественную g(x) =х и функцию следования h(x, у, z) = z + 1. Заме­тим, что здесь h(x,y,z) = I] (x,y,s'(x)).

Дата добавления: 2015-07-07