автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.11, диссертация на тему:DROL-язык спецификации для задач вычислительной геометрии

РГБ ОД

22 МАЙ 15С5

СХНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

На правах рукописи

Бухвалова Вера Вацлавовиа

ШЮЬ — ЯЗЫК СПЕЦИФИКАЦИИ ДЛЯ ЗАДАЧ ВЫЧИСЛИТЕЛЬНОЙ ГЕОМЕТРИИ

05.13.11 — Математическое и программное обеспечение вычислительных машин, комплексов, систем и сетей

АВТОРЕФЕРАТ диссертации на соискание учёной Степени кандидата физико-математических наук

Санкт-Петербург 1995

Работа выполнена на кафедре исследования операций математико-механического факультета Санкт-Петербургского государственного университета.

Наумшй руководитель: доктор физико-математических наук,

профессор И.В. Романовский

Официальные оппоненты: доктор физико-математических наук,

профессор А.Н. Терехов кандидат физико-математических паук, доцент В.Л. Кобельский

Ведущая организация: Санкт-Петербургское отделение Математического института им. В.А. Стеклова РАН

Защита диссертации состоится « ^ » 1995 г.

в 4'/ ^часов на заседании диссертационного совета К 063.57.54 по присуждению учёной степени кандидата физико-математических наук в Санкт-Петербургском государственном университете по адресу: 198904, Санкт-Петербург, Старый Петергоф, Библиотечная пл. 2.

С диссертацией можно ознакомиться в Научной библиотеке Санкт-Петербургского государственного университета по адресу: г. Санкт-Петербург, Университетская набережная, д. 7/9.

Автореферат разослан « /О » р/( 0 ^ 1995 г.

Учёный секретарь диссертационного совета,

доцент • Б.К. Мартыненко

Общая характеристика работы

Актуальность темы. Одной из важных проблем информатики является разработка методологий создания программного обеспечения (ПО), которые позволили бы одновременно повысить производительность программистского труда и качество программного продукта. Среди инструментальных средств, которые могут использоваться при различных методологиях создания ПО, всё более широкое применение получают языки спецификации (ЯС). Создание ЯС стало самостоятельной областью методологии программирования.

Наряду с универсальными создаются специализированные ЯС, предназначенные для написания проектов программ в конкретной предметной области. Одним из разделов прикладной математики, для которого актуально создание своего Я С, является вычислительная геометрия1.

Цель работы. Основная цель работы — создание языка спецификации DROL для описания геометрических построений на плоскости и записи алгоритмов вычислительной геометрии.

Методы исследования. При выборе структуры и элементов языка DROL использовались методологические подходы, которые применялись при разработке ЯС для других классов задач.

Научная новизна. В результате проведённого исследования доказана целесообразность и практическая ценность единого ЯС для описания геометрических построений на плоскости и задач вычислительной геометрии. Предлагаемый подход позволяет реализовывать этот язык как расширение практически любого универсального ЯГ1

1Так как это название до слх пор испальчустси а различных смыслах, отметим, что речь идёт о дисциплине, названной так М. Шейчосом (SUamrw M.I. Geometric complexity // Prot. 7th ACM Annu. Symp. Theory Comput., May I97Ü, p. 221-233)

сперацчонного или объектно-ориентированного типов.

С помошью созданных на языке 0Я01_ спецификаций проведена классификация алгоритмов решения задачи прямоугольного раскроя, охватывающая как большинство существующих эвристических алгоритмов, так и точные алгоритмы, рассматриваемые в этой работе. В частности, удалось доказать, что два наиболее популярных эвристических алгоритма являются частными случаями одного алгоритма, описываемого в терминах, введённых автором.

Практическая ценность. Практическая ценность работы определяется использованием её результатов в научных исследованиях и учебном процессе. В частности, разработаны оснозы методологии использования язык;* 0(Ю1. для записи алгоритмов решения задач планиметрии, аналитической геометрии, вычислительной геометрии. Результаты работы используются автором при чтении спецкурса „Вычислительная геометрия" на математико-механическом факультете СИбГУ. На основе результатов работы под руководством автора выполнен ряд дипломных работ по проблемам вычислительной геометрии и их программной реализации — п частности, работы [3, 10] являются совместными публикациями с дипломниками.

Апробация работы. Основные результаты диссертации докладывались на Всесоюзном семинаре „Математическое обеспечение расчётов линейного и прямоугольного раскроя" (Уфа, 1980), на Всесоюзной конференции „Методы и средства обработки сложноструктурированной информации" (Горький, 1983), на Всесоюзной научно-технической конференции „Общесистемное программное обеспечение для САПР" (Калинин, 1985), на Всесоюзной конференции „Математическое обеспечение рационального раскроя в системах автоматизированного проектирования" (Уфа, 1987), а также на

семинарах кафедры и лаборатории исследования операций СПбГУ, кафедры технологии и конструирования швейных изделий ЛИТЛП, секции инженерной графики и автоматизированного проекшропання Петербургского Дома учёных.

Доклад автора о созданном им ПО дня задач прямоугольного раскроя был включён в программу ORSA/TIMS Joint National Meeting, San Francisco, November 1-4, 1992. Доклад автора на тему A Specification Language for Rectangular Cutting Stock Problem включён a программу TIMS XXXIII International Conference, Singapure, June 25-28, 1995.

Публикации. По теме диссертации опубликовано 12 работ, которые отражают её основное содержание.

Структура и объём работы. Диссертация состоит из вьеде-иия, трёх глав, списка использованной литературы и трёх приложений. Диссертация содержит 132 страницы машинописного текста (в том числе, основная часть — 110 стр.) и 12 рисунков. Список литературы включает 80 наименований.

Содержание работы

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

Глава 1 посвящена обоснованию структуры проблемно-ориен-тировьлного языка спецификации DROL и изложению его общей характеристики. В разделе 1.1 содержится обзор концепций и понятий современного программирования, непосредственно связапных с темой работы: структурное программирование, сборочное програм-

-с-

миронание, объектно-ориентированное программирование, язык спецификации, средства абстракции, машинная графика и графические языки.

В разделе 1.2 приведена общая характеристика геометрического языка спецификации DROL. На выбор структуры и синтаксиса языка наибольшее влияние оказали языки программирования Algol 68, ClU, Pascal и язык проектирования программ PDL. Основная цель, которая ставилась при выборе структуры языка, — поддержать одновременно технологию структурного и сборочного программирования и использование различных видов абстракции.

Программа на языке DROL состоит из одного или нескольких модулей и набора определений или спецификаций вподи.мых автором программы типов данных. Модуль является одним из видов подпрограммы (процедурой, функцией, операцией), итератором или абстрактным типом данных (АТД). Назначение модуля и АТД в записи абстракции соответствующего типа. Так как DROL является ЯС, для каждого типа модуля и АТД определены две формы представления: спецификация и описание.

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

В разделе 2Д приведены формы записи спецификаций модулей и пример спецификации АТД. Раздел 2.2 содержит описание простых геометрических типов данных (ПГТ) в форме спецификаций соответствующих им неизменяемых А.ТД. В соответствии с традицией геометрических языков программирования, имеются следующие ПГТ: point (точка), direction (направление), ray (луч), angle (угол), line (прямая), orientation (ориентация), circle (окруж-

ность), line.seg (отрезок), агс(дуга). С каждым ПГТ связана группа действий, посредством которых можно работать с объектами этого , типа. Среди этих действий отсутствуют средства прямого доступа к координатному представлению объектов. Это сделано с целью побудить пользователя описывать геометрические построения в терминах геометрических объектов и действий. Приведём пример использования объектов ПГТ при описании простейших геометрических построений. Ниже следует фрагмент текста на языке DROL, в котором определяются вершины и медиана прямоугольного треугольника (рис. 1). Текст демонстрационной программы, реализующей этот фрагмент, приведен в приложении 2. poiat А « origin;

{точка А расположена а начале координат}

point В » up A on L;

{точка В выше точки А на L}

гау R * 8 dir cr(2»pi - alpha));

{луч Я, выходящий нэ точки В под углом 2*pi-alpha

к осп абсцисс) point С * rt A intersect R; {точка С - пересечение горизонтального луча иэ точки А и луча Н> point М ».Biddle(B.C); {точка М - середяна отрезка ВС} line.seg S « сг(А,М); {отрезок S образован точками А я Ю

В разделе 2.3 обсуждаются имеющиеся в языке способы структурирования даниых: массив, запись, миожество, ломаная, сегмент. На тип элементов массива, записи и множества не накладывается никак.ix ограничений. Ломаная и сегмент используются для организации вывода изображений на графическое устройство. Над сегментом определены операции формирования сегмента и процедуры геометрических преобразований, включённые в стандарт GKS: перенос, вращение, изменение масштаба.

В разделе 2.4 обсуждаются способы организации вычислений внутри модуля. Набор операторов, имеющихся в языке, традиционен для популярных языков программирования: оператор присваивания, оператор вызова процедуры, условный оператор, оператор выбора, различные виды оператора цикла, специальные операторы управления (break, continue, return). Для вызова итератора предусмотрена специальная форма оператора lor.

Раздел 2.5 содержит описание'имеющихся типов подпрограмм (процедура, функция, операция) и формулы записи их определений. Для подпрограмм разрешён полиморфизм. Способы определения типов данных описаны в разделе 2.6. В качестве примера приведём два описания г.олиморфпой функции sym:

function sym « (point a, с) peint: (Создаёт точку, синиетричму» точке а относительно топки с} begin Teturn( betwe«n(»,c,2); end;

function ауч » (point a; line 1) peint: {Создает точку, cnKMSTpipnry» точке а относительно пряной 1} begin

point b - » perp 1 intesect 1;

{точка b - проекция точки а па прямуя 1} return(вуп(а,Ь)); end;

В разделе 2.7 рассказано о применении языка DROL как языка конструктора одежды (5. 6].

В разделе 2.8 обсуждаются особенности реализаций языка DROL на. базе различных языков программирования [1, 2, 3, 4, 10]. Приложение 1 содержит текст реализации на языке Turbo Pascal 7.0.

В главе 3 на примере задачи прямоугольного раскроя рассматривается использование языка DROL как ЯС для записи алгоритмов вычислительной геометрии.

Раздел 3.1 содержит описание алгоритма В.А.Залгаллера для задачи составления постава для распиловки брёвен и его спецификацию на языке DROL. Реализация этого алгоритма на языке Turbo Pascal приведена в приложении 3,

Раздел 3.2 содержит постановку задачи прямоугольного раскроя в полуполосе и обзор существующих алгоритмов её решения.

Рассматривается задача раскроя (ЗПР) в следующей постановке. На плоскости имеется бесконечная полуполоса G. Задан набор R из N замкнутых прямоугольников, стороны которых параллельны осям координат. Требуется разместить эти прямоугольники в полосе без пересечений по внутренним точкам и без изменения их ориентации так, чтобы длина занятой части нолуполосы была минимальна. Так как ЗПР является ./VP-полной, возник интерес к построению приближённых алгоритмов её решения, имеющих хотя бы полиномиальную сложность. Дая многих из этих алгоритмов доказаны

строгие оценки их поведения в худшем случае (U). На оцеику U существенно влияет предварительное упорядочивание прямоугольников по убыванию размеров одной из сторон. Многие из эвристических алгоритмов являются модификациями двух алгоритмов, названных в литературе соответственно нижний левый (НЛ-алгоритм) и первый подходящий с упорядочиванием по убыванию длины (ППУД-алгоритм). НЛ-алгоритм, при условии предварительпого упорядочения прямоугольников по убыванию ширин, имеет оценку U — 3. Для ППУД-алгоритма известно, что его оценка U < 2.7. Лучший из эвристических алгоритмов, базирующихся на объединении возможностей НЛ- и ППУД-алгорнтмов, называется уровневий с расщеплением и имеег оценку U < 2.5.

В разделе 3.3 изложен метод зов — новый подход к решению ЗПР, предложенный в конце 1980-х годов А.И. Липовецким. Этот подход позволил сформулировать ЗПР как комбинаторную задачу, у которой существует' оптимальное решение, обладающее рядом специальных геометрических свойств.

Зоной прямоугольника, размещенного на плоскости, называется открытый левый квадрант, построенный из его верхней правой вершяиы. А.И,Липовецким впервые были доказаны следующие два утверждения, связанные с этим понятием.

Предложение 1. При любом допустимом размещении прямоугольников на плоскости существует такая их нумерация, что любой прямоугольник не пересекается с зонами прямоугольников, предшествующих ему в смисле этой нумерации.

Предложение 2. Чюбое допустимое размещение прямоугольников на плоскости можно преобразовать таким образом, чти дли-

на размещения не увеличится, а нижняя левая вершина любого прямоугольника будет находится в самой нижней из возможных то-•чек на границе объединения зон прямоугольников, предшествующих этому прямоугольнику в смысле нумерации из предложения 1.

Имеется несколько различных доказательств предложения 1. Б работе приведено доказательство, принадлежащее автору. Использованный в нём метод — сопоставление размещению орграфа и доказательство отсутствия в этом орграфе контуров — был позже применён А.И.Липовецким для доказательства аналогичного утверждения в случае некоторых типов непрямоугольных фигур. Из сформулированных утверждений следует, что для нахождения размещепия, имеющего минимальную лишу, достаточно перебрать не более ЛП размещений, удовлетворяющих условию из предложения 2 при каждой нумерации. Этот перебор может быть значительно сокращён, если учесть свойстьа, которыми обладают оптимальные размещения. Например, достаточно рассматривать только плотные размещения (невозможен сдвиг прямоугольников влево и вниз). Можно перебирать не все N1 нумераций, а только их половину, так как симметричным нумерациям соответствуют симметричные размещения. Всего в разделе 3.3 сформулированы и доказаны 9 правил сокращения перебора.

В разделе 3.4 проведён сравнительный анализ НЛ-алгоритма, ГШ УД- ал го ри тм а и точного алгоритма, основанного па методе зоп. На основе этого анализа выделены две общие абстракции, используемые в них: заготовка и ступень. Заготовками пазваны прямоугольники, которые должны быть размещепы. Ступени — это прямоугольники, объелинепием которых является область для размещения заготовок. Алгоритм определяется выбором ступени, па которой происходит размещение очередной заготовки, и разбиением на сту-

пени области размещения. Формальные определения этих понятий даны в виде абстрактных типов данных, имеющих общего предка (прямоугольник). Приведено также определение абстрактного типа данных, соответствующего понятию ЗПР.

На базе определённых абстрактных типов в разделе 3.5 проведён сравнительный анализ рассматриваемых эвристических алгоритмов Данный подход иозволил выявить и доказать, что IIJ1-алгоритм и ППУД-алгоритм являются частными случаями одного алгоритма, имеющего оценку 0(jV2). Этот алгоритм назван ЛПС-алгорптм (левая подходящая ступень). Раздел 3.5 содержит также тексты реализаций рассматриваемых алгоритмов, в которых используются введённые абстрактные типы.

На базе спецификаций, описанных в разделах 3.4 и 3.5, была создана программа cut решения ЗПР на языке Pascal. В разделе 3.6 приведена спецификация этой программы и временные характеристики различных её версий. В 1992 году на конференции SICUP (Special Interest Group on Cutting and Packing) наряду с другими программами демонстрировалась программа cut (версия 5.0), Сообщений о программах с лучшими характеристиками получено не было.

Основные результаты

Основные результаты, полученные в диссертации, состоят в следующем:

1. Разработан язык спецификаций DROL для описания геометрических построений на 1лоскости и записи алгоритмов вычислительной геометрии.

2. Разработаны основы методологии использования этого языка для записи алгоритмов решения задач планиметрии, аналитической геометрии, вычислительной геометрии.

3. Впервые реализованы новые точные алгоритмы комбинаторного типа для решения задачи прямоугольного раскроя.

4. С помощью созданных на языке DROL спецификаций проведена классификация алгоритмов решения задачи прямоугольного раскроя, охватывающая как большинство существующих эвристических алгоритмов, так и точные алгоритмы, рассматриваемые в этой работе. В частности, удалось доказать, что два наиболее популярных эвристических алгоритма являются частными случаями одного алгоритма, описываемого в терминах, введённых автором.

Работы автора по теме диссертации

[1] Бухвалова В.В. Геометрическое моделирование на Алголе-68 // Вс. семинар „Математическое обеспечение расчётов липейно-го и прямоугольного раскроя" (Уфа, 22-27 июня 1980 г.): Материалы семинара. — Уфа, 1981. — С. 150-154.

[2] Бухвалова В.В. Геометрический язык DROL как средство представления и хранения графической информации // I Вс. конф. „Методы и средства обработки сложноструктурированной, семантически насыщенной графической информации" (сентябрь 1983 г.): Тезисы докладов. — Горький, 1983. — С. 150.

[3] Бухвалова В.В., Дуровин Д.И. Диалоговая система формирования и корректировки карт раскроя //I респ. конф. моло-

дых учёных „Применение ЭБМ в решении научно-технических и народно-хозяйственных задач": Тезисы докладов. — Уфа, 1985.

— С. 86.

[4] Бухвалова D.B. Универсальный геометрический язык DROL и его применение в САПР // Вс. н.-т. конф. „Программные средства как продукция производственно-технического назначения". Секция „Общесистемное программное обеспечение САПР": Тезисы докладов. — Калинин, 1985. — С. 56-58.

[5] Бухвалова В.В. Геометрический яллк для конструирования одежды /'/ Известия вузов. Технология лёгкой промышленности.

— 198G. — №4. — С. 132-138.

[6] Бухвалов A.B., Бухвалова В.В. Организация единого цикла „конструирование-производство" в швейной промышленности // Экономические проблемы управления промышленным производством: Межвуз. сборник. — Л.: ЛФЭИ, 1987. — С. 46-50.

[7] Бухвалова В.В., Сгукалова И.П. Система вывода сложных изображений на АЦПУ // Выч. техника и вопросы кибернетики (Ленинград). — 1987. — №24. — С. 95-99.

[8] Бухвалова В.В. Реализация метода зон Липовецкого для прямоугольного раскроя // Вс. н.-т. конф. „Математическое обеспечение рационального раскроя в САПР" (Уфа, 15-18 июня 19S7 г.): Тезисы докладов. — Уфа, 1987. — С. 24-25.

[9] Бухвалова В.В. Использование язык а геометрического моделирования в прямоугольном раскрое // Математическое обеспечение рационального раскроя в САПР: Материалы конференции. — Уфа, 1988. — С. 80-87.

[10] Бухвалбва,В.В., Загорская Н.М. Применение графического пакета на Паскале к задачам обработки изображений // Применение ЭВМ в решении научно-технических и народнохозяйственных задач: Тезисы докладов. — Уфа, 1989. — С. 38.

[11] Бухвалова В.В., Одинцова Т.В. Схема перебора для задачи прямоугольного раскроя // Математическое моделирование в технологии машиностроения: Сборник научных трудов. — Свердловск: УрО АН СССР, 1989. — С. 100-107.

[12] Bukhvalova V.V. Abstracts of Papers // SICUP - Bulletin, no.8, May 1992. — pp. 2-3.

Подписано к печати 5.Co.95.

Формат 6СхУ0 1/16. Печать офсетная,

Пзч.л.1,0. Тир.-л 100 экз. Заказ №171.

F-ТП СП5ГИЭЛ. 191002, С.-Петербург, ул.«арата,31.