Журналы
Email: Пароль: Войти Регистрация
E-mail: braigor@yandex.ru

Доктор физико-математических наук, профессор кафедры математической теории микропроцессорных систем управления факультета прикладной математики – процессов управления СПбГУ.

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

В статье рассматриваются задачи для олимпиад школьников по информатике, решения которых могут быть получены как с помощью реализации соответствующих алгоритмов, так и аналитически, то есть чисто математическими средствами. Такие задачи названы задачами двойного назначения. Предлагаются 3 типа таких задач: 1) задачи, решаемые выполнением алгоритмов; 2) задачи, для решения которых требуется анализ алгоритмов с целью их упрощения перед выполнением; 3) задачи, решаемые математическими средствами, без выполнения алгоритмов. Методика разработки задач двойного назначения иллюстрируется на примере алгоритма схождения чисел. На его основе сформулированы 5 задач, относящихся к трем указанным типам. Статья содержит решения каждой из этих задач. Описанный подход к разработке задач для олимпиад школьников должен способствовать более полному тестированию участников, так как позволит оценить не только знание ими основ программирования, но и их математическую подготовку.

In this paper the problems for Olympiads of the pupils on Computer Science which decisions can be received by execution of the relevant algorithms and analytically, i.e. by purely mathematical means are considered. Such problems are called dual-use problems. There are 3 types of them: 1) problems solved by executing algorithms; 2) problems whose solution requires the analysis of algorithms to simplify them before the execution; 3) problems solved by mathematical means, without the execution of algorithms. The methodology of developing dual-use problems is illustrated on an example of algorithm of a convergence of numbers. On its basis are formulated 5 problems concerning three specified types. The paper contains decisions of each of these problems. The described approach to the development of problems for the Olympiads of the pupils should promote fuller testing of participants as it allows to evaluate not only their knowledge of the fundamentals of programming, but also their mathematical training.

Ключевые слова: олимпиада для школьников по информатике, задачи двойного назначения, алгоритм, анализ алгоритмов, алгоритм схождения чисел, аналитическое решение задачи.
Keywords: of the pupils on computer science, dual-use problems, algorithm, the analysis of algorithms, algorithm of a convergence of numbers, the analytical decision of a problem.
В статье рассматриваются суживающие (сокращающие перебор) стратегии для резолюционных алгоритмов логического вывода в базах знаний, построенных на основе логической модели знаний. Особенностью этих стратегий является предварительная настройка на работу с конкретными базами знаний. Для настройки используется метод абстракций и формально-грамматическая интерпретация логического вывода. Абстракция – это функция, которая отображает класс задач K1 в более простой класс K2. При решении задачи A принадлежит K1 ее отображают в задачу B принадлежит K2. Затем задача B решается, и ее решения используются для поиска решений исходной задачи A. В настоящей работе класс задач K1 – это проблема дедукции в исчислении предикатов первого порядка. Для K1 рассматриваются две абстракции – пропозициональная, при которой K2 – это проблема дедукции в исчислении высказываний, и абстракция, при которой проблема дедукции решается для конструкций, названных псевдо-предикатами. Для обеих абстракций предлагается формально-грамматическая интерпретация, позволяющая выполнить предварительную настройку, которая гарантирует перебор лишь успешных вариантов выводов. Приведенные примеры иллюстрируют достоинства предложенной методики.

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

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