?
Полиномиальный по времени алгоритм проверки логико-термальной эквивалентности программ
Труды Института системного программирования РАН. 2012. Т. 22. С. 435-455.
Захаров В. А., Новикова Т. А.
Логико-термальная эквивалентность программ – это одно из наиболее слабых отношений эквивалентности программ, аппроксимирующих отношение функциональной эквивалентности и обладающих разрешающим алгоритмом. В данной статье предложена новая модификация алгоритма проверки логико-термальной эквивалентности программ, основанная на операции вычисления точной нижней грани в решетке конечных подстановок. Показано, что трудоемкость предложенного алгоритма оценивается величиной O(n6) , где n - размер анализируемых программ. Полученная верхняя оценка сложности задачи проверки логико-термальной эквивалентности программ существенно меньше ранее известных полиномиальных оценок сложности указанной задачи.
Научное направление:
Компьютерные науки
Приоритетные направления:
компьютерно-математическое
Язык:
русский
Захаров В. А., Новикова Т. А., Труды Института системного программирования РАН 2012 Т. 23 С. 455-476
Унифицировать два алгебраических выражения и означает отыскать такую подстановку термов вместо переменных этих выражений, чтобы оба терма и имели одинаковое значение. Задачу унификации можно распространить и на программы. Унифицировать две программы и означает отыскать такие цепочки присваиваний и ...
Добавлено: 30 сентября 2015 г.
Захаров В. А., Новикова Т. А., Труды Института системного программирования РАН 2014 Т. 26 № 2 С. 245-268
Задача унификации пары подстановок θ_1 и θ_2 состоит в вычислении такой пары подстановок η' и η'', чтобы композиции θ_1 η' и θ_2 η'' были равны. По существу, задача унификации подстановок равносильна задаче решения линейных уравнений вида θ_1 X=θ_2 Y в полугруппе подстановок. Но некоторые линейные уравнения над подстановками также можно рассматривать как новые варианты задачи ...
Добавлено: 30 сентября 2015 г.
Захаров В. А., Новикова Т. А., Труды Института системного программирования РАН 2011 Т. 21 С. 141-166
Для решения многих задач системного программирования, к числу которых относятся задачи реорганизации программ, деобфускации программ, выявления уязвимостей в программном коде и др., желательно иметь инструментальное средство, позволяющее обнаруживать фрагменты программ, имеющие сходное поведение. Современные средства обнаружения программных клонов позволяют выявлять лишь фрагменты программ, имеющие сходное синтаксическое устройство, поскольку более глубокий семантический анализ программ сталкивается с ...
Добавлено: 30 сентября 2015 г.
Захаров В. А., Cybernetics and Systems Analysis 2010 № 4 С. 39-48
В статье показано, каким образом двухленточные автоматы можно применять для проверки эквивалентности последовательных программ. Семантика последовательных программ определяется на основе моделей динамической логики. В том случае, когда динамическая шкала ациклична (т.е. в программе нет взаимно обратимых операторов), она может быть описана двухленточным детерминированным автоматом. Тогда задача проверки эквивалентности программ, семантика операторов которых определяется динамическими ...
Добавлено: 30 сентября 2015 г.
Захаров В. А., Труды Института системного программирования РАН 2015 Т. 27 № 2 С. 221-250
Автоматы-преобразователи с конечным числом состояний над полугруппами могут служить простой моделью последовательных реагирующих программ. Эти программы работают во взаимодействии с окружающей средой, получая на входе поток управляющих сигналов и выполняя последовательности действий. Как только программа достигает определенного состояния управления, она выдает на выходе текущий результат вычисления. Элементарные действия реагирующей программы можно рассматривать как порождающие элементы ...
Добавлено: 30 сентября 2015 г.
Захаров В. А., Жайлауова Ш. Р., Моделирование и анализ информационных систем 2017 Т. 24 № 4 С. 415-433
Стандартные схемы программ - это одна из наиболее простых моделей последовательных императивных программ, предназначенная для решения задач оптимизации и верификации программ. Мы рассматриваем разрешимое отношение логико-термальной эквивалентности стандартных схем программ и задачу минимизации их размера при условии сохранением отношения логико-термальной эквивалентности. Нами доказано, что эта задача является алгоритмически разрешимой. Далее показано, что стандартные схемы программ ...
Добавлено: 12 октября 2017 г.
Захаров В. А., Варновский Н. П., Кузюрин Н. Н. и др., Труды Института системного программирования РАН 2014 Т. 26 № 3 С. 167-198
Обфускацией программ называется такое эквивалентное преобразование программ, которое придает программе форму, затрудняющую понимание алгоритмов и структур данных, реализуемых программой, и препятствующую извлечению из текста программы определенной секретной информации, содержащейся в ней. Поскольку обфускация программ может найти широкое применение при решении многих задач криптографии и компьютерной безопасности, задаче оценки стойкости обфускации придается очень большое значение, начиная ...
Добавлено: 30 сентября 2015 г.
Кириченко А. А., М. : Государственный университет-Высшая школа экономики, 2015
Объектно-ориентированный стиль программирования требует от программиста повышенной квалификации из-за сложности языка. В учебном пособии проводится анализ архитектуры таких стилей программирования, как визуальное (точнее – событийное), и объектно-ориентированное программирование, вводятся ограничения на использование пакета Visual Studio при объектно-ориентированном программировании и формулируются способы коррекции программного проекта для сохранения базовых принципов инкапсуляции. Изложенная методика создания и приведенные примеры ...
Добавлено: 4 декабря 2015 г.
Кириченко А. А., М. : ИПЦ "Маска", 2010
Монография представляет собой результат исследования проблемы повышения производительности работы программиста в рыночных условиях. Для рыночных условий характерно, что разрабатываемые программы должны представлять собой пусть не лучший, но работающий продукт, соответствующий определённым потребностям рынка. Такие программы могут быть созданы за счёт комплексирования программных средств, то есть за счёт сборки программных средств из существующих программ, часто разработанных ...
Добавлено: 29 марта 2013 г.
Zakharov V.A., Lecture Notes in Computer Science 2015 Vol. 9270 P. 208-221
Добавлено: 30 сентября 2015 г.
Кириченко А. А., М. : ГУ-ВШЭ, 2016
Монография представляет собой результат изучения проблемы нейросетевого исследования. Для проведения такого исследования необходимы нейросетевые пакеты и программные комплексы, различные инструменты (алгоритмы, программы, методики) и технологии. Чаще всего требуемые средства отсутствуют или доступны по запредельным ценам. Относительно несложные инструменты, необходимые для исследования, могут быть изготовлены самостоятельно за счёт комплексирования программных средств, технология которого связана с использованием ...
Добавлено: 28 декабря 2016 г.
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 г.
Yaroslavl : Ярославский государственный университет им. П.Г. Демидова, 2018
Добавлено: 26 октября 2018 г.
М. : МГУ, МАКС Пресс, 2017
Книга представляет собой сборник статей, написанных на основе докладов, представленных на 18-ой Международной конференции "Теоретические проблемы кибернетики" в Пензенском государственном университете, 19-23 июня 2017 г. ...
Добавлено: 12 октября 2017 г.
Макарова Т. Л., Макаров С. Л., Известия высших учебных заведений. Технология текстильной промышленности 2017 № 3 (369) С. 175-179
В статье приведён анализ символа "животное" в дизайне современного костюма (в системе "костюм-среда" за период 1981-2010 гг.), а также рассмотрено использование результатов анализа в дальнейшей разработке базы данных и компьютерной программы "Система символов костюма" ...
Добавлено: 19 ноября 2017 г.
М. : Издательский центр «Российский государственный гуманитарный университет», 2019
Сборник включает 27 докладов международной конференции по компьютерной лингвистике и интеллектуальным технологиям «Диалог 2019», не вошедшие в ежегодник «Компьютерная лингвистика и интеллектуальные технологии», но рекомендованные Программным Комитетом к представлению на конференции. Для специалистов в области теоретической и прикладной лингвистики и интеллектуальных технологий. ...
Добавлено: 10 декабря 2019 г.
Карпов В. Э., Карпова И. П., Procedia Engineering 2015 Vol. 100 P. 1459-1468
Добавлено: 14 марта 2015 г.
Chernyshev S. V., Cherepanov E. A., Pankratiev E. V. и др., Journal of Mathematical Sciences 2005 Vol. 128 No. 6 P. 3487-3495
Добавлено: 27 января 2014 г.
Chuprikov P., Николенко С. И., Davydow A. и др., IEEE Transactions on Networking 2018 Vol. 26 No. 1 P. 342-355
Добавлено: 14 марта 2018 г.
В статье представлена технология, позволяющая собирать в полевых исследованиях пространственно локализованные данные об объектах городской среды. Технология основана на автоматической привязке фотографий к пространственным координатам. Приведен план полевых и камеральных мероприятий, предложены варианты ГИС-обработки собираемых таким образом данных. В качестве примера приведены данные об использовании белорусского языка в общественном пространстве городов Белоруссии. ...
Добавлено: 12 апреля 2015 г.
Сотникова С. Ю., Динамика сложных систем 2012 № 3 С. 84-87
В статье описывается разработанный программный комплекс моделирования физических процессов, который также позволяет проводить идентификацию параметров печатного узла (физической модели), на котором реализуется проектируемый бортовой источник вторичного электропитания. Для него разработаны интерфейсы связи управляющей программы с известными программами моделирования и оптимизации. ...
Добавлено: 5 декабря 2014 г.
Skoptsov K. A., Sheshenin S., Галатенко В. В. и др., International Journal of Applied Mechanics 2016 Vol. 8 No. 2 P. 1650016-01-1650016-18
We present a method for evaluating elastic properties of a composite material produced by molding a resin filled with short elastic fibers. A flow of the filled resin is simulated numerically using a mesh-free method. After that, assuming that spatial distribution and orientation of fibers are not significantly changed during polymerization, effective elastic moduli of ...
Добавлено: 22 мая 2016 г.
Малышев Д. С., Discrete Mathematics 2015 Vol. 338 No. 11 P. 1860-1865
We completely determine the complexity status of the 3-colorability problem for hereditary graph classes defined by two forbidden induced subgraphs with at most five vertices. © 2015 Elsevier B.V. All rights reserved. ...
Добавлено: 7 апреля 2014 г.