Параллельность и одновременность
Во введении к этому разделу алгоритм был определен как набор, а не как последовательность инструкций. Различие между этими двумя терминами состоит в том, что второй предполагает некоторую упорядоченность инструкций, тогда как первый этого не предполагает. Однако все алгоритмы, которые мы рассматривали до сих пор, в некотором смысле были упорядочены. Например, были пронумерованы шаги, и мы ссылались на нормальный порядок выполнения, который соответствовал этой нумерации. Отсюда возникают вопросы: так ли необходимо было слово набор? Существуют ли алгоритмы, которые выполняются не в заданном порядке? Оба ответа будут утвердительными
Вернемся к алгоритму умножения. Очевидно, что шаги 1 и 2 можно было бы, не влияя на результат работы алгоритма, поменять местами. То же самое справедливо для шагов 4 и 5. В самом деле, почему бы не выполнять шаги 1 и 2 одновременно, т. е. параллельно? ЭВМ, способных выполнять параллельную обработку, на сегодняшний день сравнительно немного, но нет сомнений в том, что они будут очень широко распространены. Поэтому Вы можете, пусть не сию же минуту, но в некоторый момент, столкнуться с необходимостью разработки алгоритмов для прогона на таких машинах.
Следовательно Вы должны быть в состояний определить, какие шаги могут выполняться параллельно, и применить для указания этого некоторый способ записи, подобный Алголу 68, при помощи которого инструкции, выполняемые в произвольном порядке, в частности параллельно, заключаются в скобки и отделяются друг от друга запятыми. Для представления такого типа выполнения в графическом виде группе инструкций, заключенной в скобки, ставится в соответствие одна точка линии (один блок блок-схемы), поскольку для хода выполнения алгоритма не имеет значения, соответствует каждая точка одной или нескольким инструкциям, при условии что порядок выполнения инструкций в такой группе действительно независим.
Как известно, идея параллельной обработки сравнительно нова. Однако эта идея приобретает огромное значение, особенно для тех, кто будет разрабатывать алгоритмы, поскольку разработчики должны будут эффективно применять методы, использующие параллельные процессоры.
Эффективность, универсальность, элегантность. Пусть даны два различных алгоритма, которые выполняют одно и то же задание. Тогда, вероятно, можно решить, какой из них лучше. В этом подразделе мы сформулируем три критерия, на которых может основываться это решение: алгоритм X можно считать лучшим, чем алгоритм Y, если он более эффективный, или более универсальный, или более элегантный.
Указанное решение носит относительный характер, и очевидно, как правило, трудно или вообще невозможно утверждать, что данный алгоритм эффективен в некотором абсолютном смысле. Скорее этот вывод можно сформулировать либо по отношению к другому алгоритму, как это было сделано выше, либо по отношению к конкретным ресурсам (таким как машинное время или память) или к конкретному типу данных (например, некоторые алгоритмы сортировки могут считаться эффективными для обработки совершенно неупорядоченных данных, но для довольно упорядоченных данных более предпочтительным может оказаться какой-либо другой алгоритм). Эта относительность и разнообразие соответствующих критериев могут сделать определение эффективности очень трудным. Например, общеизвестно, что нередко один алгоритм заменяют другим, который работает быстрее, но требует большего объема памяти (компромисс время — память) ; но будет ли быстрый алгоритм эффективнее, особенно если учесть, что задания, требующие большего объема памяти в алгоритмах обслуживания очередей некоторых операционных систем, получают более низкий приоритет прогона?