Журналы
Email: Пароль: Войти Регистрация
Cтатья продолжает цикл, начатый в № 1, 2 за 2007 г., рассматривает алгоритмы построения выпуклой оболочки в трехмерном пространстве: алгоритм «Заворачивания подарка», алгоритм разделения и слияния, быстрый алгоритм. (С. 3-17)
В продолжение статьи предыдущего номера рассматриваются алгоритмы построения выпуклой оболочки на плоскости. Связь этой задачи с задачей сортировки позволяет найти нижнюю оценку сложности задачи построения выпуклой оболочки. Кроме того, аналогия между этими двумя задачами приводит к некоторым оптимальным по сложности алгоритмам построения выпуклой оболочки. Рассматриваются также алгоритмы Киркпатрика-Зайделя и Чена, асимптотическая сложность которых зависит от размера построенной выпуклой оболочки. (С. 6-18)
Рассматривается реализация приведений в объектно-ориентированной модели семантики на примере языка программирования Алгол 68.

Ключевые слова: априорный и апостериорный виды конструкций и значений, план приведений конструкции, приведение значений.
Рассматривается реализация условных и вариантных предложений как конструкций в объектно-ориентированной модели семантики на примере языка программирования Алгол 68.

The implementation of the conditional clause and the case clause based on the object-oriented model of semantics of the programming language Algol 68, as example, is discussed.

Ключевые слова: балансировка видов, вариантное предложение, приводимое, условное предложение.
При автоматическом распознавании изображения на первом этапе исследования требуется определить, существует ли на нем что-то подобное искомому объекту. Ответ на этот вопрос можно получить с помощью анализа информативности изображения. В работе предлагается новая мера информативности, основанная на использовании элементарных трёхпиксельных кластеров. Сравнивая количество кластеров на заданном изображении с количеством кластеров на случайном изображении и на максимально упорядоченном изображении с одинаковым количеством пикселей, можно сделать выводы о структуре исследуемого изображения. Эта информация может быть использована для выбора стратегии поиска объекта, то есть необходимых масок изображения, а также при выборе эффективного метода архивирования изображения.

Some conclusions about the structure of the image can be drawn from comparing one of two images - the one under consideration and the most ordered one both having the same quantity of 3-pixel clusters.

Ключевые слова: автоматическое распознавание изображений, мера информативности.
Проводится краткий обзор алгоритмов, среди которых лидирует алгоритм Брендана МакКея, реализованный им в библиотеке 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.

Ключевые слова: канонический код, каноническая нумерация, изоморфизм графов, автоморфизмы графов, nauty.
Цель работы – создание инструментального средства для трансляции описаний графов переходов автоматов, представленных в формате MS Visio, в программный код на языке C. В качестве языка реализации указанного средства выбран язык C#, предназначенный для платформы .NET, так как он обеспечивает хорошую поддержку COM-технологии, используемой при взаимодействии с MS Visio. Программа транслятора может быть запущена в двух режимах. В первом из них трансляция производится интерактивно, и вся информация считывается из командной строки. Этот режим удобен при использовании в средствах автоматической сборки (например make, менеджер проектов MS Visual Studio). Во втором режиме интерфейсом программы является диалоговое окно.

The open-source tool for translation of discrete finite automata descriptions from Microsoft Visio format to source code in C language is developed. There is a number of similar tools, but some of them have poor error diagnostics while translation, some have poor stability and quality of code they generate, and some of them arenРІР‚в„ўt open-source. The aim of this project is the development of tool without these drawbacks. The tool itself is written on C# language for .NET platform.

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

Some unresolved questions of implementation of semantics of algorithmic languages in a context of the discussed project are considered.

Ключевые слова: балансировка видов, конструкции объединённых видов, окружения, параметрическая генерация модулей, приводимые, сопоставляющие предложения.
В статье рассматриваются проблемы, связанные с широким применением языков предметной области (DSL). Обсуждается связанное с этим понятие языкоориентированного программирования. Неоднозначность синтаксиса программы, написанной на нескольких языках, видится как критическая проблема. Объясняется один из подходов к преодолению этого ограничения и рассматривается реализация этого подхода на примере среды разработки языков JetBrains MPS.

In this article some difficulties of domain-specific languagesРІР‚в„ў (DSLs) widespread application are discussed. Related notion of language-oriented programming is explained. Ambiguity of a concrete syntax of a program written in several different languages is considered to be a critical issue. One approach to overcome such an obstacle is explained and its implementation in Jetbrains MPS is overviewed.

Ключевые слова: MPS, DSL, LOP, языкоориентированное программирование, языки, среда разработки, синтаксис, AST, абстрактное синтаксическое дерево, клеточный редактор.
Статья посвящена проблемам доказательства полиномиальной вычислимости функций, другими словами, доказательства принадлежности функций классу FP. Доказательства могут производиться с помощью паскалевидных функций, которые более удобны программистам, чем модели вычислений, основанные на машине Тьюринга. Будет приведена идея доказательства теоремы, что если не только число шагов вычисления паскалевидной функции, но и размер записи всех промежуточных вычислений не превосходят полинома от длины записи исходных данных, то эта функция принадлежит классу FP и обратно.

The paper is devoted to the problem of proving that some function is in FP complexity class. Such proofs may use pascal-like functions, that are more easy for programmers, than computation models based on a Turing machine. It will be presented the idea of proof of the theorem, that if both the number of steps of pascal-like function evaluation and a size of all intermediate evaluations are not greater than some polynomial of the length of initial data, then this function is in FP and vice versa.

Ключевые слова: P, FP, NP, машина тьюринга, паслкалевидные функции, NP-полнота, NP-трудность, примеры NP-полных задач.
Keywords: P, FP, NP, Turing machine, pascal-like functions, NP-full, NP-complete, NP-complete functions examples.
На примере решения логической задачи излагается метод построения компьютерных инструментов, имеющих значение универсальных интеллектуальных орудий для решения широкого круга задач или выполнения определенных этапов решения. Алгоритм решения не зависит в данном случае от специфики содержания задачи, но обеспечивает «самопреобразование» исходных данных в системную форму, содержащую искомый результат в явном виде, посредством последовательной актуализации свойств каждого объекта в среде других объектов. Главная направленность работы – продемонстрировать на конкретном примере возможность и эффективность приведения во взаимосвязь концептуального и вычислительного, математического и программного аспектов при построении компьютерных инструментов.

The approach to the construction of computer tools is discussed. The decisions of task or problem are made on the basis of "self-transformation" of the initial data. Solution algorithm does not depend on specific content of the task, but only provides an opportunity for each object, to prescribe its properties in the environment of other objects.

Ключевые слова: компьютерные инструменты, самопреобразование данных, системообразующий принцип, логические задачи.
Keywords: data self-transformation, system-creating principle, computer tools.
В статье обсуждаются парадигмы программирования и то, как разные парадигмы применяются для решения программистских задач. В частности, обсуждается, как решить одну трудную олимпиадную задачу по программированию с использованием трёх парадигм программирования: логического, функционального и императивного. Разработку эффективного императивного алгоритма решения этой задачи можно рассматривать как пример обращения аналогичной логической программы. Функциональный алгоритм при таком подходе представляет собой промежуточный вариант решения задачи, более эффективный, чем логический алгоритм, а эффективный императивный алгоритм фактически является ленивой мемоизацией этого функционального алгоритма.

This paper is about programming paradigms, how different paradigms can fertilize each other. In particular the paper discusses a challenging contest programming problem and solves it in three programming paradigms: logic, functional and imperative. It can be considered as a case study of algorithm inversion, since we start with logic algorithm, that answers the question "Is balancing M times sufficient for detecting a single fake in a set of coins?", and finishes with imperative algorithm, that effectively computes the minimal number of balancing that is sufficient for detection the fake. Functional paradigm is used for developing an intermediate functional algorithm that also computes the minimal number of balancing, but inefficiently, while the efficient imperative algorithm is a Р’В«lazy memoizationР’В» of the functional one.

Ключевые слова: парадигмы программирования, императивное программирование, функциональное программирование, логическое программирование, мемоизация, динамическое программирование.
Keywords: programming paradigms, imperative programming, functional programming, logical programming, memoization, dynamic programming.
В [3] даны определения числа шагов и длины записи промежуточных вычислений паскалевидных функций. С их помощью было получено представление класса всех функций, вычислимых на машинах Тьюринга за число шагов, ограниченное сверху полиномом от длины записи исходных данных (класса FP), с помощью дважды полиномиальных (то есть полиномиальных по числу шагов и по длине записи промежуточных вычислений) паскалевидных функций. Для удобства доказательства принадлежности паскалевидной функции классу FP здесь введено понятие паскалевидных функций над списком S паскалевидный функций. Для этих функций даны определения числа шагов и длины записи промежуточных вычислений, наконец, определены дважды полиномиальные паскалевидные функции над списком S. (для каждой функции из S число шагов и длина записи промежуточных вычислений равны единице). Функции из S соответствуют базовым подпрограммам. Доказывается теорема о совпадении класса дважды полиномиальных паскалевидных функций над S и класса FP.

[3] gives definitions of time and space comlexity of pascal-like functions. Using this definitions it was obtained the representation of the class of all functions computable by Turing machine in time upper bounded by the polynomial of the length of the initial data (FP class) by means of double polynomial (i.e. polynomial in time and space) pascal-like functions. For the convinience of proving that a pascal-like function is in FP, we introduce the notion of the pascal-like functions over a list S of pascal-like functions. For such functions we give definitions of time and space complexities, finally, we define double polynomial pascal-like functions over a list S. (for every function in S, time and space complexity are equal to one). Functions from S correspond to basic subroutines. The theorem about the equality of the class of double polynomial pascal-like functions over S and the FP class is proved.

Ключевые слова: верхние оценки числа шагов, машины Тьюринга, класс FP, функции языка Паскаль.
Keywords: Upper bounds for time complexity, Turing machine, FP complexity class, functions of pascal programming language.
В статье излагается формализм для описания двумерных графо-подобных диаграмм. Основанный на формализации диаграмм, предложенной Е.А. Жоголевым, он расширяет ее, вводя конкретные типы двумерных конструкций и допустимые отношения между ними. При этом рассматриваются элементы таких визуальных языков, как сети Петри, ERD, UML, IDEFx и SDL.

The paper proposes formalism to specify plane graph like diagrams. Formalism is based on formalization described by Zhogolev E. A. New kind of diagrammatic constructions introduced with possible relationships between them. Elements of such visual languages as PetriРІР‚в„ўs Nets, ERD, UML, IDEF and SDL are considered throughout the paper.

Ключевые слова: графо-подобная диаграмма, формализация графических конструкций, нотация, конкретный синтаксис.
Keywords: diagramming, graph-like diagram, notation, drawing formalization.
Существует множество технологических средств построения анализаторов формальных языков, используемых при создании разного вида трансляторов языков программирования. Все они, в конечном счёте, основываются на КС-грамматиках с теми или иными ограничениями, частным случаем которых являются регулярные (автоматные) грамматики. Как правило, эти технологические средства обеспечивают лишь проверку соответствующих требований, предъявляемых к грамматике, и выдачу диагностических сообщений об их нарушениях, тогда как существует множество способов эквивалентных преобразований КС-грамматик, которые могут быть выполнены автоматически и дать грамматики, удовлетворяющие требованиям метода анализа. Цель этой статьи – описать способ исключения несамовставленных нетерминалов из КС-грамматик за счёт введения регулярных выражений в правые части правил грамматики. В предельном случае такая преобразованная грамматика включает единственное правило для начального нетерминала.

There is a variety of parser generators for formal languages being used during designing compilers for programming languages of different types. All of them are based on the use of context-free grammars with various restrictions, regular grammars being a special case. As a rule, they only check the requirements imposed on grammar, and issue diagnostic messages in case of their violation. The purpose of this article is to describe the way of eliminating all nonterminals from the non-self-embedding grammar that gives the equivalent regular expression as result.

Ключевые слова: КС-грамматика, регулярное выражение, эквивалентное преобразование грамматики.
Keywords: context-free grammar, regular expression, equivalent conversion of grammar.
Облачная платформа MS Azure предоставляет множество сервисов, которые позволяют разрабатывать производительные и надежные приложения. Управление этими сервисами производится из исходного кода облачного приложения, что приводит к проблеме «сквозной функциональности», когда реализация одной функции распределена по всему коду. Данная работа предлагает подход, который позволяет устранить этот недостаток.

The MS Azure cloud platform provides a set of services which allow to develop efficient and safe applications. Control of these services is made from the source code of cloud application that leads to a problem of «cross-cutting concerns» when implementation of one function is tangled on all code. This paper describes an approach which allows to remove this disadvantage.

Ключевые слова: аспектно-ориентированное программирование, АОП-рефакторинг, унаследованный код, Aspect.NET.
Keywords: aspect-oriented programming, AOP-refactoring, legacy code, Aspect.NET.
Вводятся алгоритмы Маркова-Турчина как обобщение алгоритмов, введённых автором в [5], и являющиеся существенной модификацией программ, написанных на языке рефал-5. Предлагается критерий их эффективности для реализации на машине Тьюринга за полиномиальное число шагов. Этот критерий не использует ограничения памяти, в отличие от того, как это было установлено в [3] для дважды полиномиальных программ на языке рефал-5. Критерий основан на специального вида рекурсии в программах, являющейся существенным обобщением хвостовой рекурсии, предложенной Т. Борландом для программ на турбо прологе. Это обобщение связано с основным типом данных в языке рефал-5, представляющем собой древовидно структурированные тексты посредством круглых скобок. Для алгоритмов Маркова-Турчина (со встроенным динамическим интерпретатором) просто доказываются некоторые модификации теорем теории сложности алгоритмов, полезные для математиков-программистов. Иначе говоря, вводится математическое понятие алгоритма, модифицирующее (в основном, упрощающее, а также объединяющее в единый алгоритм все вспомогательные алгоритмы с помощью использования встроенного интерпретатора) понятие рефал-5 функции, введённой В.Ф. Турчиным (см., например, [2, 6]), в частности, путем расширения понятия нормального алгоритма А.А. Маркова на древовидно оформленные тексты с помощью структурных (круглых) скобок. Введение встроенного динамического интерпретатора (в терминологии В.Ф. Турчина – расширения встроенной метауниверсальной функции), вычисляющего применение любого алгоритма с динамически полученной его записью к исходным данным, является существенным расширением понятия алгоритма Маркова. Известно, что на практике алгоритмы и исходные данные ограничены по длине. В статье также доказываются теоремы о вариантах проблемы применимости алгоритмов Маркова-Поста с учётом этого обстоятельства. Точнее, доказываются нижние оценки длины программ, разрешающих проблему применимости коротких программ к коротким данным на языке алгоритмов Маркова-Турчина (со встроенным динамическим интерпретатором). С. 41-49.

Refal5 functions and introduced by the author in [5] Markov-Turchin algorithms are under consideration in the paper. Such an algorithm is an essential modification of a Refal5 program. The test of its polynomial efficiency for the Turing machine implementation of such a program is offered. This test does not use the bound on the used memory size as it was stated in [3] for double polynomial Refal5 programs. The test is based on a special kind of recursion in a program which is an essential generalisation of a tail recursion proposed by T. Borland for a Turbo Prolog program. This generalisation is connected with the main Refal5 data type: a tree-like text structured by means of brackets. For a Markov-Turchin algorithm (with a built-in dynamical interpreter) some modifications of complexity theory theorems useful for mathematicians-programmers have simple proofs. In other words an introduced here mathematical notion of an algorithm modifies (mainly simplifying and combining into a single algorithm all needed auxiliary algorithms with the use of the built-in dynamical interpreter) the notion of a Refal5 function introduced by V.F. Turchin (see, for example, [2, 6]). This modification is, in particular, an extension of the Markov algorithm notion for tree-like formed texts with the help of structural brackets. The introduction of the built-in dynamical interpreter (in the terminology of V.F. Turchin – the extended built-in meta-universal function) computing an application of any dynamically received algorithm to the input data is an essential extension of the Markov algorithm. It is known that in practice algorithms and the initial data have bounded lengths. Theorems on variants of the halting problem for the Markov algorithm with such a restriction are proved in the paper. More precisely, lower bounds of the length of a Markov-Turchin algorithm (with a built-in dynamical interpreter) for the program checking the halting problem for short programs and short data are proved.

Ключевые слова: машина Тьюринга, полиномиальное число шагов, рефал-5, нормальный алгоритм Маркова, класс сложности FP, проблема применимости алгоритмов к данным.
Keywords: Turing machine, polynomial number of steps, Refal5, Markov algorithm, complexity class FP, halting problem.
Этот текст является слегка отредактированной стенограммой содоклада на совместном заседании Санкт-Петербургского Математического общества и Секции математики Дома учёных 23 марта 2010 года. Материалы заседания, включая видеозаписи, доступны в [1].

This publication is a slightly edited verbatim report of author's co-talk presented at joint meeting of St.Petersburg Mathematical Society and Mathematical section of the House of Scientists on March 23, 2010; related materials, including video recording, can be found on [1].

Ключевые слова: формальное доказательство, интерактивное доказательство, нулевое знание.
Keywords: formal proof, interactive proof, zero knowledge.
В статье рассматривается подход к перебору субоптимальных решений, основанный на введении специальных процессов перебора – «перечислителей», решающих задачи такого типа, и создании специальных, достаточно простых операций, позволяющих получать перечислители из более простых. Приводятся примеры таких операций. С. 25-34.

The paper presents an approach to enumeration of suboptimal solutions, based on introduction of special processes of enumeration – «enumerators», which solve problems of that kind for various smaller problems. Some special operations presented in the paper allow us to make the required enumerators of simpler ones. Some examples are presented.

Ключевые слова: субоптимальные решения, дискретные задачи оптимизации, динамическое программирование.
Keywords: suboptimal solutions, discrete optimization, dynamic programming.
В работе описан метод классификации изображений, иллюстрирующих процесс распространения вещества в среде, в частности изменения, происходящие при действии сверхмалых доз лекарственных препаратов. Изображение рассматривается как решетка пикселей заданной интенсивности. По изображению строится ориентированный граф, так что каждый узел соединен с N соседями. Всем выходящим из узла дугам приписывается значение интенсивности узла, деленное на N (для точек границы – на N – 1). Построенный поток нормируется. Для полученной таким образом марковской цепи методом Шелейховского-Брэгмана строится стационарное распределение, которое максимизирует взвешенную энтропию. Именно значение взвешенной энтропии выбирается как классификационный признак при анализе изображений, соответствующих различным дозам вещества. Приведены результаты численных экспериментов.

The method of a classification of images concerning to a substance propagation process is proposed. The image is considered as a lattice formed by pixels of given intensity. Then an oriented graph corresponding to the image is constructed in the following way: every vertex (pixel) is connected with N neighbours. For a given vertex all outcoming edges have a value (pixel intensity/N), for boundary vertex – pixel intensity/(N – 1). The constructed flow is normed. For obtained markov chain by the Sheleihovsky-Bregman method a stationary distribution is constructed, which maximizes weighted entropy. It is weighted entropy that is used as a classifying sign when images with different doses of a substance are analyzed. The results of numerical experiments are given.

Ключевые слова: Марковские цепи, стаци¬онарный процесс на графе, аппроксимация ин¬вариантной меры, динамические системы, мак¬симизация взвешенной энтропии.
Keywords: Markov chain, stationary process on graph, approximation of an invariant measure, dynamical systems, maximization of weighted entropy.
Вводятся иерархии классов сложности функций как из FP, так и из FP-SPACE. В статье доказывается теорема о замкнутости классов функций этих иерархий, а также классов функций FP||LIN-SPACE и FP||QLIN-SPACE и классов предикатов P||LIN-SPACE и P||QLIN-SPACE относительно определения рефал-5 функций с ограниченными сверху числом рекурсивных вызовов и величиной использованной памяти. С. 3-8.

Complexity classes hierarchies for functions from both FP and FP-SPACE classes are introduced. Theorems about closure of these function classes of hierarchies as well as the classes of functions FP||LIN-SPACE and FP||QLIN-SPACE and classes of predicates P||LIN-SPACE and P||QLIN-SPACE under the definition of Refal-5 functions with bounded numbers of recursive calls and the used memory size are proved.

Ключевые слова: машина Тьюринга, полиномиальное число шагов, рефал-5, подклассы класса FP-SPACE, подклассы класса FP.
Keywords: Turing machine, polynomial number of steps, Refal-5, subclasses of the class FP-SPACE, subclasses of the class FP.
В работе всесторонне изучается методология полногеномного поиска зависимости фенотипа с одним или несколькими генотипами. В данной части работы обсуждается проблема интерпретации результатов множества тестов, реализация статистических методов, описанных в первой части работы, на языке программирования R и особенности использования статистических методов в комплексных исследованиях заражаемости ВИЧ и развития СПИД. Также будут предложены некоторые соображения, касающиеся интерпретации результатов однотипных статистических тестов, полученных на базе независимых экспериментов.

Methodology of genome association discovery is discussed comprehensively in this paper. The multiple testing problem, implementation of the statistical methods discussed in the first part of the paper and their applications in HIV-infection and AIDS progression studies are considered here. Several ideas on common interpretation results of independent or dependent similar tests will be given too.

Ключевые слова: полногеномный поиск закономерностей (ассоциаций), GWAS, проблема интерпретации результатов множества тестов, эпидемиология ВИЧ.
Keywords: Whole genome association discovery, genome wide association study (GWAS), multiple testing problem, HIV/AIDS research.
Язык программирования рефал-5 позволяет решать некоторые важные задачи программирования короче и эффективнее, чем другие языки программирования. Однако существующие реализации диалектов языка программирования рефал не имеют возможности вызова программой встроенного интерпретатора и простого способа подключения внешних библиотек кода. Для устранения этих недостатков было решено разработать новый диалект языка программирования рефал – рефал-5е. Язык рефал-5е поддерживает возможность вызова из программы встроенного интерпретатора, а также добавлена возможность подключения внешних библиотек кода. Также язык программирования рефал-5е позволяет функции возвращать такие значения как «Успех» и «Неуспех», что позволяет расширить возможности использования возврата, как в языке программирования пролог. C. 3-13.

Refal-5 language gives an ability to perform important tasks shorter and more effectively than another programming languages But existing implementations of Refal programming language dialects have no possibility to call a built-in interpreter from a program or to use external code libraries. To overcome these demerits a new programming language Refal-5e is offered. Refal-5e programming language provides an opportunity to call a built-in interpreter from a program and allows to use external code libraries. Also Refal-5e language allows a function to return such result as “Success” or “Failure”, which permits to use backtracking like in Prolog language.

Ключевые слова: рефал-5, трансляция, интерпретация, рефал-5е машина, библиотеки кода, встроенный интерпретатор.
Keywords: REFAL-5, translation, compilation, interpretation, DLL, REFAL-5 machine.
Несмотря на стремительный рост как производительности, так и емкости запоминающих устройств, темпы роста количества вновь создаваемых данных существенно опережают возможности их хранения и, тем более, возможности обработки. В связи с этим попытки экстенсивного подхода, основанного на наращивании мощности вычислительных систем, не могут радикально решить возникающие проблемы. В статье обсуждаются актуальные классы аналитических задач обработки данных, извлечения информации и знаний и анализируются различные альтернативные подходы к их решению. Этот круг задач и подходов, часто неформально объединяемый под зонтиком Big Data, в последнее время характеризуется уже пятью V (Volume, Variety, Velocity, Veraсity and Value). Наиболее сложными и наиболее интересными представляются задачи, связанные с обеспечением скорости получения результатов обработки и оценки их надежности и корректности. С. 10-18.

In spite of rapid growth of both performance and capacity of available processing and storage devices, the amount of produced data significantly exceeds the capacity of available storage and available processing resources and this gap grows steely. Thus the problem cannot be resolved with scale-out approach. In this paper we discuss several classes of analytical processing, tasks, information and knowledge extraction and analyse alternative approaches to their solution. typically these problems are considered under informal umbrella of Big Data, which are characterised with 5 V: volume, variety, velocity, veracity, and value. The most important and challenging issues are the processing speed, reliability and quality of results.

Ключевые слова: большие данные, аналитические запросы, приближенное выполнение, оценка качества, производительность.
Keywords: big data, performance, analytical queries, approximate evaluation, data quality, reliability.
В данной статье приводятся основные понятия относительно нового направления информационных технологий - теории статистического обучения В. Вапника. Эта теория с каждым годом набирает все большую популярность, поскольку объясняет суть машинного обучения с математической точки зрения. Дальнейшие исследования данной теории могут дать существенные улучшения в скорости и качестве работы алгоритмов машинного обучения. Среди огромного количества публикаций, посвященных теории статистического обучения, автор выбрал десяток статей, в которых раскрываются основные понятия и проблемы этой теории, приводятся практически полезные алгоритмы и результаты экспериментов по сравнению различных подходов. В данной статье в сжатом виде приводятся основные результаты обозреваемых работ, что позволит специалистам, только начинающим знакомиться с этой популярной теорией, облегчить вхождение и приступить к реальным исследованиям. C. 19-26.

The basic concepts regarding the new direction of information technology — statistical learning theory — are described in the article. The theory has been gaining more and more popularity since it explains the essence of machine learning from a mathematical point of view. Further studies of the theory may provide significant improvements in the speed and quality of machine learning algorithms. The dozen articles were chosen among the large number of publications devoted to the theory of statistical learning. These articles reveal the basic concepts and problems of this theory and provide practically useful algorithms and the results of experiments comparing different approaches. Main results of the reviewed works are provided in concise form. The form allows professionals just starting to get acquainted with this popular theory facilitate the entry and proceed to the actual studies.

Ключевые слова: машинное обучение, теория статистического обучения, SLT, SVM, ELM.
Keywords: machine Learning, Statistical Learning Theory, SLT, SVM, ELM.
Язык программирования рефал-5е расширяет существующий диалект языка программирования рефал, названный рефал-5, и позволяет решать современные важные задачи программирования эффективнее, чем другие диалекты языка рефал при использовании современной вычислительной техники. Среди особенностей языка программирования рефал-5е можно выделить такие, как: наличие встроенного интерпретатора, возможность подключения внешних динамически загружаемых библиотек кода, добавление возможности возврата функциями таких значений, как «Успех» и «Неуспех», возможность реализации функций высшего порядка и анонимных функций. Также транслятор языка программирования рефал-5е использует возможности современных многопроцессорных компьютеров, что позволяет увеличить скорость выполнения программ в несколько раз. С. 16-24.

Refal-5e programming language extends the existing refal programming language dialect called refal-5 and allows to solve important modern programming tasks more efficiently than other refal dialects. The most interesting features of the refal-5e programming language are: a built-in interpreter; the ability to use external dynamic link libraries of code; the ability of functions to return values such as «success» and «failure»; the possibility of implementing high-order functions and anonymous functions. Also refal-5e programming language translator uses possibilities of modern multiprocessor computers that can speed up program execution several times.

Ключевые слова: рефал-5, рефал-5е, компиляция, трансляция, интерпретация, бэктрекинг.
Keywords: refal-5, refal-5e, compilation, translation, interpretation, backtracking.
В статье рассматриваются алгоритмы прямого и жадного синтеза минимального графа смежности. Проведен сравнительный статистический анализ времени работы указанных алгоритмов на основе вычислительных экспериментов со специально сгенерированными наборами входных данных. Для генерации тестовых данных был разработан алгоритм генерации нагрузок вершин графа смежности с заданными характеристиками. Результаты статистического анализа отношений скорости работы двух алгоритмов позволили выделить три поддиапазона мощности наборов вершин графов смежности: в поддиапазоне 5–35 жадный алгоритм работает существенно быстрее прямого, в поддиапазоне 60–105 прямой алгоритм работает существенно быстрее жадного, а в под диапазоне 35–60 выигрыш в скорости зависит от конкретного набора данных. Кроме того, можно ожидать, что в диапазоне 5–60 будет обнаружено некоторое число статистических выбросов, сигнализирующих об особенностях в соответствующих наборах исходных данных. Статья также имеет дидактическую цель: обеспечить читателя последовательным описанием мотивированного применения ряда статистик в задаче сравнения двух алгоритмов и особенностей интерпретации полученных показателей. Статистический подход к сравнительной оценке мотивирован тем, что теоретические оценки сложности обсуждаемых алгоритмов не очевидны, зависят от скрытых особенностей исходных данных и не вычисляются по ним непосредственно. С. 3-18.

The paper considers straightforward and greedy minimal joint graph synthesis algorithms. Comparative statistical analysis of runtime was done based on experiments run on specially generated datasets. A new algorithm for generating the loads with certain characteristics was developed. Statistical analysis pointed out three subintervals of joint graph vertix set cardinality (number of elements): that of 5–35 where the greedy algorithm had sufficiently higher speed than the straightforward algorithm did, that of 60–105 the straightforward algorithm had sufficiently higher speed than the greedy algorithm did, and that of 35–60 where the algorithms advantage in their speed dependtd on each specific initial dataset. According to rank statistics, there may be detected a few autliers in the subinterval of 5–60. The paper has a didactic pupose as well.

Ключевые слова: представление неопределенности, алгебраические байесовские сети, вероятностные графические модели, фрагмент знаний, знания с неопределенностью, логико-вероятностный вывод, статистическое исследование сложностей алгоритмов.
Keywords: uncertainty representation, algebraic Bayesian networks, probabilistic graphical models, knowledge pattern, knowledge with uncertainty, probabilistic-logic inference, statistical indicators for algorithm's complexity.
Исследование влияния сверхмалых доз вещества (или излучения) на биологические системы является важной задачей. Многочисленные исследования в естест венных науках и особенно в физике и биофизике живых организмов привели к созданию модели действия сверхмалых доз, которая основана на специальной структуре воды в живых клетках (фрактальные кристаллы) и механизме передачи и преобразования энергии в цепочке биомолекул. В настоящее время наблюдать это влияние непосредственно в живом организме невозможно, но можно регистрировать происходящие в нем изменения используя данные различных измерений состояния организма. Большая часть таких данных представляет собой цифровые изображения, что делает возможным применение математических и компьютерных методов исследования. В работе описано применение математических методов для анализа изображений биомедицинских препаратов и получения численных характеристик изучаемого процесса. Описан метод исследования малых доз электромагнитного излучения, используемого в магнитотерапии. С. 19-27.

Investigation of effects of substance (or radiation) ultralow doses on biological systems is a problem of significant importance. Numerous researches in natural sciences, especially in physics and biophysics of living organism, resulted in making a model of ultralow doses effects. These effects are based on the special structure of water in living cell (fractal crystals) and the mechanism of energy transfer and transformation in biomolecule chains. As for now it is practically impossible to observe this effect in a living organism directly. But we can register changes in an organism states using data of blood analysis or thermal imager. Considering biological system as a complex dynamical system we assume that images of a process in an organism obtained in different instants of time are phase portraits of the process. This leads to application of mathematical and computer investigation methods to studying biological processes. In this paper we describe the application mathematical methods to analyze biomedical preparations images and obtain some numerical characteristics of the process under investigation. We also discuss a method of exploration of the influence of low doses of magnetic fields in magneto therapy devices on a human organism.

Ключевые слова: сверхмалые дозы, цифровые изображения, динамические системы, стационарные процессы, фрактальный анализ, математическая морфология, магнитотерапия.
Keywords: ultralow doses, digital images, dynamical systems, stationary process, fractal analysis, mathematical morphology, magneto therapy.
В статье рассмотрена задача построения симплициального подразделение специального вида, допускающего локальное укрупнение в трехмерном слое. Предложен метод, позволяющий однозначно определить подразделение с необходимыми свойствами. Выведены калибровочные соотношения аппроксимации Куранта, соответствующие укрупнению симплициального подразделения. С. 3-11.

The problem of the definition of the special simplicial subdivision of a three-dimensional layer is considered in the article. The method that allows to uniquely define the subdivision with required characteristics is introduced. The calibration relations for the Courant-type approximation, which correspond to the enlargement are derived.

Ключевые слова: симплициальное подразделение, триангуляция, аппроксимация Куранта.
Keywords: simplicial subdivision, triangulation, Courant-type approximation.
На основе использования иерархии временных масштабов Н.Н. Боголюбова строится феноменологическая модель процесса лазер-индуцированого тромбоза. Стохастический характер процесса отражается в развиваемой модели путём явного введения функции вероятности. Лежащие в основе модели положения соответствуют фундаментальным экспериментальным результатам относительно процессов тромбообразования, полученным в последние годы. Модельные кривые позволяют добиться качественного согласия между предсказаниями модели и экспериментальными данными. Производится сравнение данной модели с другими феноменологическими моделями процессов роста тромба: показано, что многие черты явления могут быть описаны в основном в терминах физических, а не биологических понятий. С. 12-22.

Phenomenological mathematical model of laser-induced thrombi growth is developed on the basis of N.N. Bogolubov’s hierarchy of time scales. The stochastic character of thrombi growth is revealed in the model by explicit introduction of the probability function. The main foundations of the model correspond to the basic experimental results concerning thrombus formation obtained in recent years. The modeling curves permit to achieve qualitative agreement between model and experimental data. The comparison of the model with other models of thrombus growth is performed: it is shown that many features of the phenomenon can be described mainly in terms of physics but not biological terms.

Ключевые слова: математическая модель, микрососуды, развитие тромба, тромбоциты, иерархия временных масштабов.
Keywords: mathematical model, microvessels, thrombus growth, platelets, hierarchy of time scales.
Метод минимизации приведённых детерминированных конечных автоматов, описанный в частности в [1], не всегда даёт минимальный по числу состояний автомат. В данной статье предлагается процесс минимизации этим методом считать лишь первым этапом и дополнить его вторым этапом, гарантирующим искомый результат. С. 23-27.

The method for minimizing reduced deterministic finite automata, described in particular in [1], not always gives minimum on number of it states. It is offered to add the second stage to the method in question in order to guarantee required outcome.

Ключевые слова: конечный автомат, минимизация.
Keywords: finite automaton, minimization.
Разработка систем поиска основана на успехе поиска контента. Основной проблемой в такой разработке является высокая вероятность неправильного результата при поиске в случае нахождения ошибки в системе. В статье рассматривается алгоритм, увеличивающий шанс успешного нахождения пользователем интересующего его контента в системе поиска, на основании пользовательского взаимодействия. Алгоритм описывает процесс получения данных системой, преобразования данных в ранжируемые сущности, а также определения отображаемых результатов. Также в статье приведены примеры основных алгоритмов, вошедших в основу алгоритма <<ложного пути>>, их особенности и проблемы. Кроме того, в статье предоставлены дальнейшие пути улучшения алгоритма. C. 9-16.

Search systems design is based on the successful rate of content find. The key problem in that kind of design is a good probability of failure in content find if any mistake in the system occurs. The article discusses an algorithm that increases the chances of successful content find in content search systems by analyzing user behavior. The algorithm describes the process of data gain by the system, data transfer into marshallable essences, and corresponding results determination. The article also refers to most common algorithms that serve as the basement for the <> algorithm, their problems and key features. The article discusses possible improvements of the algorithm that should be taken into account in future.

Ключевые слова: алгоритм, <<ложный путь>>, ранжируемые сущности, системы поиска контента.
Keywords: algorithm, <>, marshallable essences, content search systems.
Статья посвящена изложению алгоритма выделения максимальной общей с точностью до имён переменных подформулы двух элементарных конъюнкций атомарных предикатных формул. Предлагаемый алгоритм использует введённую ранее автором модификацию обратного метода Маслова, а также Муравьиные тактики и параллельные вычисления. Проблема выделения максимальной общей с точностью до имён переменных подформулы предикатных формул имеет достаточно широкое применение при построении эффективных алгоритмов решения задач искусственного интеллекта, допускающих формализацию средствами исчисления предикатов. Приведены асимптотические оценки числа шагов работы описанного алгоритма. С. 17-25.

The article is devoted to the describing of an algorithm which extract a maximal common up to the names of variables sub-formula of two elementary conjunctions of atomic predicate formulas. The offered algorithm uses the proposed earlier by the author modification of inverse method of S. Yu. Maslov as well as Ant tactics and concurrent processing. The problem of the extraction of a maximal common up to the names of variables sub-formula of predicate formulas has wide enough application while development of an effective algorithm solving an Artificial Intelligence problem permitting its description in the frameworks of predicate calculus language. Asymptotic estimates of the number of run steps for the described algorithm are formulated.

Ключевые слова: искусственный интеллект, логико-предметное распознавание образов, исчисление предикатов, сложность алгоритмов, обратный метод Маслова, параллельные вычисления, неполная выводимость.
Keywords: artificial intelligence, logic-objective approach to pattern recognition, predicate calculus, complexity theory, inverse method of S. Yu. Maslov, concurrent processing, partial deducibility.
В статье рассматриваются современные методы бинаризации, которые широко используются в полиграфии при печати для процесса растрирования, и связанные с этим процессом теоретические вопросы растрирования. Особое внимание уделено блочному алгоритму бинаризации, относящемуся к методам, основанным на условии равенства яркостей, когда бинарное изображение имеет яркость равную яркости исходного изображения. Приводится его описание, а также краткое описание алгоритмов, выбранных для сравнения. Изображение, полученное бинаризацией полутонового изображения блочным алгоритмом бинаризации, на основе вычисления выбранных мер искажений показывает лучшие характеристики по сравнению с другими алгоритмами бинаризации. Также целью данной работы являлся эксперимент по печати тоновой шкалы и измерение коэффициентов отражения полутонов при помощи спектрофотометра. В ходе эксперимента были построены градационные кривые для заданного принтера и проанализированы полученные характеристики. Найдено, что для блочного алгоритма наблюдается увеличение контраста, что подтверждается реальным печатным экспериментом. При анализе свойств блочного алгоритма бинаризации выявлено, что он может быть рекомендован в виде коммерческого алгоритма бинаризации. С. 26-36.

Modern methods of the binarization which are widely used in printing industry by printing for the halftoning process are considered in the article. From the results of binarization grayscale image from the calculations the chosen distortion measures it has been found that binarized image created using block-based halftoning algorithm has the best results, than those results which were obtained by other halftoning algorithms. Also the goal of this work was experiment on printing tone scale and measurement of the reflectance coefficients of the halftones using spectrophotometer. Gradation curves for given printer model were obtained. It is founded, that for the block-based binarization algorithm increasing a contrast is observed, that confirmed by real printing experiment. From the analysis of the properties block-based binarization algorithm was discovered that it can be recommended as a commercial halftoning algorithm.

Ключевые слова: цифровое изображение, полутоновое изображение, блочный алгоритм бинаризации, растрирование, бинаризация, меры искажения, градационная кривая, модель принтера.
Keywords: digital image, grayscale image, block-based binarization algorithm, halftoning, distortion measures, gradation curve, printer model.
В статье предложен инкрементальный алгоритм, ускоряющий синтез минимального графа смежности по исходному минимальному графу смежности и новой вершине с заданной допустимой нагрузкой; доказана корректность работы такого алгоритма. Выполнен сравнительный анализ статистических оценок сложности реализаций предложенного алгоритма и двух известных алгоритмов синтеза минимального графа смежности: жадного и прямого; результаты вычислительных экспериментов представлены в виде графиков, снабжены комментариями и выводом. В целом, на наборах со средним и большим числом вершин инкрементальный алгоритм в 3-6 раз оказался быстрее, чем прямой, и в 10-50 раз быстрее, чем жадный. На наборах с небольшим числом вершин скорость алгоритмов отличается не сильно. Отмечено, что, чем больше в наборе вершин с нагрузкой 5-9 символов, тем более велик разброс отношения скоростей сравниваемых алгоритмов. В статье также достигнуты дидактические цели: в контексте синтеза минимальных графов смежности продемонстрировано обоснованное применение методов инкрементализации алгоритмов, статистического анализа скорости работы реализаций алгоритмов, визуализации данных, полученных в результате проведения вычислительных экспериментов. С. 3-18.

The paper provides the description of an incremental algorithm that accelerates a minimal joint graph upgrade when a new node with a correct load is inserted. The algorithms correctness is proven. We compare relative performance statistical estimates for the new incremental algorithm and two known greedy and streightforward algorithms that implement minimal joint graph synthesis. The computational experiments results are represented with plots, discussed and summarized. For the middle and large sized sets of loads, the incremental algorithm is 3-6 times faster than the streight-for-ward one and 10-50 times faster than the greedy one. For the small sized sets of loads, the algorithms permormance differs less dramatically. The relative performance variation of compared algorithms are the larger the higher fraction of loads with 5-9 symbols the set of loads has. The paper also reaches didactical goals: in the context of minimal joint grah synthesis, we demonstrate a rational application of the algorithm incrementation, an example of relative algorithmical performance statistical estimates, an approach to the visualisation of performance comparison compuational experiments.

Ключевые слова: граф смежности, вероятностные графические модели, инкрементальный алгоритм, статистическая оценка сложности, структурное обучение, машинное обучение.
Keywords: joint graph, probabilistic graphical model, incremental algorithm, performance statistical estimate, structure learning, machine learning.
В статье предлагаются реализации на языках рефал-5 и Haskell алгоритма поиска вывода в секвенциальном исчислении высказываний. Реализации сравниваются по временной эффективности и удобочитаемости. В приложениях изложены базовые сведения об использованных языках программирования. Данную статью можно рассматривать как ориентирующую программиста при выборе языка программирования для реализации машины вывода в системах автоматического доказательства теорем и других интеллектуальных системах, основанных на логическом выводе. C. 19-33.

In this paper author describes implementations of inference algorithm for sequent propositional calculus in Refal-5 and Haskell programming languages. Time efficiency and readability of these implementations are compared. Also, there is a concise description of considered programming languages presented in appendix section. The aim of this paper is to provide the basis of the programming language selection for the implementation of inference engine for artificial intelligence systems, based on logical inference and automated theorem proving tools in particular.

Ключевые слова: автоматическое доказательство теорем, пропозициональная логика, секвенциальное исчисление, рефал-5, Haskell, удобочитаемость программы, временная эффективность программы.
Keywords: automated theorem proving, propositional logic, sequent calculus, Refal-5, Haskell, readability of program, time efficiency of program.
Рассматриваются три задачи составления описания объекта по достоверной информации, полученной несколькими агентами, причём информация, которой располагает каждый агент, не полна. В первой задаче объект характеризуется своими глобальными бинарными признаками и описывается набором значений этих признаков. Во второй и третьей задачах объект представлен как множество своих элементов, характеризуется свойствами этих элементов и отношениями между ними и описывается множеством постоянных атомарных формул исчисления предикатов. Во второй задаче предполагается, что все агенты располагают одинаковыми именами частей объекта. В третьей задаче каждый агент не знает подлинных имён частей объекта и даёт им имена произвольно. Приводятся алгоритмы решения рассмотренных задач и доказываются верхние оценки числа шагов их работы. Для второй и третьей задач приведены модельные примеры работы алгоритмов. С. 5-18.

Three problems of an object description based on certain incomplete information received by several agents are under consideration. An object in the first problem is characterized by global binary features and is described by a string of these features values. An object in the second and in the third problems is presented as a set of its elements and is characterized by properties of these elements and relations between them. It is described by a set of constant atomic predicate formulas. pagebreak It is supposed that all agents in the second problem have the same name for every object element. In the third problem every agent does not know the true names of the object elements and arbitrarily gives names for them. Algorithms solving the set problems are described and the upper bounds of these algorithms run steps are proved. Model examples of an algorithm implementation are given for the second and the third problems.

Ключевые слова: мультиагентное описание объекта, формула исчисления предикатов, неполная выводимость формулы, вычислительная сложность алгоритма.
Keywords: multi-agent description of an object, predicate formula, partial deduction, computational complexity of an algorithm.
Математические методы исследования, основанные на статистике, применяются в социологии достаточно давно. С развитием теории и методов динамических систем, а также компьютерных технологий методы компьютерного моделирования становятся одним из главных инструментов исследования. Большое количество моделей, создаваемых для изучения сложных процессов, происходящих в обществе, представляют собой динамические системы или неавтономные дифференциальные или разностные уравнения с большим числом параметров. В этой ситуации важно выбрать подходящий инструмент для изучения поведения таких систем. В данной работе мы рассматриваем среду визуального моделирования RMD (RandModelDesign), созданную для работы со сложными системами, имеющую простой и удобный интерфейс и язык моделирования высокого уровня. На примерах исследованных ранее моделей социальной диффузии и социогенеза мы показываем применение пакета и обсуждаем его преимущества. С. 5-16

In sociology mathematical methods based on statistic approach have long been in use. With advances in the theory and methods of dynamical sustems , and computer technologies the computer modeling methods become one of main exploration tools. A great body of models describing complex processes in society are dynamical systems or non-autonomous differential and difference equations with a large number of parameters. In this connection the choice of an appropriate tool for study of such systems is of considerable importance. In this work we consider tye environment for visual modeling RMD (RandModelDesign) designed for studying complex systems and having simple and convenient interface and high- level modeling language. The advantages of the package are demonstrated with models of social diffusion and sociogenesis.

Ключевые слова: динамические системы, компьютерное моделирование, пакет визуального моделирования RMD, социальная диффузия, социогенез.
Keywords: dynamical systems, computer modeling, visual modeling environment RMD, social diffusion, sociogenesis.
Описывается метод генерации тестов минимальной длины для синтаксически управляемых конечных процессоров, реализующих регулярные языки. Критерий выбора тестовых вариантов выражает заданную степень покрытия дуг графа, представляющего регулярное выражение, по которому строится процессор. Поскольку дуги графа помечены семантическими метками, то критерий выражает соответствующую степень взаимодействия между семантиками, и тест гарантирует выполнение этого критерия. Метод основан на алгоритме решения задачи Китайского почтальона на ориентированном графе, выводимом из регулярного выражения, определяющем конечно-автоматный язык, реализуемом процессором. С. 17-45

A method of generation of tests of minimum length for the purpose of testing of syntax directed finite processors recognizing regular languages is described. A criterion of the test cases selection is introduced that represents the requested level of coverage for the acres of the graph that corresponds to the regular expression for which the processor has been constructed. Since the graph acres are labeled with semantic labels, the criterion defines the degree of interaction between these semantics, so such a test must be built that the criterion conditions are met. The method is based on the algorithm of the solution of the Chinese Postman Problem on a directed graph, that is built for the input regular expression that defines the language recognized by the finite processor.

Ключевые слова: задача Китайского почтальона, ориентированный граф, регулярное выражение, рёберный граф, синтаксическая диаграмма Н. Вирта, тест минимальной длины.
Keywords: Chinese Postman Problem; Directed graph; Finite processor; Line graph; Regular expression; N. Wirth’s syntactic diagrams, Test of minimal length.
В этой статье предлагается метод решения одной из классических задач оптимизации --- задачи о максимальном потоке. Алгоритм основан на общей процедуре балансирования дуг и не дает выигрыша по времени работы относительно существующих методов, однако обладает другими полезными свойствами: простую реализацию на распределенных вычислительных системах, сохранение близости к оптимальному решению при изменении параметров сети во времени. Рассматривается два варианта алгоритма: рандомизированный и синхронный. Рандомизированная версия использует идеи покоординатного градиентного спуска и рандомизированных алгоритмов стохастической аппроксимации. Рандомизированная версия оказывается предпочтительней, так как имеет такой же порядок сходимости (экспоненциальный), но при этом устойчива к помехам и допускает более простую распределенную реализацию по сравнению с синхронной версией. С. 46-61.

This paper presents an algorithm for solving one of the fundamental optimization problems --- maximum flow problem. The algorithm is based on the ideas of arc balancing procedure and projected gradient method. Although the algorithm does not improve asymptotic complexity over existing methods it still possess some usefull properties: natural implementation in distributed systems and convergence to an optimal solution even if network parameters are changing slightly over time. Two versions of the algorithm are considered: randomized and concurrent. Both versions mainain adaptability but randomized version is preferable due to better convergence rate and simpler implementation in distributed systems.

Ключевые слова: оптимизация с ограничениями, градиентный спуск, распределенные алгоритмы, рандомизированные алгоритмы, стохастическая аппроксимация, задача о максимальном потоке.
Keywords: constraint optimization, gradient descent, distributed algorithms, randomized algorithms, network flow.
Описывается алгоритм минимизации приведённых детерминированных конечных автоматов, основанный на использовании классов эквивалентности по признаку неразличимости множеств цепочек, принимаемых в соответствующих состояниях. Проводится сравнение с алгоритмом Дж. Хопкрофта, в котором классы эквивалентных состояний строятся, исходя из отношения различимости состояний по допустимым входным цепочкам. C. 5-14.

An algorithm for minimizing the number of states of the well-formed deterministic finite automaton is described. It is based on the use of equivalence classes on the relation of the indistinguishability of string sets accepted by the automaton. A comparison is made with the well-known algorithm of J.E. Hopcroft, which constructs the classes of equivalent states on the property of the distinguishability of input strings accepted in the corresponding states.

Ключевые слова: конечный автомат, диаграмма состояний, неразличимые состояния, алгоритм Дж.Хопкрофта.
Keywords: finite automaton, state diagram, indistinguishable states, Hopkroft’s algorithm.
Данная статья продолжает серию о языках разметки и полностью посвящена верстке таблиц в языках LaTeX и HTML

The present article is the next part of a cycle concerning the markup languages and covers the tables layout in LaTeX and HTML.

Ключевые слова: HTML, LaTeX, вёрстка таблиц

Keywords: HTML, LaTeX, tables layout
В статье представлена история языков представления онтологий. Автор описывает основные этапы эволюции, дает краткую характеристику и обзор основных свойств языков. Также в статье представлены некоторые программные инструменты, с помощью которых можно осуществлять редактирование онтологий, записанных посредством одного из языков.

The article presents the history of ontology representation languages. The author describes the main stages of evolution, gives a brief description and overview of the basic properties of languages. The article also presents some software tools that one can use to edit ontologies, represented by one of the languages.

Ключевые слова: Онтологии, программные инструменты.

Keywords: ontology, programming tools
В статье описывается опыт автора по преподаванию и использованию операционных систем. Анализируется текущая, благоприятная для студентов и преподавателей, ситуация в области активной разработки ОС, в том числе – с открытым кодом. Предлагается ряд методов, современных инструментов и ресурсов для преподавания ОС.

The article describes the author's experience on teaching and using operating systems. The current situation is analyzed in the area of agile OS development (including open source OS projects), which is beneficial both for students and for teachers. A number of methods, modern tools and resources for teaching OS are proposed.

Ключевые слова: операционные системы, Windows, Solaris, UNIX, Linux, IBM 360, «Эльбрус
Keywords: operating systems, IBM, linux, solaris, unix, windows.
Рассматривается моделирование генераторов Алгола 68 в форме объектов-конструкций, а также результатов их исполнения, то есть значений имён соответствующих видов. В частности, обсуждается представление косвенных имён. Демонстрируется их использование на примерах.

The modelling of the Algol 68 generators in the form of object-constructions, as well as results of their elaboration, i.e. values of names of appropriating types, is considered. In particular, the representing of indirect names is discussed. Their use based on examples is demonstrated.

Ключевые слова: генератор, имя, присваивание.
В статье рассмотрена концепция параметризованных типов данных (generics), играющая ключевую роль в современном программировании, и сформулированы предложения авторов по расширению параметризованных типов в Java. Статья написана по материалам доклада на международной конференции EclipseCon 2011 Europe, Людвигсбург, Германия, ноябрь 2011 г.

The article covers the concept of generic data types that plays key role in modern programming, and the proposal by the authors on extending generics in Java. The article is based on the talk at the International Conference EclipseCon 2011 Europe, Ludwigsburg, Germany, November 2011.

Ключевые слова: параметризованные типы данных (generics), абстрактные типы данных, шаблоны, переменные виды (модалы), параметризованные пакеты, Simula 67, Ada, Java, C++, C#.
Keywords: parametrized data types (generics), abstract data types, templates, modals, generic packages, Simula 67, Ada, Java, C++, C#.
Цель данной статьи – методологическая. Описывается опыт применения модифицированных синтаксических диаграмм Н. Вирта в SYNTAX-технологии, разработанной в связи с реализацией языка программирования Алгол 68 в начале 1970-х. С. 3-19.

The purpose of the article is a methodological one. An application of modified the Wirth's syntactic charts is described in connection with the implementation of the programming language Algol 68 in the early 1970s.

Ключевые слова: грамматики, синтаксические диаграммы Н. Вирта, граф-схемы, трансляции.
Keywords: grammars, Wirth syntactic flowcharts, graph-schemes, regular splines, translations.
Описаны реализации классического алгоритма моделирования процессов агрегации, ограниченной диффузией, как на плоскости, так и на триангуляционной сетке. Разработаны и реализованы оптимизации этих алгоритмов, основанные на априорной оценке вероятности присоединения частицы к граничным точкам агрегата. Дана оценка сложности описываемых алгоритмов. Приведены результаты численных экспериментов. С. 3-8.

The implementations of diffusion-limited aggregation algorithms both on plane and a surface approximated by irregular triangulation net are described. The optimization of the method based on the a priori estimation of the sticking probability of a particle to the aggregation (joining coefficient) has been proposed and realized. The algorithm complexity estimation and results of numerical experiments are described.

Ключевые слова: процессы агрегации, ограниченной диффузией; алгоритмы на триангуляционной сетке; априорная оценка вероятности присоединения.
Keywords: diffusion-limited aggregation processes, algorithms on triangulation net, a priori estimation of joining probability.
В работе рассматриваются две задачи анализа данных геномного и метагеномного секвенирования — задача de novo сборки генома (сборка неизвестного генома) и задача сравнительного анализа метагеномов, которая возникает при анализе геномов микроорганизмов из почв, океанов, кишечника человека и т. д. Несмотря на то, что эти задачи в основном возникают у исследователей, работающих в области биологии, их использование в образовательных целях — необходимый шаг при обучении молодых медиков, биологов и биоинформатиков, а также для повышения квалификации специалистов из этих областей. В настоящей статье приводится обзор методов сборки генома и сравнительного анализа метагеномов, исследуется вопрос применимости существующих средств для обучающихся и предлагаются новые подходы к решению данных задач. Такие подходы использовались авторами при обучении студентов в Санкт-Петербургском политехническом университете Петра Великого. В работе также приводятся результаты экспериментов по сравнению предложенных подходов с известными. С. 5-15.

In this paper we address two problems of analyzing genome and metagenome sequencing data — de novo genome assembly problem (assembly of an unknown genome) and problem of comparative metagenome analysis which arises in the analysis of microorganisms in soil, sea, human gut, etc. Despite these problems are of interest to scientists working in the biology area, using them for education is essential for teaching medical students, biologists, bioinformaticians and also in the process of further training of specialists in this areas. In this paper we present a survey of methods for de novo genome assembly and comparative metagenome analysis, examine the possibility of using such approaches in educational processes and propose novel approaches for solving these problems. Proposed solutions have already been used for educating students in the Peter the Great St.Petersburg Polytechnic University. In this paper we also present the results of experiments of comparing proposed methods against known ones.

Ключевые слова: биоинформатика, ДНК, геном, метагеном, секвенирование ДНК, сборка генома de novo, сравнительный анализ метагеномов, персональный компьютер.
Keywords: bioinformatics, DNA, genome, metagenome, DNA sequencing, de novo genome assembly, comparative metagenome analysis, personal computer.
Рассматривается одна из базовых задач вычислительной геометрии (Computational Geometry) - построение выпуклой оболочки конечного множества точек на плоскости. Представлены три алгоритма решения задачи: метод Джарвиса («заворачивания подарка»), обход Грэхема и последовательный (рекуррентный) алгоритм. В следующей статье будут рассмотрены другие алгоритмы построения выпуклой оболочки и связь данной задачи с задачей сортировки.
Данная статья открывает серию, посвященную языкам разметки текста, и основана на лекциях, которые автор прочитал в СПбГЭТУ "ЛЭТИ" осенью 2007 г. Эта статья содержит введение в язык TeX вместе с примерами написания простейших программ, а также рассказывает о макропоследовательностях в TeX.

The article represents the first article of a cycle concerning the markup languages. The article based on the course delivered in Saint-Petersburg Electrotechnical University "LETI" and covers the introduction in TeX.

Ключевые слова: TeX, LaTeX, вёрстка математических формул

Keywords: formatting of the mathematical formulas, HTML, LaTeX
Данная статья продолжает серию о языках разметки. В ней обсуждаются основные средства форматирования текстов в языках LaTeX и HTML: переключение шрифтов, параметры абзацев и создание списков.

The present article is the next part of a cycle concerning the markup languages. The article covers the essential formatters in LaTeX and HTML: switching the fonts, paragraph's characteristics, creating the lists.

Ключевые слова: HTML, LaTeX, форматирование текстов.

Keywords: HTML, LaTeX, text formatting
В статье рассматриваются принципы работы синтактико-семантического анализатора, разработанного на основе теории Тузова В.А., с точки зрения обработки существительных. Данная система получает синтаксическую структуру предложения, совпадающую с семантической. Кроме того, анализатор выбирает правильные семантические альтернативы слов, в том числе существительных. Материал статьи снабжен значительным числом поясняющих примеров.

The article describes the functions of syntactic-semantic analyzer based on the theory of V. Touzov and the nouns treatment. The given system receives the syntactic structure of a sentence, that matches to the semantic one. The analyzer chooses the correct semantic word alternatives, including nouns. The article contains some practical examples.

Ключевые слова: синтаксическая структура, семантическая структура

Keywords: semantic structure, syntactic structure
Алгоритм Тарского позволяет установить истинность или ложность любого утвержения про конечное количество вещественных чисел. Вместе с методом координат Декарта это позволяет автоматически доказывать широкий класс теорем элементарной геометрии. Изложенный здесь вариант алгоритма предназначен для первоначального знакомства с этой областью - его нетрудно понять, несложно запрограммировать, но полученная программа будет крайне неэффективной.

Tarskis algorithm allows to determine whether a given statement about a finite set of real numbers is true of false. Together with the Cartesian coordinate system, it allows to prove automatically a large class of theorems of elementary geometry. The version of the algorithm presented here is suitable for introduction to the subject - it is not difficult to understand the algorithm, it is easy to write a program, but it would be extremely inefficient.

Ключевые слова: Алгоритм Тарского, разрешимость элементарной алгебры и геометрии, элиминация кванторов.
Keywords: quantors elimination, solvability of elementary algebra and geometry, Tarski's algorithm
Рассматривается представление значений простых видов в форме объектов-контейнеров и реализация элементарных конструктов, источников таких значений, в форме объектов-конструкций, то есть изображений соответствующих видов, а также формул над простыми значениями со стандартными операциями. Описывается реализация последовательных предложений, входящих в состав всех других предложений, таких как замкнутые, выбирающие (по логическому условию, вариантные целому или по виду) и циклические предложения.

The representation of the plain mode values in the forms of the object-containers and the elementary constructs resulting in values of such a kind, i.e. the plain denotations and the standard mode formulas, are considered. The implementation of the serial clauses constituting closed, choice using boolean, integral or united clauses, as well as the loop clauses, is described also.

Ключевые слова: значение, конструкт, окружение, последовательное предложение, стандартная операция, сцена, участок, формула над простыми значениями
Keywords: value, constuct, plain denotation, standard mode formula, serial clause, integral clause, united clause, loop clause
В статье описывается опыт автора по преподаванию и развитию технологий 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.

Ключевые слова: Sun Microsystems, Java, компиляторы, Sun Studio, операционные системы, Solaris, SPARC, открытое программное обеспечение.
При разработке многократно используемых программ важно, чтобы их выполнение было достаточно быстрым. В книге Ду Д.З. и Ко К.И. сформулирован обобщенный тезис Чёрча: «Функция, вычислимая за полиномиальное время на разумной вычислительной модели, использующей разумное измерение временной сложности, вычислима на детерминированной машине Тьюринга за полиномиальное время» (то есть принадлежит классу FP). Этот расширенный тезис Чёрча более естественно называть полиномиальным тезисом Чёрча для машин Тьюринга. «Разумность» вычислительной модели разными исследователями понимается по-разному, вследствие чего в последнее время всё чаще появляются «доказательства» (содержащие ошибки) знаменитой проблемы: верно ли, что P = NP? При этом шаг различных моделей алгоритмов трактуется интуитивно. В настоящей работе доказано, что «разумность» шага вычисления рекурсивной функции может заключаться в использовании таких рефал-5-предложений из класса FP, длина записи результата выполнения которых (включая длину записи всего изменяемого стека) увеличивается не более чем на константу, единую для всех исходных данных. В этом смысле обычное определение общерекурсивной функции не является «разумной» вычислительной моделью. Достаточно сложным является подсчет числа шагов рекурсивного алгоритма. В настоящей статье доказаны необходимые и достаточные условия полиномиальности по времени функции, реализованной на языке программирования рефал-5. Этот язык является практически реализованным обобщением таких математических моделей алгоритма как нормальные алгоритмы, а также вводимые здесь алгоритмы Маркова-Поста и рекурсивные алгоритмы Маркова-Поста. Поэтому в качестве следствий основной теоремы доказаны условия полиномиальности по времени и этих математических моделей, применимых в теоретических исследованиях. Весьма актуальным является вопрос о возможности доказательства того, что программа, написанная на языке рефал-5, задает полиномиально быструю функцию, то есть функцию, принадлежащую классу FP. В статье вводится понятие дважды полиномиальных рекурсивных вызовов рефал-5-функции, обеспечивающее решение этого вопроса.

It is important for multiple-used programs that their run be sufficiently quick. Du D.Z. and Ko K.I. have formulated a extended Church thesis: В«A function computable in polynomial time in any reasonable computational model using a reasonable time complexity measure is computable by a deterministic Nuring machine in polynomial timeВ» (i.e. it belongs to the class FP. It is more natural to call this extended Church thesis as a polynomial Church thesis for Turing machine. Different researchers differently understand the term reasonable in consequence of which at the last time many В«proofsВ» (containing mistakes) of the famous problem whether P = FP appear. In such В«proofsВ» a step of different algorithm models treats intuitively. In the present work it is proved that reasonability of a recursive function step may be consisted in the use of such refal-5-sentenses from FP, for which the length of result notation (including the lenth of all stack) increases not more than by additive constant unique for all arguments. In such a sence a usual definition of a recursive function is not a reasonable calculation model. The count of recursive algorithm steps is rather difficult. Nesessary and sufficient conditions of time polynomiality of a function, realized by means of programming language refal-5, are proved in the present paper. This language is a practicaly realized generalization of such mathematical models of algorithm notion as normal algoritm and here introduced Markov-Post algorithm and recursive Markov-Post algorithm. That is why conditions of time polynomiality of these mathematical models (used in theoretical reseaches) are proved as corollaries of the main theorem. The question whether it is possible to prove that a refal-5 program realizes a polynomiall time function (i.e. function belonging to FP) is very actual. A notion of a double polynomial recursive refal-5 function call, which provides the solution of this question, is introduced in the paper.

Ключевые слова: полиномиальные верхние оценки числа шагов алгоритма, машины Тьюринга, класс FP, функции на языке рефал-5, дважды полиномиальный алгоритм.
Keywords: polynomial time algorithm, Turing machine, class FP, refal-5 function, double polynomial algorithm.
Статья содержит два основных раздела. Первый из них (п. 2) отвечает на вопрос о том, как можно расширить понятие нормального алгоритма Маркова, включив, в частности, полиномиальные функции над длинами используемых слов и сохранив при этом объём вычислений в пределах полиномиального числа шагов. Ответом на этот вопрос является последовательность математических понятий алгоритма со всё более мощными вычислительными средствами, но тем не менее совпадающими с классом алгоритмов, полиномиальных по времени (с классом FP) при реализации их на машинах Тьюринга. Второй из основных разделов (п.3) отвечает на вопрос, каким образом можно, всё более расширяя понятие нормального алгоритма Маркова, вложить их в каждый из подклассов FP, алгоритмы которого используют промежуточную память, длина которой ограничена полиномом k-ой степени. Результаты второго раздела могут рассматриваться также и как подтверждение естественной формулировки тезиса Чёрча для последнего из классов алгоритмов, использованных в формулировках теорем этого раздела.

This paper contains two main sections. The first one (section 2) answers the question: В«How to extend the notion of Markov algorithm by inclusion of a polnomial function of a word length and to conserve computation inside polynomial number of steps?В». A sequence of mathematical notions of algorithm with more and more powerfull computational tools is presented. It is proved that every of them coinsides with the class of polynomial in time algorithms (class FP). The second one (section 3) answers the question: В«How to extend the notion of Markov algorithm in order to include it into subclass of FP containing only algorithms using intermediate memory with the length not more than a polynomial of k-th degree?В». The results of this section may be also regarded as a confirmation of the natural formulation of Church thesis for the last two classes of algoritmms used in the formulations of the theorems of this section.

Ключевые слова: полиномиальные верхние оценки числа шагов алгоритма, класс FP, полиномиальные верхние оценки памяти, подклассы FP-SPACE, нормальные алгоритмы Маркова, правила Поста.
Keywords: polynomial time algorithms, class FP, polynomial space algorithms, subclasses of FP-SPACE, Markov algorithm, Post rules.
Проведено математическое исследование и исследование с помощью компьютерного моделирования алгоритма Кейпона. В частности, получены условия линейной независимости и ортогональности сигнальных векторов и векторов координат помех.

Mathematical investigation and the investigation by means of computer simulation for Capon algorithm is done. In particular, some conditions for linear independence and for the orthogonality of signal vectors and the vectors of obstacles coordinates.

Ключевые слова: радиолокация, алгоритм Кейпона, ковариационная матрица, функция рельефа, независимые координаты, ортогональные векторы, собственные числа, собственные векторы, решетка, статистическое моделирование.
Keywords: radio-location, Capon algorithm, covariation matrix, relief function, independent coordinates, orthogonal vectors, eigenvalues, eigenvectors, grating, statistical simulation.
Описывается метод регуляризации приведённых КС-грамматик без самовставлений, основанный на топологической сортировке нетерминалов грамматики по отношению зависимости, определяемой правилами грамматики.

The method for the regularization of reduced non-self-embedding context-free grammars, based on the topological sorting of nonterminals of the grammar according the relation of the dependence defined by the grammar rules, is described.

Ключевые слова: КС-грамматика, регулярное выражение, отношение зависимости, топологическая сортировка нетерминалов, эквивалентное преобразование грамматики.
Keywords: : context-free grammar, regular expression, dependence relation, topological sorting of nonterminals, equivalent conversion of grammar.
Рассматривается аппроксимация Зламала для представления функции заданной на двумерной области. Из аппроксимационных соотношений выведены выражения базисных элементов аппроксимации. Для триангуляции специального вида получены калибровочные соотношения, обеспечивающие удобный способ перехода между базисами аппроксимации при локальном укрупнении триангуляции. С. 20-28.

Zlamal-type approximation for representation of a function defined upon a two-dimensional area is considered. Basic elements of the approximation are derived from the approximation relations. For the triangulation of a special kind, the calibration relations are presented, which provide a convenient way of the basis transformation upon the local triangulation enlargement.

Ключевые слова: аппроксимация, сплайны, вейвлеты.
Keywords: approximation, splines, wavelets.
В работе всесторонне изучается методология полногеномного поиска связей фенотипа с одним или несколькими генетическими маркерами. В данной части работы рассмотрены различные типы данных, наиболее часто встречающиеся при проведении генетических исследований, и методы их анализа. C. 17-32.

Methodology of genome association discovery is discussed comprehensively in this paper. In this part we consider main types of statistical data arises in genome association study experiments and wide range of statistical tests for these types of data analysis.

Ключевые слова: полногеномный поиск закономерностей, GWAS, категориальные данные, данные типа времени жизни, модель Кокса, короткие временные ряды, обобщенные линейные модели.
Keywords: Whole genome association discovery, genome wide association study (GWAS), categorical data, survival data, Cox model, longitudinal data, generalized linear models.
Очень часто непосредственное использование стандартных моделей приводит к результатам низкого качества. В статье рассмотрены два примера. Первый пример касается классификации популярных данных «Credit», полученных с платформы Kaggle. В качестве классификатора мы используем стандартную функцию nnet (нейронные сети) в программной среде R. Проблема состоит в том, что данные «Credit» являются несбалансированными, а функция nnet склонна игнорировать класс, который составляет меньшинство. В качестве решения проблемы несбалансированности мы предлагаем рассмотреть большое число относительно небольших и сбалансированных подмножеств, в которых элементы из тренировочной базы данных отбираются случайным образом. Второй пример касается широкоизвестных данных MNIST при использовании стандартной функции svm (метод опорных векторов) в среде Python. Показана необходимость нормализации исходных признаков. С. 16-24.

In many cases direct application of the standard classification models leads to poor quality of results. In this paper we consider two examples. The subject of the first example are popular imbalanced data «Credit» from the platform Kaggle. Standard function nnet (neural networks) in the program environment R is used as a classificator. This function is ignoring an important minority class. As a solution to this problem, we are proposing to consider a large number of relatively small and balanced subsets, where elements were selected randomly from the training set. The subject of the second example are famous data MNIST and standard function svm (support vector machine) in the environment Python. The necessity of normalisation of the original features is demonstrated.

Ключевые слова: машинное обучение, анализ данных нейронные сети, однородное ансамблирование, несбалансированность данных, распознавание образов, метод опорных векторов.
Keywords: machine learning, data mining, neural networks, homogeneous ensemble, imbalanced data, patterns recognition, support vector machine.
В статье описываются классы сложности алгоритмов, приводится пример разработки алгоритмов различной сложности, практического использования результатов теории в криптографии.
Статья рассказывает о курсах и лекциях по Computer Science, которые регулярно проходят в центре Санкт-Петербурга. Дан обзор курсов, прочитанных в прошлых семестрах, приведен план на осенний семестр 2008 г. Подробно рассказано о курсе "Эффективные алгоритмы". На диске к журналу - pdf-слайды и видеоматериалы по теме "Приближенные алгоритмы", читаемой в рамках этого курса.

The article gives a broad overview of the courses and lectures delivered in the Saint-Petersburg Computer Science Club during the past term. The curriculum for the 2008 is given. The course "Effective Algorithms" is discussed more detailed. On the CD the pdf-presentations and video materials for one theme from this course can be found

Ключевые слова: Computer Science, эффективные алгоритмы, приближенные алгоритмы.

Keywords: approximate algorithms, computer science, effective algorithm
В статье рассматриваются вопросы правильности перевода англоязычной терминологии по ИТ на русский язык. Предлагается идея создания КПП - Web-словаря правильных переводов и типичных ошибок при переводе, которых следует избегать.
Обычно программа, работающая с синтаксическими структурами естественного языка, должна содержать синтаксический анализатор - парсер. Альтернативой созданию своего парсера является использование существующих, которые могут не совсем хорошо подходить для конкретной задачи программы. Лучшее решение заключается в создании одного парсера, выдающего в результате работы такую структуру данных, которая могла бы быть применима к как можно большему количеству прикладных задач. В статье предложен такой формат выходных данных парсера, приведены его преимущества по сравнению с более традиционными структурами представления текста и показана его к ним сводимость, а также возможности этого формата по автоматическому разрешению лексических неоднозначностей.

Typically, an NLP tool which has to work with syntactic structures should contain a parser. An alternative to developing one’s own parser is to use existing parsers that are likely to be not so well suited for the tool’s particular goals. A better solution would be to have one parser to produce some output that would be able to fit as many domain problems as possible. Such output format is presented, and its advantages are discussed, including backward compatibility to other widely used structures and lexical ambiguity resolution.

Ключевые слова: Парсер, структура непосредственно составляющих, структура зависимостей, синтаксис, семантика, разрешение неоднозначностей.

Keywords: ambiguity resolution, component structure, dependency structure, semantics, syntax, parser
Реверсивный поиск – один из алгоритмов, идея которого «витает в воздухе» десятилетиями и который часто изобретается заново программистами, знакомыми с такими алгоритмами, как поиск в ширину (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.

Ключевые слова: реверсивный поиск, перебор подграфов, перебор поддеревьев
Keywords: reverse search, enumeration of the subtrees, enumeration of the subgraphs
Рассматривается представление описаний простых видов в форме объектов-конструкций, а также окружений, реализуемых в виде иерархии участков в стеке, заполненных индикаторами, посредством которых программа получает доступ к значениям. Описывается сам этот метод доступа.

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.

Ключевые слова: окружение, последовательное предложение, стек, участок.
В статье анализируется 17-летний опыт автора в области обучения компиляторам. Подчеркивается фундаментальный характер компиляторов как учебной дисциплины и их важность для полноценного современного университетского образования в области ИТ. Рассмотрены принципы построения современного курса по компиляторам, подход автора к обучению компиляторам и современные инструменты построения компиляторов и обучения компиляторам. Даны ссылки на публикации автора в данной области и на полезные Web-ресурсы.

The article analyses the author's 17-years experience in compiler teaching. Fundamental nature of compiler development as educational discipline and their importance for modern university education in the IT area are emphasized. Principles of organization of a modern compiler course and the author's approach to compiler teaching, and modern tools for compiler development and compiler teaching are covered. References to author's publications in this area and to useful Web resources are provided.

Ключевые слова: компиляторы, динамические компиляторы, надежные и безопасные компиляторы, лексический анализ, синтаксический анализ, семантический анализ, оптимизация, генерация кода, инструменты построения компиляторов, Java, .NET, Microsoft Phoenix, ANTLR, CoCo/R.
Keywords: compilers, just-in-time (JIT) compilers, trustworthy compilers, lexical analysis, parsing, semantic analysis, optimization, code generation, compiler development tools, Java, .NET, Microsoft Phoenix, ANTLR, CoCo/R.
На основе анализа истории развития языков программирования делается вывод, что предметно-ориентированный подход может стать следующим шагом эволюции языков программирования и существенно повысить продуктивность и качество разработки программных продуктов. В статье выявляются общие черты существующих методик применения предметно-ориентированного подхода, и на основе анализа их недостатков формулируется новая методика его применения. Приведен пример системы, использующей предметно-ориентированный язык, позволяющий преподавателям, не имеющим опыта программирования, формализовывать сложные условия геометрических задач.

Based on analysis of the history of programming languages papers [3,5] conclude that language-oriented approach may become the next step in the evolution of programming languages, and significantly improve productivity and quality of software development. The paper identifies common features of existing methods of language-oriented approach usage, and based on an analysis of their shortcomings presents a new method of application of the approach. An example of a system that uses a domain-specific language is presented. The language is used to enable teachers that are not skilled in programming to formalize complex statements of geometric problems.

Ключевые слова: предметно-ориентированные языки, дистанционное обучение, использование компьютера в обучении, языково-ориентированное программирование, динамическая геометрия.
Keywords: Domain Specific Languages, Distance Learning, computer aided education, Language Oriented Programming, Dynamic geometry.
Задача Штейнера на ориентированных графах – наиболее общая в семействе задач Штейнера. Известно, что она является NP-полной. Существует алгоритм для точного решения задачи, основанный на динамическом программировании, пригодный для задач маленького размера. В нашей статье приводятся специальные типы задач, на которых с помощью модификации названного метода точное решение может быть получено за полиномиальное время. Кроме того, представлен метод, предназначенный для приближенного решения произвольных задач Штейнера на ориентированных графах.

Steiner tree problem on oriented graphs is the most general in the family of Steiner tree problems. It is known to be NP-complete. There exists an algorithm to find an exact solution, based on dynamic programming, but applicable only for problems of modest size. Here special types of problems are presented, for which this algorithm is modified to find exact solution at polynomial time. Also approximate method, based on this algorithm for solving arbitrary problems is produced.

Ключевые слова: задача Штейнера, ориентированный граф, динамическое программирование, функция Беллмана, приближенные алгоритмы.
Keywords: Steiner problem, oriented graph, dynamic programming, Bellman function, approximation algorithms.
Работа посвящена разработке и реализации основанного на интервальной арифметике алгоритма локализации инвариантных множеств динамических систем. Используется метод аппроксимации системы с помощью символического образа, представляющего собой ориентированный граф, построенный по системе. Ячейки разбиения рассматриваются как интервальные вектора в пространстве соответствующей размерности. Оценка параметров символического образа позволяет определить точность построения. Приведены результаты численных экспериментов и сравнение с алгоритмами локализации, основанными на обычной арифметике.

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

The applicability of the method of modified fractal signature to classify images of two different application domains is considered. The method is based on the calculation of the Minkovsky dimension for a fractal surface that is the graph of the gray-level function of the image. It is well known that for nonempty bounded sets in Euclidean space the Minkovsky dimension coincides with the capacity one, but it can be calculated more effectively. The given examples show that the method allows us to obtain reliable results for classes of images under consideration.

Ключевые слова: фрактальная размерность, размерность Минковского, емкостная размерность, анализ и классификация изображений.
Keywords: fractal dimension, Minkovski dimension, capacity dimension, image analysis and classification.
В данной статье рассмотрен метод, позволяющий проводить локальное укрупнение правильной триангуляции, заданной на двумерной плоскости, сохраняющий правильность результирующей триангуляции. Представлен алгоритм, позволяющий построить триангуляцию с локальным укрупнением по заданой исходной триангуляции. Реализована программа, позволяющая курантовскую аппроксимацию поверхности на исходной триангуляции заменить курантовской аппроксимацией поверхности на локально укрупненной с учетом особенностей поверхности триангуляции. Проведена апробация предложенного алгоритма на модельных примерах. С. 29-34.

This article considers method, allows to process local triangulation enlargement on double-dimension surface, while keeping it's regularity. Proposed algorithm, building triangulation with local enlargement on provided source triangulation. Program, allowing to replase Kurant's approximation on source triangulation replace with Kurant's approximation on enlarged with taking into account local singularities triangulation was implemented. Aprobation of considered algorithm is presented.

Ключевые слова: курантовская аппроксимация, аппроксимация поверхности, триангуляция, локальное укрупнение.
Keywords: Kurant approximation, surface approximation, triangulation, local enlargement.
В статье рассматривается эволюция идеи учета последующего контекста, возникшая в середине 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.

Ключевые слова: учет последующего контекста, методы сначала-в-ширину и сначала-в-глубину, рекурсивно-переборные задачи, BDD, оптимизация объектного кода.
Статья посвящена имитационному моделированию квантового алгоритма Дойча в среде MATLAB/Simulink.

The article is devoted to quantum Deutsch’s algorithm simulation in the MATLAB/Simulink environment.

Ключевые слова: квантовый алгоритм Дойча, MATLAB, Simulink.
Keywords: quantum Deutsch’s algorithm, MATLAB, Simulink.
Предложены новые варианты измельчения симплициального топологически правильного подразделения вблизи границы области с сохранением свойства невырожденности.

New variants of nongenerate refinement for simplicial subdivision near the boundary of region are discussed. Construction of refinement is offered.

Ключевые слова: алгоритм, симплициальный комплекс, подразделение, невырожденность, измельчение, бинарное дерево.
Keywords: algorithm, simplicial complex, subdivision, nondegeneracy, refinement, binary tree.
Рассматривается методика использования характеристик фрактальной геометрии на примере анализа экспериментальных нейтронно-физических данных, регистрируемых измерительным комплексом при испытании активной зоны ядерной энергетической установки. На основе применения вейвлет-фильтрации шумовых помех измерительного тракта и вычисления локального индекса фрактальности по относительно короткому дискретному ряду эквидистантного временного сигнала определяются моменты качественного изменения характера функционирования исследуемой системы. Приводятся результаты исследования для режимов, в которых проявлялись теплогидравлическая неустойчивость циркуляции теплоносителя и связанные с этим стохастические колебания сигналов нейтронной мощности реакторной установки.

The paper describes the use of fractal geometry characteristics for analysis of experimental neutron data which is recorded by measuring system during testing of reactor plant core. Moments of qualitative changes in the system are determined by using the wavelet filtration of noise interferences in the measuring channel and calculation of the local fractal index over relatively short discrete sequence of equidistant time signal. The paper presents results for reactor behavior with thermal-hydraulic instability of coolant circulation and related stochastic oscillations of neutron power signals.

Ключевые слова: фрактальная размерность, индекс вариации, неустойчивость, временные ряды, обработка сигнала, вейвлет-преобразование.
Keywords: Fractal dimension, index of variation, instability, time series, signal processing, wavelet transform.
Тонкие оболочки, подкрепленные ребрами переменной высоты, позволяют снизить опасную концентрацию напряжений. Для анализа напряженно-деформированного состояния подкрепленной конструкции необходимо знать не только наибольший прогиб и наибольшее нормальное напряжение, но и картину прогибов и интенсивности напряжений по всей оболочке. Более того, построение поля прогибов оболочки от поверхности конструкции (а не от плоскости) может более наглядно отразить процесс деформирования. Это все можно учесть, разрабатывая специальное программное обеспечение для дальнейшего практического применения, обладающее удобным графическим интерфейсом и предоставляющее результаты расчетов в удобном пользователю виде. Целью данной работы является описание визуализации математической модели напряженно-деформированного состояния тонкостенных оболочечных конструкций, подкрепленных ребрами переменной высоты и имеющих в качестве составных частей элементы следующих оболочек: пологой, цилиндрической, конической, сферической, тороидальной, катеноидной. Описываемые в данной работе результаты получены при помощи разработанного программного модуля, который может быть использован в практике расчета оболочечных конструкций при их проектировании, а также в научных исследованиях, связанных с нелинейными проблемами деформирования тонкостенных конструкций. В разработанном программном модуле геометрическая форма оболочки задается при помощи параметров Ламе, а сама оболочка и подкрепляющие ее ребра рассматриваются как оболочка ступенчато-переменной толщины. Это существенно упрощает подготовку задачи к решению. Контакт ребра и обшивки происходит по полосе, что более точно отражает реальную работу конструкции. С. 35-45.

Thin shells that are reinforced by ribs of variable height can reduce harmful stress concentrations. For analisys of the stress-strain state of a stiffened structure it is necessary to know not only the greatest deflection and the maximum normal stress but also a picture of the deflection and the stress intensity across the shell. Moreover the construction of the field deflection of the shell from the surface structure (and not from a plane) can be more clearly reflect the deformation process. It can be taken into account by developing special software for further practical use, that has a convenient graphical interface and provides the results of calculations in a user friendly form. The purpose of this paper is to describe an imaging of a mathematical model of stress-strain state of thin-walled shell structures that are reinforced by ribs of variable height. The results that are described in this paper have been obtained using the developed software module, which can be used in the practice of calculating shell structures in their design, as well as in scientific research related to the problems of nonlinear deformation of thin-walled structures. The geometric shape of the shell is defined using Lame parameters, and the shell itself and its supporting ribs are seen as step-variable thickness shell. The contact of rib and shell occurs on the band that more accurately reflects the actual work of construction.

Ключевые слова: тонкие оболочки, подкрепленные оболочки, ребра жесткости переменной высоты, устойчивость, прочность, напряженно-деформированное состояние, визуализация оболочечных конструкций.
Keywords: thin shells, stability and strength of the shells, visualization of thin shells, reinforced shells, ribs of variable height.
Статья продолжает цикл, начатый в №№ 1, 2, 3 за 2007 г. Аыторы раасказывают об одной из базовых задач вычислительной геометрии – задаче о пересечении отрезков на плоскости, знакомят читателя с таким важным и эффективным приемом построения геометрических алгоритмов, как метод заметания плоскости прямой линией.
Канонический код – это способ записи графа, инвариантный относительно изоморфизма. В статье вкратце объясняется значимость канонических кодов и показывается связь задачи вычисления канонического кода с другими задачами, известными из курса теории алгоритмов. Приводится алгоритм вычисления канонического кода для дерева с помеченными вершинами и рёбрами, который работает за линейное время от размера дерева. Алгоритм основан на известном алгоритме проверки изоморфизма двух деревьев.

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.

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

The main objective of the article is to demonstrate the ability of the education software development and research in the domain of the quantum computing. This article describes the use of the free software tools for quantum simulation: libquantum library along with GUI toolkit Qt.

Ключевые слова: алгоритмы квантовых вычислений, библиотека libquantum, графическая библиотека Qt, открытое программное обеспечение.
Keywords: quantum computing, libquantum library, GUI toolkit Qt.
В статье рассматриваются суживающие (сокращающие перебор) стратегии для резолюционных алгоритмов логического вывода в базах знаний, построенных на основе логической модели знаний. Особенностью этих стратегий является предварительная настройка на работу с конкретными базами знаний. Для настройки используется метод абстракций и формально-грамматическая интерпретация логического вывода. Абстракция – это функция, которая отображает класс задач K1 в более простой класс K2. При решении задачи A принадлежит K1 ее отображают в задачу B принадлежит K2. Затем задача B решается, и ее решения используются для поиска решений исходной задачи A. В настоящей работе класс задач K1 – это проблема дедукции в исчислении предикатов первого порядка. Для K1 рассматриваются две абстракции – пропозициональная, при которой K2 – это проблема дедукции в исчислении высказываний, и абстракция, при которой проблема дедукции решается для конструкций, названных псевдо-предикатами. Для обеих абстракций предлагается формально-грамматическая интерпретация, позволяющая выполнить предварительную настройку, которая гарантирует перебор лишь успешных вариантов выводов. Приведенные примеры иллюстрируют достоинства предложенной методики.

In this paper restricting (reducing search) strategies for resolution algorithms of logical inference in knowledge bases formed in terms of logical model of knowledge are considered. Peculiarity of these strategies is preliminary adjustment to a concrete knowledge bases. For the adjustment an abstraction and formal-grammar interpretation of the deduction problem is used. An abstraction is a function that maps certain class of problems K1 onto a simpler class K2. In order to solve a problem A пѓЋ K1 it is mapped onto a problem B пѓЋ K2. Then B is solved and its solutions are used for searching solutions of the initial problem A. In the paper class K1 is the deduction problem in the first-order predicate calculus. Two abstractions are considered for K1. The first one is propositional abstraction in which K2 is the deduction problem in the propositional calculus. In the second one the deduction problem is solved for structures named pseudo-predicates. For both abstractions formal-grammar interpretations are proposed that allow to fulfill the preliminary adjustment which guarantees searching only successful variants of inference . Given examples illustrate virtues of suggested methods.

Ключевые слова: база знаний, логическая модель представления знаний, проблема дедукции, суживающая стратегия логического вывода, входная линейная резолюция, метод абстракций, формальная грамматика.
Keywords: knowle3dge base, logical model of knowledge, deduction problem, restricting strategy of logical inference, input linear resolution, abstraction method, formal grammar.
Заметка содержит описание алгоритма, нумерации элементов выборки m элементов из n. Благодаря использованию биномиальных разложений натуральных чисел, алгоритм становится универсальным и удобным для приложений.

The notes contain description of natural renumbering algorithm for units of sample of m elements from n. Algorithm based on presentation of natural numbers as sum of binomial coefficients.

Ключевые слова: выборка m элементов из n, биномиальные коэффициенты, биномиальное разложение.
Keywords: sample of m elements from n, binomial coefficients, binomial decomposition.
Для пополнения баланса выберите страну, оператора и отправьте СМС с кодом на указанный номер. Отправив одну смс, вы получаете доступ к одной статье.
Закрыть