ПРИЕМЫ ОБРАБОТКИ ИНФОРМАЦИИ, РАЗРАБОТКА СХЕМ И ТЕСТИРОВАНИЕ ПРОГРАММ. Кафедра геоинформационных систем приемы обработки информации, разработка схем и тестирование программ лабораторный практикум по дисциплине "Технология программирования" Часть 1 Уфа 2005 4
 Скачать 1.11 Mb.
|
|
3 Федеральное агентство по образованию Государственное образовательное учреждение высшего профессионального образования Уфимский государственный авиационный технический университет Кафедра технической кибернетики Кафедра геоинформационных систем ПРИЕМЫ ОБРАБОТКИ ИНФОРМАЦИИ, РАЗРАБОТКА СХЕМ И ТЕСТИРОВАНИЕ ПРОГРАММ Лабораторный практикум по дисциплине “Технология программирования” Часть 1 Уфа 2005 4 Составители: В. Н. Мукасеева, Г. М. Сайфутдинова УДК 004.43: С++ (07) ББК 32. 973. 26 – 018.1 (я7) Приемы обработки информации, разработка схем и тестирование программ: Лабораторный практикум по дисциплине “Технология программирования”. Ч.1. / Уфимск. гос. авиац. техн. ун-т; Сост. В. Н. Мукасеева, Г. М.Сайфутдинова - Уфа, 2005. – 35 с. Содержатся сведения, касающиеся разработки алгоритмов обработки информации, соответствующих алгоритмам схем программ согласно ГОСТ 19.701-90 и методов тестирования программ с применением этих схем. Излагаются теоретические сведения о подходах и методах тестирования, о файловых структурах данных и их обработке. Приводятся описания операторов обработки файловых данных на языке программирования С++, примеры разработки алгоритмов обработки информации и соответствующих им схем программ. Теоретический и методический материалы сопровождаются примерами практических заданий. Лабораторный практикум используются в курсах лабораторных работ по дисциплине “Технология программирования” для студентов, обучающихся по направлению 230100 - Информатика и вычислительная техника, специальностей 230101 – Вычислительные машины, комплексы, системы и сети, 230102 – Автоматизированные системы обработки информации и управления, 230104 – Системы автоматизированного проектирования, 230201 – Информационные системы и технологии. Табл.7. Ил.10. Библиогр.: 7 назв. Рецензенты: доктор техн.наук Р.А. Мунасыпов; канд.техн.наук Р.Р.Каримов © Уфимский государственный авиационный технический университет, 2005 5 Содержание Введение 4 Лабораторная работа 1. Тестирование методами 5 “белого ящика” 1 Цель работы 5 2 Краткие теоретические сведения. Методы “белого ящика” 5 2.1 Метод покрытия операторов 6 2.2 Метод покрытия решений (покрытия переходов) 6 2.3 Метод покрытия условий 7 2.4 Критерий решений (условий) 7 2.5 Метод комбинаторного покрытия условий 8 3 Методика выполнения работы 10 3.1 Правила применения символов и линий в схемах программ 10 3.2 Пример разработки схемы программы 12 3.3 Порядок выполнения работы 15 4 Содержание отчета 15 5 Контрольные вопросы 16 6 Варианты заданий 16 6 Введение Задачей 90-х годов и начала XXI века стало совершенствование качества компьютерных приложений, которое целиком определяется эффективностью и возможностями программного обеспечения. К этому периоду наметился разрыв между возможностями аппаратной и программной составляющих автоматизированных систем, обусловленный как расширением сфер автоматизации (автоматизироваться стали предметные области, в которых задачи либо слабо формализуются, либо не формализуются вовсе), так и сложностью программного обеспечения. Основным подходом к решению проблемы является технология создания такого программного обеспечения, которое надежно и эффективно работает в компьютерных приложениях. Дисциплина “Технология программирования” посвящена изучению теоретических основ промышленного конструирования программных систем. Дисциплина охватывает широкий круг вопросов, таких, как методики разработки программ, способы разработки эффективных программ, разработка программ с защитой от ошибок, разработка спецификаций программ, методы тестирования и отладки программ и др. Практическое усвоение вопросов дисциплины происходит на протяжении всего периода обучения в вузе таким направлениям и специальностям, как информатика и вычислительная техника, автоматизированные системы обработки информации и управления, системы автоматизированного проектирования и ряд других. В предлагаемых методических указаниях отражен лишь малый круг вопросов: разработка эффективных алгоритмов обработки данных и отображения этих алгоритмов в виде схем программ, а также тестирование программ на основе таких схем. Выполнение описанных в методических указаниях лабораторных работ должно помочь студенту в усвоении правил специфицирования программ согласно ГОСТ, общих правил кодирования обработки файловой информации и проектирования тестов для разработанных программ с целью установления соответствия спецификациям. 7 Лабораторная работа 1 Тестирование программ методами “белого ящика” 1. ЦЕЛЬ РАБОТЫ Усвоение студентами методов тестирования логики программы, формализованного описания результатов тестирования и стандартов по составлению схем программ. 2. КРАТКИЕ ТЕОРЕТИЧЕСКИЕ СВЕДЕНИЯ. МЕТОДЫ СТРАТЕГИИ „БЕЛОГО ЯЩИКА‟ Тестирование программного обеспечения охватывает целый ряд видов деятельности, аналогичных последовательности процессов разработки программного обеспечения. В него входят /1/: а) постановка задачи для теста, б) проектирование теста, в) написание тестов, г) тестирование тестов, д) выполнение тестов, е) изучение результатов тестирования. Решающую роль играет проектирование тестов. Возможны разные подходы к проектированию тестов. Первый состоит в том, что тесты проектируются на основе внешних спецификаций программ и модулей, либо спецификаций сопряжения программы или модуля. Программа при этом рассматривается как „черный ящик‟ (стратегия „черного ящика‟ или функциональный подход). Существо такого подхода - проверить соответствует ли программа внешним спецификациям. При этом логика модуля совершенно не принимается во внимание. Второй подход основан на анализе логики программы (стратегия „белого ящика‟ или структурный подход). Существо подхода - в проверке каждого пути, каждой ветви алгоритма. При этом внешняя спецификация во внимание не принимается. Тестирование по принципу белого ящика характеризуется степенью, какой тесты выполняют или покрывают логику (исходный текст программы). Покажем реализацию разных методов структурного тестирования на примере, фрагмент схемы программы которого приведен на рис. 2.1. 8 Рисунок 2.1 Фрагмент схемы программы 2.1. Метод покрытия операторов Целью этого метода тестирования является выполнение каждого оператора программы хотя бы один раз. Для фрагмента на рис. 2.1 можно выполнить каждый оператор, записав один единственный тест, который реализовал бы путь ace. Т.е., если бы на входе было: А=2, В=0, Х=3, каждый оператор выполнился бы один раз. 2.2. Метод покрытия решений (покрытия переходов) Согласно данному методу каждое направление перехода должно быть реализовано по крайней мере один раз. Покрытие решений обычно удовлетворяет критерию покрытия операторов. Поскольку каждый оператор лежит на некотором пути, исходящем либо из оператора перехода, либо из точки входа программы, при выполнении каждого направления перехода каждый оператор должен быть выполнен. Для программы, приведенной на рисунке 2.1, покрытие решений может быть выполнено двумя тестами, покрывающими пути {ace, abd}, либо {aсd,abe}. Пути {aсd,abe}покроим, выбрав следующие исходные данные: {A=3, B=0, X=3} и {A=2, B=1, X=1}. X=X/A A>1 and B=0 A=2 or X>1 X=X+1 a b Y Y C e N d N 9 2.3. Метод покрытия условий Лучшие результаты по сравнению с предыдущими методами может дать метод покрытия условий. В этом случае записывается число тестов, достаточное для того, чтобы все возможные результаты каждого условия в решении выполнялись по крайней мере один раз. В предыдущем примере имеем четыре условия: {A>1, B=0}, {A=2, X>1}. Для реализации метода требуется достаточное число тестов, такое, чтобы реализовать ситуации, где A>1, A1, B=0 и B0 в точке а и A=2, A2, X>1 и X1 в точке в. Тесты, удовлетворяющие критерию покрытия условий и соответствующие им пути: A=2, B=0, X=4 ace A=1, B=1, X=0 abd. 2.4. Критерий решений (условий) Критерий покрытия решений/условий требует такого достаточного набора тестов, чтобы все возможные результаты каждого условия в решении выполнялись по крайней мере один раз, все результаты каждого решения выполнялись по крайней мере один раз и, кроме того, каждой точке входа передавалось управление по крайней мере один раз. Два теста метода покрытия условий а) A=2, B=0, X=4 ace б) A=1, B=1, X=0 abd отвечают и критерию покрытия решений/условий. Это является следствием того, что одни условия приведенных решений скрывают другие условия в этих решениях. Так, если условие А>1 будет ложным, транслятор может не проверять условия В=0, поскольку при любом результате условия В=0, результат решения ((А>1)&(В=0)) примет значение ложь. Следовательно, недостатком критерия покрытия решений/условий является невозможность его применения для выполнения всех результатов всех условий. Другая реализация рассматриваемого примера приведена на рисунке 2.2. Многоусловные решения исходной программы разбиты на отдельные решения и переходы. Для удовлетворения критерию решений необходимо покрытие тестами всех результатов каждого простого решения. Для этого нужно покрыть пути HILP (тест А=2, 10 В=0, Х=4), HIMKT (тест А=3, В=1, Х=0), HJKT (тест А=0, В=0, Х=0), HJKR (тест А=0, В=0, Х=2).. Рисунок 2.2. Реализация фрагмента программы с простыми логическими условиями Протестировав алгоритм на рисунке 2.3, нетрудно убедиться в том, что критерии покрытия условий и критерии покрытия решений/условий недостаточно чувствительны к ошибкам в логических выражениях. 2.5. Метод комбинаторного покрытия условий Критерием, который отчасти более чувствителен к ошибкам в логических условиях, является комбинаторное покрытие условий. Он требует создания такого числа тестов, чтобы все возможные комбинации результатов условия в каждом решении выполнялись по крайней мере один раз. Набор тестов, удовлетворяющих критерию комбинаторного покрытия условий, удовлетворяет также и критериям покрытия решений, покрытия условий и покрытия решений/условий. По этому критерию в рассматриваемом примере должны быть покрыты тестами следующие восемь комбинаций: а) A>1, B=0; б)A>1, B0; в) A1, B=0; A> 1 B=0 A=2 X>1 X=X+1 Y Y Y Y N N M P R X=X/A L I H J K T 11 г) А1, B0; д) A=2, X>1; е) A=2, X1; ж) А2, X>1; з) А2, X1; Для того чтобы протестировать эти комбинации, необязательно использовать все 8 тестов. Фактически они могут быть покрыты четырьмя тестами: - A=2, B=0, X=4 {покрывает а, д}; - A=2, B=1, X=1 {покрывает б, е}; - A=0,5, B=0, X=2 {покрывает в, ж}; - A=1, B=0, X=1 {покрывает г, з}. Результаты тестирования рекомендуется представлять в виде нижеприведенной таблицы 2.1. Таблица 2.1 Итоги тестирования программы Тест Путь Ожидаемый результат Фактический результат Результат тестирования А=2, В=0, Х=4 асе X=3 X= А=2, В=1, Х=1 аве X=2 X= А=0, В=0, Х=2 аве X=3 X= А=1, В=0, Х=1 abd X=1 X= В графу “фактический результат” записываются получаемые при прогоне значения выходных переменных. Если эти значения совпадают с ожидаемыми, то в программе ошибка не обнаруживается и в графе “результат тестирования” записываем “неуспешно”, что может свидетельствовать как об отсутствии ошибок, так и о наличии в программе ошибок, которые данным тестом не были найдены. 12 3. МЕТОДИКА ВЫПОЛНЕНИЯ РАБОТЫ 3.1. Правила применения символов и линий в схемах программ Структурные методы тестирования программ требуют разработки схемы программы и выделения в ней всевозможных путей выполнения. Практика показывает, что построение схемы программы вызывает большие трудности, чем само кодирование алгоритма преобразования информации, поэтому подробно остановимся на правилах разработки схем согласно ГОСТ 19.701-90. В этом стандарте каждой группе действий ставится в соответствие специальный блок, перечень этих блоков и контекст их применения приведен в приложении А. Символ предназначен для графической идентификации функции, которую он отображает, независимо от текста внутри символа. Большинство символов обеспечивает возможность включения текста внутри символа. Символы должны быть, по возможности, одного размера. Символы могут быть вычерчены в любой ориентации, но, по возможности, предпочтительной является горизонтальная ориентация. Зеркальное изображение формы символа означает одну и ту же функцию, но не является предпочтительным. Минимальное количество текста для понимания функции символа следует помещать внутри символа. Текст должен записываться слева направо и сверху вниз независимо от направления потока. Если объѐм текста внутри символа превышает его размеры, следует использовать символ комментария. Текст комментариев должен быть помещен около ограничивающей фигуры. Хотя этот стандарт предусматривает блоки для обозначения циклов, он не запрещает и произвольной передачи управления, т. е. допускает использование команд условной и безусловной передачи управления при реализации алгоритма. Вы, наверное, обратили внимание, что в основные конструкции не вошел цикл с заданным числом повторений (счетный цикл) - обозначает повторение некоторых действий указанное количество раз. С использованием символов стандарта ГОСТ 19.701-90 такой цикл в схемах программ может быть представлен так, как изображено на рис. 3.1, на котором обозначены: начальное значение переменной цикла I 13 имеет значение n1, конечное значение – n2, а шаг изменения переменной цикла равен h. I=n1,n2,h Рис. 3.1. Счетный цикл Потоки данных или потоки управления в схемах показываются линиями. Направление потока слева направо и сверху вниз считается стандартным. В случаях, когда необходимо внести большую ясность в схему (например, при соединениях), на линиях используются стрелки. Если поток имеет направление, отличное от стандартного, стрелки должны указывать это направление. В схемах следует избегать пересечения линий. Пересекающиеся линии не имеют логической связи между собой, поэтому изменения направления в точках пересечения не допускаются, что иллюстрируется рисунком 3.2. Рисунок 3.2. Пересекающиеся линии Две или более входящие линии могут объединяться в одну исходящую линию, место объединения должно быть смещено как показано на рисунке 3.3. Рисунок 3.3. Объединение потоков информации Действие 14 Линии в схемах должны подходить к символу либо слева либо сверху, а исходить либо справа, либо снизу. Линии должны быть направлены к центру символа. При необходимости линии в схемах следует разрывать для избежания излишних пересечений или слишком длинных линий, а также, если схема состоит из нескольких страниц. Соединитель в начале разрыва называется внешним соединителем, соединитель в конце разрыва - внутренним соединителем. 3.2. Пример разработки схемы программы Рассмотрим построение схемы программы (алгоритма обработки) для программы расчета суммы бесконечного знакопеременного ряда: 1-1/2 2 +1/3 2 -1/4 2 + . . . Общий член ряда выражается формулой (-1) (N-1) / 2 N , а сумма ряда равна Pi 2 /12, где Pi – число =3,14…….. Сумма членов бесконечной последовательности a 1 , а 2 , а 3 , . . . , a N , . . . называется бесконечным рядом и записывается в виде a 1 + а 2 + а 3 + . . . + a N + . . . . Здесь a N - общий член ряда. Сумма конечного числа членов ряда называется частичной суммой и обозначается S N Если сумма членов бесконечного ряда имеет конечный предел S,то ряд называется сходящимся. Для сходящегося ряда вычисляется последовательность частичных сумм с заданной погрешностью delta (погрешность должна иметь порядок значений 3 5 10 10 ). Если точное значение суммы ряда S известно, абсолютная погрешность расчетов определяется по формуле Eps=abs(S-S N ), либо Eps=abs(a N ), если значение S неизвестно. Относительная погрешность расчетов определяется по формуле Eps_o=abs((S-S N )/S), либо Eps_o=abs(a N /S N ). Частичные суммы вычисляются по формуле:S N =S N-1 + a N Часто студенты записывают в программе оператор вычисления очередного члена рассматриваемого ряда в виде: 2 / )) 1 ln( * exp( : N N a N , которая, по сути, отражает формулу общего члена ряда, однако, стандартные программы вычисления логарифма определяют значения функции для аргументов, больших нуля. Следовательно, нужно искать другой способ для нахождения очередного члена рассматриваемого нами ряда. Достаточно часто в бесконечных сходящихся рядах N-й член ряда выражается через (N-1)-й, например, для рассматриваемого ряда 15 коэффициент изменения (аналог коэффициента геометрической прогрессии) может быть определен следующим образом: k = а N /а N-1 = ((-1) (N-1) / 2 N )/ 2 2 ) 1 /( ) 1 ( N N = - 2 2 / ) 1 ( N N (1). Следовательно, очередной член ряда N a , начиная со второго, будем рассчитывать по формуле 2 2 1 / ) 1 ( * N N a a N N Следует отметить, что с точки зрения экономичности разрабатываемой программы, описанный выше прием разработки алгоритма является наиболее удачным, поскольку в вычислениях отсутствуют обращения к функциям, требующие наибольших затрат машинного времени. В итоге можем словесно сформулировать алгоритм обработки данных для программы расчета суммы знакопеременного ряда следующим образом: а) задать точность расчета суммы delta; б) присвоить начальное значение суммы ряда (это значение равно первому элементу ряда, а именно, 1), очередному члену ряда (это значение тоже равно первому члену ряда) и начальное значение номера члена ряда N=1; в) увеличить номер члена ряда на 1, рассчитать очередной член ряда по формуле (1) и добавить полученное значение к сумме ряда для получения частичной суммы; г) определить абсолютную погрешность вычисления суммы ряда и сравнить ее с заданной точностью delta; д) выполнять пункты б-г до тех пор, пока абсолютная погрешность вычисления суммы не окажется меньше заданной delta; е) вывести на печать полученное приближенное значение суммы ряда и точное значение (в нашем примере это Pi 2 /12). На рисунке 3.4 приведена соответствующая описанному алгоритму схема программы. Схема начинается и заканчивается терминаторами “начало” и “конец”. Алгоритмом предусматриваются циклические вычисления членов ряда и частичной суммы ряда, однако схема выполнена без символов начала и конца цикла, что стандартом допускается. Примечание. Обратите внимание, что надписи в символах схемы поясняют смысловое содержание преобразований информации. Студенты часто делают ошибку, и в надписях повторяют операторы программы. Такая схема мало информативна, часто непонятна программисту, знающему другой язык программирования, нежели автор схемы. Особенно 16 Рисунок 3.4. Схема программы вычисления с заданной точностью суммы знакопеременного бесконечного ряда Ввести точность delta Наращивание переменной цикла цц Вычисление очередного члена ряда Определение частичной суммы Инициализация нач. значений Начало |a n | < delta Да Конец s : = 1 n : = 1 a n : = 1 n : = n+1 a n := -a n* (n-1) 2 /n 2 S : = S+a n модуль очередного члена ряда меньше заданной точности? печать приближѐнного и точного значений Нет 17 бесполезными бывают такие схемы для программ без комментариев. С целью углубленного изучения вопроса о построение схем программ рекомендую обращаться к литературным источникам последних лет издания, таким, как / 4,5 /. Тестирование разработанной программы структурными методами будет заключаться в задании разных значений delta из указанного диапазона и прогонах программы с новыми значениями точности delta. 3.3. Порядок выполнения работы 1. Написать программу, реализующую заданный преподавателем алгоритм обработки данных. 2. Отобразить алгоритм решения задачи в виде схемы программы. 3. Обозначить буквами или цифрами ветви алгоритма. 4. Выбрать метод тестирования, который, по Вашему мнению, может дать наибольшую вероятность обнаружения ошибок в программе. 5. Выписать пути алгоритма, которые должны быть проверены тестами для выбранного метода тестирования. 6. Записать тесты, которые позволят пройти по путям алгоритма, выбранными Вами в п.5. 7. Протестировать разработанную Вами программу. Результаты оформить в виде таблицы (см. таблицу 2.1). 8. Оформить отчет по лабораторной работе. 4. СОДЕРЖАНИЕ ОТЧЕТА 1. Сформулировать цель работы (цель Вашей работы не совпадает с целью лабораторной работы вообще, она, Ваша цель, более конкретна и определяется заданной преподавателем задачей обработки информации). 2. Записать программу решения поставленной Вам задачи. 3. Отобразить схему программы. 4. Мотивировать выбор метода тестирования. Перечислить реализующие выбранный метод тестирования пути алгоритма и тесты для прохождения этих путей. 5. Привести таблицу тестирования программы. 18 6. Записать выводы по результатам тестирования (не забывайте, что целью тестирования является обнаружение ошибок в программе). 5. КОНТРОЛЬНЫЕ ВОПРОСЫ 1. Какие подходы к тестированию программ Вы знаете? В чем разница этих подходов? 2. Что является основой для структурного тестирования? 3. Какие методы структурного тестирования Вы знаете? Каковы недостатки этих методов и пути их устранения? 4. Что является целью тестирования? Какие выводы можно сделать, если тестирование не обнаруживает ошибок программы? 5. Для чего предназначены схемы программ? Какие основные правила построения схем программ Вы знаете? 6. Перечислите правила применения символов в схемах программ. 7. Перечислите правила соединения символов в схемах программ. 6. ВАРИАНТЫ ЗАДАНИЙ 1. Идентифицировать треугольник по трем сторонам (остроугольный, прямоугольный, тупоугольный, равносторонний, равнобедренный). 2. Идентифицировать четырехугольник по четырем сторонам (квадрат или ромб, прямоугольник, трапеция или обыкновенный четырехугольник). 3. Идентифицировать треугольник по двум сторонам и углу между ними (остроугольный, прямоугольный, тупоугольный, равносторонний, равнобедренный). 4. Определить, является ли заданное с клавиатуры шестизначное число четным, счастливым (сумма первых трех цифр равна сумме последних трех цифр) или делится на 13. 5. Идентифицировать треугольник по трем углам (остроугольный, прямоугольный, тупоугольный, равносторонний, равнобедренный). 6. Идентифицировать равнобедренную трапецию по двум сторонам и углу между ними (квадрат, прямоугольник, обыкновенная). 19 7. Идентифицировать трапецию по двум прилежащим углам (обыкновенная, прямоугольная, равнобедренная, прямоугольник). 8. Определить, в каком квадранте плоскости или на оси находится заданная координатами x и y точка. 9. Рассчитать значение функции y=f(x) при заданном значении х с использованием представления функции в виде ряда: N Вид ряда Общий член ряда N Y X 1 1 - x 2 /2! + x 4 /4! -... )! * 2 /( * ) 1 ( * 2 * 2 n x n n 0,1,… cos(x) любое 2 1 + x/1! + 2 x /2!+... x N /N! 0,1,… е х любое 3 x - x 3 /3 + x 5 /5-… 1) N * (2 x * ) 1 ( 1) N * (2 N 0,1,… arct(x) |X|<1; 4 x * 2 ) 1 - x ( x 1) - (x 2 2 N N x * N ) 1 - x ( 1,2, … ln(x) X>0.5 5 x–x 2 /2 + x 3 /3 -… (-1) N *x N /N 1,2, … ln(1+x) 1 10. Составьте диалоговую программу угадывания случайно выбранных координат цели в квадрате: по оси х от 3 до 7, по оси у от -4 до 2 с пяти попыток с сообщением корректировщика, например: уменьшить Х, увеличить Y. 11. Составьте диалоговую программу угадывания случайно выбранных координат цели в квадрате: по оси х от –10 до 30, по оси у от 2 до 28 c восьми попыток с двойным сообщением корректировщика, например: уменьшить Х, либо: немного уменьшить Х (если отклонение от цели меньше 3). Примечание. Прежде чем выполнять в программе непосредственные вычисления и проверки логических условий рекомендуется проверять вводимые данные на существование (например, являются ли введенные три значения длины сторонами треугольника). 20 Составители: МУКАСЕЕВА Валентина Николаевна САЙФУТДИНОВА Гузель Маратовна ПРИЕМЫ ОБРАБОТКИ ИНФОРМАЦИИ, РАЗРАБОТКА СХЕМ И ТЕСТИРОВАНИЕ ПРОГРАММ МЕТОДИЧЕСКИЕ УКАЗАНИЯ к лабораторным работам № 1, 2 Подписано к печати . .05. Формат 60х84 1/16. Бумага офсетная. Печать плоская. Гарнитура Times New Roman. Усл. печ. л. 2,0. Усл. кр.-отт. . 2,0. Уч.-изд. л. 1,9. Тираж экз. Заказ N Уфимский государственный авиационный технический университет Центр оперативной полиграфии УГАТУ 450000, Уфа-центр, ул. К. Маркса, 12 |