Как осуществляется структурирование текста на алгоритмическом языке
Перейти к содержимому

Как осуществляется структурирование текста на алгоритмическом языке

  • автор:

Виды алгоритмов и способы их записи

Существует два вида алгоритмов: работы с величинами (числовыми, символьными, логическими) и работы «в обстановке» (например, робот). Они должны быть записаны на алгоритмическом языке, т. е. представлены в виде графического и/или словесного описания, таблицы, последовательности формул, на учебном алгоритмическом языке, языке программирования. Иногда их записывают на псевдокодах (специальных языках). Алгоритмический язык — это система обозначений и правил для единообразной и точной записи алгоритмов и исполнения их. Язык записи алгоритма должен быть понятным для человека.

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

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

Алг Сложение цел А, В, С нач

ввод А ввод В С:=А+В вывод С

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

Рис. 3.1. Структурная схема исполнения компьютером вычислений алгоритма за или метода решения задачи, в котором используются символы для отображения операций, данных, потока, оборудования и др.». Могут быть схемы данных, программ, работы системы, взаимодействия программ, ресурсов системы. Схемы обеспечивают наглядность, читаемость, отображение последовательности выполняемых процессов. Схема — это ориентированный граф, стрелками (или линиями) указывающий порядок исполнения команд алгоритма, а вершины (события) такого графа представлены геометрическими фигурами, которые называются символами. Например, (рис. 3.2): начало и конец записи алгоритма обозначаются овалом, данные (носитель которых не определен) — параллелограммом, процесс (обработка данных любого вида) — в виде прямоугольника, решение (или функция переключательного типа, например условие) — в виде ромба и т. д. Стандарт на этот специальный графический язык дан в ЕСПД (Единая система программной документации — ГОСТ 19.701—90).

Графические символы записи алгоритма в структурных схемах

Рис. 3.2. Графические символы записи алгоритма в структурных схемах

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

  • 1) всякий реальный алгоритм может быть построен с использованием трех базовых элементов: следования, ветвления и цикла;
  • 2) любая алгоритмическая структура, состоящая из базовых элементов, может быть представлена как единый процесс;
  • 3) алгоритм проектируется по нисходящей схеме;
  • 4) поэтапное уточнение или пошаговая детализация алгоритма.

В графической форме базовые вершины могут быть одного из трех типов:

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

Схемы основных алгоритмических структур

Рис. 3.3. Схемы основных алгоритмических структур

Первая схема на рис. 3.3 — самая простая структура алгоритма — последовательность, когда команды следуют одна за другой в естественном порядке. Такой алгоритм называется линейным. Здесь 51 и 52 некоторые серии команд для использования (5 — функциональные вершины).

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

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

Схему алгоритма можно нарисовать, например, вызвав через меню текстового процессора MS Word команды Вид Панели инструментов Рисование, с помощью автофигур (группа Блок-схема), где представлены начертания всех стандартных фигур и их обозначения. Надписи в фигурах следует создать с помощью команд Вставка -> Надпись.

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

На рис. 3.4 представлена структурная схема линейного алгоритма для решения следующей задачи: «Найти энергию магнитного поля при заданных значениях магнитного потока, силы

Структурная схема алгоритма к задаче линейной структуры

Рис. 3.4. Структурная схема алгоритма к задаче линейной структуры

тока и количества витков». (Программу к этой задаче см. в разделе 3.2.)

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

На рис. 3.6 представлена схема циклического алгоритма.

Для составления алгоритма следует:

Типовая структурная схема разветвляющегося алгоритма

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

Рис. 3.5. Типовая структурная схема разветвляющегося алгоритма

Типовая структурная схема циклического алгоритма

Рис. 3.6. Типовая структурная схема циклического алгоритма: а — цикл с предусловием; б — цикл с постусловием

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

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

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

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

инициализация начального действия

repeat (повторять до тех пор) выбор очередного действия if подходит then его запись; if решение не полное then RETR;

if неудача then стирание оператора и возврат на предыдущий

until (пока) удача or (или) нет действия

Такая рекурсивная процедура поможет правильно построить программу.

Рекурсивные алгоритмы, например, позволяют строить регулярные образы, постепенно образующие красивые узоры. Узор создается из серии определенным образом задаваемого мотива.

Например, кривые Серпинского первого и второго порядка можно разбить на части, которые соединяются четырьмя отрезками. Эти четыре части кривой представляют одну и ту же ломаную, поворачивающуюся каждый раз на 90°.

Контрольные вопросы

  • 1. Что такое алгоритм?
  • 2. Что такое система команд исполнителя?
  • 3. Какие вы знаете виды алгоритмов?
  • 4. Что такое алгоритмический язык?
  • 5. Каков графический язык описания алгоритмов?
  • 6. Какие вы знаете графические символы записи действий алгоритма?
  • 7. Какая теорема лежит в основе построения алгоритмических структур?
  • 8. Какие вы знаете структуры алгоритмов?
  • 9. Дайте характеристику алгоритмическим структурам.
  • 10. Что такое рекурсия и рекурсивный алгоритм?

Как осуществляется структурирование текста на алгоритмическом языке

Тема: Компьютер как формальный исполнитель алгоритмов (программ).

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

В данном примере все указанные действия выполняет Петя, следовательно, он и есть тот объект, который выполняет алгоритм. Петя умеет и может выполнять действия, указанные в алгоритме. Он выполняет эти действия в указанном порядке. Объект, который выполняет алгоритм называют исполнителем .

Различают формальных и неформальных исполнителей. Формальный исполнитель одну и туже команду выполняет одинаково. Неформальный исполнитель может выполнять команду по-разному.

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

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

Среда исполнителя – условия, при которых возможно исполнение алгоритма.

Система команд исполнителя (СКИ) – перечень действий, который способен понять и выполнить исполнитель.

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

Режимы работы исполнителя – режим непосредственного и программного управления. Непосредственное управление – исполнитель ждёт команды от человека и каждую команду выполняет немедленно. Программное управление – исполнителю задаётся последовательность команд (программа), а затем исполняет команды в автоматическом режиме. Некоторые исполнители работает только в одном из режимов.

1. Основные алгоритмические структуры: следование, ветвление, цикл. Изображение алгоритмических структур на блок-схемах.

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

В настоящее время существует всего три базовых алгоритмических конструкции:

 следование (линейный алгоритм);
 ветвление (разветвляющийся алгоритм);
 повторение (циклический алгоритм).

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

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

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

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

Команда ветвления — это составная команда алгоритма, в которой в зависимости от условия Р выполняется или одно S1 , или другое S2 действие. Из команд следования и команд ветвления составляются разветвляющиеся алгоритмы (алгоритмы ветвления). Примером разветвляющегося алгоритма будет нахождение большего из двух чисел, введенных с клавиатуры.

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

Команда повторения — это составная команда алгоритма, в которой в зависимости от условия Р возможно многократное выполнение действия S . Из команд следования и команд повторения составляются циклические алгоритмы (алгоритмы повторения). На рисунке представлена команда повторения с предусловием. Называется она так потому, что вначале проверяется условие, а уже затем выполняется действие. Причем действие выполняется, пока условие соблюдается. Пример циклического алгоритма может быть следующий. Пока с клавиатуры вводятся положительные числа, алгоритм выполняет нахождение их суммы.
Команда повторения с предусловием не является единственно возможной. Разновидностью команды повторения с предусловием является команда повторения с параметром. Она используется тогда, когда известно количество повторений действия. В блок-схеме команды повторения с параметром условие записывается не в ромбе, а в шестиугольнике. Примером циклического алгоритма с параметром будет нахождение суммы первых 20 натуральных чисел.

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

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

Табл.5. Линейный алгоритм

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

Табл.6. Разветвляющийся алгоритм

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

Табл.7. Циклический алгоритм программирования Pascal

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

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

Запишем алгоритм вычисления суммы первых n натуральных чисел. Для этого воспользуемся циклом с параметром, поскольку заранее известно сколько раз будет выполняться команда нахождения суммы. Во всех звеньях цепочки поменяем цикл «пока» на цикл «для» и приведем пример перевода алгоритма с языка блок-схем на школьный алгоритмический язык и на язык программирования Pascal.

Табл.8. Алгоритм вычисления суммы первых n натуральных чисел

2. Представление о программировании. Структурированные типы величин: константы, переменные типы величин.

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

В настоящее время существует много различных языков программирования: Кобол, С, Фортран, Visual Basic, Pascal и др.

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

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

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

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

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

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

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

Трансляторы — компиляторы и интерпретаторы

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

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

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

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

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

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

Основы языка программирования.

Первая версия языка Паскаль была разработана швейцарским ученым Никлаусом Виртом в 1968 году. Первоначально язык предназначался для целей обучения, поскольку он является достаточно детерминированным, т.е. все подчиняется определенным правилам, исключений из которых не так много. Основные характеристики: относительно небольшое количество базовых понятий, простой синтаксис, быстрый компилятор для перевода исходных текстов в машинный код. В 1992 г. фирма Borland International выпустила два пакета, основанных на языке Паскаль: Borland Pascal 7.0 и Turbo Pascal 7.0.

Основные элементы языка программирования Паскаль.

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

Язык Турбо Паскаль состоит приблизительно из 80 зарезервированных слов и специальных символов. Алфавит языка составляют буквы латинского алфавита, цифры, а также специальные символы, такие, например, как +, -, _. Специальными символами языка являются и некоторые пары символов. Как уже отмечалось, зарезервированные слова в языке Паскаль могут применяться только по своему прямому назначению, то есть в качестве имен операторов, названий операций и т. д.

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

Переменная — это ячейка (или несколько ячеек) оперативной памяти компьютера. Такой ячейке присвоено определенное имя, ее содержимое может изменяться в ходе выполнения программы.

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

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

Описание переменной начинается с зарезервированного слова Var. Затем следует сама переменная, ставится двоеточие, тип переменной и точка с запятой.

Существуют следующие типы переменных:

1. Integer (целые) – от -32 768 до +32 768.

2. Real (вещественные) – значения могут быть как дробные так и вещественные.

3. Boolean (логический) – True (истина), False (ложь).

4. Char (символьный) – @, %, $ и т.д.

5. String (строковый) – ‘доска’

Константа отличается от переменной тем, что ее значение фиксировано и не может быть изменено в ходе выполнения программы. Перед употреблением должна быть объявлена в разделе констант const. Определены два типа констант: истинные и типизированные.

Истинная константа — Она объявляется со значением. Ее тип неизвестен, поэтому ее значение в программе менять нельзя.

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

Пример: const: p:=3,14;

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

Операторы языка Паскаль бывают простыми и составными (структурными).

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

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

Массивы — это совокупности однотипных элементов. Характеризуются они следующим:

— каждый компонент массива может быть явно обозначен и к нему имеется прямой доступ;

— число компонент массива определяется при его описании и в дальнейшем не меняется.

Для обозначения компонент массива используется имя переменной-массива и так называемые индексы, которые обычно указывают желаемый элемент. Тип индекса может быть только порядковым (кроме longint). Чаще всего используется интервальный тип (диапазон).

Описание типа массива задается следующим образом:

имя типа = array[ список индексов ] of тип

Здесь имя типа — правильный идентификатор; список индексов — список одного или нескольких индексных типов, разделенных запятыми; тип — любой тип данных.

Вводить и выводить массивы можно только поэлементно.

Пример 1 . Ввод и вывод одномерного массива.

mas = array[1..n] of integer;

writeln(‘ введите элементы массива ‘);

for i:=1 to n do readln(a[i]);

writeln(‘вывод элементов массива:’);

for i:=1 to n do write(a[i]:5);

Определить переменную как массив можно и непосредственно при ее описании, без предварительного описания типа массива, например:

var a,b,c: array[1..10] of integer;

Если массивы a и b описаны как:

a = array[1..5] of integer;

b = array[1..5] of integer;

то переменные a и b считаются разных типов. Для обеспечения совместимости применяйте описание переменных через предварительное описание типа.

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

Вместе с тем, над массивами не определены операции отношения. Сравнивать два массива можно только поэлементно.

Так как тип, идущий за ключевым словом of в описании массива, — любой тип Турбо Паскаль, то он может быть и другим массивом. Например:

mas = array[1..5] of array[1..10] of integer;

Такую запись можно заменить более компактной:

mas = array [1..5, 1..10] of integer ;

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

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

for j:=1 to n do a[i,j]:=random(10);

Для «красивого» вывода матрицы на экран используется такой цикл:

for i:=1 to m do begin

for j:=1 to n do write(a[i,j]:5);

Об объектах, описываемых формулами в алгоритмическом языке Текст научной статьи по специальности «Математика»

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

i Надоели баннеры? Вы всегда можете отключить рекламу.

Похожие темы научных работ по математике , автор научной работы — Фрумкин А. М.

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

Текст научной работы на тему «Об объектах, описываемых формулами в алгоритмическом языке»

ОБ ОБЪЕКТАХ, ОПИСЫВАЕМЫХ ФОРМУЛАМИ В АЛГОРИТМИЧЕСКОМ ЯЗЫКЕ

© 2015 А. М. Фрумкин

ст. науч. сотрудник кафедры математического анализа и прикладной математики, канд. техн. наук, e-mail: frumkinamamail. ru

Курский государственный университет

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

Ключевые слова: F-операция, операция присваивания, суперпозиция, функция подстановки, дерево суперпозиции, правильная нумерация, вычисление суперпозиции, выражение.

Ранее автором статьи [Фрумкин 2014] было предложено определение формального языка как математической структуры, включающей в качестве компонентов множество описываемых объектов и семантическое отображение. Был дан вариант определения вычислительного алгоритма как композиции вычислительных операций и вариант простейшего языка для описания алгоритмов. Возможности рассматриваемого языка оказались ограниченными. Например, в нем отсутствовали формулы как инструмент описания композиций операций и, соответственно, операторы присваивания. Для того чтобы ввести в язык формулы, необходимо, чтобы на нем можно было описывать операции, ссылки на которые изображаются так же, как функции в математике. Это операции с выделенной переменной, значение которой функционально зависит от остальных. В такой форме операция определяется в большинстве языков высокого уровня. Это «процедура-функция» в языке «Паскаль» [Фаронов 1998], «функция» в языках C\C++ [Павловская 2013], «функция» в языке «Matlab» [Дьяконов 1999] и т.д. При этом в каждом языке понятие «функция» имеет свои смысловые особенности.

В данной статье в терминологии работы [Фрумкин 2014] дается формальное определение F-операции — аналога понятия процедуры-функции и исследуются возможные интерпретации суперпозиции F-операций. Таким образом, статья продолжает исследование процесса построения алгоритмического языка.

1. Обобщение определения ссылки на операцию

Определение 1. Пусть p=(Q,T,f) — вычислительная операция. Переменную aeQ назовем независимой или входной переменной операции p, если значение этой переменной после выполнения операции всегда совпадает с ее значением до выполнения операции.

Формально: V xeDm(f)eQAT [f(x)]a=xa. Переменную aeQ назовем строго зависимой или выходной переменной операции p, если значение этой переменной после выполнения операции не зависит от ее значения до выполнения операции.

[ х^((а,и)>еБш(0 л х^ еБшф ] ^ [Г(хи)]а = [Г(хи)]а. Переменную аеО назовем обычной, если множество содержит более одного элемента.

Утв. 1. Обычная переменная не может быть одновременно и входной и выходной.

^ Пусть переменная а одновременно входная и выходная. Пусть хе(0\)ЛТ, иеТ(а), уеТ(а) и и^у. Так как переменная выходная, то [Г(х^)]а = [Г(х^)]а. Так как переменная входная, то [Г(х^)]а=[х^]а=и и [Дх^)]а=[х^]а=у, то есть и=у, ■. ►

Определение 2. Пусть (О,Т) и (Л,8) — области переменных, Л и О -непересекающиеся множества: ЛпО=0. Функцию назовем подстановкой

переменных, если УаеО Т(а)=Б(^(а)).

Функция подстановки переменных не обязательно инъективна. Пусть р=(О,Т,Г) -операция и множество О упорядочено. Используя отношение порядка на О, определим вычислительную операцию (Н^^), определенную операцией р и функцией подстановки Положим Н=^(О) и 0=БН — сужение Б на Н.

Область определения g Бш(§)= < х е HЛQ: еDш(f)>. Для вычисления значения g на наборе xеDш(g) определим набор у= и вычислим z=f(y). Для каждой переменной РеН найдем а=шт Положим ир=2а. В результате получим набор значений иеНЛБ, который и будем считать значением функции g.

2. Операции с передаваемой переменной Определение 3. Операцией с передаваемой переменной (Б-операцией) назовем кортеж (О,Т,£,л:), в котором О — конечное множество внутренних переменных, л:1О -передаваемая (внешняя) переменная, Т — семейство множеств (типов) с областью индексов О^, Г Dm(f)e ОЛТ^(О^)ЛТ.

Функцию Го: хе Dш(f)^f(x)Q назовем внутренним преобразованием Б-операции. Функцию Г1=)ЛТ: хОе Dш(f) л у= Г(хО)и > назовем полным преобразованием Б-операции.

Б-операцию назовем простой, если все переменные аеО являются входными относительно операции (О^,Т,Г1), или, иными словами, если £ — тождественное отображение на своей области определения. Простая Б-операция определяет внешнюю функцию, то есть функцию, которая набору значений внутренних переменных ставит в соответствие значение передаваемой переменной.

Определение 4. Операцией присваивания, порожденной Б-операцией (О,Т,£,л:) и переменной а называется операция (Л,Б^) с компонентами:

Л=Ои, Б=Т^ и g=< (х,у): хеЛЛБ л xQеDш(f) л у=<(Р,1): (реО\л 1= [Г(хп)]р ) V (р=а л 1= [АМ]*) > >. В определении функции g набор хО обозначает сужение х на множество переменных О. Определение применимо как для случая а1О, так и для случая аеО. В последнем случае в процессе вычисления функции g значение а, вычисленное с помощью функции заменяется на значение внешней переменной л, вычисленное с помощью функции Г Из определения следует, что а является выходной переменной операции присваивания. 3. Композиции суперпозиции для операций с передаваемой переменной Б-операции можно использовать для того, чтобы ввести в алгоритмический язык формулы (алгебраические выражения) и сформулировать правила их интерпретации. Рассмотрим пример формулы:

В ней A обозначает операцию или F-операцию, B и C обозначают некоторые F-операции, x, у, z обозначают переменные. Множества переменных, участвующих в определении операций A, B, C, в формуле никак не обозначены, потому что переменные x, у, z «подставлены» на место этих переменных. Место подстановки определяют позиции между запятыми. Более того, на место двух переменных, участвующих в определении операции A, подставлены обозначения F-операций B и C. Это означает, что при вычислении по формуле мы должны сначала вычислить B(x,y) и С(у^) и затем подставить результирующие значения их внешней переменной л в формулу для А. Но в общем случае переменная х может измениться при вычислении В(х,у), а переменная у -при вычислении С(у^). Поэтому результат зависит от порядка вычислений. Далее рассматривается модель, согласно которой может интерпретироваться формула общего вида, и выбирается один из вариантов вычисления согласно данной модели.

Определение 5. Пусть (Л,Б) — область переменных, Р — множество уже определенных F-операций. Суперпозицией F-операций над областью переменных (Л,Б) назовем кортеж ^^^,ш,£,г), в котором F — конечное непустое множество позиций F-операций, V — конечное непустое множество позиций переменных, FnV=0, —

семейство F-операций, ш^^-Л — семейство переменных, P=FoV — функция

Функция g каждой позиции pеF автоматически ставит в соответствие все атрибуты F-операции g(p): О, Т, Г, л. При описании свойств функции подстановки придадим каждому символу функциональный смысл, то есть будем считать, что мы задали семейства О, Т, Г, л с одной и той же областью индексов F. Функция подстановки обладает следующими свойствами.

1) Для каждой позиции pеF и аеОр если £(p,а)еF, то Т£(р,а)(л£(р,а))=Тр(а), а если ^(р,а)е^ то Б(ш(£(р,а)))=Тр(а). Это свойство назовем свойством согласованности типов.

2) Существует единственная позиция геР, которая не является образом подстановки.

3) Функция £ инъективна: VpеF (аеОрлРеОрла^Р)^£(р,а)^£(р,Р); Vp,qеF р^ ^ V аеОр VpGОq £(р,а)^ £(^р).

4) Маршрутом подстановки £ длины п назовем последовательность р:[1..п]^Р, обладающую свойством V те[1..п-1] pmеFл Зае Орт ■ рт+1=£(рт,а). У функции подстановки отсутствуют циклические маршруты, то есть маршруты, в которых повторяются позиции.

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

Утв. 2. Пусть — суперпозиция. Определим отношения

1) оба отношения являются функциями;

2) тройка (Р,г^) является деревом [Новиков 2011], то есть Бт(^=Р\ и VqеDm(h) ЗnеN : ^(ф=г;

3) множество V есть множество терминальных узлов дерева.

^ Пусть (р^) е h л(р^) еhлq^s.

Тогда ЗaеОq, РеО./ р=£^,а), р=£^,Р). Так как £ инъективна, из q^s следует, что р^р, ■. Следовательно, h — функция.

Пусть (р,а)е9л (р,Р)е9. Тогда найдутся £(дьа)=рл£(дьР)=р. Так как £ -инъективна, то я^гл а=р. Таким образом, (р,а)е9л (р,Р)е9 ^а=Р, то есть 9 является функцией.

Из определения функции И следует, что область определения И совпадает с образом функции подстановки, то есть по свойству 2) функции £, От(Ь)=Р\. Возьмем любую позицию де Бт(Ь). Пусть для некоторого п>1 Ьп(д)=8. Если б^г, то 8еБт(Ь) и найдется 1еР: 1= Ип1(д). Если не найдется такого п, что Ип(д)=г, то последовательность Ип(д) — бесконечна. Но тогда в ней обязательно встретится повторяющийся элемент, то есть у функции £ найдется циклический маршрут, И. Следовательно, найдется такое натуральное п, что Ип(д)=г, то есть (Р,г,И) — дерево.

Если позиция ре У, то на ней не определена функция £, то есть р — терминальная позиция. Обратно, если р — терминальная позиция, то на ней не определена функция £, то есть реУ. ►

Определение 6. Дерево, определенное в последнем утверждении, назовем деревом суперпозиции. Для реБ наследников р, принадлежащих Б, назовем Б-наследниками, а наследников р, принадлежащих У, назовем У-наследниками. Для реР\ позицию И(р) будем называть родительской позицией позиции р, а переменную 9(р) — родительской переменной позиции р.

В определении суперпозиции участвуют множество переменных ш(У)^Л и семейство множеств переменных Ор, реБ. Переменные из множеств Ор будем называть формальными. Переменные из множества ю(У) будем называть фактическими. Определим Б-операцию с множеством переменных ю(У), задаваемую суперпозицией, описав процесс ее вычисления. При этом формальные переменные будем использовать для «хранения» промежуточных результатов.

Если (Б,§,У,ш,£,г) — суперпозиция, то для каждой позиции реБ множество Ор делится на два непересекающихся подмножества:

множество У-переменных Бр= и множество Б-переменных Ур=.

Определение 7. Элементарной операцией вычисления суперпозиции (Б,§,У,ш,£,г) в позиции реБ\ назовем операцию (Е^^) со следующими компонентами.

Множество переменных Е включает родительскую переменную 9(р), множество подставляемых переменных [шо£(р,-)](Др) (образ множества У-переменных) и множество Б-переменных Ур, то есть Б=^ [шо£(р,-)](Др)о> Ур.

Семейство типов Q определяется теми типами переменных из Е, которые определены моделью суперпозиции.

Вычислительное преобразование w осуществляется в следующей последовательности. Пусть хеЕ^. Сначала каждой переменной аеДр ставим в соответствие значение переменной шо£(р,а)е[шо£(р,-)](Др). В результате получаем набор значений переменных уеОрЛТр. Затем осуществляем вычисление ъ=Гр(у)е(Оро>)лтр. Далее для каждой переменной Ре[шо£(р/)](Др) найдем а=тт и положим ир=ъа. В результате получим набор значений ие[шо£(р,-)](Др)л8. Дополним этот набор сужением функции ъ на множество Б-переменных Ур и парой (9(р),г^). В результате получим набор значений w(x)е EЛQ.

Определение 8. Элементарной операцией вычисления суперпозиции (Б,§,У,ш,£,г) в позиции р=г назовем операцию с передаваемой переменной (Е^^,л:г), компоненты кортежа которой определяются так. Множество переменных Е=[шо£(г,-)](Дг)о> Уг. Семейство типов Q определяется теми типами переменных из Е, которые определены моделью суперпозиции.

При вычислении w(x) для xeEAQ сначала каждой переменной аеЛр ставим в соответствие значение переменной шо^(р,а)е[шо^(р,-)](Лр). В результате получаем набор значений переменных yeQrATr. Затем осуществляем вычисление z=fr(y)e(Qr^)ATr. Далее для каждой переменной Ре[шо^(р,-)](Лр) найдем а=шт и положим up=za. В результате получим набор значений ие[шо^(р,-)](Лр)А8. Дополним этот набор u сужением функции z на множество Yr^). В результате получим набор значений w(x)e (E^)AQ.

Для того чтобы описать последовательность вычислений, добавим в каждый из типов формальных переменных элемент е. Готическая буква «е» здесь означает «етр1у», то есть «пустой». Если набор значений xeQ^Tf, таков, что для какой-то переменной a xa=e, то xIDmfj,). Будем считать, что до начала вычисления суперпозиции заданы начальные значения переменных из ra(V), а все формальные переменные имеют значение е.

Определение 9. Пусть в множестве F n элементов и р:[1..п]оБ — нумерация множества F. Набор значений переменных xera(V)AS назовем допустимым для данной нумерации, если можно последовательно выполнить элементарное вычисление в позициях р1з р2, . рп.

Утв. 3. Для того чтобы набор xgq(V)aS был допустим для нумерации, необходимо, чтобы согласно данной нумерации каждой позиции предшествовали все ее F-наследники.

^ Любая формальная переменная aeQq может изменить свое исходное значение е только в случае, если выполнена элементарная операция в позиции ^(q,a). Если позиция ^(q,a) расположена в последовательности р после q, то при достижении в процессе вычисления позиции q окажется, что значение переменной a равно е. ^

Определение 10. Если согласно нумерации F-позиций суперпозиции каждой позиции предшествуют все ее F-наследники, то данную нумерацию назовем правильной.

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

^ Пусть нумерация правильная. Пусть q и s — две F-позиции, причем q -потомок s. Если q — наследник (непосредственный потомок) s, то, в силу правильности нумерации, s располагается после q. Если q не является наследником s, то воспользуемся индукцией по расстоянию от q до s. Позиция h(q) располагается после q в силу правильности нумерации, а s располагается после h(q) по предположению индукции. Следовательно, s располагается после q.

Обратно, если каждая позиция располагается после всех своих потомков, то, в частности, каждая позиция располагается после своих F-наследников. ^

Утв. 5. Если нумерация F-позиций является правильной, то первая позиция не имеет F-наследников, а последняя позиция является корневой.

^ Если бы первая позиция имела F-наследника, то этот наследник должен был бы располагаться перед первой позицией, И. Вторая часть утверждения является прямым следствием предыдущего утверждения. ^

Определение 11. F-операцией, порожденной суперпозицией (F,g,V,Q,^,r), и правильной нумерацией p:[1..n]oF множества F назовем кортеж (ra(V), Sro(V), w, л:г) в котором функция преобразования w определяется так. Dm(w) — множество допустимых для нумерации р наборов значений xgq(V)aS. Для допустимого набора значений x результатом преобразования является набор значений ye(ra(V)^)AS и значение

переменной л:г, полученное после выполнения всех элементарных процедур в позициях Pl, P2, . Pn.

Утв. 6. Пусть (Р^^,ш,Ъ,г) — суперпозиция и p:[1..n]oF — правильная нумерация. Возьмем позицию qeF\. Обозначим через F’ множество F-позиций, достижимых из позиции q, через V’ множество V-позиций, достижимых из позиции q, Пусть P’= V’, g’, ш’,Ъ’ — сужения функций g,ш,Ъ на множества F’, V’, F’®Q соответственно. Тогда — суперпозиция и нумерация множества F’, порожденная p, является

^ Так как Ъ’ есть сужение Ъ, то Ъ’ инъективна и обладает свойствами согласованности типов. Кроме того, не существует циклических маршрутов относительно Ъ’. Позиция q не является образом функции Ъ’. В противном случае существовал бы циклический маршрут. Таким образом, все свойства функции Ъ повторяются для функции Ъ’ , и q есть корневая позиция.

Утв. 7. Если все F-оперaции в суперпозиции просты, то любая правильная нумерация порождает одну и ту же простую F-оперaцию.

^ Воспользуемся индукцией по высоте дерева суперпозиции. Пусть утверждение верно для деревьев высоты, не большей п>2. Рассмотрим суперпозицию высоты п+1.

Корневая F-оперaция простая. Ее передаваемое значение определяется значениями ее V- и F-переменных и она не изменит значений переменных. Все F-поддеревья корня задают суперпозиции высоты, не превышающей п. Правильная нумерация позиций исходной суперпозиции определяет правильные нумерации поддеревьев. Поэтому по предположению индукции при любой нумерации значения одноименных F-переменных для коневой функции будут одинаковы. Но и значения V-переменных одинаковы и равны исходным значениям, потому что ни одна F-оперaция поддерева их не изменила. Следовательно, преобразуемый набор переменных коневой функции не зависит от нумерации. ^

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

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

4. Синтаксис выражений Синтаксические конструкции, описывающие суперпозиции в формальном языке, называют выражениями. Опишем грамматику [Ахо, Ульман 1978] выражений, которая может быть использована для усовершенствования языка из статьи [Фрумкин 2014]. Будем использовать метасимволы, определенные в упомянутой статье. Частным случаем

суперпозиции будем считать константы и переменные. Простейшая грамматика строится с помощью следующих предложений. ::= | | $ ::= ()$

Более сложная грамматика выражений, содержит обозначения алгебраических операций. С точки зрения построения алгоритмического языка алгебраические операции — это некоторые выделенные простые F-операции, для обозначения которых предусмотрены специальные символы сложения, вычитания, умножения, деления и т.д. ::= | $ ::= | ^суперпозици^ () $

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

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

Объектами, описываемыми усовершенствованным алгоритмическим языком, являются композиции операций и F-операций, которые определяют как эквивалентные операции, так и F-операции. Если в усовершенствованном языке используются различные типы данных, то заголовок процедуры, посвященной F-операции, отличается от заголовка процедуры, посвященной обычной операции, описанием типа внешней переменной. Но в нашем простейшем языке используется только один тип (целые числа), поэтому заголовок процедуры, посвященной F-операции, будет совпадать с заголовком процедуры, посвященной обычной операции. Описания операций и F-операций будут отличаться не заголовками, а наличием некоторой конструкции внутри текста. Можно предложить два варианта такой конструкции — конструкцию «return», возвращающую значение внешней переменной, или конструкцию присваивания внешней переменной ее значения. В последнем варианте фиксированное имя внешней переменной становится зарезервированным словом, таким же как «if», «while» и др. Выберем второй вариант и для обозначения внешней переменной выберем слово «passed» ( передаваемая ).

Новая версия языка отличается от версии [Фрумкин 2014] следующими особенностями:

1) в описателях if-композиций и while-композиций кроме имени управляющей переменной можно указать выражение, описывающее суперпозицию с результирующей F-операцией;

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

Далее приводится часть грамматики, связанная описанными изменениями. ::= if # (< выражение >^) # #end | if # # # else #end $

::= passed = ;$ ::= =; $ К данному набору правил добавляется более сложный вариант грамматика выражений с обозначениями алгебраических операций из предыдущего пункта.

Определение переменной — это частный случай присваивания, поэтому в новой версии языка не нужно правило:

::= =< целое число>; Элементарная операция копирования также описывается как операция присваивания. Нет упоминания ссылки, потому что понятие выражения обобщает ссылку. Элементарные операции арифметических действий описываются с помощью алгебраических выражений со стандартными обозначениями этих операций: «+», «-», «*», «/».

Приведем примеры описаний простейших алгоритмов на модифицированном

Factorial (x) % вычисление факториала положительного числа x passed=1; m=1;

i Не можете найти то, что вам нужно? Попробуйте сервис подбора литературы.

IsSimple(x) % простое ли положительное число x ? y=2; passed=1;

Приведем также пример, иллюстрирующий рассуждения из п. 3. Рассмотрим четыре вычислительных процедуры. A(x,y,z)passed=x+y+z; end B(x) x=x+2; passed =1; end C(x,y) x=x+1; passed=1; end D(x) x=xA2; passed=1; end Проанализируем процесс вычисления выражения A(x,B(x),C(x,D(x))). Согласно стандартной нумерации позиций (стандартному обходу дерева суперпозиции) процедуры выполняются в последовательности: D, B, C, A. При начальном значении x=2 результатом выполнения суперпозиции будет число 9. Если же принять другой допустимый обход, например B, D, C, A, то результатом будет число 19.

АхоА., УльманДж. Теория синтаксического анализа, перевода и компиляции. Т. 1 Синтаксический анализ. М.: Мир, 1978. 612 с.

Дьяконов В.П., Абраменкова И.В. MATLAB 5.0/5.3. Система символьной математики. М.: Нолидж, 1999. 640 с.

Новиков Ф.А. Дискретная математика. СПб.: Питер, 2011. 384 с.

Павловская Т.А. C/C++. Программирование на языке высокого уровня. СПб.: Питер, 2013. 461 с.

Фаронов В.В. Турбо Паскаль 7.0. Начальный курс. М.: Нолидж, 1998. 516 с.

Как осуществляется структурирование текста на алгоритмическом языке

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

■ Алгоритм — строго определенная последовательность действий для некоторого исполнителя, приводящая к поставленной цели или заданному результату за конечное число шагов.

Любой алгоритм составляется в расчете на конкретного исполнителя с учетом его возможностей. Исполнитель — субъект, способный исполнять некоторый набор команд. Совокупность команд, которые исполнитель может понять и выполнить, называется системой команд исполнителя.

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

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

Свойства алгоритмов

Алгоритм должен обладать определенными свойствами. Наиболее важные свойства алгоритмов:

  • Дискретность. Процесс решения задачи должен быть разбит на последовательность отдельных шагов — простых действий, которые выполняются одно за другим в определенном порядке. Каждый шаг называется командой (инструкцией). Только после завершения одной команды можно перейти к выполнению следующей.
  • Конечность. Исполнение алгоритма должно завершиться за конечное число шагов; при этом должен быть получен результат.
  • Понятность. Каждая команда алгоритма должна быть понятна исполнителю. Алгоритм должен содержать только те команды, которые входят в систему команд его исполнителя.
  • Определенность (детерминированность). Каждая команда алгоритма должна быть точно и однозначно определена. Также однозначно должно быть определено, какая команда будет выполняться на следующем шаге. Результат выполнения команды не должен зависеть ни от какой дополнительной информации. У исполнителя не должно быть возможности принять самостоятельное решение (т. е. он исполняет алгоритм формально, не вникая в его смысл). Благодаря этому любой исполнитель, имеющий необходимую систему команд, получит один и тот же результат на основании одних и тех же исходных данных, выполняя одну и ту же цепочку команд.
  • Массовость. Алгоритм предназначен для решения не одной конкретной задачи, а целого класса задач, который определяется диапазоном возможных входных данных.

Способы представления алгоритмов:

  • словесная запись (на естественном языке). Алгоритм записывается в виде последовательности пронумерованных команд, каждая из которых представляет собой произвольное изложение действия;
  • блок–схема (графическое изображение). Алгоритм представляется с помощью специальных значков (геометрических фигур) — блоков;
  • формальные алгоритмические языки. Для записи алгоритма используется специальная система обозначений (искусственный язык, называемый алгоритмическим);
  • псевдокод. Запись алгоритма на основе синтеза алгоритмического и обычного языков. Базовые структуры алгоритма записываются строго с помощью элементов некоторого базового алгоритмического языка.
Словесная запись алгоритма

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

■ Пример 1. Записать в словесной форме правило деления обыкновенных дробей.

Решение.
Шаг 1. Числитель первой дроби умножить на знаменатель второй дроби.
Шаг 2. Знаменатель первой дроби умножить на числитель второй дроби.
Шаг 3. Записать дробь, числителем которой являет результат выполнения шага 1, знаменателем — результат выполнения шага 2.

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

Формальные исполнители алгоритма

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

Программы на языке произвольного формального исполнителя могут состоять только из элементарных команд, которые входят в его систему (которые исполнитель «понимает»).

Исполнитель может иметь свою среду (например, систему координат, клеточное поле и др.). Среда исполнителя — это совокупность объектов, над которыми он может выполнять определенные действия (команды), и связей между этими объектами. Алгоритмы в этой среде выполняются исполнителем по шагам.

■ Пример 2. Исполнитель Крот имеет следующую систему команд:

  1. вперед k — продвижение на указанное число шагов вперед;
  2. поворот s — поворот на s градусов по часовой стрелке;
  3. повторить m [команда1 … командаN] — повторить m раз серию указанных команд.

Какой след оставит за собой исполнитель после выполнения следующей последовательности команд?

Повторить 5 [вперед 10 поворот 72]

Решение. Команда вынуждает исполнителя 5 раз повторить набор действий: пройти 10 шагов вперед и повернуть на 72° по часовой стрелке. Так как поворот происходит на один и тот же угол, то за весь путь исполнитель повернет на 5 х 72° = 360°. Поскольку все отрезки пути одинаковой длины и сумма внешних углов любого многоугольника составляет 360°, то в результате будет оставлен след в форме правильного пятиугольника со стороной в 10 шагов исполнителя.

Заметим, что если увеличить количество повторов серии команд, то исполнитель будет повторно передвигаться по тем же отрезкам (произойдет повторное движение по тому же пятиугольнику).

■ Пример 3. В системе команд предыдущего исполнителя Крот сформировать алгоритм вычерчивания пятиступенчатой лестницы (длина ступеньки — 10 шагов исполнителя).

Решение. За каждый шаг цикла должно происходить 4 действия: движение вперед на 10 шагов исполнителя, поворот на 90° по часовой стрелке, еще 10 шагов вперед и поворот на 90° против часовой стрелки (= 270° по часовой). В результате за один шаг цикла формируется ломаная из двух отрезков длиной 10 под прямым углом. За пять таких шагов сформируется 5–ступенчатая лестница (ломаная будет содержать 10 звеньев).

Повторить 5 [вперед 10 поворот 90 вперед 10 поворот 270]

Блок–схема

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

Основные элементы блок–схемы алгоритма:

Основные элементы блок–схемы алгоритма:

Общий вид блок–схемы алгоритма:

Общий вид блок–схемы алгоритма:

■ Пример 4. Алгоритм целочисленных преобразований представлен в виде фрагмента блок–схемы. Знаком := в нем обозначен оператор присваивания некоторого значения указанной переменной. Запись X := 1 означает, что переменная Х принимает значение 1.

Определить результат работы алгоритма для исходных данных Х = 7, Y = 12.

  1. Блок ввода данных определит исходные значения переменных Х и Y (7 и 12 соответственно).
  2. В первом условном блоке осуществляется сравнение значений Х и Y. Поскольку условие, записанное в блоке, неверно (7 < 12), происходит переход по линии «нет».
  3. Во втором условном блоке выполняется второе сравнение, которое для исходных данных оказывается верным. Происходит переход по линии «да».
  4. Вычисляется результат выполнения алгоритма: X := 0, Y := 1.

Ответ: X := 0, Y := 1.

Алгоритмические языки

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

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

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

Псевдокод

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

Служебные слова учебного алгоритмического языка:

Служебные слова учебного алгоритмического языка:

Стандартная структура алгоритма

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

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

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

В следующих строках конкретизируют, какие именно переменные являются аргументами алгоритма (входными данными), а какие — его результатами (выходными данными). Для этого после служебного слова арг приводится список имен переменных–аргументов; в следующей строке после служебного слова рез приводится список имен переменных–результатов.

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

Примеры заголовков алгоритмов:

В первом примере алгоритм имеет название Объем_шара, один вещественный аргумент Радиус и один вещественный результат Объем. Во втором примере алгоритм под названием Choice имеет три аргумента — целые M и N и логический b, а также два результата — вещественные Var1 и Var2.

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

На вход алгоритму даются два вещественных аргумента a и b (величины катетов), результатом является вещественная переменная с (гипотенуза). Для ее расчета используется функция вычисления квадратного корня sqrt.

Описание величин и действия над ними

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

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

Все величины в алгоритме разделяют на постоянные (константы) и переменные. Константа не может изменять свои значения в процессе работы алгоритма. Переменная может приобретать различные значения, которые сохраняются до тех пор, пока она не получит новое значение. Переменным величинам назначают имена. Таким образом, переменная — это именуемая величина, которая в процессе выполнения алгоритма может приобретать и хранить различные значения.

В алгоритмическом языке не существует специальных правил именования переменных. Однако их названия не должны совпадать со служебными словами алгоритмического языка. Во многих языках программирования для имен можно использовать только латинские буквы, цифры, знак подчеркивания. Имена обязательно должны начинаться с буквы, при этом строчные и прописные буквы в именах не различаются. В одном алгоритме не могут существовать разные объекты с одинаковыми именами. Все имена являются уникальными. Имена переменных и констант стараются выбирать так, чтобы они напоминали их смысл. Например, имена переменных и констант: S, p12, result, итог.

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

Величина — переменная, с которой связывается определенное множество значений. Этой величине присваивается имя (в языках программирования его называют идентификатор).

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

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

Числовой тип предназначен для обработки числовых данных. Различают целый и вещественный числовые типы. Целый тип в учебном алгоритмическом языке обозначается служебным словом цел, к нему относятся целые числа некоторого определенного диапазона. Они не могут иметь дробной части, даже нулевой. Число 123,0 является не целым, а вещественным числом. Вещественные величины относятся к вещественному типу данных и обозначаются в учебном алгоритмическом языке служебным словом вещ. Такие величины могут отображаться двумя способами: в форме с фиксированной запятой (например, 0,0511 или –712,3456) и с плавающей запятой (те же примеры: 5,11*10 -2 и –7,123456*10 2 ).

Над числовыми данными можно выполнять арифметические операции и операции сравнения.

обозначение операций

Над целыми числами можно также выполнять две операции целочисленного деления div и mod. Операция div обозначает деление с точностью до целых чисел (остаток от деления игнорируется). Операция mod позволяет узнать остаток при делении с точностью до целых чисел. Например, результатом операции 100 div 9 будет число 11, а результатом 100 mod 9 — число 1.

Литерный тип представляет собой символы и строки, он дает возможность работать с текстом. Литерные величины — это произвольные последовательности символов. Эти последовательности заключаются в двойные кавычки: «результат», «sum_price». В качестве символов могут быть использованы буквы, цифры, знаки препинания, пробел и некоторые другие специальные знаки (возможными символами могут быть символы таблицы ASCII). В учебном алгоритмическом языке литерные величины обозначаются лит.

Над литерными величинами возможны операции сравнения и слияния. Сравнение литерных величин производится в соответствии с их упорядочением: «a» < «b», «b» < «с» и т. д. Слияние (конкатенация) литерных величин приводит к образованию новой величины: «пол» + «е» образует «поле».

Логический тип определяет логические переменные, которые могут принимать только два значения — истина (True) или ложь (False). Над логическими величинами можно выполнять все стандартные логические операции.

Команды учебного алгоритмического языка

Учебный алгоритмический язык использует следующие команды для реализации алгоритма:

ОПЕРАЦИЯ ПРИСВАИВАНИЯ

Ко всем типам величин может быть применена операция присваивания, которая обозначается знаком «:=» и служит для вычисления выражения, стоящего справа, и присваивания его значения переменной, указанной слева. Например, если переменная H имела значение 12, а переменная М — значение 3, то после выполнения оператора присваивания H := М + 10 значение переменной H изменится и станет равным 13.

Вычисления в операторе присваивания выполняются справа налево: сначала необходимо вычислить значение выражения справа от знака присваивания. Поэтому допустимы конструкции вида H := Н + 10. В этом случае сначала будет вычислено выражение в правой части (12 + 10), а его результат будет присвоен в качестве нового значения переменной Н (значение 22).

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

ВВОД И ВЫВОД ДАННЫХ

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

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

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

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

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

Список вывода может содержать имена переменных, константы и выражения. Если в списке вывода указано имя переменной, будет выведено ее значение. Если список вывода содержит выражение, будет выведен результат его вычисления. Текстовые константы следует записывать в списке вывода в кавычках (выводиться они будут без кавычек).

Если при выполнении алгоритма ввести значения 20 и 10, то переменная v примет значение 20, а переменная t — значение 10. По окончании работы алгоритма будет выведен результат:

Путь 200 м

Тот же результат был бы получен, если бы изменить строку вывода на

вывод «Путь «, v * t, » м»

Конспект по информатике «Алгоритм. Свойства алгоритмов. Блок-схемы. Алгоритмические языки».

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *