ВУЗ:
непрофессионалы, нуждающиеся в детальных инструкциях, сочтут ее неоднозначной. Обратите внимание, что проблема за-
ключается не в том, что неоднозначен лежащий в основе алгоритм, а в том, что, с точки зрения непрофессионалов, он пред-
ставлен недостаточно подробно. Таким образом, неоднозначность скорее присуща представлению алгоритма, а не самому
алгоритму. В следующем разделе мы увидим, как во избежание проблем неоднозначности в представлении алгоритма может
использоваться концепция примитивов.
Требование, утверждающее, что алгоритм должен определять конечный процесс, означает, что выполнение алгоритма
обязательно должно приводить к его завершению. Это требование происходит из теории вычислений, в задачи которой вхо-
дит получение ответа на вопросы типа: "Что является предельным ограничением алгоритмов и машин?". В данном случае
теория вычислений пытается разграничить вопросы, ответы на которые могут быть получены алгоритмическим путем, и вопросы,
ответы на которые лежат за пределами возможностей алгоритмических систем. В этом контексте грань проводится между процес-
сами, которые приводят к конечному результату, и процессами, которые выполняются бесконечно, не приводя к окончательному
результату.
На практике требование конечности определяемого алгоритмом процесса полезно тем, что исключает бесконечные
процессы, которые никогда не приведут к получению каких-либо содержательных результатов. Например, прямое следова-
ние инструкции "Выполнить этот этап еще раз" лишено смысла. Однако в действительности существуют примеры содержа-
тельных приложений, использующих бесконечные процессы, например контроль показателей жизнедеятельности пациента в
больнице или поддержание установленной высоты полета авиалайнера. Можно возразить, что на самом деле в этих прило-
жениях многократно повторяются конечные алгоритмы, каждый из которых доходит до своего завершения, а затем автомати-
чески начинается вновь. Тем не менее, трудно возразить утверждению, что такие аргументы являются лишь попытками остаться
верными ограничительному формальному определению.
Независимо от того, какую точку зрения считать правильной, на практике термин "алгоритм" часто неформально ис-
пользуется по отношению к последовательностям этапов, не обязательно определяющим конечные процессы. Примером
может служить известный нам еще со школьной скамьи алгоритм деления в столбик, который не определяет конечный про-
цесс в случае деления 1 на 3.
Вопросы для самопроверки
1. Охарактеризуйте различия между процессом, алгоритмом и программой.
2. Приведите примеры алгоритмов, с которыми вы знакомы. Действительно ли они являются алгоритмами в строгом смысле
этого слова?
3. Укажите элементы неопределенности в том неформальном определении алгоритма, которое было предложено в начале
этого раздела.
4. Каким пунктам в определении алгоритма не соответствует приведенная ниже последовательность инструкций?
Этап 1. Возьмите монету из вашего кармана и положите ее на стол.
Этап 2. Возвратитесь к этапу 1.
4.2. ПРЕДСТАВЛЕНИЕ АЛГОРИТМА
В этом разделе мы рассмотрим вопросы, относящиеся к представлению алгоритмов. Наша задача – ввести основные по-
нятия примитивов и псевдокода, а также разработать некоторую систему представления для собственного использования.
Примитивы. Для представления алгоритмов необходимо использовать некоторую форму языка. Если с алгоритмом работа-
ет человек, то это может быть и традиционный язык (английский, русский, японский), и язык картинок, представленный на
рис. 4.2. (На этом рисунке приведен алгоритм изготовления игрушечной птички из квадратного листа бумаги.) Однако зачас-
тую использование этих естественных средств общения ведет к неправильному пониманию. Иногда причина состоит в неод-
нозначности используемой терминологии. Например, предложение "Посещение внуков – это большая нагрузка на нервную
систему" может иметь двоякий смысл: либо приезд внуков вызывает массу хлопот, либо поездка к ним является серьезным
испытанием для пожилого человека. Другой источник проблем – это неправильное понимание алгоритма, вызванное недоста-
точной детализацией его описания. Мало кто из читателей сможет успешно сделать птичку, пользуясь лишь указаниями,
приведенными на рис. 4.2, тогда как для тех, кто уже изучал искусство оригами, это, вероятно, будет несложно. Короче го-
воря, проблемы восприятия возникают в тех случаях, когда выбранный для представления алгоритма язык неточно опреде-
лен или представленная в описании алгоритма информация недостаточно детальна.
В компьютерных науках эти проблемы решают путем создания четко определенного набора составных блоков, из
которых могут конструироваться представления алгоритмов. Такие блоки называются примитивами (primiteve). То, что
примитивам даются точные определения, устраняет многие проблемы неоднозначности и одновременно требует одинаково-
го уровня детализации для всех описываемых с их помощью алгоритмов. Набор примитивов вместе с набором правил, уста-
навливающих, как эти примитивы могут комбинироваться для представления более сложных идей, образуют язык програм-
мирования. Каждый примитив состоит из двух частей: синтаксической и семантической. Синтаксис относится к символьно-
му представлению примитива, а семантика – к представляемой концепции, т.е. к значению примитива. Например, синтаксис
слова "воздух" включает шесть соответствующих символов, тогда как семантически – это окружающая нас газовая субстан-
ция.
В качестве примера на рис. 4.3 представлены некоторые примитивы, используемые в искусстве оригами.
Страницы
- « первая
- ‹ предыдущая
- …
- 77
- 78
- 79
- 80
- 81
- …
- следующая ›
- последняя »
