ПРЕДСТАВЛЕНИЕ АЛГОРИТМА.docx

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

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

Примитивы. Для представления алгоритмов необходимо использовать некоторую форму языка. Если с алгоритмом работа- ет человек, то это может быть и традиционный язык (английский, русский, японский), и язык картинок, представленный на рис. 4.2. (На этом рисунке приведен алгоритм изготовления игрушечной птички из квадратного листа бумаги.) Однако зачас- тую использование этих естественных средств общения ведет к неправильному пониманию. Иногда причина состоит в неод- нозначности используемой терминологии. Например, предложение "Посещение внуков – это большая нагрузка на нервную систему" может иметь двоякий смысл: либо приезд внуков вызывает массу хлопот, либо поездка к ним является серьезным испытанием для пожилого человека. Другой источник проблем – это неправильное понимание алгоритма, вызванное недоста- точной детализацией его описания. Мало кто из читателей сможет успешно сделать птичку, пользуясь лишь указаниями, приведенными на рис. 4.2, тогда как для тех, кто уже изучал искусство оригами, это, вероятно, будет несложно. Короче го- воря, проблемы восприятия возникают в тех случаях, когда выбранный для представления алгоритма язык неточно опреде- лен или представленная в описании алгоритма информация недостаточно детальна.

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

В качестве примера на рис. 4.3 представлены некоторые примитивы, используемые в искусстве оригами.

Рис. 4.2. Сложение птицы из квадратного листа бумаги

Рис. 4.3. Примитивы, используемые в оригами

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

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

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

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

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

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

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

Пример псевдокода. Начиная с этого момента, мы отказываемся от использования команд формального языка про- граммирования в пользу менее формальной и более интуитивной системы обозначений, известной как псевдокод.

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

Одна из таких повторяющихся семантических структур – присвоение значения описательному имени. Например, будем использовать для значений такие имена: Температура, СуммарноеКоличествоОсадков, БалансБанка и Положение. Для уста- новления связи между именем и значением будем использовать форму

имя ← выражение

где имя – это описательное имя, а выражение описывает значение, которое присваивается этому имени. Такое утверждение читается как "присвоить имени значение выражения". Например, утверждение

Итог ← Цена + Налог

присваивает результат сложения значений Цена и Налог имени Итог.

Другая повторяющаяся семантическая структура – выбор одного из действий в зависимости от истинности или ложно- сти какого-либо условия.

Примеры:

Если валовой внутренний продукт растет, покупать обыкновенные акции; в противном слу- чае продавать обыкновенные акции.

Покупать обыкновенные акции, если валовой внутренний продукт растет, и продавать их в противном случае.

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

Каждое из этих предложений можно переписать так, чтобы оно соответствовало следующей структуре:

if (условие) then {действие} else {действие}

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

Рассмотрим приведенное ниже предложение.

В зависимости от того, является год високосным или нет, разделить итог на 366 или 365,

соответственно.

Хотя приведенный выше вариант больше отвечает литературному стилю, мы будем использовать следующую его вер-

сию:

if (год високосный) then {разделить итог на 366} else {разделить итог на 365}

Мы также примем сокращенный синтаксис этого конструкта:

if (условие) then {действие}

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

В случае уменьшения объема продаж снизить цену на 5 %.

Применение ее позволяет сократить исходный вариант следующим образом:

if (продажи сократились) then {снизить цену на 5 %}

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

До тех пор, пока есть билеты для продажи, продолжать продавать билеты. Пока есть билеты для продажи, продолжать продажу билетов.

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

while (условие) do {действие}

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

while (имеются билеты, которые можно продать) do {продавать билеты} Использование отступов при размещении текста позволяет повысить читабельность программы: if (товар налогооблагаемый)

then {if (цена > минимум)

then {платить х}

else {платить у}

}

else {платить z}

Эта конструкция воспринимается легче, чем ее эквивалент, приведенный ниже:

if (товар налогооблагаемый) then {if (цена > минимум) then {платить х} else {платить у}} else {платить z}

Поэтому мы договоримся использовать отступы для отражения структуры текста в нашем псевдокоде. (Заметим, что мы даже будем выравнивать скобки, связанные с внешней конструкцией then, чтобы отметить начало и окончание этой струк- туры.)

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

procedure имя

Рис. 4.4. Процедура "Приветствие", записанная на псевдокоде

Когда где-либо в псевдокоде потребуется выполнить действия, реализованные в некоторой процедуре, эта процедура будет просто вызываться по имени. Например, пусть две процедуры имеют имена Предоставление3айма и Отклоне- ниеЗаявки, соответственно. Тогда мы сможем включить их выполнение в структуру if-then-else, написав следующую инструкцию:

if (...)

then {выполнить процедуру Предоставление3айма}

else {выполнить процедуру ОтклонениеЗаявки}

В результате процедура Предоставление3айма будет выполняться, если проверяемое условие истинно, а процедура

Отклонение-Заявки – если это условие ложно.

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

ным параметром.

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

Procedure Сортировка (список)

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

Применить процедуру Сортировка к списку членов организации.

В зависимости от наших потребностей, мы можем применить другой вариант синтаксиса:

Применить процедуру Сортировка к списку гостей на свадьбе.

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

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

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

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

2.     В каком смысле построение процедур является построением примитивов?

3.     Алгоритм Евклида позволяет найти наибольший общий делитель двух положительных целых чисел X и Y с помо- щью следующего процесса:

до тех пор, пока значения X и Y отличны от нуля, выполнять деление большей величины на меньшую и присваивать переменным X и Y значения делителя и остатка, соответственно. (Конечное значение X является наибольшим общим дели- телем.)

Запишите этот алгоритм с помощью нашего псевдокода.

4.     Опишите набор примитивов, используемых не в программировании, а в какой-либо другой области.