Графы в задачах анализа и синтеза структур сложных систем

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

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

Список литературы

1. Ахо А., Хопкрофт Д., Ульман Д. Построение и анализ вычислительных алго-ритмов. М.: Мир, 1979
2. Ахо А.В., Хопкрофт Д.Э., Ульман Д.Д. Структуры данных и алгоритмы. М.: Издательский дом Вильямс, 2003.3
3. Ахо А., Ульман Дж. Теория синтаксического анализа, перевода и компиляции. М.: Мир, 1978. Т. 1.
4. Ахо А., Ульман Дж. Теория синтаксического анализа, перевода и компиляции. М.: Мир, 1978. Т. 2
5. Дал У., Дейкстра Э., Хоор К. Структурное программирование. М.: Мир, 1975
6. Иванова Г.С. Методология и средства разработки алгоритмов решения задач анализа и синтеза структур программного обеспечения и устройств вычислительной техники: дис. ... д-ра техн. наук. М., 2007.
7. Касперский К. Техника оптимизации программ. Эффективное использование памяти. СПб.: БХВ-Петербург, 2003
8. Касьянов В.Н., Евстигнеев В.А. Графы в программировании: обработка, визуа-лизация и применение. СПб.: БХВ-Петербург, 2003
9. Касьянов В.Н. Оптимизирующие преобразования программ. М.: Наука, 1988.10
10. Компаниец Р.И., Маньков Е.В., Филатов Н.Е. Системное программирование. Основы построения трансляторов. СПб.: Корона принт, 2000
11. Кормен Т., Лейзерсон Ч., Риверст Р. Алгоритмы: построение и анализ. М.: МЦНМО, 2000.12
12. Котов В.Е., Сабельфельд В.К. Теория схем программ. М.: Наука, 1991
13. Кристофидес Н. Теория графов. Алгоритмический подход. М.: Мир, 197
14. Лекции по теории графов / В.А. Емеличев, О.И. Мельников, В.И. Сарванов, Р.И. Тышкевич. М.: Наука, 1990.
15. Мелихов А.Н., Берштейн Л.С. Гиперграфы в автоматизации проектирования дискретных устройств. Ростов н/Д: Изд-во Ростовского университета, 1981
16. Мелихов А.Н. Ориентированные графы и конечные автоматы. М.: Наука, 1971
17. Мелихов А.Н., Берштейн Л.С., Курейчик В.М. Применение графов для про-ектирования дискретных устройств. М.: Наука, 1974
18. Новиков Ф.А. Дискретная математика для программистов. СПб: Питер, 2001
19. Овчинников В.А. Алгоритмизация комбинаторно-оптимизационных задач при проектировании ЭВМ и систем: учеб. для вузов. М.: Изд-во МГТУ им. Н.Э. Баумана, 2001
20. Овчинников В.А., Иванова Г.С. Информационно-логическая модель алгоритма // Вестник МГТУ им. Н.Э. Баумана. Сер. «Приборостроение». 2005. № 2 (59). C. 109–121.
21. Овчинников В.А. Математические модели объектов задач структурного син-теза: Наука и образование. Инженерное образование: эл. науч. издание. 2009. № 3.
22. Овчинников В.А. Операции над ультра- и гиперграфами для реализации про-цедур анализа и синтеза структур сложных систем: Наука и образование. Инженерное образование: эл. науч. издание. 2009. № 10
23. Овчинников В.А. Операции над ультра- и гиперграфами для реализации про-цедур анализа и синтеза структур сложных систем: Наука и образование. Инженерное образование: эл. науч. издание. 2009. № 11
24. Овчинников В.А. Операции над ультра- и гиперграфами для реализации про-цедур анализа и синтеза структур сложных систем: Наука и образование. Инженерное образование: эл. науч. издание. 2009. № 12
25. Овчинников В.А. Операции над упорядоченными множествами: Наука и об-разование. Инженерное образование: эл. науч. издание. 2011. № 6
26. Овчинников В.А., Иванова Г.С. Оценка эффективности применения операций над упорядоченными множествами. Наука и образование. Инженерное образование: эл. науч. издание. 2011. № 10
27. Овчинников В.А., Иванова Г.С. Методика формального синтеза комбиниро-ванных структур данных для представления графов // Вестник МГТУ им. Н.Э. Баумана. Сер. «Приборостроение». Спец. выпуск № 4 «Компьютерные системы и технологии». 2012. С. 135–145.
28. Овчинников В.А., Иванова Г.С., Павлов А.Е. Оценка эффективности оптими-зирующих преобразований алгоритмов операций над ультраграфами. Наука и образо-вание. Инженерное образование: эл. науч. издание. 2013. № 1
29. Савельев А.Я., Овчинников В.А. Конструирование ЭВМ и систем: учеб. для техн. вузов по спец. «Электрон. выч. маш.». М.: Высш. шк., 1984.
30. Савельев А.Я., Овчинников В.А. Конструирование ЭВМ и систем: Учеб. для вузов по спец. «Выч. маш., компл., сист. и сети.». 2-е изд., перераб. и доп. М.: Высш. шк., 1989
31. Судоплатов С.В., Овчинникова Е.В. Элементы дискретной математики: учеб-ник. М.: ИНФРА-М, Новосибирск: Изд-во НГТУ, 200
32. Харари Ф. Теория графов. М.: Мир, 1973
33. Karypis G., Aggarwal R., Kumar V., Shekhar S. Multilevel Hipergraph Partitioning: Application in VLSI Domain // Proc. Design Automation Conf., June 1998