Содержание журнала, редсовет, редколлегия, информация об обложке и о диске.

Table of contents, editorial board, editors, information on cover, information on CD.

Три из четырех золотых медалей и одну серебряную в финале студенческого командного чемпионата мира по программированию ACM ICPC завоевали российские команды. Мы поздравляем победителей, в особенности команду СПбГУ ИТМО, занявшую (как и в 2008 г.) первое место и желаем россиянам дальнейших успехов.

В статье описывается опыт автора по преподаванию и развитию технологий Sun Microsystems – Java, компиляторов Sun Studio, ОС Solaris, архитектуры SPARC – и использованию открытого программного обеспечения в преподавании на математико-механическом факультете СПбГУ. Анализируются преимущества открытого программного обеспечения. Сформулированы рекомендуемые направления дальнейшей работы для преподавателей ИТ. Намечены перспективы новых технологий. Даны ссылки на полезные ресурсы.

The article describes the author’s experience of teaching Sun Microsystems’ technologies – Java, Sun Studio compilers, Solaris OS, SPARC architecture – and of using open software in teaching at the Faculty of Mathematics and Mechanics of St. Petersburg University. Advantages of open software are analyzed. Directions for future work of IT teachers formulated; perspectives of new technologies outlined; references to useful resources provided.

Рассматривается представление описаний простых видов в форме объектов-конструкций, а также окружений, реализуемых в виде иерархии участков в стеке, заполненных индикаторами, посредством которых программа получает доступ к значениям. Описывается сам этот метод доступа.

The article describes representation of plain mode declarations as object-oriented constructs, and implementation of environments in the form of hierarchy of stack frames. The indicators stored in a stack frame are used for the program to have access to valid values. The access method to the values in question is described.

В статье рассматривается эволюция идеи учета последующего контекста, возникшая в середине 50-х годов в задаче автоматического перевода с русского языка на английский, её пробная реализация в середине 70-х годов на примере синтеза эффективной объектной программы в компиляторах и, наконец, её современная реализация и применение в задачах поиска решений методом сначала-в-ширину (breadth-first). Для реализации этой идеи применялись различные техники, наиболее эффективной из которых оказалась техника использования BDD (двоичных диаграмм решений). Конечным, хотя и несколько неожиданным результатом, явилось утверждение, что для широкого класса рекурсивно-переборных задач метод решения сначала-в-ширину выигрывает у традиционного механизма возвратов (метод сначала-в-глубину).

The article covers the evolution of the idea of taking subsequent context into account. This idea emerged in the middle of 1950th in the automated Russian-English translation task. The article describes its trial implementation for the task of efficient object program in compilers in 1970th, and its modern implementation for the task of width-first searching problem decisions. Different techniques to implement this idea were applied, the most effective being the technique that uses BDD (binary decision diagrams). Finally, the advantages of the width-first method, as compared to traditional mechanism of backtracking (depth-first method) for wide class of recursive search tasks are claimed.

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

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.

В статье вводится темпоральная логика линейного времени (LTL), ее формулы объясняются на многочисленных примерах. Объясняется, как свойства поведения дискретных динамических систем, в частности, реагирующих систем (reactive systems) могут быть заданы в этой логике. Статья является изложением одной из глав книги автора «Model checking. Верификация параллельных и распределенных программных систем», которая выходит в издательтве БХВ Петербург.

Linear temporal logic (LTL) is presented and its formulas are explained by numerous examples. It is demonstrated how behavior properties of discrete dynamic systems, in particular reactive systems, may be presented in LTL. The paper is a brief exposition of a chapter from the authorРІР‚в„ўs book Р’В«Model checking. Verification of parallel and distributed programsР’В», to be published at BHV St. Petersburg Publishing office.

Данная статья является второй из серии статей, посвященных изложению «нулевого уровня» языка C#. Рассматриваются понятия типа и экземпляра типа, встроенные типы языка C#, определение новых типов с помощью перечислений и структур, неявное и явное приведение типов.

The article is the second one of the series of articles devoted to teaching Р’В«zero levelР’В» of the C# language. Concepts of type and of type instance, primitive data types, definition of new types by means of enumerations and structures, implicit and explicit cast are considered.

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

The paper gives a detailed description of the busy beaver problem, its variations, methods for solving and well-known results on the busy beaver problem.