Статья
Применение алгоритмов проверки эквивалентности для оптимизации программ
На примере двух моделей программ показано, что задача оптимизации размера программ может быть эффективно решена при помощи процедур проверки эквивалентности программ в рассматриваемых моделях. Основной результат работы – полиномиальные по времени алгоритмы минимизации конечных детерминированных автоматов-преобразователей над конечно порожденными разрешимыми группами и схем последовательных программ, семантика которых определяется конечно порожденными разрешимыми упорядоченными левосократимыми полугруппами. Предложенные алгоритмы можно использовать в качестве теоретической основы для построения эффективных процедур глобальной оптимизации императивных и реагирующих программ.
Эффективная разрешимость проблемы л-т эквивалентности дает возможность приступить к решению задачи минимизации - построения схемы программ наименьшего размера, л-т эквивалентной заданной схеме. Чтобы отыскать ее решение, заметим, что модель вычислений стандартных схем программ сходна модели вычислений автоматов-преобразователей, работающих над полугруппами. Ранее был предложен метод минимизации автоматов-преобра\-зо\-вателей, работающих над упорядоченными левосократимыми полугруппами. В данной заметке мы покажем, что этим методом можно воспользоваться для минимизации стандартных схем программ относительно л-т эквивалентности в случае, когда эти схемы определены над ортогональными консервативными подстановками.
Стандартные схемы программ были введены для разработки математических методов решения задач трансляции, оптимизации и верификации последовательных операторных программ. Ранее было показано, что логико-термальная эквивалентность аппроксимирует функциональную эквивалентность стандартных схем программ. Другое достоинство логико-термальной эквивалентности состоит в том. что это отношение разрешимо за полиномиальное время. Возникает вопрос: можно уточнить отношение логико-термальной эквивалентности, сохранив при этом ее полиномиальную разрешимость? В статье показано, что проблема логико-термальной эквивалентности для недетерминированных стандартных схем программ алгоритмически неразрешима.
Показано, что задача проверки k-значности конечного автомата-преобразователя, работающего над полугруппой, вложимой в разрешимую группу, может быть решена за время, полиномиальное относительно размера автомата.
Автоматы-преобразователи с конечным числом состояний над полугруппами могут служить простой моделью последовательных реагирующих программ. Эти программы работают во взаимодействии с окружающей средой, получая на входе поток управляющих сигналов и выполняя последовательности действий. Как только программа достигает определенного состояния управления, она выдает на выходе текущий результат вычисления. Элементарные действия реагирующей программы можно рассматривать как порождающие элементы некоторой полугруппы, а результат последовательного выполнения этих действий расценивается как элемент полугруппы, представляющий собой композицию этих действий. В данной статье предложен общий подход к решению двух задач анализа вычислений преобразователей такого вида – задачи проверки k-значности конечных преобразователей и задачи проверки эквивалентности k-значных преобразователей. Показано, что обе указанные задач можно свести к задаче поиска опровергающих вершин в ограниченных фрагментах размеченных системах переходов. При помощи предложенного подхода показано, что задача проверки эквивалентности детерминированных конечных преобразователей над полугруппами, которые могут быть вложены в конечно порожденные разрешимые полугруппы, и задача проверки k-значности таких преобразователей разрешимы за полиномиальное время. Кроме того, установлено, что задача проверки эквивалентности k-значных преобразователей разрешима за время, экспоненциальное относительно их размеров.
Журналы событий, сохраняемые современными информационными и техническими системами, как правило, содержат достаточно данных для автоматизированного восстановления моделей соответствующих процессов. Разработано множество алгоритмов для построения моделей процессов, проверки соответствия фактического поведения системы модельному, сравнения моделей процессов, и т.д. Однако возможность быстрого анализа выбираемых пользователями частей журнала до сих пор не нашла полноценной реализации. В статье описан метод многомерного хранения журналов событий для извлечения и анализа процессов, основанный на подходе ROLAP. Результатом анализа журнала является направленный невзвешенный граф, представляющий собою сумму возможных последовательностей событий, упорядоченных по вероятности их возникновения с учетом заданных условий. Разработанный инструмент позволяет выполнять совместный анализ моделей подпроцессов, восстановленных из частей журнала путем задания критериев отбора событий и требуемого уровня детализации модели.
В монографии приведены результаты исследования, посвященного управлению жизненным циклом информационных систем, а также анализу стандартов, сводов знаний и корпоративных методик, использующихся в ИТ-проектах. Приведены характеристики фаз ЖЦИС из практики управления ИТ-проектами, а также практические рекомендации по управлению такими проектами. Книга предназначена для научных работников, сотрудников научно- технических предприятий и работников государственных органов управлений, а также студентов, аспирантов, слушателей бизнес-школ повышения квалификации и переподготовки кадров. Книга содержит практические рекомендации для руководителей ИТ-проектов, а также сотрудников компаний, занимающихся проектной деятельностью в области ИТ-проектов.
The geographic information system (GIS) is based on the first and only Russian Imperial Census of 1897 and the First All-Union Census of the Soviet Union of 1926. The GIS features vector data (shapefiles) of allprovinces of the two states. For the 1897 census, there is information about linguistic, religious, and social estate groups. The part based on the 1926 census features nationality. Both shapefiles include information on gender, rural and urban population. The GIS allows for producing any necessary maps for individual studies of the period which require the administrative boundaries and demographic information.
В данной работе рассматривается пятое уравнение Пенлеве, которое имеет 4 комплексных параметра. Методами степенной геометрии ищутся асимптотические разложения его решений в окрестности его неособой точки z=z0, z0≠0, z0≠∞, при любых значениях параметров уравнения. Показано, что имеется ровно 10 семейств разложений решений уравнения. Все они - по целым степеням локальной переменной z - z0. Из них одно новое; у него произвольный коэффициент при четвертой степени локальной переменной. Одно из семейств однопараметрическое, остальные - двухпараметрические. Доказано, что все разложения сходятся в окрестности (а являющиеся полюсами - в проколотой окрестности) точки z=z0.
В данной работе рассматривается пятое уравнение Пенлеве, которое имеет 4 комплексных параметра α, β, γ, δ. Методами степенной геометрии ищутся асимптотические разложения его решений при x → ∞. При α≠0 найдено 10 степенных разложений с двумя экспоненциальными добавками каждое. Шесть из них - по целым степеням x (они были известны), и четыре по полуцелым (они новые). При α=0 найдено 4 однопараметрических семейства экспоненциальных асимптотик y(x) и 3 однопараметрических семейства сложных разложений x=x(y). Все экспоненциальные добавки, экспоненциальные асимптотики и сложные разложения найдены впервые. Также уточнена техника вычисления экспоненциальных добавок.
В данной работе рассматривается пятое уравнение Пенлеве. Методами степенной геометрии ищутся асимптотические разложения его решений при x → 0. Получено 27 семейств разложений решений уравнения. 19 из них получены из разложений решений шестого уравнения Пенлеве. Среди остальных 8 семейств одно было известно раньше, ещё одно может быть получено из разложения решения третьего уравнения Пенлеве. Новыми являются 3 семейства полуэкзотических разложений, 2 семейства сложных разложений и семейство степенно-логарифмических разложений.
Электронное издание является сборником материалов международной научно-практической конференции "Теория активных систем" (ТАС-2014)