Синтез оптимальных структур данных для алгоритмов решения комбинаторных задач на графах тема диссертации и автореферата по ВАК РФ 05.13.11, кандидат технических наук Пасечников, Константин Алексеевич

• Пасечников, Константин Алексеевич
• кандидат технических наук
• 2009

Оглавление диссертации кандидат технических наук Пасечников, Константин Алексеевич

ВВЕДЕНИЕ.

1. АНАЛИЗ СУЩЕСТВУЮЩИХ МЕТОДОВ СИНТЕЗА СТРУКТУР ДАННЫХ И ПОСТАНОВКА ЗАДАЧИ.

1.1. Анализ существующих методов оптимизации структур данных

1.1.1. Языки сверхвысокого уровня и абстрактные типы данных.

1.1.2. Специализация структур данных.

1.1.3. Оптимизация структур данных, использующих указатели.

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

1.2. Анализ методов автоматического выбора оптимальных структур данных.

1.3. Анализ существующих формальных описаний структур данных

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

Выводы по главе 1.

2. РАЗРАБОТКА МОДЕЛЕЙ СТРУКТУР ДАННЫХ.

2.1. Анализ операций над структурами данных.

2.2. Модели базовых одноуровневых структур данных.

2.3. Модели комбинированных одноуровневых структур данных.

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

2.5. Модели базовых двухуровневых структур данных.

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

Выводы по главе 2.

3. РАЗРАБОТКА МЕТОДИКИ СИНТЕЗА ОПТИМАЛЬНЫХ СТРУКТУР ДАННЫХ И ГЕНЕРАЦИИ ИХ ОПИСАНИЙ.

3.1. Синтез комбинированных одноуровневых структур данных.

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

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

3.1.3. Способ задания функций одного переменного.

3.1.4. Реализация операции объединения структур данных.

3.1.5. Генерация описания одноуровневой структуры данных.

3.2. Синтез многоуровневых структур данных.

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

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

Выводы по главе 3.

4. ЭКСПЕРИМЕНТАЛЬНЫЕ ИССЛЕДОВАНИЯ ПОЛУЧЕННЫХ РЕЗУЛЬТАТОВ.

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

4.2. Исследование зависимости вычислительной сложности реализации алгоритма уравновешенной двоичной свертки от структур данных.

4.3. Исследование зависимости вычислительной сложности алгоритма неуравновешенной двоичной свертки от свойств входных данных

4.4. Исследование зависимости вычислительной сложности алгоритма лингвистического анализа текста от структур данных.

Выводы по главе 4.

ВЫВОДЫ.

Введение диссертации (часть автореферата) на тему «Синтез оптимальных структур данных для алгоритмов решения комбинаторных задач на графах»

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

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

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

Вычислительная сложность вариантов реализации алгоритма при использовании различных структур данных может отличаться на несколько порядков. Данная задача, т.е. задача синтеза оптимальных структур данных, является самостоятельной научной проблемой, актуальной для многих научно-технических направлений. На данный момент существуют системы, которые решают лишь задачу выбора оптимальной структуры данных [32, 49, 51], в то время как формальной постановки задачи синтеза до сих пор не было получено.

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

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

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

1. Выполнить анализ существующих структур данных с целью выявления Pix свойств и классификации основных операций над ними.

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

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

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

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

6. Выполнить экспериментальную проверку полученных теоретических результатов.

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

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

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

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

3. Формально определена операция объединения моделей структур данных, позволяющая получать модели комбинированных структур данных и их характеристики из базовых.

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

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

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

Апробация работы. Основные положения работы обсуждались на научно-технической конференции, посвященной 175-летию МГТУ им. Н.Э. Баумана (Москва, 2005), на научной конференции «Информатика и системы управления», проходившей в МГТУ им. Н.Э. Баумана (Москва, 2007).

Реализация и внедрение. Все основные теоретические и практические результаты работы в виде методик и программных средств внедрены в промышленность. Они использованы при разработке очередной версии системы защиты Windows-приложений StarForce Protection Builder 5.70 в ООО «Протекшей Технолоджи» (StarForce) и при создании системы анализа и классификации текстов БКФ 2.00 в ЗАО «ИнфоВотч» (дочерняя компания ЗАО «Лаборатория Касперского»). Документы, подтверждающие внедрение, приведены в приложении.

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

Объем и структура диссертации. Диссертационная работа включает введение, четыре главы, заключение и список литературы, занимающих 159 страниц текста, в том числе 32 рисунка и 23 таблицы, список использованной литературы из 58 наименований на 6 страницах.

Заключение диссертации по теме «Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей», Пасечников, Константин Алексеевич

ВЫВОДЫ

1. Для представления простых структур разработаны модели базовых структур данных, позволяющие оценивать вычислительную сложность базовых операций и емкостную сложность исследуемой структуры, а также обладающие меньшей избыточностью по сравнению с моделями, предложенными В [13].

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

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

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

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

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

Список литературы диссертационного исследования кандидат технических наук Пасечников, Константин Алексеевич, 2009 год

1. Архангельский А. Я. Программирование в Delphi 7. — М.: Бином-Пресс, 2003.- 1152 с.

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

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

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

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

6. Вирт Н. Алгоритмы+структуры данных=программы: Пер. с англ. М.: Мир, 1985.-406 с.

7. Гамма Э., Хелм Р., Джонсон Р. Приемы объектно-ориентированного проектирования. Паттерны проектирования. — М.: Питер, 2006, 368 с.

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

9. Иванова Г.С., Домосканов A.A. Оптимизация управления динамическим распределением оперативной памяти. // Современные информационные технологии: Сб. докл. и сооб. Межвузовской юбилейной научно-технической конференции. М., 2001. - С. 6-13.

10. П.Иванова Г.С. Математические модели структур данных // Информационные технологии. 2006. - № 9. — С. 44-52.

11. Иванова Г.С. Модели объектов задач структурного синтеза // Наука и образование. Инженерное образование: Эл. науч. издание. 2006. — № 12. (Номер гос. регистрации 0420600025\0053.)

12. Иванова Г.С. Методология и средства разработки алгоритмов решения задач анализа и синтеза структур программного обеспечения и устройств вычисли-тельной техники: Дисс. докт. техн. наук. М., 2007. - 416 с.

13. Н.Иванова Г.С. Способы представления структурных моделей // Наука и образование. Инженерное образование: Эл. науч. издание. 2007. - № 1. (Номер гос. регистрации 0420700025\003.)

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

15. Касперски К. Техника оптимизации программ. Эффективное использование памяти. СПб.: БХВ - Петербург, 2003. - 464 с.

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

17. Макконнелл Дж. Основы современных алгоритмов: Пер. с англ. М.: Техносфера, 2004. - 368 с.

18. Норенков И.П. Основы автоматизированного проектирования: Учеб. для вузов. М.: Изд-во МГТУ им. Н.Э. Баумана. - 2000. - 360 с.

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

20. Пасечников К.А., Иванова Г.С. Модели структур данных для представления объектов задач структурного анализа и синтеза. // Информатика и системы управления: Сб. трудов молодых учёных, аспирантов и студентов МГТУ им. Баумана. 2006. - №4. - С. 45-48.

21. Пасечников К.А., Иванова Г.С. Генерация оптимальных структур данных для алгоритмов решения комбинаторных задач на графах. // Аэрокосмические технологии: Труды Всероссийских и Международной научно-технических конференций. М., 2008. - С. 112-115.

22. Пасечников К.А. Генерация комбинированных структур данных

23. Наука и образование. Инженерное образование: Эл. науч. издание. 2008. -№11. (Номер гос. регистрации 0420900025)

24. Пасечников К.А., Иванова Г.С. Синтез оптимальных структур данных для решения задач на графах // Вестник Московского государственного технического университета им. Н.Э. Баумана. Приборостроение. 2008. - № 4(73).-С. 29-38.

25. Пасечников К.А. Модели структур данных с векторной, списковой и древовидной организацией элементов // Наука и образование. Инженерное образование: Эл. науч. издание. 2008. - № 10. (Номер гос. ре-гистрации 0420900025)

26. Райли Д. Абстракция и структуры данных: Пер. с англ. М.: Мир, 1993.-752 с.

27. Рихтер Дж. Программирование на платформе Microsoft .NET Framework. M.: Издательско-торговый дом "Русская редакция", 2003. — 512 с.

28. Рихтер Дж. Windows для профессионалов: создание эффективных \Ут32-приложений с учетом специфики 64-разрядной версии Windows. M.: Издательско-торговый дом "Русская редакция", 2001. - 752 с.

29. Соломон, Д. Внутреннее устройство Microsoft Windows 2000. Мастер-класс. M.: Издательско-торговый дом "Русская редакция", 2001. - 992 с.

30. Cai J., Façon Ph. Type analysis and data structure selection // Constructing Programs from Specifications / B. Moller. North-Holland, 1991. - P. 124-164.

31. Chase D., Wegman M., Zadek F. Analysis of pointers and structures

32. Proceedings of the SIGPLAN '90 Conference on Program Language Design and Implementation. New York, 1990. - P. 296-310.

33. Childs D.L. Feasibility of a set-theoretical data structure a general structure based on a reconstituted definition of relation // IFIP Cong. - Michigan, 1968. - 123 p.

34. Cook W. Object-oriented programming versus abstract data types // Proceedings of REX Workshop School on the Foundations of Object-Oriented Languages. London, 1990.-P. 151-178.

35. Freudenberger S., Schwartz J. Experience with the SETL Optimizer // Abstract in TOPLAS 5(1). New York, 1983. - P. 26-45.

36. Guttag J. J. Abstract data types and the development of data structures // Communications of the ACM. New York, 1977. - V. 20. - P. 396-404.

37. Hoare C. A. R. Proof of correctness of data representations // Acta Information-New York, 1972.-V.l P. 271-281.

38. Hummel J., Hendren L. J., Nicolau A. Abstract description of pointer data structures: An approach for improving the analysis and optimization of imperative programs // ACM Letters on Programming Languages and Systems. New York, 1992.-P. 243-260.

39. Jones N.D. An introduction to partial evaluation // ACM Computing Surveys. New York, 1996. - V. 28. - P. 480-503.

40. Jones N.D., Muchnick. S.S. Flow analysis and optimization of LISP-Iike structures // ACM SIGPLAN Notices. New York, 1981. - P. 343-359.

41. Kant E. The selection of efficient implementations for a high-level language // Proceedings of the 1977 symposium on Artificial intelligence and programming languages. New York, 1977. - P. 140-146.

42. Lattner C. Macroscopic Data Structure Analysis and Optimization : Ph.D. Thesis, Computer Science Dept., University of Illinois. — Urbana-Champaign, 2005.-225 p.

43. Liskov B. Data Abstraction and Hierarchy // ACM SIGPLAN Notices. -New York, 1987. V.23.-P. 17-34.

44. Liskov B., Zilles N. Programming with abstract data types. // SIGPLAN Notices. New York, 1974. - V.9. - P. 50-59.

45. Low J. R. Automatic Data Structure Selection: An Example and Overview // Communications of the ACM. -New York, 1978. V. 21. - P.376-385.

46. Park J. G., Park M. S. Using Indexed Data Structures for Program Specialization // Internet Computing Lab., Department of Computer Science and Engu-neering, Korea University. Seoul (Korea), 2001. — P. 61-69.

47. Schonberg E., Schwartz J. Automatic data structure selection in SETL

48. Conference record of the 6th annual ACM symposium on principles of programming languages. San Antonio (Texas), 1979. - P. 197-210.

49. Schwartz J. Automatic and semiautomatic optimization of SETL // Proceedings of the ACM SIGPLAN symposium on Very high level languages. New York, 1974.-P. 42-49.

50. Schwartz, J. Automatic data structure choice in a language of very high level // CACM 18. New York, 1975. - V.12. - P. 722-728.

51. Schwartz J., Dubinsky E. Programming With Sets: An Introduction to SETL. New York, 1986. - 127 p.

52. Snyder. K. The SETL2 programming language: Technical Report 490, Courant Institute of Mathematical Sciences. New York, 1990. - P. 44-53.

53. Standish T. A. Data structures: An axiomatic approach // Communications of the ACM. New York, 1977. - V.20. - P. 396-404.

54. Tenenbaum A. Program efficiency and data structures // ACM SIGCSE Bulletin. New York, 1977. - V. 9. - P. 21-27.

55. Truong D. N., Bodin F. Improving cache behavior of dynamically allocated data structures // Proceedings of the International Conference on Parallel Architectures and Compilation Techniques. Paris, 1998. - P. 322-329.

56. Wegbreit B. Goal-directed program transformation // IEEE Transactions on Software Engineering SE. New York, 1976. - P.69-79.

57. Zilles S. Abstract specifications for data types // IBM Res. Lab. San Jose (California), 1975.-P.453-479.