База знаний студента. Реферат, курсовая, контрольная, диплом на заказ

курсовые,контрольные,дипломы,рефераты

Технология разработки программного обеспечения — Программирование, Базы данных

              Государственный Комитет Российской Федерации

                        по высшему образованию

            Саратовский государственный технический университет

           Т Е Х Н О Л О Г И Я     П Р О Г Р А М М И Р О В А Н И Я

             Методические указания по курсовому проектированию

                    для студентов специальности 220400

                                                Одобрено

                                    редакционно-издательским советом

                                    Саратовского государственного

                                    технического университета

                          Саратов, 1995

                         В В Е Д Е Н И Е

    Подготовка курсовой работы является  завершающим  этапом  изучения

дисциплины "Технология программирования". В период курсового  проекти-

рования закрепляются теоретические знания и  приобретаются  практичес-

кие навыки разработки программного обеспечения и программной  докумен-

тации.

    В соответствии с рабочей программой дисциплины курсовая работа вы-

полняется в течение второго и третьего семестров в  процессе  проведе-

ния лабораторных занятий, связанных с разработкой программного обеспе-

чения конкретной проблемы, а также в  период  вычислительной  практики

(табл.1). Проблемы, разрабатываемые на лабораторных занятиях и в  ходе

курсового проектирования, представлены в приложениях в виде  постанов-

ки задачи  и  отдельных  частей  технического  задания  согласно  ГОСТ

19.201-78.

                                                             Таблица 1

    Перечень лабораторных работ и отрабатываемых на них вопросов

┌───┬───────────────────────┬────────────────────────────────────────┐

│   │ Наименование лаб.раб. │     Отрабатываемые  вопросы            │

├───┼───────────────────────┼───┬────────────────────────────────────┤

│ 1 │Использование абстрак- │ 1 │Разработка спецификаций типов данных│

│   │ций в разработке прог- │   │для многооконного интерфейса        │

│   │раммного обеспечения   ├───┼────────────────────────────────────┤

│   │                       │ 2 │Разработка спецификаций типов данных│

│   │                       │   │для заданной проблемы               │

│   │                       ├───┼────────────────────────────────────┤

│   │                       │ 3 │Разработка спецификации алгоритма   │

│   │                       │   │проблемы                            │

├───┼───────────────────────┼───┼────────────────────────────────────┤

│ 2 │Анализ требований на   │ 1 │Анализ требований из методических   │

│   │программное обеспечение│   │указаний на лабораторный практикум  │

├───┼───────────────────────┼───┼────────────────────────────────────┤

│ 3 │Разработка спецификаций│ 1 │Разработка функциональной специфика-│

│   │на программное обеспе- │   │ции программы                       │

│   │чение                  │   │                                    │

├───┼───────────────────────┼───┼────────────────────────────────────┤

│ 4 │Проектирование програм-│ 1 │Уточнение спецификаций типов данных │

│   │много обеспечения      ├───┼────────────────────────────────────┤

│   │                       │ 2 │Разработка модульной структуры      │

├───┼───────────────────────┼───┼────────────────────────────────────┤

│ 5 │Программирование       │ 1 │Программирование модулей            │

│   │                       ├───┼────────────────────────────────────┤

│   │                       │ 2 │Компоновка всей программы           │

├───┼───────────────────────┼───┼────────────────────────────────────┤

│ 6 │Тестирование и отладка │ 1 │Индивидуальное тестирование модулей │

│   │программного обеспече- ├───┼────────────────────────────────────┤

│   │ния                    │ 2 │Интегральное тестирование программы │

├───┼───────────────────────┼───┼────────────────────────────────────┤

│ 7 │Сопровождение програм- │ 1 │Адаптация программы                 │

│   │много обеспечения      ├───┼────────────────────────────────────┤

│   │                       │ 2 │Усовершенствование программы        │

├───┼───────────────────────┼───┼────────────────────────────────────┤

│ 8 │Разработка программной │ 1 │Техническое задание                 │

│   │документации           ├───┼────────────────────────────────────┤

│   │                       │ 2 │Программа и методика испытаний      │

│   │                       ├───┼────────────────────────────────────┤

│   │                       │ 3 │Программная документация согласно   │

│   │                       ├───┼────────────────────────────────────┤

│   │                       │ 4 │техническому заданию                │

└───┴───────────────────────┴───┴────────────────────────────────────┘

    Допускается проведение лабораторных занятий и разработка  курсовой

работы группой до 5 человек.

               1.СОДЕРЖАНИЕ И ЭТАПЫ ВЫПОЛНЕНИЯ

    Курсовая работа должна включать оттестированное программное  обес-

печение, соответствующее техническому заданию, и пояснительную  запис-

ку, включающую:

- техническое задание (ГОСТ 19.201-78);

- технический проект;

- программу и методику испытаний (ГОСТ 19.301-79),

а также программную документацию:

- тексты программ (ГОСТ 19.401-78);

- описание программы (ГОСТ 19.404-78);

- пояснительная записка (ГОСТ 19.404-79);

- описание применения (ГОСТ 19.502-78);

- руководство системного программиста (ГОСТ 19.503-79);

- руководство программиста (ГОСТ 19.504-79);

- руководство оператора (ГОСТ 19.505-79),

состав которой определяется руководителем курсового  проектирования  и

указывается в техническом задании.

                                                             Таблица 2

        Этапы и сроки выполнения курсовой работы

┌─────────────────────────────────────────┬──────────────────────────┐

│ Этапы выполнения                        │          Сроки           │

├─────────────────────────────────────────┼──────────────────────────┤

│ Технический проект                      │ 15-17 недели II семестра │

├─────────────────────────────────────────┼──────────────────────────┤

│ Утверждение технического задания и      │   4 неделя III семестра  │

│ программы и методики испытаний          │                          │

├─────────────────────────────────────────┼──────────────────────────┤

│ Приемка программного обеспечения        │ 12-14 недели III семестра│

├─────────────────────────────────────────┼──────────────────────────┤

│ Защита курсовой работы                  │ 15-17 недели III семестра│

└─────────────────────────────────────────┴──────────────────────────┘

                  2.ТЕХНИЧЕСКИЙ ПРОЕКТ

    Согласно ГОСТ 19.102-77  "Стадии  разработки"  технический  проект

предполагает выполнение следующих работ: уточнение струтуры входных  и

выходных данных; разработку алгоритма решения задачи; определение фор-

мы представления входных и выходных данных;  определение  семантики  и

синтаксиса языка; разработку структуры программы; окончательное  опре-

деление конфигурации технических средств.

    В связи с этим, технический проект должен быть разработан в  форме

иерархического набора формальных спецификаций, описывающих  процедуры,

данные и итерации в соответствии с шаблонами, описанными в [1].

                  3.ОБЩИЕ ТРЕБОВАНИЯ

    Разрабатываемое ПО должно работать в многооконном графическом  ре-

жиме и поддерживать работу как клавиатуры,  так  и  манипулятора  типа

"мышь". Рекомендации по разработке графического пользовательского  ин-

терфейса приведены в [1].

    Программная документация, входящая в состав курсовой работы,  дол-

жна соответствовать требованиям Единой системы программной  документа-

ции (ЕСПД) [2]. В [1] приводятся выдержки из основных стандартов ЕСПД.

                                                          ПРИЛОЖЕНИЕ 1

              ГЕОМЕТРИЧЕСКИЙ РЕДАКТОР ПЛОСКИХ ДЕТАЛЕЙ

                         Постановка задачи

    Проектирование изготовления деталей из листовых материалов  всегда

начинается с получения их разверток или выкроек,  которые  могут  быть

представлены  двумерной  абстракцией,  вполне  пригодной  для  решения

многих  технологических  задач.  В   связи   с   этим,   необходимость

разработки   геометрического   редактора,   позволяющего   формировать

двумерные детали, является достаточно актуальной.

    Проектируемые при этом детали должны описываться  своими  наружным

и внутренними контурами.  Будем  полагать,  что  все  контуры  деталей

являются многоугольниками, что позволяет определить объекты  детали  в

форме Бэкуса-Наура следующим образом:

<ДЕТАЛЬ>..................:=<список контуров>

<список контуров>.........:=<наружный контур>

                          :=<наружный    контур><список     внутренних

                             контуров>

<КОНТУР>..................:=<замкнутый список ребер>

<СЕГМЕНТ>.................:=<ребро>

                          :=<разомкнутый список ребер>

<РЕБРО>...................:=<две граничные точки>

<ГРАНИЧНАЯ ТОЧКА>.........:=<две координаты>

<список ребер>............:=<последовательность непересекающихся ребер,

                             в   котором   любые   два   соседних    в

                             последовательности  ребра   имеют   общую

                             граничную точку>

<замкнутый список ребер>..:=<кольцевой список ребер>

<разомкнутый список ребер>:=<линейный список ребер>

    К основным функциям редактирования можно отнести следующие [3]:

- перенос объекта изображения в другое место. Это действие  связано  с

  выполнением поступательного движения;

- копирование объекта изображения в другом месте. Функция  копирования

  подобна функции переноса, но при этом положение копируемого  объекта

  не изменяется;

- поворот объекта. Это преобразование  вращения,  при  котором  объект

  поворачивается на заданный угол относительно исходной ориентации;

- зеркальное отображение объекта.  Выполняется  относительно  заданной

  плоскости;

- уничтожение  объекта  изображения.  Эта  функция  вызывает  удаление

  выбранного объекта изображения с экрана;

- изменение масштаба. Выбранный  объект  изображения  можно  увеличить

  или   уменьшить   с   заданными   масштабными   коэффициентами    по

  координатным осям.

    Многие   из   операций   редактирования   связаны   с   двумерными

преобразованиями графических объектов.  Геометрические  преобразования

на плоскости используются  для  перемещения  и  модификации  объектов.

Преобразования  представлены  в  матричной  форме   с   использованием

однородных координат. Декартовы координаты точки  (x,y)  на  плоскости

заменятся ее однородными координатами (x,y,1).

    Геометрическое преобразование, примененное к объекту или  совокуп-

ности объектов, может быть  конкатенацией  (последовательностью)  нес-

кольких преобразований. Для его описания используется  матрица,  пред-

ставляющая собой произведение матриц более простых преобразований (что

является следствием ассоциативности матричного умножения).

    К основным (элементарным) преобразованиям на  плоскости  относятся

следующие [4]:

- преобразование переноса на вектор Т (tx,ty);

- преобразование поворота относительно начала координат на  угол al;

- преобразование масштаба на вектор Е (ex,ey),

- преобразования зеркальной симметрии относительно координатных осей.

      Матрицы основных двумерных геометрических преобразований

┌────────────────────────────────────────────────────────────────────┐

│                                                                    │

│           │ 1   0   0 │                │ cos(al)  sin(al)  0 │     │

│    M(T) = │ 0   1   0 │     M(R(al)) = │-sin(al)  cos(al)  0 │     │

│           │ tx  ty  1 │                │    0        0     1 │     │

│                                                                    │

│                                                                    │

│        │ ex   0  0 │             │-1  0  0 │            │ 1  0  0 ││

│ M(E) = │  0  ey  0 │   M(S(x)) = │ 0  1  0 │  M(S(y)) = │ 0 -1  0 ││

│        │  0   0  1 │             │ 0  0  1 │            │ 0  0  1 ││

│                                                                    │

└────────────────────────────────────────────────────────────────────┘

    Преобразование вектора P(x,y,1) в вектор P'(x',y',1)  производится

умножением вектора-строки на матрицу M соответсвующего преобразования

                         │ a  b  c │

P' = P*M = │ x  y  1 │ * │ d  e  f │ = │(ax+dy+g) (bx+ey+h) (cx+fy+i)│,

                         │ g  h  i │

    где выражения (ax+dy+g) и (bx+ey+h) соответствуют  компонентам  x'

и y'вектора P'.

    Рассмотрим получение матрицы сложного преобразования, осуществляю-

щего поворот на угол al относительно  произвольной  точки  A  (xa,ya).

Матрица  этого  преобразования   может   быть   получено   с   помощью

последовательности элементарных преобразований:

- перенос  на  вектор  (-xa,-ya)  для  совмещения  центра  вращения  с

  началом координат;

- поворот на угол al относительно начала координат;

- обратный перенос на вектор (xa,ya).

    Суммарная матрица преобразования в данном  случае  будет  получена

из выражения

         │ 1   0   0 │   │ cos(al)  sin(al)  0 │   │  1   0  0 │

     M = │ 0   1   0 │ * │-sin(al)  cos(al)  0 │ * │  0   1  0 │

         │-xa -ya  1 │   │    0        0     1 │   │ xa  ya  1 │

    Программа должна поддерживать локальную базу  данных,  в  которой,

по   желанию   пользователя,   может   сохраняться    информация     о

спроектированных деталях.

    Должна  быть  обеспечена  возможность  как  проектирования   одной

детали, так и формирования размещения уже спроектированных  деталей  в

прямоугольной области.

    Выходная   информация   должна   формироваться   в   виде    файла

геометрической информации (Приложение 4). Если в такой файл  выводится

информация о размещении, то первой деталью должен быть  прямоугольник,

внутри которого расположены детали.

    Естественно, что файл геометрической  информации  может  использо-

ваться редактором в качестве входной информации.

                    Техническое задание

                           ВВЕДЕНИЕ

    Наименование -  геометрический  редактор  плоских  деталей  (далее

просто редактор).

    Краткая характеристика  -  двумерный геометрический редактор с ло-

кальной базой сформированных контуров.

                   1.ОСНОВАНИЕ ДЛЯ РАЗРАБОТКИ

    Задание преподавателя для проведения лабораторных занятий и выпол-

нения курсовой работы.

                   2.НАЗНАЧЕНИЕ РАЗРАБОТКИ

    Редактор предназначен для формирования  и  редактирования  плоских

деталей, ограниченных многоугольниками, а также для их хранения в  ба-

зе данных.

                    3.ТРЕБОВАНИЯ К ПРОГРАММЕ

        3.1.Требования к функциональным характеристикам

    3.1.1.Редактор должен работать в многооконном  графическом  режиме

и поддерживать работу как клавиатуры, так и манипулятора типа "мышь".

    3.1.2.Пользователь, по своему желанию,  должен  иметь  возможность

установки масштабного поля для каждого окна.

    3.1.3.В одном окне возможна  работа  с  несколькими  деталями.

    3.1.4.Программа   должна    обеспечивать     следующие     функции

редактирования: указание,  формирование,  фиксация,  отмена  фиксации,

копирование, удаление, перемещение, вращение точек, ребер,  сегментов,

контуров, деталей.

    Все  указанные  функции,  кроме  копирования,  должны  работать  в

пределах активного окна.  Функция  копирования  должна  осуществляться

также и в межоконном режиме.

    При  наличии  нескольких  деталей  в  окне  редактор   не   должен

допускать взаимных наложений.

    3.1.5.Редактор должен обеспечивать расчет следующих характеристик:

- для точки:

  - координаты в принятом масштабном поле;

- для ребра:

  - длина;

  - угол наклона;

- для детали (контура):

  - периметр;

  - площадь;

  - положение центра масс;

  - положение центра давления;

  - момент инерции относительно произвольной точки.

    3.1.6.Информация о сформированной детали может  быть  сохранена  в

локальной базе данных редактора.

    3.1.7.Должен быть обеспечен графический  просмотр  базы  данных  с

возможностью  удаления  из  нее  или  копирования  в   активное   окно

указанной детали.

    3.1.8.Информация о сформированной детали может  быть  сохранена  в

форме выходного файла следующей структуры:

...

...

    3.1.9.Редактор должен уметь  считывать  геометрическую  информацию

из файла описанной структуры.

...

...

    3.1.10.Редактор   должен   позволять   размещение    деталей     в

прямоугольной  области  и  вывод   получаемого   размещения   в   файл

геометрической   информации,   первой   деталью     которого     будет

прямоугольник области размещения.

                   3.2.Требования к надежности

    3.2.1.Программа   должна   обрабатывать     ошибочные     действия

пользователя и сообщать ему об этом.

    3.2.2.Программа должна обеспечивать контроль  входной  и  выходной

информации в форме файлов геометрической информации.

                           . . .

        3.4.Требования к составу и параметрам технических средств

    3.4.1.Программное  обеспечение  разрабатывается  для  персональной

вычислительной  техники  типа  не  ниже  IBM  PC-386   со   следующими

характеристиками:

- объем ОЗУ не ниже 1 Mb;

- графический адаптер SVGA;

- манипулятор типа "мышь".

    3.4.2.ЭВМ должна работать под управлением операционной системы  не

ниже чем MS-DOS 5.0.

        3.5.Требования к информационной и программной совместимости

    3.5.1.Требование   информационной   совместимости   должно    быть

обеспечено работой с файлами  геометрической  информации  определенной

структуры в качестве входной и выходной информации.

                                                          ПРИЛОЖЕНИЕ 2

             СИСТЕМА ТРИАНГУЛЯЦИИ МНОГОУГОЛЬНЫХ ОБЛАСТЕЙ

                       Постановка задачи

    Метод конечных элементов  (МКЭ)  широко  применяется  для  решения

различных задач, математическая модель которых  представляется  диффе-

ренциальными уравнениями в частных производных.  Первый  этап  решения

задачи этим методом состоит в дискретизации рассматриваемой области на

треугольники, четырехугольники, трехгранные пирамиды ит.д. Такое  раз-

биение несет геометрическую информацию о покрытии области  элементами,

с каждым из которых связано определенное количество  численных  значе-

ний, необходимых для последующих вычислений в МКЭ (построение  матриц,

блокирование некоторых степеней свободы, решение систем уравнений, ви-

зуализация и т.д.). Эту информацию  удобно  определить  как  структуру

данных,  содержащую  в  сжатой  и   доступной   форме   все   величины

(геометрические и числовые).

    Многочисленные методы построения разбиений областей с геометричес-

кой точки зрения подразделяются на три основных класса [4,5]:

- построение  разбиения,  осуществляемого  подходящим  преобразованием

  отображения разбиения области с геометрически простой формой;

- построение  разбиения,  осуществляемого  подходящим  преобразованием

  уже существующего разбиения;

- прямое,  элемент  за  элементом,  построение  разбиения,  начиная  с

  задания распределения точек в области или на границе.

    Настоящее задание заключается в построении разбиения двумерной об-

ласти, ограниченной  многоугольником,  на  треугольники.  Треугольники

должны иметь примерно равную площадь и по форме приближаться к равнос-

торонним. Степень дискретизации (количество треугольников  в  области)

может регулироваться пользователем. Исходя из особенностей МКЭ необхо-

димо, чтобы все узлы (вершины  треугольников)  были  пронумерованы,  а

разность  номеров  вершин  любого  треугольника  разбиения   была   бы

минимальной.

    Разрабатываемое ПО должно использовать файл геометрической  инфор-

мации (Приложение 4) в качестве входной информации об области  разбие-

ния.

    Выходная информация о разбиении  области  должна  формироваться  в

форме файла такого же типа, в котором каждый  треугольник  сети  будет

представлен  как  деталь,  а  размещение  вершин   в   соответствующем

дескрипторе   должно   удовлетворять   оговоренному   выше     условию

минимизации разности номеров.

    Программа должна быть оснащена локальной базой данных, в  которой,

по желанию пользователя, может  сохраняться  полученная  информация  о

разбиениях.

                       Техническое задание

                              ВВЕДЕНИЕ

    Наименование - система трангуляции многоугольных  областей  (далее

просто триангулятор).

    Краткая характеристика - двумерный триангулятор с локальной  базой

сформированных сеток деталей.

                     1.ОСНОВАНИЕ ДЛЯ РАЗРАБОТКИ

    Задание преподавателя для проведения лабораторных занятий и выпол-

нения курсовой работы.

                      2.НАЗНАЧЕНИЕ РАЗРАБОТКИ

    Триангулятор предназначен для формирования и редактирования  треу-

гольной сетки, заполняющей заданный многоугольник, а также для  хране-

ния полученных сетей в базе данных.

                     3.ТРЕБОВАНИЯ К ПРОГРАММЕ

           3.1.Требования к функциональным характеристикам

    3.1.1.Редактор должен работать в многооконном  графическом  режиме

и поддерживать работу как клавиатуры, так и манипулятора типа "мышь".

    3.1.2.Пользователь, по своему желанию,  должен  иметь  возможность

установки масштабного поля для каждого окна.

    3.1.3.Программа  должна   обеспечивать   разбиение   многоугольной

области  на  треугольники,  количество  которых  может   устанавливать

пользователь.

    3.1.4.Программа  должна   включать,   по   желанию   пользователя,

минимизацию разности номеров вершин треугольников.

    3.1.5.Информация о сформированной сети  треугольников  может  быть

сохранена в локальной базе данных триангулятора.

    3.1.6.Должен быть обеспечен графический  просмотр  базы  данных  с

возможностью  удаления  из  нее  или  копирования  в   активное   окно

указанного разбиения.

    3.1.7.Информация о сформированном разбиении может быть сохранена в

форме выходного файла геометрической информации следующей структуры:

...

...

    3.1.8.Триангулятор   может   использовать   в   качестве   входной

информации  файл  геометрической  информации  о  детали  или  об   уже

имеющемся разбиении.

    3.1.9.Программа должна обеспечивать возможность просмотра выхоного

файла.

                   3.2.Требования к надежности

    3.2.1.Программа   должна   обрабатывать     ошибочные     действия

пользователя и сообщать ему об этом.

    3.2.2.Программа должна обеспечивать контроль  входной  и  выходной

информации в форме файлов геометрической информации.

                           . . .

        3.4.Требования к составу и параметрам технических средств

    3.4.1.Программное  обеспечение  разрабатывается  для  персональной

вычислительной  техники  типа  не  ниже  IBM  PC-386   со   следующими

характеристиками:

- объем ОЗУ не ниже 1 Mb;

- графический адаптер SVGA;

- манипулятор типа "мышь".

    3.4.2.ЭВМ должна работать под управлением операционной системы  не

ниже чем MS-DOS 5.0.

        3.5.Требования к информационной и программной совместимости

    3.5.1.Требование   информационной   совместимости   должно    быть

обеспечено работой с файлами  геометрической  информации  определенной

структуры в качестве входной и выходной информации.

                                                          ПРИЛОЖЕНИЕ 3

     СИСТЕМА МИНИМИЗАЦИИ ПУТИ РЕЖУЩЕГО ИНСТРУМЕНТА ПРИ РАСКРОЕ

                         Постановка задачи

    Получение заготовок во многих отраслях,  таких  как  судостроение,

авиастроение6  легкая  промышленность,   автомобилестроение   и   др.,

основано на вырезке необходимых  контуров  из  листового  материала  с

помощью термических устройств. Минимизация пути  режущего  инструмента

обеспечивает существенную экономию энергии и трудозатрат.

    Рассмотрим  исходную  постановку  задачи.  Имеется   прямоугольная

область,  в  которой  размещены  многоугольные  контуры  деталей   без

отверстий. касания между деталями  могут  быть  только  точечными.  По

отношению к прямоугольной области контуры деталей  могут  касаться  ее

границы либо вершиной, либо  ребром.  Термическое  режущее  устройство

имеет автоматизированное двухкоординатное управление и  начинает  свою

работу с нижнего левого угла прямоугольной области.

    Очевидно,минимальным будет путь, когда режущее устройство  пройдет

через каждое ребро любого контура только один раз. Если точки  касания

контуров  деталей  рассматривать  как  вершины  плоского   графа,   то

сформулированная задача минимизации пути  является  задачей  опреления

цикла Эйлера для этого графа [6].

    Входная информация для системы будет представляться в форме  файла

геометрической информации (Приложение 4). Первой деталью в этом  файле

будет прямоугольник области размещения.  Детали,  размещенные  в  этой

области, будут представлены в произвольном порядке.

    Найденный путь режущего устройства может быть показан на экране  и

выведен в форме файла геометрической информации.  Перечисление  вершин

треугольников  в  соответствующем  дескрипторе  этого   файла   должно

соответствовать найденному пути.

    Полученные решения могут быть сохранены в локальной  базе  данных,

для которой должен  быть  организован  графический  просмотр,  запись,

удаление и копирование в активное окно.

                       Техническое задание

                              ВВЕДЕНИЕ

    Наименование - система минимизации пути режущего  инструмента  при

раскрое листовых материалов (далее просто минимизатор).

    Краткая характеристика - двумерный минимизатортор с локальной  базой

сформированных маршрутов резки.

                     1.ОСНОВАНИЕ ДЛЯ РАЗРАБОТКИ

    Задание преподавателя для проведения лабораторных занятий и выпол-

нения курсовой работы.

                      2.НАЗНАЧЕНИЕ РАЗРАБОТКИ

    Минимизатор  предназначен  для  формирования   минимального   пути

вырезки многоугольных контуров, размещенных в  прямоугольной  области,

а также для хранения полученных маршрутов в базе данных.

                     3.ТРЕБОВАНИЯ К ПРОГРАММЕ

        3.1.Требования к функциональным характеристикам

    3.1.1.Редактор должен работать в многооконном  графическом  режиме

и поддерживать работу как клавиатуры, так и манипулятора типа "мышь".

    3.1.2.Пользователь, по своему желанию,  должен  иметь  возможность

установки масштабного поля для каждого окна.

    3.1.3.Минимизатор  должен  обеспечивать  нахождение   минимального

пути  с  проходом  только  один  раз  через   каждое   ребро   каждого

многоугольного контура детали в области размещения.

    3.1.4.Найденный путь должен демонстрироваться на экране в различных

режимах.

    3.1.5.Информация о размещении контуров и  сформированном  маршруте

может быть сохранена в локальной базе данных минимизатора.

    3.1.6.Должен быть обеспечен графический  просмотр  базы  данных  с

возможностью  удаления  из  нее  или  копирования  в   активное   окно

указанного размещения с имеющимся маршрутом.

    3.1.7.Информация о  размещении  и  сформированном  маршруте  может

быть  выведена  в  форме  файла  геометрической  информации  следующей

структуры:

...

...

    3.1.8.Перечисление  вершин  контуров  деталей  в   соответствующем

дескрипторе выходного  файла  должно  соответствовать  сформированному

маршруту резки.

    3.1.9.Программа должна использовать в качестве входной  информации

файл  геометрической  информации,  первой   деталью   которого   будет

прямоугольник области размещения.

    3.1.10.Программа должна обеспечивать просмотр выходного файла.

                   3.2.Требования к надежности

    3.2.1.Программа   должна   обрабатывать     ошибочные     действия

пользователя и сообщать ему об этом.

    3.2.2.Программа должна обеспечивать контроль  входной  и  выходной

информации в форме файлов геометрической информации.

                           . . .

        3.4.Требования к составу и параметрам технических средств

    3.4.1.Программное  обеспечение  разрабатывается  для  персональной

вычислительной  техники  типа  не  ниже  IBM  PC-386   со   следующими

характеристиками:

- объем ОЗУ не ниже 1 Mb;

- графический адаптер SVGA;

- манипулятор типа "мышь".

    3.4.2.ЭВМ должна работать под управлением операционной системы  не

ниже чем MS-DOS 5.0.

        3.5.Требования к информационной и программной совместимости

    3.5.1.Требование   информационной   совместимости   должно    быть

обеспечено работой с файлами  геометрической  информации  определенной

структуры в качестве входной и выходной информации.

                                                          ПРИЛОЖЕНИЕ 4

         СТРУКТУРА ДАННЫХ ФАЙЛА ГЕОМЕТРИЧЕСКОЙ ИНФОРМАЦИИ

    Файл должен иметь следующую структуру (см.рис):

- информационная часть;

- дескриптор деталей;

- дескриптор контуров;

- дескриптор ребер;

- дескриптор вершин;

    Информационная часть должна содержать следующую информацию:

- количество деталей в соответствующем дескрипторе;

- количество контуров в соответствующем дескрипторе;

- количество ребер в соответствующем дескрипторе;

- количество вершин в соответствующем дескрипторе.

    Каждая деталь должна быть представлена в своем дескрипторе:

- количеством контуров детали;

- списком контуров детали  (номеров  контуров  в  дескрипторе;  первым

  всегда указывается номер наружного контура детали).

    Каждый контур должен быть представлен в своем дескрипторе:

- количеством ребер контура;

- списком  ребер  контура  (номеров   ребер   в   дескрипторе;   ребра

  указываются  последовательно  в  порядке  обхода   против   движения

  часовой стрелки для наружных контуров и по движению часовой  стрелки

  для внутренних контуров;  если  расположение  начальной  и  конечной

  вершин ребра не соответствует требуемому  направлению  обхода  ребер

  контура, то номер этого ребра должен быть с отрицательным знаком).

    Каждое  ребро  должно  быть  представлено  в   своем   дескрипторе

номерами начальной и конечной вершин в их дескрипторе.

    Каждая вершина должна быть представлена в своем дескрипторе  двумя

координатами (x,y).

              Структура файла геометрической информации

                     ┌─────────────────────┐

┌────────────────────┤  Количество деталей │   ИНФОРМАЦИОННАЯ ЧАСТЬ

│                    ├─────────────────────┤

│                    │ Количество контуров ├─────────────────────────┐

│                    ├─────────────────────┤                         │

│ ┌──────────────────┤   Количество ребер  │                         │

│ │                  ├─────────────────────┤                         │

│ │                  │  Количество вершин  ├──────────────────────┐  │

│ │                  └─────────────────────┘                      │  │

│ │   ┌────────┬───────────┐                                      │  │

│ │   │Кол-во  │ Списки    │  ДЕСКРИПТОР ДЕТАЛЕЙ                  │  │

│ │   │контуров│ контуров  │                                      │  │

│ │   └────────┴───────────┘                                      │  │

│ │   ┌────────┬─┬─┬─┬─┬─┬─┐                                      │  │

│ │   │        │ │ │ │ │ │ │                                      │  │

│ │   │        │ │ │ │ │ │ │                                      │  │

└─┼──│        ││││ │ │ │                                      │  │

  │   │        │││││││ │ │ │                                      │  │

  │   │        │││││││ │ │ │                                      │  │

  │   │        │││││││ │ │ │                                      │  │

  │   │        │││││││ │ │ │                                      │  │

  │   └────────┴│┴│┴│┴─┴─┴─┘            ┌────────┬───────────┐    │  │

  │             │ │ │ДЕСКРИПТОР КОНТУРОВ│кол-во  │  Списки   │    │  │

  │             │ │ │                   │ребер   │  ребер    │    │  │

  │             │ │ │                   └────────┴───────────┘    │  │

  │             │ │ │                   ┌────────┬─┬─┬─┬─┬─┬─┐    │  │

  │             └─┼─┼──────────────────│        │ │ │ │ │ │ │    │  │

  │               │ │                   │        │ │ │ │ │ │ │    │  │

  │               │ └──────────────────│        │││││ │ │───┼──┘

  │               │                     │        │││││││││ │ │    │

  │               │                     │        │││││││││ │ │    │

  │               └────────────────────│        │││││││││ │ │    │

  │                                     │        │││││││││ │ │    │

  │   ┌─────────┬──────────┐            └────────┴│┴│┴│┴│┴─┴─┘    │

  │   │ Начало  │  Конец   │ ДЕСКРИПТОР РЕБЕР     │ │ │ │         │

  │   └─────────┴──────────┘                      │ │ │ │         │

  │   ┌─────────┬──────────┐                      │ │ │ │         │

  │   │         │          │─────────────────────┼─┘ │ │         │

  │   │         │          │─────────────────────┼───┼─┘         │

  └──│        │         │                      │   │           │

      │    │    │    │     │─────────────────────┼───┘           │

      │    │    │    │     │─────────────────────┘               │

      │    │    │    │     │                                      │

      │    │    │    │     │                                      │

      └────┼────┴────┼─────┘                                      │

           │         │                  ┌─────────┬──────────┐    │

           │         │ДЕСКРИПТОР ВЕРШИН │    X    │    Y     │    │

           │         │                  └─────────┴──────────┘    │

           │         │                  ┌─────────┬──────────┐    │

           │         │                  │         │          │    │

           │         └─────────────────│         │          │    │

           │                            │         │          │    │

           └───────────────────────────│         │          │───┘

                                        │         │          │

                                        │         │          │

                                        │         │          │

                                        │         │          │

                                        └─────────┴──────────┘

                                                          ПРИЛОЖЕНИЕ 5

             ИНТЕРАКТИВНЫЙ КОРРЕКТИРОВЩИК ПРАВОПИСАНИЯ

                        Постановка задачи

    Корректировщик правописания представляет собой программу,  которая

получает в качестве входных данных словарь и текстовый файл и  исправ-

ляет затем в текстовом файле ошибки правописания. Программа  работает,

отыскивая каждое слово текстового файла в словаре. Если  слово  отсут-

ствует в словаре, то оно может содержать или же не содержать ошибку. В

обоих случаях программа отражает слово на экране с объемом  окружающе-

го текста, достаточным для того, чтобы показать  контекст,  в  котором

оно находится. Пользователь может предпринять  несколько  действий  по

исправлению ошибки: перепечатать неверно  напечатанное  слово,  заста-

вить программу ввести его без изменений и включить это  слово  в  сло-

варь. Результатом работы корректировщика является  исправленный  текст

и, возможно, обновленный словарь.

    Корректировщик правописания должен  иметь  достаточно  эффективную

реализацию  по  двум  соображениям.  Во-первых,  программа   выполняет

большое количество вычислений, поэтому неэффективная  реализация  сде-

лает ее непрактичной. Во-вторых, поскольку программа является интерак-

тивной, работа пользователя за терминалом должна быть максимально  об-

легчена. Основная проблема заключается в поиске слов  в  словаре.  Эта

операция выполняется для каждого слова во входном тексте. Для удовлет-

ворения требования по эффективности нам необходим алгоритм  просмотра,

более быстрый, чем прстой линейный поиск в словаре.  Примеры  алгорит-

мов просмотра с приемлемой эффективностью есть (1) бинарный  поиск  по

упорядоченному списку, (2) просмотр упорядоченного бинарного дерева  и

(3) хэширование.

    Мы будем ориентироваться на словарь из нескольких тысяч слов. Сло-

варь представляет собой ASCII файл, слова  в  котором  представлены  в

буквах нижнего регистра и разделены пробелами, символами  табуляции  и

перевода строки. Слова в словаре неупорядоченны.

   Этот набор требований к программе является  неполным.  Для  словаря

может понадобиться дополнительная информация. Вы должны также  принять

решение о возможностях, предоставляемых программой, и так же  подробно

проанализировать обработку входных символов. Можно вывести ряд предпо-

ложений:

1.Символьная обработка. Вы должны определить то, каким  образом  прог-

рамма обращается с символами пунктуации, например с кавычками, со сло-

вами или акронимами, включающими цифры, дефисами, стандартными  сокра-

щениями ("и т.д.") и так далее. Например, выможете рассматривать дефи-

сы как ограничители, поскольку большинство слов  с  дефисами  являются

сочетаниями из нескольких распознаваемых подчастей.

2.Интерфейс с пользователем. Интерфейс с пользователем  в  интерактив-

ной программе является весьма важной частью, которая должна быть  тща-

тельно  продумана.  Необходимо,  чтобы  программой  можно  было  легко

пользоваться. На этот счет имеются следующие соображения: а)  возложи-

те на пользователя указание имен для исходного и результирующего  фай-

лов - как для текста, так и для словаря; б) дайте возможность  пользо-

вателю исправить несколько текстовых файлов без  выхода  из  программы

корректировщика; в) запрашивайте у пользователя  ввод  возможных  пра-

вильных ответов при отображении неверно заданного слова; г)  реализуй-

те команду help  ("вспомогательная  информация"),  описывающую  эффект

каждого из вышеописанных ответов подробно.

                                                          ПРИЛОЖЕНИЕ 6

              ИНТЕРАКТИВНЫЙ ФОРМАТИРОВЩИК ТЕКСТА

                      Постановка задачи

    Входные данные для форматировщика  текста  состоят  из  последова-

тельности вводимых с клавиатуры неформатированных строк текста.  Прог-

рамма выдает выравненный по правому краю, разбитый построчно и  содер-

жащий абзацные отступы текст.

    По умолчанию строка должна включать 70  символов,  за  исключением

символа перевода строки, и 60 строк в  странице.  Пользователь  должен

иметь возможность переустановки этих значений.

    Входная строка состоит из последовательности слов и символов  раз-

деления слов. К символам, разделяющим слова, относится символ пробела,

символ табуляции и символ перехода к новой строке. Все остальные  сим-

волы являются состовляющими слов.

    Форматировщик имеет два основных режима работы. В режиме ввода ин-

формации входной текст разбивается на строки так,  чтобы  последним  в

строке было первое слово, выходящее за пределы форматирования. В режи-

ме форматирования в строке остаются слова,  не  выходящие  за  пределы

форматирования. Затем строка выравнивается по правому краю. Выравнива-

ние осуществляется вставкой между словами дополнительных символов про-

бела до тех пор, пока крайний правый символ последнего слова  не  ока-

жется в крайней правой позиции строки. Пробелы должны добавляться мак-

симально равномерно, чтобы избежать широких пустых участков.  Формати-

рование должно осуществляться от текущей позиции  курсора  до  границы

абзаца.

                       Л И Т Е Р А Т У Р А

    1.Курсовое проектирование.  Методические  указания  для  студентов

специальности 220400. Электронная версия.

    2.Единая система программной документации.- М.: Изд-во стандартов,

1985.- 128 с.

    3.Гардан И., Люка М. Машинная графика и автоматизация конструиро-

вания.- М.: Мир, 1987.- 272 с.

    4.Математика и САПР: В 2-х кн.  Кн.1.-  М.:  Мир,  1988.-  204  с.

Кн.2.М.: Мир, 1989.- 264 с.

    5.Шикин Е.В.,  Боресков  А.В.,  Зайцев  А.А.  Начала  компьютерной

графики.М.: ДИАЛОГ-МИФИ, 1993.- 138 с.

    6.Липский В. Комбинаторика для  программистов.-  М.:  Мир,  1988.-

213 с.

                       С О Д Е Р Ж А Н И Е

    В В Е Д Е Н И Е................................................. 3

    1.Содержание и этапы выполнения................................. 4

    2.Технический проект............................................ 4

    3.Общие требования.............................................. 4

    Приложение 1. Геометрический редактор плоских деталей........... 5

    Приложение 2. Система триангуляции многоугольных областей....... 9

    Приложение 3. Система минимизации пути режущего инструмента при

                  раскрое...........................................11

    Приложение 4. Структура данных файла геометрической информации..13

    Приложение 5. Интерактивный корректировщик текста...............15

    Приложение 6. Интерактивный форматировщик текста................16

    Литература......................................................17

        Т Е Х Н О Л О Г И Я     П Р О Г Р А М М И Р О В А Н И Я

              Методические указания к курсовой работе

    Составили:  Клеванский Николай Николаевич

                Алексеева Елена Юрьевна

     Рецензент: Лалетин Сергей Сергеевич

     Редактор


      1.ИСПОЛЬЗОВАНИЕ АБСТРАКЦИЙ И СПЕЦИФИКАЦИЙ В РАЗРАБОТКЕ ПО

                    1.1.Абстракции программы

    Любые достаточно большие программы составляются  путем  декомпози-

ции задачи. Эта декомпозиция основана на опознавании абстракций.

    Базовая парадигма в подходе к любой большой задаче ясна: необходи-

мо "разделять и властвовать". Абстракция представляет собой  эффектив-

ный способ декомпозиции, осуществляемый посредством  изменения  списка

детализации. Абстрагирование от  проблемы  предполагает  игнорирование

ряда подробностей с тем, чтобы свести задачу к более простой.

    Задачи абстрагирования и последующей декомпозиции типичны для про-

цесса создания программ: декомпозиция используется для разбиения прог-

раммы на компоненты, которые могут быть затем объединены, позволив ре-

шить основную задачу; абстрагирование же предполагает продуманный  вы-

бор компонент.

    В общем случае, любую программу можно представить набором  следую-

щих процедурных абстракций. Причем процедура преобразования может  но-

сить как единичный характер, так и итеративный.

┌────────────────────────────────────────────────────────────────────┐

│                                                                    │

│┌────────────┐          ┌────────────────┐            ┌────────────┐│

││    Ввод    │ исходная │ Преобразование │преобразов. │   Вывод    ││

││            │═════════│                │═══════════│            ││

││ информации │информация│   информации   │информация  │ информации ││

│└────────────┘          └────────────────┘            └────────────┘│

│                                                             ║      │

│                                                 Выходная    ║      │

│                                              ══════════════╝      │

│                                                 информация         │

└────────────────────────────────────────────────────────────────────┘

  Рис.1.1.Абстракция программы  как  набора  процедур,  обрабатывающих

          данные.

    Анализируя рис.1.1, можно получить обобщенную абстракцию  процеду-

ры в следующем виде.

┌────────────────────────────────────────────────────────────────────┐

│                  Управляющая                                       │

│                ════════════════════╗                               │

│                  информация        ║                               │

│                                    ║                               │

│                                    ­                               │

│                              ┌───────────┐                         │

│          Входная             │           │   Выходная              │

│         ════════════════════│ Процедура │════════════════════    │

│          информация          │           │   информация            │

│                              └───────────┘                         │

│                                                                    │

└────────────────────────────────────────────────────────────────────┘

                   Рис.1.2.Абстракция процедуры

    Рассматривая программу не как набор процедур, а прежде  всего  как

некоторые наборы данных, каждый из которых  имеет  разрешенную  группу

процедур, получаем следующее абстрактное представление программы.

┌────────────────────────────────────────────────────────────────────┐

│           Ввод                                                     │

│      ╔═══════════════                                              │

│      ║ информации                                                  │

│      ­                                                             │

│┌────────────┐                                        ┌────────────┐│

││  Исходная  │ Преобразование                         │  Выходная  ││

││            │══════════════════╗                ╔═══│            ││

││ информация │   информации     ║                ║    │ информация ││

│└────────────┘                  ║                ║    └────────────┘│

│                   ╔════════════╝                ║                  │

│                   ║                             ╚═════╗            │

│                   ║   ┌─────────────────┐             ║            │

│                   ║   │ Преобразованная │   Вывод     ║            │

│                   ╚══│                 │═════════════╝            │

│                       │   информация    │ информации               │

│                       └─────────────────┘                          │

│                                                                    │

└────────────────────────────────────────────────────────────────────┘

 Рис.1.3.Абстракция  программы  как  набора   данных,   обрабатываемых

         процедурами.

    Анализ рис.1.3 позволяет также получить абстракцию данных.

┌────────────────────────────────────────────────────────────────────┐

│               Процедуры                                            │

│              ═════════════════╗                                    │

│               управления      ║                                    │

│                               ­                                    │

│                          ┌──────────┐                              │

│          Процедуры       │          │     Процедуры                │

│         ════════════════│  Данные  │═══════════════              │

│          ввода           │          │     вывода                   │

│                          └──────────┘                              │

│                               ‑                                    │

│               Процедуры       ║                                    │

│              ═════════════════╝                                    │

│               преобразования                                       │

└────────────────────────────────────────────────────────────────────┘

                    Рис.1.4.Абстракция данных.

    Полученные абстракции процедуры и данных  лежат  в  основе  многих

формализованных методов разработки спецификаций программного обеспече-

ния. Условно эти методы можно разделить на формульные и графические.

    Наиболее широко используются абстракции процедур,  которыми  любой

программист начинает пользоваться с первых же шагов практической  дея-

тельности. Разделяя в программе тело процедуры и обращения к ней, язык

высокого уровня реализует два важных метода абстракции: абстракцию че-

рез параметризацию и абстракцию через спецификацию.

    Абстракция через параметризацию  позволяет,  используя  параметры,

представить фактически неограниченный набор различных  вычислений  од-

ной прграммой, которая есть абстракция всех  этих  наборов.  Например,

необходима прцедура сортировки массива целых чисел А.  При  дальнейшей

разработке программы возможно возникновение потребности  в  сортировке

другого массива, но уже с другим именем. Использование абстракции  че-

рез параметризацию обобщает процедуру сортировки  и  делает  ее  более

универсальной.

    Абстракция через параметризацию является важным средством  повыше-

ния универсальности программ. Программа, сортирующая произвольный мас-

сив чисел, полезнее той, которая работает только с  конкретным  масси-

вом чисел.  Дальнейшее  абстрагирование  позволяет  добиться  большего

обобщения процедуры. Например, можно определить абстракцию такой  про-

цедуры сортировки, которая работает над массивами  как  целых,  так  и

действительных чисел или даже вообще над  различными  массивоподобными

структурами.

    Абстракция через спецификацию позволяет абстрагироваться  от  про-

цесса вычислений, описанных в теле прцедуры, до уровня знания лишь то-

го, что что данная прцедура должна в итоге реализовать. Это достигает-

ся путем задания для каждой процедуры  спецификации,  описывающей  эф-

фект ее работы, после чего смысл обращения к данной  процедуре  стано-

вится ясным через анализ этой спецификации, а не самого тела  процеду-

ры. В какой-то степени достаточно информативный  комментарий,  связан-

ный с процедурой, позволяет работать с ней без анализа тела  прцедуры.

Одним из удобных способов составления таких комментариев является  ис-

пользование пар утверждений. Первое  утверждение  (начальное  условие)

задает на входе процедуры истинность или ложность некоторого  условия,

связанного с входной информацией. Второе утверждение  (конечное  усло-

вие) задает некоторое условие, которое предполагается истинным по  за-

вершению данной процедуры в предположении, что для этой процедуры  бы-

ло удовлетворено начальное условие.

    При анализе спецификации для уяснения смысла обращения к  процеду-

ре следует придерживаться двух правил.

    1.После выполнения процедуры можно считать, что  конечное  условие

выполнено.

    2.Можно ограничиться только теми  свойствами,  которые  подразуме-

вает конечное условие.

    Эти два правила демонстрируют  два  преимущества,  предоставляемых

абстракцией через спецификацию. Первое из них состоит в том,  что  для

использования данной процедуры нет необходимости знакомиться с ее  те-

лом. Второе правило уточняет абстрагирование от тела  процедуры  путем

отказа от несущественной информации. Такое "забывание информации"  от-

личает абстракцию от декомпозиции.

    Абстракции через параметризацию и через спецификацию позволяют оп-

ределить три различных вида абстракций:  процедурную  абстракцию,  аб-

стракцию данных и абстракцию через итерацию.  В  общем  случае  каждая

процедурная абстракция, абстракция через  данные  и  абстракция  через

итерацию используют оба способа.

    Процедурная абстракция позволяет расширить заданную некоторым язы-

ком программирования виртуальную машину  новой  операцией.  Такой  вид

расширения наиболее полезен для задач, которые легко представляются  в

виде набора независимых функциональных единиц. Однако часто оказывает-

ся более удобным добавить к виртуальной машине несколько объектов дан-

ных с новыми типами.

    Поведение объектов данных наиболее естественно представить в  тер-

минах набора операций, применимых к данным объектам. Такой набор вклю-

чает в себя операции по созданию объектов,  полученнию  информации  от

них и, возможно, их модификации. Таким образом, абстракция данных  (и-

ли тип данных) состоит из набора объектов.

    В дополнение к процедурным абстракциям и абстракциям  данных  сле-

дует рассмотреть абстракцию через итерацию. Абстракция через  итерацию

дает возможность не рассматривать информацию, не имеющую прямого отно-

шения к управляющему потоку или циклу.  Типичная  абстракция  итерации

позволяет обработать все элементы объектов данных без накладывания ка-

ких-либо ограничений на последовательность обработки.

                  1.2.Процедурная абстракция

    Процедуры объединяют в себе методы абстракции  через  параметриза-

цию и через спецификацию, позволяя абстрагировать  отдельную  операцию

или событие. Процедура выполняет преобразование входных  аргументов  в

выходные. Более точно, это есть отображение  набора  значений  входных

аргументов в выходной набор результатов с возможной модификацией вход-

ных значений.

    Абстракция представляет собой некоторый способ отображения за счет

абстрагирования от "несущественных" подробностей и отношения к  решае-

мой задаче.

    В абстракции через параметризацию  осуществляется  абстрагирование

от конкретных используемых данных. Эта абстракция определяется в  тер-

минах формальных параметров. Фактические данные  связываются  с  этими

параметрами в момент использования  такой  абстракции.  Параметризация

позволяет обобщить модули, уменьшить объем программы и объем модифика-

ций.

    В абстракции через спецификацию фокусируется внимание  на  особен-

ностях, от которых зависит пользователь абстракции, при  абстрагирова-

нии от подробностей реализации этих особенностей.  Главное  преимущес-

тво абстракции через спецификацию заключается в несущественности  спо-

соба реализации.

    Абстракция через спецификацию наделяет структуру  программы  двумя

отличительными особенностями. Первая из этих особенностей  заключается

в локальности, которая означает, что реализация одной  абстракции  мо-

жет быть создана или рассмотрена без необходимости анализа  реализации

какой-либо другой абстракции. Второй особенностью  является  модифици-

руемость. Если реализация абстракции изменяется,  но  ее  спецификация

при этом остается прежней, то эти изменения не повлияют на  оставшуюся

часть программы.

    Для достижения указанных преимуществ необходимо дать четкие  опре-

деления абстракций. Абстракция будет определяться посредством специфи-

каций с использованием языка спецификаций.

    Спецификация процедуры состоит из заголовка  и  описания  функции,

выполняемой процедурой. Заголовок содержит имя процедуры, номер, поря-

док и типы входных и выходных параметров. Кроме этого, выходные  пара-

метры могут, а входные должны быть поименованы.

    Семантическая часть спецификации состоит  из  трех  предложений  -

requires (требует), modifies (модифицирует) и  effects  (делает).  Эти

предложения должны появляться в указанном ниже порядке, однако предло-

жения requires и modifies обязательными не являются.

 ┌──────────────────────────────────────────────────────────────────┐

 │ pname = proc(входные данные) returns (выходные данные)           │

 │      requires  - этот оператор задает необходимые требования     │

 │      modifies  - этот оператор идентифицирует все модифицируемые │

 │                  входные данные                                  │

 │      effects   - этот оператор описывает выполняемые функции     │

 └──────────────────────────────────────────────────────────────────┘

        Рис.1.5.Шаблон спецификации для процедурных абстракций.

    Предложение requires задает ограничения, накладываемые на абстрак-

цию. Предложение requires необходимо в том случае, если процедура  яв-

ляется частичной, то есть если ее поведение для некоторых входных зна-

чений недетерминировано. Если же процедура глобальна, то есть ее пове-

дение определено для всех входных значений,  то  предложение  requires

может быть опущено. В этом случае единственными требованиями, предъяв-

ляемыми при обращении к процедуре, являются  требования,  указанные  в

заголовке, о числе и типе аргументов.

    Оператор modifies задает список имен входных параметров, модифици-

руемых процедурой. Если входные параметры не указаны, то это предложе-

ние может быть опущено.

    Предложение effects описывает работу процедуры со  значениями,  не

охваченными предложением requires. Оно определяет выходные значения  и

модификации, производимые над входными параметрами, перечисленными в в

списке modifies. Предложение effects составляется исходя из  предполо-

жения, что требования предложения requires удовлетворены. Однако в том

случае, когда требования в предложении requires  не  удовлетворены,  о

поведении процедуры ничего не сообщается.

    На рис.1.6 приведено несколько процедурных спецификаций.  Процеду-

ры sort и search не изменяют входные данные, а процедура clear - изме-

няет, что отмечено в предложении modifies ее  спецификации.  Процедуры

sort и clear являются общими процедурами, поскольку их спецификации не

содержат предложений requires. Процедура  search  является  частичной;

она выполняет свои функции только в том случае,  если  входной  массив

отсортирован. Однако в предложении effects ничего не говорится  о  ре-

зультатах работы процедуры для неотсортированного входного массива.

    Приведенная на рис.1.6 спецификация процедуры  sort  предназначена

для работы с массивом целых чисел. Эта процедура была бы более  полез-

ной, если бы могла работать с массивами любых типов данных -  действи-

тельных чисел, символьных, строковых, вплоть до  вводимых  пользовате-

лем. Для обеспечения подобного обобщения используется  абстракция  че-

рез параметризацию, при которой типы данных являются параметрами.

 ┌──────────────────────────────────────────────────────────────────┐

 │ sort  = proc(a:array of int) returns (b:array of int)            │

 │      effects   - возвращает новый массив той же размерности,     │

 │                  что и a, содержащий элементы из массива a, упоря│

 │                  доченные по возрастанию                         │

 └──────────────────────────────────────────────────────────────────┘

 ┌──────────────────────────────────────────────────────────────────┐

 │ clear = proc(a:array of int)                                     │

 │      modifies  - a                                               │

 │      effects   - удаляет из массива a все повторяющиеся элементы │

 └──────────────────────────────────────────────────────────────────┘

 ┌──────────────────────────────────────────────────────────────────┐

 │ search= proc(a:array of int;x:int) returns (i:int)               │

 │      requires  - массив a упорядочен по возрастанию              │

 │      effects   - если элемент x принадлежит массиву a, то возвра-│

 │                  щается значение i, такое, что a[i]=x; в против- │

 │                  ном случае - значение i на единицу большее верх-│

 │                  ней границы массива a                           │

 └──────────────────────────────────────────────────────────────────┘

          Рис.1.6.Спецификации процедурных абстракций.

    При использовании типов в качестве параметров  некоторые  значения

параметров могут не иметь смысла. Например, массивы могут быть  отсор-

тированы только в том случае, когда элементы, принадлежащие типу, упо-

рядочены. Ограничения на параметры типа предполагают  набор  некоторых

заданных операций над ними. Спецификация абстракции  должна  содержать

эти ограничения в предложении requires.

    Некоторые спецификации для параметризованных процедур показаны  на

рис.1.7. Эти спецификации отличаются от спецификаций непараметризован-

 ┌──────────────────────────────────────────────────────────────────┐

 │ sort  = proc[t:type](a:array [t]) returns (array [t])            │

 │      requires  - t имеет операцию                                │

 │                    lt:proctype(t,t) returns(bool),               │

 │                  которая упорядочивает t                         │

 │      modifies  - a                                               │

 │      effects   - возвращает новый массив той же размерности,     │

 │                  что и a, содержащий элементы из массива a, упоря│

 │                  доченные по возрастанию                         │

 └──────────────────────────────────────────────────────────────────┘

 ┌──────────────────────────────────────────────────────────────────┐

 │ search= proc[t:type](a:array [t];x:t) returns (int)              │

 │      requires  - t имеет операции                                │

 │                    equal,lt:proctype(t,t) returns (bool),        │

 │                  такие, что t упорядочивается через equal, а     │

 │                  массив a упорядочен по возрастанию через lt     │

 │      effects   - если элемент x принадлежит массиву a, то возвра-│

 │                  щается значение i, такое, что a[i]=x; в против- │

 │                  ном случае - значение i на единицу большее верх-│

 │                  ней границы массива a                           │

 └──────────────────────────────────────────────────────────────────┘

          Рис.1.7.Спецификации параметризованных процедур.

ных процедур только заголовком, который содержит дополнительную часть,

содержащую параметры. Предложение requires помимо  прочих  ограничений

содержит ограничения, накладываемые на параметры. Если ограничения от-

сутствуют, то предложение requires может быть опущено.  Например,  аб-

стракция sort требует, чтобы параметр t имел операцию  lt,  упорядочи-

вающую t. Аналогично процедура search требует, чтобы ее параметр  под-

держивал как операцию lt, так и операцию equal. (lt - меньше, equal  -

равно).

    Параметризованная абстракция в действительности  представляет  со-

бой класс взаимосвязанных абстракций, определенных в одной  специфика-

ции. Спецификация процедуры естественным образом получается из  специ-

фикации класса путем замены имени параметра его значением и  удалением

из предложения requires ограничений на тип параметра(ов).

    При  создании  процедурных  абстракций  желательно  наличие  таких

свойств, как минимальность, простота и обобщенность.

                 1.3.Абстракция типа данных

    Процедуры дают возможность добавления в базовый язык новых  опера-

ций. Кроме операций, однако, базовый уровень  предусматривает  различ-

ные типы данных (целые, вещественные, логические, символьные, массивы,

записи и т.д.). Как указывалось выше, необходимо иметь возможность до-

бавлять в базовый уровень не только новые процедуры, но и  новые  типы

данных. Эта необходимость удовлетворяется абстракцией данных.

    Необходимые типы данных зависят от области применения  программно-

го обеспечения. В каждом конкретном случае абстракция  данных  состоит

из набора объектов и набора операций.

    Новые типы данных должны включать в себя абстракции как через  па-

раметризацию, так и через спецификацию. Абстракции через  параметриза-

цию могут быть осуществлены так же, как для процедур.  Абстракции  че-

рез спецификацию достигаются за счет представления операций как  части

типа. Если рассматривать тип данных просто как набор объектов, то все,

что необходимо сделать для реализации типа, - это выбрать  представле-

ние памяти для объектов. Тогда все программы могут быть реализованы  в

терминах этого представления. В случае изменения  представления  прог-

раммы, использующие этот тип, также должны быть изменены.

    При включении операций в тип данных единственным  требованием  бу-

дет следующее: пользователи  (программы)  употребляют  непосредственно

эти операции, не обращаясь к представлению. Операции типа должны  реа-

лизовываться в терминах выбранного представления. При изменении  пред-

ставления будут изменяться реализации операций типа, но программы, ис-

пользующие тип, переделывать не нужно. То есть, получается  абстракция

через спецификацию.

    Если обеспечено достаточное количество операций, отсутствие досту-

па к представлению не создаст  никаких  трудностей  для  пользователя.

Обычно должны быть операции по созданию и модификации объектов, а так-

же по получению информации об их значениях.

    Абстракции данных  -  наиболее важный метод в проектировании прог-

рамм. Выбор правильных структур данных играет решающую роль для созда-

ния эффективной программы. При отсутствии абстракций данных  структуры

данных должны быть определены до начала реализации  модулей.  Абстрак-

ции данных позволяют отложить окончательный выбор структур  данных  до

момента, когда эти структуры станут вполне ясны.

    Абстракции данных также полезны при  модификации  и  сопровождении

программного обеспечения.  Чаще  предпочтительнее  изменить  структуры

данных, чем улучшать производительность или приспосабливаться к  изме-

няющимся требованиям. Абстрации данных сводят все изменения к  измене-

ниям в реализации типа, тогда как модули программ изменять не нужно.

    Также как для процедур, значение типа не должно  задаваться  ника-

кой его реализацией. Вместо этого должна иметься определяющая его спе-

цификация. Так как объекты типа используются только вызовом  операций,

основная часть спецификации посвящена описанию того, что эти  операции

делают. Общий вид спецификации данных состоит из заголовка, определяю-

щего имя типа и имена его операций, и двух  главных  секций  -  секции

описания и секции операций.

      ┌─────────────────────────────────────────────────────────┐

      │    dname = data type is  список операций                │

      │    Описание                                             │

      │         Здесь приводится описание абстракции данных     │

      │    Операции                                             │

      │         Здесь задаются спецификации для всех операций   │

      │    end dname                                            │

      └─────────────────────────────────────────────────────────┘

              Рис.1.8.Общий вид спецификации абстракции данных.

    В секции описания тип описывается как целое. Иногда там дается мо-

дель для объектов, то  есть  объекты  описываются  в  терминах  других

объектов - таких, которые по предположению понятны тем, для  кого  эта

спецификация предназначена. Например, стеки могут быть описаны в  тер-

минах математических последовательностей.  В  секции  описания  должно

также говориться, изменяемый или неизменяемый это тип.

    В секции операций содержатся спецификации для всех операций.  Если

операция - процедура, то ее спецификация будет процедурной  специфика-

цией. В этих спецификациях могут использоваться концепции, введенные в

секции описания.

    Рассмотрим спецификацию абстракции данных intset. Наборы целых чи-

сел intset - это неограниченные множества  целых  чисел  с  операциями

создания нового, пустого набора, проверки данного целого числа на при-

надлежность данному набору intset и добавления или удаления элементов.

 ┌──────────────────────────────────────────────────────────────────┐

 │intset = data type is create, insert, delete, member, size, choose│

 │                                                                  │

 │Описание                                                          │

 │                                                                  │

 │ Наборы целых чисел intset - это неограниченные математические    │

 │ множества целых чисел. Наборы целых чисел изменяемые: операции   │

 │ insert и delete добавляют и удаляют целые числа из набора.       │

 │                                                                  │

 │Операции                                                          │

 │                                                                  │

 │ create = proc ()  returns (intset)                               │

 │        effects возвращает новый, пустой набор intset             │

 │                                                                  │

 │ insert = proc (s: intset, x:int)                                 │

 │        modifies s                                                │

 │        effects добавляет x к элементам s; после добавления -     │

 │                возврат                                           │

 │                                                                  │

 │ delete = proc (s: intset, x:int)                                 │

 │        modifies s                                                │

 │        effects удаляет x из s                                    │

 │                                                                  │

 │ member = proc (s:intset, x:int) returns (bool)                   │

 │        effects возвращает значение true, если x принадлежит s    │

 │                                                                  │

 │ size = proc (s: intset) returns (int)                            │

 │        effects возвращает число элементов в s                    │

 │                                                                  │

 │ choose = proc (s: intset) returns (int)                          │

 │        requires набор s не пуст                                  │

 │        effects возвращает произвольный элемент s                 │

 │                                                                  │

 │end intset                                                        │

 └──────────────────────────────────────────────────────────────────┘

             Рис.1.9.Спецификация типа данных intset.

    На рис.1.10 представлена спецификация типа данных  poly.  Полиномы

poly - это неизменяемые полиномы с целыми  коэффициентами.  Предостав-

ляются операции для создания одночленного полинома, для сложения,  вы-

читания и умножения полиномов, а также для проверки двух полиномов  на

равенство.

 ┌──────────────────────────────────────────────────────────────────┐

 │poly = data type is create,degree,coef,add,mul,sub,minus,equal    │

 │                                                                  │

 │Описание                                                          │

 │                                                                  │

 │ Полиномы poly - это неизменяемые полиномы с целыми коэффициентами│

 │                                                                  │

 │Операции                                                          │

 │                                                                  │

 │ create = proc (c,n:int)  returns (poly)                          │

 │        requires n>=0                n                            │

 │        effects возвращает полином cx. Например,                  │

 │                    poly.create(0,0) = 0                          │

 │                    poly.create(3,0) = 3 3                        │

 │                    poly.create(6,3) = 6x                         │

 │                                                                  │

 │ degree = proc (p: poly)  returns(int)                            │

 │        effects возвращает степень p, т.е. наибольшую степень при │

 │                ненулевом коэффициенте. Степень нулевого полинома │

 │                равна 0. Например,                    2           │

 │                    poly.degree(17) = 0  poly.degree(x +1) = 2    │

 │                                                                  │

 │ coef   = proc (p: poly, n:int) returns (int)                     │

 │        requires n>=0                                             │

 │        effects возвращает коэффициент члена p со степенью n. Воз-│

 │                вращает 0, если n больше степени p. Например,     │

 │                               3                                  │

 │                    poly.coef(x +2x+1,4) = 0                      │

 │                               3                                  │

 │                    poly.coef(x +2x+1,1) = 2                      │

 │                                                                  │

 │ add    = proc (p,q: poly) returns (poly)                         │

 │        effects возвращает полином, являющийся суммой полиномов p │

 │                и q                                               │

 │                                                                  │

 │ mul    = proc (p,q: poly) returns (poly)                         │

 │        effects возвращает полином, являющийся произведением поли-│

 │                номов p и q                                       │

 │                                                                  │

 │ sub    = proc (p,q: poly) returns (poly)                         │

 │        effects возвращает полином, являющийся разностью полиномов│

 │                p и q                                             │

 │                                                                  │

 │ minus  = proc (p: poly) returns (poly)                           │

 │        effects возвращает полином, являющийся разностью полиномов│

 │                z и p, где z - нулевой полином                    │

 │                                                                  │

 │ equal  = proc (p,q: poly) returns (bool)                         │

 │        effects возвращает значение true, если p и q имеют одинако│

 │                вые коэффициенты при соответствующих членах, и зна│

 │                чение false - в противном случае                  │

 │                                                                  │

 │end poly                                                          │

 └──────────────────────────────────────────────────────────────────┘

        Рис.1.10.Спецификация абстракции данных для полиномов.

    Типы  -  выгодные параметры для данных, как и для процедур. Напри-

мер, рассмотрим абстракцию общего набора set, в котором элементы набо-

ра могут быть произвольного типа. Конечно,  не  все  типы  могут  быть

имеющими смысл параметрами общего набора. Так как общие наборы set  не

хранят дублирующих друг друга элементов, должен быть некий способ  оп-

ределить, дублируют элементы друг друга или нет. Следовательно, специ-

фикация set, представленная на рис.1.11, требует, чтобы элементы  типа

имели операцию equal. Эти требования помещены сразу после заголовка.

 ┌──────────────────────────────────────────────────────────────────┐

 │ set = data type [t:type] is create, insert, delete, member, size,│

 │                             choose                               │

 │                                                                  │

 │Requires t имеет операцию                                         │

 │            equal:proctype(t,t) returns(bool),                    │

 │         то есть условие проверки равенства t                     │

 │                                                                  │

 │Описание                                                          │

 │                                                                  │

 │ Общие наборы set - это неограниченные математические наборы      │

 │ Эти наборы изменяемые: операции insert и delete добавляют и унич-│

 │ тожают элементы набора                                           │

 │                                                                  │

 │Операции                                                          │

 │                                                                  │

 │ create = proc ()  returns (set [t])                              │

 │        effects возвращает новый, пустой набор set                │

 │                                                                  │

 │ insert = proc (s: set[t], x:t)                                   │

 │        modifies s                                                │

 │        effects добавляет x к элементам s; после добавления -     │

 │                возврат                                           │

 │                                                                  │

 │ delete = proc (s: set[t], x:t)                                   │

 │        modifies s                                                │

 │        effects удаляет x из s                                    │

 │                                                                  │

 │ member = proc (s: set[t], x:t) returns (bool)                    │

 │        effects возвращает значение true, если x принадлежит s    │

 │                                                                  │

 │ size = proc (s: set[t]) returns (int)                            │

 │        effects возвращает число элементов в s                    │

 │                                                                  │

 │ choose = proc (s: set[t]) returns (t)                            │

 │        requires набор s не пуст                                  │

 │        effects возвращает произвольный элемент s                 │

 │                                                                  │

 │end set                                                           │

 └──────────────────────────────────────────────────────────────────┘

        Рис.1.11.Спецификация параметризованной абстракции данных.

    В качестве параметра для набора set  может  быть  использован  тип

poly. Например,

                pset = set[poly].

Poly является законным параметром для абстракции данных set,  так  как

имеет операцию equal.

    В следующем примере параметризованного  типа  данных,  описывающих

списки, требования налагаются на индивидуальные операции, а не на  тип

как целое. Неограниченные списки содержат элементы  некоторого  произ-

вольного типа. Для них имеются операции создания пустого списка,  фор-

мирования нового списка, состоящего из данного  элемента  и  элементов

уже существующего списка, и декомпозиции списка на  первый  элемент  и

остальные элементы.

 ┌──────────────────────────────────────────────────────────────────┐

 │list = data type [t:type] is create,cons,first,rest,empty,equal   │

 │                                                                  │

 │Описание                                                          │

 │                                                                  │

 │ Списки - это неизменяемые неограниченные последовательности      │

 │ элементов типа t                                                 │

 │                                                                  │

 │Операции                                                          │

 │                                                                  │

 │ create = proc ()  returns (list [t])                             │

 │        effects возвращает новый, пустой список                   │

 │                                                                  │

 │ cons   = proc (x: list[t], i:t) returns(list[t])                 │

 │        effects возвращает список, у которого первый элемент i, а │

 │                остальные элементы - элементы x                   │

 │                                                                  │

 │ first  = proc (x: list[t]) returns(t)                            │

 │        requires x - не пуст                                      │

 │        effects возвращает первый элемент x                       │

 │                                                                  │

 │ rest   = proc (x: list[t]) returns (list[t])                     │

 │        requires x - не пуст                                      │

 │        effects возвращает список, содержащий все элементы x, кро-│

 │                ме первого                                        │

 │                                                                  │

 │ empty  = proc (x: list[t]) returns (bool)                        │

 │        effects возвращает значение true, если x - пуст, и значе- │

 │                ние false - в противном случае                    │

 │                                                                  │

 │ equal  = proc (x,y: list[t]) returns (bool)                      │

 │        requires t имеет операцию                                 │

 │                     equl:proctype(t,t) returns(bool),            │

 │                 то есть условие равенства t                      │

 │        effects возвращает значение true, если x и y содержат оди-│

 │                наковые (в соответствии с t.equal) и одинаково рас│

 │                положенные элементы                               │

 │                                                                  │

 │end list                                                          │

 └──────────────────────────────────────────────────────────────────┘

    Рис.1.12.Спецификация параметризованной абстракции данных для

             списков.

    Следует заметить, что списки как целое не налагают никаких  требо-

ваний на тип параметра. Таким образом, list[intset]  -  законный  тип.

Однако операция equal должна проверять элементы на равенство,  поэтому

она в предложении requires налагает на  t  требования.  Следовательно,

list[intset] имеет все операции списков, кроме операции equal, так как

intset не имеет операции equal.

    В качестве последнего примера рассмотрим упорядоченные  списки,  в

которых элементы отсортированы по доступу. Упорядоченные списки -  из-

меняемы и параметризуемы по типу, который должен быть полностью упоря-

дочен его операциями lt и equal. То есть, упорядоченные списки не  со-

держат дублирующих друг друга элементов.

 ┌──────────────────────────────────────────────────────────────────┐

 │olist = data type [t:type] is create,addel,remel,is_in,empty,least│

 │                                                                  │

 │Requires  - t имеет операции                                      │

 │                    equal,lt:proctype(t,t) returns (bool),        │

 │            которые определяют упорядочение t                     │

 │                                                                  │

 │Описание                                                          │

 │                                                                  │

 │Упорядоченные списки olist - изменяемые списки элементов. Операции│

 │addel и remel модифицируют списки. Каждый элемент упорядоченного  │

 │списка отличается от остальных (как определяется t.equal). Опера- │

 │ция least возвращает наименьший элемент olist (как определяется   │

 │t.lt)                                                             │

 │                                                                  │

 │Операции                                                          │

 │                                                                  │

 │ create = proc ()  returns (olist [t])                            │

 │        effects возвращает новый, пустой список                   │

 │                                                                  │

 │ addel  = proc (s: olist[t], x:t)                                 │

 │        requires x не содержится в s; т.е. обращение к is_in(s,x) │

 │                 возвращает false                                 │

 │        modifies s                                                │

 │        effects вставляет x в s                                   │

 │                                                                  │

 │ remel  = proc (s: olist[t], x:t)                                 │

 │        requires x содержится в s; т.е. обращение к is_in(s,x)    │

 │                 возвращает true                                  │

 │        modifies s                                                │

 │        effects удаляет x из s                                    │

 │                                                                  │

 │ is_in  = proc (s: olist[t], x:t) returns (bool)                  │

 │        effects возвращает значение true, если s содержит элемент │

 │                равный x (используется t.equal), в противном слу- │

 │                чае возвращает значение false                     │

 │                                                                  │

 │ empty  = proc (s: olist[t]) returns (bool)                       │

 │        effects возвращает значение true, если s не содержит эле- │

 │                ментов, и значение false - в противном случае     │

 │                                                                  │

 │ least  = proc (s: olist[t]) returns(t)                           │

 │        requires список не пуст, то есть обращение к операции     │

 │                 empty(s) возвращает значение false               │

 │        effects возвращает элемент e из s, такой, что в s не суще-│

 │                ствует элемента, меньшего e(как определяется t.lt)│

 │                                                                  │

 │end olist                                                         │

 └──────────────────────────────────────────────────────────────────┘

    Рис.1.13.Спецификация параметризованной абстракции данных для

             упорядоченных списков.

    Абстракции данных либо изменяемы (с  объектами,  значения  которых

могут изменяться), либо неизменяемы. К определению этого аспекта  типа

следует относиться внимательно. В общем случае тип должен быть неизме-

няемым, если его объекты  естественным  образом  имеют  неизменяющиеся

значения (целые числа, полиномы, комплексные числа). Как правило,  тип

должен быть изменяемым, если моделируется что-то  из  реального  мира.

Неизменяемый тип более надежен, чем изменяемый, однако менее  эффекти-

вен в связи с необходимостью частой очистки памяти (сбор мусора).

    Операции абстракции данных распадаются на четыре класса.

    1)Примитивные конструкторы. Эти операции создают объекты  соответ-

ствующего им типа, не используя никаких объектов в  качестве  аргумен-

тов. (Операция create для наборов intset).

    2)Конструкторы. Эти  операции  используют  в  качестве  аргументов

объекты соответствующего им типа и создают другие  объекты  такого  же

типа. (Операции add и mul - конструкторы для полиномов, операции  cons

и rest - конструкторы для списков).

    3)Модификаторы.     Эти  операции  модифицируют  объекты  соответ-

ствующего им типа. (Операции insert и delete - модификаторы для  набо-

ров intset). Очевидно, что только изменяемые типы могут иметь  модифи-

каторы.

    4)Наблюдатели.  Эти  операции  используют  в  качестве  аргументов

объекты соответствующего им типа и возвращают результат другого  типа.

Они используются для получения информации об объектах. (Операции size,

member и choose для наборов intset, операции coef, degree и equal  для

полиномов).

    Обычно примитивные конструкторы создают не все, а  только  некото-

рые объекты. Например, операция poly.create создает  только  одночлен-

ные полиномы, а операция intset.create создает  только  пустой  набор.

Другие объекты создаются конструкторами или модификаторами.  Например,

операция poly.add может быть использована для получения  полиномов,  у

которых количество членов больше одного, а  операция  intset.insert  -

для получения наборов с многими элементами.

    Модификаторы играют ту же роль для изменяемых типов,  что  и  кон-

структоры для неизменяемых. Изменяемый тип может иметь как конструкто-

ры, так и модификаторы; например, наборы intset могут  иметь  операцию

copy, которая создает новый набор, содержащий те же элементы, что и ее

аргумент. Иногда наблюдатели комбинируются с конструкторами или  моди-

фикаторами; например, операция remel для упорядоченных списков olist с

помощью операций least и remel может модифицировать список  и  возвра-

тить удаленный элемент.

    Тип данных является полным, если он обеспечивает достаточно опера-

ций для того, чтобы все требующиеся пользователю  работы  с  объектами

могли быть проделаны с приемлемой эффективностью. Строгое  определение

полноты дать невозможно, хотя существуют  пределы  относительно  того,

насколько мало операций может иметь тип, оставаясь при  этом  приемле-

мым. Например, если для наборов intset будут существовать только  опе-

рации create, insert и delete, то программы не смогут  получить  ника-

кой информации относительно элементов набора (так как не имеется  наб-

людателей). Если к этим трем операциям добавить только одну - size, то

уже возможно получение информации об элементах набора (например,  мож-

но проверять на принадлежность, удаляя целые числа и анализируя, изме-

нился ли размер). Но тип в этом случае получится неэффективным и  неп-

риемлемым.

    В общем случае абстракция данных должна иметь операции по  крайней

мере трех из четырех рассмотренных классов. Она должна иметь примитив-

ные конструкторы, наблюдатели и либо конструкторы (если она неизменяе-

мая), либо модификаторы (если изменяемая).

    Полнота типа зависит от контекста использования, то есть тип  дол-

жен иметь достаточно богатый выбор операций  для  его  предполагаемого

использования. Если тип  предполагается  использовать  в  ограниченном

контексте, то должно быть обеспечено достаточно  операций  только  для

этого контекста. Если тип предназначен для общего использования, жела-

тельно иметь богатый набор операций. Введение дополнительных  операций

должно быть соотнесено с затратами на реализацию этих  операций.  Если

тип является полным, его набор операций может быть расширен процедура-

ми, функционирующими вне реализации типа.

    Корректность программы, использующей тип данных,  определяется  на

основе анализа свойств объектов типа. Этот  анализ  осуществляется  на

абстрактном уровне, то есть использованием спецификации типа.

    Например, иногда полезно установить свойство, являющееся общим для

всех объектов типа. Такое свойство называется инвариантом  абстракции.

Для доказательства используется метод индукции. Чтобы установить инва-

риант абстракции необходимо показать,  что  он  сохраняется  для  всех

объектов, произведенных типом. Как правило, используется следующий ме-

тод.

1)Показать, что свойство сохраняется для всех  объектов,  возвращаемых

примитивными конструкторами.

2)Показать, что свойство сохраняется для объектов,  возвращаемых  кон-

структорами, предполагая, что свойство сохраняется для объектов, пере-

даваемых конструкторам в качестве аргументов.

3)Показать, что при выходе из модификатора  свойство  сохраняется  для

модифицированных объектов, предполагая, свойство сохраняется при вызо-

ве модификатора.

    Например, упорядоченные списки (рис.1.13) не содержат  дублирующих

элементов. Этот инвариант полезен для определения корректности  реали-

зации наборов intset с использованием упорядоченных списков.  То,  что

это свойство является инвариантом, устанавливается следующим образом:

1)оно сохраняется для единственного примитивного конструктора  create,

так как операция create возвращает новый пустой список;

2)оно сохраняется для операции addel(s,x). При возврате из этой опера-

ции в s содержатся те же элементы, которые там были  до  вызова,  плюс

элемент x. По предположению, до вызова в s не  было  дублирующих  друг

друга элементов. Кроме того, операция  addel  требует  (в  предложении

requires), чтобы x не содержался в s. Следовательно, набор s с  добав-

ленным элементом x не содержит дублирующих друг друга элементов;

3)оно сохраняется для операции remel(s,x), так как оно сохраняется для

s (по предположению), а операция remel только удаляет элементы из s.

    Этот способ анализа называется  индукцией  типа  данных.  Индукция

осуществляется по количеству вызовов процедур, используемых для  полу-

чения текущего значения объекта. Первый шаг  индукции  -  установление

сохранения свойства для примитивного конструктора. Последующие  индук-

ционные шаги устанавливают сохранность свойства  для  конструкторов  и

модификаторов.

                 1.4.Исключительные ситуации

    Процедурная абстракция есть отображение аргументов в результаты  с

возможной модификацией некоторых аргументов. Аргументы принадлежат об-

ласти определения процедуры, а результаты - области изменения.

    Часто процедура имеет смысл только для  аргументов,  принадлежащих

подмножеству ее области определения. Например, операция choose для на-

боров целых чисел имеет смысл, только если ее аргумент - не пустой на-

бор. В приведенной выше спецификации типа данных intset (рис.1.9)  эта

ситуация учитывалась использованием процедуры choose, заданной на  не-

которой области определения.

      ┌─────────────────────────────────────────────────────┐

      │ choose = proc (s: intset) returns (int)             │

      │        requires набор s не пуст                     │

      │        effects Возвращает произвольный элемент s    │

      └─────────────────────────────────────────────────────┘

    Но в этом случае, реализуя операцию  choose,  игнорируется  случай

пустого множества. Такие процедуры приводят к неустойчивым программам.

Устойчивая программа - это такая программа, которая ведет себя коррек-

тно даже в случае ошибки. То есть, она должна вести себя определенным,

предсказуемым образом.

    Метод, который гарантирует устойчивость, заключается в использова-

нии процедур, заданных на всей  области  определения.  Если  процедура

неспособна осуществить свою функцию для некоторых аргументов, она дол-

жна оповестить обратившегося к ней о возникшем затруднении. Таким  об-

разом, разрешение ситуации передается обратившемуся к процедуре, кото-

рый может быть в состоянии что-то  предпринять  или  избежать  послед-

ствий ошибки.

    Проверка входных аргументов на принадлежность допустимому  подмно-

жеству области определения требует затрат времени и очень часто ее ис-

пользуют только при отладке ПО и  отключают  в  сдаваемом  программном

продукте. Однако это не самое  лучшее  решение.  Лучшим  является  ис-

пользование защитного программирования, когда программы сами  защищают

себя от ошибок. Защитное программирование облегчает отладку  программ.

При эксплуатации ПО оно еще более ценно,  так  как  исключает  возмож-

ность того, что незначительная ошибка приведет к  серьезной  проблеме.

Проверка на нелегальные аргументы может быть отключена только при  аб-

солютной уверенности в невозможности ошибки или если  проверка  приво-

дит к крайней неэффективности.

    Чтобы специфицировать процедуры, которые  вызывают  исключительные

ситуации, добавим в спецификацию предложение signals. Это предложение

- часть заголовка. Оно следует за предложением returns. Если  исключи-

тельных ситуаций не имеется, оно может быть опущено.

    Как и раньше, секция effects должна определять поведение  процеду-

ры для всех фактических аргументов, отвечающих  предложению  requires.

Так как это поведение включает в себя исключительные ситуации,  секция

effects должна определять,  что  приводит  к  вызову  каждой  исключи-

тельной ситуации и что делает процедура в каждом таком случае.  Завер-

шение процедуры оповещением об исключительной ситуации - это  один  из

нормальных режимов работы этой процедуры.

    С учетом всего вышесказанного, спецификация процедуры  choose  бу-

дет иметь вид:

 ┌──────────────────────────────────────────────────────────────────┐

 │ choose = proc (s: intset) returns (int) signals (empty)          │

 │        effects Если size(s)=0, то сигнализировать об исключитель-│

 │                ной ситуации empty, иначе возвратить произвольный │

 │                элемент s.                                        │

 └──────────────────────────────────────────────────────────────────┘

    При реализации процедуры с исключительными ситуациями работа прог-

раммиста заключается в том, чтобы обеспечить соответствующую  специфи-

кации работу процедуры. Если спецификация  включает  в  себя  исключи-

тельные ситуации, программа должна в нужное  время  сигнализировать  о

соответствующих исключительных ситуациях и передавать  определенные  в

спецификации значения. Для выполнения этой задачи, программа,  возмож-

но, должна будет обрабатывать исключительные ситуации,  возникающие  в

процедурах, к которым она обращается.

    Исключительные ситуации могут обрабатываться двумя различными спо-

собами. Иногда исключительная  ситуация  распространяется  до  другого

уровня, то есть вызывающая процедура также завершает работу сигнализа-

цией об исключительной ситуации с тем же самым или  другим  значением.

Перед распространением исключительной  ситуации  вызывающая  процедура

может осуществить некоторую локальную обработку. Такая обработка иног-

да необходима для достижения соответствия со спецификацией  вызывающей

процедуры. Например, операция типа данных  должна  гарантировать,  что

объекты перед ее завершением будут удовлетворять инварианту  представ-

ления.

    Другой способ заключается в том, что вызывающая  процедура  маски-

рует исключительную ситуацию, то есть обрабатывает ее сама.

    Рассмотрим в качестве примера спецификацию упорядоченных  списков,

в операциях которой удалены предложения requires и добавлены  исключи-

тельные ситуации в операциях addel, remel и least.  Полученная  в  ре-

зультате спецификация (рис.1.14) будет обладать большей  устойчивостью

по сравнению с исходной (рис.1.13).

 ┌──────────────────────────────────────────────────────────────────┐

 │olist = data type [t:type] is create,addel,remel,is_in,empty,least│

 │                                                                  │

 │Requires  - t имеет операции                                      │

 │                    equal,lt:proctype(t,t) returns (bool),        │

 │            которые определяют упорядочение t                     │

 │                                                                  │

 │Описание                                                          │

 │                                                                  │

 │Упорядоченные списки olist - изменяемые списки элементов. Операции│

 │addel и remel модифицируют списки. Каждый элемент упорядоченного  │

 │списка отличается от остальных (как определяется t.equal). Опера- │

 │ция least возвращает наименьший элемент olist (как определяется   │

 │t.lt)                                                             │

 │                                                                  │

 │Операции                                                          │

 │                                                                  │

 │ create = proc ()  returns (olist [t])                            │

 │        effects возвращает новый, пустой список                   │

 │                                                                  │

 │ addel  = proc (s: olist[t], x:t) signals(dupl)                   │

 │        modifies s                                                │

 │        effects  если x принадлежит s, сигнализирует об исключи-  │

 │                 тельной ситуации dupl, иначе вставляет x в s     │

 │                                                                  │

 │ remel  = proc (s: olist[t], x:t) signals(not_in)                 │

 │        modifies s                                                │

 │        effects  если x не принадлежит s, сигнализирует об исключи│

 │                 тельной ситуации not_in,иначе удаляет x из s     │

 │                                                                  │

 │ is_in  = proc (s: olist[t], x:t) returns (bool)                  │

 │        effects возвращает значение true, если s содержит элемент │

 │                равный x (используется t.equal), в противном слу- │

 │                чае возвращает значение false                     │

 │                                                                  │

 │ empty  = proc (s: olist[t]) returns (bool)                       │

 │        effects возвращает значение true, если s не содержит эле- │

 │                ментов, и значение false - в противном случае     │

 │                                                                  │

 │ least  = proc (s: olist[t]) returns(t) signals(empty)            │

 │        effects если s пуст, сигнализирует об исключительной ситуа│

 │                ции empty, иначе возвращает элемент e из s, такой,│

 │                что в s не существует элемента, меньшего e(как оп-│

 │                ределяется t.lt)                                  │

 │                                                                  │

 │end olist                                                         │

 └──────────────────────────────────────────────────────────────────┘

    Рис.1.14.Спецификация параметризованной абстракции данных для

             упорядоченных списков.

    Исключительные  ситуации  следует  использовать  для    устранения

большинства ограничений, перечисленных в  предложениях  requires.  Эти

предложения следует оставлять только из соображений эффективности  или

если контекст использования настолько ограничен, что можно  быть  уве-

ренным, что ограничения удовлетворяются.

    Cледует остановиться на взаимосвязи модификаций аргументов  с  за-

вершением работы процедуры выходом на исключительную ситуацию.  Секция

modifies спецификации указывает, что аргумент может  модифицироваться,

но не говорит о том,  когда  это  происходит.  Если  имеются  исключи-

тельные ситуации, то обычно  модификации  происходят  только  для  ка-

ких-нибудь из них. Точное описание происходящего должно быть  приведе-

но в секции effects. Модификации должны быть  описаны  явно  в  каждом

случае, в котором они совершаются; если не описано  никаких  модифика-

ций, это означает, что они не совершаются вообще.  Например,  рассмот-

рим процедуру

 ┌──────────────────────────────────────────────────────────────────┐

 │                                                                  │

 │ addel  = proc (s: olist[t], x:t) signals(dupl)                   │

 │        modifies s                                                │

 │        effects  если x принадлежит s, сигнализирует об исключи-  │

 │                 тельной ситуации dupl, иначе вставляет x в s     │

 │                                                                  │

 └──────────────────────────────────────────────────────────────────┘

    Так как для случая, когда процедура addel сигнализирует об  исклю-

чительной ситуации dupl, не описано никаких модификаций,  s  модифици-

руется только при обычном возврате из процедуры addel.

    Исключительная ситуация failure  является  неявной  исключительной

ситуацией каждой процедуры, однако она не упоминается ни в каких  спе-

цификациях. Спецификация описывает поведение процедуры при ее работе и

для случая, когда аргументы удовлетворяют предложению requires. Исклю-

чительная ситуация failure возникает тогда, когда в  работе  процедуры

происходит сбой и она больше не отвечает своей спецификации или  когда

заданы неверные аргументы.

    Обычно исключительная ситуация failure не  может  быть  обработана

программой. Эта ситуация означает либо ошибку в математическом обеспе-

чении, либо сбой в аппаратной части.

                    1.5.Абстракции итерации

    Для работы с набором данных требуется некоторый общий метод итера-

ции, который удобен и эффективен и который сохраняет абстракцию  через

спецификацию. Итератор обеспечивает эти требования. Он вызывается  как

процедура, но вместо окончания с выдачей всех результатов имеет  много

результатов, которые каждый раз выдает по одному. Полученные  элементы

могут использоваться в других модулях, которые задают действия, выпол-

няемые для каждого такого элемента. Использующий итератор  модуль  бу-

дет содержать некоторую структуру организации цикла. Каждый раз,  ког-

да итератор выдает некоторый элемент, над этим  элементом  выполняется

тело цикла. Затем управление возвращается в итератор, так что  он  мо-

жет выдавать следующий элемент. Следует отметить разделение обязаннос-

тей в такой форме взаимодействия. Итератор ответственен  за  получение

элемента, а модуль, содержащий цикл, определяет то  действие,  которое

будет над ним выполняться.  Итераторы  являются  некоторой  обобщенной

формой методов итерации, имеющихся в большинстве языков программирова-

ния.

    Как и другие абстракции, итераторы должны  быть  определены  через

спецификации. Форма спецификации итерации аналогична форме для  проце-

дуры. Заголовок имеет вид:

  iname = iter(список входных данных)   yields(список выходных данных)

          signals (сообщение об исключительной ситуации)

    Ключевое слово iter используется для обозначения абстракции итера-

тора. Итератор может совсем не выдавать объектов  на  каждой  итерации

или выдать несколько объектов. Число и тип этих объектов описываются в

предложении yields. Итератор может не  выдавать  никаких  результатов,

когда он заканчивается нормально, но он может заканчиваться по  исклю-

чительной ситуации с именем и результатами, указанными  в  предложении

signals. Например,

 ┌──────────────────────────────────────────────────────────────────┐

 │ elements = iter (s: intset) yields (int)                         │

 │          requires s не модифицируется в теле цикла               │

 │          effects Выдает элементы s в некотором произвольном по-  │

 │                  рядке, причем каждый элемент только один раз.   │

 └──────────────────────────────────────────────────────────────────┘

    Эта операция вполне  правдоподобна  для  набора  intset.  Операция

elements не имеет исключительных ситуаций. Если ей будет задан  в  ка-

честве аргумента пустой набор intset, она просто заканчивается, не вы-

давая ни одного элемента. Характерно, что использование итераторов ис-

ключает проблемы, связанные с заданием  некоторых  аргументов  (таких,

как пустой набор intset) для соответствующих процедур (таких, как про-

цедура choose).

    Требование о том, чтобы набор s не модифицировался при использова-

нии цикла, является ограничением, типичным для итераторов.

    Таким образом, рассмотрена проблема полноты типов данных,  которые

являются совокупностью объектов. Поскольку  совокупность  используется

для выполнения некоторого действия над ее элементами, необходим  неко-

торый способ доступа ко всем элементам. Этот способ должен быть  эфек-

тивным в смысле времени и пространства, удобным для использования и не

должен разрушать данную совокупность. Кроме того, он должен  обеспечи-

вать абстракцию через спецификацию.

    Итераторы являются механизмом, решающим эту задачу. Поскольку  они

выдают объекты по одному, не  требуется  дополнительного  пространства

для хранения объектов, и процедура может быть остановлена, когда  нуж-

ный объект будет найден. Метод выдачи объектов зависит от знания пред-

ставления этих объектов, но использующие  его  программы  защищены  от

этого знания.

    Итераторы полезны сами по себе, однако их основным применением яв-

ляются операции над типами данных.

            1.6.Использование абстракций в языке Паскаль

    В языке Паскаль непосредственно не  обеспечиваются  ни  абстракции

данных или итераций, ни абстракция через параметризацию. Тем не  менее

при проектировании программ, которые будут  реализовываться  на  языке

Паскаль, все же можно с успехом применять эти  абстракции.  Для  этого

при проектировании надо использовать приемущества тех методов построе-

ния программ, которые хорошо обеспечивает язык Паскаль, и избежать та-

ких методов, которые черезмерно трудно реализовывать.

    Рассмотрим по очереди абстракции процедур, данных  и  итераций,  а

затем приведем пример их использования.

               1.6.1.Абстракции процедур и функций

    1.  В общем случае нецелесообразно проектировать абстракции, кото-

рые зависят от глобальных переменных, поскольку тогда знание такой аб-

стракции бкдет зависеть от того контекста, в котором она находится.

    2. Для обработки исключительных ситуаций  в  программах  на  языке

Паскаль зададим некоторую процедуру failure. Эта процедура  помещается

в начало программы, и к ней может обращаться  любая  операция  в  этой

программе.

 ┌───────────────────────────────────────────────────────────────────┐

 │  procedure failure (s:error_msg)                                  │

 │        modifies  выходной поток на основном устройстве вывода     │

 │        effects   печатает следующую строку на основном устройстве │

 │                  вывода: "Сбой. Программа окончилась из-за: +S",  │

 │                  а затем выполнение программы останавливается     │

 └───────────────────────────────────────────────────────────────────┘

                     1.6.2.Абстракции данных

    В общем случае эти абстракции могут быть основаны на объектах, за-

поминаемых в стеке, и на объектах, хранящихся в неупорядоченном масси-

ве. Рассмотрим второй случай, который дает большую  гибкость  за  счет

некоторой неэффективности.

    Зададим спецификацию абстракции данных для очереди целых чисел.

 ┌───────────────────────────────────────────────────────────────────┐

 │ intqueue = data type is q_new, q_isempty, q_append, q_remfirst    │

 │                                                                   │

 │ Описание                                                          │

 │     Типы данных intqueue используются для хранения значений типа  │

 │ целого числа. Элементы могут извлекаться из очереди или удалять-  │

 │ ся из нее только по методу FIFO (First Input-First Output)        │

 │ Операции                                                          │

 │ function q_new:intqueue                                           │

 │        effects  Возвращает новую очередь без элементов в ней      │

 │ function q_isempty (q:intqueue): boolean                          │

 │        effects  Возвращает значение true, если в очереди q нет    │

 │                 элементов, в противном случае возвращает значе-   │

 │                 ние false                                         │

 │ procedure q_append (q:intqueue; e:integer)                        │

 │        modifies  q                                                │

 │        effects  Добавляет элемент  e  в конец очереди  q          │

 │ function q_remfirst (q:intqueue): integer                         │

 │        requires  чтобы очередь  q  не была пустой                 │

 │        modifies  q                                                │

 │        effects  Возвращает элемент из начала очереди  q  и        │

 │                 удаляет этот элемент из очереди  q                │

 │ end intqueue                                                      │

 └───────────────────────────────────────────────────────────────────┘

    Рис.1.15.Спецификация абстракции данных для очереди целых чисел.

    Решение хранить абстрактные объекты в неупорядоченном массиве про-

диктовано тем, что надо реализовать типы,  чьи  объеты  изменяют  свой

размер по мере работы программы. Реализация такого  абстрактного  типа

данных использует указатель на неупорядоченный массив. То есть при пе-

редаче в процедуру некоторого абстрактного объекта  всегда  передается

только ссылка. При модификации  абстрактного  объекта,  модифицируется

тот объект, на который указывает ссылка, а не сама ссылка. Таким обра-

зом, абстрактные объекты введенного типа никогда  не  передаются,  как

параметры типа var. Кроме того, представление объекта некоторой  ссыл-

кой гарантирует то, что абстрактные объекты могут быть возвращены  при

помощи функций.

    В результате тип intqueue будет иметь следующее представление

type

    intqueue = ^intqueue_rep;

    intqueue_rep = ^intqueue_elem;

    intqueue_elem = record

             var  : integer;

             next : intqueue_rep;

             end;

    Теперь для объявления переменных некоторого абстрактного типа дос-

таточно указать

    var q:intqueue;

    Смысл этого объявления  состоит  в  том,  что  в  стеке  отводится

пространство для некоторой  неинициализированной  переменной q.  Когда

очередь q объявлена, выделяется только указатель, а при выходе из про-

цедуры, освобождается только этот указатель.

    Чтобы гарантировать правильное освобождение пространства, для каж-

дого типа должна существовать некоторая дополнительная операция, назы-

ваемая destroy.

 ┌───────────────────────────────────────────────────────────────────┐

 │ procedure q_desstroy (q:intqueue)                                 │

 │       modifies  q                                                 │

 │       effects  В неупорядоченном массиве освобождается вся        │

 │                память, занимаемая очередью  q                     │

 └───────────────────────────────────────────────────────────────────┘

    По соглашению нельзя  освобождать  абстрактные  объекты  непосред-

ственно. Вместо этого необходимо обращение к операции destroy для  ти-

па данного объекта.  На  рис.1.16  приведена  реализация  типа  данных

intqueue, включая и операцию destroy.

 ┌───────────────────────────────────────────────────────────────────┐

 │ Type  IntQueue = ^IntQueue_Rep;                                   │

 │       IntQueue_Rep = ^IntQueue_Elem;                              │

 │       IntQueue_Elem = Record                                      │

 │           i : Word;                                               │

 │           Next : IntQueue_Rep;                                    │

 │           End;                                                    │

 │                                                                   │

 │ Function q_new:IntQueue;                                          │

 │ Function q_isempty(q:IntQueue):Bollean;                           │

 │ Procedure q_append(q:IntQueue; e:Word);                           │

 │ Function q_remfirst(q:Intqueue):Word;                             │

 │ Procedure failure(s:String);                                      │

 │                                                                   │

 │ Function q_new:IntQueue;                                          │

 │ Var q:IntQueue;                                                   │

 │   Begin                                                           │

 │     new(q);                                                       │

 │     q^:=nil;                                                      │

 │     q_new:=q;                                                     │

 │   End;                                                            │

 │                                                                   │

 │ Function q_isempty(q:IntQueue):Bollean;                           │

 │ Var buf:bollean;                                                  │

 │   Begin                                                           │

 │     buf:=(q^=nil);                                                │

 │     q_isempty:=buf;                                               │

 │   End;                                                            │

 │                                                                   │

 │ Procedure q_append(q:IntQueue; e:Word);                           │

 │ Var last,elem:IntQueue_Rep;                                       │

 │   Begin                                                           │

 │     new(elem);                                                    │

 │     elem^.i:=e;                                                   │

 │     elem^.next:=nil;                                              │

 │     if q_isempty(q) then q^:=elem                                 │

 │     else begin                                                    │

 │            last:=q^;                                              │

 │            while  last^.next <> nil  do                           │

 │              last:=last^.next;                                    │

 │            last^.next:=elem;                                      │

 │          end;                                                     │

 │   End;                                                            │

 │                                                                   │

 │ Function q_remfirst(q:IntQueue):Word;                             │

 │ Var oldq:IntQueue_Rep;                                            │

 │   Begin                                                           │

 │     if q_isempty(q) then failure ('К функции q_remfirst           │

 │                          обратились с пустой очередью')           │

 │     else begin                                                    │

 │            q_remfirst:=q^^.i;                                     │

 │            oldq:=q^;                                              │

 │            q^:=q^^.next;                                          │

 │            dispose(oldq);                                         │

 │     end;                                                          │

 │   End;                                                            │

 │                                                                   │

 │ Procedure failure(s:String);                                      │

 │   Begin                                                           │

 │     OutTextXT(320,200,s);                                         │

 │     Readln;                                                       │

 │     Halt(0);                                                      │

 │   End;                                                            │

 └───────────────────────────────────────────────────────────────────┘

        Рис.1.16.Реализация операций типа данных intquaeue.

                     1.6.3.Абстракция итерации

    Для реализации итератора создадим тип некоторого специального  ви-

да, называемый генератором. Генераторы имитируют работу итераторов.  У

каждого генератора есть три функции и одна процедура. Эти три  функции

создают объект генератора, получают следующий элемент и проверяют, все

ли элементы были выданы. Процедура уничтожает объект генератора.

    Например,  для  очереди  целых  чисел  создадим  генератор  qelems

(рис.1.17). Функция qelems_create выполняет некоторую работу  по  ини-

циализации, то есть возвращает некоторый объект с типом  qelems.  Вто-

рая функция qelems_next выдает каждый раз один элемент при обращении к

ней и модифицирует объект генератора qelems, чтобы указать,  что  этот

элемент уже был выдан. Последняя функция qelems_done используется  для

определения  того,  были  ли   выданы    все    элементы.    Процедура

qelems_destroy освобождает пространство, которое было выделено при ра-

боте функцией qelems_create и qelems_next.

 ┌───────────────────────────────────────────────────────────────────┐

 │ qelems = generator type is qelems_create, qelems_done,            │

 │                            qelems_next, qelems_destroy            │

 │ Описание                                                          │

 │     Генераторы qelems используются для выполнения итераций по     │

 │ элементам очередей целых чисел IntQueue.                          │

 │ Операции                                                          │

 │ function qelems_create (q:IntQueue): qelems                       │

 │       effects  Возвращается некоторый объект qelems, который      │

 │                может быть использован для выдачи всех элементов   │

 │                в очереди q                                        │

 │ function qelems_done (qi:qelems): boolean                         │

 │       requires  Чтобы очередь целых чисел intqueue, используемуя  │

 │                 для создания элементов qi, не модифицировалась    │

 │                 после того, как создан элемент qi                 │

 │       effects  Возвращается значение true, если все элементы в    │

 │                очереди целых чисел intqueue, используемой для     │

 │                создания элементов qi, были "выданы" после того,   │

 │                как был создан элемент qi. В противном случае      │

 │                возвращается значение false                        │

 │ function qelems_next (qi:qelems): word                            │

 │       requires  Чтобы очередь целых чисел intqueue, используемуя  │

 │                 для создания элементов qi, не модифицировалась    │

 │                 после того, как создан элемент qi, и чтобы сущест-│

 │                 вовал некоторый элемент в очереди целых чисел     │

 │                 intqueue, который еще не был выдан                │

 │       modifies  qi                                                │

 │       effects  Возвращается некоторый элемент в очереди чисел     │

 │                intqueue, используемой для создания элемента qi.   │

 │                Этот элемент очереди не был выдан после того, как  │

 │                был создан элемент qi. Элемент qi модифицируется   │

 │                для того, чтобы отметить тот факт, что данный      │

 │                элемент был "выдан"                                │

 │ procedure qelems_destroy (qi:qelems)                              │

 │       modifies  qi                                                │

 │       effects  Освобождается вся память из неупорядоченного       │

 │                массива, занимаемая элементом qi                   │

 │ end qelems                                                        │

 └───────────────────────────────────────────────────────────────────┘

      Рис.1.17.Спецификация типа данных генератор для очередей.

    Реализация операций над типом данных qelems, совместная с реализа-

цией очереди целых чисел intqueue, имеет вид:

 ┌───────────────────────────────────────────────────────────────────┐

 │ type                                                              │

 │     qelems = ^qelems_rep;                                         │

 │     qelems_rep = ^intqueue_elem;                                  │

 │ function qelems_create (q:intqueue): qelems;                      │

 │     var qi:qelems;                                                │

 │     begin                                                         │

 │          new(qi);                                                 │

 │          qi^:=q^;                                                 │

 │          qelems_create:=qi;                                       │

 │     end;                                                          │

 │ function qelems_done (qi:qelems): bollean;                        │

 │     begin                                                         │

 │          qelems_done:=(qi^=nil);                                  │

 │     end;                                                          │

 │ function qelems_next (qi:qelems): word;                           │

 │     begin                                                         │

 │          if qi^=nil                                               │

 │             then failure('К функции qelems_next обратились        │

 │                           с пустой очередью генератора')          │

 │          else begin                                               │

 │                    qelems_next:=qi^^.i;                           │

 │                    qi^:=qi^^.next;                                │

 │               end;                                                │

 │     end;                                                          │

 │ procedure qelems_destroy (qi:qelems);                             │

 │     begin                                                         │

 │          dispose(qi);                                             │

 │     end;                                                          │

 └───────────────────────────────────────────────────────────────────┘

     Рис.1.18.Реализация генератора для типа данных очередь целых

              чисел intqueue.

    В результате этой реализации осуществляется доступ  к  представле-

нию очереди целых чисел intqueue. Следует отметить, что  представление

имеет дополнительный уровень косвенности для  того,  чтобы  гарантиро-

вать правильность совместимого использования.

    Пример суммирования всех членов очереди примет вид:

    sum:=0;

    qi:=qelems_create(q);

    while  not (qelems_done(qi))  do

        sum:=sum+qelems_next(qi);

    qelems_destroy(qi);

                2.ВВЕДЕНИЕ В ИНЖЕНЕРНОЕ ПРОГРАММИРОВАНИЕ

            2.1.Цели и задачи инженерного программирования

    П р о г р а м м н о е   о б е с п е ч е н и е - это совокупность

программ, процедур работы и соответствующей документации для  вычисли-

тельной системы(ВС).

    И н ж е н е р н о е   п р о г р а м м и р о в а н и е - это такое

применение естественных и математических наук, в  результате  которого

потенциальные возможности ЭВМ реализуются на  пользу  человеку  с  по-

мощью машинных программ, организационных  процедур  и  соответствующей

документации.

    Стоимость и качество производимого ПО определяются уровнем  разви-

тия инженерного программирования. Важность инженерного  программирова-

ния обуславливается следующими двумя тенденциями:

- ПО является сложным изделием и стоимость его все более возрастает;

- ПО оказывает значительное и все возрастающее воздействие  на  общес-

твенное благосостояние.

    Стоимость ПО, разработанного в  США,  характеризуется  следующими

данными.

                Табл.2.1.Стоимость ПО в США

┌──────────────────┬─────────────────────────────────────────────────┐

│                  │        Стоимость ПО                             │

│   Годы           ├──────────────────────┬──────────────────────────┤

│                  │        млрд $        │        %% ВНП            │

├──────────────────┼──────────────────────┼──────────────────────────┤

│                  │                      │                          │

│    1980          │         40           │        2,0               │

│                  │                      │                          │

│    1985          │        190           │        8,5               │

│                  │                      │                          │

│    1990          │        297           │       13,0               │

└──────────────────┴──────────────────────┴──────────────────────────┘

    Общемировые тенденции роста стоимости ПО  можно  проиллюстрировать

тем, что стоимость ПО по сравнению со стоимостью  технических  средств

вычислительной техники имеет более высокий темп роста (рис.2.1)

                                             Западноевропейская оценка

 Доля пол-  100 ---------------------------        .................

 ной стои-      |            |     .......|........       ..  ..

 мости, %%      |    ТС      | ....       |   ..        ..      ..

                |          ..|.           |      ..   ..          ..  ..

                |        ..  |            |         ..              ..

             50 |------------|------------|        Японская оценка

                |       .    |            |

                |      .     |            |

                |   ...      |     ПО     |

                |..          |            |

              0 ---------------------------

              1955          1970        1985

         Рис.2.1.Тенденции изменения стоимости ТС и ПО

    Подобный рост спроса на ПО предъявляет существенные  требования  к

инженерному программированию:

- существенно повысить производительность труда при разработке ПО;

- повысить эффективность сопровождения ПО, так как оно составляет око-

ло половины стоимости ПО (рис.2.1).

    Рост спроса на ПО является следствием того, что автоматизация тру-

да человека с помощью ЭВМ становится все более и более  выгодной.  Эта

тенденция может быть подтверждена следующими данными. В настоящее вре-

мя в США более половины работающих используют ЭВМ в  своей  профессио-

нальной деятельности, не обязательно зная как функционируют ТС  и  ПО.

То есть, они неявно полагались на правильность результатов  применения

ПО. Еще более глубокое воздействие ЭВМ и ПО оказывают на частную жизнь.

    Исходя из этого возникает еще ряд требований к  инженерному  прог-

раммированию. Они состоят в необходимости разработки  и  сопровождения

ПО, которое гарантирует, что ВС являются:

- исключительно надежными

- удобными в использовании

- естественными

- проверяемыми

- труднодоступными для злоупотреблений

- оставляющими главную роль за человеком, а не за машиной.

    Попытка сформулировать общую  цель  инженерного  программирования,

достижение которой привело бы к удовлетворению всех указанных требова-

ний, обречена на неудачу, так как  некоторые  требования  противоречат

друг другу.

    Пример противоречий: пяти бригадам программистов дано  одно  и  то

                         же задание по программированию. Однако  перед

                         разными бригадами были поставлены разные цели.

               Табл.2.2.Оценки результатов работы бригад

┌─────────────────────┬──────────────────────────────────────────────┐

│Цель бригады -       │ Оценки (1-наилучшая, 5-наихудшая)            │

│                     ├────────┬───────────┬───────┬────────┬────────┤

│оптимизировать       │затраты │число опе- │объем  │ясность │четкость│

│                     │труда   │операторов │памяти │програм.│данных  │

├─────────────────────┼────────┼───────────┼───────┼────────┼────────┤

│Затраты труда        │   1    │     4     │  4    │   5    │   3    │

│                     │        │           │       │        │        │

├─────────────────────┼────────┼───────────┼───────┼────────┼────────┤

│Число операторов     │   2    │     1     │  2    │   3    │   5    │

│программы            │        │           │       │        │        │

├─────────────────────┼────────┼───────────┼───────┼────────┼────────┤

│Объем требуемой      │   5    │     2     │  1    │   4    │   4    │

│памяти               │        │           │       │        │        │

├─────────────────────┼────────┼───────────┼───────┼────────┼────────┤

│Ясность программы    │   4    │     3     │  3    │   2    │   2    │

│                     │        │           │       │        │        │

├─────────────────────┼────────┼───────────┼───────┼────────┼────────┤

│Четкость выходных    │   3    │     5     │  5    │   1    │   1    │

│данных               │        │           │       │        │        │

└─────────────────────┴────────┴───────────┴───────┴────────┴────────┘

    Как видно, область инженерного программирования к счастью  (или  к

несчастью) не столь проста.

    Существует большое количество предлагаемых в  качестве  рекоменда-

ций "стандартов" программирования: "разрабатывайте сверху-вниз",  "до-

казывайте правильность программ", "разрабатывайте дважды", "используй-

те метод главного программиста", "программируйте  структурно",  "четко

определяйте этапы", "привлекайте к работе пользователя" и т.д.  Каждый

из этих советов способствует выполнению  определенных  требований,  но

никак не учитывает другие и фактически препятствует их удовлетворению.

    Наиболее важным в инженерном программировании является знание  ме-

тодов достижения разнообразных, возможно,  противоречащих  друг  другу

целей и согласования разнообразных применяемых средств, каждое из  ко-

торых в зависимости от ситуации в различной степени помогает  или  ме-

шает достижению конкретной цели.

    Эффективность инженерного программирования основывается на осущес-

твлении двух основных подцелей:

- получение качественного программного изделия

- реализация эффективного процесса разработки и сопровождения ПО.

    Каждая из этих подцелей состоит из следующих трех компонентов:

- учет человеческих факторов

- управление ресурсами

- программотехника (технология программирования).

    В общем случае цели инженерного  программирования  можно  предста-

вить следующей иерархической структурой (рис.2.2).

            ┌─────────────────────────────────────────────┐

            │  Эффективность инженерного программирования │

            └───────┬───────────────────────────────┬─────┘

                    │                               │

┌───────────────────┴────────┐          ┌───────────┴────────────────┐

│   Качество программного    │          │   Эффективность процесса   │

│        изделия             │          │       разработки ПО        │

└───┬───────────┬───────────┬┘          └┬───────────┬──────────┬────┘

    │           │           │            │           │          │

┌───┴────┐  ┌───┴────┐  ┌───┴────┐  ┌────┴───┐  ┌────┴───┐  ┌───┴────┐

│Человеч.│  │Управлен│  │Програм-│  │Человеч.│  │Управлен│  │Програм-│

│факторы │  │ресурсам│  │мотехник│  │факторы │  │ресурсам│  │мотехник│

└────────┘  └────────┘  └────────┘  └────────┘  └────────┘  └────────┘

Легкость    Эффектив-   Специфици-  Планируе-   Анализиру-  Осуществи-

использова  ность       рованность: мость       емость эф-  мость

ния         Сбаланси-   полнота     Организу-   фективности Подтверж-

Удовлетво-  рованность  непротиво-  емость      затрат      даемость

рение пот-  Измеряе-    речивость   Укомплек-   Планируе-   Полнота и

ребностей   мость       безопас-    тованность  мость       непротиво-

пользовате-             ность       штатов      Оценивае-   речивость

ля                      осуществи-  Руководи-   мость       требований

Реализация              мость       мость       Контроли-   Подтвержда-

потенц.спо-             проверяе-   Контроли-   руемость    емость

собностей               мость       руемость    Выполняе-   Проектируе-

пользовате-             Правиль-    Автомати-   мость       мость изде-

ля                      ность       зируемость  сроков и    лия

Следование              Адаптиру-   Следование  бюджета     Программи-

модифицир.              емость:     модифицир.              руемость

"золотому"              структури-  "золотому"              Комплекси-

правилу                 рованность  правилу                 руемость

                        независи-                           Внедряе-

                        мость                               мость

                        понятность                          Сопровож-

                                                            даемость

                                                            Снимаемость

                                                            Управляе-

                                                            мость кон-

                                                            фигурацией

        Рис.2.2.Структура целей инженерного программирования.

                         2.2.Типы пользователей

                      2.2.1.Уровни пользователей ПО

    Можно выделить три квалификационные категории пользователей, кото-

рые занимаются разработкой и использованием программного обеспечения.

    К первому уровню относятся разработчики ПО - специалисты в  облас-

ти применения ЭВМ, способные разрабатывать базовые методы, средства  и

оснащение ПО, общесистемное  ПО,  инструментальные  и  технологические

средства, осуществлять генерацию и настройку ПО на условия конкретного

применения.

    Ко второму - те, кто хорошо знает тонкости  построения  системы  и

может ее модифицировать,  то  есть  прикладные  программисты,  которые

знают методологию проектирования, алгоритмы прикладной области  и  мо-

гут разрабатывать специализированное ПО, используя общесистемное ПО.

    К третьему относятся пользователи, работающие в системе с  помощью

ориентированного на них языка взаимодействия. Процесс  работы  в  этом

случае сводится к заданию исходных данных, постановке задачи, проведе-

нию расчетов, анализу результатов и принятию решений.

          2.2.2.Психофизиологические особенности взаимодействия

                человека и ЭВМ

    ЭВМ дополняет человека, но не заменяет его,  поэтому  рассмотрение

основных особенностей их сотрудничества является необходимым.

    Л о г и ч е с к и й   м е т о д   р а с с у ж д е н и я. У челове-

ка он основан на интуиции, на использовании накопленного опыта и вооб-

ражения. Метод ЭВМ строгий и систематический. Наиболее удачным являет-

ся сочетание когда ЭВМ реализует отдельные расчетные процедуры,  а  их

логическая  последовательность  определяется  человеком  -  создателем

проектируемого объекта.

    С п о с о б н о с т ь   к   о б  у  ч  е  н  и  ю. Человек  обуча-

ется постепенно, степень "образованности" ЭВМ определяется ее програм-

мным обеспечением. Желательно, чтобы количество  информации,  получае-

мой на запрос пользователя, было переменным и могло изменяться по тре-

бованию пользователя.

    О б р а щ е н и е   с   и н ф о р м а ц и е й.  Емкость мозга  че-

ловека для сохранения детализированной информации невелика,  но  обла-

дает интуитивной, неформальной возможностью ее организации.  Эффектив-

ность вторичного обращения к памяти зависит от времени. В ЭВМ  емкость

памяти большая, организация формальная и  детализированная,  вторичное

обращение не зависит от времени. Поэтому целесообразно  накапливать  и

организовывать информацию автоматическим путем и осуществлять ее  быс-

трый вызов по удобным для человека признакам.

    О ц е н к а   и н ф о р м а ц и и.  Человек умеет хорошо разделять

значимую и несущественную информацию. ЭВМ таким свойством не обладает.

Поэтому  должна  существовать  возможность  макропросмотра  информации

большого объема,  что  позволяет  человеку  выбрать  интересующую  его

часть, не изучая всю накопленную информацию.

    О т н о ш е н и е   к   о ш и б к а м.  Человек  часто  допускает

существенные ошибки, исправляя их интуитивно, при этом метод обнаруже-

ния ошибок чаще всего также интуитивный. ЭВМ, наоборот,  не  проявляет

никакой терпимости к ошибкам и метод обнаружения ошибок строго  систе-

матичен. Однако в области формальных  ошибок  возможности  ЭВМ  значи-

тельно больше, чем при обнаружении неформальных. Поэтому нужно обеспе-

чить возможность пользователю вводить в ЭВМ исходную информацию в сво-

бодной форме, написанную по правилам, близким к  обычным  математичес-

ким выражениям и к разговорной речи. ЭВМ выполняет контроль и преобра-

зование информации к стандартному виду, удобному в процедурах обработ-

ки и формального устранения ошибок. Затем желательно обратное преобра-

зование этой информации для показа пользователю в наглядной, например,

графической форме, для обнаружения смысловых ошибок.

    О б р а щ е н и е   с о   с л о ж н ы м и   о п и с а н и я м и.

Человеку трудно воспринять большое количество информации. Поэтому сле-

дует поручать ЭВМ автоматическое разбиение сложных конфигураций на от-

носительно независимые части, охватываемые одним взглядом.  Естествен-

но, что изменения, сделанные в одной из этих частей, должны  автомати-

чески производиться во всех остальных.

     Р а с п р е д е л е н е   в н и м а н и я   н а   н е с к о л ь -

к о   з а д а ч.  Выполнить это условие человеку, в основном, не  уда-

ется.  При решении подзадачи приходится отвлекаться от основной  зада-

чи. Поэтому в ЭВМ организована система  прерываний,  восстанавливающая

состояние основной задачи к моменту, нужному для пользователя.  Анало-

гичным образом ЭВМ обслуживает процедуру анализа нескольких  вариантов

решения.

    П а м я т ь   п о   о т н о ш е н и ю   к   п р о в е д е н н о й

р а б о т е.  Человек может забыть как то, что уже сделано, так и то,

что ему запланировано еще сделать. Этот недостаток компенсируется ЭВМ,

которая четко фиксирует и информирует пользователя о выполненных  про-

цедурах и предстоящей работе.

    С п о с о б н о с т ь   к   с о с р е д о т а ч и в а н и ю. Эта

способность у человека зависит от многих факторов, например, продолжи-

тельности и напряжения  внимания,  влияния  среды,  общего  состояния.

Усталостью обуславливается рассеянность,  удлинение  реакций,  нецеле-

сообразные действия. В связи с этим интерактивная система  с  разделе-

нием  времени  должна  адаптироваться  к  времени  реакции  отдельного

пользователя.

    Т е р п е н и е. При многократном повторении одних и тех же дейст-

вий человек может испытывать чувство досады. Поэтому  предусматривает-

ся, например, ввод исходных данных  одним  массивом  при  многократном

анализе этих данных. К этому же относится включение в системы макроко-

манд или гибкие сценарии.

    С а м о ч у в с т в и е.  ЭВМ должна беречь самочувствие пользова-

теля, его чувство собственного достоинства и показывать ему, что имен-

но машина его обслуживает, а не наоборот. Вопросы, ответы и  замечания

должны соответствовать разговору между подчиненным и  его  руководите-

лем, определяющим ход и направление процесса проектирования.

    Э м о ц и о н а л ь н о с т ь. Это чувство свойственно человеку и

чуждо ЭВМ. ПО должно возбуждать у пользователя положительные эмоции  и

не допускать отрицательных.

          2.3.Классификация ПО и количественные характеристики

    В основу первой классификации может быть положен объем  ПО,  выра-

жаемый числом исходных команд (ЧИК). Этот термин -  исходные  команды,

охватывает все команды, разработанные в ходе проектирования и  перера-

ботанные в машинный код с помощью препроцессоров, компиляторов  и  ас-

семблеров. Исходные команды не включают комментарии и штатное  ПО,  но

включают операторы языка управления  заданиями,  операторы  флрмата  и

описание.

    Исходя из числа исходных команд (ЧИК)  можно  классифицировать  ПО

следующим образом по размеру:

                Малый...........  2 000 ЧИК

                Промежуточный...  8 000 ЧИК

                Средний......... 32 000 ЧИК

                Большой.........128 000 ЧИК

    Введем следующие обозначения. Будем  считать,  что  человеко-месяц

(ЧМ) состоит из 152 часов рабочего времени. Тогда  для  преобразования

можно использовать следующие правила:

             для получения человеко-часов....умножить ЧМ на 152

             для получения человеко-дней.....умножить ЧМ на 19

             для получения человеко-годов....разделить ЧМ на 12

    Если возможна предварительная оценка разрабатываемого ПО  в  тыся-

чах исходных команд (КЧИК), то затраты труда в ЧМ и  сроки  разработки

могут быть определены уравнениями

                       1,05                      0,38

          ЧМ=2,4*(КЧИК)               СР=2,5*(ЧМ)

    Эти же данные можно представить следующей таблицей.

         Табл.2.3.Характеристики проектов распространенного типа

┌──────────────────┬───────────┬───────────────┬──────────┬──────────┐

│Размер ПО, КЧИК   │ Затраты   │ Производитель-│ Сроки,   │ Средние  │

│                  │ труда, ЧМ │ ность, ЧИК/ЧМ │ месяцы   │ штаты, ЧИ│

├──────────────────┼───────────┼───────────────┼──────────┼──────────┤

│Малый, 2          │    5,0    │     400       │    4,6   │    1,1   │

├──────────────────┼───────────┼───────────────┼──────────┼──────────┤

│Промежуточный, 8  │   21,3    │     376       │    8,0   │    2,7   │

├──────────────────┼───────────┼───────────────┼──────────┼──────────┤

│Средний, 32       │   91,0    │     352       │   14,0   │    6,5   │

├──────────────────┼───────────┼───────────────┼──────────┼──────────┤

│Большой, 128      │  392,0    │     327       │   24,0   │   16,0   │

└──────────────────┴───────────┴───────────────┴──────────┴──────────┘

    Приведенные в табл.2.3 данные относятся  к  коммерческим  програм-

мным продуктам, подразумевающим тщательное документирование,  отладку,

обеспечение надежности при наличии ошибок,  обучение  пользователей  и

т.п. Необходимо помнить, что затраты на такую  разработку  примерно  в

три раза выше, чем на персональную программу.

    Данные табл.2.3 получены на основании анализа 63  проектов  разра-

ботки ПО для разных типов ЭВМ, разных объемов, разного назначения, ис-

пользуюшего различные языки программирования.

    Второй характеристикой для классификации ПО может  служить  качес-

твенная оценка. Различают три типа ПО: распространенный, полунезависи-

мый и встроенный.

    Р а с п р о с т р а н е н н ы й   тип характеризуется тем, что  ПО

разрабатывается относительно небольшой группой  специалистов  в  усло-

виях своей организации. Большинство связанных с проектом  людей  обла-

дают большим опытом работы с аналогичными системами в  условиях  своей

организации.

    Это означает, что большинство участников проекта могут  с  пользой

участвовать на начальных стадиях разработки, не создавая больших  нак-

ладных расходов на обмен информацией о сущности проекта.

    В проекте распространенного  типа  налагаются  относительно  менее

жесткие ограничения на соответствие ПО требованиям и спецификациям ин-

терфейса.

    Другими характерными чертами ПО  распространенного  типа  являются

следующие:

- стабильные условия разработки проекта;

- минимальная необходимость новых системных и алгоритмических решений;

- относительно малое поощрение за раннее завершение проекта;

- относительно малый размер (как правило, до 50 КЧИК).

    В с т р о е н н ы й   тип отличается от других жесткими  ограниче-

ниями на характеристики ЭВМ и правила использования интерфейса.  Такое

изделие должно работать при тесной взаимосвязи  аппаратуры,  программ,

руководств и вычислительных процессов. (Пример - система  резервирова-

ния авиабилетов или система управления воздушным движением).

    При разработке встроенного ПО, как  правило,  отсутствует  возмож-

ность договориться об уменьшении изменений и исправлений в  программах

при модификации требований и интерфейса. Поэтому большие затраты  тру-

да на установление соответствия ПО своим спецификациям  и  обеспечение

правильности изменений.

    По сравнению с распространенным встроенный  проект,  как  правило,

планируется при меньшем объеме информации об условиях его  реализации.

Это требует привлечения бригады аналитиков на ранних  стадиях  проекта

для избежания огромных накладных расходов.

    После завершения проектирования изделия лучшей стратегией  осущес-

твления встроенного проекта является привлечение очень большой  группы

программистов для параллельного выполнения детального  проектирования,

кодирования и автономной отладки.

    П о л у н е з а в и с и м ы й   тип ПО занимает промежуточное поло-

жение между распространенными и  встроенными  типами.  Промежуточность

положения определяется наличием любого из следующих свойств:

- промежуточные значения характеристик проекта;

- смещение характеристик распространенного и встроенного типов.

    Обычно не превосходит 300 КЧИК.

    Теперь можно расширить табл.2.3 характеристиками для  двух  других

типов (табл.2.4).

        Табл.2.4.Оценки для разработки ПО разных типов

┌───────┬────────┬────────────────────────────────────────────────────┐

│Харак- │Тип раз-│            Оценки для размеров                     │

│терис- │работки ├───────┬──────────┬─────────┬─────────┬─────────────┤

│тики   │        │ малый,│ промежу- │ средний │ большой │очень большой│

│       │        │ 2 КЧИК│ точный,  │ 32 КЧИК │ 128 КЧИК│512 КЧИК     │

│       │        │       │ 8 КЧИК   │         │         │             │

├───────┼────────┼───────┼──────────┼─────────┼─────────┼─────────────┤

│Затраты│Распр.  │  5,0  │  21,3    │     91  │   397   │             │

│труда, │Полун.  │  6,5  │  31,0    │    146  │   687   │    3250     │

│ЧМ     │Встр.   │  8,3  │  44,0    │    230  │  1216   │    6420     │

├───────┼────────┼───────┼──────────┼─────────┼─────────┼─────────────┤

│Произво│Распр.  │  400  │  376     │    352  │   327   │             │

│дитель-│Полун.  │  308  │  258     │    219  │   186   │     158     │

│ность, │Встр.   │  241  │  182     │    139  │   105   │      80     │

│ЧИК/ЧМ │        │       │          │         │         │             │

├───────┼────────┼───────┼──────────┼─────────┼─────────┼─────────────┤

│Сроки  │Распр.  │  4,6  │  8,0     │     14  │    24   │             │

│разра- │Полун.  │  4,8  │  8,3     │     14  │    24   │      42     │

│ботки, │Встр.   │  4,9  │  8,4     │     14  │    24   │      42     │

│месяцы │        │       │          │         │         │             │

├───────┼────────┼───────┼──────────┼─────────┼─────────┼─────────────┤

│Среднее│Распр.  │  1,1  │  2,7     │    6,5  │    16   │             │

│число  │Полун.  │  1,4  │  3,7     │   10,0  │    29   │      77     │

│исполни│Встр.   │  1,7  │  4,2     │   16,0  │    51   │     157     │

│телей  │        │       │          │         │         │             │

└───────┴────────┴───────┴──────────┴─────────┴─────────┴─────────────┘

              1.05

 4M = 2.4*КЧИК    - распространенный

              1.12

 4М = 3.0*КЧИК     - полунезависимый

              1.20

 4М = 3.6*КЧИК     - встроенный

              2.4.Жизненный цикл программного обеспечения

    Рассмотрим жизненный цикл программного обеспечения, то  есть  про-

цесс его создания и применения от начала до конца. Этот  процесс  сос-

тоит из нескольких  стадий:  определения  требований  и  спецификаций,

проектирования, программирования, отладки и сопровождения.

    Первая стадия - определение требований и спецификаций, может  быть

названа стадией системного анализа. Общие требования  к  ПО  -  надеж-

ность, технологичность, правильность, универсальность,  эффективность,

информационная согласованность и т.д. Они дополняются требованиями за-

казчика, включающими пространственно-временные ограничения,  необходи-

мые функции и возможности, режимы функционирования, требования точнос-

ти и надежности и т.д., то есть вырабатывается описание системы с точ-

ки зрения пользователя. При определении спецификаций производится точ-

ное описание функций ПО, разрабатываются и утверждаются входные и про-

межуточные языки, форма выходной информации для каждой  из  подсистем,

описывается возможное взаимодействие с другими программными комплекса-

ми, специфицируются средства расширения и модификации  ПО,  разрабаты-

ваются интерфейсы обслуживающих и основных подсистем, решаются  вопро-

сы базы данных, утверждаются  основные  алгоритмы.  Итогом  выполнения

этого этапа являются эксплуатационные и  функциональные  спецификации,

содержащие конкретное описание  ПО.  Разработка  спецификаций  требует

тщательной работы системных аналитиков, постоянно контактирующих с за-

казчиками, которые в большинстве случаев  не  способны  сформулировать

четкие и реальные требования.

    Эксплуатационные спецификации содержат сведения  о  быстродействии

ПО, затратах памяти, требуемых технических средствах, надежности и

т.д.

    Функциональные спецификации определяют функции, которые должно вы-

полнять ПО, то есть в них определяется что надо делать, а не  как  это

делать.

    Спецификации должны быть полными, точными и ясными. Полнота исклю-

чает необходимость получения разработчиками ПО в процессе их работы от

заказчиков иных сведений, кроме  содержащихся  в  спецификациях.  Точ-

ность не позволяет различных толкований.  Ясность  подразумевает  лег-

кость понимания как заказчиком, так и  разработчиком  при  однозначном

толковании.

    Значение спецификаций:

1.спецификации являются заданием на разработку ПО и  их  выполнение  -

  закон для разработкчика;

2.спецификации используются для проверки готовности ПО;

3.спецификации являются неотемлимой частью  программной  документации,

  облегчают сопровождение и модификацию ПО.

    Второй стадией является проектирование ПО. На этом этапе:

1.формируется структура ПО  и  разрабатываются  алгоритмы,  задаваемые

  спецификациями;

2.устанавливается состав модулей с  разделением  их  на  иерархические

  уровни на основе изучения схем алгоритмов;

3.выбирается  структура  информационных  массивов,  составляющих  базу

  данных;

4.фиксируются межмодульные интерфейсы.

    Цель этапа - иерархическое разбиение сложных задач создания ПО  на

подзадачи меньшей сложности. Результатом работы на этом этапе  являют-

ся спецификации на отдельные модули, дальнейшая  декомпозиция  которых

нецелесообразна.

    Третья стадия - программирование.  На  данном  этапе  производится

программирование модулей. Этап менее сложен по сравнению со всеми  ос-

тальными. Проектные решения, полученные на предыдущей  стадии,  реали-

зуются в виде программ. Разрабатываются отдельные блоки и  подключают-

ся к создаваемой системе. Одна из задач -  обоснованный  выбор  языков

программирования. На этой же стадии решаются все вопросы, связанные  с

особенностями типа ЭВМ.

    Четвертая стадия -  отладка  ПО,  заключающаяся  в  аппробировании

всех требований, всех структурных элементов системы и такого  количес-

тва всевозможных комбинаций, какое только позволяет  здравый  смысл  и

бюджет. Этап предполагает выявление в программах ошибок, проверку  ра-

ботоспособности ПО, а также его соответствие спецификациям.

    Пятая стадия - сопровождение, то есть процесс исправления  ошибок,

координации всех элементов  системы  в  соответствии  с  потребностями

пользователя, внесения всех нужных ему исправлений  и  изменений.  Это

вызвано, как минимум, двумя причинами: во-первых, в ПО остаются  ошиб-

ки, не выявленные при тестировании; во-вторых, пользователи в ходе эк-

сплуатации ПО настаивают на внесении в него изменений и  его  дальней-

шем совершенствовании.

    В общем случае, в процессе  разработки  ПО  требуется  осуществить

несколько итераций.

    Распределение временных и стоимостных затрат по отдельным  стадиям

жизненного цикла программного обеспечения представлено в табл.2.5 и

2.6.

       Табл.2.5.Затраты по стадиям жизненного цикла ПО

                   ┌──────────────────────────────────────────┐

                   │       Сведения из разных источников      │

┌──────────────────┼────────┬─────────┬───────┬────────┬──────┼───────┐

│Стадии жизненного │Гласс Р.│Энкарнач-│Боэм Б.│Федорчук│Вишня-│       │

│цикла программного│Нуазо Р.│чо Ж.    │       │Чернень-│ков   │Среднее│

│обеспечения       │        │         │       │кий     │      │       │

├──────────────────┼────────┼─────────┼───────┼────────┼──────┼───────┤

│Определение требо-│    10  │    15   │    6  │    6   │   6  │   8,6 │

│ваний и специфик. │        │         │       │        │      │       │

├──────────────────┼────────┼─────────┼───────┼────────┼──────┼───────┤

│Проектирование    │    10  │    12   │   18  │    5   │   6  │  10,2 │

├──────────────────┼────────┼─────────┼───────┼────────┼──────┼───────┤

│Программирование  │    10  │    12   │    9  │    7   │   6  │   8,8 │

├──────────────────┼────────┼─────────┼───────┼────────┼──────┼───────┤

│Отладка           │    20  │    15   │   17  │   15   │  14  │  16,2 │

├──────────────────┼────────┼─────────┼───────┼────────┼──────┼───────┤

│Сопровождение     │    50  │    46   │   50  │   67   │  68  │  56,2 │

│──────────────────┼────────┼─────────┼───────┼────────┼──────┼───────┤

│Всего             │   100  │   100   │  100  │  100   │ 100  │ 100   │

└──────────────────┴────────┴─────────┴───────┴────────┴──────┴───────┘

    Табл.2.6.Основные параметры стадий жизненного цикла ПО

┌────────────────────┬──────────────┬─────────────┬──────────────┐

│Стадии жизненного   │  Количество  │  Обнаруже-  │  Затраты на  │

│цикла программного  │  ошибок,%%   │  ние ошибок │  устранение  │

│обеспечения         │              │  %%         │  ошибок,%%   │

├────────────────────┼──────────────┼─────────────┼──────────────┤

│Определение требо-  │              │             │      9       │

│ваний и спецификаций│              │             │              │

├────────────────────┼──────────────┼─────────────┼──────────────┤

│Проектирование      │     61-64    │             │      6       │

├────────────────────┼──────────────┼─────────────┼──────────────┤

│Программирование    │     36-39    │             │     10       │

├────────────────────┼──────────────┼─────────────┼──────────────┤

│Отладка             │              │      46     │     12       │

├────────────────────┼──────────────┼─────────────┼──────────────┤

│Сопровождение       │              │      54     │     63       │

└────────────────────┴──────────────┴─────────────┴──────────────┘

    Основные временные соотношения между отдельными видами работ можно

представить сетевым графиком разработки ПО.

              ┌──┐                ┌──┐                ┌──┐

              │13│                │13│                │ 8│

    ┌─────────┴──┤      ┌─────────┴──┤      ┌─────────┴──┤

    │ Разработка │─────│ Проектиро- │─────│ Документи- │──────┐

    │ требований │      │ вание      │      │ рование    │      │

    └────────────┘      └────────────┘      └────────────┘      │

      ‑         │                  │                            │

      │         │        ┌──┐      │                            │

      │         ­        │ 8│      │              ┌──┐          │

      │        ┌─────────┴──┤      ­              │ 8│          ­

 ┌────────┐    │ Подготовка │     ┌───────────────┴──┤      ┌───────┐

 │ Начало │    │ данных для │     │ Программирование │      │ Конец │

 └────────┘    │ отладки    │     └──────────────────┘      └───────┘

      │        └────────────┘                      │            ‑

      │         │          │                       │            │

      │         │          └───────────────────┐   │            │

      │         │                              │   │            │

      ­         ­                              ­   ­            │

    ┌────────────┐      ┌────────────┐      ┌────────────┐      │

    │ Планирова- │      │ Разработка │      │ Испытание  │      │

    │ ние отладки│─────│ драйверов  │─────│ программно-│──────┘

    │            │      │ тестов     │      │ го изделия │

    └─────────┬──┤      └─────────┬──┤      └─────────┬──┤

              │ 8│                │25│                │17│

              └──┘                └──┘                └──┘

              Рис.2.7.Сетевой график разработки ПО.

       (цифры означают время в %% от полного времени первых

        четырех этапов жизненного цикла)

                    2.5.Общие принципы разработки ПО

                    2.5.1.Общие принципы

    Программное обеспечение  различается  по  назначению,  выполняемым

функциям, формам реализации. В этом смысле ПО  -  сложная,  достаточно

уникальная программная система. Однако можно полагать, что  существуют

некоторые общие принципы, которые следует использовать при  разработке

ПО.

    Ч а с т о т н ы й   п р и н ц и п. Основан на выделении в алгорит-

мах и в обрабатываемых структурах действий и  данных  по  частоте  ис-

пользования. Для действий, которые часто встречаются  при  работе  ПО,

обеспечиваются условия их быстрого выполнения.  К  данным,  к  которым

происходит частое обращение, обеспечивается наиболее  быстрый  доступ.

"Частые" операции стараются делать более короткими.

    П р и н ц и п   м о д у л ь н о с т и.  Под модулем в общем случае

понимают функциональный элемент рассматриваемой системы, имеющий офор-

мление, законченное и выполненное в  пределах  требований  системы,  и

средства сопряжения с подобными элементами или элементами более  высо-

кого уровня данной или другой системы.

    Способы обособления составных частей ПО в отдельные  модули  могут

быть существенно различными. Чаще всего разделение происходит по  фун-

кциональному признаку. В значительной степени  разделение  системы  на

модули определяется используемым методом проектирования ПО.

    П р и н ц и п   ф у н к ц и о н а л ь н о й   и з б и р а т е л ь-

н о с т и.  Этот принцип является логическим продолжением частотного и

модульного принципов и используется при проектировании ПО, объем кото-

рого существенно превосходит имеющийся объем оперативной памяти. В  ПО

выделяется некоторая часть важных модулей,  которые  постоянно  должны

быть в состоянии готовности для эффективной организации вычислительно-

го процесса. Эту часть в ПО называют ядром или монитором. При формиро-

вании состава монитора  требуется  удовлетворить  двум  противоречивым

требованиям. В состав монитора, помимо чисто управляющих модулей, дол-

жны войти наиболее часто используемые модули. Количество модулей  дол-

жно быть таким, чтобы объем памяти, занимаемой монитором, был не слиш-

ком большим. Программы, входящие в состав монитора, постоянно  хранят-

ся в оперативной памяти. Остальные  части  ПО  постоянно  хранятся  во

внешних запоминающих устройствах и загружаются  в  оперативную  память

только при необходимости, перекрывая друг друга при необходимости.

    П р и н ц и п   г е н е р и р у е м о с т и.   Основное  положение

этого принципа определяет такой способ исходного представления ПО, ко-

торый бы позволял осуществлять настройку  на  конкретную  конфигурацию

технических средств, круг решаемых проблем, условия работы пользовате-

ля.

    П р и н ц и п   ф у н к ц и о н а л ь н о й   и з б ы т о ч н о с-

т и.  Этот принцип учитывает возможность проведения одной и той же ра-

боты различными средствами. Особенно важен  учет  этого  принципа  при

разработке пользовательского интерфейса для выдачи данных из-за психо-

логических различий в восприятии информации.

    П р и н ц и п   "п о   у м а л ч и в а н и ю". Применяется для об-

легчения организации связей с системой как на стадии генерации, так  и

при работе с уже готововым ПО. Принцип основан на хранении  в  системе

некоторых базовых описаний структур, модулей, конфигураций  оборудова-

ния и данных, определяющих условия работы с ПО.

    Эту информацию ПО использует в качестве заданной,  если  пользова-

тель забудет или сознательно не конкретизирует ее. В данном случае  ПО

само установит соответствующие значения.

                    2.5.2.Общесистемные принципы

    При создании и развитии ПO рекомендуется применять следующие обще-

системные принципы:

- принцип включения, который предусматривает, что требования к  созда-

  нию, функционированию и развитию ПО определяются  со  стороны  более

  сложной, включающей его в себя системы;

- принцип системного единства, который состоит  в  том,  что  на  всех

  стадиях создания, функционирования и  развития  ПО  его  целостность

  будет   обеспечиваться   связями   между   подсистемами,   а   также

  функционированием подсистемы управления;

- принцип развития,  который  предусматривает  в  ПО  возможность  его

  наращивания и совершенствования компонентов и связей между ними;

- принцип комплексности, который заключается в том, что ПО обеспечива-

  ет связность обработки информации как  отдельных  элементов,  так  и

  для всего объема данных в целом на всех стадиях обработки;

- принцип информационного  единства,  то  есть  во  всех  подсистемах,

  средствах обеспечения и компонентах ПО используются единые  термины,

  символы, условные обозначения и способы представления;

- принцип совместимости, который состоит в  том,  что  язык,  символы,

  коды и средства обеспечения ПО согласованы, обеспечивают  совместное

  функционирование всех его подсистем и сохраняют  открытой  структуру

  системы в целом;

- принцип инвариантности, который  предопределяет,  что  подсистемы  и

  компоненты ПО  инвариантны  к  обрабатываемой  информации,  то  есть

  являются универсальными или типовыми.


               3.АНАЛИЗ ТРЕБОВАНИЙ И РАЗРАБОТКА СПЕЦИФИКАЦИЙ

                        3.1.Общие положения

    Разработку программного обеспечения можно рассматривать как после-

довательность следующих действий: определение требований;  составление

спецификаций; проектирование логики;  программирование;  тестирование;

документирование.

                         │

                         │─────────────────────────────────────────┐

   ──────────────╔════════════════╗                                 │

    ‑            ║                ║                                 │

    │            ║    Условия     ║                                 │

    │            ║                ║                                 │

    │            ╚════════════════╝                                 │

    │ Определение        │                                          │

    │ требований         ­ Анализ                                   │

    │            ╔════════════════╗                                 │

    │            ║ Функциональная ║                                 │

    │            ║   архитектура  ║                                 │

    ­            ║                ║                                 │

   ──────────────╚════════════════╝                                 │

                         │                                          │

                         │ Проектирование                           │

                         │      ╔════════════════╗                  │

                         │      ║  Архитектура   ║                  │

                         └─────║    системы     ║                  │

                                ║                ║                  │

                                ╚════════════════╝                  │

                                         │                          │

                                         │  Построение              │

                                         │       ╔════════════════╗ │

                                         │       ║  Операционная  ║ │

                                         └──────║    система     ║─┘

                                                 ║                ║

                                                 ╚════════════════╝

                   Рис.3.1.Этапы построения системы.

    Два первых этапа имеют в основном аналитический  характер,  причем

уровень этого анализа выше уровня проектирования  и  реализации  новой

системы. Их результатом является функциональная спецификация. На  сле-

дующем этапе проектирования определяется архитектура  системы.  Задачи

проектирования должны быть оценены с точки зрения спецификации  и  тех

целей, которые нужно достигнуть. Программирование и тестирование  под-

держиваются операционной системой. Документирование необходимо на всех

этапах разработки.

    Составление спецификации, проектирование логики  и  реализация  ПО

очень часто начинаются еще до того, как станут известны все  имеющиеся

требования, граничные условия и функции системы.  Однако  даже  лучший

программист не сможет написать хорошую программу, если точно  не  уяс-

нит условия задачи, а оптимально структурированная  программа  не  вы-

даст осмысленных результатов, если задача соответствующим  образом  не

поставлена. Поэтому необходимо полностью и всесторонне описать  требо-

вания, которым программа должна удовлетворять.

    Определение требований включает в себя анализ  задачи  и  ведет  к

составлению функциональной спецификации. Необходимо ответить  на  сле-

дующие три основные вопроса:

        Условия

          

   ┌────────────────┐

   │     Анализ     │

   │   внедрения    │  Почему?    Почему понадобилась система?

   │    системы     │             (необходим анализ той среды, в ко-

   └────────────────┘             торую система должна внедряться);

           │

           ­

   ┌────────────────┐             Что система должна делать?

   │ Функциональная │             (в функциональной спецификации дол-

   │  спецификация  │  Что?       жны быть описаны наиболее важные

   │                │             возможности системы);

   └────────────────┘

           │                      Каким образом можно реализовать

           ­                      систему?

   ┌────────────────┐             (этот вопрос относится к ресурсам,

   │    Проектные   │             которые могут понадобиться при реа-

   │   ограничения  │  Как?       лизации и эксплуатации системы, а

   │                │             также к ограничениям, налагаемым

   └────────────────┘             средой; вопрос о том, какие шаги

           │                      необходимо предпринять для реализа-

           ­                      ции, будет поставлен позже в проце-

                                  ссе разработки системы).

   Рис.3.2.Вопросы, возникающие в процессе разработки системы.

    Ответы на эти вопросы должны полностью описывать требования, кото-

рым должна удовлетворять  система.  Такого  рода  описания  определяют

структуру задачи, но не решают ее. Описание  ограничений  лишь  задает

граничные условия, необходимые для последующего составления специфика-

ций, проектирования логики и реализации. Анализ системы, в  результате

которого определяется функциональная архитектура, должен проводится на

таком уровне детализации, который позволит точно определить:

- функциональные возможности системы (набор функций и налагаемые  сре-

  дой ограничения);

- тип описания (на формальном или естественном языке);

- критерии оптимизации (которые необходимы  для  нахождения  разумного

  компромисса между противоречивыми требованиями).

    Из-за пренебрежения анализом требований и  предварительным  анали-

зом осуществимости были прекращены такие проекты:

- система стоимостью  56  млн  долларов  для  предварительного  заказа

авиабилетов;

- система стоимостью 217  млн  долларов  для  материально-технического

снабжения;

    Исправление ошибки на фазе сопровождения большого проекта обходит-

ся обычно в 100 раз дороже, чем исправление той же ошибки на фазе ана-

лиза требований (табл.2.6).

┌──────┬─────────────────────────────────────────────────────────────┐

│Пример│П1.Определение предметной области и начальных требований     │

├──────┴─────────────────────────────────────────────────────────────┤

│    Рассмотрим весь комплекс вопросов, связанных с разработкой прог-│

│раммного обеспечения, моделирующего работу центральных устройств ЭВМ│

│- центрального  процессора  (ЦП) и  оперативного  запоминающего  ус-│

│тройства (ОЗУ) в мультипрограммном режиме.                          │

│                                                                    │

│    Почему понадобилась система?                                    │

│    Одной из ключевых проблем любой  операционной  системы  является│

│распределение ресурсов. Операционная система распределяет ресурсы  в│

│соответствии с нуждами пользователей и возможностями машины и с уче-│

│том обычных требований эффективности и надежности работы.           │

│    Основными ресурсами любой ЭВМ являются время ЦП и память ОЗУ.   │

│Планирование этих ресурсов для распределения между  различными  про-│

│цессами породило большое число вариантов  стратегий.  Изучение  этих│

│стратегий с той или иной степенью детализации входит в  число  задач│

│многих дисциплин профессиональной подготовки в области информатики и│

│вычислительной техники.                                             │

│                                                                    │

│    Для ответа на вопрос, что система должна делать, введем  концеп-│

│туальные понятия теории операционных систем (ОС).                   │

│    Процессом называется программа находящаяся в решении. Для выпол-│

│нения вычислительной работы ОС выделяет процессам ЦП. В однопрограм-│

│мной ОС присутствует только один пользовательский процесс. В мульти-│

│программной системе на ресурсы может претендовать много  независимых│

│процессов. Процесс создается, когда выполнение задания  пользователя│

│начинается, и уничтожается, когда задание завершается. Во время сво-│

│его существования процесс может находиться в одном из  трех  состоя-│

│ний. Процесс активен, когда он использует ЦП  для  выполнения  своих│

│команд. Процесс блокирован, если его выполнение может быть продолже-│

│но только после наступления некоторого ожидаемого им события. Напри-│

│мер, процесс может быть заблокирован, потому что ему требуется ждать│

│завершения операции ввода/вывода (I/O). Процессы, которые не  актив-│

│ны и не блокированы, называются находящимися в состоянии готовности.│

│Этим процессам будет передан ЦП после того, как текущий процесс  его│

│отдаст. Возможные переходы из одного состояния в другое показаны  на│

│рисунке.                                                            │

│                                                                    │

│                                                                    │

│            Ожидает           ┌──────────────┐     Событие          │

│        ┌─────────────────── │ Блокирование ├─────────────────┐    │

│        │   события           └──────────────┘     наступило   │    │

│        │                                                      │    │

│   ┌────┴───────┐ Истек квант                                  │    │

│   │ Активность ├───────────────────┐                          │    │

│   └────────────┘ времени           │                          │    │

│        ‑                           │                          │    │

│        │                           ­                          │    │

│        │                     ┌────────────┐                   │    │

│        └─────────────────────┤ Готовность │──────────────────┘    │

│                              └────────────┘                        │

│                                                                    │

│                                                                    │

│    В любой момент времени активным может быть только один  процесс.│

│При передаче управления процессу пользователя ОС  устанавливает  ин-│

│тервальный таймер, задавая тем самым квант времени, являющийся  мак-│

│симальным количеством времени ЦП, на которое процесс получает управ-│

│ление. Если это время истекает, процесс переводится из состояния ак-│

│тивности в состояние готовности. После этого ОС, согласно  стратегии│

│планирования, выбирает следующий процесс, находящийся в  готовности,│

│переводит его в состояние активности и передает ему управление.  Мо-│

│жет оказаться, что активный процесс, не использовав  полностью  пре-│

│доставленный ему квант времени, должен ожидать наступления некоторо-│

│го события, например завершения операции I/O. В этом  случае  актив-│

│ный процесс блокируется, а какой-то другой готовый процесс активизи-│

│руется. Обычно до своего завершения процесс много  раз  пребывает  в│

│состояниях активности, готовности и блокировки.                     │

│    Выбор следующего процесса для  активизации  из  очереди  готовых│

│процессов и организация таких очередей могут осуществляться  различ-│

│ными способами. Простейший способ организации очередей заключается в│

│формировании очереди по мере порождения, то есть  вновь  порождаемый│

│процесс ставится в конец очереди. Это так  называемая  бесприоритет-│

│ная организация. Процессу при его  порождении  может  быть  присвоен│

│приоритет, в соответствии с которым он может быть поставлен в соот- │

│ветствующее место очереди. Обслуживание очереди готовых процессов,  │

│как правило, осуществляется активизацией первого в очереди процесса.│

│    В наиболее простом случае, выбранному для  активизации  процессу│

│разрешается использовать ЦП вплоть до своего завершения.  Если  оче-│

│редь бесприоритетна, то такая стратегия называется FIFO (First In  -│

│First Out). В более сложной стратегии, называемой круговым цикличес-│

│ким алгоритмом (Robin Round), каждому активизируемому процессу  пре-│

│доставляется одинаковый квант времени, по  истечении  которого  про-│

│цесс либо завершается, либо возвращается в конец очереди для  после-│

│дующего обслуживания.                                               │

│    Приоритеты могут быть статическими  и  динамически  изменяемыми.│

│Если не рассматривать субъективное назначение  приоритетов,  связан-│

│ное с типами пользователей и важностью программ, то наиболее  сущес-│

│твенным критерием для назначения приоритета является время ЦП,  тре-│

│буемое процессу. Более короткие по времени выполнения процессы  дол-│

│жны обслуживаться раньше. Реализация такой стратегии в  ОС  пакетной│

│обработки получила название SJF (Shortest Job First).  Процессу  при│

│его порождении присваивается приоритет в зависимости  от  требуемого│

│времени ЦП, в соответствии с которым он ставится в  очередь  готовых│

│процессов, а при активизации выполняется до конца. В ОС  с  разделе-│

│нием времени используют назначение неявных динамических приоритетов,│

│когда каждый активный процесс, которому  еще  необходимо  время  ЦП,│

│возвращается в конец менее приоритетной очереди. Такая стратегия на-│

│зывается стратегией обратных очередей или FB (Feed Back).           │

│    Любая ОС, поддерживающая мультипрограммный режим работы,  должна│

│обладать механизмом разделения ОЗУ  между  совместно  выполняющимися│

│процессами. Процесс может считаться порожденным только  при  условии│

│размещения его загрузочного модуля в ОЗУ.  Многие  мультипрограммные│

│ОС разбивают ОЗУ на разделы (partitions), с выделением каждому  про-│

│цессу своего раздела. Размер и расположение разделов могут быть  ли-│

│бо заранее заданы  (разделы  фиксированного  размера),  либо  назна-│

│чаться динамически в процессе выполнения заданий (разделы переменно-│

│го размера).                                                        │

│    В простейшей стратегии распределения с разделами  фиксированного│

│размера каждое входящее задание загружается в наименьший  подходящий│

│по объему раздел. Если размер раздела превосходит размер загружаемо-│

│го модуля, то оставшаяся внутри раздела память не используется.  Од-│

│нажды загруженное в раздел задание остается там до конца своего  вы-│

│полнения. После того как задание завершится,  занимаемый  им  раздел│

│вновь становится доступным для использования.                       │

│    В стратегии распределения с разделами  переменного  размера  для│

│каждого загружаемого задания создается  новый  раздел  с  размерами,│

│соответствующими заданию. После окончания задания отведенная ему па-│

│мять ОЗУ освобождается и объединяется со всеми  смежными  свободными│

│областями, а затем может быть использована при распределении  других│

│разделов.                                                           │

│    Единой проблемой для обеих рассмотренных  стратегий  распределе-│

│ния памяти ОЗУ между загружаемыми модулями является фрагментация па-│

│мяти, когда доступная свободная память разбита на несколько  несмеж-│

│ных блоков, каждый из которых слишком мал для использования.        │

│    Одно из возможных решений этой проблемы связано с использованием│

│стратегии перемещаемых разделов. После окончания каждого задания ос-│

│тавшиеся разделы сдвигаются к одному из концов памяти. В результате │

│этого вся доступная свободная память собирается в один общий блок,  │

│который больше подходит для  распределения новых разделов.          │

│    В зависимости от стоящих перед учебной дисциплиной целей необхо-│

│димо иметь:                                                         │

│- чисто визуальное моделирование взаимосвязанной работы  центральных│

│  устройств ЭВМ по обслуживанию процессов;                          │

│- более детальное моделирование с возможностью  фиксации  размещения│

│  отдельных заданий в ЦП и ОЗУ и временных интервалов обработки;    │

│- инструментальное средство для накопления  статистической  информа-│

│  ции обслуживания процессов;                                       │

│- возможность генерации случайной последовательности  обрабатываемых│

│  процессов с задаваемыми характеристиками распределения параметров.│

│    Решение указанных задач должно быть выполнено с  помощью  персо-│

│нальной вычислительной техники.                                     │

│    В большинстве случаев, анализ стратегий работы ЦП и  ОЗУ  прово-│

│дится независимо друг от друга, хотя и делаются оговорки о необходи-│

│мости учета взаимосвязанности  этих  устройств.  Разрабатываемое  ПО│

│предполагает совместное моделирование центральных устройств ЭВМ.    │

│    Учебный характер разрабатываемого программного обеспечения  тре-│

│бует тщательной проработки формы и методов визуализации процесса мо-│

│делирования и его результатов.                                      │

│                                                                    │

│    Как можно реализовать систему моделирования  работы  центральных│

│устройств ЭВМ?                                                      │

│    Очевидно, что для моделирования мультипрограммного  обслуживания│

│каждый процесс может быть представлен тремя параметрами:            │

│- требуемым временем обработки на ЦП;                               │

│- временным интервалом порождения  по  отношению  к  предшествующему│

│  процессу;                                                         │

│- требуемым объемом оперативной памяти.                             │

│    Исходя из этого, необходимо создать генератор случайной последо-│

│вательности процессов с регулируемыми законами распределения по каж-│

│дому из указанных выше параметров,  а  также  структуру  данных  для│

│представления характеристик процессов. Структура данных  должна  до-│

│пускать динамическое изменение числа процессов в  последовательности│

│и очередях, а связанные с ней процедуры и функции - наращивание чис-│

│ла рассматриваемых стратегий планирования, что соответствует  объек-│

│тно-ориентированной форме представления очереди или очередей процес-│

│сов.                                                                │

│    Моделирование работы ЦП и ОЗУ должно быть осуществлено  обработ-│

│кой последовательности процессов в соответствии с назначаемыми стра-│

│тегиями и с помощью процедур и функций вводимых типов данных.       │

└────────────────────────────────────────────────────────────────────┘

                  3.2.Документирование требований

                3.2.1.Цели документации требований

    Для того, чтобы документация требований была согласованной  и  по-

лезной, необходимо принять явные решения относительно  целей,  которым

она должна служить. Ее содержание, организация и стиль зависят от  ре-

шений, принятых по следующим вопросам:

      - на какие вопросы документация должна давать ответы?

      - кто ее читатели?

      - как ее будут использовать?

      - какие предварительные знания нужны читателю?

    Исходя из этих вопросов целями документирования требований являют-

ся следующие шесть пунктов.

      1.Задавать только внешнее поведение.

    Описание требований должно задавать лишь внешнее поведение  систе-

мы и не навязывать какой-либо конкретной реализации.

      2.Задавать ограничения на реализацию.

    Кроме определения корректного поведения программы, требования дол-

жны содержать ограничения, накладываемые  на  реализацию,  особенно  в

части интерфейсов с внешним окружением.

      3.Быть легко изменяемым.

    Поскольку требования изменяются, должно  быть  облегчено  внесение

изменений в соответствующие документы. Если документация не обновляет-

ся в течение жизненного цикла системы, то контроль за развитием систе-

мы теряется и становится трудно координировать изменения,  вносимые  в

программу сопровождающим персоналом.

      4.Служить справочным материалом.

    Основное назначение документа - быстро давать ответы  на  конкрет-

ные вопросы, а не объяснять в  общих  словах,  что  делает  программа.

Необходимо предусмотреть глоссарий, детальное оглавление и  различного

рода указатели.

      5.Прогнозировать жизненный цикл системы.

    Для любого программного продукта одни изменения сделать легче, чем

другие, и соответствующие указания в требованиях помогут  разработчику

добиться того, чтобы наиболее вероятные изменения были  легко  осущес-

твимы.

      6.Описывать дупустимую реакцию на нежелательные события.

    При определении требований следует предвидеть нежелательные  собы-

тия, такие, как сбои аппаратуры и ошибки пользователя. Реакции на  не-

желательные события следует задавать в документе, содержащем определе-

ние требований, а не оставлять на усмотрение программиста.

               3.2.2.Принципы документирования требований

    При документировании требований следует  придерживаться  следующих

трех принципов.

      1.Ставить вопросы прежде, чем пытаться на них отвечать.

    На всех стадиях написания  требований  необходимо  концентрировать

усилия на формулировке тех вопросов, на которые следует  дать  ответы.

Для этого очень полезно иметь общие классы вопросов хотя бы в виде ог-

лавления будущего документа.

               Таблица 3.1.Примерное оглавление документа требований

 ┌───────────────────────┬──────────────────────────────────────────┐

 │     Глава             │           Содержание                     │

 ├───────────────────────┼──────────────────────────────────────────┤

 │   Введение            │ Принципы организации документа; краткое  │

 │                       │ содержание остальных глав; обозначения   │

 ├───────────────────────┼──────────────────────────────────────────┤

 │ 1.Характеристики ЭВМ  │ Если ЭВМ задана заранее, то ее общее опи-│

 │                       │ сание с учетом специфических черт; в про-│

 │                       │ тивном случае - основные требования к ЭВМ│

 ├───────────────────────┼──────────────────────────────────────────┤

 │ 2.Интерфейсы с внешним│ Краткое описание информации, получаемой  │

 │   окружением          │ и передаваемой разрабатываемой системой  │

 ├───────────────────────┼──────────────────────────────────────────┤

 │ 3.Функции программы   │ Что должна делать программа, чтобы удов- │

 │                       │ летворять требованиям в разных ситуациях;│

 │                       │ какой должна быть ее реакция на различные│

 │                       │ события                                  │

 ├───────────────────────┼──────────────────────────────────────────┤

 │ 4.Временные ограниче- │ Как быстро и как часто должна выполняться│

 │   ния                 │ каждая из функций. Этот аспект рассматри-│

 │                       │ вается отдельно от главы 3, так как отве-│

 │                       │ ты на вопросы "что?" и "когда?" изменяют-│

 │                       │ ся независимо                            │

 ├───────────────────────┼──────────────────────────────────────────┤

 │ 5.Требования к точнос-│ Каковы допустимые отклонения выходных па-│

 │   ти                  │ раметров от точных значений              │

 ├───────────────────────┼──────────────────────────────────────────┤

 │ 6.Реакция на нежела-  │ Что программа должна делать при выходе из│

 │   тельные события     │ строя аппаратуры и датчиков, получении   │

 │                       │ некорректных данных от пользователя и т.п│

 ├───────────────────────┼──────────────────────────────────────────┤

 │ 7.Подмножества        │ Какие части системы необходимо сделать   │

 │                       │ легко удаляемыми                         │

 ├───────────────────────┼──────────────────────────────────────────┤

 │ 8.Фундаментальные     │ Характеристики программы, которые не из- │

 │   предположения       │ меняются ни при каких модификациях       │

 ├───────────────────────┼──────────────────────────────────────────┤

 │ 9.Изменения           │ Типы внесенных или ожидаемых изменений   │

 ├───────────────────────┼──────────────────────────────────────────┤

 │10.Глоссарий           │                                          │

 └───────────────────────┴──────────────────────────────────────────┘

    Затем готовятся вопросы по каждой главе. Как и  всякая  работа  по

проектированию, постановка вопросов носит итеративный характер.

      2.Разделять аспекты.

    Смысл состоит в сосредоточении на хорошо определенной  совокупнос-

ти вопросов. Соблюдение этого принципа способствует  также  облегчению

модификации документа, поскольку приводит к хорошей локализации  изме-

нений.

      3.Как можно больше формализации.

    Следует избегать чисто словесных описаний, а для  достижения  точ-

ности, краткости,  непротиворечивости  и  полноты  разрабатывать  фор-

мальные способы представления информации.

┌──────┬─────────────────────────────────────────────────────────────┐

│Пример│П2.Уточнение требований                                      │

├──────┴─────────────────────────────────────────────────────────────┤

│    Неообходимость создания достаточно простых механизмов  генерации│

│случайных характеристик процессов и их статистической обработки пос-│

│лужила причиной принятия решения о дискретном характере данных. Каж-│

│дый из трех случайно генерируемых параметров  процесса  будет  изме-│

│ряться натуральным числом из интервала от 1 до 9. Этими числами  бу-│

│дут определяться условные единицы времени и памяти ОЗУ.             │

│    В качестве стратегий распределения времени ЦП  между  различными│

│процессами приняты следующие :                                      │

│- стратегия очередей (первым пришел - первым обслужен);             │

│- планирование по приоритету (обслуживание первыми самых кратких);  │

│- круговой циклический алгоритм;                                    │

│- очередь с обратной связью.                                        │

│    Моделирование работы ОЗУ осуществляется для следующих  стратегий│

│распределения памяти:                                               │

│- с разделами фиксированного размера;                               │

│- с разделами переменного размера;                                  │

│- с перемещаемыми разделами.                                        │

│    Разнообразные цели использования  разрабатываемого  программного│

│обеспечения требуют нескольких форм визуализации процессов моделиро-│

│вания:                                                              │

│- раздельного представления, для возможности  изучения  работы  либо│

│  ЦП, либо ОЗУ;                                                     │

│- совместного представления, но либо в виде моделируемых устройств c│

│  интерпретацией обрабатываемых процессов, либо в виде накапливаемой│

│  статистической информации.                                        │

│                                                                    │

└────────────────────────────────────────────────────────────────────┘

                       3.3.Анализ требований

    Предлагаемое заказчиком исходное описание программы обычно не  яв-

ляется ни полным, ни точным. Назначение анализа требований  заключает-

ся в изучении требований заказчика таким  образом,  чтобы  можно  было

правильно понять и аккуратно описать эти требования. Этот  анализ  мо-

жет предполагать консультации, поскольку главным судьей в  данной  си-

туации является сам заказчик.

    Анализ требований лучше всего начать с рассмотрения того, как  об-

стоит дело у заказчика в настоящий момент. Если имеющаяся у него  сис-

тема уже работала некоторое время, то наверняка уже  были  разработаны

некоторые методы удовлетворительной работы, обработки ошибок и различ-

ных конфликтных ситуаций. Имеющаяся система может  служить  источником

идей не только относительно имеющихся решений, но и  относительно  но-

вых задач. Изучение системы заказчика может  также  облегчить  процесс

согласования новой системы с существующей организацией.  Система  дол-

жна быть совместима с уже имеющимися  системами,  а  также  согласовы-

ваться с имеющимися организационными требованиями.

    При анализе требований необходимо  рассматривать  как  нормальные,

так и аварийные ситуации. Изучение поведения в нормальном режиме пред-

полагает определение эффекта всех безошибочных взаимодействий  пользо-

вателя с программой в предположении, что программа  находится  в  нор-

мальном состоянии. Случай рассмотрения нормального режима является са-

мой простой частью проблемы, поэтому рекомендуется начинать  именно  с

него. Хорошим подходом может служить разработка сценариев  всех  типо-

вых взаимодействий с системой.

    Случаи, предполагающие  безошибочную  работу,  представляют  собой

лишь весьма малую часть всех возможных вариантов поведения  программы,

поэтому весьма важно рассмотреть и описать поведение программы при на-

личии ошибок. Аналитик должен попытаться обнаружить все возможные  ва-

рианты ошибок, которые могут произойти, и разработать  соответствующие

реакции программы во всех таких случаях. Ошибки исходят из двух источ-

ников: пользователей, работающих с программой, и программных  и  аппа-

ратных сбоев. Для изучения  ошибок  пользователя  удобно  использовать

сценарии, которые позволяют  выделить  места  внесения  пользователями

ошибок.

    В процессе анализа требований должен быть рассмотрен  ряд  следую-

щих аспектов:

- поведение программы должно быть определено как для правильных, так и

  для неправильных входных значений;

- должны быть исследованы различные аспекты, связанные с  программными

  и аппаратными ошибками, в частности ограничения на доступность и на-

  дежность;

- должны быть учтены пространственно-временные ограничения.  Эффектив-

  ность должна учитываться с самого начала;

- необходим учет ограничений в сроках разработки. График поставки  го-

  тового продукта заказчику может оказать большое влияние на весь про-

  цесс проектирования и реализации;

- полезно отдельно рассматривать те части спецификации, которые в  бу-

  дущем могут быть изменены;

- желательно знать, является ли создаваемая система  совершенно  новой

  или же следующей в ряду аналогичных систем, с тем чтобы  предусмотреть

  в ней возможности дальнейшей модификации.

    Конечной целью анализа требований  является  составление  функцио-

нальной спецификации. Составить спецификацию значит  точно  определить

данную задачу программирования. Основные правила составления  специфи-

кации следующие:

- в спецификации должны  содержаться  только  предложения,  касающиеся

  вопроса "что сделать?"  (требования,  которым  должно  удовлетворять

  ПО), а не вопроса "как сделать?" (проблемы реализации ПО);

- спецификация должна представлять собой полное и точное описание  за-

  дачи, которую ПО должно решать;

- для различных категорий читателей  должна  быть  обеспечена  возмож-

  ность без труда найти в спецификации интересующую их информацию; ин-

  формация должна подаваться в легковоспринимаемом виде;

- поскольку большинство читателей спецификаций не  относится  к  числу

  специалистов в области обработки данных, следует, насколько это воз-

  можно, избегать терминологии, связанной с  обработкой  данных;  фор-

  мальные представления следует помещать в приложении, а примеры  дол-

  жны приводиться только в иллюстративных целях;

- все спецификации должны строиться по модульному принципу; вся после-

  дующая документация, описывающая конечный продукт, должна  строиться

  на основе соответствующих частей спецификации без необходимости  из-

  менения структуры (в основном с помощью дополнительного редактирова-

  ния текста);

- спецификация должна быть составлена так, чтобы внесение в нее допол-

  нений, изменений и исключений не требовало больших усилий.

┌──────┬─────────────────────────────────────────────────────────────┐

│Пример│П3.Функциональная спецификация                               │

├──────┴─────────────────────────────────────────────────────────────┤

│    Полученная в результате анализа требований функциональная специ-│

│фикация системы моделирования работы центральных устройств ЭВМ имеет│

│следующий вид.                                                      │

│                                                                    │

│              1.Общие требования к системе                          │

│    1.1.Пользователю должна быть предоставлена возможность выбора  в│

│любой момент работы с программой установки исходных данных,  модели-│

│рования или просмотра накапливаемой статистической информации.      │

│    1.2.При выборе пользователем режима  моделирования  в  начальный│

│момент сеанса работы программа должна по  умолчанию  установить  все│

│требуемые параметры, включая генерацию последовательности  процессов│

│с равномерным распределением.                                       │

│    1.3.Программа должна быть застрахована от некорректных  действий│

│пользователя, указывая ему на то, что необходимо исправить, или осу-│

│ществляя программную корректировку.                                 │

│    1.4.Программа должна сама выяснять тип видеоадаптера  и  осущес-│

│твлять настройку.                                                   │

│    1.5.По желанию пользователя должна быть возможной настройка  ис-│

│пользуемых программой цветов.                                       │

│    1.6.Для единообразия масштабов шкала ординат в гистограммах про-│

│цессов должна быть логарифмической (0, 1, 10, 100, 1000, 10000)     │

│    1.7.В любой момент сеанса работы пользователь должен иметь  воз-│

│можность распечатки накопленной статистической информации.          │

│                                                                    │

│                    2.Установка параметров                          │

│    2.1.Программа должна обеспечивать генерацию или выбор  сохранен-│

│ной последовательности процессов, выбор способа визуализации модели-│

│руемых устройств и стратегий их работы, установку числовых  значений│

│различных параметров.                                               │

│    2.2.Длительность процесса, интервал его порождения по  отношению│

│к предшествующему процессу и  объем  требуемой  памяти  определяются│

│случайными натуральными числами в интервале от 1 до 9.              │

│    2.3.Распределение длительности, интервала порождения и требуемо-│

│го объема памяти для процессов выборки должно  быть  равномерным  по│

│умолчанию или регулируемым при желании пользователя для  каждого  из│

│генерируемых параметров.                                            │

│    2.4.Количество процессов, генерируемых программой для  статисти-│

│ческой выборки, устанавливается пользователем или равно 100 по умол-│

│чанию.                                                              │

│    2.5.Количество процессов, генерируемых программой свыше заданно-│

│го числа выборки, равно десяти по умолчанию. Пять из них  -  началь-│

│ные, с временем порождения, равным нулю, пять - конечные,  с  произ-│

│вольным временем порождения.                                        │

│    2.6.Пользователь по желанию может изменять количество  начальных│

│и конечных процессов.                                               │

│    2.7.Последовательность процессов может сохраняться  при  желании│

│пользователя на протяжении  сеанса  работы  для  изучении  различных│

│стратегий, а также может быть сохранена в базе данных для  последую-│

│щих сеансов работы.                                                 │

│    2.8.Стратегии планирования работы ЦП должны быть следующими:    │

│- стратегии очередей:                                               │

│  - первым пришел, первым обслужен (First In First Out);            │

│- планирование по наивысшему приоритету (Highest Priority First):   │

│  - обслуживание первыми самых кратких (Shortest Job First);        │

│- круговой циклический алгоритм (Round Robin);                      │

│- очередь с обратной связью (Feed Back):                            │

│  - переход в низшую очередь после получения кванта времени ЦП в ре-│

│    жиме кругового циклического алгоритма.                          │

│    2.9.Стратегии распределения ОЗУ должны должны быть следующими:  │

│- с разделами фиксированного размера;                               │

│- с разделами переменного размера;                                  │

│- с перемещаемыми разделами.                                        │

│    2.10.Выбор способа визуализации моделируемых устройств и страте-│

│гий их работы осуществляется пользователем  или  устанавливается  по│

│умолчанию.                                                          │

│    2.11.Объем памяти ОЗУ принимается равным 100  условным  единицам│

│памяти по умолчанию или задается пользователем, но не  более  100  и│

│кратно 10. 10% объема ОЗУ автоматически отводится под ядро  операци-│

│онной системы.                                                      │

│    2.12.При выборе стратегии распределения ОЗУ на разделы  фиксиро-│

│ванного размера количество разделов и объем каждого из  них  опреде-│

│ляется пользователем.                                               │

│    2.13.При изучении стратегий планирования центрального  процессо-│

│ра память ОЗУ должна распределяться  по  умолчанию  на  перемещаемые│

│разделы.                                                            │

│    2.14.При изучении распределения  памяти  ОЗУ  планирование  цен-│

│трального процессора должно реализовываться по круговому циклическо-│

│му алгоритму по умолчанию.                                          │

│                                                                    │

│             3.Моделирование работы центральных устройств           │

│    3.1.Программа должна обеспечивать совместную или раздельную  ви-│

│зуализацию моделирования работы центрального процессора (ЦП) и  опе-│

│ративного запоминающего устройства (ОЗУ)  при  различных  стратегиях│

│планирования и распределения.                                       │

│    3.2.При визуализации моделирования работы одного из  центральных│

│устройств программа должна обеспечивать возможность  работы  другого│

│устройства в соответствии с принятой пользователем или устанавливае-│

│мой по умолчанию стратегией.                                        │

│    3.3.Величина кванта времени предоставления ЦП процессу  в  соот-│

│ветствующих стратегиях планирования  равна  одной  условной  единице│

│времени по умолчанию.                                               │

│    3.4.Работа программы при моделировании должна допускать  автома-│

│тический и пошаговый режимы. Под шагом понимается  единица  времени.│

│Переход от одного режима  к  другому  в  процессе  работы  программы│

│произволен.                                                         │

│    3.5.При изучении стратегий планирования ЦП на экране должна при-│

│сутствовать следующая информация:                                   │

│- время (условные единицы);                                         │

│- процесс - обладатель ЦП;                                          │

│- очереди процессов;                                                │

│- накапливаемая статистическая информация в графической форме.      │

│    3.6.При изучении стратегий распределения ОЗУ  на  экране  должна│

│присутствовать следующая информация:                                │

│- время (условные единицы);                                         │

│- процессы, находящиеся в ОЗУ (в графической форме);                │

│- текущая загрузка ОЗУ в %%;                                        │

│- накапливаемая статистическая информация в графической форме.      │

│    3.7.При изучении совместной работы центральных устройств на  эк-│

│ране должна присутствовать информация согласно п.3.5 и 3.6.         │

│    3.8.Процесс моделирования должен осуществляться вплоть до завер-│

│шения обработки последнего процесса выборки.                        │

│    3.9.Должна быть предусмотрена  возможность  прерывания  процесса│

│моделирования (с подтверждением) и выхода в главное меню программы. │

│    3.10.Каждый процесс во время моделирования должен иметь  следую-│

│щие характеристики:                                                 │

│- последовательный номер ─┐                                         │

│- длительность            │    начальные сведения, генерируемые     │

│- требуемый объем памяти  │    программой                           │

│- время порождения      ──┘                                         │

│- время постановки в очередь (загрузка в ОЗУ);                      │

│- время первого предоставления ЦП;                                  │

│- время завершения обслуживания (время выгрузки из ОЗУ).            │

│    3.11.Накапливаемая статистическая информация для  процессов  вы-│

│борки при изучении стратегий планирования ЦП должна включать:       │

│- длительность процесса;                                            │

│- количество процессов с одинаковой длительностью;                  │

│- суммарный интервал от момента порождения до момента  постановки  в│

│  очередь (загрузки в ОЗУ);                                         │

│- средний интервал от момента порождения  до  момента  постановки  в│

│  очередь (загрузки в ОЗУ);                                         │

│- суммарный интервал от момента постановки  в  очередь  (загрузки  в│

│  ОЗУ) до момента первого предоставления ЦП;                        │

│- средний интервал от момента постановки в очередь (загрузки в  ОЗУ)│

│  до момента первого предоставления ЦП;                             │

│- суммарный интервал обслуживания (время нахождения в ОЗУ);         │

│- средний интервал обслуживания (время нахождения в ОЗУ).           │

│    3.12.Накапливаемая статистическая информация при изучении  стра-│

│тегий распределения ОЗУ должна включать:                            │

│- гистограмму загрузки;                                             │

│- среднюю загруженность памяти.                                     │

│    3.13.Накапливаемая статистическая информация до завершении моде-│

│лирования любой из стратегий работы центральных устройств  по  жела-│

│нию пользователя может быть представлена в числовом виде.           │

│    3.14.Накапливаемая статистическая информация по завершении моде-│

│лирования любой из стратегий работы центральных устройств  по  жела-│

│нию пользователя может быть сохранена в базе данных системы.        │

│                                                                    │

│          4.Просмотр накопленной статистической информации          │

│    4.1.Программа должна обеспечивать просмотр и удаление  накоплен-│

│ной в файлах базы данных статистической информации для любого сохра-│

│ненного в них сочетания стратегий обслуживания ЦП  и  ОЗУ,  а  также│

│возможность просмотра информации для нескольких сочетаний.          │

│    4.2.Пользователю должна быть предоставлена возможность  просмот-│

│ра накопленной статистической информации в  числовом  и  графическом│

│виде.                                                               │

└────────────────────────────────────────────────────────────────────┘

    Полученная функциональная спецификация должна иметь  результатом

функциональную структуру программного продукта.

┌──────┬─────────────────────────────────────────────────────────────┐

│Пример│П4.Функциональная структура системы моделирования ЦП и ОЗУ   │

├──────┴─────────────────────────────────────────────────────────────┤

│                            ╔═══════════╗          ┌───────────┐    │

│                            ║           ║          │           │    │

│                            ║ УСТАНОВКИ ╟──────────┤ Локальная │    │

│                            ║           ║          │           │    │

│                   ┌────────╢режимов мо-║ ┌────────┤ база      ├──┐ │

│                   │        ║           ║ │        │           │  │ │

│                   │ ┌ ─ ─ ─╢делирования╟─│─┐ ┌ ─ ─┤ данных    │  │ │

│                   │        ║           ║ │        │           │  │ │

│                   │ │      ╚═══════════╝ │ │ │    └─────┬─────┘  │ │

│                   │                      │                       │ │

│                   │ │                    │ │ │          │        │ │

│                   │                      │                       │ │

│     ┌───────────┐ │ │      ╔═══════════╗ │ │ │    ┌─────┴─────┐  │ │

│     │           ├─┘        ║           ║ │        │           │  │ │

│     │ База      │   │      ║МОДЕЛИРОВА-╟─┘ └ ┼ ─ ─┤ Модуль    │  │ │

│     │           ├──────────╢           ║          │           │  │ │

│     │ данных    │   │  ┌─ ─╢НИЕ работы ╟ ─ ─ ┼ ─ ─┤ отображе- │  │ │

│     │           │          ║           ║          │           │  │ │

│     │ системы   ├───┼──┼─┐ ║ЦП и ОЗУ   ║     │ ┌ ─┤ ния       │  │ │

│     │           │        │ ║           ║          │           │  │ │

│     └───────────┘   │  │ │ ╚═══════════╝     │ │  └─────┬─────┘  │ │

│                          │                                       │ │

│                     │  │ │                   │ │        │        │ │

│                          │                                       │ │

│     ┌───────────┐   │  │ │ ╔═══════════╗     │ │  ┌─────┴─────┐  │ │

│     │           │        │ ║           ║          │           │  │ │

│     │ Модуль    ├ ─ ┘  │ └─╢ ПРОСМОТР  ╟ ─ ─ ┘ │  │ Модуль    │  │ │

│     │           │          ║           ║          │           │  │ │

│     │ обработки ├ ─ ─ ─┘   ║накопленной║       │  │ визуализа-├──┘ │

│     │           │          ║           ║          │           │    │

│     │ команд    ├ ─ ─ ─ ─ ─╢информации ╟ ─ ─ ─ ┘  │ ции       │    │

│     │           │          ║           ║          │           │    │

│     └─────┬─────┘          ╚═══════════╝          └─────┬─────┘    │

│           │                                             │          │

│           │                                             │          │

│           │  Команды                       Информация   │          │

│           └──────────────                 ──────────────┘          │

│              пользователя                  для экрана              │

│                                                                    │

│                                                                    │

│                ───── - данные;  ─ ─ ─  - управление.               │

│                                                                    │

└────────────────────────────────────────────────────────────────────┘

   !!!!!!!!!!! Дальше пока читать не нужно !!!!!!!!!!!!!!!!

                       3.5.HIPO-технология

         (HIPO - Hierarchical Input Process Output Diagramms)

    Методология HIPO на основе  графических  диаграмм  (IBM)  является

наиболее известной для реализации нисходящего проектирования.  В  этой

методологии предусмотрено три вида диаграмм. Диаграммы первого типа  -

вспомогательные - предназначены для окончательного оформления програм-

мной документации. С помощью  диаграмм  второго  типа,  иерархических,

постепенно проектируется полная структура ПО.

                           ┌────────────────┐

                           │                │

                           │    Монитор     │

                           │                │

                           └────────┬───────┘

                                    │

                                    │

              ┌─────────────────────┼───────────────────┐

              │                     │                   │

           ┌──┴──┐               ┌──┴──┐             ┌──┴──┐

           │  A  │               │  B  │             │  C  │

           └──┬──┘               └─────┘             └──┬──┘

              │                                         │

         ┌─────────┬─────────┐                     ┌────┴────┐

         │         │         │                     │         │

      ┌──┴──┐   ┌──┴──┐   ┌──┴──┐               ┌──┴──┐   ┌──┴──┐

      │ A1  │   │ A2  │   │ A3  │               │ C1  │   │ C2  │

      └──┬──┘   └─────┘   └──┬──┘               └──┬──┘   └─────┘

         │                   │                     │

         ├─────────┐         │                     │

         │         │         │                     │

      ┌──┴──┐   ┌──┴──┐   ┌──┴──┐               ┌──┴──┐

      │ A11 │   │ A12 │   │ A31 │               │ C11 │

      └─────┘   └─────┘   └─────┘               └─────┘

             Рис.3.10. Вариант структуры программного обеспечения.

    Каждый модуль этой диаграммы представляется диаграммой "вход - об-

работка - выход".

                        ┌───────────────────┐

      ┌─────────┐       │   Функции модуля  │       ┌──────────┐

      │ Входные │──────│ 1.................│──────│ Выходные │

      │ данные  │       │ 2.................│       │ данные   │

      └─────────┘       │ 3.................│       └──────────┘

                        └───────────────────┘

                       Рис.3.11. IPO-диаграмма

    Спецификации, составленные с  помощью  метода  HIPO,  представляют

альбом связанных между собой схем, каждая  из  которых  описывает  ка-

кую-либо часть задачи или системы, подлежащей разработке. Чтобы соста-

вить спецификацию данным методом, необходимо  разделить  рассматривае-

мую задачу на части.

    Деление объекта разработки должно осуществляться последовательно и

сверху вниз. Такое деление приводит к построению древовидной  структу-

ры, верхним уровнем которой будет объект в  целом,  а  на  последующих

уровнях все более и более детализируемые его части. При  этом  следует

отметить:

- каждая часть объекта и разложение этой части на следующем уровне не

  обязательно эквивалентны. Некоторые детали, достаточно понятные, мо-

  гут не подвергаться дальнейшему разложению;

- разложение каждой части объекта не зависит от разложения других час-

  тей.

    Разложение системы на части выполняется по функциональному призна-

ку. Это означает, что каждая выделяемая  часть  должна  описывать  ка-

кую-либо законченную содержательную функцию, а  методы  и  особенности

реализации не должны учитываться при разложении.

                      3.6.Структурный анализ (SA)

          (SADT - Structured Analysis and Design Technique)

    Систему SADT можно использовать уже при определении требований  ко

всей системе в целом. Она полезна также на следущем этапе при  состав-

лении спецификации и на дальнейших, где производится  детализация.  На

этих этапах осуществляется тесное взаимодействие между уровнем  проек-

тирования логики, на котором должна быть разработана структура  компо-

нентов, и спецификацией этих компонентов.

    Система SADT основана на концептуальном  различии  между  функцио-

нальной архитектурой и архитектурой системы. Функциональная архитекту-

ра в точности отражает те действия, которые выполняет  система,  и  те

объекты, с которыми она взаимодействует.

    Составление представлений об объектах  и  действиях  на  различных

уровнях абстракции и их последующее  объединение  с  помощью  соответ-

ствующих связей в функциональную архитектуру является задачей  систем-

ного аналитика. Результат этого анализа лучше  всего  представлять  не

только в виде словесного описания,  но  и  в  виде  графических  схем.

Использование в SADT графических методов является  принципиальным  мо-

ментом. Графический язык SADT представляет ограниченное число  базовых

элементов, которые могут использоваться аналитиками и  проектировщика-

ми для составления упорядоченных структур любой размерности (рис.2.12).

    Этими базовыми элементами являются блоки и стрелки. Блок  соответ-

ствует части целого, а  стрелка  соответствует  связи  между  частями.

Блок-схема соответствует целому, состоящему из блоков, стрелок, наиме-

нований на принятом языке и прочих описаний. Модель в  SADT  представ-

ляет собой  последовательность  блок-схем  с  соответствующим  каждому

уровню текстом. На следующем, более высоком уровне, вся эта  структура

представляется в сокращенном виде. В SADT модель является  графическим

представлением иерархической структуры системы, которую можно  развер-

тывать до любого требуемого уровня детализации.

              Государственный Комитет Российской Федерации                         по высшему образованию             Саратовский государственный технический университет            Т Е Х Н О Л О Г И Я     П Р О Г Р

 

 

 

Внимание! Представленная Работа находится в открытом доступе в сети Интернет, и уже неоднократно сдавалась, возможно, даже в твоем учебном заведении.
Советуем не рисковать. Узнай, сколько стоит абсолютно уникальная Работа по твоей теме:

Новости образования и науки

Заказать уникальную работу

Похожие работы:

Типовые расчеты надежности систем на персональном компьютере
Информационные системы в экономике
Объективное программирование
ЛИСП
Методическая разработка по C++
Описание языка Turbo Basic для студентов всех специальностей
Обучение начальных курсов методам программирования на языке Turbo Pascal
Структура и реализация макроязыков
Информационные технологии в экономике. Разработка информационных технологий.
Информационные технологии в экономике. Средства организации экономико информационных систем

Свои сданные студенческие работы

присылайте нам на e-mail

Client@Stud-Baza.ru