ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 31.03.2021
Просмотров: 6809
Скачиваний: 51
261
6) анализ алгоритма и его сложности;
7) тестирование программы;
8)документирование.
Кратко остановимся на каждом из этих этапов.
При
постановке задачи
для крупных компьютерных программ необходимо провести сле-
дующие работы:
• выработать требования (свойства, качества и возможности), необходимые для решения
проблемы или достижения цели (как правило, эта деятельность носит экспертный характер);
• разработать
спецификации, включающие:
• цель программы;
• граничные условия;
• описание функций системы;
• спецификации входных и выходных данных;
• верификационные требования (установление тестовых случаев);
• тип и количество документов.
В ходе этой работы выявляются свойства, которыми должна обладать система в конечном
виде (замысел), описываются функции системы, характеристики интерфейса.
Чтобы приступить к решению задачи необходимо точно ее сформулировать. В первую оче-
редь, это означает определение исходных и выходных данных, т.е. ответы на вопросы: а) что дано;
б) что нужно найти. Дальнейшая детализация постановки задачи представляет собой ответы на
серию вопросов такого рода:
• как определить решение;
• каких данных не хватает и все ли они нужны;
• какие сделаны допущения и т.п.
Проектирование программы.
Сначала производится проектирование архитектуры про-
граммной системы. Это предполагает первичную (общую) стадию проектирования и заканчивает-
ся декомпозицией спецификаций в структуру системы. Обычно на модульном уровне по каждому
модулю разрабатывается спецификация модуля:
• имя/цель - дается
имя модулю и предложение о функции модуля с формальными парамет-
рами;
• неформальное описание - обзор действий модуля;
• ссылки - какие модули ссылаются на него и на какие модули ссылается данный модуль;
• вход/выход - формальные и фактические параметры, глобальные, локальные и связанные
(общие для ряда модулей) переменные;
• примечания - полезные комментарии общего характера по модулю.
Следующим шагом является детальное проектирование. На этом этапе происходит проце-
дурное описание программы, выбор и оценка алгоритма для реализации каждого модуля. Входной
информацией для проектирования являются требования и спецификации системы.
Для проектирования программ существуют различные подходы и методы. Современный
подход к проектированию основан на декомпозиции, которая, в свою очередь, основана на ис-
пользовании абстракции. Целью при декомпозиции является создание модулей, которые взаимо-
действуют друг с другом по определенным и простым правилам. Декомпозиция используется для
разбиения программы на компоненты, которые затем могут быть объединены.
Методы проектирования архитектуры делятся на две группы:
1) ориентированные на обработку и
2) ориентированные на данные.
Методы, ориентированные на обработку,
включают следующие общие идеи.
а)
Модульное программирование.
Основные концепции:
• каждый модуль реализует единственную независимую функцию;
• имеет единственную точку входа/выхода;
• размер модуля минимизируется;
• каждый модуль разрабатывается независимо от других модулей;
• система в целом построена из модулей. Исходя из этих принципов каждый модуль тести-
руется отдельно, затем после кодирования и тестирования происходит их интеграция и тестирует-
ся вся система.
262
б)
Функциональная декомпозиция.
Подобна стратегии «разделяй и управляй». Практически является декомпозицией в форме
пошаговой детализации и концепции скрытия информации. Каждый модуль характеризуется
субъективным решением проектировщика, связь осуществляется с помощью хорошо организо-
ванных интерфейсов.
в)
Проектирование с использованием потока данных.
Использует поток данных как генеральную линию проектирования программы. Содержит
элементы структурного проектирования сверху-вниз с пошаговой детализацией:
• экспертиза потоков данных и отображение графа потока данных;
• анализ входных, центральных и выходных преобразующих поток данных элементов;
• формирование иерархической структуры программы;
• детализация и оптимизация структуры программы.
г)
Технология структурного анализа проекта.
Основана на структурном анализе с использованием специальных графических средств по-
строения иерархических функциональных связей между объектами системы. Эффективна на ран-
них стадиях создания системы, когда диаграммы просты и читаемы.
Методы проектирования, основанные на использовании структур данных
,
описаны
ниже.
а)
Методология Джексона.
Здесь структура данных - ключевой элемент в построении проекта. Структура программы
определяется структурой данных, подлежащих обработке. Программа представляется как меха-
низм, с помощью которого входные данные преобразуются в выходные. В методе предусматрива-
ется:
• разработка и изображение структуры входных и выходных данных;
• изображение структуры программы путем соединения изображений этих структурных
элементов:
• определение дискретных операций над структурами данных;
• построение алгоритмов обработки структур данных.
б)
Методология Уорнера.
Подобна предыдущей, но процедура проектирования более детализирована. Используются
следующие виды представления проекта:
• диаграммы организации данных (описывают входные и выходные данные);
• диаграммы логического следования (логический поток этих данных);
• список инструкций (команды, используемые в проекте);
• псевдокод (описание проекта);
• определение входных данных системы;
• организация входных данных в иерархическую структуру;
• детальное определение формата элементов входного файла;
• то же самое для выходных данных;
•спецификация программы: чтение, ветвление, вычисление, выходы, вызови подпрограмм;
• составление диаграммы (по типу блок-схем) указывающие логическую последователь-
ность инструкций.
в)
Метод иерархических диаграмм.
В этом методе определяется связь между входными, выходными данными и процессом об-
работки с помощью иерархической декомпозиции системы (без детализации). По сути использу-
ются три элемента: вход, обработка, выход.
Алгоритм проектирования по этому методу заключается в следующих шагах:
• начать с наивысшего уровня абстракции, определив вход, выход, обработку;
• соединить каждый элемент входа и выхода с соответствующей обработкой;
• документировать каждый элемент системы, используя диаграммы;
• детализировать диаграммы, используя шаги 1 - 3.
г)
Объектно-ориентированная методология проектирования.
Основана на концепции упрятывания информации и абстрактных типов данных. Рассмат-
риваются данные, модули и системы в качестве объектов. Каждый объект содержит некоторую
структуру данных с набором процедур, знающих как работать с этими данными. По этой методо-
263
логии создаются абстракции по заданной проблемной области:
определение проблемы;
развитие неформальной стратегии, удовлетворяющей требованиям к системе;
формализация стратегии;
создание объектов и их атрибутов;
определение операций над объектами;
установка интерфейсов;
реализация операций.
Построение модели в большинстве случаев является непростой задачей. Чтобы приобрести
опыт в моделировании, необходимо изучить как можно больше известных и удачных моделей.
При построении моделей,
как правило, используют два принципа: дедуктивный (от общего
к частному) и индуктивный (от частного к общему).
Рис. 3.3.
Схема построения модели при дедуктивном способе
При дедуктивном подходе (рис.3.3) рассматривается частный случай общеизвестной фун-
даментальной модели. Здесь при заданных предположениях известная модель приспосабливается
к условиям моделируемого объекта. Например, можно построить модель свободно падающего те-
ла на основе известного закона Ньютона
та = mg - F
coпp
и в качестве допустимого приближения
принять модель равноускоренного движения для малого промежутка времени.
Рис. 3.4.
Схема построения модели при индуктивном способе
Индуктивный способ (рис.3.4) предполагает выдвижение гипотез, декомпозицию сложного
объекта, анализ, затем синтез. Здесь широко используется подобие, аналогичное моделирование,
умозаключение с целью формирования каких-либо закономерностей в виде предположений о по-
ведении системы.
Технология построения модели при индуктивном способе:
1) эмпирический этап
• умозаключение;
• интуиция;
• предположение;
• гипотеза.
2) постановка задачи для
моделирования;
3) оценки; количественное и качественное описание;
4) построение модели.
Разработка алгоритма - самый сложный и трудоемкий процесс,
но и самый интересный в
творческом отношении. Выбор метода разработки зависит
от постановки задачи, ее модели. (О не-
264
которых приемах и методах разработки алгоритмов говорилось ранее в гл. 1 и будет сказано в сле-
дующих разделах данной главы.) На этом этапе необходимо провести анализ правильности алго-
ритма, что очень непросто и трудоемко. Наиболее распространенная процедура доказательства
правильности алгоритма - это прогон его на множестве различных тестов. Однако, это не гаранти-
рует того. что не может существовать случая, в котором программа «не сработает». В общей мето-
дике доказательства правильности алгоритма предполагают, что алгоритм описан в виде последо-
вательности шагов. Для каждого шага предлагается некое обоснование его правильности для всех
подходящих входных (условиях до данного шага) и выходных данных (условиях после этого ша-
га). Затем предлагается доказательство конечности алгоритма с окончательными исходными вход-
ными и выходными данными.
На этапе реализации алгоритма происходит конструирование и реализация алгоритма,
включая:
• кодирование;
• интеграцию;
• тестирование (сертификацию).
По сути проводится перевод проекта в форму программы для конкретного компьютера,
сборка системы и ее прогон при тестовых и нормальных условиях для подтверждения ее работы в
соответствии со спецификациями системы. Этот этап зависит от того, какой язык программирова-
ния выбран, на каком компьютере алгоритм будет реализован. С этим связаны выбор типов дан-
ных, вводимых структур данных, связь с окружающей средой и т.п. Важно осознавать интерак-
тивность, вид транслятора (компилятор или интерпретатор), наличие библиотек подпрограмм, мо-
дулей и объектов.
Анализ алгоритма
и его сложности необходим для оценки ресурсов компьютеров, на ко-
торых он будет работать, времени обработки конкретных данных, приспособления в работе в ло-
кальных сетях и телекоммуникациях. Хотелось бы также иметь для данной задачи количествен-
ный критерий для сравнения нескольких алгоритмов с целью выбора более простого и эффектив-
ного среди них.
Перед началом эксплуатации программы необходим этап ее отладки и
тестирования.
Тестирование
-
это процесс исполнения программ с целью выявления (обнаружения) оши-
бок. Тестирование - процесс деструктивный, поэтому считается, чти тест удачный, если обнару-
жена ошибка. Хорошим считается тест, который имеет большую вероятность обнаружения еще не
выявленной ошибки. Удачным считается тест, который обнаруживает еще не выявленную ошиб-
ку.
Существуют различные способы тестирования программ.
Тестирование программы как «черного ящика» (стратегия «черного ящика» определяет тес-
тирование с анализом входных данных и результатов работы программы). Критерием исчерпы-
вающего входного тестирования является использование всех возможных наборов входных дан-
ных.
Тестирование программы как «белого ящика» заключается в стратегии управления логикой
программы, позволяет использовать ее внутреннюю структуру. Критерием выступает исчерпы-
вающее тестирование всех маршрутов и управляющих структур программы.
Разумная и реальная стратегия тестирования - сочетание моделей «черного» и «белого
ящиков».
Принципы тестирования:
• описание предполагаемых значении выходных данных или результатов должно быть не-
обходимой частью тестового набора;
• тесты для неправильных и непредусмотренных входных данных следует разрабатывать
так же тщательно, как для правильных и предусмотренных;
• необходимо проверять не только делает ли программа то, для
чего она предназначена, но
и не делает ли она то, что не должна делать;
• нельзя планировать тестирование в предположении, что ошибки не будут обнаружены;
• вероятность наличия необнаруженных ошибок в части программы пропорциональна чис-
лу ошибок, уже обнаруженных в этой части;
• тестирование - процесс творческий.
При разработке программ очень полезным бывает метод «ручного тестирования» без ком-
265
пьютера на основе инспекции и сквозного просмотра (тестирование «всухую»).
Инспекция и сквозной просмотр - это набор процедур и приемов обнаружения ошибок при
чтении текста.
Основные типы ошибок, встречающихся при программировании:
• обращения к переменным, значения которым не присвоены или не инициализированы;
• выход индексов за границы массивов;
• несоответствие типов или атрибутов переменных величин;
• явные или неявные проблемы адресации памяти;
• ошибочные передачи управления;
• логические ошибки.
При проектировании процедуры тестирования предусматривают серии тестов, имеющих
наивысшую вероятность обнаружения большинства ошибок. Для целей исчерпывающего тестиро-
вания создают эквивалентные разбиения входных параметров. причем предусмативают два класса:
правильные входные данные и неправильные (ошибочные входные значения). Для каждого класса
эквивалентности строят свой тест. Классом эквивалентности тестов можно назвать такое множе-
ство тестов, что выполнение алгоритма на одном из них гарантирует аналогичный результат про-
гона для других.
Особое внимание необходимо уделять тестам на граничных условиях. Граничные условия -
это ситуации, возникающие непосредственно на, выше или ниже границ входных и выходных
классов эквивалентности (т.е. вблизи границ эквивалентных разбиений). В частности, примерами
классов эквивалентных тестов для алгоритма решения квадратного уравнения могут служить сле-
дующие классы: множество действительных, отличных от нуля, чисел
а, b, с,
таких, что
b∙b -
4
∙
а
∙
с
< 0; множество чисел а = 0,
b
и с не равны нулю;
b
= 0,
а
и с не равны нулю, и т.п.
Сам процесс тестирования может быть пошаговым и/или монолитным. В том и в другом
случае используют стратегии нисходящего тестирования, - начиная с верхнего, головного модуля,
и затем подключая последовательно другие модули (аппарат заглушек), и восходящего тестирова-
ния, начиная с тестирования отдельных модулей.
В процессе отладки программы используют метод грубой силы - использование выводов
промежуточных данных по всей программе (трассировка) или использование автоматических
средств. Например, в Турбо-Паскале имеется в наличии мощный аппарат автоматической отладки
программ (режим DEBUG).
Есть золотое правило программистов - оформляй свои программы в том виде, в каком бы
ты хотел видеть программы, написанные другими. К каждому конечному программному продукту
необходимо документированное сопровождение в виде помощи (help), файлового текста (read-
me.txt).
Контрольные вопросы и задания
1. Каковы основные этапы проектирования и разработки программы?
2. Что означает хорошо сформулированная постановка задачи?
3. Назовите методологии проектирования и разработки программ.
4. Как выбрать модель задачи?
5. Что такое тестирование программы?
6. Постройте группу тестов для алгоритма решения системы линейных уравнений.
4.2. ОСНОВНЫЕ ПРИНЦИПЫ РАЗРАБОТКИ И АНАЛИЗА АЛГОРИТМОВ
При построении алгоритма для сложной задачи используют системный подход -
использованием декомпозиции (нисходящее проектирование сверху-вниз) и синтеза (программи-
рование снизу-вверх). Как и при разработке структуры любой сложной системы, при формирова-
нии алгоритма используют дедуктивный и индуктивный методы.
.
При дедуктивном подходе рассматривается частный случай общеизвестных
алгоритмиче-
ских моделей. Здесь при заданных предположениях известный алгоритм приспосабливается к ус-
ловиям решаемой задачи. Например, многие вычислительные задачи линейной алгебры, в частно-
сти, нелинейные уравнения, системы алгебраических уравнений и т.п., могут быть решены с ис-
пользованием известных методов и алгоритмов, для которых существует множество специальных