Проводится краткий обзор алгоритмов, среди которых лидирует алгоритм Брендана МакКея, реализованный им в библиотеке nauty. Излагаются главные принципы этого алгоритма: уточнение разбиений вершин и использование автоморфизмов для сокращения поиска. Приводится псевдокод всего алгоритма в упрощённом виде.

Canonical code is the notation for the graph structure, which is invariant to isomorphism. The article briefly illustrates the significance of canonical codes in general, and reveals some connection of the canonical code building to other problems common to computer science. A short overview of the currently popular algorithms is presented. The ideas of Brendan McKay's algorithm, implemented in his famous library В«nautyВ», are described. That is, refinement of the vertex partition and use of automorphisms to prune the search tree. A simplified pseudo-code of the entire algorithm is shown.

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

The article throws light upon the theory and practice of symbolic integration. The statement of the problem is considered for several categories of functions, and the main theorems are listed. The overview of the most significant achievements in this area is given. The last section lists the open questions, which are present in both theory and implementations.

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

The article briefly describes a number of open problems in cheminformatics, solving which will allow sooner or later to work out a proper chemical compounds and articles search engine, suitable for the needs of present-day pharmacology. On each problem, the most well-known results are listed, and the weaknesses of the available services are mentioned.

Реверсивный поиск – один из алгоритмов, идея которого «витает в воздухе» десятилетиями и который часто изобретается заново программистами, знакомыми с такими алгоритмами, как поиск в ширину (BFS) и поиск в глубину (DFS). В 1996 г. алгоритму было дано имя и довольно общая формулировка [1], с которой его можно применить ко множеству различных задач. В статье показано ещё одно применение этого алгоритма – перебор поддеревьев произвольного графа.

The idea of reverse search was in the air for decades, and lot of programmers were reinventing it without giving it a name, while the similar algorithms such as breadth-first search and depth-first search were widely known. In 1996 the general algorithm was presented in [1], which was shown to be suitable for variety of problems. In the present paper another application of this algorithm is shown: enumeration of the subtrees of an arbitrary graph.

Канонический код – это способ записи графа, инвариантный относительно изоморфизма. В статье вкратце объясняется значимость канонических кодов и показывается связь задачи вычисления канонического кода с другими задачами, известными из курса теории алгоритмов. Приводится алгоритм вычисления канонического кода для дерева с помеченными вершинами и рёбрами, который работает за линейное время от размера дерева. Алгоритм основан на известном алгоритме проверки изоморфизма двух деревьев.

Canonical code is the notation for the graph structure, which is invariant to isomorphism. The article briefly illustrates the significance of canonical codes in general, and reveals some connection of the canonical code building to other problems common to computer science. A linear-time algorithm for calculating the canonical code of a colored tree is presented. The algorithm is based on widely known procedure of tree isomorphism detection.