Программа как математический объект: Методические указания для самостоятельного изучения темы и выполнения РГР, страница 28

Задачи для проектирования предлагаются студентам из [1, 8, 10].

5.1.1 Анализ и проектирование

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

При разработке алгоритма используйте метод пошаговой разработки.

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

1)  средства, предоставляемые тем языком, на котором алгоритм будет запрограммирован; (для выполнения данного задания этот фактор не существенен)

2)  структуры данных, на которые ориентирован проект;

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

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

5.1.2 Тестирование

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

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

Язык описания проектов PDL и язык конечных автоматов.

Примеры описания проектов на PDL приведены в 1.7.1, 1.7.2.

Примеры описания проектов в терминах конечных автоматов приведены 2.3.1, 2.3.2.

5.2 Верификация программ

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

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

При доказательстве необходимо использовать теорему правильности (4.3.3,[12, 6.2, стр.218]).

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

Примеры определения программных функций и их верификации см.(4.5.1 примеры 1,2). Верификация при проектиров см. 5.3.

5.3 Построение инвариантов

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

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

Как правило в этом задание используются результаты, получаемые в втором пункте задания. При построении инварианта необходимо использовать теорему об инвариантах (4.5.1, 4.5.2, 4.5.3 [12, 6.6, стр. 281]). Инвариант должен характеризовать функцию.

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

Верификацию при проектировании  и построение инварианта рассмотрим на примере задачи 2 из 1.7.2. Выберем подзадачу поиска конца последовательности.