Теория алгоритмов

АЛГОРИТМ

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

Теория алгоритмов

Выяснение того, какие объекты и действия над ними следует считать точно определенными, какими свойствами и возможностями обладают комбинации элементарных действий, что можно и чего нельзя сделать с их помощью‚- все это стало предметом теории алгоритмов и формальных систем, которая первоначально возникла в рамках метаматематики и стала важнейшей ее частью. Главным внутриматематическим приложением теории алгоритмов явились доказательства невозможности алгоритмического (т. е. точного и однозначного) решения некоторых математических проблем. Такие доказательства (да и точные формулировки доказываемых утверждений) неосуществимы без точного понятия алгоритма. Пока техника использовала чисто вычислительные методы, эти высокие проблемы чистой математики ее мало  интересовали. В технику термин «алгоритм» пришел вместе с кибернетикой. Если понятие метода вычисления не нуждалось в пояснениях, то понятие процесса управления  пришлось вырабатывать практически заново. Понадобилось осознавать, каким требованиям должна удовлетворять последовательность действий (или ее описание), чтобы считаться конструктивно заданной, т. е. иметь право называться алгоритмом. В этом осознании огромную помощь инженерной интуиции оказала практика использования вычислительных машин, сделавшая понятие алгоритма ощутимой реальностью. С точки зрения современной практики алгоритм это программа, а критерием алгоритмичности процесса является возможность его запрограммировать. Именно благодаря этой реальности алгоритма, а также потому, что подход инженера к математическим методам всегда был конструктивным, понятие алгоритма в технике за короткий срок стало необычайно популярным (быть может, даже больше, чем в самой математике). Однако у всякой популярности есть свои издержки.  В повседневной практике слово «алгоритм» употребляется слишком широко, теряя зачастую свой точный смысл. Приблизительные описания понятия «алгоритм» час то принимаются за точные определения. В результате за алгоритм зачастую выдается любая инструкция, разбитая на шаги. Появляются такие дикие словосочетания, как  «алгоритм изобретения» (а ведь наличие «алгоритма изобретения» гению означало бы конец изобретательства как творческой деятельности) Ясное представление о том, что такое алгоритм, важно, конечно, не только для правильного словоупотребления. Оно нужно и при разработке конкретных алгоритмов, особенно когда имеется в виду их последующее программирование. Однако оно еще важнее при наведении порядка и в бурно растущем алгоритмическом хозяйстве. Чтобы     ориентироваться в море алгоритмов, захлестнувшем техническую кибернетику, необходимо уметь сравнивать различные алгоритмы решения одних и тех же задач, причем не только по качеству решения, но и по характеристикам самих алгоритмов (числу действий, расходу памяти и т. д.). Такое сравнение невозможно без введения точного языка для обсуждения всех этих вопросов; иначе говоря, сами алгоритмы должны стать такими же предметами точного исследования, как и те объекты, для работы с которыми они предназначены. Строгое исследование основных понятий теории алгоритмов начнется в следующем параграфе. Прежде чем приступить к нему, обсудим на неформальном уровне некоторые основные принципы, по которым строятся алгоритмы, и выясним, что же именно в понятии алгоритма нуждается в уточнении.

Основные требования к алгоритмам.

1. Первое, что следует отметить в любом алгоритме‚- это то, что он применяется к исходным данным и выдает результаты. В привычных технических терминах это означает, что алгоритм имеет входы и выходы. Кроме того, в ходе работы алгоритма появляются промежуточные результаты, которые  используются в дальнейшем. Таким образом, каждый алгоритм имеет дело с данными твходньми, промежуточными и выходными. Поскольку мы собираемся уточнять понятие алгоритма, нужно уточнить и понятие данных, т. е. указать, каким требованиям должны удовлетворять объекты, чтобы алгоритмы могли с ними работать.  Ясно, что эти объекты должны быть четко определены и отличимы как друг от друга, так и от «необъектов». Во многих важных случаях хорошо понятно, что это значит: к таким алгоритмическим объектам относятся числа, векторы, матрицы смежностей графов, формулы. Изображения (например, рисунок графа) представляются менее естественными в качестве алгоритмических объектов. Наконец, с такими объектами, как «хорошая книга» или «осмысленное утверждение», с которыми легко управляется любой человек -(но каждый по-своему!) алгоритм работать откажется, пока они не будут описаны как данные с помощью других, более подходящих объектов.   Вместо того чтобы пытаться дать общее словесное определение четкой определенности объекта, в теории алгоритмов фиксируют конкретные конечные наборы исходных 1 объектов (называемых элементарными) и конечный набор средств построения других объектов из элементарных. Набор элементарных объектов образует конечный алфавит исходных символов (цифр, букв и т. д.), из которых строятся другие объекты; типичным средством построения ч являются индуктивные определения, указывающие, как строить новые объекты из уже построенных. Простейшее индуктивное определение-это определение некоторого множества слов. Слова конечной длины в конечных алфавитах (в частности, числа) - наиболее обычный тип алгоритмических данных, а число символов в слове (длина слова) “естественная единица измерения объема обрабатываемой информации. Более сложный случай алгоритмических объектов - формулы. Они также определяются индуктивно и также являются словами в конечном алфавите, однако не каждое слово в этом алфавите является формулой. В этом случае обычно основным алгоритмам  предшествуют вспомогательные, которые проверяют, удовлетворяют ли исходные данные нужным требованиям.  Такая проверка называется синтаксическим анализом.
2. Данные для своего размещения требуют памяти. Память обычно считается однородной и дискретной, т. е. со- 1; стоит из одинаковых ячеек, причем каждая ячейка может содержать один символ алфавита данных. Таким образом, из  единицы измерения объема данных и памяти согласованы. При этом память может быть бесконечной. Вопрос о том, нужна ли одна память или несколько и, в частности, нужна ли отдельная память для каждого из трех видов данных (входных, выходных и промежуточных), решается поразному.
3.   Алгоритм состоит из отдельных элементарных шагов, или действий, причем множество различных шагов, из которых составлен алгоритм, конечно. Типичный пример множества элементарных действий - система команд ЭВМ. Обычно элементарный шаг имеет дело с фиксированным числом символов (это удобно, например, для измерения времени работы алгоритма числом проделанных шагов), однако это требование не всегда выполняется. Например, в ЭВМ третьего поколения есть команды типа «память - память»‚ работающие с полями памяти переменной длины.
4. Последовательность шагов алгоритма детерминирована, т. е. после каждого шага либо указывается, какой шаг делать дальше, либо дается команда остановки, после чего работа алгоритма считается законченной.
5. Естественно от алгоритма потребовать результативности, т. е. остановки после конечного числа шагов (зависящего от данных) с указанием того, что считать результатом. В частности, всякий, кто предъявляет алгоритм решения некоторой задачи, например вычисления функции fх), обязан показать, что алгоритм останавливается после конечного числа шагов (как говорят, сходится) для любого х из области задания . Cходимость обычно не удается установить простым просмотром описания алгоритма; общего же метода проверки сходимости, при- годного для любого алгоритма А и любых данных  х, , вообще не существует.
6. Следует различать:

 а) описание алгоритма (инструкцию или программу);

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

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

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

Пример.

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

 Возникает естественный  вопрос: что значит «и так далее». Для большей ясности перепишем  описание способа решения в  более четкой форме, разбив его  на шаги и указав переходы  между шагами.

Шаг 1. Ищем в Р наименьшее число.

Шаг 2. Найденное число приписываем, справа к R (в начальный момент R пуста) и вычеркиваем   его из Р.

Шаг З. Если в Р нет чисел, то переходим к шагу 4. В противном случае переходим к шагу 1.

Шаг 4. Конец.

Результатом считать последовательность R, построенную к данному моменту.

Большинство читателей сочтет такое описание достаточно ясным (и даже излишне формальным), чтобы, пользуясь им, однозначно получить нужный результат. Однако это впечатление ясности опирается на некоторые неявные предположения, к правильности которых мы привыкли, но  которые нетрудно нарушить. Например, что значит «дана последовательность чисел»? Является ли таковой последовательность- ( корень второй степени из числа 3;корень пятой степени из числа 2; (1,2)^п) ? Очевидно, да, однако, в нашем описании ничего не сказано, как найти наименьшее число среди таких чисел. В нем вообще не говорится о том, как искать наименьшие числа, по-видимому, предполагается, что речь идет о числах, представленных в виде. А десятичных дробей, и что известно, как. их сравнивать. Итак, необходимо уточнить формы представления данных. При этом нельзя просто заявить, что допустимо любое представление чисел. Ведь для каждого представления существует свой алфавит (который, помимо цифр, может  включать запятые, скобки, знаки операций и функций  и т. д.) и свой способ сравнения чисел (например, способ перевода в десятичную дробь), тогда как конечность алфавита требует фиксировать его заранее, а конечность описания алгоритма позволяет включить в него лишь заранее фиксированное число способов сравнения. Фиксация представления чисел в виде десятичных дробей также не решает всех проблем. Сравнение 10-20-разрядных чисел уже не может считаться элементарным действием: сразу нельзя сказать, какое из чисел больше: 90811557001‚15 или З28999О1467,0048. В машинных алгоритмах само представление числа еще требует дальнейшего уточнения: нужно, во-первых, ограничить число разрядов (цифр) в числе, так как от этого зависит, сколько ячеек памяти будет занимать число, а во-вторых, договориться о способе размещения десятичной запятой в числе, т. е. выбрать представление в виде числа с фиксированной или плавающей запятой, поскольку способы обработки этих двух представлений различны. Наконец, любой, кто имел дело с программированием, отметит, что на шаге 1 требуется узнать две вещи: само наименьшее число (чтобы записать его в R) и его место в Р, т. е. его адрес в той части памяти,  где хранится Р (чтобы вычеркнуть его из Р), а следовательно нужно иметь средства указания этого адреса. Таким образом, даже в этом простом примере несложный анализ показывает, что описанию, которое выглядит вполне ясным, еще далеко до алгоритма. Мы столкнулись здесь с необходимостью уточнить почти все основные характеристики алгоритма, которые отмечались ранее: алфавит данных и форму их представления, память и размещение в ней элементов Р и R, элементарные шаги (поскольку шаг 1 явно не элементарен).Кроме того, становится ясным, что выбор механизма реализации (скажем, человека или ЭВМ) будет влиять и на сам характер уточнения: у человека требования к памяти, представлению данных и к элементарности шагов гораздо более слабые и «укрупненные», отдельные незначительные детали он может уточнить сам. Пожалуй, только два требования к алгоритмам в приcоединенном описании выполнены в достаточной мере (они-то и создают впечатление ясности). Довольно очевидна сходимость алгоритма: после выполнения шагов 1 и 2 либо работа заканчивается, либо из Р вычеркивается одно число; поэтому ровно после n выполнений шагов 1 и 2 из Р будут вычеркнуты все числа и алгоритм остановится, а R будет результатом. Кроме того, не вызывает сомнения детерминированность: после каждого шага ясно, что делать дальше, если учесть, что здесь и в дальнейшем используется общепринятое соглашение -если шаг не содержит указаний о дальнейшем переходе, то выполняем шаг, следующий за ним в описании. Поскольку использованные в примере средства обеспечения детерминированности носят довольно общий характер, остановимся на них несколько подробнее.

Классические методы решения задач

Существуют четыре основных способа решения какой-либо задачи:

1. Применение явной формулы.

2. Использование рекурсивного  определения.

3. Использование алгоритма.

4. Метод перебора, метод  проб и ошибок и др.

 Несомненно, первый способ  является “наилучшим”: мы используем  найденную и доказанную ранее  формулу, которая во всех случаях  дает решение поставленной задачи. К подобному “лобовому” подходу сводится решение таких задач, как определение нулей квадратного уравнения, определение названия дня, соответствующего произвольной дате, определение силы тока в заданной электрической схеме. Собственно задача математики и состоит в том, чтобы найти явные формулы для решения как можно большего числа возможных задач. Если такая формула существует, сложность задачи оказывается связанной с эффективностью вычислений. По определению в формулу может входить только конечное число символов и операций, и это верно для любого числа параметров, включенных в эту формулу, т. е. для любой размерности входной задачи. Следовательно, в этом случае сложность постоянна (не за- висит от п) и равна О(1). Мы предполагаем, что сложность любой операции (т. е. +‚ -‚ -н- и т. д.) не зависит от разряда чисел, над которыми она производится, т. е. сложность пропорциональна числу операций.

Примеры хорошего алгоритма

Пример 1. Подсчитайте сумму п чисел натурального ряда. Вы знаете соответствующую явную‘ формулу, обладающую постоянной сложностью: в ней используется одна операция сложения, одна операция умножения и одна операция деления: ___________________

Пример 2. Провести элементарную сортировку чисел с помощью сравнений

 Классификация задач по степени сложности

Как показывает опыт, любое более или менее близкое знакомство с той или иной областью формирует у каждого из нас “интуитивное представление” о том, что одна задача является “более трудной”, чем другая. Это чисто субъективное понятие не может нас удовлетворить. Однако можем ли мы определить истинную сложность задачи?

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

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

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

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

1. До какого состояния  можно улучшать данный алгоритм? Известны ли для отдельных  случаев методы оптимальной сложности? Каково число задач, которые хорошо  решаются, т. е. задач невысокой степени  сложности (например, п или пд, где п‚- размерность входных данных)?

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

 Три класса задач

Самыми лучшими являются линейные алгоритмы, которые обладают Сложностью порядка (a*b=n) и называются также алгоритмами порядка О(n) (где n-размерность входных данных). Такие алгоритмы реально существуют. Например, подсчет суммы чисел, состоящих из n1 и n2 цифр, способом, с которым все знакомятся в начальной школе, требует подсчета не более n1 + n2 одноразрядных чисел и не более чем max n1,n2          запоминаний. Перемножение двух одноразрядных чисел, прибавление числа и запоминание-все это элементарные операции, которые может выполнить любая машина. Таким образом, данный алгоритм сложения в целом имеет сложность порядка О(n1 +n2); при этом, разумеется, приведенное выражение показывает только порядок величины: постоянные факторы в нем не учитываются (вот почему исчезают подсчеты, связанные с запоминаниями). Другие хорошо известные алгоритмы - деление‚ извлечение квадратного корня, решение уравнений второй степени в результате обобщения этой линейности попадают в первый класс - класс полиномиальных алгоритмов.

Класс _Р: Полиномиальные алгоритмы

В теории алгоритмов классом P называют множество алгоритмов, время работы которых не слишком сильно(полиномиально) зависит от размера входных данных (не превосходит многочлена от размера данных). Алгоритмы, принадлежащие классу P, считаются быстрыми. Класс P включён в более широкие классы сложности алгоритмов. Мы называем “хорошей”, или принадлежащей классу Р, задачу, для которой известен алгоритм, сложность которого составляет полином заданной, постоянной и не зависящей от размерности входной величины n степени.

Класс Е: Экспоненциальные алгоритмы

По природе экспоненциальной считается задача, сложность которой не менее порядка f^n (где f - константа или полином от n), например, в случае, когда число ожидаемых ответов уже само по себе экспоненциально. К этому классу относятся задачи, в которых требуется построить все подмножества некоторого множества, все клики (т. е. полные подграфы) некоторого графа или же все поддеревья некоторого графа. Действительно, можно доказать, что число выходов в этом случае представляется в виде (полином от n). Заметим, что при небольших значениях n, Экспоненциальный алгоритм может быть более быстрым, чем полиномиальный. Однако различие между этими двумя типами задач велико и всегда проявляется при больших значениях n. На практике существуют задачи, которые заранее не могут быть отнесены ни к одному из рассмотренных выше классов (ни к классу Р, ни к классу Е), В их условиях не содержатся экспоненциальные исчисления. Однако для многих из них до сих пор не разработан эффективный (т. е. полиномиальный) алгоритм.