Данная диаграмма должна быть проверена с точки зрения возможности получения всех справок, указанных в техническом задании или показанных на диаграмме потоков данных разрабатываемой системы (см. рис. 4.14).
4.6. Математические модели задач, разработка или выбор методов решения
Для задач, алгоритм решения которых не очевиден, используют разного рода математические модели. Процесс построения такой модели включает:
•анализ условия задачи;
•выбор математических абстракций, адекватно, т. е. с требуемой точностью и полнотой представляющих исходные данные и результаты;
•формальную постановку задачи;
•определение метода преобразования исходных данных в результат, т. е. метода решения задачи.
Для многих задач, которые часто встречаются на практике, в математике определены как модели, так и методы решения. К таким задачам, например, относится большинство задач аналитической геометрии на плоскости и в пространстве, задачи моделирования дискретных систем и т. д.
Основная проблема в подобных случаях - обоснование применимости той или иной математической модели для решения конкретной задачи.
В ряде случаев формальная постановка задачи однозначно определяет метод ее решения, но, как правило, методов решения существует несколько, и тогда для выбора метода решения может потребоваться специальное исследование. При выборе метода учитывают:
•особенности данных конкретной задачи, связанные с предметной областью (погрешность, возможные особые случаи и т. п.);
•требования к результатам (допустимую погрешность);
•характеристики метода (точный или приближенный, погрешности результатов, вычислительную и емкостную сложности, сложность реализациии т. п.).
Пример 4.8. Выполнить формальную постановку задачи поиска цикла минимальной длины (задачи коммивояжера).
Вспомним, что задача коммивояжера или поиска цикла минимальной длины в простейшем варианте формулируется следующим образом. Задан список городов и дорог, соединяющих данные города. Известны расстояния между городами. Необходимо объехать все города, не заезжая ни в какой город дважды, и вернуться в исходный город так, чтобы суммарная длина пути была минимальной.
Анализ условия задачи показывает, что математической моделью объектов системы и существующих или возможных связей между ними может являться взвешенный ориентированный или неориентированный граф G(X, <U, L>), где X, U, L - множества вершин, ребер и весов ребер соответственно.
Для перехода от объектов задачи к их математическим моделям необходимо [55]:
•сформулировать правила соответствия компонентов объекта компонентам модели;
•определить вид этих соответствий (взаимно однозначные, однозначные, многозначные);
•определить способ отображения свойств и характеристик компонентов объекта в характеристики выбранной математической абстракции.
Все это определяется, исходя из отношений, существующих между компонентами объекта, а также свойств объекта и характеристик его компонентов.
В графе G множество Э объектов системы (городов) поставлено во взаимно однозначное соответствие множеству X, а множеству связей С между парами объектов (дорог) поставлено в
такое же соответствие множество ребер U. Расстояние между городами (эi , эj )интерпретируется
как вес соответствующего ребра w(xi , x j ).
Таким образом, в терминах теории графов рассматриваемая задача - это поиск в ориентированном или неориентированном графе гамильтонова цикла минимальной длины.
Формальная постановка задачи имеет вид - выполнить преобразование исходного графа G в граф результата Gc:
D
G(X , <U , W >)→Gc (X , U c )
так что
U c U U c = X c :W (Gc )= ∑w(ur )→ min ur U c
причем
( xi X )p(xi )= 2,( xi, xi X ) S(xi , xi ),
где p(xi ) - количество ребер, подходящих к вершине; a S(xi , xi ) - маршрут между вершинами xi , xi , т. е. последовательность смежных ребер, связывающих зги вершины.
Следует иметь в виду, что граф имеет гамильтонов цикл, если сумма локальных степеней любой пары вершин больше или равна числу его вершин:
( xi , xi X )[p(xi )+ p(x j )]≥n.
В противном случае граф может не иметь гамильтонова цикла, что для нас означает, что в некоторых случаях задача может не иметь решения.
Задача относится к классу NP-сложных - задач, вычислительная сложность которых не выражается в виде полинома от размерности ее входа (количества городов), а носит экспоненциальный характер, т. е. очень быстро возрастает при увеличении размерности задачи. Известно, что точное решение задачи коммивояжера может быть получено алгоритмами, реализующими полный перебор или метод ветвей и границ. Приближенное решение дают методы поиска в глубину и двоичной свертки.
Поскольку по техническому заданию необходимо обеспечить получение точного решения, следует реализовать хотя бы по одному методу из указанных групп. Для выбора методов нужно провести дополнительные исследования.
Определив методы решения, целесообразно для некоторых вариантов исходных данных вручную, на калькуляторе или с использованием других средств подсчитать ожидаемые результаты. Эти данные в дальнейшем будут использованы при тестировании программного обеспечения. Кроме того, выполнение операций вручную позволяет точно уяснить последовательность действий, что упростит разработку алгоритмов.
Кроме того, имеет смысл продумать, для каких сочетаний исходных данных результат не существует или не может быть получен данным методом, что тоже необходимо учесть при разработке программного обеспечения.
Контрольные вопросы и задания
1.В чем сущность структурного подхода к программированию? Какие этапы охватывает данный подход?
2.Что понимают под термином «спецификации»? В чем сложность их уточнения? Назовите модели, используемые в качестве функциональных спецификаций при структурном подходе. Какие характеристики проектируемого программного обеспечения описывает каждая из них?
3.В каких случаях целесообразно использовать диаграммы переходов состояний? Разработайте диаграмму переходов для калькулятора, техническое задание на который составлялось вами в соответствии заданием к предыдущей главе.
4.В чем заключается основное различие между функциональными диаграммами и диаграммами потоков данных? Постройте оба вида диаграмм для выполнения вычислений с использованием внутренней памяти калькулятора. Проанализируйте сходство и различие. В каких случаях использование диаграмм потоков данных является предпочтительным?
5.Что называют «структурами данных»? Какие данные имеются в виду? В каких случаях структуры данных необходимо описывать? Какие модели используют для описания структур данных?
6.Опишите стек и очередь с использованием предлагаемых моделей описания данных. Какие аспекты этих структур остались не описанными и почему?
7.В каких случаях используют математические модели? Что понимают под адекватностью модели? Зачем необходимо выполнять доказательство адекватности и как строятся подобные доказательства?
5. ПРОЕКТИРОВАНИЕ ПРОГРАММНОГО ОБЕСПЕЧЕНИЯ ПРИ СТРУКТУРНОМ ПОДХОДЕ
Как уже упоминалось ранее, сущность структурного подхода заключается в декомпозиции программы или программной системы по функциональному принципу. Все предлагаемые методы декомпозиции используют интерфейсы простейшего типа: примитивные интерфейсы и традиционные меню, и рассчитаны на анализ и проектирование как структур данных, так и обрабатывающих их программ.
Причем в большинстве случаев первичным считают проектирование обрабатывающих компонентов, проектирование же структур данных выполняют параллельно. Существует и альтернативный подход, при котором первичным считают проектирование данных, а обрабатывающие программы получают, анализируя полученные структуры данных.
В любом случае проектирование программного обеспечения начинают с определения его структуры.
5.1. Разработка структурной и функциональной схем
Процесс проектирования сложного программного обеспечения начинают с уточнения его структуры, т. е. определения структурных компонентов и связей между ними. Результат уточнения структуры может быть представлен в виде структурной и/или функциональной схем и описания (спецификаций) компонентов.
Структурная схема разрабатываемого программного обеспечения. Структурной
называют схему, отражающую состав и взаимодействие по управлению частей разрабатываемого программного обеспечения.
Структурные схемы п а к е т о в п р о г р а м м не информативны, поскольку организация программ в пакеты не предусматривает передачи управления между ними. Поэтому структурные схемы разрабатывают для каждой программы пакета, а список программ пакета определяют, анализируя функции, указанные в техническом задании.
Самый простой вид программного обеспечения - программа, которая в качестве структурных компонентов может включать только подпрограммы и библиотеки ресурсов. Разработку структурной схемы программы обычно выполняют методом пошаговой детализации (см. § S.2).
Структурными компонентами программной системы или программного комплекса могут служить программы, подсистемы, базы данных, библиотеки ресурсов и т. п.
Структурная схема п р о г р а м м н о г о к о м п л е к с а демонстрирует передачу управления от программы-диспетчера соответствующей программе (рис. 5.1).
Структурная схема п р о г р а м м н о й с и с т е м ы, как правило, показывает наличие подсистем или других структурных компонентов. В отличие от программного комплекса отдельные части (подсистемы) программной системы интенсивно обмениваются данными между собой и, возможно, с основной программой. Структурная же схема программной системы этого обычно не показывает (рис. 5.2).
Более полное представление о проектируемом программном обеспечении с точки зрения взаимодействия его компонентов между собой и с внешней средой дает функциональная схема.
Функциональная схема. Функциональная схема или схема данных (ГОСТ 19.701-90) - схема взаимодействия компонентов программного обеспечения с описанием информационных потоков, состава данных в потоках и указанием используемых файлов и устройств. Для изображения функциональных схем используют специальные обозначения, установленные стандартом. Основные обозначения схем данных по ГОСТ 19.701-90 приведены в табл. 5.1.
Функциональные схемы, более информативны, чем структурные. На рис. 5.3 для сравнения приведены функциональные схемы программных комплексов и систем.
Все компоненты структурных и функциональных схем должны быть описаны. При структурном подходе особенно тщательно необходимо прорабатывать спецификации межпрограммных интерфейсов, так как от качества их описания зависит количество самых дорогостоящих ошибок. К самым дорогим относятся ошибки, обнаруживаемые при комплексном тестировании, так как для их устранения могут потребоваться серьезные изменения уже отлаженных текстов.
