АЛГОРИТМ И ЕГО СВОЙСТВА
/>/> 1.1.РАЗЛИЧНЫЕ ПОДХОДЫ К ПОНЯТИЮ«АЛГОРИТМ»
Понятие алгоритма — одно из фундаментальных понятийинформатики. Алгоритмизация наряду с моделированием выступает в качестве общегометода информатики. К реализации определенных алгоритмов сводятся процессыуправления в различных системах, что делает понятие алгоритма близким икибернетике.
Алгоритмы являются объектом систематического исследованияпограничной между математикой и информатикой научной дисциплины, примыкающей кматематической логике — теории алгоритмов.
Особенность положения состоит в том, что при решениипрактических задач, предполагающих разработку алгоритмов для реализации на ЭВМ,и тем более при использовании на практике информационных технологий, можно, какправило, не опираться на высокую формализацию данного понятия. Поэтомупредставляется целесообразным познакомиться с алгоритмами и алгоритмизацией наоснове содержательного толкования сущности понятия алгоритма и рассмотренияосновных его свойств. При таком подходе алгоритмизация более выступает какнабор определенных практических приемов, особых специфических навыковрационального мышления в рамках заданных языковых средств. Можно провестианалогию между этим обстоятельством и рассмотренным выше подходом к измерениюинформации: тонкие математические построения при «кибернетическом» подходе неочень нужны при использовании гораздо более простого «объемного» подхода припрактической работе с компьютером.
Само слово «алгоритм» происходит от algorithmi — латинскойформы написания имени великого математика IX века аль-Хорезми, которыйсформулировал правила выполнения арифметических действий. Первоначально подалгоритмами и понимали только правила выполнения четырех арифметическихдействий над многозначными числами.
/>/> 1.2.ПОНЯТИЕ ИСПОЛНИТЕЛЯАЛГОРИТМА
Понятие исполнителя невозможно определить с помощьюкакой-либо формализации. Исполнителем может быть человек, группа людей, робот,станок, компьютер, язык программирования и т.д. Важнейшим свойством,характеризующим любого из этих исполнителей, является то, что исполнитель умеетвыполнять некоторые команды. Так, исполнитель-человек умеет выполнять такиекоманды как «встать», «сесть», «включить компьютер» и т.д., а исполнитель-языкпрограммирования Бейсик — команды PRINT, END, LIST и другие аналогичные. Всясовокупность команд, которые данный исполнитель умеет выполнять, называетсясистемой команд исполнителя (СКИ).
В качестве примера (рис.1.11) рассмотрим исполнителя-робота,работа которого состоит в собственном перемещении по рабочему полю (квадратупроизвольного размера, разделенному на клетки) и перемещении объектов, вначальный момент времени находящихся на «складе» (правая верхняя клетка).
/>
Рис.1.11. Исполнитель-робот
Одно из принципиальных обстоятельств состоит в том, чтоисполнитель не вникает в смысл того, что он делает, но получает необходимыйрезультат. В таком случае говорят, что исполнитель действует формально, т.е. отвлекаетсяот содержания поставленной задачи и только строго выполняет некоторые правила,инструкции.
Это — важная особенность алгоритмов. Наличие алгоритмаформализует процесс решения задачи, исключает рассуждение исполнителя. Использованиеалгоритма дает возможность решать задачу формально, механически исполняякоманды алгоритма в указанной последовательности. Целесообразностьпредусматриваемых алгоритмом действий обеспечивается точным анализом со сторонытого, кто составляет этот алгоритм.
Введение в рассмотрение понятия «исполнитель» позволяетопределить алгоритм как понятное и точное предписание исполнителю совершитьпоследовательность действий, направленных на достижение поставленной цели. Вслучае исполнителя-робота мы имеем пример алгоритма «в обстановке»,характеризующегося отсутствием каких-либо величин. Наиболее жераспространенными и привычными являются алгоритмы работы с величинами — числовыми,символьными, логическими и т.д.
/>/> 1.3.ГРАФИЧЕСКОЕ ПРЕДСТАВЛЕНИЕАЛГОРИТМОВ
Алгоритм/>/>/>1.4.СВОЙСТВА АЛГОРИТМОВ
Алгоритм должен быть составлен таким образом, чтобы исполнитель,в расчете на которого он создан, мог однозначно и точно следовать командамалгоритма и эффективно получать определенный результат. Это накладывает назаписи алгоритмов ряд обязательных требований, суть которых вытекает, вообщеговоря, из приведенного выше неформального толкования понятия алгоритма. Сформулируемэти требования в виде перечня свойств, которым должны удовлетворять алгоритмы,адресуемые заданному исполнителю.
1. Одно из первых требований, которое предъявляется калгоритму, состоит в том, что описываемый процесс должен быть разбит напоследовательность отдельных шагов. Возникающая в результате такого разбиениязапись представляет собой упорядоченную совокупность четко разделенных друг отдруга предписаний (директив, команд, операторов), образующих прерывную (или,как говорят, дискретную) структуру алгоритма. Только выполнив требования одногопредписания, можно приступить к выполнению следующего. Дискретная структураалгоритмической записи может. Например, подчеркиваться сквозной нумерациейотдельных команд алгоритма, хотя это требование не является обязательным. Рассмотренноесвойство алгоритмов называют дискретностью.
2. Используемые на практике алгоритмы составляются сориентацией на определенного исполнителя. Чтобы составить для него алгоритм,нужно знать, какие команды этот исполнитель может понять и исполнить, а какие — не может. Мы знаем, что у каждого исполнителя имеется своя система команд. Очевидно,составляя запись алгоритма для определенного исполнителя, можно использовать лишьте команды, которые имеются в его СКИ. Это свойство алгоритмов будем называтьпонятностью.
3. Будучи понятным, алгоритм не должен содержатьпредписаний, смысл которых может восприниматься неоднозначно, т.е. одна и та жекоманда, будучи понятна разным исполнителям, после исполнения каждым из нихдолжна давать одинаковый результат.
Запись алгоритма должна быть настолько четкой, полной ипродуманной в деталях, чтобы у исполнителя не могло возникнуть потребности впринятии решений, не предусмотренных составителем алгоритма. Говоря иначе,алгоритм не должен оставлять места для произвола исполнителя. Кроме того, валгоритмах недопустимы также ситуации, когда после выполнения очередной командыалгоритма исполнителю неясно, какая из команд алгоритма должна выполняться наследующем шаге.
Отмеченное свойства алгоритмов называют определенностью илидетерминированностью.
4. Обязательное требование к алгоритмам — результативность. Смыслэтого требования состоит в том, что при точном исполнении всех предписаний алгоритмапроцесс должен прекратиться за конечное число шагов и при этом долженполучиться определенный результат. Вывод о том, что решения не существует — тожерезультат.
5. Наиболее распространены алгоритмы, обеспечивающие решениене одной конкретной задачи, а некоторого класса задач данного типа. Этосвойство алгоритма называют массовостью. В простейшем случае массовостьобеспечивает возможность использования различных исходных данных.
/>/> 1.5.ПОНЯТИЕ АЛГОРИТМИЧЕСКОГО ЯЗЫКА
Достаточно распространенным способом представления алгоритмаявляется его запись на алгоритмическом языке, представляющем в общем случаесистему обозначений и правил для единообразной и точной записи алгоритмов иисполнения их. Отметим, что между понятиями «алгоритмический язык» и «языкипрограммирования» есть различие; прежде всего, под исполнителем валгоритмическом языке может подразумеваться не только компьютер, но иустройство для работы «в обстановке». Программа, записанная на алгоритмическомязыке, не обязательно предназначена компьютеру. Практическая же реализацияалгоритмического языка — отдельный вопрос в каждом конкретном случае.
Как и каждый язык, алгоритмический язык имеет свой словарь. Основуэтого словаря составляют слова, употребляемые для записи команд, входящих всистему команд исполнителя того или иного алгоритма. Такие команды называютпростыми командами. В алгоритмическом языке используют слова, смысл и способупотребления которых задан раз и навсегда. Эти слова называют служебными. Использованиеслужебных слов делает запись алгоритма более наглядной, а форму представленияразличных алгоритмов — единообразной.
Алгоритм, записанный на алгоритмическом языке, должен иметьназвание. Название желательно выбирать так, чтобы было ясно, решение какойзадачи описывает данный алгоритм. Для выделения названия алгоритма перед нимзаписывают служебное слово АЛГ (АЛГоритм). За названием алгоритма (обычно сновой строки) записывают его команды. Для указания начала и конца алгоритма егокоманды заключают в пару служебных слов НАЧ (НАЧало) и КОН (КОНец). Командызаписывают последовательно.
Последовательность записи алгоритма:
АЛГ название алгоритма
НАЧ
серия команд алгоритма
КОН
Например, алгоритм, определяющий движениеисполнителя-робота, может иметь вид:
АЛГ в_склад
НАЧ
вперед
поворот на 90° направо
вперед
КОН
При построении новых алгоритмов могут использоватьсяалгоритмы, составленные ранее. Алгоритмы, целиком используемые в составе другихалгоритмов, называют вспомогательными алгоритмами. Вспомогательным можетоказаться любой алгоритм из числа ранее составленных. Не исключается также, чтовспомогательным в определенной ситуации может оказаться алгоритм, самсодержащий ссылку на вспомогательные алгоритмы.
Очень часто при составлении алгоритмов возникаетнеобходимость использования в качестве вспомогательного одного и того жеалгоритма, который к тому же может быть весьма сложным и громоздким. Было бынерационально, начиная работу, каждый раз заново составлять и запоминать такойалгоритм для его последующего использования. Поэтому в практике широкоиспользуют, так называемые, встроенные (или стандартные) вспомогательныеалгоритмы, т.е. такие алгоритмы, которые постоянно имеются в распоряженииисполнителя. Обращение к таким алгоритмам осуществляется так же, как и к«обычным» вспомогательным алгоритмам. У исполнителя-робота встроеннымвспомогательным алгоритмом может быть перемещение в склад из любой точкирабочего поля; у исполнителя-язык программирования Бейсик это, например,встроенный алгоритм «SIN».
Алгоритм может содержать обращение к самому себе каквспомогательному и в этом случае его называют рекурсивным. Если командаобращения алгоритма к самому себе находится в самом алгоритме, то такуюрекурсию называют прямой. Возможны случаи, когда рекурсивный вызов данногоалгоритма происходит из вспомогательного алгоритма, к которому в данномалгоритме имеется обращение. Такая рекурсия называется косвенной. Пример прямойрекурсии:
АЛГ движение
НАЧ
вперед
вперед
вправо
движение
КОН
Алгоритмы, при исполнении которых порядок следования командопределяется в зависимости от результатов проверки некоторых условий, называютразветвляющимися. Для их описания в алгоритмическом языке используютспециальную составную команду — команда ветвления. Она соответствует блок-схеме«альтернатива» и также может иметь полную или сокращенную форму. Применительнок исполнителю-роботу условием может быть проверка нахождения робота у краярабочего поля (край/не_край); проверка наличия объекта в текущей клетке(есть/нет) и некоторые другие:
ЕСЛИ условие ЕСЛИ условие ЕСЛИкрай
ТО серия 1 ТОсерия ТО вправо
ИНАЧЕ серия2 ВСЕ ИНАЧЕвперед
ВСЕ ВСЕ
Ниже приводится запись на алгоритмическом языке командывыбора (см. рис.1.14, б), являющейся развитием команды ветвления:
ВЫБОР
ПРИ условие 1: серия 1
ПРИ условие 2: серия 2
…
ПРИ условие N: серия N
ИНАЧЕ серия N+1
ВСЕ
Алгоритмы, при исполнении которых отдельные команды илисерии команд выполняются неоднократно, называют циклическими. Для организациициклических алгоритмов в алгоритмическом языке используют специальную составнуюкоманду цикла. Она соответствует блок-схемам типа «итерация» и может приниматьследующий вид:
ПОКА условие НЦ
НЦ серия
Серия ДОусловие
КЦ КЦ
В случае составления алгоритмов работы с величинами можнорассмотреть и другие возможные алгоритмические конструкции, например, цикл спараметром или выбор. Подробно эти конструкции будут рассматриваться признакомстве с реальными языками программирования.
В заключение данного параграфа приведем алгоритм,составленный для исполнителя-робота, по которому робот переносит все объекты сосклада в левый нижний угол рабочего поля (поле может иметь произвольные размеры):
АЛГ перенос АЛГв_угол3 АЛГ до_края
НАЧ НАЧ НАЧ
в_угол3 до_края ПОКАне_край
ЕСЛИ есть вправоНЦ
ТО до_края вперед
взять вправо КЦ
в_угол3 КОН КОН
установить
перенос
ИНАЧЕ
в_угол3
ВСЕ
КОН