ЛЕКЦИЯ 5. Алгоритмизация

5.1. Понятие алгоритма: свойства алгоритмов, исполнители алгоритмов, система команд исполнителя 1. Запись программы на метаязыке. Метаязык — это любой способ описания последовательности действий, понятный людям. Когда человеку, заблудившемуся в незнакомом городе, объясняют, как куда-то пройти, фактически ему дают программу действий на метаязыке. Алгоритм — это формальное описание способа решения задачи путем разбиения ее на последовательность элементарных операций. Слово «формальное» означает, что описание должно быть абсо-лютно полным и учитывать все возможные ситуации, которые мо-гут возникнуть по ходу решения. Понятие алгоритма - одно из фун-даментальных понятий информатики. Алгоритмизация наряду с мо-делированием выступает в качестве общего метода информатики. К реализации определенных алгоритмов сводятся процессы управле-ния в различных системах, что делает понятие алгоритма близким и кибернетике. Алгоритмы являются объектом систематического исследования пограничной между математикой и информатикой научной дисцип-лины, примыкающей к математической логике - теории алгоритмов. Особенность положения состоит в том, что при решении практиче-ских задач, предполагающих разработку алгоритмов для реализации на ЭВМ, и тем более при использовании на практике информацион-ных технологий, можно, как правило, не опираться на высокую формализацию данного понятия. Поэтому представляется целесо-образным познакомиться с алгоритмами и алгоритмизацией на ос-нове содержательного толкования сущности понятия алгоритма и рассмотрения основных его свойств. При таком подходе алгорит-мизация выступает как набор определенных практических приемов, особых специфических навыков рационального мышления в рамках заданных языковых средств. Само слово «алгоритм» происходит от algorithm - латинской формы написания имени великого математика IX века Мухаммеда аль-Хорезми, который сформулировал правила выполнения ариф-метических действий. Первоначально под алгоритмами и понимали

только правила выполнения четырех арифметических действий над многозначными числами. Понятие исполнителя невозможно определить с помощью какой-либо формализации. Исполнителем может быть человек, группа людей, робот, станок, компьютер, язык программирования и т.д. Важнейшим свойством, характеризующим любого из этих исполни-телей, является то, что исполнитель умеет выполнять некоторые команды. Вся совокупность команд, которые данный исполнитель умеет выполнять, называется системой команд исполнителя (СКИ). Одно из принципиальных обстоятельств состоит в том, что ис-полнитель не вникает в смысл того, что он делает, но получает не-обходимый результат. В таком случае говорят, что исполнитель действует формально, т.е. отвлекается от содержания поставленной задачи и только строго выполняет некоторые правила, инструкции. Это важная особенность алгоритмов. Наличие алгоритма формали-зует процесс решения задачи, исключает рассуждение исполнителя. Использование алгоритма дает возможность решать задачу фор-мально, механически исполняя команды алгоритма в указанной по-следовательности. Целесообразность предусматриваемых алгорит-мом действий обеспечивается точным анализом со стороны того, кто составляет этот алгоритм. Введение в рассмотрение понятия «исполнитель» позволяет оп-ределить алгоритм как понятное и точное предписание исполните-лю совершить последовательность действий, направленных па достижение поставленной цели. Наиболее распространенными и привычными являются алгоритмы работы с величинами - число-выми, символьными, логическими и т.д. Алгоритм, составленный для некоторого исполнителя, можно представить различными спо-собами: с помощью графического или словесного описания, в виде таблицы, последовательностью формул, записанным на алгорит-мическом языке (языке программирования). Остановимся на графи-ческом описании алгоритма, называемом блок-схемой. Этот способ имеет ряд преимуществ благодаря наглядности, обеспечивающей, в частности, высокую «читаемость» алгоритма и явное отображение управления в нем. Прежде всего, определим понятие блок-схемы.

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

На рис. 1 изображены «функциональная» (а) вершина (имеющая один вход и один выход); «предикатная» (б) вершина, имеющая один вход и два выхода (в этом случае функция Р передает управ-ление по одной из ветвей в зависимости от значения Р (Т, т.е. true, означает «истина», F, т.е. false - «ложь»); «объединяющая» (в) вер-шина (вершина «слияния»), обеспечивающая передачу управления от одного из двух входов к выходу. Иногда вместо Т пишут «да» (либо знак +), вместо F - «нет» (либо знак -).

Из данных элементарных блок-схем можно построить четыре блок-схемы (рис. 2), имеющих особое значение для практики алго-ритмизации. Рис. 2. Основные алгоритмические структуры На рис. 2 изображены следующие блок-схемы: а - композиция, или следование; б - альтернатива, или развилка, в и г - блок-схемы,

каждую из которых называют итерацией, или циклом (с предусло-вием (в), с постусловием (г)). S1 и S2 представляют собой в общем случае некоторые серии команд для соответствующего исполните-ля, Б — это условие, в зависимости от истинности (Т) или ложности (F) которого управление передаётся по одной из двух ветвей. Можно доказать, что для составления любого алгоритма доста-точно представленных выше четырех блок-схем, если пользоваться их последовательностями и/или суперпозициями. Блок-схема «аль-тернатива» может иметь и сокращенную форму, в которой от-сутствует ветвь S2 (рис.3, а). Развитием блок-схемы типа альтерна-тива является блок-схема «выбор» (рис.3, б). Рис. 3. Развитие структуры типа «альтернатива»: а) - неполная развилка; б) ~ структура «выбор» На практике при составлении блок-схем оказывается удобным использовать и другие графические знаки (некоторые из них приве-дены на рис.4).

Рис. 4. Некоторые дополнительные конструкции для изо-бражения блок-схем алгоритмов

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

С введением в рассмотрение понятия алгоритма вытекает необ-ходимость ввести следующие понятия.

Величина – это отдельный информационный объект, который имеет имя, значение и тип. Величины бывают постоянными и пере-менными. Постоянная величина (константа) не изменяет своего значения в ходе выполнения алгоритма. Переменная величина мо-жет изменять значение в ходе выполнения алгоритма. Переменная всегда обозначается символическим именем (X, F и т.п.). Тип вели-чины определяет множество значений, которые может принимать величина, и множество действий, которые можно выполнять с этой величиной. Основные типы величин: целый, вещественный, сим-вольный, логический. Выражение – запись, определяющая последо-вательность действий над величинами. Выражение может содер-жать константы, переменные, знаки операций, функции. Команда присваивания – команда исполнителя, в результате которой пере-менная получает новое значение. Формат команды: <имя перемен-ной>:=<выражение>

Исполнение команды присваивания происходит в таком порядке: сначала вычисляется выражение, а затем полученное значение при-сваивается переменной.

Алгоритм должен быть составлен таким образом, чтобы испол-нитель мог однозначно и точно следовать командам алгоритма и эффективно получать определенный результат. Это накладывает на записи алгоритмов ряд обязательных требований, суть которых вы-текает из неформального толкования понятия алгоритма. Сформу-лируем эти требования в виде перечня свойств, которым должны удовлетворять алгоритмы, адресуемые заданному исполнителю. 1.Одно из первых требований, которое предъявляется к алго-ритму, состоит в том, что описываемый процесс должен быть раз-бит на последовательность отдельных шагов. Возникающая в ре-зультате такого разбиения запись представляет собой упорядочен-ную совокупность четко разделенных друг от друга предписаний (директив, команд, операторов), образующих прерывную (или, как говорят, дискретную) структуру алгоритма. Только выполнив тре-бования одного предписания, можно приступить к выполнению следующего. Дискретная структура алгоритмической записи может, например, подчеркиваться сквозной нумерацией отдельных команд алгоритма, хотя это требование не является обязательным. Рассмот-ренное свойство алгоритмов называют дискретностью. 2. Используемые на практике алгоритмы составляются с ориен-тацией на определенного исполнителя. Чтобы составить для него алгоритм, нужно знать, какие команды этот исполнитель может по-нять и исполнить, а какие - не может. Составляя запись алгоритма для определенного исполнителя, можно использовать лишь те ко-манды, которые имеются в его СКИ. Это свойство алгоритмов бу-дем называть понятностью. 3. Будучи понятным, алгоритм не должен содержать предписа-ний, смысл которых может восприниматься неоднозначно, т.е. одна и та же команда, будучи понятна разным исполнителям, по-сле исполнения каждым из них должна давать одинаковый резуль-тат. Запись алгоритма должна быть настолько четкой, полной и продуманной в деталях, чтобы у исполнителя не могло возникнуть потребности в принятии решений, не предусмотренных составите-лем алгоритма. Говоря иначе, алгоритм не должен оставлять места для произвола исполнителя. Кроме того, в алгоритмах недопустимы также ситуации, когда после выполнения очередной команды алгоритма исполнителю неясно, какая из команд алгоритма должна вы-полняться на следующем шаге. Отмеченное свойство алгоритмов называют определенностью или детерминированностью. 4. Обязательное требование к алгоритмам - результативность. Смысл этого требования состоит в том, что при точном исполнении всех предписаний алгоритма процесс должен прекратиться за ко-нечное число шагов и при этом должен получиться определенный результат. Вывод о том, что решения не существует – тоже резуль-тат. 5. Наиболее распространены алгоритмы, обеспечивающие реше-ние не одной конкретной задачи, а некоторого класса задач данного типа. Это свойство алгоритма называют массовостью. В про-стейшем случае массовость обеспечивает возможность исполь-зования различных исходных данных. Достаточно распространенным способом представления алго-ритма является его запись на алгоритмическом языке, представ-ляющем в общем случае систему обозначений и правил для едино-образной и точной записи алгоритмов и исполнения их. Отметим, что между понятиями «алгоритмический язык» и «языки програм-мирования» есть различие; прежде всего, под исполнителем в алго-ритмическом языке может подразумеваться не только компьютер, но и устройство для работы «в обстановке». Программа, записанная на алгоритмическом языке, не обязательно предназначена компью-теру. Практическая же реализация алгоритмического языка - от-дельный вопрос в каждом конкретном случае. Как и каждый язык, алгоритмический язык имеет свой словарь. Основу этого словаря составляют слова, употребляемые для записи команд, входящих в систему команд исполнителя того или иного алгоритма. Такие ко-манды называют простыми командами. В алгоритмическом языке используют слова, смысл и способ употребления которых задан раз и навсегда. Эти слова называют служебными. Использование слу-жебных слов делает запись алгоритма более наглядной, а форму представления различных алгоритмов - единообразной. Алгоритм, записанный на алгоритмическом языке, должен иметь название. На-звание желательно выбирать так, чтобы было ясно, решение какой задачи описывает данный алгоритм. Для выделения названия алгоритма перед ним записывают служебное слово АЛГ (АЛГоритм). За названием алгоритма (обычно с новой строки) записывают его ко-манды. Для указания начала и конца алгоритма его команды заклю-чают в пару служебных слов НАЧ (НАЧало) и КОН (КОНсц). Ко-манды записывают последовательно. Последовательность записи алгоритма: АЛГ название алгоритма НАЧ серия команд алгоритма КОН При построении новых алгоритмов могут использоваться алго-ритмы, составленные ранее. Алгоритмы, целиком используемые в составе других алгоритмов, называют вспомогательными алгорит-мами. Вспомогательным может оказаться любой алгоритм из числа ранее составленных. Не исключается также, что вспомогательным в определенной ситуации может оказаться алгоритм, сам содержащий ссылку на вспомогательные алгоритмы. Очень часто при составле-нии алгоритмов возникает необходимость использования в качестве вспомогательного одного и того же алгоритма, который к тому же может быть весьма сложным и громоздким. Было бы нерациональ-но, начиная работу, каждый раз заново составлять и запоминать та-кой алгоритм для его последующего использования. Поэтому в практике широко используют, так называемые, встроенные (или стандартные) вспомогательные алгоритмы, т.е. такие алгоритмы, которые постоянно имеются в распоряжении исполнителя. Обраще-ние к таким алгоритмам осуществляется так же, как и к «обычным» вспомогательным алгоритмам. Алгоритм может содержать обраще-ние к самому себе как вспомогательному и в этом случае его назы-вают рекурсивным. Если команда обращения алгоритма к самому себе находится в самом алгоритме, то такую рекурсию называют прямой. Возможны случаи, когда рекурсивный вызов данного алго-ритма происходит из вспомогательного алгоритма, к которому в данном алгоритме имеется обращение. Такая рекурсия называется косвенной. Алгоритмы, при исполнении которых порядок следования ко-манд определяется в зависимости от результатов проверки некоторых условий, называют разветвляющимися. Для их описания в ал-горитмическом языке используют специальную составную команду - команда ветвления. Она соответствует блок-схеме «альтернатива» и также может иметь полную или сокращенную форму. Алгоритмы, при исполнении которых отдельные команды или серии команд выполняются неоднократно, называют циклическими. Для организации циклических алгоритмов в алгоритмическом языке используют специальную составную команду цикла. Она соответст-вует блок-схемам типа «итерация». В случае составления алгоритмов работы с величинами можно рассмотреть и другие возможные алгоритмические конструкции, например, цикл с параметром или выбор. Подробно эти конструк-ции будут рассматриваться при знакомстве с реальными языками программирования. Понятие алгоритма, рассмотренное выше, мож-но назвать понятием алгоритма в интуитивном смысле. Оно имеет нечеткий, неформальный характер, ссылается на некоторые точно не определенные, но интуитивно понятные вещи. Например, при определении и обсуждении свойств алгоритма мы исходили из воз-можностей некоторого исполнителя алгоритма. Его наличие пред-полагалось, но ничего определенного о нем не было известно. Гово-ря языком математики, ни аксиоматического, ни исчерпывающего конструктивного определения исполнителя мы так и не дали. Уста-новленные свойства алгоритмов следует называть эмпирическими. Они выявлены на основе обобщения свойств алгоритмов различной природы и имеют прикладной характер. Этих свойств достаточно для практического программирования, для создания обширного круга программ для компьютеров, промышленных роботов и т.д. Однако, как фундаментальное научное понятие алгоритм требует более обстоятельного изучения. Оно невозможно без уточнения по-нятия «алгоритм», более строгого его описания или, как еще гово-рят, без его формализации. Известно несколько подходов к формализации понятия «алго-ритм»: теория конечных и бесконечных автоматов; теория вычислимых (рекурсивных) функций;

λ -исчисление Черча. Все эти возникшие исторически независимо друг от друга под-ходы оказались впоследствии эквивалентными. Главная цель фор-мализации понятия алгоритма такова: подойти к решению пробле-мы алгоритмической разрешимости различных математических за-дач, т.е. ответить на вопрос, может ли быть построен алгоритм, приводящий к решению задачи. Формализацию понятия алгоритма можно рассмотреть в теории автоматов на примере машин Поста, Тьюринга. Идеи λ-исчислений Черча реализованы в языке LISP. Вместе с тем, формально определенный любым из известных спо-собов алгоритм не может в практическом программировании заме-нить то, что мы называли алгоритмами. Основная причина состоит в том, что формальное определение резко сужает круг рассматри-ваемых задач, делая многие практически важные задачи недоступ-ными для рассмотрения. 5.2. Основные принципы разработки и анализа алгоритмов

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

мента (управляющие структуры): композицию, альтернативу, ите-рацию.

Рис. 5. Функциональные (а), предикатные (б) и объединяющие (в) вершины Композиция - это линейная конструкция алгоритма, составлен-ная из последовательно следующих друг за другом функциональ-ных вершин, рис.6.

Рис. 6. Структура «композиция» Альтернатива - это конструкция ветвления, имеющая преди-катную вершину. Конструкция ветвления в алгоритмах может быть представлена в виде развилки (а), неполной развилки (б) и выбора (в) (рис. 7). Рис. 7. Структура «альтернатива». Здесь В — условие (логическое выражение) Итерация - это циклическая конструкция алгоритма, которая, вообще говоря, является составной структурой, состоящей из ком-позиции и альтернативы. Итерации, могут быть представлены в двух формах: с предусловием (а) и с постусловием (б) (рис.8). Каж-дая из рассмотренных структур имеет один вход и один выход. По-этому любая компьютерная программа может быть представлена

блок-схемой, сформированной из представленных трех управляю-щих структур. Рис. 8. Структура «итерация» Процесс структурного программирования обычно начинается с разработки блок-схемы. Для представления алгоритма в полном и законченном виде, а также для обозначения связей с окружающей средой добавляют дополнительные структуры ввода-вывода и нача-ла-конца программного блока, модуля, алгоритма: Для начального шага разработки программы чрезвычайно важ-ным и необходимым является определение исходных (ввод) и вы-ходных (вывод) данных задачи. С этого этапа начинается разработ-ка практически любого алгоритма. Метод разработки программы сверху-вниз предполагает процесс пошагового разбиения алгоритма на все более мелкие части до уровня элементарных конструкций, для которых можно составить конкретные команды. Идея структур-ного программирования сверху-вниз состоит в том, что, если для некоторой функции f существует ее композиция через две другие функции g и h, т.е. f=h(g(x)), то проблема разработки алгоритма для f сводится к проблемам разработки алгоритмов для h и g. В струк-турном программировании сверху-вниз на каждом шаге пытаются текущую функцию выразить как композицию двух (или более) дру-гих функций, которые представимы в виде рассмотренных выше управляющих структур. Зачастую используют метод структурного программирования снизу-вверх. По сути, мы приходим к конечному результату системным методом. Сначала разбиваем задачу на от-дельные блоки (модули) с их связями между собой (декомпозиция), затем, после их разработки, проводим сборку блоков в единую про-

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

Дата добавления: 2014-01-06