Файл: Алгоритмизация как обязательный этап разработки программы(Построение информационной модели разработки программного обеспечения).pdf

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

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

1.2. Алгоритм, его свойства, способы записи

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

Например:

Алгоритм – организованная последовательность действий.

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

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

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

В начальных классах школы дети изучают порядок выполнения арифметических действий над многозначными числами. Этот порядок был предложен выдающимся математиком средневекового Востока Мухаммедом аль-Хорезми и по латинскому написанию его имени (Alhorithmi) был назван алгоритмом. В дальнейшем это понятие в значительной мере расширилось.

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

Рассмотрим свойства алгоритмов.

Исполнение алгоритма распадается на последовательность отдельных шагов. Выполнить каждый шаг предписывает команда. Таким образом, алгоритм представляет собой последовательность команд, определяющих действия исполнителя. Алгоритм имеет прерывистую (дискретную) структуру: только выполнив одну команду, исполнитель может приступить к выполнению следующей. Это свойство называется дискретностью.

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

Набор команд, которые может выполнить данный исполнитель системой команд исполнителя (СКИ), или набором допустимых действий исполнителя[3;25].

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

Важным свойством алгоритма является точность (определенность, однозначность). Каждая команда алгоритма должна однозначно восприниматься исполнителем и предполагать его определенное действие. Выполнив шаг алгоритма, исполнитель должен точно знать, какой шаг выполнять следующим. Примером неточного алгоритма является фраза из рецепта «всыпать 2-4 столовые ложки сахара» или классическое изречение «казнить нельзя помиловать».

Исполнение алгоритма должно приводить к получению результата (свойство результативности) за конечное число шагов (свойство конечности).

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

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

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

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

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

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

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

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

Если алгоритм записан на языке, понятном исполнителю, он превращается в программу.

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

Перевод алгоритма с естественного языка на язык программирования не всегда прост, поэтому часто используются следующие способы записи алгоритмов:

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

псевдокоды.

Псевдокод – система обозначений и правил для единообразной и точной записи алгоритмов.

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

ГЛАВА 2. ОСНОВНЫЕ АЛГОРИТМИЧЕСКИЕ КОНСТРУКЦИИ

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

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

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

2.1. Конструкция следования

Конструкция следования – это такая форма организации действий, когда действия выполняются последовательно, одно за другим.

Об алгоритме, в составе которого нет других конструкций, кроме следования, говорят, что он имеет линейную структуру, что это линейный алгоритм.

На школьном алгоритмическом языке конструкция следования выглядит следующим образом.

Команда 1

Команда 2

Команда 3

………….

Команда N

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

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

Серия команд 1

Серия команд 2

Серия команд N

Здесь в качестве серий команд могут выступать:

• простые команды (одна или несколько);
• обращения к вспомогательным алгоритмам;
• структурные команды (ветвления и циклы).

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

2.2. Конструкция ветвления

Конструкция ветвления – это форма организации действий, при которой в зависимости от выполнения (невыполнения) некоторого условия выполняется одна из двух серий команд.

Алгоритм, содержащий конструкцию ветвления, имеет разветвляющуюся структуру.

Исполнитель, который в состоянии исполнять такие алгоритмы, должен иметь в своей системе команд команду ветвления, которая, как и цикл, относится к структурным командам. Получив такую команду, исполнитель проверяет, выполняется указанное условие или нет, и в зависимости от этого выбирает один из двух способов действий. Следовательно, чтобы исполнитель мог выполнить команду ветвления, он должен «уметь» проверять условие – проверка условия должна быть его допустимым действием[6;22].