Строчная словесная запись алгоритма

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

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

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

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

Рассмотрим несколько примеров строчной записи алгоритмов для различных исполнителей.

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

1. Если а = b, результатом считать а; закончить вычисления.

2. Если а > b, найти разность а - b; новым значением а считать значение разности; перейти к п. 1;

3. Если b > а, найти разность b - а; новым значением b считать значение разности; перейти к п. 1;

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

Формула - строчная запись действий, обеспечивающих обработку числовых, символьных или логических данных. Формулы, предназначенные для исполнителя «человек», не обязательно могут быть строчными - это приводит к некоторой неоднозначности порядка действий, не сказывающейся, однако, на результат вычислений вследствие дистрибутивного и сочетательного законов.

Пример:

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

· операции в скобках;

· возведение в степень, вычисление значения стандартных функций и процедур-функций;

· логическое отрицание NOT;

· умножение, деление, целочисленное деление (div), остаток от целочисленного деления (mod), логическое И (AND);

· сложение, вычитание, логическое ИЛИ (OR);

· операции отношения (>, <, =, >=, <=,< >).

Помимо указанных приоритетов принимается дополнительное правило:

· при наличии операций равного приоритета они выполняются в порядке слева направо.

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

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

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

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

· внешнее оформление: АЛГ - начало алгоритма, ПРОЦ - начало процедуры, КНЦ; - конец процедуры, КНЦ. - конец алгоритма;

· ветвление: ЕСЛИ ...ТО...ИНАЧЕ...ВСЕ; после ЕСЛИ ставится описание логического условия, по которому происходит ветвление, после ТО - описание действий (их может быть несколько), которые исполняются при значении условия TRUE, если ветвление полное - после ИНАЧЕ описываются альтернативные действия, в любом случае в конце ставится слово ВСЕ, которое служит признаком окончания данной конструкции;

· цикл: ПОКА...ПОВТОРЯТЬ...КЦ; после ПОКА ставится описание логического условия выполнения команд цикла, после ПОВТОРЯТЬ - описание действий (тела цикла), КЦ - признак конца циклической конструкции.

Часто при записи алгоритма отдельные действия заканчиваются разделителем (например, «;») - это позволяет избежать ошибок в случае, если описание действия занимает не одну строку. Помимо этого, для удобочитаемости и наглядности применяется так называемая «структурная запись», при которой запись отдельных элементов структур производится не с начала строки, а с отступом, показывающим вложенность и подчиненность этих элементов.

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

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

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

Различают языки низкого уровня (машинно-ориентированные) и высокого уровня (машинно-независимые). К языкам первого типа относятся:

· машинный язык (язык машинных кодов) - совокупность команд, интерпретируемых и исполняемых компьютером; каждый оператор программы на этом языке является машинной командой, а все данные отыскиваются по абсолютным значениям адресов, по которым они располагаются в ОЗУ;

· ассемблер (макроассемблер) - язык символического кодирования - операторами языка являются машинные команды, которым приписываются мнемонические обозначения, а в качестве операндов используются не конкретные адреса в ОЗУ, а их символические имена.

Пример команд ассемблера:

CLA - очистить один из регистров сумматора (аккумулятор);

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

MOV - содержимое аккумулятора пересылается в ячейку с номером, записанным вслед за командой;

HLT - стоп.

Безусловно, ассемблеры содержат и другие команды.

Рассмотрим простой пример сложения чисел a, b и с. Результат должен присваиваться переменной d.

Запись алгоритма производится в текстовом редакторе с ASC-кодировкой. Ясно, что для преобразования текста в последовательность машинных команд необходима еще одна промежуточная программа - она называется компилятор. На этапе компиляции производится также распределение данных в ОЗУ; при этом вместо имен переменных подставляются относительные адреса ячеек, в которых данные располагаются. Абсолютные адреса данным присваивает операционная система при размещении программы в ОЗУ компьютера перед ее использованием.

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

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

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

Примерами являются язык FORTRAN (FORmula TRANslator) -язык решения сложных научных и инженерных задач (кстати, это был первый язык программирования высокого уровня); COBOL (Common Business Oriented Language) - язык для решения экономических и коммерческих задач; LISP (List Processing Language) -язык, используемый в решении задач искусственного интеллекта. К универсальным языкам относятся PASCAL (Philips Automatic Sequence CALculator), BASIC (Beginner ALL-purpose Symbolic Instruction Code), С (C++), Jawa, а также современные среды визуального программирования DELPHI, VISUAL BASIC и др. Эти языки позволяют решить, вообще говоря, любую задачу, хотя трудоемкость решения конкретной задачи в разных языках будет различаться.

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

Таблица 8.1

Парадигма программирования	Представление программ и данных	Исполнение программы	Связь частей программы между собой
Процедурное	Программа и данные представляют собой отдельные, не связанные друге другом элементы	Последовательное выполнение операторов	Возможна только через совместно обрабатываемые данные
Объектно-ориентированное	Данные и методы их обработки инкаспулированы в рамках единого объекта	Последовательность событий и реакций объектов на эти события	Отдельные части программы могут наследовать методы и элементы данных друг у друга
Логическое	Данные и правила их обработки объединены в рамках единого логического структурного образования	Преобразование логического образования в соответствии с логическими правилами	Разбиение программы на отдельные независимые части затруднительно

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

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

Пример 4.13

Пример 9.3

Характеристики канала связи

Об объектном подходе в прикладной информатике

Вернуться в оглавление: Теоретические основы информатики