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

ВВЕДЕНИЕ.

1 ИССЛЕДОВАНИЕ ПРОЦЕССА АЛГОРИТМИЗАЦИИ ЗАДАЧ СТРУКТУРНОГО СИНТЕЗА И ПОСТАНОВКА ЗАДАЧИ.

1.1 Анализ основных этапов процесса решения задачи структурного синтеза.

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

1.3 Автоматическая генерация описаний структур данных.

1.4 Анализ вычислительной и емкостной сложности алгоритмов.

Выводы.

2 РАЗРАБОТКА ЯЗЫКА ОПИСАНИЯ АЛГОРИТМОВ СТРУКТУРНОГО СИНТЕЗА И ТРАНСЛЯТОРА С НЕГО.

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

2.2 Анализ алгоритмов решения задач на графах и определение совокупности операций над абстракциями, используемыми для их описания.

2.3 Определение синтаксиса и семантики конструкций языка.

2.4 Выбор механизма (способа) трансляции.

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

Выводы. 3 РАЗРАБОТКА СРЕДСТВ ОЦЕНКИ И КЛАССИФИКАЦИЯ СПОСОБОВ

СНИЖЕНИЯ ВЫЧИСЛИТЕЛЬНОЙ СЛОЖНОСТИ АЛГОРИТМОВ.

3.1 Оценка вычислительной сложности по описанию на языке и разработка анализатора.

3.2 Оценка временной сложности с учетом реализации множеств.

3.3 Классификация способов снижения вычислительной сложности и ф выработка рекомендаций по их применению.

Выводы. 4 ОПИСАНИЕ АВТОМАТИЗИРОВАННОЙ СИСТЕМЫ РАЗРАБОТКИ * АЛГОРИТМОВ И ПРИМЕРЫ ЕЕ ИСПОЛЬЗОВАНИЯ.

4.1 Структура автоматизированной системы разработки алгоритмов.

4.2 Разработка транслятора.

4.3 Разработка макрогенератора описаний абстракций объектов.

4.4 Методика разработки алгоритмов с использованием средств ф автоматизации.

4.5 Пример - последовательный алгоритм разрезания гиперграфа схемы.

4.6 Пример - уравновешенная двоичная свертка без учета связности.

Выводы.

ВЫВОДЫ.

Актуальность. Задачи структурного синтеза решаются при разработке структуры практически любых объектов на всех этапах проектирования. К этому типу задач относятся, например, многие задачи проектирования ЭВМ, телекоммуникационных систем и сетей, а также задачи оптимизации транспортных потоков, причем количество подобных задач постоянно увеличивается. С развитием прикладных и фундаментальных наук задачи, связанные с исследованием и синтезом структур, ставятся, например, в таких далеких от техники областях, как химия и биология.

В большинстве случаев задачи структурного синтеза - это задачи большой размерности (более 50 тыс. элементов), кроме того, многие из них принадлежат к классу задач с экспоненциальной оценкой вычислительной сложности [7, 8, 9, 17, 19, 26, 27, 28], точное решение которых невозможно даже на современных ЭВМ по причине неприемлемых временных затрат. В настоящее время для решения таких задач используют приближенные методы и алгоритмы, которые требуют различных вычислительных ресурсов и обеспечивают разную точность решения.

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

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

Широкое распространение, многообразие постановок задач структурного синтеза и высокая трудоемкость разработки алгоритмов решения этих задач делают актуальной автоматизацию процесса разработки алгоритмов их решения. Это подтверждается увеличившимся интересом к разработке и исследованию алгоритмов решения задач структурного синтеза в отечественной и иностранной литературе [2, 7, 8, 27,29,37, 39, 40].

Автоматизировать творческий процесс разработки моделей, метода решения ^ задачи и формального описания алгоритма невозможно. Однако при получении и исследовании моделей и алгоритмов разработчик оперирует понятиями и терминами ^ теории графов, теории множеств и математической логики. Создание на этой основе f специализированного языка описания алгоритмов и данных позволит автоматизировать разработку алгоритмов на этом уровне представления.

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

Вычислительная и емкостная сложность алгоритма существенно зависят от используемых структур данных. Отсюда возникает проблема выбора представления графовых моделей в виде структур данных. Целесообразно разрешить разработчику описывать требуемые реализации, следовательно, необходимо решить задачу автоматической генерации описаний структур данных на универсальном языке по метаописанию на языке описания алгоритмов. ф Поскольку после получения алгоритма необходимо выполнять оценку рь вычислительной и емкостной сложности полученных преобразований, на основе которой может проводиться его доработка, актуальной является проблема создания методики автоматического получения оценок и средств ее реализации. Более того, # наличие языка описания алгоритмов позволяет поставить задачу оценки не только вычислительной, но и временной сложности программы, что позволит уточнить результаты оценок.

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

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

Для достижения указанной цели в работе поставлены и решены следующие задачи:

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

2. Определение синтаксиса и семантики языка формального описания алгоритмов и разработка транслятора с него.

Ф 3. Обеспечение автоматической генерации описаний выбранных структур данных и реализации операций над ними.

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

5. Создание программной системы разработки и анализа алгоритмов. Методы исследований. При решении задач были использованы: методы теории графов, теории множеств, математической логики. Методика оценки ф вычислительной сложности базируется на методе Д-карт, ориентированном на структурный подход в программировании. При разработке языка используются теория формальных языков и методы грамматического разбора. Научная новизна работы.

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

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

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

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

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

6. Предложена методика разработки алгоритмов решения задач структурного синтеза.

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

Апробация работы. Основные положения диссертационной работы обсуждались на Студенческой научной конференции «Информатика и системы управления в XXI веке» (г. Москва 2003), Международной научно-технической конференции «Гражданская авиация на современном этапе развития науки, техники и общества» (г. Москва 2003), Первой международной научно-технической конференции «Аэрокосмические технологии» (Москва-Реутов 2004).

Реализация и внедрение. Теоретические и практические результаты работы, полученные автором, нашли применение для решения задачи синтеза схемы "DACT' реляционной базы данных "VAO" в Информационном центре Управления внутренних дел Восточного административного округа г. Москвы и анализа структуры предприятия ОАО «Гидрометприбор». Документы, подтверждающие внедрение, приведены в приложении.

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

Объем и структура диссертации. Диссертационная работа состоит из введения, четырех глав, заключения, списка литературы, приложения, занимающих 133 страницы текста, в том числе 20 рисунков и 21 таблиц на 53 страницах, список использованной литературы из 51 наименований на 5 страницах.

ВЫВОДЫ

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

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

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

4. Синтаксис языка приведен к операторной грамматике, являющейся подклассом 1Л?(А:)-грамматик. Техника разбора основана на отношениях предшествования, соответственно, была построена матрица предшествования. Распознаватель реализует восходящий детерминированный анализ слева направо, производя правый разбор.

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

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

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

8. Разработаны средства автоматизации, интегрированные в систему разработки и анализа алгоритмов решения задач структурного синтеза. Основными компонентами системы являются: специализированный текстовый редактор; генератор классов, реализующих структуры данных; транслятор с языка описаний алгоритмов на язык Delphi Pascal, анализатор вычислительной сложности; анализатор емкостной и временной сложности.

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

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

127

Включение ■ Строгое включение

Min/max

Malti

Card

Sort

SlI

03 ЧО CD та Е к с | ю Я о а та та п> я н к та л> 2

2 ес о * п> о н к о го < q. ш X m X тг X тг и" X

7Г

С о V m со ф д. g.Q.Q.®"P М

- ■ - ■ ЛОХ v ^ -о

П|

5'Я ф х ГЗ Ж"

Q. СП "' =? п> ф ф я s s? о со

It ш » L- 0)

5?

F3 fo м Р Л о й (Ц ю м (D (л =3 x

7Г п> о— ф ii со

5? 5 тг (л

IS

А || <Q =; Н

3" § 5'«

7г cd

8 2.4 s. q) ф

I? л сп

О X ф ф с

О s

3 ш о а Ф н со я> г?

3 СП

CD " ■ ш

F3

CD ф & ® тэ 3.

2 ■о

0 с 8

01 гн.

5 5< и о ф ф

3 ф а и о

II ТГ; ~ II 2

О ф ф 3 ф э от тз я та s п о * w я о о н сг н в о\

§ s я о я о X л

SS as в

1. Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. -М.: Мир, 1979. 536 с.

2. Ахо А.В., Хопкрофт Дж., Ульман Дж. Структуры данных и алгоритмы: Пер. с англ. М.: Издательский дом «Вильяме», 2003. - 384 с.

3. Вирт Н. Алгоритмы и структуры данных: Пер. с англ. 2-е изд., испр. -СПб.: Невский Диалект, 2001. - 352 с.

4. Гудман С., Хидетниеми С. Введение в разработку и анализ алгоритмов. -М.: Мир, 1981.-368 с.

5. Кнут Д. Искусство программирования для ЭВМ: Пер. с англ. 2-е изд. -М.: Издательский дом "Вильяме", 2001. - Т. 1 - Основные алгоритмы. - 720 с.

6. Кнут Д. Искусство программирования для ЭВМ: Пер. с англ. 2-е изд. -М.: Издательский дом "Вильяме", 2001. - Т.З - Сортировка и поиск. - 823 с.

7. Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. М.: МЦНМО, 2000. - 960 с.

8. Овчинников В.А. Алгоритмизация комбинаторно-оптимизационных задач при проектировании ЭВМ и систем: Учеб. для вузов. М.: Изд-во МГТУ им. Н.Э. Баумана, 2001. - 288 с.

9. Савельев А.Я., Овчинников В. А. Конструирование ЭВМ и систем: Учеб. для вузов по спец. "Выч. мат., компл., сист. и сети". 2-е изд., перераб. и доп. -М.: Высшая школа, 1989.-312 с.

10. Ахо А., Ульман Дж. Теория синтаксического анализа, перевода и компиляции. М.: Мир, 1978. - Т.1 - Синтаксический анализ. - 611 с.1.. Ахо А., Ульман Дж. Теория синтаксического анализа, перевода и компиляции. М.: Мир, 1978. Т.2 - Компиляция. - 487 с.

11. Грис Д. Конструирование компиляторов для цифровых вычислительных машин. М.: Мир, 1975. - 544 с.

12. Компаниец Р. И., Маньков Е. В., Филатов Н. Е. Системное программирование. Основы построения трансляторов: Учебное пособие. СПб.: КОРОНА принт, 2000. - 256 с.

13. Льюис Ф., Розенкранц Р., Стринз Р. Теоретические основы проектирования компиляторов: Пер. с англ. Исаева / Под ред. В. Н. Агафонова. М.: Мир, 1979.• 654 с.

14. Кофман А. Введение в прикладую комбинаторику. М.: Мир, 1981.480 с.

15. Кузнецов О.П., Адельсон Вельский Г.М. Дискретная математика для инженера. 2-е изд., перераб. и доп. - М.: Энергоатомиздат, 1988. - 480 с.

16. Мелихов А.Н., Берштейн JI.C., Курейчик В.М. Применение графов для проектирования дискретных устройств. М.: Наука, 1974. - 303 с.

17. Морозов К.К., Одиноков В.Г., Курейчик A.M. Автоматизированное проектирование конструкций радиоэлектронной аппаратуры. М.: Радио и связь, 1983.-280 с.

18. Алгоритмы и программы решения задач на графах и сетях * /М.И.Нечепуренко, В.К. Попков, С.М. Майнагашев и др. Новосибирск: Наука.

19. Сиб. отделение, 1990. 515 с.

20. Норенков И. П. Разработка систем автоматизированного проектирования: Учеб. для вузов. М.: Изд-во МГТУ им. Н.Э. Баумана, 1994. - 207 с.

21. Оре О. Теория графов. -М.: Наука, 1980. 336 с.

22. Панадимитриу X., Стайглиц К. Комбинаторная оптимизация. Алгоритмы и сложность. М.: Мир, 1985. - 512 с.

23. Райли Д. Абстракция и структуры данных: Вводный курс:

24. Пер. с англ. М.: Мир, 1993. - 752 с.

25. Кристофидес Н. Теория графов. Алгоритмический подход. М.: Мир, 1978.-427 с.

26. Татт У. Теория графов: Пер. с англ. М.: Мир, 1988. - 424 с.

27. Базилевич Р.П. Декомпозиционные и топологические методы автоматизированного конструирования электронных устройств. Львов: Вища школа, 1981. - 168 с.

28. Ф 27. Липский В. Комбинаторика для программистов: Пер. с польск. М.: Мир, 1988.-213 с.

29. Мину М. Математическое программирование. Теория и алгоритмы. М.: Наука, 1990.-488 с.

30. Новиков Ф.А. Дискретная математика для программистов. СПб.: Питер, 2001.-304 с.

31. Асанов М.О., Баранский В.А., Расин В.В. Дискретная математика: графы, матроиды, алгоритмы. Ижевск, 2001. - 288 с.

32. Пратт Т., Зелковиц М. Языки программирования: разработка и реализация /Под ред. А. Матросова. СПб.: Питер, 2002. - 688 с.

33. Иванова Г.С. Технология программирования: Учеб. для вузов. М.: Изд-во МГТУ им. Н.Э. Баумана, 2002. - 320 с.

34. Байцер Б. Архитектура вычислительных комплексов. М.: Мир, 1974. -1064 с.

35. Дал У., Дейкстра Э., Хоор К. Структурное программирование. М.: Мир, * 1975.-248 с.

36. Феррари Д. Оценка производительности вычислительных систем: Пер. с англ.-М.: Мир, 1981.-576 с.

37. Лавров С.С. Программирование. Математические основы, средства, теория.- СПб.: БХВ-Петербург, 2001. 320 с.

38. Касьянов В.Н., Евстигнеев В.А. Графы в программировании: обработка, визуализация и применение. СПб.: БХВ-Петербург, 2003. - 1104 с.

39. Зубков С.В. Assembler для DOS, Windows и Unix для программистов.• СПб.: Питер, 2005. 608 с.

40. Иванов Б.Н. Дискретная математика. Алгоритмы и программы: Учебное пособие. -М.: Лаборатория Базовых Знаний, 2003. 288 с.

41. Макконнелл Дж. Основы современных алгоритмов. 2-е доп. издание. М.: Техносфера, 2004. - 368 с.

42. Юбилейный сборник трудов кафедры. М.: Изд-во МГТУ им. Н.Э.Баумана, 2002. -С. 68-77.

43. Иванова Г.С., Бакулина М.А. Автоматизация процесса разработки алгоритмов решения задач структурного синтеза на графах // Тез. Докл. Международной научно-технической конференции. М., 2003. - С. 166.

44. Овчинников В.А., Николаев К.В., Попов А.Ю. Исследование вычислительной сложности алгоритмов двоичной свертки схем ЭВМ // Вестник Московского государственного технического университета: Серия Прибоространение 1997. - N2. - С.113-120.

45. Vitter J., Flajolet Ph. Average-Case Analisys of Algorithms and Data Structure. Handbook of Handbook of theoretical computer science: algorithms and complexity. -1991.- Vol. A. P. 431-524.http://www.cs.duke.edu/ujsv/Papers/STV92.layeredshortest.pdf.

46. Flajolet Ph., Salvy В., Zimmermen P. Automatic Average-Case Analisys of Algorithms // Theoretical Computer Science. — 1991. -Feb. -P. 37-109. http:llwww-lipn.univ-parisl3frlubanderierlSeminarlflajolet.pdf

47. Попов А.Ю. Модели и алгоритмы автоматизированной декомпозиции схем ЭВМ: Дис. на соискание уч. степени канд. техн. наук. Москва, 2004. - 136 с.

48. Овчинников В.А., Бакулина М.А. Разработка и исследование алгоритмов компоновки схем по методу двоичной свертки // Юбилейный сборник трудов кафедры. М.: Изд-во МГТУ им. Н.Э.Баумана, 2002. - С. 65-68.

49. Бакулина М.А. Выбор структур данных для систем решения задач структурного синтеза // Сб. трудов каф., посвященный 175-летию МГТУ им. Н.Э.Баумана М.: Эликс+, 2004. - С. 66-68.

50. ГУВД г. Москвы Управление внутренних дел Восточного административного округа г. Москвы Информационный центр 105264, г. Москва, 8-я Парковая ул., дом 141. В Учёный Совет• I1. МГТУ им. Баумана1. Акт ! !1: 1 'о внедрении диссертационной работы j' ! : I

51. Диссертационная работа аспирантки МГТУ им. j Баумана Бакулиной■ j

52. М.А. по теме «Средства разработки и анализа алгоритмов решения задач структурного синтеза на графах» использована при решении задачи; синтеза• ! j I |схемы "DACV реляционной базы данных "ГЛО". ij ji ! I

53. И I . I ! данных используется в Информационном центре Управления внутренних I ! j ■■ = • • !дел Восточного административного округа г. Москвы для решения задачи "Дактилоскопия граждан".11майор милиции4*4.1. Чернов В.В

54. РОССИЙСКАЯ ФЕДЕРАЦИЯ ОАО: * ГИДРОМЕТПРИБОР »

55. ИНН 7719023708; КПП771901001 105187, г. Москва,' ул. Кирпичная, 43а

56. Р/с 40702810600130000279 в ОАО «МИнБ» г.Москва! БИК 044525600 к/с 301018103000000006001. З/У от "25"1. OffiSp? 200 ^Y.

57. В Ученый Совет МГТУ им.Баумана1. АКТо внедрении диссертационной работы

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

59. Генеральный ди | ОАО«Гидромет1. А. Е. Голод