![]() КАТЕГОРИИ: Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748) |
Пример 3. Для системы образующих примера 2 формулы обратных преобразований имеют вид:
Для системы образующих примера 2 формулы обратных преобразований имеют вид: В качестве примера этих преобразований рассмотрим задачу выражения собственного полинома 2-ой степени Вычислим преобразования каждого из мономов
Просуммируем полученные равенства и выделим полином, не зависящий от Это и есть представление 4. Собственные полиномы и Пусть Отметим, что для операторов – жордановых клеток теорема 4 дает описание этого базиса через полиномы набора
Пусть В частности, один из вопросов может быть сформулирован таким образом: пусть множество базисных мономов задано формулой
Очевидно, (примеры 2, 3) базисом подпространства Для каждой жордановой клетки
Собственным числом подпространства Рассмотрим линейный оператор, образованный двумя жордановыми клетками
Через
Если
то
а собственное число этого подпространства равно Если жорданова форма линейного оператора
для оператора Теорема 5. Если собственные числа двух подпространств собственных полиномов линейного оператора
Доказательство очевидно. Ниже мы покажем, что определение подпространств собственных полиномов – одна из наиболее важных задач теории программных инвариантов линейных операторов. Рассмотрим теперь задачу построения -
Эти инварианты мы будем называть внутриклеточными. Замечание 3. Система L-инвариантов (18), определяемая через собственные многочлены, задает т.н. орбиту линейного оператора
Можно ожидать, что орбита удовлетворяет соотношению (6):
Теорема 5 определяет так называемые межклеточные инварианты. Именно, пусть пространство собственных полиномов произвольного линейного оператора содержит два различных подпространства - Теорема 6. Пусть Доказательство. Мы можем считать, что дробь
Поскольку несократимые дроби в поле рациональных выражений
Теорема доказана. В заключение сформулируемосновную теорему об Теорема 7. Пусть
Тогда - L-инвариант линейного оператора Доказательство очевидно. Таким образом, проблема описания L-инвариантов линейного оператора Если все собственные числа линейного оператора В случае, когда Литература 1. Годлевский А.Б., Капитонова Ю.В., Кривой С.Л., Летичевский А.А. Итеративные методы анализа программ // Кибернетика. – 1984. – №2, С.23-28. 2. A.Letichevsky, M.Lvov. Discovery of invariant Equalities in Programs over Data fields. Applicable Algebra in Engineering, Communication and Computing. – 1993. – №4. – pp. 21-29 3. Львов М.С. Инвариантные равенства малых степеней в программах, опеределенных над полем. // Кибернетика. – 1988. - №1. – С. 108 – 110. 4. Львов С.М. О реализации вычислений в задачах анализа программ, определенных над векторными пространствами // Проблемы программирования – 2004.-№№2-3. Специальный выпуск. С. 95-101. 5. Львов М.С. Инвариантные неравенства в программах, интерпретированных над упорядоченными полями. // Кибернетика. – 1986. – №5. – С.22-27 6. Müller-Olm M., Seidl H. Computing polynomial program invariants. // Inf. Process. Lett. September 2004.- Vol 91, Issue 5. Elsevier North-Holland, Inc. Amsterdam. - pp. 233-244. 7. Sankaranarayanan S., Sipma H., Manna Z. Non-linear loop invariant generation using Gröbner bases.// Proc. of Symposium on Principles of Programming Languages. - Venice, Italy, January 14-16, 2004. ACM: New York, NY, USA, 2004.- pp. 318-329. 8. Rodríguez-Carbonell E., Kapur D. Automatic generation of polynomial loop invariants: algebraic foundations. // Proc. Of International Symposium on Symbolic and Algebraic Computation.- Santander, Spain, July 4-7, 2004.- ACM: New York, NY, USA 2004.- pp. 266-273. 9. Rodríguez-Carbonell E., Kapur D. Automatic generation of polynomial invariants of bounded degree using abstract interpretation. // Sci. Comput. Program. Volume 64, Issue 1 (January 2007).- Elsevier North-Holland, Inc. Amsterdam, The Netherlands.- 2007.-pp.54-75.
Дата добавления: 2014-01-20; Просмотров: 529; Нарушение авторских прав?; Мы поможем в написании вашей работы! Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет |