Технология разработки программного обеспечения

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

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

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

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

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

для студентов специальности 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 неделя семестр │

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

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

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

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

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.В одном окне возможн работ c несколькими деталями.

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.Символьная обработка. Вы должны определить то, какима образома прог-

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

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

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

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

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

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; │

│ 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.Уровни пользователей ПО

Можно выделить три квалификационные категории пользователей, кото-

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

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

ти применения ЭВМ, способные разрабатывать базовые методы, средств и

оснащение ПО, общесистемное ПО, инструментальные и технологические

средства, осуществлять генерацию и настройку ПО на условия конкретного

применения.

Ко второму - те, кто хорошо знает тонкостиа построения системы и

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

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

гут разрабатывать специализированное ПО, используя общесистемное ПО.

К третьему относятся пользователи, работающие в системе c помощью

ориентированного на них языка взаимодействия. Процесса работы ва этом

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

нию расчетов, анализу результатов и принятию решений.

2.2.2.Психофизиологические особенности взаимодействия

человека и ЭВМ

ЭВМ дополняет человека, но не заменяет его, поэтому рассмотрение

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

Л о г и ч е с к и й м е т о д р с с у ж д е н и я. У челове-

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

ражения. Метод ЭВМ строгий и систематический. Наиболее удачным являет-

ся сочетание когда ЭВМ реализует отдельные расчетные процедуры, их

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

проектируемого объекта.

С п о с о б н о с т ь к о ба у ча еа на и ю. Человека обуча-

ется постепенно, степень "образованности" ЭВМ определяется ее програм-

мным обеспечением. Желательно, чтобы количество информации, получае-

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

бованию пользователя.

О б р щ е н и е с и н ф о р м ц и е й. Емкость мозг че-

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

дает интуитивной, неформальной возможностью ее организации. Эффектив-

ность вторичного обращения к памяти зависит от времени. В ЭМа емкость

памяти большая, организация формальная и детализированная, вторичное

обращение не зависит от времени. Поэтому целесообразно накапливать и

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

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

О ц е н к и н ф о р м ц и и. Человек меет хорошо разделять

значимую и несущественную информацию. ЭВМ таким свойством не обладает.

Поэтомуа должн существовать возможность макропросмотр информации

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

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

О т н о ш е н и е к о ш и б к м. Человека часто допускает

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

ния ошибок чаще всего также интуитивный. ЭВМ, наоборот, не проявляет

никакой терпимости к ошибкам и метод обнаружения ошибок строго систе-

матичен. Однако в области формальныха ошибока возможности ЭМа значи-

тельно больше, чем при обнаружении неформальных. Поэтому нужно обеспе-

чить возможность пользователю вводить в ЭВМ исходную информацию в сво-

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

ким выражениям и к разговорной речи. ЭВМ выполняет контроль и преобра-

зование информации к стандартному виду, добному в процедурах обработ-

ки и формального странения ошибок. Затем желательно обратное преобра-

зование этой информации для показа пользователю в наглядной, например,

графической форме, для обнаружения смысловых ошибок.

О б р щ е н и е с о с л о ж н ы м и о п и с н и я м и.

Человеку трудно воспринять большое количество информации. Поэтому сле-

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

носительно независимые части, охватываемые одним взглядом. Естествен-

но, что изменения, сделанные в одной из этих частей, должны автомати-

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

с п р е д е л е н е в н и м н и я н н е с к о л ь -

к о з д а ч. Выполнить это словие человеку, в основном, не да-

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

чи. Поэтому в ЭВМ организована систем прерываний, восстанавливающая

состояние основной задачи к моменту, нужному для пользователя. Анало-

гичным образом ЭВМ обслуживает процедуру анализа несколькиха вариантов

решения.

П м я т ь п о о т н о ш е н и ю к п р о в е д е н н о й

р б о т е. Человек может забыть как то, что же сделано, так и то,

что ему запланировано еще сделать. Этот недостаток компенсируется ЭВМ,

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

цедурах и предстоящей работе.

С п о с о б н о с т ь к с о с р е д о т ч и в н и ю. Эта

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

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

Усталостью обуславливается рассеянность, длинениеа реакций, нецеле-

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

ниема времени должн адаптироваться к времениа реакции отдельного

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

Т е р п е н и е. При многократном повторении одних и тех же дейст-

вий человек может испытывать чувство досады. Поэтому предусматривает-

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

анализе этих данных. К этому же относится включение в системы макроко-

манд или гибкие сценарии.

С м о ч у в с т в и е. ЭВМ должна беречь самочувствие пользова-

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

но машина его обслуживает, не наоборот. Вопросы, ответы и замечания

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

лем, определяющим ход и направление процесса проектирования.

Э м о ц и о н а л ь н о с т ь. Это чувство свойственно человеку и

чуждо ЭВМ. ПО должно возбуждать у пользователя положительные эмоции и

не допускать отрицательных.

2.3.Классификация ПО и количественные характеристики

В основу первой классификации может быть положен объема ПО, выра-

жаемый числом исходных команд (ЧИК). Этот термин -а исходныеа команды,

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

ботанные в машинный код с помощью препроцессоров, компиляторова и ас-

семблеров. Исходные команды не включают комментарии и штатное ПО, но

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

описание.

Исходя из числа исходных команд (ЧИК)а можно классифицировать ПО

следующим образом по размеру:

Малый........... 2 ЧИК

Промежуточный... 8 ЧИК

Средний......... 32 ЧИК

Большой.........128 ЧИК

Введем следующие обозначения. Будема считать, что человеко-месяц

(ЧМ) состоит из 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а проектова разра-

ботки ПО для разных типов ЭВМ, разных объемов, разного назначения, ис-

пользуюшего различные языки программирования.

Второй характеристикой для классификации ПО можета служить качес-

твенная оценка. Различают три типа ПО: распространенный, полунезависи-

мый и встроенный.

с п р о с т р н е н н ы й тип характеризуется тем, что ПО

разрабатывается относительно небольшой группой специалистова ва сло-

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

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

организации.

Это означает, что большинство частников проекта могута са пользой

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

ладных расходов на обмен информацией о сущности проекта.

В проекте распространенного тип налагаются относительно менее

жесткие ограничения на соответствие ПО требованиям и спецификациям ин-

терфейса.

Другими характерными чертами По распространенного тип являются

следующие:

- стабильные словия разработки проекта;

- минимальная необходимость новых системных и алгоритмических реш� 503 Service Unavailable

Service Unavailable

The server is temporarily unable to service your request due to maintenance downtime or capacity problems. Please try again later.