научный журнал по математике Программирование ISSN: 0132-3474

ПОДЛОВЧЕНКО Р.И. — 2011 г.

В статье изучается задача проверки эквивалентности схем программ в уравновешенных полугрупповых моделях программ. Для этой задачи предложен метод построения разрешающих алгоритмов в том случае, если полугрупповая модель программ обладает свойством левого сокращения h\hi = h\h^ => hi = hs- Показано также, что проверку эквивалентности схем программ можно осуществить за время, полиномиально зависящее от размеров проверяемых схем, если уравновешенная полугрупповая модель программ наряду со свойством левого сокращения обладает также и свойством правого сокращения h^hi = НДг\ => h<2 = Ъ,%.

СМЕЛЯНСКИЙ Р.Л. — 2011 г.

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

КУЛЯМИН В.В., ПЕТУХОВ А.А. — 2011 г.

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

КАМКИН А.С., ЧУПИЛКО М.М. — 2011 г.

Работа представляет собой сравнительный анализ современных подходов к имитационной верификации (тестирования) моделей аппаратуры: AVM (Advanced Verification Methodology) от компании Mentor Graphics, OVM (Open Verification Methodology) - совместной разработки Mentor Graphics и Cadence Design Systems - и технологии UniTESK (Unified TEsting and Specification tool Kit), разработанной в Институте Системного Программирования РАН. В статье анализируются сильные и слабые стороны различных подходов, сопоставляются архитектуры тестовых систем, даются рекомендации по развитию технологии UniTESK и ее унификации с методологией OVM, набирающей все большее распространение и претендующей на то, чтобы стать стандартом в области верификации аппаратного обеспечения.

РЯБЕНКО А.А. — 2011 г.

Рассматривается определенное суммирование гипергеометрических термов двух переменных. В настоящее время в системах компьютерной алгебры для суммирования таких термов используется сочетание алгоритма Цейлбергера и дискретного аналога формулы Ньютона-Лейбница, что, как известно, не всегда дает правильный результат. Мы предлагаем несложное предварительное исследование терма перед использованием алгоритма Цейлбергера. Если гипергеометрический терм относится к описываемому нами виду, то использование алгоритма Цейлбергера будет корректным, или, даже, в его использовании не будет необходимости.

ФЕДОРОВ А.В. — 2011 г.

Библиотека NPTL полностью поддерживает нити POSIX - один из самых популярных интерфейсов для создания многопоточных приложений. Она постепенно перерабатывается с учетом требований систем реального времени, но на настоящее время подходит только для систем мягкого реального времени. В статье описываются причины, по которым библиотека не соответствует требованиям жесткого реального времени, и делается попытка их устранить.

ЗАВРИЕВ Н.К. — 2011 г.

Описан подход к реализации учебного плана профиля „Технологии программирования" в старших классах, в котором развитие у учащихся навыков разработки собственных алгоритмов сочетается с освоением конкретных языков и технологий.

ГАВРИЛОВА Э.А. — 2011 г.

В настоящей статье описана реализация информационно-поисковой системы высшего учебного заведения по технологии Semantic Web. Портал спроектирован на основе платформы «Научный институт». Описаны разработанная автором онтология предметной области, архитектура системы, ее ресурсы и сервисы.

ВОЛЬФ Т. — 2011 г.

Данная статья преследует две цели. Во-первых, возможно непосредственно прикладное использование полученного нами алгоритма для получения параметрического решения недоопределенных линейных обыкновенных дифференциальных уравнений с коэффициентами, являющимися произвольными аналитическими функциями одной переменной. Второй важной целью служит построение алгоритма, в определенном смысле двойственного к фундаментальному алгоритму Евклида и, как следствие, альтернативного алгоритму построения дифференциального базиса Гребнера в данном специальном случае. В статье сравниваются алгоритм Евклида и его <дуальная> версия, анализируется их вычислительная мощность на примере решения недоопределенных линейных обыкновенных дифференциальных уравнений. Реализация описанного в статье алгоритма доступна в интерактивном режиме по ссылке [7].

БУРДОНОВ И.Б., КОСАЧЕВ А.С. — 2011 г.

Статья посвящена проблемам отношения ioco, определяющего соответствие (конформность) реализации спецификации. Рассматриваются проблемы нерефлексивности отношения ioco, наличие в спецификации неконформных (отсутствующих в любой конформной реализации) трасс, несохранение ioco при композиции (композиция реализаций, конформных своим спецификациям, может быть неконформна композиции этих спецификаций) и проблема "ложных" ошибок при тестировании в контексте. Для решения этих проблем в статье предлагается алгоритм пополнения спецификации, по отношению к которому ioco инвариантно (сохраняется класс конформных реализаций). На классе пополненных спецификаций указанные проблемы отсутствуют.

ГОГИН Н., МЮЛЛЯРИ А. — 2011 г.

В статье получена явная формула для весового многочлена автокорреляции q-арных слов, позволяющая легко вычислять ее весовые коэффициенты стандартными алгоритмическими средствами компьютерной алгебры.

ДИМОВСКИ И.Х., СПИРИДОНОВА М.Н. — 2011 г.

В работе рассматривается возникновение резонансных колебаний в линейных упругих системах (на примере струны и балки), которые являются результатом нелокальных краевых условий, даже при отсутствии внешних сил. Приводятся точные решения соответствующих краевых задач. По формулам решения удобно получать их численные значения и строить соответствующие графики. Система компьютерной алгебры Mathematica использована для вывода и анализа точного решения, а также для разработки программных пакетов, позволяющих удобное проведение численных расчетов по выведенным формулам и визуализацию решения. Авторы считают, что представленное исследование можно применить при попытке объяснения причин колебаний Такомского и Волгоградского мостов (возникших соответственно в 1940 и 2010 годах).

АБРАМОВ С.А., ГЕФФАР А., ХМЕЛЬНОВ Д.Е. — 2011 г.

Исследуются сложности некоторых известных алгоритмов поиска рациональных решений линейных разностных уравнений с полиномиальными коэффициентами.

АБРАМОВ С.А., БОГОЛЮБСКАЯ А.А., ЕДНЕРАЛ В.Ф., РОСТОВЦЕВ В.А. — 2011 г.

КАПЦОВ О.В. — 2011 г.

В работе рассматриваются нелинейные переопределенные системы уравнений в частных производных с двумя независимыми переменными и любым числом искомых функций. Получен эффективный критерий конечномерности многообразия решений некоторого класса таких систем. Дана оценка типа Безу размерности многообразия решений и найдены алгебраические условия, при выполнении которых эта оценка достигается. На этой основе предложен метод построения матричного преобразования Дарбу линейных систем уравнений второго порядка. Работа выполнена при финансовой поддержке Российского фонда фундаментальных исследований (проект 11-01-00049), СО РАН (интеграционный проект 103) и гранта поддержки ведущих научных школ НШ-7256.2010.1.

ИГНАТЕНКО А.В., ФРОЛОВ В.А., ХАРЛАМОВ А.А. — 2011 г.

В данной работе представлен подход к синтезу фотореалистичных изображений на графических процессорах (GPU). В его основе лежит сочетание алгоритмов кэширования освещённости с когерентной адаптивной трассировкой путей.

БАРЛАДЯН Б.Х., ВОСТРЯКОВ К.А., ГАЛАКТИОНОВ В.А., ЖДАНОВ Д.Д., ПОТЕМИН И.С., ШАПИРО Л.З. — 2011 г.

Данная статья посвящена анализу ошибок цветопередачи, возникающих при компьютерном построении изображений сцен со сложными оптическими свойствами. В работе произведен анализ причин возникновения ошибок цветопередачи при построении изображений в RGB пространстве, и предложен эффективный и аккуратный алгоритм решения задач построения спектрального изображения. Предложенные решения были реализованы для программ прямой стохастической и обратной детерминистической трассировки лучей. Кроме того, для сложных сцен, содержащих смесь оптических свойств, определенных в различных моделях, включая RGB, было предложено эффективное и аккуратное решение для приведения всех оптических свойств к единой спектральной модели.

БУЛЫЧЕВ П.Е. — 2011 г.

Одним из наиболее распространенных методов проверки правильности программ является верификация моделей программ. В этом методе проверяется не сама программа, а её модель, задаваемая структурой Крипке (размеченной системой переходов). Спецификация обычно задаётся формулой темпоральной логики. Во многих подзадачах верификации моделей программ используются отношения, заданные на множестве моделей и сохраняющие выполнимость формул темпоральных логик. Существует целый ряд таких отношений, и они называются отношениями симуляции. В настоящей статье предложена программная система, предназначенная для проверки широкого класса отношений симуляции между конечными моделями программ. В основу этой системы положен теоретико-игровой подход к проверке симуляции. Система состоит из двух компонентов: формального языка, позволяющего описывать различные симуляции в терминах антогонистической игры двух игроков, и программно-инструментального средства, которое по двум размеченным системам переходов и описанию симуляции проверяет, выполняется ли заданная симуляция между этими системами переходов.

ИЛЬИН В.П., СКОПИН И.Н. — 2011 г.

Обсуждаются проблемы, стоящие перед вычислительным программированием сегодня и в связи с грядущим переходом к использованию экзафлопcного оборудования. В качестве основы изложения рассматривается жизненный цикл математического моделирования и связанные с ним общие задачи, которые решаются при разработке моделей. Это направление является и всегда будет одним из главных потребителей вычислительных ресурсов. Изучение его подходов и методов позволяет сформулировать основные направления целесообразного развития, обусловленные необходимостью формирования технологий вычислительного программирования.

ПЛАКСИН М.А. — 2011 г.

Статья посвящена анализу требований к курсу информатики, предъявляемых формирующимся информационным обществом. В качестве средства решения предлагается курс ТРИЗформатики -„Пермской версии" пропедевтического курса информатики, которая объединяет в себе компьютерные и интеллектуальные технологии работы с информацией. Описано содержание курса и изданный учебно-методический комплекс.