Алгоритмы

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

Лри создании алгоритма программы по результатам математи ческого анализа задачи обычно проводят оптимизацию для учетv дополнительных условий, важнейшими из которых являются слr дующие:

технические характеристики ЭВМ (объем ОЗУ, матнитног~~ диска, производительность процессора и т.д.);

имеющиеся в наличии инструменты программирования (транс ляторы или интерпретаторы языков программирования, библиа~ теки стандартных подпрограмм, текстовые редакторы, отладчn кИ, оболочки и т.д.);

степень универсальности программы и соответствующие трс бования к надежности и модифицируемости программы и форл~r диалога с ней.

Эти правила противоречивы, и поиск разумного компромиссv требует разносторонней квалификации специалиста (в крупнi>w vlсреждениях, занимающихся созданием программ, предусмотре~~ целый штат алгоритмистов). Разработан свод правил, облегчакv щих построение эффективных алгоритмов. Например, алгоритn~ должен по иозможности решать именно поставленную задачу, ;~ не серию отдельных задач. Использование циклических, итерацv онных процедур позволяет сократить размер программы, сделаnn ее понятнее при программировании и надежнее при эксплуата ции. Максимально используются тотовые отлаженные и провс ренные блоки и подлрограммы.

Именно при составлении алгоритма следует предусмотретn проверки на соответствие исходных данных и результатов pas личным отраничениям. Например, при вычислениях делитель г{а должен быть близок к нулю, детерминант не должен быть мен~ ше нуля; при программировании операции точения для станка автомата программа должна проверитъ наличие и закрепленност заготовки, установить суппорт в искодное положение; при со здании протокола обмена между управляющей ЭВМ и програv мируемым контроллером еледует разработать удобный и компак тный набор условных кодов, подлежаших передаче по линии cвsv ЗИ, И Т. Д.

Понятие алгоритма было сформировано и широко применяеn ся в математике для описания последовательности действий прn решении задач; оно бьио заимствовано специа,~тистами в обласгn программирования. Алгоритм есть пусть не точная, но понятнаs~ программисту форма постановки задачи, наглядно иллюстрирук~ цtая исходные данные программы, логику решения задачи и трс буемьае результаты. В алгоритме обычно олускаются несуществеv ные или очевидные детали, прорабатываемые на следующем этг~ пе во время программирования по алгоритму.

Степень детализации алгоритма определяется уровнем квалисjw кации потребителя алгоритма. Например, требуется создать про

грамму вычисления среднего арифметического по результатам за­меров. Возможны различнъте формы представления алгоритма рас­чета.

Это, например, могут бътть формулы для вычисления среднего:

Однако эта форма предполагает обычно въiсокую квалифика­цию потребителя алгоритма и примениется в основном в специ­альной литературе.

Для повышения наглядности часто используют блок-схему алгоритма (рис. 3.60). При усложнении алгоритма блок-схемы те­ряют наглядность, поэтому их применяют главным образом для изображения укрупненного алгоритма, которое отражает его логику.

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

Существует два основных подхода к решению этой проблемы. Первым из них является создание и запуск задачи-интерпретато­ра. Интерпретатор принимает из исходной программы по одному оператору языка высокого уровня, расшифровывает содержанис оператора и запускает один из своих модулей, ответственный за выполнение этого оператора. При выполнении операторов интер­претатор общается с ОС: вы,дает системные вызовы, получает от­веты на них, реагирует на сигналы от ОС.

Программа для интерпретатора с языка BASIC, составленнаs~ по рассмотренному выше алгоритму, имеет следующий вид:

Тексты программ, оформленные таким образом, не нуждают­ся в дополнительном описании и блок-схемах, понятны не толь­ко автору, но и его коллегам, что уменьшает число ошибок, по­вышает производительность и качество программирования и сни­жает стоимость программ. Комментарии не учитываются при вы­полнении программы и не влияют на скорость обработки данных.

Особенностью интерпретаторов является независимое выпол­нение отдельных операторов. При выполнении приведенной про­граммы интерпретатор N раз расшифрует операторы ввода Х и сложения чисел и выполнит их, причем основная часть времени

`, уйдет на многократную расшифровку одних и тех же операторов. Интерпретаторы широко используются ввиду простоты их со­здания и малой требовательности к ресурсам ЭВМ. '~'ак ~ервые микроЭВМ вместо громоздкой ОС имели только ~стро~нный в ;, ПЗУ интерпретатор с языка BASIC, вполне удовлетворявший нуж­, ды обычного пользователя. Работа УЧПУ также базируется на по­i следовательной интерпретации команд управляющей программы. Не будет преувеличением утверждать, что основой управления `~ на базе микропроцессоров является именно интерпретация программ. Для решения сложных задач обработки данных, требующих р; много времени работы ЦП, интерпретация неприемлема. Програм­;{ му на языке высокого уровня типа FORTRAN или С подвергают С предварительной переработке - трансляции или компиляции, во ~ время которой выполняется анализ программы как единого цело­~: го, производится ее эквивалентное преобразование с целью со­~` кращения повторов, оптимизации последовательности выполне­~ ния операций и т. д., после чего программа переводится в коды ~ команд процессора. Результатом трансляции является задача, об­~ щающаяся с ОС без посредников, например расчетная задача, или интерпретатор BASIC, или интерпретатор команд ОС.

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

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

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

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