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

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.

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

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

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

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

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

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

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

Данная статья открывает серию, посвященную языкам разметки текста, и основана на лекциях, которые автор прочитал в СПбГЭТУ "ЛЭТИ" осенью 2007 г. Эта статья содержит введение в язык TeX вместе с примерами написания простейших программ, а также рассказывает о макропоследовательностях в TeX.

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

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

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

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.

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

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

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

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

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