В ы с ш е е п р о ф е с с и о н а л ь н о е о б р а з о в а н и е информатика и программироВание осноВы информатики
Гл а в а 9 основы алгорИтмИзацИИ
жүктеу/скачать 4,7 Mb. Pdf көрінісі
|
| 108
Гл а в а 9 основы алгорИтмИзацИИ 9.1. понятие алгоритма В основу работы ЭВМ положен программный принцип управле- ния, состоящий в том, что ЭВМ выполняет действия по заранее за- данной программе. Программа — это упорядоченная последователь- ность команд, которые понимает ЭВМ. В основе любой программы лежит алгоритм. Алгоритм — это полное и точное описание на некотором языке конечной последова- тельности правил, указывающих исполнителю действия, которые он должен выполнить, чтобы за конечное время перейти от (варьируе- мых) исходных данных к искомому результату. Термин «алгоритм» произошел от имени среднеазиатского учено- го аль-Хорезми (787 — ок. 850), который описал общие правила (на- званные позднее алгоритмами) выполнения основных арифметиче- ских действий в десятичной системе счисления. Эти алгоритмы изу- чаются в начальных разделах школьной математики. К числу алгоритмов школьного курса математики относятся также правила решения определенных видов уравнений или неравенств, правила построения различных геометрических фигур и т. п. Понятие «алго- ритм» используется не только в математике, но и во многих областях человеческой деятельности: например, говорят об алгоритме управ- ления производственным процессом, алгоритме управления полетом ракеты, алгоритме пользования бытовым прибором. Причем интуи- тивно под алгоритмом понимают некоторую систему правил, обла- дающих определенными свойствами. Далее, изучая понятие «алгоритм», мы будем предполагать, что его исполнителем является автоматическое устройство - ЭВМ. Это на- кладывает на запись алгоритма целый ряд обязательных требований. Сформулируем эти требования в виде перечня свойств, которыми должен обладать алгоритм, адресуемый к исполнению на ЭВМ. 1. Первым свойством алгоритма является дискретный (пошаговый) характер определяемого им процесса. Возникающая в результате такого разбиения запись алгоритма представляет собой упорядочен- 109 ную последовательность отдельных предписаний (директив, команд), образующих прерывную/дискретную структуру алгоритма: только выполнив требования одного предписания, можно приступить к ис- полнению следующего. 2. Исполнитель может выполнить алгоритм, если он ему понятен, т.е. записан на понятном ему языке и содержит предписания, которые исполнитель может выполнить. Набор действий, которые могут быть выполнены исполнителем, называется системой команд исполни- теля. Алгоритм не должен содержать описания действий, не входящих в систему команд исполнителя, т. е. своей структурой команд и фор- мой записи алгоритм должен быть ориентирован на конкретного исполнителя. 3. Алгоритмы, предназначенные для исполнения техническим устройством, не должны содержать предписаний, приводящих к не- однозначным действиям. Алгоритм рассчитан на чисто механическое исполнение, и если применять его повторно к одним и тем же ис- ходным данным, то всегда должен получаться один и тот же результат; при этом и промежуточные результаты, полученные после соответ- ствующих шагов алгоритмического процесса, тоже должны быть одинаковыми. Это свойство определенности и однозначности — де- терминированности - алгоритма позволяет использовать в качестве исполнителя специальные машины-автоматы. 4. Основополагающим свойством алгоритма является его массо- вость, применимость к некоторому классу объектов, возможность получения результата при различных исходных данных на некоторой области допустимых значений. Например, исходными данными в алгоритмах аль-Хорезми могут быть любые пары десятичных чисел. Конечно, его способ не всегда самый рациональный по сравнению с известными приемами быстрого счета. Но смысл массовости алгорит- ма состоит как раз в том, что он одинаково пригоден для всех случаев, требует лишь механического выполнения цепочки простых действий и при этом исполнителю нет нужды в затратах творческой энергии. 5. Цель выполнения алгоритма — получение конечного результата посредством выполнения указанных преобразований над исходными данными. В алгоритмах аль-Хорезми исходными данными и резуль- татом являлись числа. Причем при точном исполнении всех пред- писаний алгоритмический процесс должен заканчиваться за конечное число шагов. Это обязательное требование к алгоритмам — требова- ние их результативности или конечности. В математике известны вычислительные процедуры алгоритмиче- ского характера, не обладающие свойством конечности. Например, процедура вычисления числа π. Однако если мы введем условие за- вершения вида «закончить после получения n десятичных знаков числа π», то получим алгоритм вычисления n десятичных знаков числа π. На этом принципе построены многие вычислительные ал- горитмы. 110 6. Если алгоритм должен быть выполнен не просто за конечное время, а за разумное конечное время, то речь идет об эффективности алгоритма. Время выполнения алгоритма — очень важный параметр, однако понятие эффективности алгоритма трактуется шире, включая такие аспекты, как сложность, необходимые ресурсы, информационно- программное обеспечение. Эффективность алгоритма нередко определяет возможность его практической реализации. жүктеу/скачать 4,7 Mb. Достарыңызбен бөлісу:
|