Под редакцией проф. Виктора Николаевича Касьянова
Серия "Конструирование и оптимизация программ"
Новосибирск 2001
Является седьмым в серии сборников, издаваемых Институтом систем информатики СО РАН по проблемам конструирования и оптимизации программ. Посвящен решению актуальных задач разработки
методов и средств, повышающих эффективность использования супервычислителей и телекоммуникационных сетей.
Сборник представляет интерес для системных программистов, а также студентов и аспирантов, специализирующихся в области системного
и теоретического программирования.
Сборник в формате PDF
О работе 16 Всемирного компьютерного конгресса ИФИП
Представлен обзор работ 16-го Всемирного компьютерного конгресса, проходившего в августе 2000-го года в Пекине под лозунгом "Обработка информации. За рубежом 2000 года". Компьютерные конгрессы, проводимые
ИФИП, являются главным мировым научным форумом в области информационных технологий, на котором рассматриваются основные проблемы и
наиболее важные результаты в современной информатике.
|
Анализ зависимостей по данным на базе алгоритма Шостака
При распараллеливании программ одной из основных проблем является выявление зависимостей по данным. В настояшей статье строится точный тест
для анализа зависимостей по данным, основанный на исследовании разрешимости системы линейных неравенств с двумя переменными на базе алгоритма Шостака. В данной работе приводится модель входной программы,
описываются алгоритм Шостака и его модификация, а также программная
реализация проекта.
|
NUMA-архитектура: некоторые особенности компиляции и генерации кода
Обсуждаются некоторые особенности компиляции и генерации кода для
NUMA-архитектур, дается определение понятия NUMA-архитектуры, приводятся различия между мультипроцессорами и мультикомпьютерами, перечисляются машины с NUMA-архитектурой, описываются особенности программного обеспечения NUMA-машин, затрагиваются вопросы реструктуризации циклов, порогового планирования графа заданий, унифицирующих
преобразований данных и управления, а также представлен обзор работ, имеющих непосредственное отношение к реструктуризации циклов и преобразованиям данных и управления.
|
Функциональный язык Sisal 3.0
Представлен язык функционального программирования Sisal 3.0, выбранный в качестве начальной версии входного языка системы функционального
программирования СФП, разрабатываемой в ИСИ СО РАН при финансовой
поддержке РФФИ (грант N 98-01-00748). В работе кратко описаны семантические и синтаксические характеристики этого языка, а также сделан обзор
материалов, связанных с проблематикой языка Sisal 3.0.
|
Параллельный алгоритм решения задачи о взаимодействии потоков разреженной плазмы
Исследуется параллельный алгоритм решения задачи о взаимодействии потоков разреженной плазмы. Рассматривается простейшая параллельная архитектура. В рамках некоторых естественных предположений сделаны оценки времени выполнения алгоритма в параллельном и последовательном случаях, а также коэфициента ускорения.
|
О распараллеливании метода "МЕДУЗА"
Рассматриваются вопросы, возникающие при распараллеливании метода "МЕДУЗА", который используется для решения ряда задач математической физики.
|
Программные средства для тестирования алгоритмов по обработке изображений
Кратко описываются алгоритмы, положенные в основу программы "испытательного стенда", который предназначен для разработки прикладного программного обеспечения в области обработки изображений.
|
Язык описания графовых моделей и алгоритмов GRAMAL
При построении программных систем различных уровней сложности часто и
широко используются графовые модели и различные методы их обработки.
Графы, являясь очень удобным инструментом описания структур данных и
информационных потоков, активно используются в различных математических задачах. Именно для этого создана система GRAMAL, преследующая
четыре цели: предоставить инструмент для описания графовых моделей;
графически представить эту модель; предоставить средства тестирования
и отладки методов работы с графами; обеспечить возможность генерации
программного кода для последующего применения.
|
Трансформ: интерфейс для ввода информации
Описывается интерфейс для ввода информации в информационно-поисковую
систему Трансформ. Источник данных для этой системы - публикации по
преобразованиям программ. Цель этой работы - создание программного комплекса, предоставляющего удаленному пользователю, связавшемуся с WWW-сервером ИС Трансформ, удобный интерфейс для регистрации в системе,
ввода информации в базу данных, формирования запросов поиска, осуществления этого поиска и выдачи результатов в удобном виде.
|
Применение графов в программировании
Теория графов из академической дисциплины все более превращается в средство, владение которым становится решающим для успешного применения
ЭВМ во многих прикладных областях. Статья посвящена средствам поддержки применения графов в программировании, которые создаются сотрудниками лаборатории конструирования и оптимизации программ Института систем информатики СО РАН им. ак. А.П. Ершова при финансовой
поддержке РФФИ. Дается обзор работ над "энциклопедией" алгоритмов на
графах для программистов. Описываются методы и инструменты для визуальной обработки графов (графовых моделей). Рассматривается толковый
словарь по теории графов в информатике и программировании, а также его электронная версия.
|
Эквивалентность моделей локальных вычислений
Рассматривается эквивалентность моделей локальных вычислений. В настоящее время существует несколько моделей локальных вычислений на графах: системы переписывания графов с приоритетом, системы переписывания графов с запрещенными контекстами, локальные алгоритмы Журавлева, сети конечных автоматов. Обсуждается вопрос сравнения классов задач,
разрешимых за полиномиальное время в различных моделях локальных вычислений. Формулируется ряд предложений и приводятся их доказательства.
|
Некоторые инварианты кубоподобного графа
Кубоподобный граф введен в рассмотрение Ловасом. Это граф со специальным отношением смежности на своих вершинах. Статья посвящена изучению
ряда инвариатов кубоподобного графа, в частности, хроматических. Найдено значение реберного предписанного хроматического числа, а также найден метод вычисления кликоматического числа и плотности кубоподобного графа.
|
Организация графического вывода в системе визуализации иерархических графовых моделей
Рассматриваются методы организации графического вывода в системах визуализации графовых объектов. Отмечаются и классифицируются основные
проблемы, возникающие при проектированнии таких систем, даются общие
методы их решения и описывается конкретный вариант реализации данных
подходов в системе Higres, являющейся визуализатором и редактором иерархических графовых моделей.
|
Организация пользовательского интерфейса в системе визуализации иерархических графовых моделей
Описываются интерфейсные решения, примененные в системе Higres, являющейся визуализатором и редактором иерархических графовых моделей.
Рассматриваются особенности визуализации иерархической структуры графа, методы, позволяющие предоставить пользователю возможность быстро
и удобно редактировать граф и его изображение, алгоритмы автоматического достраивания изображения, а также дополнительные возможности, реализованные в системе.
|
Подготовка графовых иллюстраций с помощью системы VEGRAS
В настоящее время растет интерес к методам и системам визуализации графов. Статья посвящена описанию системы VEGRAS для подготовки графовых иллюстраций, которая отличается простотой в использовании и позволяет создавать достаточно качественные изображения. Данная система является универсальным инструментом для визуализации и редактирования
атрибутированных графов.
|
Реализация сопоставления с образцом в языке Lisp на основе аналогичных средств в языках Refal и Haskell
Описано расширение языка Lisp средствами сопоставления с образцом на основе аналогичных средств в языках Refal и Haskell. Рассматриваются некоторые способы введения в язык Lisp средств сопоставления с образцом и
оценивается удобство применения этих средств для обработки структурированных данных.
|
Использование шаблонов при разработке WIS
В настоящее время WEB является самым популярным информационным
хранилищем. Возрастающая популярность Интернета и быстрая эволюция
программного обеспечения от любительских Web-сайтов до корпоративных
систем заставляет развиваться гипермедиа-технику быстрее, чем когда-либо
прежде. В предлагаемой статье рассматривается использование проектных
шаблонов для решения различных проблем, возникающих на современном
этапе проектирования гипермедиа-приложений, а именно процесс применения шаблонов для улучшения проектирования архитектуры Web- Информационных Систем (WIS).
|
Логическая структура процесса генерации и отгадывания загадок
Исследуются методы принятия решений в концепции ТРИЗ на примере процесса генерации и отгадывания загадок.
|
|