Журналы
Email: Пароль: Войти Регистрация
E-mail: kosov@NK1022.spb.edu

Доктор физико-математических наук, старший научный сотрудник СПИИРАН.

Статьи автора:

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

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

Ключевые слова: P, FP, NP, машина тьюринга, паслкалевидные функции, NP-полнота, NP-трудность, примеры NP-полных задач.
Keywords: P, FP, NP, Turing machine, pascal-like functions, NP-full, NP-complete, NP-complete functions examples.
В [3] даны определения числа шагов и длины записи промежуточных вычислений паскалевидных функций. С их помощью было получено представление класса всех функций, вычислимых на машинах Тьюринга за число шагов, ограниченное сверху полиномом от длины записи исходных данных (класса FP), с помощью дважды полиномиальных (то есть полиномиальных по числу шагов и по длине записи промежуточных вычислений) паскалевидных функций. Для удобства доказательства принадлежности паскалевидной функции классу FP здесь введено понятие паскалевидных функций над списком S паскалевидный функций. Для этих функций даны определения числа шагов и длины записи промежуточных вычислений, наконец, определены дважды полиномиальные паскалевидные функции над списком S. (для каждой функции из S число шагов и длина записи промежуточных вычислений равны единице). Функции из S соответствуют базовым подпрограммам. Доказывается теорема о совпадении класса дважды полиномиальных паскалевидных функций над S и класса FP.

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

Ключевые слова: верхние оценки числа шагов, машины Тьюринга, класс FP, функции языка Паскаль.
Keywords: Upper bounds for time complexity, Turing machine, FP complexity class, functions of pascal programming language.
Рассматриваются три задачи составления описания объекта по достоверной информации, полученной несколькими агентами, причём информация, которой располагает каждый агент, не полна. В первой задаче объект характеризуется своими глобальными бинарными признаками и описывается набором значений этих признаков. Во второй и третьей задачах объект представлен как множество своих элементов, характеризуется свойствами этих элементов и отношениями между ними и описывается множеством постоянных атомарных формул исчисления предикатов. Во второй задаче предполагается, что все агенты располагают одинаковыми именами частей объекта. В третьей задаче каждый агент не знает подлинных имён частей объекта и даёт им имена произвольно. Приводятся алгоритмы решения рассмотренных задач и доказываются верхние оценки числа шагов их работы. Для второй и третьей задач приведены модельные примеры работы алгоритмов. С. 5-18.

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

Ключевые слова: мультиагентное описание объекта, формула исчисления предикатов, неполная выводимость формулы, вычислительная сложность алгоритма.
Keywords: multi-agent description of an object, predicate formula, partial deduction, computational complexity of an algorithm.
Статья написана на основе части курса «анализ алгоритмов» для студентов кафедры информатики математико-механического факультета Санкт-Петербургского государственного университета. На примере компьютерной реализации метода Гаусса проиллюстрирована разница между алгебраической сложностью (числом арифметических операций) обработки целых чисел и вычислительной сложностью, зависящей от длины записи входных данных. Доказана формула, задающая увеличение длины матричных коэффициентов при реализации метода Гаусса. Показаны проблемы, возникающие при обработке больших целых чисел, связанные с «нарезкой» цифр. Для преодоления указанных проблем предлагается возможность использования многозначных целых чисел. Показано, что верхние границы числа шагов при обработке многозначных целых чисел совпадают с такими границами для многоленточной машины Тьюринга (на англ.). С. 90-95.

The paper is written on the basis of a part of “Analysis of algorithms'' course for students of the Computer science department of the Division of mathematics and mechanics of Saint Petersburg State University. The example of the computer implementation of the Gauss method illustrates the difference between the algebraic complexity (the number of arithmetic operations) of processing integers and the computational complexity which depends on the length of the input data. A formula which specifies the increase in the length of matrix coefficients, along with the implementation the Gauss method, is proved. The problems arising in the processing of large integers associated with ``chopping'' numbers are shown. To overcome the indicated problems, the possibility of using multi-valued integers is proposed. The upper bounds of the number of steps for processing the multi-valued integers is shown to coincide with such bounds for a multi-tape Turing machine.

Ключевые слова: метод Гаусса, вычислительная сложность, вычисления с большими целыми числами.
Keywords: Gauss method, computational complexity, computation with large integers.
При разработке многократно используемых программ важно, чтобы их выполнение было достаточно быстрым. В книге Ду Д.З. и Ко К.И. сформулирован обобщенный тезис Чёрча: «Функция, вычислимая за полиномиальное время на разумной вычислительной модели, использующей разумное измерение временной сложности, вычислима на детерминированной машине Тьюринга за полиномиальное время» (то есть принадлежит классу FP). Этот расширенный тезис Чёрча более естественно называть полиномиальным тезисом Чёрча для машин Тьюринга. «Разумность» вычислительной модели разными исследователями понимается по-разному, вследствие чего в последнее время всё чаще появляются «доказательства» (содержащие ошибки) знаменитой проблемы: верно ли, что P = NP? При этом шаг различных моделей алгоритмов трактуется интуитивно. В настоящей работе доказано, что «разумность» шага вычисления рекурсивной функции может заключаться в использовании таких рефал-5-предложений из класса FP, длина записи результата выполнения которых (включая длину записи всего изменяемого стека) увеличивается не более чем на константу, единую для всех исходных данных. В этом смысле обычное определение общерекурсивной функции не является «разумной» вычислительной моделью. Достаточно сложным является подсчет числа шагов рекурсивного алгоритма. В настоящей статье доказаны необходимые и достаточные условия полиномиальности по времени функции, реализованной на языке программирования рефал-5. Этот язык является практически реализованным обобщением таких математических моделей алгоритма как нормальные алгоритмы, а также вводимые здесь алгоритмы Маркова-Поста и рекурсивные алгоритмы Маркова-Поста. Поэтому в качестве следствий основной теоремы доказаны условия полиномиальности по времени и этих математических моделей, применимых в теоретических исследованиях. Весьма актуальным является вопрос о возможности доказательства того, что программа, написанная на языке рефал-5, задает полиномиально быструю функцию, то есть функцию, принадлежащую классу FP. В статье вводится понятие дважды полиномиальных рекурсивных вызовов рефал-5-функции, обеспечивающее решение этого вопроса.

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

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

The paper is devoted to the modifying of Maslov inverse method for a special form of predicate formulas used in the solution of an artificial intelligence problem permitting its setting in the frameworks of predicate calculus. An algorithm based on the inverse method application for such a type formula is justified. Upper and lower bounds of the number of steps of the proposed algorithm are obtained. An example of the extraction and recognition of a given object included into a complex one by means of the presented algorithm is regarded.

Ключевые слова: искусственный интеллект, логико-предметное распознавание образов, исчисление предикатов, обратный метод Маслова.
Keywords: artificial intelligence, logic-objective approach to pattern recognition, predicate calculus, inverse method of S.Yu.Maslov, complexity theory.
Статья написана на основе части курса «анализ алгоритмов» для студентов кафедры информатики математико-механического факультета Санкт-Петербургского государственного университета. На примере компьютерной реализации метода Гаусса проиллюстрирована разница между алгебраической сложностью (числом арифметических операций) обработки целых чисел и вычислительной сложностью, зависящей от длины записи входных данных.
Доказана формула, задающая увеличение длины матричных коэффициентов при реализации метода Гаусса.
Показаны проблемы, возникающие при обработке больших целых чисел, связанные с «нарезкой» цифр.
Для преодоления указанных проблем предлагается возможность использования многозначных целых чисел. Показано, что верхние границы числа шагов при обработке многозначных целых чисел совпадают с такими границами для многоленточной машины Тьюринга (на англ.). С. 90-95.

The paper is written on the basis of a part of ``Analysis of algorithms'' course for students of the Computer science department of the Division of mathematics and mechanics of Saint Petersburg State University. The example of the computer implementation of the Gauss method illustrates the difference between the algebraic complexity (the number of arithmetic operations) of processing integers and the computational complexity which depends on the length of the input data.
A formula which specifies the increase in the length of matrix coefficients, along with the implementation the Gauss method, is proved.
The problems arising in the processing of large integers associated with ``chopping'' numbers are shown.
To overcome the indicated problems, the possibility of using multi-valued integers is proposed. The upper bounds of the number of steps for processing the multi-valued integers is shown to coincide with such bounds for a multi-tape Turing machine.

Ключевые слова: метод Гаусса, вычислительная сложность, вычисления с большими целыми числами.
Keywords: Gauss method, computational complexity, computation with large integers.
Статья посвящена сложности алгоритмов. Рассматриваются примеры алгоритмов, решающих одну и ту же задачу, но затрачивающих различное число шагов.
Для пополнения баланса выберите страну, оператора и отправьте СМС с кодом на указанный номер. Отправив одну смс, вы получаете доступ к одной статье.
Закрыть