Реализация алгоритма на ЭВМ

.

Здесь мы рассмотрим проблему реализации алгоритма на ЭВМ. Однако, прежде введем ряд понятий.

Определение 9.1. Программа - алгоритм, представленный в форме пригодной для его восприятия и выполнения ЭВМ.

Определение 9.2. Алгоритмический язык - формальная алгоритмическая система, предназначенная для реализации алгоритмов на ЭВМ.

Итак, в чем суть рассматриваемой проблемы? Программа, т.е. реализация алгоритма на ЭВМ, должна удовлетворять ряду требований:

Программа должна быть эффективной:

восприниматься однозначно;

не требовать больших затрат на подготовку к выполнению и хранение;

быстро выполняться ЭВМ.

Преобразование алгоритма в форму программы человеком должно быть эффективным:

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

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

Программа должна быть легко читаемой и понимаемой разными людьми;

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

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

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

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

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

Заметим, что под множеством допустимых исходных данных программы мы понимаем область применимости ее алгоритма, представленную в надлежащей форме.

Итак, алгоритм должен быть записан на алгоритмическом языке, чтобы быть исполненным. Сам алгоритмический язык должен быть с одной стороны понятен ЭВМ, а с другой - он должен быть достаточно выразителен для человека. Чтобы удовлетворять первому условию, алгоритмический язык должен иметь:

строго определенный синтаксис и словарь.

словарь должен содержать только те действия и типы данных, с которыми может работать ЭВМ.

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

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

данные, представленные константами и переменными;

тип данных, как множество возможных значений;

выражения, как действия, определяющие правило вычисления значения; Действия в выражениях называются операциями.

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

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

Рассмотрим пример.

Пример 9.1.

Написать программу на Pascal, вычисляющую сумму гармонического ряда, т.е. ряда вида . Эта программа представлена на рис. 9.1.

Program Harmonic (input, output);

{ Программа Harmonic вычисляет сумму n первых членов гармонического ряда от 1 до п ;

Input: (пÎN)Ù(п>0);

Output: ;

}

1. varn, i : integer; {n - количество суммируемых членов ряда;

i - параметр цикла

};

s : real; {s - суммаряда};

begin

{Ввод исходных данных}

write (¢Введите п= ¢) ; {Приглашение к вводу}

readln (n) ; {Ввод исходных данных}

{Проверка исходных данных}

if n>0 then

{Вычисление суммы ряда}

begin

s:=1 ; {Инициализация цикла}

i:=1;

while i<n do {Суммирование}

begin

i:= i+1;

s:= s +1/i

end;

{Вывод результата}

writeln (¢Сумма¢, п , ¢ членов гармонического ряда = ¢ ,s)

end {Вычисление суммы ряда}

elsewriteln (¢Ошибка в исходных данных n должно быть >0¢)

end {Program}.

Рис. 9.1. Программа для примера 9.1.

На этом рисунке строки 1 и 2 определяют набор используемых в программе переменных и их типы. Операторы в строках 3 и 4 обеспечивают ввод исходного значения n . Операторы в строках 5 и 6 определяют начальные значения надлежащих переменных перед входом в цикл. В строках 7 и 8 записан оператор цикла, организующий вычисление суммы первых n членов гармонического ряда. Последовательность действий i:=i+1; s:=s+1/i будет выполняться до тех пор, пока выражение i<n будет иметь значение истина. Как только при очередном вычислении значения этого выражения будет получено значение ложь, то будет выполняться действие в строке 9, где стоит оператор вывода полученной суммы.

Конструкции i<n , i+1 , s+1/i в строках 7 и 8 рисунка 9.1 - выражения. Выражение s+1/i определяет правило вычисления очередной промежуточной суммы ряда. Конструкции s:=1 и i:=1 - примеры действий, изменяющие значения переменных, а следовательно, изменяющие состояние вычислительного процесса.

Символ ; обозначает последовательную композицию двух действий. Так, например, запись в строках 7 и 8: s:=s+1/i ; i:=i+1 означает, что сначала состояние вычислительного процесса изменится, т.к. изменится значение переменной s , а потом оно изменится еще раз, т.к. изменится состояние i .

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

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

как представляются константы и переменные;

какие типы данных есть в этом языке;

как записываются выражения;

как записываются действия последовательной композиции, выбора и повторения;

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

Обратите внимание, не исполняться, а использоваться для построения других программ.

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

программа на этом языке должна быть пригодна для восприятия компьютером;

программа на этом языке должна быть понятной для человека.

Ниже, на рис. 9.2 представлена программа из примера 9.1. в форме, ясной для ЭВМ.

Program Harmonic (input, output);

var n, i : integer ;

s : real ;

begin

write (¢Введитеп = ¢) ;

readln (n) ;

s:=1 ;

i:=1;

while i<n do begin i:=i+1; s:=s+1/i ; end ;

writeln (¢Сумма п членов гармонического ряда =¢, s)

end.

Рис. 9.2.

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

Синтаксис и Семантика.

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

Например, в Pascal'е есть понятие имени. Переменная, функция, процедура, равно как и программа на Pascal'е имеют имя. Синтаксис этого понятия “имя” - последовательность букв и цифр, начинающаяся с буквы.

Другой пример - синтаксис оператора присваивания. Примером оператора присваивания может служить конструкция s:=s+1/i из строки 7 на рис. 9.1. Синтаксис оператора присваивания:

<переменная>:=<выражение>.

Здесь синтаксическая конструкция <переменная> должна всегда стоять слева от символа := алфавита языка Pascal, а синтаксическая конструкция <выражение> - справа от него. Если мы теперь определим, что в каких-то случаях <переменная> есть <имя>, то тем самым мы определим синтаксис понятия "переменная", так как синтаксис понятия "имя" мы уже определили ранее. На семинарских занятиях Вы подробно ознакомитесь как с разными способами определения синтаксиса конструкций языка Pascal, так и с синтаксисом самих этих конструкций.

Несколько замечаний необходимо сделать о наборе символов, использование которых допускается в программе на языке Pascal. Наряду с символами латинского алфавита и цифрами в этот набор входит небольшое количество вспомогательных символов. Необходимо знать ограничения этого набора символов, определяемого стандартом ASCII - Американский Стандартный Код для Обмена Информацией.

В ASCII набор, например, не входят математические символы S, £, ", $ и т.д. Часто этот набор расширяют национальными алфавитами. Например, программисты в России должны иметь возможность писать комментарий по-русски.

Под семантикой той или иной языковой конструкции понимается ее смысл. Для примера рассмотрим фразу: "На столе лежит карандаш.". Мы знаем, какие объекты реального мира обозначаются словом "стол", какие объекты обозначаются словом "карандаш" и что обозначает слово "лежать". Заметим, что, например, слово "стол" обозначает сразу множество объектов реального мира, а не один какой-то конкретный объект.

Если мы увидим фразу: "Стол съел карандаш", то без дополнительных комментариев она для нас бессмысленна, так как объекты реального мира, обозначаемые словом стол, не могут ничего и никого съесть. Таким образом, конструкции языка могут быть корректны синтаксически, а семантически - нет.

Итак, семантика - это отображение, соответствие между конструкциями языка и объектами из некоторого множества объектов, называемого миром или Universum. Так, в примере со столом, когда фраза, пусть даже синтаксически правильная, описывала ситуацию, не согласующуюся со здравым смыслом (столы не могут никого/ничего есть), мы рассматривали эту фразу как бессмысленную, т.е. семантически не корректную. Что же это означает применительно к языкам программирования?

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

Поскольку программа - суть алгоритм, оформленный должным образом, то все вышесказанное справедливо и по отношению к программе. Вернемся к нашему примеру 9.1 и рассмотрим выполнение этой программы для n=5.

После выполнения строки 4 переменная n примет значение 5, а значения переменных s и i будут неопределенными. Обозначим это состояние так - (5, ", "). После строки 5 мы получим состояние (5, ", 0), затем (5, 1, 0). Вся последовательность состояний приведена на рис 9.3.

Рис. 9.3.

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