35 Билет. Понятие структурного программирования, этап проектирования - композиция и декомпозиция, понятие статической и динамической структуры программы, спецификация программы.

Структурное программирование (сверху вниз) делится на 3 этапа.

1) Проектирование сверху вниз.

2) Модульное программирование.

3) Структурное кодирование.

Проектирование сверху вниз можно описать следующим образом:

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

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

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

Этап проектирования - композиция и декомпозиция.

Понятие статической и динамической структуры программы.

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

Статическая структура не зависит от значения исходных данных.

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

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

Любой оператор в программе или изменяет состояние вычислений или анализирует и принимает решение об изменение вычислительного процесса.

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

На каждой структурной схеме определены состояния вычислений с помощью соотношений, которые должны выполняться для входных данных, промежуточных и для окончательных результатов. Фундаментальным свойством всех способов композиции является возможность объединения в одну сложную схему любого количества различных стр. ?????схем и тогда в самом общем виде стр. схему можно представить в виде (1) {P}S{Q}

Если соотношение P верно перед выполнением S, то после завершения P будет истинно выражение Q.

Если S это программа, правильность которой мы хотим доказать, то необходимо доказать эту нотацию (1) где P- соотношение, накладываемое на входные данные, а Q - на выходные.

ПРО СПЕЦИФИКАЦИЮ ЕЩЕ НИЧЕГО НЕТУ.

36 Билет. Понятие частичной и полной корректности программы, правила вывода - общий вид, правила консеквенции.

Понятие частичной и полной корректности программы.

??????????????????????????????????????????????

Правила вывода - общий вид:

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

Если над чертой истинные выражения, то и под чертой истина.

Первое правило консеквенции.

Если выполнение S для P приводит к R, то выполнение S приведет к выполнению любое соотношение следующее из R. ????

Второе правило консеквенции.

Если R - соотношение следующее из P, и выполнение S для R приводит к Q, то выполнение S для P также приведет к Q.

37 билет. Правила вывода для операторов С/C++, пустого, присваивания, составного.

Для пустого:

{P}{P}

Для присваивания

{Pe}x=e;{P}

?????????????

Cоставной оператор/последовательная композиция

----S1 -->S2 --> ... --> Sn -->

Описание правила.

Если S есть { } и если имеет место {P} {R}; {R} {Q} , то истинно и {P} { } {Q}.

Для составного оператора.

В общем виде:

38 Билет. Правила вывода для операторов ветвления.

Правило вывода сокращенного условного оператора.

39 Билет. Правила вывода для циклов с предусловием и постусловием.

Предусловие:

Постусловие:

40 Билет. Пример доказательства правильности программы.

41. Статические и динамические переменные, динамическая память, работа с динамическими переменными.

Память на основании описания - статическая, а переменные в ней - статические переменные.

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

Каждая статическая переменная описана в каком-то блоке программы и имеет собственное имя, идентификатор, с помощью которого к ней и обращаются.

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

int x = 15 // статическая переменная занимает 4 байта памяти

int *x

x = new (int) - выделяет в динамической памяти место для хранения величины целого типа и адрес этой области памяти присваивается указателю x . ? )

x - имя указателя

значение - адрес байта

оператор cout <<x<< '\t' << '\t' << x

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