ПОНЯТИЕ АЛГОРИТМА.docx

ПОНЯТИЕ АЛГОРИТМА

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

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

F = (9/5)С + 32.

Однако его можно представить и в виде инструкции: умножить значение температуры в градусах Цельсия на 9/5, а за- тем к полученному произведению прибавить 32.

Эту последовательность действий можно представить даже в виде электронной схемы. В каждом случае лежащий в ос- нове алгоритм остается прежним, отличаются только методы его представления.

В контексте обсуждения различий между алгоритмами и их представлениями следует также прояснить различие между двумя другими, связанными с ними понятиями: программами и процессами. Программа является представлением алгоритма. По сути, специалисты в области компьютерных наук используют термин "программа" по отношению к формальному пред- ставлению алгоритма, разработанного для некоторого компьютерного приложения. В главе 3 мы определили процесс как деятельность, связанную с выполнением программы. Однако следует заметить, что выполнить программу – означает также и выполнить

Рис. 4.1. Определение алгоритма

 

алгоритм, представленный этой программой; поэтому процесс можно эквивалентно определить как деятельность по выпол- нению алгоритма. Из сказанного можно сделать заключение, что процессы, алгоритмы и программы – это различные, хотя и взаимосвязанные понятия.

Рассмотрим теперь формальное определение алгоритма, приведенное на рис. 4.1. Требование упорядоченности этапов алгоритма указывает, что отдельные этапы алгоритма должны составлять четко определенную структуру в смысле порядка их выполнения. Однако это не означает, что этапы должны выполняться в строгой последовательности: первый, второй и т.д. Например, некоторые алгоритмы, называемые параллельными, содержат больше одной последовательности этапов, каждая из которых разработана так, что может выполняться отдельным процессором многопроцессорной машины. В таких случаях алгоритм в целом не представляет собой единую последовательность этапов, соответствующую сценарию "первый этап, второй этап". Он содержит множество последовательностей, которые разветвляются и вновь объединяются, по мере того как разные процессоры выполняют различные части задачи. Другими примерами могут служить алгоритмы, выполняемые таки- ми электронными схемами, как триггеры (см. раздел 1.1), в которых каждый вентиль реализует отдельный этап всего алгоритма. В этом случае этапы упорядочены как причина и следствие, так как действие каждого вентиля распространяется на всю схему.

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

Этап 1. Составить список всех целых положительных чисел.

Этап 2. Упорядочить этот список в убывающем порядке (от большего значения к меньшему).

Этап 3. Выбрать первое число из отсортированного списка.

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

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

При обсуждении проблемы неоднозначности важно различать алгоритм и его представление. Неоднозначность кон- кретного представления алгоритма часто неправильно интерпретируется как неоднозначность, присущая самому алгоритму. Распространенным примером является степень детализации в описании алгоритма. Для метеорологов инструкция "Перевес- ти показания в градусах Цельсия в эквивалентные им показания по шкале Фаренгейта" будет вполне удовлетворительной, но

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

Требование, утверждающее, что алгоритм должен определять конечный процесс, означает, что выполнение алгоритма обязательно должно приводить к его завершению. Это требование происходит из теории вычислений, в задачи которой вхо- дит получение ответа на вопросы типа: "Что является предельным ограничением алгоритмов и машин?". В данном случае теория вычислений пытается разграничить вопросы, ответы на которые могут быть получены алгоритмическим путем, и вопросы, ответы на которые лежат за пределами возможностей алгоритмических систем. В этом контексте грань проводится между процес- сами, которые приводят к конечному результату, и процессами, которые выполняются бесконечно, не приводя к окончательному результату.

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

Независимо от того, какую точку зрения считать правильной, на практике термин "алгоритм" часто неформально ис- пользуется по отношению к последовательностям этапов, не обязательно определяющим конечные процессы. Примером может служить известный нам еще со школьной скамьи алгоритм деления в столбик, который не определяет конечный про- цесс в случае деления 1 на 3.

Вопросы для самопроверки

1.     Охарактеризуйте различия между процессом, алгоритмом и программой.

2.     Приведите примеры алгоритмов, с которыми вы знакомы. Действительно ли они являются алгоритмами в строгом смысле этого слова?

3.    Укажите элементы неопределенности в том неформальном определении алгоритма, которое было предложено в начале этого раздела.

4.    Каким пунктам в определении алгоритма не соответствует приведенная ниже последовательность инструкций?

Этап 1. Возьмите монету из вашего кармана и положите ее на стол.

Этап 2. Возвратитесь к этапу 1.