Под редакцией проф. Виктора Николаевича Касьянова
Серия "Конструирование и оптимизация программ"
Новосибирск 2002
Сборник является девятым в серии книг, издаваемых Институтом
систем информатики им. А.П. Ершова СО РАН по проблемам конструирования и оптимизации программ. Он посвящен решению актуальных
задач конструирования эффективных и надежных программ и систем
на основе теоретико-графовых методов, функционального программирования, сетевой обработки и средств визуализации.
Сборник представляет интерес для системных программистов, а также студентов и аспирантов, специализирующихся в области системного и теоретического программирования.
Сборник в формате PDF
Иерархический подход для автоматического размещения ациклических графов
Данная статья представляет собой обзор методологии для конструирования геометрического изображения ациклических графов. Для подчеркивания иерархичности структуры таких графов используются поуровневые представления, в которых все дуги следуют одному и тому же направлению.
Иерархический подход содержит три основные части.
- Распределение вершин по уровням так, чтобы все дуги следовали одному направлению.
- Выбор порядка вершин на уровне с целью минимизации пересечения ребер.
- Определение координат вершин на уровне с целью минимизации общей длины ребер и количества изломов.
Обзор содержит детальное описание каждой из частей алгоритма. Автор
приводит различные способы решения задач того или иного этапа с указанием первоисточников, а также проводит сравнение этих решений по удовлетворяемым эстетическим критериям и временной сложности. Помимо решения перечисленных задач, в обзоре затронуты смежные вопросы (расстановка меток, инкрементальные размещения, открытые проблемы) и описан ряд методов для сведения произвольного графа к ациклическому.
|
Методы и технологии адаптивной гипермедиа
Адаптивная гипермедиа - относительно новое направление исследований на
стыке гипермедиа и моделирования пользователя. Адаптивные гипермедиасистемы формируют модель пользователя из целей, знаний, предпочтений
и других характеристик индивидуального пользователя и используют ее в
течение взаимодействия для адаптации к потребностям этого пользователя.
Статья содержит краткий обзор существующих на данный момент методов
и технологий адаптивного представления содержания и адаптивной навигационной поддержки.
|
Транслирующие компоненты системы функционального программирования SFP
В данной работе описывается система функционального программирования
SFP и ее компоненты: транслятор, средства отладки, внутреннее представление Sisal-программ, конвертер Sisal-программ в программы на языке Си.
Также рассматривается тестирование транслирующих компонент системы.
|
Алгоритмы быстрого поиска фрагментов фотографических изображений
Поиск фрагментов в изображениях - важная задача, возникающая во многих отраслях человеческой деятельности. При этом поиск должен осуществляться максимально быстро.
Цель данной работы - создание алгоритмов и программ, обнаруживающих
заданный фрагмент на изображении. Представленная программа состоит из
двух частей - вычислительного ядра и управляющей оболочки, осуществляющей пользовательский интерфейс.
Главное преимущество нового подхода состоит в том, что все образцы разыскиваются одновременно. Разработанный алгоритм является одним из лучших в мире.
|
В статье исследованы методы принятия решения в теории решения изобретательских задач (ТРИЗ) и их применение к проблеме разрешения конфликтов. Рассмотрен алгоритм АРИЗ и его аналог для решения конфликтных
ситуаций АРПС. Описана графическая оболочка TRIZ_Computing для разбора конфликта. В программе разобраны несколько примеров.
|
Автоматизация методов принятия решений на железнодорожном транспорте как гарантия обеспечения безопасности движения
В статье представлен комплекс АРМов цеха эксплуатации, называемых АРМ
ТЧБ (Арм Нарядчика, Арм Зав.Бригадами). АРМ ТЧБ разработан в рамках
концепции автоматизированной системы управления локомотивным хозяйством (АСУТ), разработанной по заданию Департамента локомотивного хозяйства в Отраслевом Центре Внедрения МПС совместно с ВНИИЖТ, ВНИ-ИАС, Красноярской и Московской железными дорогами и другими предприятиями железнодорожного транспорта.
Основное назначение системы - полностью исключить ошибки оперативного персонала при формировании и использовании локомотивных бригад и
машинистов, работающих в одно лицо (только машинист, без помощника на
специально оборудованном локомотиве). Система также предназначена для
оптимизации процесса управления работой локомотивных бригад. Еще одной не менее важной задачей АРМ ТЧБ (в комплексе с АРМ ТЧД) является
автоматизация подготовки и отправки в систему оперативного контроля за
дислокацией бригад (ОКДБ) сообщений о дислокации и состояниях бригад
в реальном масштабе времени.
|
Конвейерная модель перевозок как модель пересылки протяженных сообщений
В данной работе показано, что наиболее близкой к задаче о "червеобразной" модели пересылки сообщений в мультипроцессорных системах является сетевая транспортная задача о перевозках однородного груза на основе конвейерной модели.
|
Развитие NUMA-архитектуры: текущее состояние
Цель этой статьи - рассмотреть динамику развития NUMA-архитектур за последние 10 лет.
|
Обзор MPEG-подобных методов кодирования видеоданных
Рассмотрены основные методы кодирования видеоданных, использующиеся
в MPEG-подобных форматах: поиск векторов движения, кодирование остаточного изображения, сжатие данных специального вида.
|
Виртуальный музей истории информатики в Сибири
В статье представлен проект создания виртуального музея истории информатики в Сибири. Кратко описана сибирская школа информатики и программирования, рассматривается структура виртуального музея и его содержимое, описывается пользовательский интерфейс и изучаются вопросы
адаптивной гипермедиа.
|
Пользовательский интерфейс интегрированной среды функционального программирования SFP
Публикация посвящена работе, которая является частью проекта по созданию интегрированной среды программирования для функционального языка Sisal. В статье описан интерфейс к интегрированной среде программирования функционального языка Sisal, а также некоторые компоненты, такие
как редактор, транслятор.
|
ИС ТРАНСФОРМ: Автоматизация наполнения системы
Статья посвящена описанию результатов опытной эксплуатации ИС ТРАНСФОРМ и возможностям ее дальнейшего развития. Так же рассматриваются
существующие методы индексации и возможные подходы к решению проблемы адекватного автоматического индексирования документов и извлечения
из них сопутствующей информации.
|
Проект системы для быстрого прототипирования распараллеливающего компилятора. Универсальное внутреннее представление системы
В первой части статьи представлен проект исследовательско-обучающей системы для быстрого создания прототипа распараллеливающего компилятора. Приведены поставленные перед системой задачи и их связь с процессом
создания компилятора. Дано описание архитектуры создаваемой системы,
ее составных частей, относящихся к определенным этапам работы транслирующей системы и основных компонентов, таких как расширяемое универсальное внутреннее представление (ВП), сценарий и язык сценария системы.
Во второй части статьи детально рассмотрено ВП системы и его языковая
и графовая составляющие. Введены понятия абстрактного синтаксического
графа и графовых теней для исследования различных теоретико-графовых
внутренних представлений программ.
|
Путевые ядра и длины циклов в неориентированных графах
Через τ(G) обозначим количество вершин в наиболее длинном пути конечного неориентированного графа G. Подмножество K множества вершин V графа G называется Pn-ядром графа G, если τ(G[K]) ≤ n-1 и каждая вершина из множества V (G\K) смежна с вершиной, которая является конечной вершиной для пути длины n в графе G. В данной статье доказана теорема о существовании Pn-ядра в графе, длина максимального цикла в котором равна n-2.
|
Слежение и определение скорости движущихся на плоскости объектов в реальном времени
В данной статье описан программный логический модуль для системы отслеживания движения объектов в реальном времени. На вход поступают
изображения, полученные с неподвижно закрепленной видеокамеры, на выходе имеются данные об объектах, которые попали в поле зрения. В качестве
аппаратной части выступает обычный компьютер класса Pentium-2.
|
Оптимальное размещение информации в вычислительных системах с учетом структурной надежности компонентов
Данная статья посвящена проблеме оптимального размещения данных в информационных системах. Рассматривается случай распределенной клиент-серверной системы. В статье предложена методика оптимального размещения таблиц по серверам баз данных. Предлагаемый подход учитывает не
только параметры быстродействия системы, пропускную способность каналов, но и надежность компонентов системы. Приведенная методика может
быть использована при проектировании вычислительных систем.
|
|