Содержание журнала, редсовет, редколлегия.

Table of contents, editorial board, editors.

С древности алгоритмы неразрывно связаны с математикой. Однако самостоятельное развитие теория алгоритмов получила лишь в первой половине ХХ века. Начальный период был связан с открытием как неразрешимых, так и очень трудных проблем. Например, в 1927 году Габриэль Судан опубликовал первый пример вычислимой функции, которая доказуемо не служит примитивно рекурсивной. Практическое значение асимптотических оценок вычислительной сложности стало очевидным лишь во второй половине ХХ века. Мы рассматриваем некоторые хорошо известные задачи принятия решений, которые можно решить за квазиполиномиальное время, то есть задачи, предположительно принадлежащие к промежуточному классу между полиномиальным и экспоненциальным временем. Коллекция включает в себя проверку изоморфности, вычисление исхода игры на чётность и (обоснованную в предположении справедливости обобщенной гипотезы Римана) факторизацию многочленов от одной переменной над конечными полями. Также представлены некоторые технические результаты, которые могут быть использованы для создания новых алгоритмов квазиполиномиального времени. С. 5-12.

Since ancient times, algorithms are inextricably linked with mathematics. However, the theory of algorithms received independent development only in the first half of the 20th century. The initial period was associated with discovery of unsolvable as well as very difficult problems. So, in 1927 Gabriel Sudan published the first example of a computable function that is provably not primitive recursive. The practical significance of asymptotic estimates of computational complexity became apparent only in the second half of the 20th century. We consider some well-known decision problems solvable in quasipolynomial time, that is, problems presumably belonging to the intermediate class between polynomial time and exponential time. The collection comprises isomorphism testing, solution to the parity game, and (validated under the generalized Riemann hypothesis) factorization of univariate polynomials over finite fields. We also present some technical results, which can be used to create new quasipolynomial-time algorithms.

В работе рассматриваются вопросы логической формализации и решения задач с использованием автоматических систем проверки выполнимости. Предлагается автоматический транслятор TouIST, который позволяет генерировать логические формулы на основе простого полуформального описания проблемы. С его помощью оказывается возможным моделировать множество статических и динамических комбинаторных задач. Подчеркивается полезность системы в качестве вспомогательного средства для сопровождения курса логики и дискретной математики. Дополнительную выгоду пользователи смогут извлечь благодаря постоянному совершенствованию SAT, QBF и SMT-систем проверки выполнимости применительно к эффективному решению конкретных логических и комбинаторных проблем, таких, как планирование задач в области искусственного интеллекта. С. 13-25. (на англ.)

This work deals with logical formalization and problem solving using automated solvers. We present the automatic translator TouIST that provides a simple language to generate logical formulas from a problem description. Our tool allows us to model many static or dynamic combinatorial problems. All this can be very helpful as a teaching support for logics and discrete mathematics. Users will benefit from the regular improvements of SAT, QBF or SMT solvers in order to solve concrete logical and combinatorial problems efficiently, e.g., different classes of planning tasks in Artificial Intelligence.

Задача представления знаний для сложных структурированных объектов является одной из актуальных задач ИИ. Это связано с тем, что многие исследуемые объекты представляют собой не единый неделимый объект, характеризующийся своими свойствами, а сложные конструкции, элементы которых обладают известными свойствами и находятся в некоторых, зачастую многоместных, отношениях между собой. В работе подход к представлению таких знаний на основе логики первого порядка (формул исчисления предикатов) сравнивается с двумя широко распространёнными в настоящее время подходами, основанными на представлении информации о~данных с помощью конечнозначных строк и на использовании графов. Показано, что использование формул исчисления предикатов для описания сложных структурированных объектов, несмотря на NP-трудность решаемых задач, возникающих после формализации, реально имеют не б'{о}льшую вычислительную сложность, чем два других подхода, о чём обычно не упоминают их сторонники. Предложен алгоритм построения онтологии, не зависящий от способа описания объекта и основанный на выделении наибольшего общего свойства объектов из заданного множества. С. 41-57.

The problem of knowledge representation for a complex structured object is one of the actual problems of AI. This is due to the fact that many of the objects under study are not a single indivisible object characterized by its properties, but complex structures whose elements have some known properties and are in some, often multiplace, relations with each other. An approach to the representation of such knowledge based on first-order logic (predicate calculus formulas) is compared in this paper with two currently widespread approaches based on the representation of data information with the use of finite-valued strings or graphs. It is shown that the use of predicate calculus formulas for description of a complex structured object, despite the NP-difficulty of the solved problems arising after formalization, actually have no greater computational complexity than the other two approaches, what is usually not mentioned by their supporters. An algorithm for constructing an ontology is proposed that does not depend on the method of describing an object, and is based on the selection of the maximum common property of objects from a given set.

Ранее первый автор ввел определение независимого компьютерного представления объекта (пользователь может изучить объект без знаний об аналогичных объектах). В статье представлены примеры описаний интерактивных математических моделей: для понятий на естественных языках (без каких-либо других языков в качестве носителей; глаголы представлены как действия пользователя); для самой математики (с минимальными пояснениями) и для физики. С. 58-65. (на англ.)

Earlier, the first author introduced a definition of independent computer presentation of an object (the user can master the object without reference to similar objects). The paper presents examples of descriptions of interactive mathematical models: for notions in natural languages (without any other languages as media; verbs are presented as the user's actions); for mathematics itself (with minimal explanations) and for physics.

Эпидемия коронавируса (COVID-19) в России заставила вузы перейти на дистанционный формат образовательной деятельности. Преподаватели в срочном порядке переходили на дистанционные образовательные технологии обучения, используя различные инструменты коммуникации. За время дистанционного обучения в условиях пандемии преподаватели получили ценный опыт чтения лекций онлайн, проведения практических занятий и контрольных работ, экзаменационной сессии и консультаций и т.,д. Дистанционное обучение требовало применения новых образовательных технологий, которые должны были обеспечить такое же качество обучения, как и при очном общении. По сравнению с традиционным обучением объем работы со студентами стал больше, у преподавателей увеличилось время, затраченное на подготовку к занятиям. Но оказалось что, благодаря техническим средствам, обеспечивающим полноценное общение на расстоянии, многие разработанные и использованные в~дистанционном обучении методические приемы вполне применимы и в традиционном (очном) обучении. В статье на примере преподавания линейной алгебры и~алгебраических структур студентам-первокурсникам одного из потоков Факультета компьютерных технологий и информатики в Санкт-Петербургском электротехническом университете (СПбГЭТУ) на основании полученного опыта делаются выводы о~возможности применения некоторых методических приемов в очном обучении с~использованием коммуникационных технологий в общении со студентами. С. 66-83.

The coronavirus (COVID-19) epidemic in Russia forced colleges and universities to switch to distance teaching and learning. The instructors had to make an emergency move to the remote methods of teaching using various platforms. In the course of the distance learning period in midst of an on-going pandemic, the instructors acquired valuable experience in on-line lecturing, administering tests, conducting tutorials, examination sessions, office hours, etc. Distance teaching called for new educational technologies that would provide the quality of education comparable to the in-person teaching. Compared to the traditional teaching, the time needed to prepare for classes has increased. However, it turned out that thanks to the technologies developed to facilitate high-quality distance interaction, many of the methodologies developed for distance learning can be quite useful in traditional (in-person) learning as well. Using a course in Linear Algebra and Algebraic Structures taught to the freshmen at Saint Petersburg Electro-technical University as an example, this article demonstrates that it is possible to use some of the communication technologies–based methodologies to enhance in-person learning.

Описаны горизонтальные связи, которые реализуются на кафедре алгоритмической математики СПбГЭТУ «ЛЭТИ», как составная часть методики обучения, основанной на синтезе трех важнейших концепций мышления и профессионального обучения: теории продуктивного мышления и обучения, конструктивистской теории обучения, теории технического мышления (ПроКоТех-подхода). Из постановки цели развития мышления профессионала, в данном случае технического мышления, в процессе обучения в техническом университете возникают общие психофизиологические вопросы формирования и развития мышления при обучении. В современном техническом образовании все более актуальными являются компетенции, связанные с информацией и знаниями --- их извлечением, преобразованием и применением. Компетенции такого рода подразумевают не только развитость навыков работы с информацией, но и гибкость мыслительной деятельности субъекта, так как именно мышление человека становится идеальной базовой моделью для технологий. Математика и другие фундаментальные дисциплины в технических университетах читаются в основном на первом курсе, что принуждает планировать не только содержание дисциплин, но и обучение приемам организации умственной работы, подготовку к увеличению интенсивности умственной работы. Показан потенциал горизонтальных связей для активизации интеллектуальной работы студентов, повышения их учебной мотивированности, а также повышения устойчивости системы умственной деятельности при увеличении нагрузки. С. 84-100.

Horizontal connections, which are implemented at the Department of Algorithmic Mathematics of St. Petersburg State Electrotechnical University «LETI» as an integral part of the methodology of the Procotech approach to learning, are described. From the statement of the goal of developing the thinking of a professional, in this case technical thinking, in the process of studying at a technical university, general psychophysiological issues of the formation and development of thinking during training arise. In modern technical education, competencies related to information and knowledge --- their extraction, transformation and application --- are increasingly relevant. Competencies of this kind imply not only the development of information skills, but also the flexibility of the subject’s mental activity, since it is human reasoning that becomes the ideal basic model for technology. Mathematics and other fundamental disciplines in technical universities are taught mainly in the first year of education. This forces us to plan not only the content of disciplines, but also training in methods of organizing mental work and preparation for increasing the intensity of mental work. Horizontal connections are shown as potential to activate the intellectual work of students, increase their academic motivation, as well as increase the stability mental activity system with an increase in workload.