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.

Цель работы – создание инструментального средства для трансляции описаний графов переходов автоматов, представленных в формате 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.

Статья посвящена проблемам доказательства полиномиальной вычислимости функций, другими словами, доказательства принадлежности функций классу 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.

В [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.

В статье излагается формализм для описания двумерных графо-подобных диаграмм. Основанный на формализации диаграмм, предложенной Е.А. Жоголевым, он расширяет ее, вводя конкретные типы двумерных конструкций и допустимые отношения между ними. При этом рассматриваются элементы таких визуальных языков, как сети Петри, 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.

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

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.

Облачная платформа 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.

Вводятся алгоритмы Маркова-Турчина как обобщение алгоритмов, введённых автором в [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.

Этот текст является слегка отредактированной стенограммой содоклада на совместном заседании Санкт-Петербургского Математического общества и Секции математики Дома учёных 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].

В статье рассматривается подход к перебору субоптимальных решений, основанный на введении специальных процессов перебора – «перечислителей», решающих задачи такого типа, и создании специальных, достаточно простых операций, позволяющих получать перечислители из более простых. Приводятся примеры таких операций. С. 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.

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

Вводятся иерархии классов сложности функций как из 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.

В работе всесторонне изучается методология полногеномного поиска зависимости фенотипа с одним или несколькими генотипами. В данной части работы обсуждается проблема интерпретации результатов множества тестов, реализация статистических методов, описанных в первой части работы, на языке программирования R и особенности использования статистических методов в комплексных исследованиях заражаемости ВИЧ и развития СПИД. Также будут предложены некоторые соображения, касающиеся интерпретации результатов однотипных статистических тестов, полученных на базе независимых экспериментов. С. 3-17.

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.

Язык программирования рефал-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.

Несмотря на стремительный рост как производительности, так и емкости запоминающих устройств, темпы роста количества вновь создаваемых данных существенно опережают возможности их хранения и, тем более, возможности обработки. В связи с этим попытки экстенсивного подхода, основанного на наращивании мощности вычислительных систем, не могут радикально решить возникающие проблемы. В статье обсуждаются актуальные классы аналитических задач обработки данных, извлечения информации и знаний и анализируются различные альтернативные подходы к их решению. Этот круг задач и подходов, часто неформально объединяемый под зонтиком 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.

В данной статье приводятся основные понятия относительно нового направления информационных технологий - теории статистического обучения В. Вапника. Эта теория с каждым годом набирает все большую популярность, поскольку объясняет суть машинного обучения с математической точки зрения. Дальнейшие исследования данной теории могут дать существенные улучшения в скорости и качестве работы алгоритмов машинного обучения. Среди огромного количества публикаций, посвященных теории статистического обучения, автор выбрал десяток статей, в которых раскрываются основные понятия и проблемы этой теории, приводятся практически полезные алгоритмы и результаты экспериментов по сравнению различных подходов. В данной статье в сжатом виде приводятся основные результаты обозреваемых работ, что позволит специалистам, только начинающим знакомиться с этой популярной теорией, облегчить вхождение и приступить к реальным исследованиям. 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.

Язык программирования рефал-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–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.

Исследование влияния сверхмалых доз вещества (или излучения) на биологические системы является важной задачей. Многочисленные исследования в естест венных науках и особенно в физике и биофизике живых организмов привели к созданию модели действия сверхмалых доз, которая основана на специальной структуре воды в живых клетках (фрактальные кристаллы) и механизме передачи и преобразования энергии в цепочке биомолекул. В настоящее время наблюдать это влияние непосредственно в живом организме невозможно, но можно регистрировать происходящие в нем изменения используя данные различных измерений состояния организма. Большая часть таких данных представляет собой цифровые изображения, что делает возможным применение математических и компьютерных методов исследования. В работе описано применение математических методов для анализа изображений биомедицинских препаратов и получения численных характеристик изучаемого процесса. Описан метод исследования малых доз электромагнитного излучения, используемого в магнитотерапии. С. 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.

В статье рассмотрена задача построения симплициального подразделение специального вида, допускающего локальное укрупнение в трехмерном слое. Предложен метод, позволяющий однозначно определить подразделение с необходимыми свойствами. Выведены калибровочные соотношения аппроксимации Куранта, соответствующие укрупнению симплициального подразделения. С. 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.

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

Метод минимизации приведённых детерминированных конечных автоматов, описанный в частности в [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.

Разработка систем поиска основана на успехе поиска контента. Основной проблемой в такой разработке является высокая вероятность неправильного результата при поиске в случае нахождения ошибки в системе. В статье рассматривается алгоритм, увеличивающий шанс успешного нахождения пользователем интересующего его контента в системе поиска, на основании пользовательского взаимодействия. Алгоритм описывает процесс получения данных системой, преобразования данных в ранжируемые сущности, а также определения отображаемых результатов. Также в статье приведены примеры основных алгоритмов, вошедших в основу алгоритма <<ложного пути>>, их особенности и проблемы. Кроме того, в статье предоставлены дальнейшие пути улучшения алгоритма. 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.

Статья посвящена изложению алгоритма выделения максимальной общей с точностью до имён переменных подформулы двух элементарных конъюнкций атомарных предикатных формул. Предлагаемый алгоритм использует введённую ранее автором модификацию обратного метода Маслова, а также Муравьиные тактики и параллельные вычисления. Проблема выделения максимальной общей с точностью до имён переменных подформулы предикатных формул имеет достаточно широкое применение при построении эффективных алгоритмов решения задач искусственного интеллекта, допускающих формализацию средствами исчисления предикатов. Приведены асимптотические оценки числа шагов работы описанного алгоритма. С. 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.

В статье рассматриваются современные методы бинаризации, которые широко используются в полиграфии при печати для процесса растрирования, и связанные с этим процессом теоретические вопросы растрирования. Особое внимание уделено блочному алгоритму бинаризации, относящемуся к методам, основанным на условии равенства яркостей, когда бинарное изображение имеет яркость равную яркости исходного изображения. Приводится его описание, а также краткое описание алгоритмов, выбранных для сравнения. Изображение, полученное бинаризацией полутонового изображения блочным алгоритмом бинаризации, на основе вычисления выбранных мер искажений показывает лучшие характеристики по сравнению с другими алгоритмами бинаризации. Также целью данной работы являлся эксперимент по печати тоновой шкалы и измерение коэффициентов отражения полутонов при помощи спектрофотометра. В ходе эксперимента были построены градационные кривые для заданного принтера и проанализированы полученные характеристики. Найдено, что для блочного алгоритма наблюдается увеличение контраста, что подтверждается реальным печатным экспериментом. При анализе свойств блочного алгоритма бинаризации выявлено, что он может быть рекомендован в виде коммерческого алгоритма бинаризации. С. 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.

В статье предложен инкрементальный алгоритм, ускоряющий синтез минимального графа смежности по исходному минимальному графу смежности и новой вершине с заданной допустимой нагрузкой; доказана корректность работы такого алгоритма. Выполнен сравнительный анализ статистических оценок сложности реализаций предложенного алгоритма и двух известных алгоритмов синтеза минимального графа смежности: жадного и прямого; результаты вычислительных экспериментов представлены в виде графиков, снабжены комментариями и выводом. В целом, на наборах со средним и большим числом вершин инкрементальный алгоритм в 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.

В статье предлагаются реализации на языках рефал-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-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.

Математические методы исследования, основанные на статистике, применяются в социологии достаточно давно. С развитием теории и методов динамических систем, а также компьютерных технологий методы компьютерного моделирования становятся одним из главных инструментов исследования. Большое количество моделей, создаваемых для изучения сложных процессов, происходящих в обществе, представляют собой динамические системы или неавтономные дифференциальные или разностные уравнения с большим числом параметров. В этой ситуации важно выбрать подходящий инструмент для изучения поведения таких систем. В данной работе мы рассматриваем среду визуального моделирования 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.

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

В этой статье предлагается метод решения одной из классических задач оптимизации --- задачи о максимальном потоке. Алгоритм основан на общей процедуре балансирования дуг и не дает выигрыша по времени работы относительно существующих методов, однако обладает другими полезными свойствами: простую реализацию на распределенных вычислительных системах, сохранение близости к оптимальному решению при изменении параметров сети во времени. Рассматривается два варианта алгоритма: рандомизированный и синхронный. Рандомизированная версия использует идеи покоординатного градиентного спуска и рандомизированных алгоритмов стохастической аппроксимации. Рандомизированная версия оказывается предпочтительней, так как имеет такой же порядок сходимости (экспоненциальный), но при этом устойчива к помехам и допускает более простую распределенную реализацию по сравнению с синхронной версией. С. 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.

Описывается алгоритм минимизации приведённых детерминированных конечных автоматов, основанный на использовании классов эквивалентности по признаку неразличимости множеств цепочек, принимаемых в соответствующих состояниях. Проводится сравнение с алгоритмом Дж. Хопкрофта, в котором классы эквивалентных состояний строятся, исходя из отношения различимости состояний по допустимым входным цепочкам. 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.

В работе представлена краткая история становления вероятностных графических моделей, рассмотрены посылы к их возникновению. Особое внимание уделено байесовским сетям доверия и родственным им алгебраическим байесовсим сетям, являющимся представлением баз знаний с неопределенностью. Приведены ключевые достижения в развитии логико-вероятностного аппарата алгебраических байесовских сетей и аппарата байесовских сетей доверия, дополненные примерами использования байесовских сетей доверия в программных продуктах. Обзор развития аппарата логико-вероятностного вывода продолжен формулировкой и доказательством решения первой задачи апостериорного вывода на матрично-векторном языке. Кроме того, перечислены задачи, стоящие в настоящий момент перед исследователями в области алгебраических байесовских сетей. Данная работа может быть полезна преподавателям дисциплин из области искусственного интеллекта, студентам, специализирующимся в области информатики и информационных технологий, рассматривающим перспективные темы для курсовых, выпускных квалификационных, научно-исследовательских работ и сотрудникам ИТ-команий, исследующим возможности применения математических моделей в бизнес процессах. С. 5-19.

The paper presents a brief history of the probabilistic graphic models formation and examines the reasons for their appearance. Special attention is given to Bayesian trust networks and related algebraic Bayesian networks, which are a representation of knowledge bases with uncertainty. Key achievements in the development of probabilistic-logic appartus in algebraic Bayesian networks and Bayesian trust networks are presented along with examples of the Bayesian trust networks using cases in software products. The review of the probabilistic-logic inference apparatus development is continued with the matrix-vector formulation and proof of the solution of the first task posterior inference. In addition, the problems in algebraic Bayesian networks currently being faced by researchers are listed. This paper might be useful to lecturers of disciplines on modern research in the field of artificial intelligence, to students specializing in information technologies, who are considering promising topics for their term papers, final or research papers and to the staff of it companies, exploring the possibilities of applying mathematical models in business processes.

Алгоритм Дейкстры является одним из наиболее популярных и фундаментальных алгоритмов решения проблемы поиска кратчайшего пути в ориентированном графе. Хорошо известно, что алгоритм Дейкстры применим к орграфам с неотрицательно взвешенными дугами. Но, как показывают простые наблюдения, существует множество орграфов и даже классов орграфов с отрицательно взвешенными дугами, к которым алгоритм Дейкстры также применим. Таким образом, условие неотрицательности весов дуг является достаточным, но не является необходимым. Необходимое условие применимости алгоритма Дейкстры не было известно. В этой статье мы представляем и доказываем необходимое и достаточное условие применимости алгоритма Дейкстры. Условие основано на введённом нами понятии рекорда пути. С. 5-13.

Dijkstra’s algorithm is one of the most popular and fundamental algorithms solving the shortest path problem in directed graphs (digraphs). It is well known that Dijkstra’s algorithm is applicable to digraphs with non-negative weighted arcs. But as simple observations show there are many digraphs and even classes of digraphs with negatively weighted arcs for which the Dijkstra’s algorithm is also applicable. Thus the non-negative weight of the arcs condition is not a necessary condition but only a sufficient one. pagebreak The necessary condition for applicability of Dijkstra’s algorithm was unknown. In this paper, we present and prove a necessary and sufficient condition for the applicability of Dijkstra’s algorithm. The condition is based on the notion of a path's record that we introduce.

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

The article describes the development of the speech synthesis methods from the beginnings to the present. The main approaches that have played an important role in the development of the speech synthesis, as well as modern advanced methods are considered. The extensive bibliography on this issue is also given.

Нечеткая логика по своей основной характеристике моделирования человеческого мышления является одним из методов искусственного интеллекта. Данный метод может быть использован для моделирования мониторинга и управления процессами. Нечеткая логика способствовала развитию нескольких направлений. В промышленном обслуживании нечеткая логика использована для того, чтобы разрешить диагностические проблемы, автоматически классифицировать сигналы вибрации, соответствие различных режимов деятельности машин. В данной статье проведен сравнительный анализ методов автоматизированной системы управления технологическими процессами (АСУ ТП) в современных промышленных областях, преимущественный анализ применения методов нечеткой логики в современных системах управления технологическими процессами, а также представлен пример использования нечёткой модели при оценке качества передачи данных в IIoT (Industrial Internet of Things) сетях. С. 29-42.

Fuzzy logic by its main characteristic of simulation of human reasoning, it is classified among the techniques of artificial intelligence. This technique can be used to model the monitoring and control of processes. Fuzzy logic has contributed to the development of several areas. In industrial maintenance, fuzzy logic is used to solve diagnostic problems by automatically classifying vibration signals corresponding to different modes of operation of machines. In this article, a comparative analysis is carried out of the methods of automated control system of technological processes (ACS TP) in modern industrial fields, the preferential analysis of applying fuzzy logic methods in modern process control systems, as well as an example of using a fuzzy model in assessing the quality of data transmission in IIoT net-works.

Статья направлена на демонстрацию практического приложения теории графов как подраздела теоретических основ информатики в решении одной из междисциплинарных задач — описании структуры молекулы сульфида кадмия с применением методов и индексов хемиоинформатики. В статье представлены результаты вычислений atom-bond connectivity индекса (ABC), геометрического и арифметического индекса GA, обобщенного индекса Рандича, GA5 и ABC4, загребских индесов для химического графа сульфида кадмия (CdS). Топологические индексы для сульфида кадмия рассматриваются впервые, хотя сама по себе задача расчета данных индексов не нова. Актуальность результатов подчеркивается тем, что сульфид кадмия широко используют в различных областях, таких как оптоэлектроника, фотоприемники, фоторезисторы и т. д. С. 44-54.

The article is aimed at demonstrating the practical application of graph theory as a subsection of the theoretical foundations of computer science in solving one of the interdisciplinary problems - describing the structure of the cadmium sulfide molecule using methods and indices of chemoinformatics. The article presents the results of calculations of the atom-bond connectivity index (ABC), of the geometric and arithmetic index GA, of the generalized Randic index, GA5 and ABC4, of the Zagreb indices for the chemical graph of cadmium sulfide (CdS). Topological indices for cadmium sulfide are considered for the first time, although the task of calculating these indices is not new in itself. The relevance of the results is emphasized by the fact that cadmium sulfide is widely used in various fields, such as optoelectronics, photodetectors, photoresistors, etc.

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

The article is aimed at summarizing the concepts of a derivative graph and a primitive graph for graphs with backbone connectivity. Theorems are formulated and proved on the main connectedness of the graph of the derivative and on the primitive graph of the main connected graphs. The theoretical and practical significance of the result is to simplify the search for successful visualization of algebraic Bayesian networks, which would help to identify the features of their structure, as well as the definition of new types of global structures of these networks. Such structures would allow us to store the same information, but use other output algorithms, which would simplify the software implementation of this model. Note that maintaining the property of trunk connectivity when finding the graph of the derivative is considered in this article for the first time.

Статья посвящена описанию особенностей функционального программирования, рассматриваемого как методология решения новых и исследовательских задач прикладного и системного программирования. Привлечена методика анализа и сравнения парадигм программирования, учитывающая приоритеты принятия решений в~процессе разработки программ. Методика сравнения языков и парадигм программирования основана на неформальном определении термина «парадигма программирования», согласно которому при сравнении парадигм следует выделять отличительные тестируемые особенности, допускающие проверку. В качестве таких признаков оказалось полезным использовать приоритеты при принятии решений на разных этапах изучения постановки задачи, а затем разработки и отладки программы её решения. Учёт приоритетов позволяет прогнозировать сложность процессов применения программируемых решений, начиная с планирования, изучения и организации разработки долгоживущих программ. Материал статьи имеет несколько дискуссионный характер. В статье дана четкая формулировка принципов парадигмы функционального программирования, отличающих её от других парадигм. На этих принципах выполнен вывод следствий, позволяющих успешно применять функциональное программирование при решении сложных задач, они конкретизированы на задачи организации параллельных вычислений и повышения производительности программ, созданных в рамках парадигмы функционального программирования. Показана сложность создания программ для решения новых задач на примере параллельных вычислений и описаны требования к универсальному мультипарадигмальному языку параллельных вычислений. Для задач функционального программирования правильность и полнота решений важнее эффективности и производительности полученных программ. Именно этот выбор приоритетов позволяет функциональное программирование рассматривать как общую методику подготовки прототипов или функциональных моделей. Можно сказать, что функциональное программирование выполняет роль проектно-конструкторского бюро для производственного программирования. С. 57-75.

The article is devoted to the description of the features of functional programming, considered as a methodology for solving new and research problems of applied and system programming. The technique of analysis and comparison of programming paradigms is involved, taking into account the priorities of decision-making in the process of developing programs. The methodology for comparing languages and programming paradigms is based on an informal definition of the term “programming paradigm”, according to which, when comparing paradigms, it is necessary to highlight the distinctive testable features that allow verification. As such signs, it turned out to be useful to use priorities in decision-making at different stages of studying the problem statement, and then developing and debugging a program for solving it. Accounting of priority allows you to predict the complexity of the application of programmable solutions, starting with planning, studying and organizing the development of long-lived programs. The material of the article is somewhat debatable. The article gives a clear formulation of the principles of the functional programming paradigm, which distinguish it from other paradigms. Based on these principles, the derivation of consequences that allow the successful application of functional programming in solving complex problems is carried out, they are concretized to the tasks of organizing parallel computing and improving the performance of programs created within the framework of the functional programming paradigm. The complexity of creating programs for solving new problems is shown on the example of parallel computing and the requirements for a universal multi-paradigm language for parallel computing are described. For functional programming problems, the correctness and completeness of solutions is more important than the efficiency and productivity of the resulting programs. It is this choice of priorities that allows pagebreak functional programming to be considered as a general technique for preparing prototypes or functional models. We can say that functional programming acts as a design office for production programming.

В компьютерной литературе описано много проблем, которые можно назвать задачами дискретной оптимизации: от шифрования информации в Интернете (включая создание программ для цифровых криптовалют) до поиска групп по интересам в социальных сетях. Часто эти задачи очень сложно решить на компьютере, поэтому их называют «труднорешаемыми».Точнее, сложно описывать возможные подходы к решению этих проблем; при этом программы, основанные на полном переборе вариантов, как правило, программируются просто, но работают значительно медленнее. Почти каждую из этих трудноразрешимых задач можно назвать математической моделью. В то же время как сама модель, так и алгоритмы, предназначенные для ее решения, часто создаваемые для одной предметной области, могут быть также использованы во многих других областях. Примером такой модели является задача коммивояжера. Особенность проблемы в том, что несмотря на относительную простоту её формулировки, поиск оптимального решения (оптимального маршрута) достаточно сложен. Эта задача очень трудна и относится к так называемому классу NP-полных задач. Кроме того, согласно существующей классификации, задача коммивояжера является примером оптимизационной задачи из самого сложного подкласса этого класса. В настоящей работе мы описываем несколько вариантов алгоритмов формирования исходных данных для задачи коммивояжера. После этого мы рассматриваем как классические эвристики, связанные с методом ветвей и границ, так и некоторые дополнения к ним. Далее мы представляем программную реализацию нашей интерпретации алгоритма. В конце статьи мы предлагаем несколько задач для дальнейшего исследования, поэтому статью можно считать описанием проекта для научной работы студентов. (На англ.) С. 41–58.

In the computer literature, a lot of problems are described that can be called discrete optimization problems: from encrypting information on the Internet (including creating programs for digital cryptocurrencies) before searching for “interests” groups in social networks. Often, these problems are very difficult to solve on a computer, hence they are called “intractable”. More precisely, the possible approaches to quickly solving these problems are difficult to solve (to describe algorithms, to program); the brute force solution, as a rule, is programmed simply, but the corresponding program works much slower. Almost every one of these intractable problems can be called a mathematical model. At the same time, both the model itself and the algorithms designed to solve it are often created for one subject area, but they can also be used in many other areas. An example of such a model is the traveling salesman problem. The peculiarity of the problem is that, given the relative simplicity of its formulation, finding the optimal solution (the optimal route). This problem is very difficult and belongs to the so-called class of NP-complete problems. Moreover, according to the existing classification, the traveling salesman problem is an example of an optimization problem that is an example of the most complex subclass of this class. In this paper, we describe several variants of algorithms for generating source data for the traveling salesman problem. We consider both the classical heuristics associated with the branch and bound method, and some added to them. Next, we present a software implementation of our interpretation of the algorithm. At the end of the paper, we formulate some tasks for further research, so the paper can be a project for students' scientific work.

Данная статья продолжает серию о языках разметки и полностью посвящена верстке таблиц в языках 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.

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

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.

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

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.

Рассматривается моделирование генераторов Алгола 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.

Цель данной статьи – методологическая. Описывается опыт применения модифицированных синтаксических диаграмм Н. Вирта в 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.

Описаны реализации классического алгоритма моделирования процессов агрегации, ограниченной диффузией, как на плоскости, так и на триангуляционной сетке. Разработаны и реализованы оптимизации этих алгоритмов, основанные на априорной оценке вероятности присоединения частицы к граничным точкам агрегата. Дана оценка сложности описываемых алгоритмов. Приведены результаты численных экспериментов. С. 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.

В работе рассматриваются две задачи анализа данных геномного и метагеномного секвенирования — задача 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.

Группа лиц должна узнать секретный код, анализируя доступную всем таблицу. Каждый участник знает свою строчку в таблице и одно слово из кода. Участник может сообщить всем другим только одно из – знает он код или не знает. В статье описан алгоритм, позволяющий строить таблицы, по которой за несколько ходов обмена сообщениями все участники узнают код. С. 5-11.

A group of people must find out a secret code by analyzing a table available to all. Each participant knows his line in the table and one word from the code. A participant is allowed to announce to all others only one of two messages – s/he knows the code or does not know it. The article describes an algorithm allowing the construction of the table, with the help of which, after a few exchanges of messages, all participants will recognize the code.

Предикат делимости на два последовательных числа DW(x,y) ÷ x | y ∧ 1+x | y был предложен Л. ван ден Дрисом и А. Уилки в работе, посвященной изучению свойств подмножеств натуральных чисел, экзистенциально выразимых с помощью единицы, сложения и делимости. В настоящей работе доказывается неразрешимость множества истинных в натуральных числах экзистенциальных формул, записанных с помощью только DW и умножения, а также выразимость всех арифметических предикатов с помощью только сложения и DW или только DW и делимости. Кроме того, получены некоторые результаты о выразимости для DW и отношения порядка. С. 5-15.

The predicate of divisibility on two consecutive numbers DW(x,y) ÷ x | y ∧ 1+x | y was introduced by L. van den Dries and A. Wilkie when they studied some properties of subsets of natural numbers, existentially definable with unit, addition and divisibility. Undecidability of the existential theory of natural numbers with multiplication and DW and definability of addition and multiplication in terms of DW and divisibility is proved in the paper. Then the definability of multiplication in the terms of addition and DW is proved. Some definability questions for order and DW are also considered in the paper.

Рассматривается одна из базовых задач вычислительной геометрии (Computational Geometry) - построение выпуклой оболочки конечного множества точек на плоскости. Представлены три алгоритма решения задачи: метод Джарвиса («заворачивания подарка»), обход Грэхема и последовательный (рекуррентный) алгоритм. В следующей статье будут рассмотрены другие алгоритмы построения выпуклой оболочки и связь данной задачи с задачей сортировки.

Данная статья продолжает серию о языках разметки. В ней обсуждаются основные средства форматирования текстов в языках 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.

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

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.

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

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.

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

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.

В статье описывается опыт автора по преподаванию и развитию технологий 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.

При разработке многократно используемых программ важно, чтобы их выполнение было достаточно быстрым. В книге Ду Д.З. и Ко К.И. сформулирован обобщенный тезис Чёрча: «Функция, вычислимая за полиномиальное время на разумной вычислительной модели, использующей разумное измерение временной сложности, вычислима на детерминированной машине Тьюринга за полиномиальное время» (то есть принадлежит классу 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.

Статья содержит два основных раздела. Первый из них (п. 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.

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

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.

Описывается метод регуляризации приведённых КС-грамматик без самовставлений, основанный на топологической сортировке нетерминалов грамматики по отношению зависимости, определяемой правилами грамматики.

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.

Рассматривается аппроксимация Зламала для представления функции заданной на двумерной области. Из аппроксимационных соотношений выведены выражения базисных элементов аппроксимации. Для триангуляции специального вида получены калибровочные соотношения, обеспечивающие удобный способ перехода между базисами аппроксимации при локальном укрупнении триангуляции. С. 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.

В работе всесторонне изучается методология полногеномного поиска связей фенотипа с одним или несколькими генетическими маркерами. В данной части работы рассмотрены различные типы данных, наиболее часто встречающиеся при проведении генетических исследований, и методы их анализа. 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.

Очень часто непосредственное использование стандартных моделей приводит к результатам низкого качества. В статье рассмотрены два примера. Первый пример касается классификации популярных данных «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.

Идея технологической сингулярности проистекает из экстраполяций эмпирических кривых ускорения технического развития. Нередко, однако, из этих ненадежных экстраполяций делаются далеко идущие следствия, которые подвергаются активной критике, и эта критика некорректно переносится на саму концепцию технологической сингулярности. В статье делается попытка отделить данную концепцию от дополнительных предположений и убеждений, в частности, касательно возможности создания искусственного интеллекта, а также выделить ряд заблуждений. Для этих целей привлекается теория метасистемных переходов, и технологическая сингулярность определяется как точка, в которой ранее наблюдаемые закономерности уменьшения времени между метасистемными переходами и уменьшения времени удвоения производительности кибернетических систем внутри одного уровня перестают выполняться. Указывается, что до достижения этой точки, вероятно, успеет произойти ряд метасистемных переходов, и возникшие системы будут показывать экспоненциальный рост с периодом удвоения менее полугода и превысят сложность существующих систем в течение нескольких десятилетий. С. 12-24.

The idea of a technological singularity stems from extrapolations of the empirical curves of the acceleration of technological development. Quite often, however, from these unreliable extrapolations far-reaching consequences are made, which are subject to active criticism, and this criticism is incorrectly transferred to the very concept of technological singularity. The article attempts to separate this concept from additional assumptions and beliefs, in particular, regarding the possibility of creating artificial intelligence, as well as to highlight a number of misconceptions. pagebreak For these purposes, the theory of metasystemic transitions is involved, and the technological singularity is defined as the point at which previously observed patterns of decreasing time between metasystem transitions and reducing the time of doubling the performance of cybernetic systems within one level cease to be fulfilled. It is pointed out that before reaching this point, a number of metasystemic transitions are likely to occur, and the resulting systems will show exponential growth with a doubling period of less than six months and will exceed the complexity of existing systems for several decades.

В работе решается задача разработки инструментария, позволяющего проводить компьютерные вычисления для получения новых результатов в теории мультиопераций. В статье приведены различные методы представления операций и мультиопераций и описаны алгоритмы для вычисления суперпозиции операций и мультиопераций. Также в работе приводятся исследования различных структур языка Python 3 и поиск наиболее подходящих для реализации представлений операций и мультиопераций. Основываясь на полученных результатах исследований структур данных, была разработана и реализована архитектура пакета Python 3 для моделирования алгебр операций и мультиопераций в теории мультиопераций. С. 16-29.

This work solves the problem of developing a toolkit that allows computer calculations to obtain new results in the theory of multioperations. The article presents various methods for representing operations and multioperations, and describes algorithms for calculating the superposition of operations and multioperations. Also, the work provides a study of various structures of the Python 3 and the search for the most suitable for the implementation of the representation of operations and multioperations. Based on the results of research on data structures, the architecture of the Python 3 package was developed and implemented for modeling algebras of operations and multioperations in the theory of multioperations.

В настоящее время компании развертывают приложения для обработки данных и анализа не на мейнфреймах с производительными аппаратными компонентами, а на обычных кластерах из персональных компьютеров. Персональные компьютеры менее надежны, нежели дорогие мейнфреймы. Приложениям, развернутым в кластерах, приходится иметь дело с частыми сбоями. В основном эти приложения выполняют сложные клиентские запросы с операциями агрегирования и объединения. Чем дольше выполняется запрос, тем больше он подвержен сбоям системы. Это приводит к тому, что вся работа должна быть выполнена заново. В этой статье представлен алгоритм отказоустойчивого hash join (FTHJ) для распределенных систем, реализованный в Apache Ignite. FTHJ обеспечивает отказоустойчивость за счет использования механизма репликации данных, реализующего промежуточные вычисления. Для оценки FTHJ мы внедрили подверженный к отказам алгоритм hash join. Экспериментальные результаты показывают, что FTHJ требуется как минимум на 30 % меньше времени для восстановления и завершения операции соединения в случае, если сбой произошел во время работы алгоритма. В этой работе описывается, как мы достигли компромисса между выполнением задач восстановления за наименьшее количество времени и использованием дополнительных ресурсов. (На англ.) С. 68–82.

Nowadays, enterprises are inclined to deploy data processing and analytical applications from well-equipped mainframes with highly available hardware components to commodity computers. Commodity machines are less reliable than expensive mainframes. Applications deployed on commodity clusters have to deal with failures that occur frequently. Mostly, these applications perform complex client queries with aggregation and join operations. The longer a query executes, the more it suffers from failures. It causes the entire work has to be re-executed.
This paper presents a fault tolerant hash join (FTHJ) algorithm for distributed systems implemented in Apache Ignite. The FTHJ achieves fault tolerance by using a data replication mechanism, materializing intermediate computations. To evaluate FTHJ, we implemented the baseline, unreliable hash join algorithm. Experimental results show that FTHJ takes at least 30% less time to recover and complete join operation when a failure occurs during the execution. This paper describes how we reached a compromise between executing recovery tasks for the least amount of time and using additional resources.

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

Статья рассказывает о курсах и лекциях по 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

В статье рассматриваются вопросы правильности перевода англоязычной терминологии по ИТ на русский язык. Предлагается идея создания КПП - 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.

Реверсивный поиск – один из алгоритмов, идея которого «витает в воздухе» десятилетиями и который часто изобретается заново программистами, знакомыми с такими алгоритмами, как поиск в ширину (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.

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

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.

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

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.

Задача Штейнера на ориентированных графах – наиболее общая в семействе задач Штейнера. Известно, что она является 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.

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

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

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.

В данной статье рассмотрен метод, позволяющий проводить локальное укрупнение правильной триангуляции, заданной на двумерной плоскости, сохраняющий правильность результирующей триангуляции. Представлен алгоритм, позволяющий построить триангуляцию с локальным укрупнением по заданой исходной триангуляции. Реализована программа, позволяющая курантовскую аппроксимацию поверхности на исходной триангуляции заменить курантовской аппроксимацией поверхности на локально укрупненной с учетом особенностей поверхности триангуляции. Проведена апробация предложенного алгоритма на модельных примерах. С. 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.

Возросшая популярность искусственных нейросетей (ИНС) в образовании, науке и бизнесе может создать впечатление свершившейся революции в компьютерном моделировании и алгоритмах оптимизации. Данный короткий обзор призван обратить внимание на фундаментальные ограничения ИНС и потенциальный вред, который может нанести поощрение изучения ИНС в ущерб строгим математическим методам. С. 25-30.

The increasing popularity of artificial neural networks (ANNs) in education, science, and commerce may give the impression of a revolution that has taken place in computer modeling and optimization algorithms. This short review highlights the fundamental shortcomings of ANNs and the potential harm that can be caused by encouraging the study of ANNs to the detriment of strict mathematical methods.

В статье рассматривается эволюция идеи учета последующего контекста, возникшая в середине 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.

Статья посвящена имитационному моделированию квантового алгоритма Дойча в среде MATLAB/Simulink.

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

Предложены новые варианты измельчения симплициального топологически правильного подразделения вблизи границы области с сохранением свойства невырожденности.

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

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

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.

Тонкие оболочки, подкрепленные ребрами переменной высоты, позволяют снизить опасную концентрацию напряжений. Для анализа напряженно-деформированного состояния подкрепленной конструкции необходимо знать не только наибольший прогиб и наибольшее нормальное напряжение, но и картину прогибов и интенсивности напряжений по всей оболочке. Более того, построение поля прогибов оболочки от поверхности конструкции (а не от плоскости) может более наглядно отразить процесс деформирования. Это все можно учесть, разрабатывая специальное программное обеспечение для дальнейшего практического применения, обладающее удобным графическим интерфейсом и предоставляющее результаты расчетов в удобном пользователю виде. Целью данной работы является описание визуализации математической модели напряженно-деформированного состояния тонкостенных оболочечных конструкций, подкрепленных ребрами переменной высоты и имеющих в качестве составных частей элементы следующих оболочек: пологой, цилиндрической, конической, сферической, тороидальной, катеноидной. Описываемые в данной работе результаты получены при помощи разработанного программного модуля, который может быть использован в практике расчета оболочечных конструкций при их проектировании, а также в научных исследованиях, связанных с нелинейными проблемами деформирования тонкостенных конструкций. В разработанном программном модуле геометрическая форма оболочки задается при помощи параметров Ламе, а сама оболочка и подкрепляющие ее ребра рассматриваются как оболочка ступенчато-переменной толщины. Это существенно упрощает подготовку задачи к решению. Контакт ребра и обшивки происходит по полосе, что более точно отражает реальную работу конструкции. С. 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.

Задача представления знаний для сложных структурированных объектов является одной из актуальных задач ИИ. Это связано с тем, что многие исследуемые объекты представляют собой не единый неделимый объект, характеризующийся своими свойствами, а сложные конструкции, элементы которых обладают известными свойствами и находятся в некоторых, зачастую многоместных, отношениях между собой. В работе подход к представлению таких знаний на основе логики первого порядка (формул исчисления предикатов) сравнивается с двумя широко распространёнными в настоящее время подходами, основанными на представлении информации о~данных с помощью конечнозначных строк и на использовании графов. Показано, что использование формул исчисления предикатов для описания сложных структурированных объектов, несмотря на NP-трудность решаемых задач, возникающих после формализации, реально имеют не б'{о}льшую вычислительную сложность, чем два других подхода, о чём обычно не упоминают их сторонники. Предложен алгоритм построения онтологии, не зависящий от способа описания объекта и основанный на выделении наибольшего общего свойства объектов из заданного множества. С. 41-57.

The problem of knowledge representation for a complex structured object is one of the actual problems of AI. This is due to the fact that many of the objects under study are not a single indivisible object characterized by its properties, but complex structures whose elements have some known properties and are in some, often multiplace, relations with each other. An approach to the representation of such knowledge based on first-order logic (predicate calculus formulas) is compared in this paper with two currently widespread approaches based on the representation of data information with the use of finite-valued strings or graphs. It is shown that the use of predicate calculus formulas for description of a complex structured object, despite the NP-difficulty of the solved problems arising after formalization, actually have no greater computational complexity than the other two approaches, what is usually not mentioned by their supporters. An algorithm for constructing an ontology is proposed that does not depend on the method of describing an object, and is based on the selection of the maximum common property of objects from a given set.

Статья продолжает цикл, начатый в №№ 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.

В статье рассматриваются суживающие (сокращающие перебор) стратегии для резолюционных алгоритмов логического вывода в базах знаний, построенных на основе логической модели знаний. Особенностью этих стратегий является предварительная настройка на работу с конкретными базами знаний. Для настройки используется метод абстракций и формально-грамматическая интерпретация логического вывода. Абстракция – это функция, которая отображает класс задач 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.

Заметка содержит описание алгоритма, нумерации элементов выборки 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.

Ранее первый автор ввел определение независимого компьютерного представления объекта (пользователь может изучить объект без знаний об аналогичных объектах). В статье представлены примеры описаний интерактивных математических моделей: для понятий на естественных языках (без каких-либо других языков в качестве носителей; глаголы представлены как действия пользователя); для самой математики (с минимальными пояснениями) и для физики. С. 58-65. (на англ.)

Earlier, the first author introduced a definition of independent computer presentation of an object (the user can master the object without reference to similar objects). The paper presents examples of descriptions of interactive mathematical models: for notions in natural languages (without any other languages as media; verbs are presented as the user's actions); for mathematics itself (with minimal explanations) and for physics.

В работе рассматривается Music Information Retrieval — область вычислительного музыковедения, которая активно развивается в современном мире. В рамках статьи описаны некоторые основные задачи и технологии данного направления, такие как генерация музыки, автоматическая музыкальная транскрипция, синтез звуков музыкальных инструментов, поиск музыки.
Особое внимание уделяется одной из интереснейших задач на стыке речевых и музыкальных технологий — синтезу поющего голоса. Рассматриваются различные подходы к этой задаче, существующие проблемы и методы их решения. С. 74-95.

This paper discusses Music Information Retrieval — a field of computational musicology that is actively developing in the modern world. The paper describes some of the main tasks and technologies of this area, such as music generation, automatic music transcription, synthesis of musical instrument sounds, and music retrieval. Special attention is paid to one of the most interesting tasks at the junction of speech and music technologies —singing voice synthesis. Different approaches to this task, existing problems and methods of their solution are discussed.