Выпуск №2
Открыто 
Содержание журнала, редсовет, редколлегия, информация об обложке и о диске.
Table of contents, editorial board, editors, information on cover, information on CD.
Table of contents, editorial board, editors, information on cover, information on CD.
Статья посвящена проблемам доказательства полиномиальной вычислимости функций, другими словами, доказательства принадлежности функций классу 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 paper is devoted to the problem of proving that some function is in FP complexity class. Such proofs may use pascal-like functions, that are more easy for programmers, than computation models based on a Turing machine. It will be presented the idea of proof of the theorem, that if both the number of steps of pascal-like function evaluation and a size of all intermediate evaluations are not greater than some polynomial of the length of initial data, then this function is in FP and vice versa.
Ключевые слова: P, FP, NP, машина тьюринга, паслкалевидные функции, NP-полнота, NP-трудность, примеры NP-полных задач.
Keywords: P, FP, NP, Turing machine, pascal-like functions, NP-full, NP-complete, NP-complete functions examples.
На примере решения логической задачи излагается метод построения компьютерных инструментов, имеющих значение универсальных интеллектуальных орудий для решения широкого круга задач или выполнения определенных этапов решения. Алгоритм решения не зависит в данном случае от специфики содержания задачи, но обеспечивает «самопреобразование» исходных данных в системную форму, содержащую искомый результат в явном виде, посредством последовательной актуализации свойств каждого объекта в среде других объектов. Главная направленность работы – продемонстрировать на конкретном примере возможность и эффективность приведения во взаимосвязь концептуального и вычислительного, математического и программного аспектов при построении компьютерных инструментов.
The approach to the construction of computer tools is discussed. The decisions of task or problem are made on the basis of "self-transformation" of the initial data. Solution algorithm does not depend on specific content of the task, but only provides an opportunity for each object, to prescribe its properties in the environment of other objects.
The approach to the construction of computer tools is discussed. The decisions of task or problem are made on the basis of "self-transformation" of the initial data. Solution algorithm does not depend on specific content of the task, but only provides an opportunity for each object, to prescribe its properties in the environment of other objects.
Ключевые слова: компьютерные инструменты, самопреобразование данных, системообразующий принцип, логические задачи.
Keywords: data self-transformation, system-creating principle, computer tools.
В статье обсуждаются парадигмы программирования и то, как разные парадигмы применяются для решения программистских задач. В частности, обсуждается, как решить одну трудную олимпиадную задачу по программированию с использованием трёх парадигм программирования: логического, функционального и императивного. Разработку эффективного императивного алгоритма решения этой задачи можно рассматривать как пример обращения аналогичной логической программы. Функциональный алгоритм при таком подходе представляет собой промежуточный вариант решения задачи, более эффективный, чем логический алгоритм, а эффективный императивный алгоритм фактически является ленивой мемоизацией этого функционального алгоритма.
This paper is about programming paradigms, how different paradigms can fertilize each other. In particular the paper discusses a challenging contest programming problem and solves it in three programming paradigms: logic, functional and imperative. It can be considered as a case study of algorithm inversion, since we start with logic algorithm, that answers the question "Is balancing M times sufficient for detecting a single fake in a set of coins?", and finishes with imperative algorithm, that effectively computes the minimal number of balancing that is sufficient for detection the fake. Functional paradigm is used for developing an intermediate functional algorithm that also computes the minimal number of balancing, but inefficiently, while the efficient imperative algorithm is a Р’В«lazy memoizationР’В» of the functional one.
This paper is about programming paradigms, how different paradigms can fertilize each other. In particular the paper discusses a challenging contest programming problem and solves it in three programming paradigms: logic, functional and imperative. It can be considered as a case study of algorithm inversion, since we start with logic algorithm, that answers the question "Is balancing M times sufficient for detecting a single fake in a set of coins?", and finishes with imperative algorithm, that effectively computes the minimal number of balancing that is sufficient for detection the fake. Functional paradigm is used for developing an intermediate functional algorithm that also computes the minimal number of balancing, but inefficiently, while the efficient imperative algorithm is a Р’В«lazy memoizationР’В» of the functional one.
Ключевые слова: парадигмы программирования, императивное программирование, функциональное программирование, логическое программирование, мемоизация, динамическое программирование.
Keywords: programming paradigms, imperative programming, functional programming, logical programming, memoization, dynamic programming.
Открыто
В статье освещаются вопросы, связанные с теорией и практикой символьного интегрирования. Рассматриваются варианты постановки задачи для разных классов функций, приведены формулировки основных теорем. Дан исторический обзор наиболее значимых результатов в этой области. В последнем разделе приведён перечень «белых пятен», которые имеются как в теории, так и в машинных реализациях.
The article throws light upon the theory and practice of symbolic integration. The statement of the problem is considered for several categories of functions, and the main theorems are listed. The overview of the most significant achievements in this area is given. The last section lists the open questions, which are present in both theory and implementations.
The article throws light upon the theory and practice of symbolic integration. The statement of the problem is considered for several categories of functions, and the main theorems are listed. The overview of the most significant achievements in this area is given. The last section lists the open questions, which are present in both theory and implementations.
Ключевые слова: Неопределенный интеграл, символьное интегрирование, теорема Лиувилля, алгоритм Риша.
Keywords: Antiderivative, symbolic integration, Liouville theorem, Risch algorithm.
В последние годы возникли и стремительно развиваются такие научные направления как визуализация информации и визуальная аналитика. В отличие от европейских и американских университетов, в программу обучения которых методы визуализации информации вошли достаточно прочно [11], в России подобные курсы почти полностью отсутствуют. В течение последних пяти лет автором этой статьи читается курс, посвященный методам визуализации информации на основе графовых моделей, в Новосибирском государственном университете. Данная статья дает общее представление о созданном курсе.
Scientific directions such as information visualization and a visual analytics have arisen quite recently. The quantity of theoretical researches in these areas increases, thanks to the quickly extending spectrum of industrial applications. The theoretical background of the information visualization and visual analytics methods are graph visualization methods. Unlike the European and American universities, which programs include courses on information visualization methods, similar courses in Russia are almost completely absent. One of the basic difficulties in teaching such a course in Russia is almost the total absence of the Russian literature, devoted to this subject. During the last five years the author of this article gives a course devoted to methods of the information visualization based on the graph models, in the Novosibirsk State University. Theoretical foundations of the tree and graph drawing construction are considered in this course. A considerable quantity of examples of real applications is given. This article describes the main topics of the course.
Scientific directions such as information visualization and a visual analytics have arisen quite recently. The quantity of theoretical researches in these areas increases, thanks to the quickly extending spectrum of industrial applications. The theoretical background of the information visualization and visual analytics methods are graph visualization methods. Unlike the European and American universities, which programs include courses on information visualization methods, similar courses in Russia are almost completely absent. One of the basic difficulties in teaching such a course in Russia is almost the total absence of the Russian literature, devoted to this subject. During the last five years the author of this article gives a course devoted to methods of the information visualization based on the graph models, in the Novosibirsk State University. Theoretical foundations of the tree and graph drawing construction are considered in this course. A considerable quantity of examples of real applications is given. This article describes the main topics of the course.
Ключевые слова: методы визуализации информации, дерево, диаграммы связей вершин и методы заполнения пространства, граф, визуализация планарных графов, силовые алгоритмы размещения неориентированных графов, поуровневое размещение ориентированных графов.
Keywords: information visualization methods, tree, node link diagrams, space filling methods, graph, planar graph visualization, force-directed placement algorithms for undirected graphs, layered drawing of directed graphs.
Обсуждается соотношение между аналитическими и вычислительными методами исследования математических моделей нелинейной динамики.
The relationship between analytical and computational methods of investigation of mathematical models of nonlinear dynamics is discussed.
The relationship between analytical and computational methods of investigation of mathematical models of nonlinear dynamics is discussed.
Ключевые слова: математическое моделирование, нелинейная динамика, иерархия моделей, вычислительный эксперимент.
Keywords: mathematical modeling, nonlinear dynamics, hierarchy of models, computational experiment.
В статье дан краткий обзор исторического развития, современного состояния и результатов одной из выдающихся отечественных научных и преподавательских школ в области ИТ – кафедры информатики математико-механического факультета Санкт-Петербургского государственного университета, 40-летие которой отмечается в 2010 году.
The article presents an overview of history, modern status and results of one of the most outstanding Russian scientific and university teaching schools of IT - Chair of Computer Science of Faculty of Mathematics and Mechanics, St. Petersburg State University, whose 40-years anniversary is celebrated in 2010.
The article presents an overview of history, modern status and results of one of the most outstanding Russian scientific and university teaching schools of IT - Chair of Computer Science of Faculty of Mathematics and Mechanics, St. Petersburg State University, whose 40-years anniversary is celebrated in 2010.
Ключевые слова: Санкт-Петербургский университет, математико-механический факультет, кафедра информатики, информатика, математическая логика, теория сложности алгоритмов, искусственный интеллект, синтаксический анализ формальных языков, базы данных, информационный поиск, компиляторы, надежные и безопасные вычисления, управление знаниями, экспертные системы, робототехника, Java, .NET.
Keywords: St. Petersburg University, Faculty of Mathematics and Mechanics, Chair of Computer Science, computer science (informatics), mathematical logic, theory of algorithmic complexity, syntax analysis of formal languages, databases, informational retrieval, compilers, trustworthy computing, knowledge management, expert systems, robotics, Java, .NET.
Для пополнения баланса выберите страну, оператора и отправьте СМС с кодом на указанный номер. Отправив одну смс, вы получаете доступ к одной статье.
Закрыть