Вопрос 14

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

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

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

Пример записи алгоритма на школьном АЯ:

алг Сумма квадратов (арг цел 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

кон

Вопрос 15

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

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

• program E3;

• uses crt;

• var t: real;

• begin

• clrscr;

• writeln(‘введите температуру воздуха t=’);

• readln(t);

• if t < 0 then writeln(‘одеть шубу’) else writeln(‘одеть куртку’);

• end.

Вопрос 16

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

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

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

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

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

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

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

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

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

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

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

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