- •Введение Цели и задачи курса «Технология программирования»
- •Классификация программного обеспечения
- •Тема 1.Понятие программного изделия
- •1.1.Основные требования к программному изделию как к продукции производственно-технического назначения
- •1.2.Жизненный цикл программных изделий
- •1.3.Методическая, технологическая, инструментальная и организационная поддержка процесса проектирования программных изделий
- •1.4.Этапы проектирования сложных программных изделий
- •Тема 2.Внешнее проектирование программных изделий
- •2.1.Разработка требований и внешнее проектирование программных изделий
- •2.2.Обеспечение целей создания программных изделий Цели проекта с точки зрения пользователя
- •Цели проекта с точки зрения разработчика
- •2.3.Разработка внешних спецификаций проекта
- •Тема 3.Внутреннее проектирование программных изделий
- •3.1.Понятие модуля. Характеристики качества модулей
- •3.2.Методы проектирования программ
- •Иерархическая декомпозиция и абстрактные машины (метод нисходящей декомпозиции)
- •Программирование на основе принципа пошагового совершенствования
- •Структурное программирование по нисходящему принципу
- •Программирование с использованием пошаговой реорганизации
- •Способы описания программ. Язык проектирования программ
- •Тема 4.Структурированные программы
- •4.1.Блок-схемы и управляющие структуры
- •4.2.Теорема о структурировании
- •4.3.Рекурсивные структурированные программы
- •Тема 5.Методы Доказательства правильности программ
- •5.1.Математический аппарат доказательства Принцип простой индукции
- •Принцип модифицированной простой индукции
- •Принцип обобщенной индукции
- •5.2.Методы доказательства правильности программ Метод индуктивных утверждений
- •Пример доказательства правильности программы методом индуктивных утверждений
- •Тема 6.Рекурсивные программы. Методы доказательства их правильности
- •6.1.Понятие рекурсивных программ. Способы их описания Язык описания рекурсивных программ
- •Примеры рекурсивных программ
- •6.2.Рекурсивные программы работы со списками Списки и операции над ними
- •Примеры программ работы со списками
- •6.3.Примеры доказательства правильности рекурсивных программ
- •Тема 7.Отладка программ
- •7.1.Типичные ошибки в программных комплексах
- •7.2.Задачи отладки программ
- •7.3.Методы разработки тестов Метод эквивалентных разбиений
- •Методы тестирования программ путем покрытия логики
- •Метод функциональных диаграмм
- •Предположения об ошибках
- •7.4.Задачи комплексной отладки программ
- •Библиографический список
3.2.Методы проектирования программ
Прежде чем создавать программное изделие, необходимо четко уяснить суть задачи и ее структуру. Для этого задачу разбивают на уровни абстракций, как правило, методом декомпозиции.
Иерархическая декомпозиция и абстрактные машины (метод нисходящей декомпозиции)
Расхождения между языком, на котором формулируются задачи, и языком, на котором описываются алгоритмы их решения, порождают трудности при разработке концепции программ. Термин «язык» определяет некоторые объекты и механизмы, позволяющие их создавать, действия (или примитивы), позволяющие оперировать объектами, и правила композиции таких действий.
Объект определяется с помощью следующих атрибутов:
имени, которое позволяет обозначить объект и отличить его от других объектов;
состояния, которое определяется в каждый данный момент и может изменяться с течением времени;
множества операций, или функций доступа, которые, в частности, позволяют создавать и уничтожать объекты, проверять и изменять состояние объекта, а также комбинировать объекты между собой.
Прежде всего отметим, что любой язык определяет, по крайней мере концептуально, некоторую «машину», способную его интерпретировать: перечень инструкций для этой машины совпадает со множеством операций языка, ее память позволяет представлять объекты, определяемые языком, а механизм выполнения инструкций определяется правилами интерпретации языка. Подобная машина называется «абстрактной», поскольку, вообще говоря, она не имеет физической реализации.
Метод нисходящей декомпозиции представляет собой разновидность декартово-покоординатного спуска, который заключается в сведении задачи к последовательности элементарных подзадач, решаемых более простыми способами. Для этого вначале определяем машину так, что с помощью объектов и примитивов, реализованных на ней, мы надеемся решить поставленную задачу более простым способом. При этом возникает проблема реализации определенной нами машины на реально имеющейся в нашем распоряжении машине . Для решения этой новой задачи определяем новую машину и так до тех пор, пока очередную машину можно будет легко реализовать на машине .
Если при реализации машины используется интерфейс, предлагаемый машиной , то говорят, что использует или зависит от . В действительности зависит лишь от интерфейса , а не от деталей ее внутренней реализации. Отношение между машинами, определенное таким образом, называется отношением зависимости. Структура системы может быть описана в этом случае с помощью графа, вершины которого представляют машины, определенные декомпозицией, а ребра - их отношения зависимости. Варианты структур, основанных на методе нисходящей декомпозиции, можно представить схемами, приведенными ниже.
На практике метод нисходящей декомпозиции никогда не применяется в чистом виде: обычно используются итеративные процедуры, а при последовательном определении машин учитываются опыт разработчика и характеристики уже реализованных машин. Кроме того, для достаточно сложных задач практически невозможно фиксировать заранее спецификации интерфейсов в деталях, так как при их разработке используются результаты экспериментов с промежуточными реализациями.
В любом случае, иерархическая структура слоев обладает рядом преимуществ, вытекающих из независимости, которая обеспечивается процессом абстрагирования:
независимость концепции: состояние машины для пользователя полностью описывается спецификациями ее интерфейса;
независимость модификаций: изменения в реализации одной из машин не влекут за собой изменений в машинах, которые используют данную, поскольку спецификации интерфейса остаются неизменными
независимость отладки: после того как интерфейс некоторой машины специфицирован, ее отладка может производиться независимо от машин, которые ее используют, и наоборот, машины, использующие , могут отлаживаться независимо от нее.