Читать онлайн «Толковый словарь по теории графов в информатике и программировании»

АКАДЕМИЯ НАУК РОССИЙСКОЙ ФЕДЕРАЦИИ СИБИРСКОЕ ОТДЕЛЕНИЕ ИНСТИТУТ СИСТЕМ ИНФОРМАТИКИ им. А. П. ЕРШОВА В. А. ЕВСТИГНЕЕВ, В. Н. КАСЬЯНОВ ТОЛКОВЫЙ СЛОВАРЬ ПО ТЕОРИИ ГРАФОВ В ИНФОРМАТИКЕ И ПРОГРАММИРОВАНИИ Под редакцией Л. С. Мельникова е НОВОСИБИРСК "НАУКА" СИБИРСКОЕ ПРЕДПРИЯТИЕ РАН 1999 УДК 519. 6 ББК 22. 18 К28 Толковый словарь по теории графов в информатике и программировании / В. А. Евстигнеев, В. Н. Касьянов. — Новосибирск: Наука. Сиб. предприятие РАН, 1999. — 291 с. ISBN 5-02-031530-3 В предлагаемом словаре впервые собраны наиболее употребительные термины по теории графов и ее приложениям в информатике и программировании. Каждый термин приводится на русском и английском языках, после чего следует его описание с указанием доступной литературы. В конце словаря помещен указатель английских терминов. Словарь хорошо иллюстрирован. Для широкого круга специалистов, использующих методы теории графов при решении своих задач, в первую очередь для системных и прикладных программистов, а также для специалистов по САПР, конструкторов СБИС и т. д. Ил. 104. Библиогр. : 59 назв. Рецензенты И. В. Поттосин, В. К. Попков Книга — лауреат конкурса научных изданий Сибирского отделения Российской академии наук 1998 г. Без объявления © Российская академия наук, 1999 © Оформление СП "Наука" РАН, 1999 ISBN 5-02-031530-3 © В. А. Евстигнеев, В. Н. Касьянов 1999 ОТ АВТОРОВ Современное состояние информатики и программирования нельзя представить себе без применения теоретико-графовых методов. Анализ программ, оптимизация, автоматическое распараллеливание, сложные структуры данных, отладка и тестирование, оценка сложности программ, повышение уровня параллелизма в программе — вот далеко не полный перечень областей применения теоретико-графовых методов в программировании. Сюда же можно добавить такие интенсивно развиваемые в последнее время направления, как проектирование сетей ЭВМ, сетей межпроцессорных связей, маршрутизация при пересылке данных в параллельных компьютерах с распределенной памятью, повышение эффективности работы с памятью, организация больших массивов информации. В теоретическом программировании важную роль играют различные теоретико-графовые модели программ и систем, включая системы переписывания графов и графовые грамматики. Активно используются методы теории графов в САПР при проектировании СБИС, а также в искусственном интеллекте. Основной проблемой в применении теоретико-графовых методов является проблема терминологии. Выход в свет книг "Применение теории графов в программировании" В. А. Евстигнеева, "Оптимизирующие преобразования программ" В. Н. Касьянова и "Теория графов: алгоритмы обработки деревьев" В. А. Евстигнеева и В. Н. Касьянова высветил эту проблему для авторов достаточно остро. Терминология в теории графов далеко не устоялась, при написании статей требуется терминологическая привязка к одной из существующих на русском языке монографий, что становится все более трудным делом из- за сокращения числа издающихся книг, в том числе переводных, и резкого сокращения их тиража.