Сборники трудов ИСП РАН


Предисловие.

В.П. Иванников.

Аннотация

19-й том Трудов института системного программирования включает 10 статей, посвященных современным проблемам систем управления данными, поддержки принятия решений, программирования в ограничениях, анализа программ. Две статьи посвящены актуальным для различных приложений алгоритмам упаковки прямоугольников в полосу.

В статье С.Д. Кузнецова «Год эпохи перемен в технологии баз данных» приводится обзор публикаций за 2009 г., посвященных новым подходам к управлению данными (в частности, в среде cloud computing). Анализ проектов, которым посвящены эти публикации, показывают, что идея пересмотра архитектур СУБД всерьез воспринята серьезными исследователями и разработчиками средств управления данными.

В статье того же автора «MapReduce: внутри, снаружи или сбоку от параллельных СУБД?» обсуждаются подходы к использованию технологии MapReduce в аналитических СУБД. Рассматриваются подходы, при которых MapReduce реализуется внутри ядра параллельной СУБД, используется в качестве коммуникационной инфраструктуры новой параллельной СУБД и применяется автономно в симбиотическом единстве с параллельной СУБД.

Также две статьи представили Л.Е. Карпов и В.Н. Юдин. Первая статья называется «Обмен данными в распределенной системе поддержки решений». Под «обменом данными авторы понимают расширение возможностей локальной системы поддержки решений с целью привлечения опыта, накопленного другими пользователями в подобных системах. Рассматриваются два варианта обмена в сети, где присутствуют несколько подобных систем: виртуальная интеграция (аналог консилиума) и консолидация (импорт знаний).

Во второй статье – «Многопараметрическое управление на основе прецедентов» – описываются основные черты нового проекта, связанного с решением задачи многопараметрического управления объектом со сложным взаимным влиянием воздействий в ситуациях, когда влияние внешних факторов может оказаться взаимозависимым и даже противоречивым, когда трудно или невозможно получить точную модель поведения объекта. Предлагается подход к математической формализации понятия управления на теории принятия решений, методов добычи данных и вывода по прецедентам.

Статья «Объектно-ориентированное программирование в ограничениях: новый подход на основе декларативных языков моделирования данных» представили В.А. Семенов, Д.В. Ильин, С.В. Морозов и О.В. Сидяка. OOCP сочетает две о парадигмы программирования: объектно-ориентированное программирование (OOP) и логическое программирование в ограничениях (CLP). До сих пор не существует единого понимания, какие конструктивные очертания может приобрести реализация этого подхода при дальнейшей проработке и развитии. Ключевыми вопросами при этом остаются выразительность описания прикладной задачи в ограничениях и ее алгоритмическая разрешимость. В статье предлагается и обсуждается новый системный подход к реализации OOCP на основе использования декларативных языков моделирования данных.

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

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

В статье Н.Н. Кузюрина и А.И. Поспелова «Вероятностный анализ одного алгоритма упаковки прямоугольников в полосу» предлагается и теоретически исследуется on-line алгоритм упаковки прямоугольников в полубесконечную полосу. Получено, что для незаполненной площади упаковок, порождаемых алгоритмом в среднем, справедлива оценка.

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

Статья И.И. Каретина и В.А. Макарова «Энергосберегающая оптимизация кода за счет использования отключаемых компонентов процессора» посвящена рассмотрению вопросов снижения энергопотребления в процессе исполнения кода программ. Объектом исследования является техника отключения отдельных компонентов процессора. Описываются теоретические аспекты модификации исходного кода с целью повышения энергетического эффекта от отключения компонентов.

Наконец, в статье А.И. Гетьмана, Ю.В. Маркина, В.А. Падаряна и Е.И. Щетинин. «Восстановление формата данных» отмечается, что одной из распространенных практических задач анализа бинарного кода является восстановление структуры полученного программой сетевого сообщения или считанного файла. При работе аналитика с защищенным бинарным кодом трудоемкость восстановления формата данных становится недопустимо большой. Предлагается метод автоматизированного восстановления формата данных, базирующийся на динамическом анализе бинарного кода. Метод позволяет восстановить иерархическую структуру изучаемых данных и выявлять определенную семантику полей.

Издание

Труды Института системного программирования РАН, том 19, 2010, стр. 5-8.

ISSN 2220-6426 (Online), ISSN 2079-8156 (Print).

Полный текст статьи в формате pdf Вернуться к содержанию тома