Алгоритм, его свойства и формы представления


Алгоритм, его свойства и формы представления

Изучив этот пункт, мы:

Узнаем, Что такое алгоритм;

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

Узнаем, что такое алгоритмические языки и для чего они создаются.

==== 54.1.Алгоритм и его исполнитель ==========================================

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

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

Под алгоритмом понимают описание последовательности действий, которые нужно выполнить для достижения поставленной цели или получения необходимого результата. Любой алгоритм состоит в расчете на определенного Исполнителя, которому принадлежит выполнять предписанные действия. Каждое действие алгоритма вызывается отдельной Указанию. Указания алгоритма называются Командами. Следовательно, исполнитель алгоритма должен быть способен понять и выполнить каждую из команд алгоритма. Так, например, алгоритм решения квадратного уравнения рассчитан на исполнителя, который знает, что такое дискриминант, как вычислить квадратный корень и тому подобное.

Совокупность команд, которые исполнитель может понять и выполнить, называется Системой команд исполнителя.

Если алгоритм ориентирован на выполнение человеком, то к формулировке команд жесткие требования не предъявляются. Достаточно, чтобы человек точно поняла, что именно от него требуется. Так, обе команды: «найди произведение чисел 5 и 7» и «умножь 5 на 7» человек поймет и выполнит все равно.

Если же исполнителем алгоритма является техническое устройство, в частности компьютер, то в таком случае слова «понять команду» означают Распознать (или Идентифицировать) команду. Идентификацией (от лат. Identicus — тождественный и ficatio — делаю) называется отождествление объекта с одним из известных системе.

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

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

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

Читать  Алгоритмы и программы по разветвлениями

==== 54.2.Свойства алгоритма ==============================================

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

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

Второй свойством алгоритма является Конечность, или Результативность.По конечное число шагов алгоритм приводит к получению нужного результата или до достижения поставленной цели.

Третьей свойством алгоритма является его Понятность исполнителю. Алгоритм состоит только из таких команд, которые входят в систему команд его исполнителя.

Важным свойством алгоритма является Детерминированность (от лат. Determinare — определять), или Определенность.Каждая команда алгоритма точно и однозначно описывает действия исполнителя — что ему надо сделать на данном этапе и в которой команды перейти на следующем. У исполнителя не может возникнуть потребности в любой дополнительной информации. Возможность самостоятельного принятия исполнителем любых решений исключена. Таким образом, алгоритм приписывает Точное, то есть без каких-либо отклонений, и Формальное, то есть без вмешательства в смысл, выполнения его команд.

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

Еще одним свойством алгоритма является Массовость.Алгоритм не складывается для одной конкретной задачи. Он рассчитывается на решение всех задач определенного типа, которые отличаются между собой входными данными. С смысла задачи, способа ее решения, реализованного в алгоритме, обычно следуют определенные ограничения на допустимые значения входных данных. Эти ограничения определяют возможности применения алгоритма.

Итак, свойствами алгоритма является дискретность, конечность, понятность, детерминированность, массовость. Теперь, опираясь на эти свойства, определим, что такое алгоритм.

АлгоритмЭто точное и понятный для исполнителя предписание об осуществлении конечной последовательности определенных действий с целью решения задачи определенного типа или достижения поставленной цели.

Примером алгоритма, который дает возможность продемонстрировать все его свойства, является алгоритм сбора автомобиля на конвейере. Действительно, процесс сбора разлагается на последовательность отдельных операций. Начать следующую операцию можно только после завершения предыдущей. Последовательность операций является точно установленным, изменить их порядок нельзя (например, сначала осуществляется закрепление корпуса, и только потом установление двигателя). На каждом этапе сбора точно определено, какая именно операция должно выполняться. На конвейере работает бригада рабочих (исполнитель). Они понимают, что надо делать, и могут выполнить нужные операции. Каких-либо самостоятельных решений принимать не надо — все действия четко определены и спланированы. Бригада имеет комплект деталей (входные данные), необходимых для сбора конкретной модели автомобиля. Никакие другие детали не понадобятся. За определенный срок все этапы сбора будут завершены, и мы получим результат выполнения алгоритма — готовый автомобиль съезжает с конвейера!

Читать  КОМПЬЮТЕРНОЕ МОДЕЛИРОВАНИЕ – Основы алгоритмизации и программирования

==== 54.3.Словесная и табличная формы представления алгоритма ==========================

Алгоритм может быть представлен в различных формах.

В Словесной форме алгоритм записывается как последовательность занумерованных словесных команд. Команды выполняются в порядке возрастания их номеров.  Если нужно изменить этот

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

Записью алгоритма можно считать Формулу, потому что из нее следует порядок осуществления вычислений для получения числового результата. Если выполняется серия расчетов по одинаковым формулам, то для записи алгоритма применяется Табличная форма. По табличной форме в определенных столбцах таблицы размещаются входные данные, а значение в следующих столбцах — промежуточные выходные — вычисляются по соответствующим формулам. Таким образом, таблица отражает этапы выполнения алгоритма. Мы использовали табличную форму представления алгоритма при работе с электронными таблицами Excel.

==== 54.4.Блок-схема =============================================== ========

Распространенной формой наглядного представления алгоритма является Блок Схема.

Блок-схема состоит из отдельных геометрических фигур — блоков, которые соединяются направленными линиями. Линии показывают последовательность перехода от одного блока к следующему.

Для представления алгоритма применяются блоки двух видов: Функциональные и

Альтернативные (рис.54.1).

А) б)

Рис. 54.1. Основные элементы блок-схемы алгоритма: а) функциональный блок; б) альтернативный блок

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

Альтернативные блоки обозначаются ромбами (рис.54.1б). Слово «альтернативный» (от лат. Alternare — чередоваться)

Означает «предполагающий одну из двух возможностей, которые исключают друг друга».

Внутри ромба размещается Условие. Условием называют любое высказывание, которое может иметь только одно из двух значений — «истина» или «ложь». Например, в качестве условий могут быть высказывания: «цвет флажка оранжевый», «z — двузначное число», «рост парня не ниже 170 см», «x = 7», «a> = b» и другие.

В альтернативный блок входит одна направлена ​​линия, а выходят из него две — с надписями «да» и «нет». Условие, записанное внутри ромба, подвергается проверке. По результатам проверки — «истина» ( «да») или «ложь» ( «нет») — осуществляется выбор соответствующей направленной линии, то есть выбор одного из двух возможных вариантов продолжения выполнения алгоритма.

А) б)

Рис. 54.2. Вспомогательные элементы блок-схемы алгоритму:

Кроме функциональных и альтернативных блоков, в блок схемах применяются также Вспомогательные блоки для обозначения начала или конца алгоритма (рис.54.2) и ввода или вывода данных (рис. 54.2б).

==== 54.5.Алгоритмические языки ================================================ =

Блок-схемы удобны для наглядного представления алгоритмов, однако для сложных алгоритмов они становятся громоздкими. Более компактной формой представления алгоритма является его описание на Алгоритмическом языке.

Читать  Файлы Паскаль, файловый тип, Процедуры и Функции в Pascal

Алгоритмической языке Называется искусственный язык, предназначенный для представления алгоритмов.

Алгоритмические языки позволяют подать алгоритм в виде текста, который составляется по определенным правилам с применением специальных слов, которые называются Служебными. Количество таких слов ограничено. Каждое служебное слово имеет точно определенный смысл, назначение и способ применения. Служебные слова подбираются так, чтобы их смысл в алгоритмическом языке перекликался с обычным значением слова. Алгоритм, представленный на алгоритмическом языке, легко воспринимается, потому что он читается как обычный текст.

Можно выделить три вида алгоритмических языков. К первому относим языка, рассчитанные на представление алгоритма в виде, удобном для его осознания человеком. Если мы откроем книги, посвященные методам, то убедимся, что разные авторы применяют разные алгоритмические языки, которые они считают удобными для презентации алгоритмов читателям. Основной функцией алгоритмических языков является воссоздание логической строения алгоритма, является важнейшим для разработки алгоритма и сложным для его понимания. Представление логической строения осуществляется по четко определенным правилам, и именно для этого вводятся и применяются служебные слова. К представлению действий в таких языках обычно не выдвигается жестких требований, допускается сравнительно свободный их описание.

Второй вид алгоритмических языков составляют языки, назначением которых является представление алгоритма в форме, пригодной для однозначного преобразования алгоритма на язык компьютерных команд. Такие языка является своеобразным компромиссом между человеком и компьютером. Человек делает шаг навстречу компьютеру, ибо представляет алгоритм, используя ограниченный набор средств языка в точном соответствии с установленными правилами. Компьютер «учится» распознавать инструкции алгоритма и трансформировать их в компьютерные команды.

Алгоритмический язык, конструкции которой однозначно превращаются в команды компьютеру, называется Языком программирования (от греч. Programma — распоряжение, предписание, объявления).Текст алгоритма, записанный на языке программирования, называется Программой.

Исторически сложилось так, что языки программирования являются англоязычными в том смысле, что их служебные слова являются словами или сокращениями слов английского языка.

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

Чрезвычайное разнообразие языков программирования объясняется тем, что каждая из них имеет свои преимущества для представления алгоритмов того или иного назначения. Однако всем языкам программирования присуща одна общая свойство: они дают возможность применить компьютер для решения любой задачи, если составлен алгоритм ее решения.

Алгоритмические языки третьего вида занимают промежуточную позицию между языками первого и второго видов. Это языка учебного назначения. С одной стороны, они облегчают восприятие алгоритма человеком и придают ей такие средства представления алгоритма, которые хорошо согласуются с естественным процессом обдумывания нужных действий. С другой стороны, такие языка является определенной ступенью к языкам программирования, так как конструктивно имеют с ними много общих черт.

Читать  Одномерные массивы – Понятие массива и его свойства, инициализация массива

Алгоритмический язык, созданная для изучения правил и приемов составления алгоритмов, называется Учебной алгоритмической языке (НАМ).Служебные слова учебной алгоритмического языка являются словами или сокращениями слов украинского языка. Это упрощает как чтение и понимание алгоритмов, написанных на языке НАМ, так и составление алгоритмов средствами НАМ. Важным достоинством НАМ является то, что ее служебные слова, конструкции и правила записи алгоритма подобные тем, которые характерны для распространенных языков программирования. Благодаря такой схожести овладения НАМ является шагом к реальному программирования.

Далее мы ознакомимся с НАМ и языком программирования Паскаль.

ВЫВОДЫ

Контрольные вопросы и упражнения

1. Вставьте слова, пропущенные в следующем определении алгоритма.

«Алгоритм — это … и… предписание об осуществлении конечной последовательности определенных действий с целью решения задачи определенного типа или достижения поставленной цели».

А) четкое; б) точный;

В) понятен для исполнителя; г) короткий;

Д) простой; е) доступен.

2. свойствами алгоритма являются:

А) понятность; б) полнота;

В) лаконичность; г) массовость;

Д) дискретность;

Е) детерминированность; е) формальность;

Ж) конечности; з) правильность.

3. Понятность алгоритма означает, что:

А) каждая его команда понятна для всех;

Б) каждая команда алгоритма понятна для его исполнителя; в) каждая его команда является простой для исполнения;

Г) исполнитель понимает и может выполнить каждую команду алгоритма; д) каждая команда алгоритма может быть выполнено.

4. Детерминированность алгоритма означает, что:

А) алгоритм дает исполнителю все, что ему нужно для решения задачи; б) алгоритм ограничивает действия исполнителя;

В) алгоритм однозначно определяет все действия исполнителя;

Г) алгоритм гарантирует решения задачи по конечное число шагов.

5. Дискретность алгоритма означает, что он подает процесс решения задачи в виде: а) совокупности отдельных простых действий;

Б) определенной последовательности отдельных простых действий;

В) определенного множества понятным действий;

Г) конечного множества действий, которые исполнитель может выполнить.

6. Массовость алгоритма означает, что его можно применять: а) для решения любых задач;

Б) для решения любых задач определенного класса;

В) для решения задач определенного класса с любыми входными данными;

Г) для решения задач определенного класса, имеют входные данные, относящиеся к кругу допустимых для данного алгоритма.

7. Ответьте на вопрос:

А) из каких элементов состоит блок-схема;

Б) такое функциональный блок в блок-схеме, каково его назначение; в) такое альтернативный блок в блок-схеме, каково его назначение; г) такое условие;

Д) преимущества и недостатки имеет представление алгоритма с помощью блок-схемы?

8. Ответьте на вопрос:

А) с какой целью создаются алгоритмические языки, какие преимущества они имеют по сравнению с блок-схемами;

Б) особенности присущи учебной языке;

В) чем отличаются языка программирования от других алгоритмических языков?

9. Индийский математик Д. Капрекар доказал, что любое четырехзначное число, у которого не все цифры одинаковые, в результате преобразований по определенному алгоритму приводит к одному и тому же число, которое получило название постоянной Капрекара. Алгоритм имеет такой вид:

Читать  Тема Паскаль 7: Использование текстовых файлов для ввода и вывода информации

1) переставить цифры числа N по убыванию;

2) переставить цифры числа N по ростом;

3) вычесть из первого числа второе;

4) если полученная разница R не равно числу N, то повторить с ней действия 1) -3).За не более 7 повторений алгоритм приводит к числу, которое затем переходит же в себя. Это и есть стала Капрекара. найдите ее.

10. Существует старинный метод определения пропорции, в которой нужно смешать два вещества различных концентраций для получения вещества заданной концентрации. Алгоритм приписывает выполнения таких действий:

1) одну под другой запишите концентрации растворов, есть; слева между ними — то, что нужна;

2) найдите разницу между большей концентрацией и нужной и запишите ее справа от меньшей концентрации;

3) найдите разницу между нужной концентрацией и меньше и запишите ее справа от большей концентрации;

4) прочитайте ответ: числа дело определяют пропорцию, в которой надо смешать соответствующие растворы.

Например, для получения 7% раствора из имеющихся 10% и 6% имеем следующую запись:

Итак, для получения 7% раствора следует взять 1 часть 10% и 3 части 6% растворов.

Пользуясь приведенным алгоритмом, найдите ответы на приведенные ниже вопросы:

А) Как получить 3 литра молока жирностью 3,2%, если есть молоко 1,5% и 4,5%

Жирности?

Б) Как следует смешать чаи двух сортов — ценой 64 и 82 грн. за кг, чтобы образовать смесь цене в 70 грн. за кг?

В) Сколько конфет цене по 12 грн. 50 коп. за 1 кг нужно добавить до 20 кг конфетной смеси цене по 9 грн. 15 коп. за 1 кг, чтобы довести цену смеси до 10 грн. за 1 кг?

11. Конвей предложил алгоритм «Жизнь», по которому можно наблюдать поэтапное развитие «цивилизации» на клеточном пространстве.

Сначала в некоторых клетках пространства зародилась жизнь. Каждый следующий этап развития «цивилизации» вполне определяется ситуацией, которая была на предыдущем этапе, по следующим правилам:

·  клеточка выживает, если у нее два или три соседи;

·  клеточка погибает, если у нее меньше двух соседей (от одиночества) или более трех (от тесноты)

·  жизнь зарождается в пустой клетке, если она имеет трех соседей.

Сосед — это Живая клеточка, с которой есть хотя бы одна общая точка соприкосновения. Для подсчета соседей каждой клеточки надо рассматривать 8 клеток вокруг нее.

Постройте этапы развития таких «цивилизаций»:

12. Составьте алгоритмы решения задач о монеты:

1) среди 4 монет есть одна фальшивая, отличающаяся от настоящих по весу. За два взвешивания на весах без рычагов найти фальшивую монету;

2) среди 1000 монет есть одна фальшивая. За наименьшее количество взвешенных на весах без рычагов определить, легче или тяжелее фальшивая монета от настоящей;

3) среди 27 монет есть одна фальшивая, которая легче настоящей. За три взвешивания на весах без рычагов найти фальшивую монету.

[Всего голосов: 3    Средний: 5/5]