Метод логико-алгебраических уравнений в анализе динамических систем тема диссертации и автореферата по ВАК РФ 05.13.01, кандидат физико-математических наук Нагул, Надежда Владимировна

• Нагул, Надежда Владимировна
• кандидат физико-математических наук
• 2008

Оглавление диссертации кандидат физико-математических наук Нагул, Надежда Владимировна

Введение

Глава 1. Обзор литературы и вспомогательные сведения

1.1. Логические и логико-алгебраические уравнения

1.2. Многоосновные алгебраические системы.

1.3. Дискретно-событийные системы как класс систем

1.4. Формализм дискретно-событийных систем.

1.5. Модель сети общественного транспорта.

Глава 2. ОМАСК и алгоритмизация синтеза критериев сохранения их свойств на основе решения логико-алгебраических уравнений

2.1. Понятие общей многоосновной алгебраической системы конечного типа

2.2. Алгоритмы синтеза критериев сохранения свойств ^ ОМАСК

2.3. Переносимость свойств в направлении, обратном направлению отображений ОМАСК

2.4. Алгоритм преобразования критериев в более эффективные

Глава 3. Примеры использования алгоритмов синтеза критериев сохранения свойств ОМАСК

3.1. Устойчивость движения общей динамической системы

3.2. Динамика автоматной сети

3.3. Некоторые свойства ДСС

3.4. ДСС-модель сети общественного транспорта и ее свойства

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

Данная диссертационная работа посвящена разработке на стыке динамики систем, алгебры и логики такого метода математической теории систем, который позволяет алгоритмически синтезировать критерии сохранения свойств систем при некоторых связывающих их отображениях типа морфизмов. Предлагаемый метод является развитием известных в математической теориии систем результатов: метода сравнения, последовавшего за ним более общего метода сравнения — метода логических уравнений (ЛУ), имеющих структуру ХМШ&^З' —» ф (где ШТ, ф', ф — известные члены уравнения, X подлежит отысканию, ф — свойство, рассматриваемое в одной системе, ф' — свойство второй системы, WI — условие связи), и еще более общего метода решения логических уравнений — метода редукции, оперирующего с уравнениями вида;£&(&;{(£; : г = 1, 2,., п}) ф, где п > 1.

Для получения критериев сохранения, состоящих из условий, имеющих смысл условий типа сохранения операций или отношений (т.е. формулируемых в духе традиционных морфизмов), в развитие известных в теории алгебраических систем результатов, а также в развитие так называемых критериев переносимости термов и соотношений в теории структур Н. Бурбаки, С.Н. Васильевым и С.В. Афанасьевой был разработан метод представимости. Его особенностью является то, что каждый критерий, в отличие от критериев, получаемых методом ЛУ, обслуживает сразу целый класс свойств (например, все позитивные свойства сохраняются при гомоморфизме). К сожалению, задача представимости (эквивалентными преобразованиями) формулы изучаемого свойства в требуемом классе является, вообще говоря, алгоритмически неразрешимой. Путем развития метода ЛУ удалось избежать этой задачи представимости (С.Н. Васильев, 1988), а также совместить гибкость формирования критерия сохранения по конкретному виду изучаемого свойства с получением всех условий в духе традиционных морфизмов. Логические уравнения при этом имеют вид Х&ф' —» ф, т.е. априорно никаких условий связи не задается, что полезно, так как тем самым повышается уровень алгоритмичности развиваемого аппарата.

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

Автором представлен алгоритм автоматического формирования условий сохранения свойств многоосновных алгебраических систем, а именно, введенных в диссертации общих многоосновных алгебраических систем конечного типа. Особенностью предлагаемого метода является также тот факт, что рассматриваются такие многоосновные алгебраические системы, функции и отношения которых определены не просто на базисных множествах или их декартовых произведениях, а на произвольных ступенях в смысле Н. Бурбаки. Более того, в диссертации введены некоторые дополнительные расширения ступеней. Это позволяет охватить такие динамические системы, как дискретно-событийные, главной отличительной особенностью которых является моделирование эволюции системы путем учета наступления каких-либо событий. Потребность в ДСС обуславливается стремительным развитием производственных систем и сетей связи, транспортных сетей и других, в первую очередь антропогенных, систем. Кроме того, ДСС широко применимы в технике. Любопытным примером ДСС является модель сети общественного транспорта.

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

Исходя из вышеизложенного, в диссертации были поставлены следующие задачи:

1) разработка метода алгоритмического синтеза критериев сохранения свойств многоосновных алгебраических систем;

2) получение с помощью этого метода критериев сохранения свойств динамических систем, в частности, представление дискретно-событийных систем в виде многоосновных алгебраических систем и получение критериев сохранения различных динамических свойств ДСС в их собственных терминах;

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

Заключение диссертации по теме «Системный анализ, управление и обработка информации (по отраслям)», Нагул, Надежда Владимировна

Заключение

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

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

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

Список литературы диссертационного исследования кандидат физико-математических наук Нагул, Надежда Владимировна, 2008 год

1. Анапольский Л.Ю., Матросов В.М. Метод сравнения в анализе возмущаемых процессов // Рефераты докладов Международного симпозиума ИФАК по проблемам организационного управления и иерархическим системам, Баку, 1971. — 1972. — М., Ч. I. — С. 43 -46.

2. Аитсаклис П.И., Мишель Э.Н., Пассино К.М. Устойчивость по Ляпунову класса систем дискретных событий // АиТ. — 1992. — N 8. С. 3-18.

3. Артамонов В. А., Ященко В.В. Многоосповные алгебры в системах открытого шифрования // Успехи математических наук. — 1994. Т. 49, N 4. - С. 149-150.

4. Афанасьева С.В., Васильев С.Н. Теорема о сохранении свойств многоосновных алгебраических систем // Оптимизация, управление, интеллект. 2005. — N 3 (11). - С. 235 247.

5. Бурбаки Н. Теория множеств. — М.: Мир, 1965. — 455 с.

6. Васильев С.Н. Достижимость и связность в автоматной сети с общим правилом переключения состояний // Диф. уравнения. 2002. - Т. 38, N 11. - С. 1533-1539.

7. Васильев С.Н. Метод представимости в логико-алгебраическом подходе к качественному анализу динамических систем j j Оптимизация, управление, интеллект. — 2005.- N 3 (11). — С. 248254.

8. Васильев С.Н. Метод редукции и качественный анализ динамических систем. I, II // Изв. РАН, ТиСУ. 2006. - N 1; N 2.

9. Васильев С.Н. Метод сравнения в анализе систем. I—IV // Диф. уравнения. 1981. - Т. 17, N 9; Т. 17, N И; 1982. - Т. 18, N 2; Т. 18, N 6.

10. Васильев С.Н. : Синтез теорем с ВФЛ в математической теории систем. дис.док.физ.-мат.наук. — Иркутск: СО РАН СССР, 1988.

11. Васильев С.Н. Сохранение некоторых динамических свойств при морфизмах // Тезисы докладов III Всесоюзной Четаевской конференции по устойчивости движения, аналитической меха-пике и управлению движением. — Иркутск. — 1977. — С.99.

12. Горчинский Ю.Н. О гомоморфизмах многоосновных универсальных алгебр в связи с криптографическим применением // Труды по дискретной математике. — 1997. — Т. 1. — С. 67-84.

13. Горчинский Ю.Н. О 7г-гомоморфизмах конечных многоосновных универсальных алгебр // Дискретная математика. — 1999. Т. 11, N 2. — С. 3-19.

14. Ершов Ю.Л. Инволюторные группы // Алгебра и логика. — 1983. Т. 22, N 3. - С. 260-275.

15. Журавлев В.Ф. Основы теоретической механики. — М.: Физ-матлит, 2001. 320 с.

16. Зиглер Б.П. Представление динамических систем на основе дискретно-событийных описаний: интеллектуальное управление на базе событий // ТИИЭР. 1989. - Т. 77, N 1. — С. 68J77.

17. Зубов В.И. Методы A.M. Ляпунова и их применения. — JL: Изд-во ЛГУ, 1957. 241 с.

18. Кавинов А.В., Крищенко А.П. Устойчивость решений в разных переменных // Диф.уравнения. — 2007. — Т. 43, N 11. — С. 14701473.

19. Карпуиин Г.А., Шапошников И.Г. Скрещенные гомоморфизмы конечных многоосновных универсальных алгебр с бинарными операциями // Дискретная математика. — 2000. — Т. 12, N 2. — С. 66-84.

20. Коэн Г., Моллер П., Кадра Ж.-П., Вьо М. Алгебраические средства оценивания характеристик дискретно-событийных систем // ТИИЭР. 1989. - Т. 77, N 1. — С. 30-53.21| Мальцев А.И. Алгебраические системы. — М.: Наука, 1970. — 329 с.

21. Мальцев А.И. Модельные соответствия // Изв. АН СССР, сер. мат. 1959. - Т. 23, N 3. - С. 313-336.

22. Мальцев А.И. О представлениях моделей // ДАН. — 1956. — Т. 108, N 1. С. 27-29.

23. Матросов В.М. Метод сравнения в динамике систем. I, II // Диф. уравнения. 1974. - Т. 10, N 9; 1975. - Т. 11, N 3.

24. Матросов В.М., Анапольский Л.Ю., Васильев С.Н. Метод сравнения в математической теории систем. — Н.: Наука, 1980. 480 с.

25. Мендельсон Э. Введение в математическую логику. — М.: Наука, 1971. 320 с.27| Михалев А.В. Ортогонально полные многосортные системы // Доклады АН СССР. 1986. - Т. 289, N 6. — С. 1304-1038.

26. Нагул Н.В. Алгоритмизация получения критериев устойчивости свойств многоосновных алгебраических систем при отображениях типа морфизмов, I // Оптимизация, управление, интеллект. 2005. - N 3 (11). - С. 268-281.

27. Нагул Н.В. Дискретно-событийные системы в исследовании сложных искусственных систем // Труды XII Байкальской Всероссийской конференции "Информационные и математические технологии в науке и управлении". Ч. I. — Иркутск: ИСЭМ СО РАН, 2007. С. 91-96.

28. Нагул Н.В. К вопросу сохранения свойств многоосновных алгебраических систем // Вестник СамГУ. Естественнонаучная серия. 2007. — N 6 (56). - С. 223-241.

29. Нагул Н.В. Новый подход к исследованию дискретно-событийных систем // Труды СВМО. 2007. — Т. 9. — N 1. — С. 221-225.

30. Нагул Н.В. О сохранении свойств многоосновных алгебраических систем // Вестник ТГУ. 2006. - N 293. - С. 158-164.

31. Плоткин Б.И. Универсальная алгебра, алгебраическая логика и базы данных. — М.: Наука. Гл. ред. физ.-мат. лит., 1991. — 448 с.

32. Рамадж П.Дж., Уонэм У.М. Управление дискретно-событийными системами // ТИИЭР. — 1989. — Т. 77, N 1. — С. 78-98.

33. Романко В.К. Разностные уравнения. — БИНОМ. Лаборатория знаний, 2006. 112 с.

34. Сибирский К. С. Введение в топологическую динамику. — Кишинев: РИО АН МССР, 1970. 221 с.

35. Ульянов С.А.: Алгоритмы и программный комплекс для анализа логико-динамических моделей автоматного типа. дис.:канд.тех.наук. Иркутск: ИДСТУ СО РАН, 2005.

36. Шапошников И.Г. Гомоморфные отношения многоосновных универсальных алгебр // Дискретная математика. — 2004. — Т. 16, N 4. — С. 138-148.

37. Шапошников И. Г. О конгруэнциях конечных мпогоосповпых универсальных алгебр // Дискретная математика. — 1999. — Т. 11, N 3. С. 48-62.

38. Benabou J. Structures algebriques dans les categories // Cahiers de Topologie et Geometric Differentiel. 1968. - N 10. - P. 1-126.

39. Braker J.G. Max-Algebra Modeling and Analysis of Time-Dependent Transportation Network // Proc. of the 1st European Control Conference Grenoble, France, 1991. — 1991. — P. 18311836.

40. Bushaw D.D. Dynamical Polysystems and Optimisation // Contr. Diff. Equations. 1963. - Vol. 2. - P. 351-365.

41. Caillaud В., Darondeau P., Lavagno L., Xi X. Synthesis and Control of Discrete Event Systems. — Springer, 2002. — 238 p.

42. Cassandras C.G., Lafortune S. Introduction to Discrete Event Systems. — Springer Science+Business Media, Inc., 1999. — 776 p.

43. Ershov Yu.L. Two Theorems on Regularly R-Closed Fields j j Journ.reine angew.Math. — 1984. — Bd. 347. — P. 164-167.

44. Feferman S. Applications of Many-Sorted Interpolation Theorems // Proc. of the Tarski Symposium. Provudence, R.I.: Amer. Math. Soc. 1974. - P. 205-224.

45. Feferman S. Lectures on Proof Theory // Proceedings of the Summer School in Logic, Leeds (M. Lob, editor), Lecture Notes in Mathematics. — Springer-Verlag, 1968. — Vol. 70. — P. 1-107.5559 6061

46. Goverde R.M.P. Railway Timetable Stability Analysis Using Max-Plus System Theory // Transpartation research, Part B. — 2007. — N 41. P. 179-201.

47. Heidergott Вde Vries R. Towards a (Max, +) Control Theory for Public Transportation Networks // Discrete Event Dynamic Systems: Theory and Applications. 2001. — N 11. — P. 371-398.

48. Michel A.N., Raining W.K., Bo H. Qualitative Theory of Dynamical Systems. — N.Y.: Marcel Dekker, Inc., 2001. — 706 p.

49. Moody J.0., Antsaklis P.J. Supervisory Control of Discrete Event Systems Using Petri Nets. — Kluwer Academic Publishers, 1998. — 208 p.

50. Overkamp A., van Schuppen J.II. Control of Discrete Event Systems — Research at the Interface of Control Theory and Computer Science. — In "From Universal Morphisms to Megabytes a Baayen Space Odyssey". CWI, Amsterdam, 1994. - P. 453-467.

51. Passino K.M., Burgess K.L. Stability Analysis of Discrete Event Systems (Adaptive and Learning Systems for Signal Processing, Communications and Control Series). — Wiley-Interscience, 1998. — 202 p.

52. Ramadge P.J., Wonham W.M. Supervisory Control of Class of Discrete Event Processes // SIAM J. Control and Optimisation. — 1987. N 25 (1). - P. 206-230.

53. Ramadge P.J., Wonham W.M. On the Supremal Controllable Sublanguage of a Given Language // SIAM J. Control and Optimisation. 1987. - N 25 (3). - P. 637-659.

54. Ramadge P.J., Wonham W.M. Modular Feedback Logic for Discrete Event Systems // SIAM J. Control and Optimisation. — 1987. N 25 (5). P. 1202 1218.

55. Rossman B. Existential Positive Types and Preservation Homomorphisms // IEEE Symp. Logic In Comput. Sci. — 2005. P. 467-476.

56. Sreenivas R.S. On the Implications of the Solvability of the Supervisory Control Problem for Certain Infinite-state Discrete Event Systems Электронный ресурс]. — Режим доступа: http://www.citeseer.ist.psu.edu /138861 .html

57. Stiver J.A., Antsaklis P.J., Lemmon M.D. A Logical DES Approach to the Design of Hybrid Control Systems // Math. Comput. Modelling. 1996. - N 23 (11/12). - P. 55-76.

58. Vassilyev S.N. Machine Synthesis of Mathematical Theorems // J. of Logic Programming. 1990. - Vol. 9, N 2, 3. - P. 235-266.

59. Walther C. Many-sorted Inferences in Automated Theorem Proving //In Sorts and Types in Artificial Intelligence. — Lecture Notes in Artificial Intelligence. Springer, 1990. - Vol. 418. - P. 18-48.

60. Whitehead A.N. A Treatise on Universal Algebra, with Applications. — I. Cambridge, 1898. Reprinted 1960. — 614 p.