Журналы
Email: Пароль: Войти Регистрация
E-mail: dmitry.pavlov@gmail.com

Аспирант кафедры прикладной математики ФМФ СПбГПУ.

postgraduate student of Saint-Petersburg State Polytechnic University

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

Проводится краткий обзор алгоритмов, среди которых лидирует алгоритм Брендана МакКея, реализованный им в библиотеке 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.

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

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

The article briefly describes a number of open problems in cheminformatics, solving which will allow sooner or later to work out a proper chemical compounds and articles search engine, suitable for the needs of present-day pharmacology. On each problem, the most well-known results are listed, and the weaknesses of the available services are mentioned.

Ключевые слова: фармацевтика, фармакология, органическая химия, химическая информатика.
Keywords: pharmaceutics, pharmacology, organic chemistry, cheminformatics.
Статья описывает подходы к созданию языков, ориентированных на конкретную предметную область. Такие языки называются предметно-ориентированными языками (DSL), и их принято отличать от более известных языков общего назначения. Статья освещает преимущества использования DSL и даёт обзор современных технологий для их создания.

The article gives a brief introduction to creation of languages that are designed for a particular application domain. Such languages are called domain-specific (DSL), and are treated differently from (more widespread) general-purpose languages. The article presents the advantages of using DSL-s in programming and gives a list of modern platforms for building them.

Ключевые слова: предметно-ориентированный язык, парсинг, компиляция.
Keywords: domain-specific language, parsing, compilation.
Статья подробно описывает процесс создания простейшего предметно-ориентированного языка на платформе Racket. Присутствуют лексический анализатор, синтаксический анализатор, интерактивная среда, компиляция, отладка, бектрейсы, подсветка синтаксиса. Созданный язык интегрируется в среду разработки DrRacket. Весь проект занимает менее 300 строк кода. С. 46-63.

The article gives a detailed explanation of how to create a simple domain-specific language (DSL) on the Racket development platform. There is a lexical analyzer, parser, REPL, compiler, debugger, backtraces, syntax highlighting. The new language is integrated into the DrRacket IDE. The whole project is less than 300 lines of code.

Ключевые слова: предметно-ориентированный язык, парсинг, компиляция, Racket.
Keywords: domain-specific language, parsing, compilation, Racket.
В статье приводятся оценки популярности языков программирования в различных сферах и уделяется особенное внимание языку Питон, набравшему популярность в образовательной среде. Приводится перечень широко известных (и не свойственных другим языкам) недостатков Питона как языка и экосистемы. Полезность Питона в карьере признаётся преувеличенной, а в образовательном процессе — скорее отрицательной. С. 75-95.

Various measures of popularity of programming languages in different scopes are discussed in the paper, with Python being the main point of interest. Well-known drawbacks of Python as a language and as an ecosystem (not inherent to other popular languages) are listed. The usefullness of Python in carreer is considered overrated, while in education Python often does more harm than good.

Ключевые слова: Python, программирование, образование.
Keywords: Python, programming, education.
С. 9-14.
Реверсивный поиск – один из алгоритмов, идея которого «витает в воздухе» десятилетиями и который часто изобретается заново программистами, знакомыми с такими алгоритмами, как поиск в ширину (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.

Ключевые слова: реверсивный поиск, перебор подграфов, перебор поддеревьев
Keywords: reverse search, enumeration of the subtrees, enumeration of the subgraphs
Возросшая популярность искусственных нейросетей (ИНС) в образовании, науке и бизнесе может создать впечатление свершившейся революции в компьютерном моделировании и алгоритмах оптимизации. Данный короткий обзор призван обратить внимание на фундаментальные ограничения ИНС и потенциальный вред, который может нанести поощрение изучения ИНС в ущерб строгим математическим методам. С. 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.

Ключевые слова: нейронные сети, нелинейная оптимизация, алгоритмы искусственного интеллекта.
Keywords: neural networks, nonlinear optimization, algorithms of artificial intelligence.
В статье описано новое средство автоматической вёрстки и оформления научной и~программной документации в соответствии с требованиями ГОСТ. Средство называется GOSTdown (ГОСТ + Markdown) и рассчитано на документы крупного размера, создаваемые совместно несколькими участниками. Как правило, такие документы разрабатываются в Microsoft Word. GOSTdown --- набор шаблонов и скриптов, позволяющий пользователям работать над содержательной частью документа в формате Markdown, получая на выходе автоматически собранный документ в формате DOCX, не требующий ручной доработки. GOSTdown основан на универсальном конвертере документов Pandoc и скриптовом языке Powershell. С. 39-46.

The article presents a new tool for automatic layout and publishing of scientific and software documentation in accordance with the requirements of GOST, the Russian national standards. The tool is called GOSTdown (GOST + Markdown) and is designed for large documents created jointly by several participants. Usually such documents are developed in Microsoft Word. GOSTdown is a set of templates and scripts that allow users to work on the content of a document in Markdown format, resulting in an automatically assembled document in DOCX format that does not require manual modification. GOSTdown is based on a universal document converter Pandoc and the Powershell scripting language.

Ключевые слова: документация, генерация документов, Pandoc, Markdown.
Keywords: documentation, document processing, Pandoc, Markdown.
Канонический код – это способ записи графа, инвариантный относительно изоморфизма. В статье вкратце объясняется значимость канонических кодов и показывается связь задачи вычисления канонического кода с другими задачами, известными из курса теории алгоритмов. Приводится алгоритм вычисления канонического кода для дерева с помеченными вершинами и рёбрами, который работает за линейное время от размера дерева. Алгоритм основан на известном алгоритме проверки изоморфизма двух деревьев.

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.

Ключевые слова: канонический код, каноническая нумерация, изоморфизм графов, изоморфизм деревьев.
Статья описывает историю лазерной локации Луны от её возникновения до наших дней. Этот уникальный научный эксперимент, длящийся более 40 лет, позволяет вычислять положение нашего спутника с поразительной точностью. Научные данные, накопленные за время эксперимента, во-первых, позволяют прогнозировать орбитально-вращательное движение Луны на месяцы и даже годы вперёд (что важно для спутниковой навигации на Земле и для поддержки будущих космических миссий к Луне и планетам), во-вторых, доказывают наличие у Луны жидкого ядра и, в-третьих, помогают проверять научные теории, касающиеся фундаментальных свойств пространства-времени. С. 32-41.
Для пополнения баланса выберите страну, оператора и отправьте СМС с кодом на указанный номер. Отправив одну смс, вы получаете доступ к одной статье.
Закрыть