Понятие алгоритма. Основные свойства алгоритма

Раздел 3. Технические средства информационных технологий

Лекция 10. Понятие и свойства алгоритма. Принцип программного

Управления

Понятие алгоритма и его свойства. Способы записи алгоритмов.

Принцип программного управления.

Литература: 1. Вычислительные системы, сети и телекоммуникации /

В.Л.Бройдо. – СПб.: Питер, 2003.

2. Могилев А.В. и др. Информатика: Учеб. пособие для

студ. пед. вузов / А.В.Могилев, Н.И.Пак, Е.К.Хеннер;

Под ред. Е.К.Хеннера. – 2-е изд., стер. – М.: Изд. центр

«Академия», 2001.

Ранее неоднократно отмечалось, что основным техническим средством обработки информации является ЭВМ. Машинная обработка информации предполагает решение различных вычислительных задач в соответствии с принятым вычислительным алгоритмом. Понятие алгоритма – одно из фундаментальных понятий информатики. Алгоритмизация наряду с моделированием выступает в качестве общего метода информатики. К реализации определенных алгоритмов сводятся процессы управления в различных системах, что делает понятие алгоритма близким и кибернетике.

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

Понятие алгоритма и его свойства.

Способы записи алгоритмов

Понятие алгоритма. Основные свойства алгоритма

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

Термин "алгоритм", как свидетельствует история, происходит от имени средневекового арабского математика Абу Джафара ибн Мусы аль-Хорезми (из Хорезма). Изменение (искажение) последней части имени ученого в европейских языках привело к образованию термина "алгорифм", затем "алгоритм". Аль-Хорезми сформулировал правила выполнения арифметических действий. Первоначально под алгоритмами как раз и понимали только правила выполнения четырех арифметических действий над многозначными числами.

В настоящее время в понятие алгоритма заложен более глубокий смысл:

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

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

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

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

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

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

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

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

Основными свойствами правильно построенного алгоритма являются:

– массовость;

– детерминированность;

– результативность;

– практическая осуществимость (реалистичность);

– достоверность;

– дискретность;

– экономичность.

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

В алгоритмах решения некоторых задач свойство массовости выполняется как бы автоматически, то есть, не надо прилагать каких-либо усилий для его обеспечения. Например, в выражении у = а + b это свойство выполняется при любых исходных данных (за исключением, может быть, такого случая, когда значения а и b выходят за диапазон представления чисел в ЭВМ, что для практических задач почти нереально). В других задачах для обеспечения свойства массовости может потребоваться применение специальных мер. Так, при вычислении корней квадратного уравнения с учетом вариаций исходных данных в алгоритме надо предусмотреть нахождение действительных и мнимых значений корней.

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

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

Например, при определении значений функции у = х / (1 – х²), можно получить результаты для всех значений переменной х, кроме х = 1 (или х = -1). Следовательно, при составлении алгоритма решения уравнения на ЭВМ, необходимо предусмотреть прекращение расчетов при указанных значениях х и выдачу соответствующего сообщения.

Практическая осуществимость алгоритма – это свойство, обеспечивающее возможность решения задачи на конкретной ЭВМ в реальные сроки.

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

Остальные свойства алгоритма имеют следующий смысл:

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

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

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

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

1. 2 Способы записи алгоритмов

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

При словесном способе записи содержание последовательных этапов алгоритма описывается в произвольной форме на естественном языке.

Формульный способ основан на строго формализованном аналитическом зада­нии необходимых для исполнения действий.

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

Операторныйспособ базируется на использовании для отображения алгоритма условного набора специальных операторов: арифметических (А), логических (Р), печати (П), ввода данных (В) и т. д.; операторы снабжаются индексами и между ними указываются необходимые переходы, а сами индексированные операторы описываются чаще всего в табличной форме.

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

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

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

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

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

Чаще всего используются два способа графического изображения алгоритмов – блок-схемы и структурограммы Насси-Шнейдермана. При этом наиболее удобными и, следовательно, наиболее применяемыми являются блок-схемы.

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

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

Рассмотрим графические знаки основных блоков, применяемых в блок-схемах алгоритмов.

1. Для обозначения начала или окончания алгоритма используют блоки, именуемые НАЧАЛО-КОНЕЦ (рисунок 1).

а) б)

Рисунок 1 – Графические знаки блоков группы НАЧАЛО-КОНЕЦ:

а) пуск; б) останов

2. Процесс преобразования данных в форму, пригодную для обработки в ЭВМ или для отображения результатов обработки, изображается с помощью блока ВВОД-ВЫВОД данных (рисунок 2).

Рисунок 2 – Графический знак блока ВВОД-ВЫВОД

3. Блок, в котором происходит обработка данных (выполнение операции или группы операций) или просто размещение данных в ячейки памяти без предварительной обработки (например, у = 5, у = 2 х + 3и т. д.), носит название ПРОЦЕСС (или БЛОК ДЕЙСТВИЯ) (рисунок 3).

Рисунок 3 – Графический знак блока ПРОЦЕСС

4. Процесс выбора направления выполнения алгоритма в зависимости от некоторых переменных условий изображается с помощью блока РЕШЕНИЕ (рисунок 4), имеющего один вход и два выхода.

Рисунок 4 – Графический знак блока РЕШЕНИЕ

5. Если в алгоритме предполагается использование ранее созданных и отдельно описанных алгоритмов или программ (подпрограмм), то применяют блок вызов вспомогательного алгоритма (рис. 5).

Рисунок 5 – Графический знак блока вызов вспомогательного

алгоритма

6. Если блок-схема алгоритма вычислительного процесса занимает много места и требуется переносить часть блок-схемы на другой лист (или в другое место на том же листе), то используется блок с названием СОЕДИНИТЕЛЬ (рисунок 6). Внутри блока указывается номер того блока, к которому (от кото
рого) ведет разорванная линия потока.

Рисунок 6 – Графический знак блока СОЕДИНИТЕЛЬ

7. На блок-схему алгоритма можно выносить различные текстовые фрагменты, поясняющие тот или иной блок (действие). Для этого используется блок КОММЕНТАРИЙ (рисунок 7).

Рисунок 7 – Графический знак блока КОММЕНТАРИЙ

Мы рассмотрели, как изображаются на блок-схемах алгоритмовнаиболее часто используемые блоки. При составлении алгоритмов сложных вычислительных процессов могут быть использованы и другие блоки, предусмотренные ГОСТом.