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

• Юрасов, Павел Владиславович
• кандидат технических наук
• 2000

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

ВВЕДЕНИЕ.

1. ПУТИ ПОВЫШЕНИЯ ЭФФЕКТИВНОСТИ АВТОМАТИЗИРОВАНИЯ ИНФОРМАЦИОННЫХ СЕТЕЙ.

1.1. Графы и динамические системы в проблемах автоматизированного проектирования.

1.2. Особенности проектирования информационных сетей на основе теории графов.

1.3. Понятие и свойства слабосвязных графов.

Цель и задачи исследования.

2. РАЗРАБОТКА АЛГОРИТМИЧЕСКИХ ПРОЦЕДУР ПРОЕКТИРОВАНИЯ ИНФОРМАЦИОННОЙ СЕТИ НА ОСНОВЕ СЛАБОСВЯЗНЫХ ГРАФОВ.

2.1. Алгоритм определения диаметра точечного множества.

2.2. Разработка алгоритма и информационной программы.

2.3. Алгоритм "первого приближения" для проектирования локальных информационных сетей на основе слабосвязных графов.

Выводы.

3. МОДЕЛЬ ПРОЕКТИРОВАНИЯ И АЛГОРИТМИЗАЦИИ ПРИ ФОРМИРОВАНИИ ИНФОРМАЦИОННОГО ПРОСТРАНСТВА.

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

3.2. Определение геометрического места точек в проблеме проектарования информационных сетей. Частный случай у = —.

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

Выводы.

4. ПРИМЕНЕНИЕ РАЗРАБОТАННЫХ МОДЕЛЕЙ И АЛГОРИТМОВ ОПТИМАЛЬНОГО ПРОЕКТИРОВАНИЯ ИНФОРМАЦИОННЫХ

СЕТЕЙ.

4Л. Информационные сети в среде научно-исследовательской и производственной САПР.

4.2. Реализация моделей и алгоритмов в учебно-исследовательской САПР.

4.3. Описание программного обеспечения.

Выводы.

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

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

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

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

Работа выполнена в соответствии с межвузовской комплексной научно-технической программой ИТ 601 "Перспективные информационные технологии высшей школы"; Межведомственной программой "Создание национальной сети компьютерных телекоммуникаций для науки и высшей школы" Российского фонда фундаментальных исследований и Министерства науки и технологии России (1996-1998, 1999-2000 гг.); региональной межвузовской научно-технической программой "Вуз-Черноземье" (1995-2000 гг.); в рамках одного из основных научных направлений Воронежского государственного технического университета "САПР и системы автоматизации производства".

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

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

Научная новизна. В диссертации получены следующие новые результаты, которые выносятся на защиту: геометрическая модель физических компонент, реализующих связь в информационном пространстве, отличающаяся ориентацией на организацию решения автоматизированного проектирования информационных сетей; алгоритм определения связных компонент графа, обеспечивающий получение функции Гранди #(» для графа в = (Х,и), в каждой вершине х значение представляет собой наименьшее из тех неотрицательных чисел, которые принадлежат множеству ^(у) | у е Д»}; алгоритм "первого приближения", позволяющий проектировать локальные информационные сети на основе слабосвязных графов; вычислительная процедура решения задачи проектирования оптимальных по геометрическим характеристикам информационных сетей, отличающаяся широким использованием методов алгебраической геометрии и позволяющая находить точки плоскости, имеющие равную информацию о двух протяженных объектах, что позволяет также эффективно решать проблему геометрического моделирования информационных сетей.

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

Реализация результатов работы.

Предложенные алгоритмы и программные средства используются в НТП Минобразования РФ "Научное, научно-методическое, материально-техническое и информационное обеспечение системы образования"; подпрограмма "Научное, научно-методическое обеспечение индустрии образования"; раздел "Корпоративные сети и информационное обеспечение управления качеством образования" (2000 г.) /1,2/

Внедрены в учебный процесс ВГТУ методические рекомендации и указания по выполнению лабораторных работ, курсовое и дипломное проектирование для студентов специальностей 220300 "Системы автоматизированного проектирования" и 071900 "Информационные системы" по курсам "ЭВМ и периферийные устройства" и

Информационные сети" в рамках учебно-исследовательской САПР, соответственно /3/.

Апробация работы. Основные положения и научные результаты диссертационной работы докладывались и обсуждались на Международных, Всероссийских, региональных научно-технических конференциях, совещаниях и семинарах кафедры "Системы автоматизированного проектирования и информационные системы" (Воронеж, 1994-2000); ежегодных научных конференциях профессорско-преподавательского состава (Воронеж, 1994-2000); Всероссийском совещании-семинаре "Математическое обеспечение высоких технологий в технике, образовании и медицине" (Воронеж, 1994,1997); научно-методической конференции "Проблемы качества образования" (Уфа, 1996); Республиканской электронной научной конференции "Современные проблемы информатизации" (Воронеж, 1997); Международной научной конференции "Нелинейный анализ и функционально-дифференциальные уравнения" (Воронеж, 2000).

Публикации. Основные результаты диссертации опубликованы в 10 печатных работах, в том числе в учебном пособии.

Структура и объем работы. Диссертационная работа состоит из введения, четырех глав и заключения. Основная часть работы изложена на 129 страницах, содержит 24 рисунка, список литературы и приложение.

Заключение диссертации по теме «Системы автоматизации проектирования (по отраслям)», Юрасов, Павел Владиславович

Основные результаты работы заключаются в следующем:

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

2. Алгоритм определения связных компонент графа, обеспечивающий получение функции Гранди для графа О = (Х,и), в каждой вершине х значение ^(х) представляет собой наименьшее из тех неотрицательных чисел, которые принадлежат множеству | у е Г(х)}.

3. Алгоритм "первого приближения", позволяющий проектировать локальные информационные сети на основе слабосвязных графов.

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

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

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

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

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

8. Разработано методическое и программное обеспечение, реализующее математическую поддержку САПР информационных сетей.

9. Предложенные алгоритмы и программные средства используются в НТП Минобразования РФ "Научное, научно-методическое, материально-техническое и информационное обеспечение системы образования"; подпрограмма "Научное, научно-методическое, обеспечение индустрии образования"; раздел "Корпоративные сети и информационное обеспечение управления качеством образования" (2000 г.).

10.Внедрены в учебный процесс ВГТУ методические рекомендации и указания по выполнению лабораторных работ, курсовое и дипломное проектирование для студентов специальностей 220300 "Системы автоматизированного проектирования" и 071900 "Информационные системы" по курсам "ЭВМ и периферийные устройства" и "Информационные сети" в рамках учебно-исследовательской САПР, соответственно.

ЗАКЛЮЧЕНИЕ

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

Список литературы диссертационного исследования кандидат технических наук Юрасов, Павел Владиславович, 2000 год

1. Структура и содержание региональных и вузовских курсов дистанционного образования / Г.В.Кольцова, Я.Е.Львович, В.Н.Фролов, В.Г.Юрасов, П.В.Юрасов // Проблемы качества образования: Тез. докл. науч.-метод. конф. Уфа: УГТУ, 1996. С.121-122.

2. Юрасов В.Г. Информационные сети / В.Г.Юрасов, П.В.Юрасов, Е.А.Гончаров: Учеб. пособие. Воронеж: Изд-во ВГТУ, 2000. 115 с.

3. Siljak D. D. On pure structure of dynamic systems // Nonlinear Analysis, Theory, Methods, and Applications. 1977. N l.P. 397- 413.

4. Deo N. Graph Theory with Applications to Engineering and Computer Science. New Jersey: Prentice-Hall, Rnglewood Cliffs, 1974. 198 p.

5. Siljak D. D. On reachability of dynamic systems // International Journal of Systems Science. 1977. N 8. P. 321-338.

6. Kalman R. E. Mathematical description of linear dynamical systems // SIAM Journal on Control. 1963. N 1. P.152-192.

7. Харари Ф. Теория графов: Пер.с англ. М.: Мир, 1973. 279 с.

8. Festinger L. Social Pressures in Informal Groups /L.Festinger, S.Schachter, K.Back . New York: Harper, 1950. 175 p.

9. Berztiss A. Т. Data Structures; Theory and Practice. New York: Academic Press, 1975. 437 p.

10. Warshall S. A. A theorem on Boolean matrices // Journal of the Association of Computing Machinery. 1962. N 9. P. 11-12.

11. Hopcroft J. E., Twjan R. Planarity testing in Vlog V steps // Proceeding* of thelFIP Congress. Ljubljana: Yugoslavia, 1971. Ta-2. P.18-23.

12. Tarjan R. Depth-first search and linear graph algorithms // SI AM Journal on Computing. 1972. N 1. P.146-160.

13. Шильяк Д.Д. Децентрализованное управление сложными системами: Пер. с англ. М.: Мир, 1994. 576с.

14. Siljak D. D. Large-Scate Dynamic Systems: Stability and Structure. New York: North-Holland, 1978. 278 p.

15. Нагату F. 5 tructuraJ Models: An Introduction to the Theory of Directed Graphs /F.HaraTy , R.Z.Norman , D.Cartwright. New York: Wiley, 1965. 154 p.

16. Harary F. A graph-theoretic method for the complete reduction of a matrix with a view toward finding its eigenvalues // Journal of Mathematics and Physics. 1959. N 38. P.104-111.

17. Purdom P. A transitive closure algorithm // Nordisk Tid-skrift for Informationbehandlung. 1970. N 10. P.76-94.

18. Munro I. Efficient determination of the transitive closure of a directed graph // Information Proceedings Letters. 1971. N 1. P. 56-58.

19. Gustavson F. G. Finding the block lower triangular form of a sparse matrix- Sparse Matrix Computations / F.G.Gustavson, J. R. Bunch, D. J. Rose . New York: Academic Press, 1976. P.275-289.

20. Duff I. S., Reid J. K. An implementation of Tarjan's algorithm for the block triangularization of a matrix // ACM Journal of Mathematical Software. 1978. N4. P. 137-147.

21. Duff I. S., Reid J. K. Algorithm 529. Permutations to block triangular form 11 ACM Transactions on Mathematical Software. 1978. N 4. P. 189-192.

22. Vidyasagar M. Decomposition techniques fur larsr-scale systems with nonadditive interactions; Stability and subiliabilily // fEEE Transactions. 1980. AC-25. P.773-779.

23. Lee E. В., Markus L. Foundations of Optimal Control Theory. New York: Wiley, 1961. 276 p.

24. Lin С. T. Structural controllability //IEEE Transactions. 1974. AC-19. P. 201-208.

25. Nour-Eldin H. A. Linear multi variable systems controllability and observability; Numerical aspects // Systems and Control Encyclopedia. Oxford UK:Pergamon Press, 1987. P. 2816-2827.

26. Wonham W. M. Linear Multivariabte Control: A Geometric Approach. New York: Springer, 1979. 385 p.

27. Shields R. W., Pearson J. B. Structural contioll ability of multiinput linear systems II IEEE Transactions. 1976. AC-21. P. 203-212.

28. Glover K., Silverroan L. M. Characterization of structural controllability // IEEE Transactions. 1976. AC-21. P. 534-537.

29. Kailath T. Linear Systems. Prentice-HaJl. New Jersey: Englewood Cliffs, 1980. 415 p.

30. Гауе К.Ф. Труды по теории чисел // М.: Изд-во АН СССР, 1959. 328 с.

31. Шеннон К. Работы по теории информации и кибернетике: Пер. с анг. / Под ред. Р.Л.Добрушина, О.Б.Лупанова. М.: Изд-во иностранной литературы, 1963. 374 с.

32. Шеннон К. Принципы кодово-импульсной модуляции: Пер. с анг. / Под ред. А.А. Харкевича. М.: Изд-во иностранной литературы, 1963. 113 с.

33. Шеннон К. Связь при наличии шума: Пер. с анг. A.A. Харкевича / Под ред. P.J1. Добрушина, О.Б. Лупанова // Работы по теории информации и кибернетике: Изд-во иностранной литературы. М., 1963. 437 с.

34. Шеннон К. Пропускная способность канала с шумом при нулевой ошибке: Пер. с анг. Б.С. Цыбакова / Под ред. P.J1. Добрушина, О.Б. Лупанова // Работы по теории информации и кибернетике: Изд-во иностранной литературы. М., 1963. 437 с.

35. Шеннон К. Геометрический подход к теории пропускной способности каналов связи: Пер. с анг. М.Г. Шура / Под ред. Р.Л. Добрушина, О.Б. Лупанова // Работы по теории информации и кибернетике: Изд-во иностранной литературы. М., 1963. 437 с.

36. Шеннон К. Каналы с дополнительной информацией на передатчике: Пер. с анг. Б.С. Цыбакова / Под ред. Р.Л. Добрушина, О.Б. Лупанова // Работы по теории информации и кибернетике: Изд-во иностранной литературы М., 1963. 437 с.

37. Шеннон К. Замечания о частичном упорядочении каналов связи: Пер. с анг. Я.Г. Синал / Под ред. Р.Л. Добрушина, О.Б. Лупанова // Работы по теории информации и кибернетике: Изд-во иностранной литературы М., 1963.437 с.

38. Шеннон К. Двусторонние каналы связи: Пер. с анг. В.В. Прелова / Под ред. Р.Л. Добрушина, О.Б. Лупанова // Работы по теории информации и кибернетике: Изд-во иностранной литературы М., 1963. 437 с.

39. Шеннон К. О максимальном потоке через сеть: Пер. с анг. В.И. Левенштейна / Под ред. Р.Л. Добрушина, О.Б. Лупанова // Работы по теории информации и кибернетике: Изд-во иностранной литературы М., 1963. 437 с.

40. Hartigan J.A. Clustering Algorithms: Wiley, New York, 1975. 375 p.

41. Reingold E.M. On the optimality of some set algorithms: Journal of the ACM 19, 1972. P.649-659.

42. Reingold E.M. Combinatorial Algorithms / E.M.Reingold, J.Nievergelt, N.Deo // Theory and practice. Prentice-Hall, Englewood Cliffs, NJ, 1977. 538 p.

43. Hocking J.G. Topology: J.G.Hocking, G.S.Young / Addison-Wesley, Reading, MA, 1961. 267 p.

44. Яглом И.М. Выпуклые фигуры / И.М.Яглом, В.Г.Болтянский: М.Л.:Гостехиздат, 1951. 289 с.

45. Кнут Д. Искусство программирования для ЭВМ / Основные алгоритмы: М.: Мир, 1976. Т. 1. 345 с.

46. Кнут Д. Искусство программирования для ЭВМ / Сортировка и поиск: М.: Мир, 1978. Т.З. 264 с.

47. Агранович Ю.Я. Проблема проектирования информационных сетей, минимизирующих энтропию слабосвязного графа / Ю.Я.Агранович,

48. B.Г.Юрасов, П.В.Юрасов: Математическое обеспечение информационных технологий в технике, образовании и медицине: Тез. докл. Всерос. совещ.-сем. Воронеж: ВГТУ, 1997. 4.1. С.53.

49. Коивей Дж. Упаковка шаров, решетки и группы / Дж.Коивей, Н.Слоэн. М.: Мир, 1990. Т.2. 376 с.

50. Вороной Г.Ф. Сборник сочинений / Киев: Изд-во АНЧССР, 1952. Т.2. 432 с.

51. Агранович Ю.Я. Представление энтропии конечных схем интегралами рациональных функций // Высокие технологии в технике, медицине, экономике и образовании: Межвуз. сб. науч. тр. Ч.З. Воронеж: Изд-во ВГТУ, 2000. С. 112-119.

52. Агранович Ю.Я. Математическая модель информационного пространства в проблеме проектирования оптимальных информационных сетей / Ю.Я.Агранович, П.В.Юрасов: Информационные технологии. М., 1998. № 5. С.31-34.

53. Рохлин А.В. Избранные труды / М.: МЦНМО, ВКМНМУ, 1999. 496 с.

54. Гельфанд И.М. К общему определению количества информации / И.М. Гельфанд, А.Н. Колмогоров, A.M. Яглома // Докл. Акад. Наук СССР, 1956. Ч.З. С. 745-748.

55. Гельфанд И.М. Количество информации и энтропия для непрерывных распределений / И.М. Гельфанд, А.Н. Колмогоров, A.M. Яглома // Труды 3-го Всесоюзного математического съезда: Изд-во АНСССР, 3, 1958. С. 521-531.

56. Гельфанд И.М. О вычислении количества информации о случайной функции, содержащейся в другой такой же функции / И.М. Гельфанд, A.M. Яглома // Успехи матем. наук, 12, 1, 1975. С. 3-52.

57. Кокарев В.Н. Мосты и маршрутизаторы // Мир ПК, 1994. N 8. С. 35-36

58. Виноградов Б.Н. Как построить сеть // Мир ПК, 1993. N 8. С. 28-30.

59. Локальные сети от А до Я: курс обучения. Компьютер Пресс, N l-f-6, 1990.

60. Осадчук А. Сетевые архитектуры современных информационно-вычислительных сетей // Компьютер Пресс, 1995. N 11.С., N 3, 1996.

61. Любимов А. Сетевые технологии и решаемые задачи // Компьютер Пресс, 1995. N Ю.С. 101-105.

62. Сетевые решения Computer Mechanics. Мир ПК, N 10, 1994.

63. Кокарев В.Н. Трудный выбор скоростной ЛВС // Сети, 1994. N 6.С. 4849.

64. Мартин Н. Математическая теория энтропии / Н.Мартин, Дж.Ингленд // М.: Мир, 1988.350 с.

65. Канторович Л.В. Функциональный анализ / М.: Наука, 1977. С. 299315.

66. Канторович Л.В. Об одном функциональном пространстве и некоторых экстремальных задачах / Л.В.Канторович, Г.Ш.Рубинштейн // ДАН СССР, 115, 1957. №6. С. 1058-1061.

67. Канторович Л.В. Об одном пространстве вполне аддитивных функций / Л.В.Канторович, Г.Ш.Рубинштейн // Вестник ЛГУ, 1958. № 7. С. 52-59.

68. Белман Р. Динамическая программирование и современная теория управления / Р.Белман, Р.Калаба // М.: Наука, 1969. С. 97.

69. Борисович Ю.Г. Введение в топологию / Ю.Г. Борисович, Н.М. Близняк, Я.А. Израилевич, Т.Н. Фоменко // М.: Наука, 1995. 126 с.

70. Функциональный анализ: Справочная математическая библиотека / Под ред. С.Г. Крейна. М.: Наука, 1972. 544 с.

71. Крейн М.Г. Проблема моментов Маркова и экстремальные задачи / М.Г. Крейн, A.A. Неудельман // М.: Наука, 1973. 551 с.

72. Итоги науки и техники / Сер. Современные проблемы математики. Фундаментальные направления. Динамические системы-2 // М.: ВИНИТИ, 1985. С. 5-111.137

73. Ivanov A.O. Minimal Networks. The Steiner Problem and Its Generalizations. N.W. /A.O.Ivanov, A.A.Tuzhilin // Boorsa Ration, Florida: CRC Press, 1994. 459 p.

74. Agranovich Yu. Ya. An entropy parametrization of the Navier-Stokes equation. V Workshop on partial differential equations: theoty, computations and applications. Rio de Janeiro, IMPA, Brazil. 1997.

75. Matrix: :Matrix (int r,int c) {a=0;row=r;column=c; matrix=new signed long r*c.;for (int i=0;i<r;i++) for (int j=0;j<r;j++) matrixr*j+i.=0; }signed long& Matrix::operator ()(int r,int c) {if(r<row && c<column) return(matrix r*column+c.);return (a); }

76. Matrix: -Matrix () {delete matrix;}class Matrix 1private :int row,column; char *matrix; char a; public :Matrix 1 (int,int);char& operatorO(int,int); int Row () {return row;} int Column () {return column;} -Matrix 1 ();

77. Matrix 1: :Matnx 1 (int r,int c)a=0;row=r;column=c; matrix=new char r*c.;for (int i=0;i<r;i++) for (int j=0;j<r;j++) matrixr*j+i.=0; }char& Matrix 1:: operator ()(int r,mt c)if(r<row && c<column) retum(matrix r*column+c.);return (a); }

78. Matrix Price(9,9),temp(9,9),out(9,9);

79. Matrixl Main(9,9),comp(9,9);textbackground (9);textcolor(14);clrscr();1.put (Main);1.put (Price);

80. MakeComponentMatrix (Main,comp);