4.1.4Абстрактная природа алгоритма

Важно подчеркнуть различие между алгоритмом и его представлением, которое аналогично различию между рассказом и книгой. Рассказ по своей природе абстрактен, книга же является его физическим представлением. Если книга переводится на другой язык или переиздается в другом формате, меняется просто представление рассказа, а сам рассказ остается прежним.

Точно так же алгоритм является абстракцией, определяемой его представлениями. Отдельный алгоритм может иметь множество различных представлений. Например, алгоритм преобразования температуры по шкале Цельсия (С) в температуру по шкале Фаренгейта (F) обычно имеет вид алгебраической формулы F = (9/5) С + 32. Но его также можно представить в виде команды: «умножить температуру по шкале Цельсия на 9/-, и прибавить к результату умножения 32» или даже в виде электронной схемы. В каждом случае алгоритм остается прежним, меняется его представление.

Различие между алгоритмом и его представлением является существенным, когда мы пытаемся передать алгоритм. Например, каким должен быть уровень детализации при описании алгоритма. Для метеоролога указания «перевести температуру по шкале Цельсия в температуру по шкале Фаренгейта» может быть достаточно. Но дилетант в этой области, которому требуется более подробное описание, скажет, что эта команда не является однозначной. Однако проблема заключается не в том, что лежащий в основе алгоритм не однозначен, а в том, что представление алгоритма недостаточно подробно. Следовательно, неоднозначность заключается в представлении алгоритма, а не в самом алгоритме. В следующем разделе мы увидим, как для ликвидации проблемы неоднозначности в представлении алгоритма используется понятие примитива.

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

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

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

4.2.1Примитивы

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

ПРЕДСТАВЛЕНИЕ АЛГОРИТМА В ПРОЦЕССЕ ЕГО ПОСТРОЕНИЯ

При построении алгоритма человек должен учитывать влияние большого количества связанных идей. Эта задача может выходить за рамки возможностей человеческого разума. Джордж А. Миллер (George A. Miller) в своей статье 1956 года «Психологическое обозрение» (Psychological Review) изложил результаты исследования, которое показало, что человек может манипулировать одновременно только семью элементами. Поэтому разработчику сложных алгоритмов необходимо средство записи частей алгоритма для последующего возвращения к ним.

В 50 и 60-х годах XX века для создания алгоритмов использовались блок-схемы, в которых алгоритм изображается с помощью геометрических фигур, соединенных стрелками. Однако блок-схемы часто становились запутанной паутиной переплетающихся стрелок, что значительно осложняло понимание лежащего в основе алгоритма. Поэтому блок-схемы уступили дорогу другим средствам проектирования алгоритмов. Примером может послужить псевдокод, который используется в этой книге, в соответствии с которым алгоритмы записываются с помощью строго определенных текстовых структур. Однако блок-схемы могут быть полезны, когда целью является изображение алгоритма, а не его построение. Например, на рис. 4.4 и 4.5 используется представление в виде блок-схемы, чтобы наглядно продемонстрировать алгоритмические структуры, представленные операторами управления.

Поиск лучших средств записи все еще продолжается. В главе 6 мы увидим, что сохраняется тенденция использования графики в создании крупных систем программного обеспечения, а псевдокод остается распространенным средством разработки меньших процедурных компонентов системы.

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

КАК НАЗЫВАТЬ ЭЛЕМЕНТЫ ПРОГРАММЫ

В естественном языке названия элементов часто состоят из нескольких слов, например «стоимость производства прибора» или «предполагаемое время прибытия». Однако когда мы записываем алгоритм в виде программы, такие имена могут осложнить описание алгоритма. Опыт показывает, что лучше присваивать элементу имя, состоящее из неразрывного текста. В течение последних лет использовались разные способы сжатия нескольких слов в одну лексическую единицу для получения имен элементов программы. Один из них состоит в том, чтобы использовать символ подчеркивания для соединения слов, например предполагаемое _время прибытия. При другом способе используются заглавные буквы, чтобы читателю было легче расшифровать имя. Например, можно начинать каждое слово с заглавной буквы ПредполагаемоеВремяПрибытия. Такую технику часто называют паскалевским стилем (Pascal casing), поскольку она была распространена среди тех, кто использовал язык программирования Pascal. Разновидностью формата «паскалевский стиль» является формат «верблюжий стиль» (camel casing), который отличается от паскалевского стиля только тем, что первая буква имени является строчной: ПредполагаемоеВремяПрибытия. Какой формат использовать — это дело вкуса. Каждый примитив состоит из двух компонентов: синтаксиса и семантики. Синтаксис — это символическое представление примитива, а семантика — его значение. Синтаксис слова «воздух» включает в себя шесть символов, а семантика — газообразное вещество, которое окружает планету. Некоторые примитивы, которые используются в оригами, изображены на рис. 4.2.

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