учебное пособие. Часть1. Информатика

Контрольные вопросы

1. Какое значение получит переменная s после выполнения следующих операторов:

float s=0; int i=0;

while(i<5) i++;s+=1/i;

2. Какое значение получит переменная s после выполнения следующих операторов:

float s=0; int i=0;

while(i<5){ i++; s+=1./i;}

3. Какое значение получит переменная s после выполнения следующих операторов:

float s=0; int i=0; do

{ i++; s+ = 1./i ;} while (i<5)

4.Чем отличается оператор цикла с предусловием от оператора цикла с постусловием?

5.Какие возможности предоставляет оператор цикла со счетчиком?

6.Для чего используются в операторах цикла операторы break, continue.

7.Можно ли изменять переменную цикла в операторе цикла со счетчи- ком с шагом 0.1?

8.Как будет выглядеть фрагмент схемы алгоритма, соответствующий следующему фрагменту программы:

for (i = 0; i < n; i = i+2) k = k*i;

9.Какие ошибки допущены в следующем фрагменте программы: for (i=0; i<n) { k=k*i; ; i=i+2 }

10.Сколько операторов может выполняться в теле оператора цикла с постусловием?

3.4. Жизненный цикл программного обеспечения

Жизненный цикл программного обеспечения (ПО) – совокупность взаи-

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

191

Основные этапы жизненного цикла:

1.Проектирование

2.Изготовление

1. Эксплуатация и сопровождение. Проектирование включает:

•разработка технического задания (ТЗ). ТЗ включает постановку зада- чи, определение потоков входных, выходных параметров, технико- экономические требования (назначение ПО, основные функции, ожидаемая эффективность, стоимость и сроки разработки, надежность и т. д.). Таким об- разом, определяются требования к ПО и составляются спецификации.

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

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

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

Изготовление ПО включает:

•программирование (кодирование).

•отладка.

•верификация (проверяется, работает ли программа в соответствии со спецификацией).

•испытание (тестирование автономное и комплексное).

Эксплуатация и сопровождение включают:

•выявление ошибок при эксплуатации и исправление их.

•совершенствование системы (модификация и модернизация).

Рис. 15. Каскадная модель ЖЦ

192

Описанный процесс не столь прямолинеен. На каждом этапе возможен возврат к предыдущим этапам, квалифицируемый как требование повторить этап для исправления обнаруженной ошибки. Рассматривают различные мо- дели жизненного цикла программного обеспечения. Самыми распространен- ными являются каскадная и спиральная модели (рис. 15, рис. 16) [13].

Рис. 16. Спиральная модель ЖЦ

3.4.1. Постановка задачи и спецификация программы

При постановке задачи устанавливается основное назначение, техниче- ские характеристики, показатели качества и технико-экономические требова- ния к программе. Все эти требования записываются в техническом задании. ТЗ разрабатывается заказчиком и согласовывается с разработчиком. В ТЗ описываются:

•потоки входных, выходных и управляющих параметров;

•ожидаемая экономическая эффективность;

•стоимость разработки;

•сроки разработки;

•состав и характеристики входной информации (помехоустойчивость, интенсивность поступления и т.д.);

•основные характеристики и тип ЭВМ, на которой будет эксплуатиро- ваться программное обеспечение;

•требуемый уровень функциональных характеристик – устойчивость к искажающим воздействиям, надежность, точность и т. д.;

•дружественный интерфейс;

•простота сопровождения;

•приспособленность к модернизации;

193

• состав документации (код программы, инструкция по эксплуатации и

т. д.).

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

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

значение

{Q} S {R},

где Q и R – предикаты, а S – программа (последовательность команд), имеет следующую интерпретацию: если выполнение S началось в состоянии, удовлетворяющем Q, то имеется гарантия, что оно завершится через конеч- ное время в состоянии, удовлетворяющем R.

Под программой в данном определении понимается один или несколь- ко отдельных операторов или же действительно целая большая программа.

Предикат Q называется предусловием или входным утверждением S; R – постусловием или выходным утверждением программы.

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

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

Приведем несколько примеров.

Пример1: записать в z произведение a и b, предполагается, что значе- ния a и b – положительные числа.

{a ³ 0 Ù b ³ 0} S {z = a * b}

Здесь Ù - логическая операция «И».Если заданы начальные значение переменных, то спецификация выглядит так:

{a³ 0 Ù b ³ 0 Ù a = A Ù b = B} S {z = a * b Ù a = A Ù b = B }

Пример2: присвоить x абсолютное значение x.

{x = X} S {(X £ 0 Ù x = -X ) Ú (X ³ 0 Ù x = X)}

Пример3: обмен значениями переменных.

{x = X Ù y = Y} S {x = Y Ù y = X}

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

194

Спецификация {i=0} «i++;» {i=1} является тавтологией. Спецификация {i=0} «i++;» {i=0} ложна во всех состояниях.

Спецификация {i=0} «i++;» {i=j} истинна при j=1 и ложна в остальных состояниях.

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

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

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

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

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

3.4.2. Анализ и корректность программ. Основы доказательства правильности программ

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

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

Статический контроль включает в себя:

•синтаксический контроль программы с помощью компилятора, при котором проверяется соответствие текста программы синтаксическим прави- лам языка программирования;

•построение списка идентификаторов и списка операторов;

•верификацию программ, то есть аналитическое доказательство кор- ректности программ.

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

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

195

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

•корректность как точное соответствие целям разработки программы (которые отражены в спецификации) при условии ее завершения или частич- ная корректность;

•завершение программы, то есть достижение программой в процессе

еевыполнения своей конечной точки.

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

1) доказательство частичной корректности;

2) доказательство частичной некорректности;

3) доказательство завершения программы;

4) доказательство незавершения программы; 5) доказательство тотальной (полной) корректности (то есть одновре-

менное решение первой и третьей задач); 6) доказательство некорректности (решение второй или четвертой за-

дачи).

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

Наиболее известным из методов доказательства частичной корректно- сти программ является метод индуктивных утверждений, предложенный Флойдом и усовершенствованный Хоаром. Метод состоит из следующих этапов:

• построение структурной схемы (граф-схемы) программы;

• формулирование входных и выходных утверждений;

• поиск всех циклов и формулирование индуктивных утверждений для

них;

•формирование списка выделенных путей;

•построение условия верификации с использованием семантики опера- торов программы;

•формулирование условий верификации;

•доказательство, что выполнение программы завершится.

Доказательство неистинности условий корректности свидетельствует

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

196

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

Решить задачу верификации можно, либо следуя сверху вниз (от вход- ных данных к выходному результату), либо снизу вверх (выходных результа- тов к исходным данным).

Динамический контроль программы – это проверка правильности про- граммы при ее выполнении на компьютере, т. е. тестирование.

Рассмотрим пример из книги Д. Гриса «Наука программирования», де- монстрирующий формулирование утверждений.

Пусть требуется вычислить частное и остаток от деления неотрица- тельного числа х на положительное число y.

Если х=7, а у=2, то получим q=3, r=1

Фрагмент программы, определяющий частное и остаток от деления, выглядит так:

r = x; q = 0; while ( r>y )

{r = r - y; q = q + 1;}

После выполнения программы всегда можно проверить ее правиль- ность с помощью формулы:

x = y*q + r

Дополним программу оператором вывода: r = x; q = 0;

while ( r>y )

{r = r - y; q = q + 1;}

printf (" y*q + r =%d”, y*q + r)

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

assert( x == y*q + r );

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

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

Добавим входное и выходное утверждения: assert( y>0 );

r = x; q = 0; while ( r>y )

{r = r - y; q = q + 1;} assert( x == y*q + r );

197

Эта программа работает не правильно: при x=6 y=3 получаем q=1,

r=3.

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

assert( y>0 ); r = x; q = 0; while ( r>=y )

{r = r - y; q = q + 1;} assert( x == y*q + r && r<y);

Может случиться так, что и х окажется отрицательным, усиливаем ут- верждение:

assert( y>0 && x>=0 ); r = x; q = 0;

while ( r>=y )

{r = r - y; q = q + 1;}

assert( x == y*q + r && r<y && r>=0);

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

assert( y>0 && x>=0 ); r = x; q = 0;

assert( x == y*q + r && 0<y && r>=0); while ( r>=y )

{assert( x == y*q + r && 0<y && y<=r); r = r - y; q = q + 1;

assert( x == y*q + r && 0<y && r>=0);

}

assert( x == y*q + r && r<y && r>=0);

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

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

3.4.3. Основные принципы тестирования

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

198

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

осуществления текущего контроля состояния разработки отдельных модулей программ [15].

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

Суть автономного тестирования заключается в контроле отдельного программного модуля. Для организации автономного тестирования необхо- димо знать структуру модуля и его внешние связи.

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

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

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

При тестировании приемлемости проверяется соответствие программы требованиям пользователя.

И, наконец, при тестировании настройки осуществляется проверка приспособленности программы к настройке на различные условия ее приме- нения.

Хотя подготовка тестов и само тестирование часто имеют уникальный характер, но можно выделить общие принципы тестирования:

•хорош тест, для которого высока вероятность обнаружить ошибку, а не тот, который демонстрирует правильную работу программы;

•не следует тестировать свою собственную программу, так как при этом невольно будет проявляться тенденция к нарушению первого принципа;

199

•вычисление и описание ожидаемых результатов должно быть произ- ведено заранее;

•документировать и хранить тесты нужно в такой форме, чтобы их

можно было использовать повторно;

•следует готовить тесты для всего возможного диапазона исходных данных и предусматривать наряду с правильными («разумными») исходными данными и неправильные;

•следует детально анализировать результаты каждого теста;

•следует помнить, что по мере роста числа ошибок, обнаруженных в n- модуле программы, растет относительная вероятность существования в этом модуле необнаруженных ошибок;

•поручать тестирование следует самым опытным и способным про- граммистам;

•никогда нельзя приспосабливать программу к тестированию – всякая измененная (упрощенная) программа есть новая программа (а не тестируе- мая);

•всякое тестирование следует начинать с постановки цели;

•следует тщательно продумать и обосновать критерии завершенности тестирования.

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

Тестирование отличается от отладки программ и по времени, и по цели проведения. Отличие это заключается в том, что отладка проводится тогда, когда программа заведомо еще не работоспособна. Если программа внешне функционирует правильно, то приступают к тестированию и проводят его с целью выявления скрытых ошибок [15].

3.4.4. Критерии качества программы

Основные критерии качества программ:

1.Корректность – программа должна соответствовать своему назначе- нию и выполнять функции, заданные в техническом задании.

2.Надежность – программа должна работать на заданном подмножест- ве исходных данных.

3.Устойчивость к искажающим воздействиям.

4.Точность вычислений.

5.Эффективность (рациональность) – использование, по возможности, минимального количества ресурсов, как по памяти, так и по времени.

200