Понятие алгоритма и его свойства

4. Индексу i, определяющему порядковый номер элемента, присваивается значение 1. При i = 1 происходит обращение к первому элемента вектора, т.е. а₁.

5. К сумме S (на первом шаге i = 1, S = 0 и a_i = а₁) прибавляется значение элемента вектора a_i (S := S + a_i). В области памяти S записывается новое значение суммы.

6. С увеличением значения  i на 1 (i = i + 1) определяется порядковый номер следующего элемента вектора.

7. Количество  элементов вектора равно n. Отсюда, операция суммирования S := S + a_i должна повторяться n раз, для чего осуществляется проверка: продолжать вычисление суммы или нет. Для выбора направления вычислений применяется символ «Решение». Внутри него указывается проверка условия i <= n. Если значение i не превысило своего максимального значения n, то операция вычисления суммы повторяется (переход к шагу 5), в противном случае осуществляется переход к шагу 8.

8. Осуществляется  вывод полученной суммы S. Эта операция отображается на схеме символом «Ввода-вывода», внутри которой указывается, что именно выводится.

9. Схема заканчивается  символом «Пуск-останов».

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

Пример 3. Рассмотрим алгоритм вычисления корней квадратного уравнения .

1. Ввести исходные  данные a, b, c.

2. Вычислить  .

3. Если d 0, то 

§ ;

§ ;

§ ;

§ Вывести результаты на печать;

§ Конец вычислений.

иначе

§ Вывести сообщение  «Действительных корней нет»;

§ Конец вычислений.

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

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

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

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

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

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

Рис. 1.3. Общий вид алгоритма на псевдокоде

Часть алгоритма  от слова алг до слова нач называется заголовком, а часть, заключенная между словами нач и кон -- телом алгоритма.

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

 

 

Пример 4. Запись на псевдокоде алгоритма вычисления суммы квадратов целых чисел от 1 до n.

алг Сумма квадратов (арг цел n, рез цел S)

дано | n > 0

надо | S = 1*1 + 2*2 + 3*3 + ... + n*n

нач цел i

ввод n; S:=0

нц для i от 1 до n

S:=S+i*i

кц

вывод "S = ", S

кон

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

Следовательно, язык для записи алгоритмов должен быть формализован. Такой язык принято  называть языком программирования, а запись алгоритма на этом языке -- программой для компьютера.

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

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

· машинные;

· машинно-оpиентиpованные (ассемблеpы);

· машинно-независимые (языки высокого уровня).

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

Языки высокого уровня делятся на:

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

· логические (Prolog, Lisp и др.), ориентированные не на разработку алгоритма решения задачи, а на систематическое и формализованное описание задачи с тем, чтобы решение следовало из составленного описания;

· объектно-ориентированные (Object Pascal, C++, Java и др.), в основе которых лежит понятие объекта, сочетающего в себе данные и действия над нами. Программа на объектно-ориентированном языке, решая некоторую задачу, по сути описывает часть мира, относящуюся к этой задаче. Описание действительности в форме системы взаимодействующих объектов естественнее, чем в форме взаимодействующих процедур.

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

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

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

Пример 5. Программа на языке ассемблера для IBM PC, вычисляющая значение a = b + c для целых a, b и c:

Программа	Пояснение
MODEL SMALL DATA b DW 5 c DW 3 a DW ? CODE begin MOV AX,@DATA MOV DS,AX MOV AX,B ADD AX,C MOV A,AX MOV AH,4CH INT 21H END begin	Директива задает механизм распределения памяти под  данные и команды. Директива определяет начало участка программы с данными. Директивы DW задают типы переменных и их значения. Директива CODE определяет начало участка программы с командами. Команды MOV AX,@DATA и MOV DS,AX записывают адрес сегмента данных в регистр DS (Data Segment). Для вычисления a используются команды MOV AX,B, ADD AX,C и MOV A,AX. В директиве END задана метка первой выполняемой  программы программы begin.

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

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

· алфавит алгоритмического языка значительно шире алфавита машинного языка, что существенно  повы шает наглядность текста программы;

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

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

· требуемые операции задаются с помощью общепринятых математических обозначений;

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

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

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

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

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

· Синтаксис -- это набор правил, устанавливающих, какие комбинации символов являются осмысленными и правильными предложениями на этом языке.

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

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

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

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

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

1. Имена (идентификаторы) -- употpебляются для обозначения объектов пpогpаммы (пеpеменных, массивов, функций и дp.).

2. Опеpации. Типы операций:

· аpифметические опеpации: +, , *, / и дp.;

· логические опеpации и (AND), или (OR), не (NOT);

· опеpации отношения <, >, <=, >=, =, <>;

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

3. Данные -- величины, обpабатываемые пpогpаммой. Имеется тpи основных вида данных:

· Константы -- данные, зафиксированные в тексте программы и не изменяемые в процессе ее выполнения. К ним относятся:

- числовые константы: 7.5, 12;

- логические: да (истина, true), нет (ложь, false);

- символьные (содержат  ровно один символ) "А", "+";

- литеpные (содержат  произвольное количество символов) "a0", "Мир", ""(пустая строка).

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

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

4. Выpажения -- пpедназначаются для выполнения необходимых вычислений, состоят из констант, пеpеменных, указателей функций (напpимеp, exp(x)), объединенных знаками опеpаций.

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

Различают выражения:

· арифметические - служат для определения одного числового значения. Например, (1+sin(x))/2;

· логические - описывают некоторые условия, которые могут удовлетворяться или не удовлетворяться. Логическое выражение может принимать только два значения -- "истина" или "ложь" (да или нет). Например, логическое выражение x*x + y*y < r*r определяет принадлежность точки с координатами (x, y) внутренней области круга радиусом r c центром в начале координат. При x=1, y=1, r=2 значение этого выражения -- "истина", а при x=2, y=2, r=1 -- "ложь";

· строковые (литерные) - их значениями являются текcты. В строковые выражения могут входить литерные и строковые константы, литерные и строковые переменные, литерные функции, разделенные знаками операции конкатенации. Например, А + В означает присоединение строки В к концу строки А. Если А = "куст ", а В = "зеленый", то значение выражения А + В есть "куст зеленый".

5. Операторы (команды) -- это наиболее крупные и содержательные понятия языка: каждый оператор представляет собой законченную фразу языка и определяет некоторый вполне законченный этап обработки данных. В состав опеpатоpов входят: