От авторов

Современное состояние информатики и программирования нельзя представить себе без применения теоретико-графовых методов. Анализ программ, оптимизация, автоматическое распараллеливание, сложные структуры данных, отладка и тестирование, оценка сложности программ, повышение уровня параллелизма в программе – вот далеко не полный перечень областей применения теоретико-графовых методов в программировании. Сюда же можно добавить такие интенсивно развиваемые в последнее время направления, как проектирование сетей ЭВМ, сетей межпроцессорных связей, маршрутизация при пересылке данных в параллельных компьютерах с распределенной памятью, повышение эффективности работы с памятью, организация больших массивов информации. В теоретическом программировании важную роль играют различные теоретико-графовые модели программ и систем, включая системы переписывания графов и графовые грамматики. Активно используются методы теории графов в САПР при проектировании СБИС, а также в искусственном интеллекте.

Основной проблемой в применении теоретико-графовых методов является проблема терминологии. Выход в свет книг “Применение теории графов в программировании” В.А. Евстигнеева, “Оптимизирующие преобразования программ” В.Н. Касьянова и “Теория графов: алгоритмы обработки деревьев” В.А. Евстигнеева и В.Н. Касьянова высветил эту проблему для авторов достаточно остро. Терминология в теории графов далеко не устоялась, при написании статей требуется терминологическая привязка к одной из существующих на русском языке монографий, что становится все более трудным делом из-за сокращения числа издающихся книг, в том числе переводных, и резкого сокращения их тиража.

Предлагаемый словарь призван если не решить, то значительно облегчить эту проблему. В словаре собраны термины, использованные в таких известных монографиях по теории графов, как книги Ф. Харари, К. Бержа, О. Оре, А.А. Зыкова и др., а также в доступных для отечественного читателя публикациях по информатике и программированию, с указанием источника и вариантов. Русский термин сопровождается его английским эквивалентом, что позволит использовать его как русско-английский словарь, а прилагаемый английcко-русский словарь поможет при чтении англоязычной литературы. Последнее на наш взгляд позволит сократить размножение вариантов используемых в литературе терминов. Кроме собственно теоретико-графовых терминов в словарь включены необходимые для понимания термины из программирования, комбинаторного анализа, прикладной алгебры и исследования операций, что расширяет круг пользователей словаря.

При отборе терминов авторы исходили из следующих соображений. В качестве основного было выбрано множество понятий, представленных в монографии “Лекции по теории графов”, как наиболее полного и доступного для отечественного читателя издания по теории графов. Затем оно пополнялось терминами из переводных и других отечественных книг по теории графов, а также монографий по информатике и программированию, существенно использующих методы теории графов. Чтобы как-то уменьшить разрыв между терминологией монографий и терминологией, используемой в статьях и не успевших попасть в монографии, мы включили в словарь термины, встречающиеся в докладах ежегодной конференции “Graph Theory Concepts in Computer Science” и в статьях, опубликованных в ведущих по данной тематике журналах “Discrete Mathematics”, “J. Graph Theory” и др. В последнем случае мы указывали только название журнала при статье, не включая журнал в список литературы в конце словаря.

Литературные ссылки, приводимые в статьях словаря, указывают лишь на источники, где можно более глубоко познакомиться с соответствующими понятиями, и никоим образом не устанавливает приоритетов в их создании. Мы ограничивались небольшим набором ссылок, особенно это касается основополагающих терминов, определяемых практически во всех монографиях.

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

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

Предварительная версия словаря была издана в 1995–96 гг. тремя выпусками в Новосибирском государственном университете; электронный вариант этой версии доступен через Интернет по URL-адресу http: $\backslash\backslash$ pcosrv.iis.nsk.su и постоянно пополняется.

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

Работа над словарем поддерживалась грантами Российского фонда фундаментальных исследований и Министерства общего и специального образования России.

Февраль 1998 г.