Разработка программы начинается с этапа постановки задачи. На этом этапе необходимо уточнить все неясные моменты в условии задачи.
Конечный результат работы программы во многом зависит от того, насколько корректно и четко сформулирована задача, а также от того, насколько правильно поняли друг друга заказчик и программист, поэтому необходим постоянный тесный контакт между заказчиком и программистом.
В нашем случае в роли заказчика выступает преподаватель, а в роли программиста – студент. Причем, если заказчик не смог до конца сформулировать задачу, то вся дополнительная работа по переделке программы в итоге ляжет на программиста!
Постановка задачи завершается созданием технического задания (ТЗ) и внешней спецификации программы, которая включает:
· описание исходных данных. При этом следует учитывать, что здесь речь идет не об описании переменных в терминах языка программирования, а о задании формата данных при вводе, например:
o действительное число вводится в виде цепочки цифр, максимальная длина которой равна 20,
o в качестве разделительного символа целой и дробной частей может использоваться как точка, так и запятая;
o нулевая целая часть может присутствовать или отсутствовать (например, 0.123 или ,123),
o наличие знака перед числом необязательно. При отсутствии знака число трактуется как положительное.
· описание результатов (типы, форматы, точность, способ передачи, ограничения), например:
o результат выдается в нормализованном виде со знаком с точностью до 15 цифр после запятой;
o для представления порядка используются 4 цифры, включая знак;
· описание алгоритма, реализуемого программой;
· способ обращения к программе;
· описание возможных аварийных ситуаций и ошибок пользователя.
Таким образом, программа рассматривается как «черный ящик», для которого определены функции, а также входные и выходные данные. Для реализации указанных функций необходимо разработать внутренние структуры данных.
Большинство алгоритмов зависит от организации данных, поэтому этап проектирования программы начинается не с алгоритма, а с разработки структур для хранения и обработки (возможно, что они будут различные) входных, промежуточных и выходных данных. При этом нужно учитывать: ограничения на размер данных, необходимую точность их представления, требования к быстродействию программы. На данном этапе разработки программы следует также решить, применение каких структур данных – статических или динамических – лучше учитывает специфику решаемой задачи.
После определения структур данных приступают к проектированию, т.е. к определению общей структуры и порядка взаимодействия модулей.
Для этого разрабатывается алгоритм решения задачи на языке некоторой гипотетической машины, способной выполнять самые обобщенные действия. Каждое такое действие в дальнейшем детализируется. При этом очень важной является спецификация интерфейсов, т.е. способ взаимодействия подзадач.
Для каждой подзадачи разрабатывается своя внешняя спецификация, проектируются отдельные модули, взаимодействие которых минимизируется. Одна задача может реализовываться несколькими модулями и, наоборот, несколько подзадач – одним модулем. Только после проектирования верхнего уровня переходят к проектированию нижних уровней. Алгоритм записывают в обобщенной форме с использованием любой нотации. Если описание алгоритма затруднительно, то, скорее всего, он плохо продуман. На данном этапе следует также предусмотреть возможность и простоту дальнейших модификаций программы. Однако не следует приносить в жертву простоту программы ради возможности ее последующего усовершенствования, так как практика показывает, что та избыточная функциональность, на которую вы ориентируетесь сегодня, завтра может оказаться абсолютно ненужной.
После проектирования кодируются и отлаживаются модули верхнего уровня, причем в местах вызова модулей нижнего уровня ставятся так называемые «заглушки», которые могут либо выдавать сообщение о передаче им управления, либо предлагать использовать значения, вычисленные по упрощенному алгоритму. Таким образом, сначала задается логический скелет программы, который постепенно обрастает «плотью» кода. При кодировании сверху вниз на верхних уровнях, могут быть вскрыты трудности проектирования более низких уровней, так как при написании программы ее логика продумывается более тщательно, чем при проектировании. Для отладки каждого модуля и более крупных фрагментов требуется составлять свои тестовые примеры и программист часто вынужден имитировать то окружение, в котором должен работать модуль. При нисходящей технологии программирования обеспечивается естественный порядок создания тестов и появляется возможность нисходящей отладки.
При программировании следует отделять интерфейс (функций, процедур, модулей, классов) от его реализации, и ограничивать доступ к ненужной информации. Этапы проектирования и кодирования совмещены во времени; в идеале проектируется и кодируется верхний уровень, затем следующий и т.д. Таким образом, можно при необходимости вносить изменения в модуль нижнего уровня.
Проектирование и кодирование сопровождается тестированием и отладкой написанных частей программы. Для оценки правильности работы программы производится ее тестирование, для чего необходимо разработать специальные тесты двух типов: функциональные («черный ящик») и структурные («стеклянный (белый) ящик»). Чтобы избежать влияния стереотипов алгоритмов на тестирование, тесты следует создавать до разработки программы, а не во время ее разработки или после нее.
Набор тестов должен быть простым и полным для активизации всех ветвей алгоритма, но не избыточным, то есть таким, что удаление из этого набора любого теста лишает его полноты.
Только после того как логическое ядро полностью протестировано, и есть уверенность в правильности реализации основных интерфейсов, приступают к разработке тестов и кодированию нижних уровней. При этом готовится не один тест, а совокупность тестовых наборов для всех возможных, пограничных и запредельных ситуаций.
Функциональные тесты проверяют правильность работы программы по принципу: «не знаю как сделано, но знаю, что должно быть в результате, и именно это и проверяю».
К функциональным тестам относятся:
· «тепличные», проверяющие программу при корректных, нормальных значениях исходных данных;
· «экстремальные» («стресс–тесты»), находящиеся на границе области определения (например, наибольшая или наименьшая нагрузка системы по количеству или по времени), проверяющие поведение системы в экстремальных ситуациях, которые могут произойти и на которые программа должна корректно реагировать.
· «запредельные» («тесты обезьяны»), выходящие за границы области определения (а возможно, и здравого смысла), проверяющие ситуации, бессмысленные с точки зрения постановки задачи, но которые могут произойти из-за ошибок пользователя (корректная реакция системы на запрещенный или неподдерживаемый ввод и т.п., так называемая «защита от дурака»)
Структурные тесты контролируют (тестируют) работу всех структурных частей программы (функций, процедур, модулей, основной программы) по всем возможным маршрутам (ветвям программы).
При структурном тестировании необходимо осуществлять контроль:
· обращений к данным (т.е. проверять правильность инициализации переменных; а также размеры массивов и строк; отслеживать, не перепутаны ли строки со столбцами; соответствуют ли входных и выходных значений выбранным типам данных; проверять правильность обращения к файлам и т.п.);
· вычислений (порядок следования операторов и запись выражений; переполнение разрядной сетки или получение машинного нуля; соответствие результата заданной точности и т.п.);
· передачи управления (завершение циклов, функций, программы);
· межмодульных интерфейсов (списки формальных и фактических параметров; отсутствие побочных эффектов, когда подпрограмма изменяет аргументы, которые не должны меняться и т.п.).
Искусство тестирования сводится к разработке простого, полного и не избыточного набора тестов, а технология тестирования – к испытанию программы на всем наборе тестов, после внесения в нее каждого изменения.
Заказчик (преподаватель) и программист (студент) осуществляют функциональное тестирование методом «черного ящика», а программист – структурное тестирование методом «белого ящика», стараясь пройти по всем ветвям алгоритма. Однако следует помнить, что основной недостаток структурного метода тестирования заключается в том, что он принципиально не позволяет найти пропущенный маршрут.
Говорить о надежности программы можно в том случае, если она способна принимать корректные данные и получать для них правильные результаты либо отвергать некорректные данные по возможности с указанием причины. Тестирование должно происходить автоматически, (с возможностью коррекции), с подготовкой входных тестовых наборов в файлах или массивах и сравнением полученных результатов с выходными тестовыми значениями.
В случае, когда задачи некритичны к содержимому входных массивов (данных), можно использовать рандомизацию (случайные исходные данные). Для подготовки автоматических тестов можно написать специальную программу – генератор тестов. Это менее трудоемко, чем подготавливать тесты вручную.
Таким образом, защита разработанной программы сводится к демонстрации ее работоспособности на совокупности тестов, а именно – к совместной защите набора тестов, алгоритма и программы.
Все функциональные тесты должны быть написаны до выполнения программы, структурные тесты могут дополняться по мере отладки и корректировки программы.
Цель тестирования – установление факта наличия ошибок в программе, то цель отладки – это выявление, локализация и устранение ошибок.
Все ошибки в программах можно разделить на следующие виды:
· трансляции (компиляции), т.е. ошибки синтаксиса языка;
· компоновки (ошибки связи);
· выполнения , которые в свою очередь делятся на: а) ошибки логики (семантические); б) ошибки накопления погрешностей; в) ошибки данных
Синтаксические ошибки, как правило, первыми отслеживаются компилятором. Ошибки связи (компоновки) – это несоответствие количества фактических и формальных параметров, вызов несуществующих процедур и функций, неподключение необходимых библиотек и т.п. Сообщения о наличии таких ошибок также могут выдаваться на этапе компиляции программы.
После устранения первых двух видов ошибок программа поступает на выполнение, и на этом этапе могут возникнуть ошибки данных в операциях ввода–вывода, связанные с передачей, преобразованием или перезаписью данных, например, выход за диапазон допустимых значений при вводе, или ввод неверных по типу данных. И, наконец, последними обнаруживаются ошибки выполнения, например. при равенстве нулю знаменателя или при отрицательном подкоренном выражении и пр. Обнаружение этих ошибок также сопровождается сообщениями компилятора.
После того, как и эти ошибки будут ликвидированы, необходимо сравнить полученные результаты выполнения программы с результатами теста. Если они не совпали друг с другом, то это значит, что программа может содержать следующий вид ошибок: ошибки накопления погрешностей и ошибки логики (семантические).
Ошибки накопления погрешностей результатов вычисления заключаются в некорректном отбрасывании дробных цифр числа, некорректном использовании приближенных методов вычисления, в игнорировании ограничений разрядной сетки ЭВМ и т.п.
Ошибки логики (семантические), которыми могут быть вызваны следующими причинами:
некорректным использованием переменных (попытка использовать переменную до ее инициализации, использование индексов, выходящих за границы массивов и т.п.);
ошибками вычисления (некорректное использование целочисленной арифметики, незнание приоритетов выполнения операций и т.п.);
ошибками межмодульного интерфейса (игнорирование системных соглашений при передаче параметров, нарушение области действия локальных и глобальных переменных и т.п.);
неправильной реализацией алгоритма программы.
Семантические ошибки – самые непредсказуемые ошибки. Они могут иметь разную природу, при этом часть из них обнаруживается ОС, а часть – нет, поэтому написание полных тестов – необходимая задача программиста!
Эффективность программы оценивается потребляемыми программой ресурсами:
1) быстродействием, которое определяется количеством выполняемых операций в единицу времени, с учетом трудоемкости каждой из них, то есть, в конечном итоге, временем решения задачи определенной размерности;
2) объемом оперативной памяти (ОП), выделяемой (запрашиваемой) под данные.
Эти показатели порой противоречат друг другу: например, если увеличивается, быстродействие, то требуется дополнительный расход памяти. Если можно улучшить один показатель без ущерба для другого, то это следует делать. Однако, если возникает дилемма, то предпочтение следует отдавать экономии памяти в ущерб производительности, так как тактовая частота растет опережающими темпами по сравнению с объемом ОП.
Обычно программы отлаживаются на примерах небольшой размерности, но в реальных задачах с существенной размерностью показатели трудоемкости могут оказаться важными. В то же время некоторые задачи, имеющие факториальную зависимость трудоемкости от размерности, в состоянии «подвесить» любой ПК даже на маленьких задачах, так что проблема эффективности не снимается с ростом производительности компьютера.
Существует ряд мер для повышения эффективности программ:
1) не использовать рабочие массивы того же порядка размерности, что и обрабатываемый или создаваемый, если это возможно. Например, использовать одномерный массив для хранения строки или столбца матрицы при ее обработке;
2) использовать, где можно, короткие типы данных. Например, Byte вместо Word, String[20] вместо String;
3) использовать поименованные константы вместо неоднократного повторения констант-«близнецов»;
4) при обращении к процедурам (особенно рекурсивным) передавать параметры по адресу, а не по значению, использовать локальные переменные;
5) выбирать эффективные алгоритмы по числу операций, предварительно оценив порядок зависимости трудоемкости от размерности (логарифмическая, линейная, полиномиальная, факториальная и др.);
6) избегать вычислений в циклах выражений, не зависящих от параметра цикла (например, sin (Pi /n), где n не меняется в цикле), имея в виду, что трансцендентные функции вычисляются трудоемким разложением в ряд.
7) прекращать вычисления, когда результат достигнут, либо когда становится очевидным, что он не может быть достигнут за приемлемое время. Для этого использовать циклы типа While, Repeat…Until вместо For. Не рекомендуется обращаться к неструктурным средствам принудительного завершения программы типа Goto, Halt, Break и др., так как они сильно уменьшают наглядность программы и часто приводят к неожиданным последствиям. Это не значит, что их надо бояться, как огня, просто перед их использованием надо подумать;
8) выбирать, где возможно, наименее трудоемкие операции. Например,
N Div K вычисляется быстрее, чем Trunc(N/K) и к тому же дает гарантировано точный результат. Другой пример: Odd (N) более эффективно, чем N Mod 2.
Программа – это детальный план действий для решения некоторой задачи. Автор программы должен доказать, что задача действительно решена и подтвердить это тестированием.
Программы часто разрабатываются коллективом авторов, каждый из которых должен понимать ход мыслей другого. Кроме того, программа создается для использования не разработчиками, а для других пользователей. Следовательно, механизм ее работы должен быть понятен из текста программы, а не только из документации. Отсюда вытекает необходимость писать комментарии к программе.
Комментарии к программе должны содержать следующее: описание алгоритмов, описание проблемных мест программы (там где долго кодировали – сделайте комментарии!); описание процедур программы (входные и выходные параметры и их назначение). Программист сможет прочесть любую программу, разобраться в ней, если она хорошо прокомментирована. При этом комментарии не должны давать расшифровку операторов, а должны указывать, как решается (реализуется) та или иная конкретная задача.
Для улучшения стиля программирования рекомендуется
1) использовать осмысленные имена для глобальных переменных и короткие имена – для локальных;
2) давать схожим объектам схожие имена;
3) разбивать сложные выражения на более простые;
4) поддерживать стилевое единство оформление текста программы, лучше общепринятое (отступы, комментарии, скобки и т.п.), а не свое;
5) использовать символьные константы, а не их коды,
т.е., вместо: If ( (C >= 65) And (C <= 90)
использовать: If (C >= ‘A’) And (C <= ‘Z’), что значительно нагляднее
6) писать комментарии.
Итак, сформулируем основные требования к созданию программы:
1) надежность – адекватная реакция на любые действия пользователя;
2) сдача программы в срок (точное планирование производства программ);
3) возможность сопровождения (понятные комментарии).
На лабораторных работах по курсу «Типы и структуры данных» к сдаче принимаются отлаженные программы, которые должны содержать:
1) описание условия задачи;
2) техническое задание;
3) описание использованных структур данных и алгоритма решения задачи;
4) набор тестов с указанием для каждого теста, что он проверяет;
5) необходимые комментарии к программе;
6) оценку эффективности работы программы, т.е. подсчет времени выполнения программы и требуемой памяти при применении различных структур данных.
Все логически завершенные фрагменты алгоритма должны быть оформлены в виде отдельных подпрограмм. Выбор языка программирования осуществляется студентом.
1. Какие этапы разработки программного обеспечения существуют?
2. Что такое внутренние структуры данных?
3. Что такое тестирование и отладка программ. Какова их взаимосвязь?
4. На каком этапе разработки программ создаются тесты?
5. Какие типы тестов бывают?
6. Какие виды ошибок существуют в программах?. Какова последовательность поиска ошибок?
7. Чем определяется эффективность программ?