Учебник Технология программирования. Технология программирования
 Скачать 7.85 Mb.
|
|
Пример 3.3. Разработать техническое задание на создание системы решения комбинаторно-оптимизационных задач. Первая версия системы должна включать алгоритмы решения задач: поиска цикла минимальной длины (задача коммивояжера), поиска кратчайшего пути и поиска минимального связывающего дерева. Комбинаторными называют задачи, решение которых сводится к выбору варианта из конечного множества решений. В комбинаторно-оптимизационных задачах в конечном множестве допустимых решений отыскивается такое, для которого целевая функция достигает оптимального (минимального или максимального) значения. Задача коммивояжера или поиска цикла минимальной длины в простейшем варианте формулируется следующим образом. Задан список городов и дорог, соединяющих данные города. Известны расстояния между городами. Необходимо объехать все города, не заезжая ни в какой город дважды, и вернуться в исходный город так, чтобы суммарная длина пути была минимальной. Задача поиска кратчайшего пути при тех же исходных данных предполагает другую цель: необходимо проехать из одного города в другой так, чтобы суммарная длина пути была минимальной. 92 Задача поиска минимального связывающего дерева ставится на тех же исходных данных, но теперь мы прокладываем телефонные линии вдоль дороги и хотим, чтобы длина кабеля была минимальной. Текст технического задания приведен ниже. 1. ВВЕДЕНИЕ Настоящее техническое задание распространяется на разработку системы решения комбинаторно- оптимизационных задач, предназначенной для ввода и хранения данных указанных задач, а также для их решения и хранения полученных результатов, и использования разработчиками программных и аппаратных средств вычислительной техники. Широкий круг задач проектирования различного рода технических объектов, в том числе и компьютеров, относится к классу комбинаторно-оптимизационных задач, точные методы решения которых, как правило, имеют экспоненциальную вычислительную сложность и нереализуемы на современных компьютерах. В настоящее время для решения таких задач широко используются приближенные методы и алгоритмы, которые требуют различных вычислительных ресурсов и обеспечивают разную точность решения. В то же время эти методы и алгоритмы не систематизированы, оценки их вычислительной и емкостной сложности и сведения о возможной точности получаемых решений неполны и разбросаны по многим источникам. В рамках единой системы не существует программной реализации даже для ограниченного круга алгоритмов решения основных комбинаторно-оптимизационных задач проектирования. Создание системы, в рамках которой были бы реализованы наиболее часто упоминаемые методы и алгоритмы решения комбинаторно-оптимизационных задач, позволит как оценивать и исследовать отдельные методы и алгоритмы, так и сравнивать их с точки зрения затрат вычислительных ресурсов и точности получаемых решений. 2. ОСНОВАНИЕ ДЛЯ РАЗРАБОТКИ Система разрабатывается на основании приказа проректора по научной работе МГТУ им. Баумана № ... от .... и в соответствии с планом госбюджетных научно-исследовательских работ факультета ... на 2001-2002 гг. 3. НАЗНАЧЕНИЕ Первая версия системы предназначена для решения небольшого круга комбинаторно- оптимизационных задач на графах (поиск кратчайшего пути, минимального покрывающего дерева и покрывающего цикла минимальной длины). В следующих версиях предполагается увеличение количества решаемых задач. 93 Пользователями могут выступать научные работники и инженеры, занимающиеся проектированием компьютеров, и студенты соответствующих специальностей. Пользователями могут также быть и специалисты других предметных областей, которым приходится решать подобные задачи. 4. ТРЕБОВАНИЯ К ПРОГРАММЕ ИЛИ ПРОГРАММНОМУ ИЗДЕЛИЮ 4 . 1 . Т р е б о в а н и я к ф у н к ц и о н а л ь н ы м х а р а к т е р и с т и к а м 4.1.1. Система должна представлять совокупность методических и программных средств решения следующих задач: • задачи построения минимального покрывающего дерева; • поиск покрывающего цикла минимальной длины (задача коммивояжера); • задачи поиска кратчайшего пути. 4.1.2. Для этих задач должны быть реализованы: • алгоритм, обеспечивающий получение точного решения; • в том случае, если точное решение получается алгоритмом, имеющим неполиномиальную вычислительную сложность, то необходимо дополнительно разработать алгоритм, обеспечивающий получение приближенных решений с полиномиальной вычислительной сложностью. 4.1.3. Методическое обеспечение должно быть реализовано в пользовательском интерфейсе системы, который должен предполагать выбор задачи, метода и алгоритма ее решения; ввод данных; решение проектной задачи и сохранение исходных данных, промежуточных и окончательных результатов во встроенной базе данных для последующего анализа. 4 . 2 . Т р е б о в а н и я к н а д е ж н о с т и 4.2.1. Предусмотреть контроль вводимой информации и блокировку некорректных действий пользователя при работе с системой. 4.2.2. Обеспечить корректное завершение вычислений с соответствующей диагностикой при превышении имеющихся вычислительных ресурсов. 4.2.3. Обеспечить целостность информации, хранящейся в базе данных. 4 . 3 . Т р е б о в а н и я к с о с т а в у и п а р а м е т р а м т е х н и ч е с к и х с р е д с т в 4.3.1. Система должна работать на IBM совместимых персональных компьютерах. 4.3.2. Минимальная конфигурация: • тип процессора.............................................................Pentium-100; • объем оперативного запоминающего устройства........16 Мб; • тип монитора.......................................................... ......SVGA (15'). 94 4.4. Т р е б о в а н и я к и н ф о р м а ц и о н н о й и п р о г р а м м н о й с о в м е с т и м о с т и Система должна работать под управлением операционной системы Windows'95 и выше. 5. ТРЕБОВАНИЯ К ПРОГРАММНОЙ ДОКУМЕНТАЦИИ 5.1. Разрабатываемая система должна включать справочную информацию о работе системы и подсказки пользователю. 5.2. В состав сопровождающей документации должны входить: • пояснительная записка; • руководство пользователя. 6. ЭТАПЫ РАЗРАБОТКИ № Название этапа Срок Отчетность 1 Разработка ядра системы 1.1.2000-31.3.2000 Описание внутренних форматов, интерфейса и форматов данных базы. Реализация системы на уровне интерфейса. 2 Разработка методов и алгоритмов и их реализация для задачи коммивояжера 1.4.2000-30.6.2000 Описание методов и алгоритмов. Программные модули, реализующие методы. 3 Разработка методов и алгоритмов и их реализация для задачи построения минимального связывающего дерева и задачи поиска кратчайшего пути в графе 1.7.2000-30.9.2000 Описание методов и алгоритмов. Программные модули, реализующие методы. 4 Тестирование программного продукта и составление программной документации 1.10.2000-31.12.2000 Тесты. Документация. Программный продукт. После утверждения технического задания организация-разработчик непосредственно приступает к созданию программного обеспечения. Однако переход к следующему этапу разработки – этапу уточнения спецификаций требует принятия еще некоторых принципиальных решений, от которых во многом зависят как характеристики и возможности разрабатываемого 95 программного обеспечения, так и особенности его разработки, начиная с выбора моделей этапа уточнения спецификаций. 3.5. Принципиальные решения начальных этапов проектирования На начальных этапах процесса проектирования должны быть приняты принципиальные решения, во многом определяющие этот процесс, а также качество и трудоемкость разработки. К таким решениям относят: • выбор архитектуры программного обеспечения; • выбор типа пользовательского интерфейса и технологии работы с документами; • выбор подхода к разработке (структурного или объектного); • выбор языка и среды программирования. Другими словами, эти решения определяют, что проектируется, с какими потребительскими характеристиками, как и какими средствами. Часть решений может быть определена в техническом задании, образовав группу технологических требований, остальные должны быть приняты как можно раньше, так как представляют собой исходные данные для процесса проектирования. Выбор архитектуры программного обеспечения. Архитектурой программного обеспечения называют совокупность базовых концепций (принципов) его построения. Архитектура программного обеспечения определяется сложностью решаемых задач, степенью универсальности разрабатываемого программного обеспечения и числом пользователей, одновременно работающих с одной его копией. Различают: • однопользовательскую архитектуру, при которой программное обеспечение рассчитано на одного пользователя, работающего за персональным компьютером; • многопользовательскую архитектуру, которая рассчитана на работу в локальной или глобальной сети. Кроме того, в рамках однопользовательской архитектуры различают: • программы; • пакеты программ; • программные комплексы; • программные системы. Многопользовательскую архитектуру реализуют системы, построенные по принципу «клиент-сервер» (см. § 1.1). Программой называют адресованный компьютеру набор инструкций, точно описывающий последовательность действий, которые необходимо выполнить для решения конкретной задачи. При структурном подходе программы представляют собой иерархию подпрограмм, вызывающих друг друга в 96 процессе решения поставленной задачи, при объектном подходе – совокупность обменивающихся сообщениями объектов, для реализации которых разработаны специальные классы. Программа в этом случае представляет собой отдельно компилируемую программную единицу, которая может использовать стандартные библиотеки подпрограмм, но, как правило, не организует свои. Это самый простой вид архитектуры, который обычно используется при решении небольших задач. Пакеты программ представляют собой совокупность программ, решающих задачи некоторой прикладной области. Например, пакет графических программ, пакет математических программ. Программы такого пакета связаны между собой только принадлежностью к определенной прикладной области. Пакет программ реализуют как набор отдельных программ, каждая из которых сама вводит необходимые данные и выводит результаты. По сути дела пакет программ - это некоторая библиотека программ. Программные комплексы представляют собой совокупность программ, совместно обеспечивающих решение небольшого класса сложных задач одной прикладной области. Дня решения такой задачи может потребоваться решить несколько подзадач, последовательно вызывая программы комплекса. Вызов программ в программном комплексе осуществляется специальной программой – диспетчером, который обеспечивает несложный интерфейс с пользователем и, возможно, выдачу некоторой справочной информации. От пакета программ программный комплекс отличается еще и тем, что несколько программ могут последовательно или циклически вызываться для решения одной задачи, и, следовательно, желательно хранить исходные данные и результаты вызовов в пределах одного пользовательского проекта. Программы в этом случае могут реализовываться как отдельно, так и как совместно компилируемые программные единицы, а исходные данные храниться в оперативной памяти или в файлах. Программные системы представляют собой организованную совокупность программ (подсистем), позволяющую решать широкий класс задач из некоторой прикладной области. В отличие от программных комплексов программы, входящие в программную систему, взаимодействуют через обилие данные. Программные системы обычно имеют развитые пользовательский и внутренние интерфейсы, что требует их тщательного проектирования. Многопользовательские программные системы в отличие от обычных программных систем должны организовывать сетевое взаимодействие отдельных компонентов программного обеспечения, что еще усложняет процесс его разработки. Для разработки подобного программного обеспечения используют специальные технологии или платформы, например, технологии CORBA, COM, Java и т.п. Выбор типа пользовательского интерфейса. Различают четыре типа пользовательских интерфейсов: 97 • примитивные – реализуют единственный сценарий работы, например, ввод данных – обработка – вывод результатов; • меню – реализуют множество сценариев работы, операции которых организованы в иерархические структуры, например, «вставка»: «вставка файла», «вставка символа» и т.д.; • со свободной навигацией – реализуют множество сценариев, операции которых не привязаны к уровням иерархии, и предполагают определение множества возможных операций на конкретном шаге работы; интерфейсы данной формы в основном используют Windows-приложения; • прямого манипулирования – реализуют множество сценариев, представленных в операциях над объектами, основные операции инициируются перемещением пиктограмм объектов мышью, данная форма реализована в интерфейсе самой операционной системы Windows альтернативно интерфейсу со свободной навигацией. Тип пользовательского интерфейса во многом определяет сложность и трудоемкость разработки, которые существенно возрастают в порядке перечисления типов. По последним данным до 80% программного кода может реализовывать именно пользовательский интерфейс [49]. Поэтому понятно, что на ранних стадиях обучения программированию реализуют в основном примитивные интерфейсы и меню, хотя они и не удобны для пользователей. Появление объектно-ориентированных визуальных сред разработки программного обеспечения, использующих событийный подход к программированию и в основном рассчитанных на создание интерфейсов со свободной навигацией, существенно снизило трудоемкость разработки подобных интерфейсов и упростило реализацию интерфейсов прямого манипулирования. Таким образом, выбор двух последних типов интерфейсов предполагает использование одной из визуальных сред разработки программного обеспечения. Если соответствующие среды разработчику не доступны, то следует учитывать большую трудоемкость создания подобных интерфейсов. Кроме того, выбор типа интерфейса включает выбор технологии работы с документами. Различают две технологии: • однодокументная, которая предполагает однодокументный интерфейс (SDI – Single Document Interface); • многодокументная, которая предполагает многодокументный интерфейс (MDI – Multiple Document Interface). Многодокументную технологию используют, если программное обеспечение должно работать с несколькими документами одновременно, например, с несколькими текстами или несколькими изображениями. Однодокументную – если одновременная работа с несколькими документами не обязательна. Трудоемкость реализации многодокументных интерфейсов с использованием современных библиотек примерно на 3...5 % выше, чем первого. 98 Вы бор типа влияет на трудоемкость более существенно (более подробно типы интерфейсов будут рассмотрены в § 8.1). Выбор подхода к разработке. Если выбран интерфейс со свободной навигацией или прямого манипулирования, то, как указывалось выше, это практически однозначно предполагает использование событийного программирования и объектного подхода, так как современные среды визуального программирования, такие как Visual C++, Delphi, Builder C++ и им подобные, предоставляют интерфейсные компоненты именно в виде объектов библиотечных классов. При этом в зависимости от сложности предметной области программное обеспечение может реализовываться как с использованием объектов и, соответственно, классов, так и чисто процедурно. Исключение составляют случаи использования специализированных языков разработки Интернет-приложений, таких как Perl, построенных по совершенно другому принципу. Примитивный интерфейс и интерфейс типа меню совместимы как со структурным, так и с объектным подходами к разработке. Поэтому выбор подхода осуществляют с использованием дополнительной информации. Практика показывает, что объектный подход эффективен для разработки очень больших программных систем (более 100.000 операторов универсального языка программирования) и в тех случаях, когда объектная структура предметной области ярко выражена. Следует также учитывать, что необходимо осторожно использовать объектный подход при жестких ограничениях на эффективность разрабатываемого программного обеспечения, например, при разработке систем резального времени. Во всех прочих случаях выбор подхода остается за разработчиком. Выбор языка программирования. В большинстве случаев, никакой проблемы выбора языка программирования реально не существует. Язык может быть определен: • организацией, ведущей разработку; например, если фирма владеет лицензионным вариантом C++ Builder, то она будет вести разработки преимущественно в данной среде; • программистом, который по возможности всегда будет использовать хорошо знакомый язык; • устоявшимся мнением («все разработки подобного рода должны выполняться на C++ или на Java или на ...») и т.п. Если же все-таки выбор языка реально возможен, то нужно иметь в виду, что все существующие языки программирования можно разделить на следующие группы: • универсальные языки высокого уровня; • специализированные языки разработчика программного обеспечения; • специализированные языки пользователя; • языки низкого уровня. 99 В группе у ниверсальных языков высокого у ро вня безусловным лидером на сегодня является язык С (вместе с C++). Действительно различные версии С и C++ имеют целый ряд очень существенных достоинств: • многоплатформенность – для всех используемых в настоящее время платформ существуют компиляторы с языка С и C++; • наличие операторов, реализующих основные структурные алгоритмические конструкции (условную обработку, все виды циклов); • возможность программирования на низком (системном) уровне с использованием адресов оперативной памяти; • огромные библиотеки подпрограмм и классов. Все это сделало С и C++ основными языками, используемыми для создания операционных систем, и, в свою очередь, служит для них дополнительной рекламой. Однако С и C++ имеют и серьезные недостатки: • отсутствие полноценных встроенных структурных типов данных (имеющиеся псевдоструктурные типы, использующие адресную арифметику, недостаточно жестко определены, чтобы контролировать многие операции над этими данными, что приводит к большому количеству ошибок, выявляемых только в процессе отладки программы); • наличие синтаксических неоднозначностей, которые также не позволяют компилятору контролировать правильность программы; • ограниченный контроль параметров, передаваемых в подпрограмму, что также обнаруживается только в процессе отладки программы, и т.п. Альтернативой С и C++ среди универсальных языков программирования, используемых для создания прикладного программного обеспечения, на сегодня является Pascal, компиляторы которого в силу четкого синтаксиса обнаруживают помимо синтаксических и большое количество семантических ошибок. Версия Object Pascal, использованная в среде Delphi, сопровождается профессиональными библиотеками классов, упрощающими ведение больших разработок, в том числе и требующих использования баз данных, что делает Delphi достаточно эффективной средой для создания приложений Windows. Кроме этих языков к группе универсальных принадлежат также Basic, Modula, Ada и некоторые другие. Каждый из указанных языков, так же, как C++ и Pascal, имеет свои особенности и, соответственно, свою область применения. Специализированные языки ра зра ботч ика используют для создания конкретных типов программного обеспечения. К ним относят: • языки баз данных; • языки создания сетевых приложений; • языки создания систем искусственного интеллекта и т.д. 100 Эти языки изучаются в специальных курсах, и в настоящем учебнике рассматриваться не будут. Специализированные языки пользователя обычно являются частью профессиональных сред пользователя, характеризуются узкой направленностью и разработчиками программного обеспечения не используются. Языки низкого у ровня позволяют осуществлять программирование практически на уровне машинных команд. При этом получают самые оптимальные, как с точки зрения времени выполнения, так и с точки зрения объема необходимой памяти программы. Но эти языки совершенно не годятся для создания больших программ и, тем более, программных систем. Основная причина – низкий уровень абстракций, которыми должен оперировать разработчик, откуда недопустимо большое время разработки. Существенно и то, что сами языки низкого уровня не поддерживают принципов структурного программирования, что значительно ухудшает технологичность разрабатываемых программ. В настоящее время языки типа Ассемблера обычно используют: • при написании сравнительно простых программ, взаимодействующих непосредственно с техническими средствами, например драйверов, поскольку в этом случае приходится кропотливо настраивать соответствующее оборудование, преимущества языков программирования высокого уровня становятся несущественными; • в виде вставок в программы на языках высокого уровня, например, для ускорения преобразования данных в циклах с большим количеством повторений. |