Примеры спецификаций (например, для метода сортировки массива в возрастающем порядке

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

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

свойства: дискретностью, массовостью, определенностью, результативностью, формальностью.

Свойства Алгоритмов:

n Конечность

n Определенность

n Наличие входных данных

n Наличие выходных данных

n Эффективность

2. Понятие «язык программирования».

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

Среди конструкций языка выделяют операторы,

например:
y=sin(x) – оператор

Реализация языка – комплект программ, с помощью которого обеспечиваются:

n Поддержка операций с исходной программой (ввод, редактирование, сохранение текста, анализ синтаксических ошибок)

n Подготовка синтаксически правильной программы к исполнению на конкретном исполнителе

Система программированиявключает:

n Файловую систему

n Редактор для ввода текстов

n Транслятор для преобразования текстов программ к виду, в котором она может исполняться, или указания ошибок, если преобразование не удается

n Библиотеки периода трансляции

n Библиотеки периода исполнения

n Отладчик

n Пользовательские библиотеки

n Средства поддержки разработки программ

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

n Способов представления данных

n Способов вызова процедур и т.д.

3. Что включает в себя постановка задачи?

n Постановка задачи должна быть точной и подробной.

Вопросы на которые необходимо ответить:

n Каковы входные данные

n Какие данные считаются корректными, какие – нет.

n Для кого предназначено программное обеспечение?

n Какой пользовательский интерфейс следует применить?

n Какие сообщения об ошибках следует предусмотреть?

n Какие ограничения накладываются на программу?

n Существуют ли особые ситуации?

n В каком виде следует представить выходные данные?

n Какая документация должна сопровождать программу?

Этап 2. Проектирование:

n При разработке программ следует использовать модульный подход

4. Что такое спецификация программы??

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

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

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

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

n какие данные доступны каждому модулю при исполнении

n в каких условиях можно выполнять данный модуль

n какие действия выполняет модуль

n как изменяются данные после завершения его работы

Спецификация модуля:

n какие данные доступны каждому модулю при исполнении

n в каких условиях можно выполнять данный модуль

n какие действия выполняет модуль

n как изменяются данные после завершения его работы

n спецификация модуля не должна описывать метод решения задачи!!!

Спецификация включает в себя:

предусловия и

постусловия функции

Примеры спецификаций (например, для метода сортировки массива в возрастающем порядке

//сортировка массива

//предусловие: переменная А является массивом

//состоящим из N целых чисел, N>0

// постусловие: целые числа в массиве A упорядочены.

Достаточно ли этих пред- и постусловий?

Очевидно, что нет:

n Во-первых, не указано в каком порядке необходимо упорядочить числа

n Во-вторых, не указано, насколько большим может быть число элементов в массиве N.

Пересмотренная спецификация: Sort(A,N)

//сортировка массива в возрастающем порядке

//предусловие: переменная А является массивом

//состоящим из N целых чисел,1<=N<=MAX_N

// где MAX_N – глобальная константа

//задающая максимальный размер массива А

// постусловие: целые числа в массиве A упорядочены

// по возрастанию: A[1]<=A[2]<= …<= A[N]

// число N не изменилось

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

n В постусловии описываются результаты работы функции (либо возвращаемое функцией значение) и все последствия ее работы.

Понятие Инварианта. Инвариант цикла.

Инвариант – это условие, которое должно всегда быть истинным в некоторой точке программы

Инвариант цикла – это условие, которое должно выполняться до и после каждого выполнения цикла.

Использование инварианта цикла для решения следующей задачи: вычислить сумму первых n элементов массива А:

//вычисляет сумму элементов A[0],A[1], … A[n-1]

// для любого n>0

int j=0; sum=0;

while (j<n)

{

sum+=A[j];

++j;

} // конец оператора while

Инвариант данного цикла: значение переменной sum равно сумме элементов A[0]+A[1]+ … +A[j-1], j – значение параметра цикла

Инвариант данного цикла:

//вычисляет сумму элементов

//A[0],A[1], … A[n-1] для любого n>0

int j=0, sum=0;

***

while (j<n)

{ ***

sum+=A[j];

++j;

***

} // конец оператора while

***

n Инвариант должен быть истинным изначально

n Выполнение цикла должно сохранять инвариант

n Из выполнения инварианта должна следовать правильность алгоритма

n Цикл должен завершиться

7. Что такое защитное программирование? Перечислите пути реализации защитного программирования.

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

Защитное программирование реализуется двумя путями:

n во-первых, необходимо придерживаться определенного стиля программирования,

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

Простота реализации

n При разработке проекта программы из нескольких равнозначных решений следует выбирать наиболее простые (но не примитивные!).

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

Пример неоправданной сложности:

for (i=0; i<n; i++)

for (j=0;j<n; j++)

v[i][j]=(i/j)*(j/i);

Правильный вариант:

for (i=0; i<n; i++)