Понятие алгоритма неформально можно определить как последовательность этапов, описывающая способ решения поставленной задачи. Вначале подчеркнем различие между алгоритмом и его представлением, что аналогично различию между сюжетом и книгой. Сюжет абстрактен или концептуален по своей природе, а книга является его физическим представлением. Если книгу перевести на другой язык или опубликовать в другом формате, изменится только представление сюжета, сам по себе сюжет останется прежним.
Точно так же алгоритм является абстракцией и отличается от своего конкретного представления. Существует много способов представления одного и того же алгоритма. Например, алгоритм для перевода показаний температуры по шкале Цель лекциисия в показания по шкале Фаренгейта традиционно представляется в виде алгебраической формулы
F = (9/5)С + 32.
Однако его можно представить и в виде инструкции:
Умножить значение температуры в градусах Цель лекциисия на 9/5. а затем к полученному произведению прибавить 32.
Эту последовательность действий можно представить даже в виде электронной схемы. В каждом случае лежащий в основе алгоритм остается прежним, отличаются только методы его представления.
В контексте обсуждения различий между алгоритмами и их представлениями следует также прояснить различие между двумя другими, связанными с ними понятиями: программами и процессами. Программа является представлением алгоритма. По сути, специалисты в области компьютерных наук используют термин программа по отношению к формальному представлению алгоритма, разработанного для некоторого компьютерного приложения. Ранее мы определили процесс как деятельность, связанную с выполнением программы. Однако следует заметить, что выполнить программу — означает также и выполнить алгоритм, представленный этой программой; поэтому процесс можно эквивалентно определить как деятельность по выполнению алгоритма. Из сказанного можно сделать заключение, что процессы, алгоритмы и программы — это различные, хотя и взаимосвязанные понятия.
Рассмотрим теперь формальное определение алгоритма, приведенное на рис. 1. Требование упорядоченностиэтапов алгоритма указывает, что отдельные этапы алгоритма должны составлять четко определенную структуру в смысле порядка их выполнения. Однако это не означает, что этапы должны выполняться в строгой последовательности: первый, второй и т.д.
Рисунок1 - Определение алгоритма
Например, некоторые алгоритмы, называемые параллельными, содержат больше одной последовательности этапов, каждая из которых разработана так, что может выполняться отдельным процессором многопроцессорной машины. В таких случаях алгоритм в целом не представляет собой единую последовательность этапов, соответствующую сценарию "первый этап, второй этап". Он содержит множество последовательностей, которые разветвляются и вновь объединяются, по мере того как разные процессоры выполняют различные части задачи. Другими примерами могут служить алгоритмы, выполняемые такими электронными схемами, как триггеры, в которых каждый вентиль реализует отдельный этап всего алгоритма. В этом случае этапы упорядочены как причина и следствие, так как действие каждого вентиля распространяется на всю схему.
Теперь рассмотрим требование, по которому алгоритм должен состоять из выполнимыхэтапов. Чтобы оценить важность этого условия, рассмотрим последовательность инструкций.
Этап 1. Составить список всех целых положительных чисел.
Этап 2. Упорядочить этот список в убывающем порядке (от большего значения к меньшему).
Этап 3. Выбрать первое число из отсортированного списка.
Этот набор инструкций не является алгоритмом, так как этапы 1 и 2 выполнить невозможно. Никто не в состоянии составить список всехцелых положительных чисел, и целые положительные числа невозможно упорядочить, начиная с "наибольшего". Для понятия "выполнимый" специалисты в области компьютерных наук используют термин эффективный. Таким образом, если говорится, что данный этап эффективен, то, значит, он осуществим.
Еще одним требованием, налагаемым определением, приведенным на рис. 1, является недвусмысленностьэтапов алгоритма. Это означает, что во время выполнения алгоритма, при любом состоянии процесса, информации должно быть достаточно, чтобы полностью и однозначно определить действия, которые требуется осуществить на каждом его этапе. Другими словами, выполнение любого этапа алгоритма не потребует каких-либо творческих способностей. Наоборот, единственное требование состоит в способности следовать имеющимся инструкциям.
При обсуждении проблемы неоднозначности важно различать алгоритм и его представление. Неоднозначность конкретного представления алгоритма часто не правильно интерпретируется как неоднозначность, присущая самому алгоритму Распространенным примером является степень детализации в описании алгоритма. Для метеорологов инструкция "Перевести показания в градусах Цель лекциисия в эквивалентные им показания по шкале Фаренгейта" будет вполне удовлетворительной, но непрофессионалы, нуждающиеся в детальных инструкциях, сочтут ее неоднозначной. Обратите внимание, что проблема заключается не в том, что неоднозначен лежащий в основе алгоритм, а в том, что с точки зрения непрофессионалов он представлен недостаточно подробно. Таким образом, неоднозначность скорее присуща представлению алгоритма, а не самому алгоритму. В следующем разделе мы увидим, как во избежание проблем неоднозначности в представлении алгоритма может использоваться концепция примитивов.
Требование, утверждающее, что алгоритм должен определять конечный процесс, означает, что выполнение алгоритма обязательно должно приводить к его завершению. Это требование происходит из теории вычислений, в задачи которой входит получение ответа на вопросы типа: "Что является предельным ограничением алгоритмов и машин?". В данном случае теория вычислений пытается разграничить вопросы, ответы на которые могутбыть получены алгоритмическим путем, и вопросы, ответы на которые лежат за пределамивозможностей алгоритмических систем. В этом контексте грань проводится между процессами, которые приводят к конечному результату, и процессами, которые выполняются бесконечно, не приводя к окончательному результату.
На практике требование конечностиопределяемого алгоритмом процесса полезно тем, что исключает бесконечные процессы, которые никогда не приведут к получению каких-либо содержательных результатов. Например, прямое следование инструкции "Выполнить этот этап еще раз" лишено смысла. Однако в действительности существуют примеры содержательных приложений, использующих бесконечные процессы, например контроль показателей жизнедеятельности пациента в больнице или поддержание установленной высоты полета авиалайнера. Можно возразить, что на самом деле в этих приложениях многократно повторяются конечные алгоритмы, каждый из которых доходит до своего завершения, а затем автоматически начинается вновь. Тем не менее трудно возразить утверждению, что такие аргументы являются лишь попытками остаться верными ограничительному формальному определению.
Независимо от того, какую точку зрения считать правильной, на практике термин алгоритм часто неформально используется по отношению к последовательностям этапов, не обязательно определяющим конечные процессы. Примером может служить известный нам еще со школьной скамьи алгоритм деления в столбик, который не определяет конечный процесс в случае деления 1 на 3.
2 Представление алгоритма
В этом разделе мы рассмотрим вопросы, относящиеся к представлению алгоритмов. Наша задача — ввести основные понятия примитивов и псевдокода, а также разработать некоторую систему представления для собственного использования.
Примитивы. Для представления алгоритмов необходимо использовать некоторую форму языка. Если с алгоритмом работает человек, то это может быть и традиционный язык (английский, русский, японский), и язык картинок, представленный на рис. 2. (На этом рисунке приведен алгоритм изготовления игрушечной птички из квадратного листа бумаги.) Однако зачастую использование этих естественных средств общения ведет к неправильному пониманию. Иногда причина состоит в неоднозначности используемой терминологии. Например, предложение “Посещение внуков — это большая нагрузка на нервную систему”может иметь двоякий смысл: либо приезд внуков вызывает массу хлопот, либо поездка к ним является серьезным испытанием для пожилого человека. Другой источник проблем — это неправильное понимание алгоритма, вызванное недостаточной детализацией его описания. Мало кто из вас сможет успешно сделать птичку, пользуясь лишь указаниями, приведенными на рис. 2, тогда как для тех, кто уже изучал искусство оригами, это, вероятно, будет несложно. Короче говоря, проблемы восприятия возникают в тех случаях, когда выбранный для представления алгоритма язык неточно определен или представленная в описании алгоритма информация недостаточно детальна.
В компьютерных науках эти проблемы решают путем создания четко определенного набора составных блоков, из которых могут конструироваться представления алгоритмов. Такие блоки называются примитивами (primiteve). То, что примитивам даются точные определения, устраняет многие проблемы неоднозначности и одновременно требует одинакового уровня детализации для всех описываемых с их помощью алгоритмов. Набор примитивов вместе с набором правил, устанавливающих, как эти примитивы могут комбинироваться для представления более сложных идей, образуют язык программирования.
Рисунок 2 - Сложение птицы из квадратного листа бумаги
Каждый примитив состоит из двух частей: синтаксической и семантической. Синтаксис относится к символьному представлению примитива, а семантика — к представляемой концепции, т.е. к значению примитива. Например, синтаксис слова ”воздух”включает шесть соответствующих символов, тогда как семантически — это окружающая нас газовая субстанция. В качестве примера на рис. 3 представлены некоторые примитивы, используемые в искусстве оригами.
Рисунок 3 - Примитивы, используемые в оригами
Чтобы получить набор примитивов, пригодных для представления выполняемых машиной алгоритмов, мы можем обратиться к отдельным командам, которые эта машина способна выполнять благодаря ее конструкции. Если алгоритм будет описан с подобным уровнем детализации, то, несомненно, это будет программа, пригодная для выполнения машиной. Однако описание алгоритма на таком уровне детализации весьма утомительно, поэтому обычно используется набор примитивов более высокого уровня; каждый из которых является абстрактным инструментом, сконструированным из примитивов более низкого уровня, представляемых машинным языком. В результате будет получен формальный язык программирования, позволяющий описывать алгоритмы на более высоком концептуальном уровне, чем это возможно в собственно машинном языке. Такие языки программирования мы подробно обсудим при изучении темы языки программирования.
Псевдокод. При построении алгоритма человек должен учитывать влияние большого количества связанных идей. Эта задача может выходить за рамки возможностей человеческого разума. Джордж А. Миллер (George A. Miller) в своей статье 1956 года «Психологическое обозрение» (Psychological Review) изложил результаты исследования, которое показало, что человек может манипулировать одновременно только семью элементами. Поэтому разработчику сложных алгоритмов необходимо средство записи частей алгоритма для последующего возвращения к ним.
В 50 и 60-х годах XX века для создания алгоритмов использовались блок-схемы, в которых алгоритм изображается с помощью геометрических фигур, соединенных стрелками. Однако блок-схемы часто становились запутанной паутиной переплетающихся стрелок, что значительно осложняло понимание лежащего в основе алгоритма. Поэтому блок-схемы уступили дорогу другим средствам проектирования алгоритмов. Примером может послужить псевдокод (pseudocode), в соответствии с которым алгоритмы записываются с помощью строго определенных текстовых структур (примитивов) предназначенных для неформального представления идей в процессе разработки алгоритмов.
Один из путей создания псевдокода состоит в простом ослаблении правил того формального языка программирования, на котором требуется записать окончательную версию алгоритма. Этот подход обычно используется, когда целевой язык программирования известен заранее. В подобной ситуации псевдокод, используемый на ранних стадиях разработки программы, может состоять из синтаксических и семантических структур, аналогичных структурам целевого языка программирования, но не столь формализованных.
В заключение стоит отметить, что блок-схемы могут быть полезны, когда целью является изображение алгоритма, а не его построение.
Поиск лучших средств записи все еще продолжается. Позже мы увидим, что сохраняется тенденция использования графики в создании крупных систем программного обеспечения, а псевдокод остается распространенным средством разработки меньших процедурных компонентов системы.
Пример псевдокода. Начиная с этого момента, мы отказываемся от использования команд формального языка программирования в пользу менее формальной и более интуитивной системы обозначений, известной как псевдокод.
Однако наша задача - рассмотреть проблемы разработки и представления алгоритмов, не концентрируя внимание на каком-либо определенном языке программирования. Поэтому выбранный здесь подход к созданию псевдокода состоит в разработке непротиворечивой и краткой системы обозначений для представления повторяющихся семантических структур. В свою очередь, эти структуры станут примитивами, с помощью которых мы попытаемся выразить дальнейшие идеи.
Одна из таких повторяющихся семантических структур — присвоение значения описательному имени. Например, будем использовать для значений такие имена: Температура, СуммарноеКоличествоОсадков, БалансБанка и Положение. Для установления связи между именем и значением будем использовать форму
имя ← выражение
где имя — это описательное имя, а выражение описывает значение, которое присваивается этому имени. Такое утверждение читается как «присвоить имени значение выражения». Например, утверждение
Итог ← Цена + Налог
присваивает результат сложения значений Цена и Налог имени Итог.
Другая повторяющаяся семантическая структура — выбор одного из действий в зависимости от истинности или ложности какого-либо условия. Примеры:
Если валовой внутренний продукт растет, покупать обыкновенные акции; в противном случае продавать обыкновенные акции.
Покупать обыкновенные акции, если валовой внутренний продукт растет, и продавать их в противном случае.
Покупать или продавать обыкновенные акции в зависимости от того, растет или уменьшается валовой внутренний продукт.
Каждое из этих предложений можно переписать так, чтобы оно соответствовало следующей структуре:
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}
Эта конструкция воспринимается легче, чем ее эквивалент, приведенный ниже.
Поэтому мы договоримся использовать отступы для отражения структуры текста в нашем псевдокоде. (Заметим, что мы даже будем выравнивать скобки, связанные с внешней конструкцией then, чтобы отметить начало и окончание этой структуры.)
Мы собираемся использовать наш псевдокод для описания действий, которые могут выступать в роли абстрактных вспомогательных программ в других приложениях. В компьютерных науках такие программные элементы имеют несколько различных названий, а именно: подпрограммы, процедуры, модули и функции (значение каждого из них имеет свой смысловой оттенок). Договоримся применять к нашему псевдокоду термин процедура (procedure), используя его для обозначения заголовка, по которому можно будет распознать данный блок псевдокода. Точнее говоря, мы будем начинать каждый блок псевдокода со следующей инструкции:
procedureимя
Здесь имя — это конкретное название, присвоенное данному блоку. Ниже будут следовать инструкции, определяющие выполняемые в этом блоке действия. Например, на рис. 4 представлен псевдокод процедуры с именем Приветствие, которой трижды печатается сообщение "Привет".
Рисунок 4 - Процедура “Приветствие”, записанная на псевдокоде
Когда где-либо в псевдокоде потребуется выполнить действия, реализованные в некоторой процедуре, эта процедура будет просто вызываться по имени. Например, пусть две процедуры имеют имена Предоставление3айма и ОтклонениеЗаявки соответственно. Тогда мы сможем включить их выполнение в структуру if-then-else, написав следующую инструкцию:
В результате процедура Предоставление3айма будет выполняться, если проверяемое условие истинно, а процедура ОтклонениеЗаявки — если это условие ложно.
Процедура должна быть общей насколько это возможно. Например, процедура для сортировки списка имен должна сортировать любой список, а не какой-то один. То есть она должна быть написана так, чтобы параметры сортируемого списка задавались не в самой процедуре. Вместо этого в представлении процедуры список должен быть представлен формальным параметром.
В нашем псевдокоде мы будем записывать формальные параметры в скобках сразу после имени процедуры. Например, процедура с именем Сортировка, которая сортирует любой список имен, будет начинаться следующей инструкцией
ProcedureСортировка (список)
Если дальше в представлении упоминается сортируемый список, то для него используется имя Список. А когда мы вызываем процедуру Сортировка, мы задаем, какой именно список нужно отсортировать. Для этого можно использовать, например, следующий синтаксис:
Применить процедуру Сортировка к списку членов организации.
В зависимости от наших потребностей, мы можем применить другой вариант синтаксиса:
Применить процедуру Сортировка к списку гостей на свадьбе.
Не забывайте, что назначение нашего псевдокода состоит в предоставлении средств, позволяющих записывать схемы алгоритмов лишь в общих чертах, а не в написании законченных формальных программ. Поэтому мы не связаны запретом использования неформальных фраз, запрашивающих такие действия, детали которых не определены достаточно строго. (Как именно будут разрешены эти детали, не столь уж важно для описания алгоритма, поскольку это касается только свойств языка, на котором будет написана формальная программа.) В то же время, если позже мы обнаружим, что определенная идея повторяется в обсуждаемых нами схемах, то мы примем соответствующий синтаксис для ее представления и этим расширим наш псевдокод.
Контрольные вопросы
1. Дайте определение алгоритма и разъясните смысл входящих в его определение слов?
2. Приведите примеры различного представления одного и того же алгоритма.
3. Назовите основные понятия примитивов и псевдокода.
правильно интерпретируется как неоднозначность, присущая самому алгоритму Распространенным примером является степень детализации в описании алгоритма. Для метеорологов инструкция "Перевести показания в градусах Цель лекциисия в эквивалентные им показания по шкале Фаренгейта" будет вполне удовлетворительной, но непрофессионалы, нуждающиеся в детальных инструкциях, сочтут ее неоднозначной. Обратите внимание, что проблема заключается не в том, что неоднозначен лежащий в основе алгоритм, а в том, что с точки зрения непрофессионалов он представлен недостаточно подробно. Таким образом, неоднозначность скорее присуща представлению алгоритма, а не самому алгоритму. В следующем разделе мы увидим, как во избежание проблем неоднозначности в представлении алгоритма может использоваться концепция примитивов.
набор примитивов более высокого уровня; каждый из которых является абстрактным инструментом, сконструированным из примитивов более низкого уровня, представляемых машинным языком. В результате будет получен формальный язык программирования, позволяющий описывать алгоритмы на более высоком концептуальном уровне, чем это возможно в собственно машинном языке. Такие языки программирования мы подробно обсудим при изучении темы языки программирования.