В ы с ш е е п р о ф е с с и о н а л ь н о е о б р а з о в а н и е информатика и программироВание осноВы информатики


Гл а в а   9 основы  алгорИтмИзацИИ



Pdf көрінісі
бет76/196
Дата09.01.2022
өлшемі4,7 Mb.
#23908
түріУчебник
1   ...   72   73   74   75   76   77   78   79   ...   196
Байланысты:
1 Основы информатики

108
Гл а в а   9
основы  алгорИтмИзацИИ
9.1. понятие алгоритма
В основу работы ЭВМ положен программный принцип управле-
ния, состоящий в том, что ЭВМ выполняет действия по заранее за-
данной программе.
Программа — это упорядоченная последователь-
ность команд, которые понимает ЭВМ.
В  основе  любой  программы  лежит  алгоритм.
Алгоритм  —  это
полное и точное описание на некотором языке конечной последова-
тельности правил, указывающих исполнителю действия, которые он
должен выполнить, чтобы за конечное время перейти от (варьируе-
мых) исходных данных к искомому результату.
Термин «алгоритм» произошел от имени среднеазиатского учено-
го аль-Хорезми (787 — ок. 850), который описал общие правила (на-
званные позднее алгоритмами) выполнения основных арифметиче-
ских действий в десятичной системе счисления. Эти алгоритмы изу-
чаются  в  начальных  разделах  школьной  математики.  К  числу
алгоритмов  школьного  курса  математики  относятся  также  правила
решения  определенных  видов  уравнений  или  неравенств,  правила
построения различных геометрических фигур и т. п. Понятие «алго-
ритм» используется не только в математике, но и во многих областях
человеческой деятельности: например, говорят об алгоритме управ-
ления производственным процессом, алгоритме управления полетом
ракеты, алгоритме пользования бытовым прибором. Причем интуи-
тивно под алгоритмом понимают некоторую систему правил, обла-
дающих определенными свойствами.
Далее, изучая понятие «алгоритм», мы будем предполагать, что его
исполнителем является автоматическое устройство
- ЭВМ. Это на-
кладывает на запись алгоритма целый ряд обязательных требований.
Сформулируем  эти  требования  в  виде  перечня  свойств,  которыми
должен обладать алгоритм, адресуемый к исполнению на ЭВМ.
1. Первым свойством алгоритма является дискретный (пошаговый)
характер  определяемого  им  процесса.  Возникающая  в  результате
такого разбиения запись алгоритма представляет собой упорядочен-


109
ную последовательность отдельных предписаний (директив, команд),
образующих  прерывную/дискретную  структуру  алгоритма:  только
выполнив требования одного предписания, можно приступить к ис-
полнению следующего.
2. Исполнитель может выполнить алгоритм, если он ему понятен,
т.е. записан на понятном ему языке и содержит предписания, которые
исполнитель может выполнить. Набор действий, которые могут быть
выполнены  исполнителем,  называется
системой  команд  исполни-
теля. Алгоритм не должен содержать описания действий, не входящих
в систему команд исполнителя, т. е. своей структурой команд и фор-
мой  записи  алгоритм  должен  быть  ориентирован  на  конкретного
исполнителя.
3.  Алгоритмы,  предназначенные  для  исполнения  техническим
устройством, не должны содержать предписаний, приводящих к не-
однозначным действиям. Алгоритм рассчитан на чисто механическое
исполнение,  и  если  применять  его  повторно  к  одним  и  тем  же  ис-
ходным данным, то всегда должен получаться один и тот же результат;
при этом и промежуточные результаты, полученные после соответ-
ствующих  шагов  алгоритмического  процесса,  тоже  должны  быть
одинаковыми. Это свойство определенности и однозначности — де-
терминированности
- алгоритма позволяет использовать в качестве
исполнителя специальные машины-автоматы.
4.  Основополагающим  свойством  алгоритма  является  его  массо-
вость,  применимость  к  некоторому  классу  объектов,  возможность
получения результата при различных исходных данных на некоторой
области  допустимых  значений.  Например,  исходными  данными  в
алгоритмах  аль-Хорезми  могут  быть  любые  пары  десятичных  чисел.
Конечно, его способ не всегда самый рациональный по сравнению с
известными приемами быстрого счета. Но смысл массовости алгорит-
ма состоит как раз в том, что он одинаково пригоден для всех случаев,
требует лишь механического выполнения цепочки простых действий
и при этом исполнителю нет нужды в затратах творческой энергии.
5. Цель выполнения алгоритма — получение конечного результата
посредством выполнения указанных преобразований над исходными
данными. В алгоритмах аль-Хорезми исходными данными и резуль-
татом  являлись  числа.  Причем  при  точном  исполнении  всех  пред-
писаний алгоритмический процесс должен заканчиваться за конечное
число шагов. Это обязательное требование к алгоритмам — требова-
ние их результативности или конечности.
В математике известны вычислительные процедуры алгоритмиче-
ского характера, не обладающие свойством конечности. Например,
процедура вычисления числа
π. Однако если мы введем условие за-
вершения  вида  «закончить  после  получения
n  десятичных  знаков
числа
π»,  то  получим  алгоритм  вычисления  n  десятичных  знаков
числа
π. На этом принципе построены многие вычислительные ал-
горитмы.


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


Достарыңызбен бөлісу:
1   ...   72   73   74   75   76   77   78   79   ...   196




©emirsaba.org 2024
әкімшілігінің қараңыз

    Басты бет