?
Двусторонняя унификация программ и ее применение для задач рефакторинга
Труды Института системного программирования РАН. 2014. Т. 26. № 2. С. 245-268.
Захаров В. А., Новикова Т. А.
Задача унификации пары подстановок θ_1 и θ_2 состоит в вычислении такой пары подстановок η' и η'', чтобы композиции θ_1 η' и θ_2 η'' были равны. По существу, задача унификации подстановок равносильна задаче решения линейных уравнений вида θ_1 X=θ_2 Y в полугруппе подстановок. Но некоторые линейные уравнения над подстановками также можно рассматривать как новые варианты задачи унификации. В этой статье мы вводим понятие двусторонней унификации как процесса преобразования одной заданной подстановки θ_1 к другой заданной подстановке θ_2 при помощи композиции, применяемой как справа, так и слева к подстановке θ_1. Иначе говоря, задача двусторонней унификации состоит в решении уравнений вида Xθ_1 Y=θ_2. Двусторонняя унификация подстановок может быть использована при решении одной из задач реорганизации (рефакторинга) программ – выделения в заданном фрагменте кода тела библиотечной процедуры с целью последующей замены выделенного участка кода на вызов этой процедуры. В статье исследован вопрос о сложности задачи двусторонней унификации подстановок. Установлено, что эта задача является NP-полной. Доказательство NP-трудности задачи двусторонней унификации проводится путем сведения к ней NP-полной задачи правильного расположения домино в прямоугольной области плоскости. В статье также сформулирована и исследована задача двусторонней унификации программ в модели программ первого порядка с отношением логико-термальной эквивалентности. Доказано, что сформулированная задача двусторонней унификации программ также является NP-полной.
Научное направление:
Компьютерные науки
Приоритетные направления:
компьютерно-математическое
Язык:
русский
Захаров В. А., Новикова Т. А., Труды Института системного программирования РАН 2012 Т. 23 С. 455-476
Унифицировать два алгебраических выражения и означает отыскать такую подстановку термов вместо переменных этих выражений, чтобы оба терма и имели одинаковое значение. Задачу унификации можно распространить и на программы. Унифицировать две программы и означает отыскать такие цепочки присваиваний и ...
Добавлено: 30 сентября 2015 г.
Захаров В. А., Новикова Т. А., Труды Института системного программирования РАН 2012 Т. 22 С. 435-455
Логико-термальная эквивалентность программ – это одно из наиболее слабых отношений эквивалентности программ, аппроксимирующих отношение функциональной эквивалентности и обладающих разрешающим алгоритмом. В данной статье предложена новая модификация алгоритма проверки логико-термальной эквивалентности программ, основанная на операции вычисления точной нижней грани в решетке конечных подстановок. Показано, что трудоемкость предложенного алгоритма оценивается величиной O(n6) , где n - размер ...
Добавлено: 30 сентября 2015 г.
Захаров В. А., Новикова Т. А., Труды Института системного программирования РАН 2011 Т. 21 С. 141-166
Для решения многих задач системного программирования, к числу которых относятся задачи реорганизации программ, деобфускации программ, выявления уязвимостей в программном коде и др., желательно иметь инструментальное средство, позволяющее обнаруживать фрагменты программ, имеющие сходное поведение. Современные средства обнаружения программных клонов позволяют выявлять лишь фрагменты программ, имеющие сходное синтаксическое устройство, поскольку более глубокий семантический анализ программ сталкивается с ...
Добавлено: 30 сентября 2015 г.
Захаров В. А., Труды Института системного программирования РАН 2015 Т. 27 № 2 С. 221-250
Автоматы-преобразователи с конечным числом состояний над полугруппами могут служить простой моделью последовательных реагирующих программ. Эти программы работают во взаимодействии с окружающей средой, получая на входе поток управляющих сигналов и выполняя последовательности действий. Как только программа достигает определенного состояния управления, она выдает на выходе текущий результат вычисления. Элементарные действия реагирующей программы можно рассматривать как порождающие элементы ...
Добавлено: 30 сентября 2015 г.
Захаров В. А., Cybernetics and Systems Analysis 2010 № 4 С. 39-48
В статье показано, каким образом двухленточные автоматы можно применять для проверки эквивалентности последовательных программ. Семантика последовательных программ определяется на основе моделей динамической логики. В том случае, когда динамическая шкала ациклична (т.е. в программе нет взаимно обратимых операторов), она может быть описана двухленточным детерминированным автоматом. Тогда задача проверки эквивалентности программ, семантика операторов которых определяется динамическими ...
Добавлено: 30 сентября 2015 г.
Zakharov V.A., Lecture Notes in Computer Science 2015 Vol. 9270 P. 208-221
Добавлено: 30 сентября 2015 г.
Захаров В. А., Жайлауова Ш. Р., Моделирование и анализ информационных систем 2017 Т. 24 № 4 С. 415-433
Стандартные схемы программ - это одна из наиболее простых моделей последовательных императивных программ, предназначенная для решения задач оптимизации и верификации программ. Мы рассматриваем разрешимое отношение логико-термальной эквивалентности стандартных схем программ и задачу минимизации их размера при условии сохранением отношения логико-термальной эквивалентности. Нами доказано, что эта задача является алгоритмически разрешимой. Далее показано, что стандартные схемы программ ...
Добавлено: 12 октября 2017 г.
Викентьева О. Л., Полякова О. А., Пермь : Издательство Пермского национального исследовательского политехнического университета, 2019
В учебном пособии рассмотрены вопросы применения основных принципов структурного программирования в сложных программных системах на языке высокого уровня С++, которые демонстрируются на содержательных примерах. ...
Добавлено: 16 сентября 2020 г.
Захаров В. А., Кузюрин Н. Н., Варновский Н. П. и др., Программирование 2015 № 6
Обфускацией программ называется такое эквивалентное преобразование программ, которое придает программе форму, затрудняющую понимание алгоритмов и структур данных, используемых программой, и препятствующую извлечению из текста программы определенной полезной информации, содержащейся в ней. Поскольку обфускация программ может найти широкое применение при решении многих задач криптографии и компьютерной безопасности, задаче оценки стойкости обфускации придается очень большое значение, начиная ...
Добавлено: 13 октября 2015 г.
Захаров В. А., Новикова Т. А., В кн. : Дискретные модели в теории управляющих систем : IX Международная конференция, Москва и Подмосковье, 20-22 мая 2015 г.: Труды. : М. : МАКС Пресс, 2015. С. 173-176.
В статье предложена новая модель последовательных императивных программ, использующих средства работы с динамической памятью (указателями, списками и пр.) ...
Добавлено: 12 октября 2015 г.
Zakharov V.A., Kuzurin N. N., Varnovsky N. P. и др., Programming and Computer Software 2015 Vol. 41 No. 6 P. 361-372
Program obfuscation is a semantic-preserving transformation aimed at bringing a program into a form that impedes understanding of its algorithm and data structures or prevents extracting certain valuable information from the text of the program. Since obfuscation may find wide use in computer security, information hiding and cryptography, security requirements to program obfuscators have become ...
Добавлено: 13 октября 2015 г.
Захаров В. А., Жайлауова Ш. Р., В кн. : Проблемы теоретической кибернетики: XVIII международная конференция (Пенза, 19-23 июня 2017 г.). : М. : МГУ, МАКС Пресс, 2017. С. 84-87.
Эффективная разрешимость проблемы л-т эквивалентности дает возможность приступить к решению задачи минимизации - построения схемы программ наименьшего размера, л-т эквивалентной заданной схеме. Чтобы отыскать ее решение, заметим, что модель вычислений стандартных схем программ сходна модели вычислений автоматов-преобразователей, работающих над полугруппами. Ранее был предложен метод минимизации автоматов-преобра\-зо\-вателей, работающих над упорядоченными левосократимыми полугруппами. В данной заметке мы ...
Добавлено: 22 октября 2017 г.
Turkensteen M., Малышев Д. С., Гольденгорин Б. И. и др., Journal of Global Optimization 2017 Vol. 68 No. 3 P. 601-622
Добавлено: 10 декабря 2016 г.
В статье исследуется глобальная эволюция мирового сообщества как единой самоорганизующейся и саморазвивающейся системы (Мир-Системы) и выявляются основные характеристики и закономерности этой эволюции. При этом внимание фокусируется на рассмотрении цикличности эволюции, периодизации глобальной истории человечества, росте сложности и рождении технологических, социальных и культурных инноваций в результате прохождения кризисов. Исследование строится как междисциплинарное и опирается на результаты ...
Добавлено: 18 ноября 2013 г.
Канович М. И., Ban Kirigin T., Nigam V. и др., Computer Languages, Systems & Structures 2014 No. 40 P. 137-154
Добавлено: 23 марта 2015 г.
Yaroslavl : Ярославский государственный университет им. П.Г. Демидова, 2018
Добавлено: 26 октября 2018 г.
Yenigün H., N.Yevtushenko, Kushik N. и др., Proceedings of the Institute for System Programming of the RAS 2018 Vol. 30 No. 1 P. 7-24
Добавлено: 9 октября 2019 г.
Kontchakov R., Pratt-Hartmann I., Захарьящев М. В., Artificial Intelligence 2014 Vol. 217 P. 43-75
Добавлено: 24 марта 2015 г.
Рубчинский А. А., / Высшая школа экономики. Series WP7 "Математические методы анализа решений в экономике, бизнесе и политике". 2015. No. WP7/2015/09.
An algorithm of solution of the Automatic Classification (AC for brevity) problem is set forth in the paper. In the AC problem, it is required to find one or several partitions, starting with the given pattern matrix or dissimilarity / similarity matrix. The three-level scheme of the algorithm is suggested. The output of the procedure ...
Добавлено: 19 октября 2017 г.
Funchal : SciTePress, 2018
This book contains the proceedings of the 3rd International Conference on Complexity, Future Information Systems and Risk (COMPLEXIS 2018) which was organized and sponsored by the Institute for Systems and Technologies of Information, Control and Communication (INSTICC). This conference was technically co-sponsored by World Federation on Soft Computing (WFSC) and also held in cooperation with ...
Добавлено: 2 июня 2018 г.
Berlin : Springer, 2013
This book constitutes the refereed proceedings of the 24th Annual Symposium on Combinatorial Pattern Matching, CPM 2013, held in Bad Herrenalb (near Karlsruhe), Germany, in June 2013. The 21 revised full papers presented together with 2 invited talks were carefully reviewed and selected from 51 submissions. The papers address issues of searching and matching strings ...
Добавлено: 30 октября 2013 г.
Фомичев М. И., Ульянов М. В., Головешкин В. А. и др., International Journal of Open Information Technologies 2016 Т. 4 № 12 С. 131-137
На основе статистического анализа сложности индивидуальной задачи коммивояжера, решаемой методом ветвей и границ, показано, что распределение логарифма сложности удовлетворительно аппроксимируется нормальным распределением. Коэффициенты линейной регрессии выборки логарифма сложности на стандартное нормальное распределение использовались для оценки значений параметров аппроксимирующего нормального распределения. Даны оценки границ 90% интервала сложности. ...
Добавлено: 19 августа 2017 г.
Berlin : Springer, 2013
This book constitutes the refereed proceedings of the 24th Annual Symposium on Combinatorial Pattern Matching, CPM 2013, held in Bad Herrenalb (near Karlsruhe), Germany, in June 2013. The 21 revised full papers presented together with 2 invited talks were carefully reviewed and selected from 51 submissions. The papers address issues of searching and matching strings ...
Добавлено: 30 октября 2013 г.