II International Conference "Сomputer Assisted Mathematics"
CAM-2021
July 28–30, 2021Photo: Yuriy Bezsonov

_______________________________________

HOW A COMPUTER COULD DISCOVER PRIME NUMBERS

Yuri Matiyasevich (researchgate.net) (math-net.ru)

St. Petersburg Department of Steklov Mathematical Institute of Russian Academy of Sciences

Abstract

Computers can be of help to mathematicians in several ways. Sometimes a computer can prove a hypothesis suggested by a man. Sometimes a computer cannot produce proof but can provide some kind of numerical evidence supportingthe hypothesis and thus encourage mathematician to work hard in order to prove the hypothesis.

Often a mathematician has no definite hypothesis, and computer calculations could allow him/her to state a plausible mathematical hypothesis. 

But could a computer suggest a mathematical notion? The speaker was performing intensive computations and suddenly realized that his computer reinvented the Sieve of Eratosthenes and a new kind of a sieve dual to the Sieve of Eratosthenes.

 

_______________________________________

SAT-BASED CIRCUIT LOCAL IMPROVEMENT

Alexandr Kulikov (math-net.ru)

St. Petersburg Department of Steklov Mathematical Institute of the Russian Academy of Sciences

St. Petersburg State University

Abstract

Finding exact circuit size is a notorious optimization problem in practice. Whereas modern computers and algorithmic techniques allow to find a circuit of size seven in blink of an eye, it may take more than a week to search for a circuit of size thirteen.

One of the reasons of this behavior is that the search space is enormous. In this talk, we explore the following natural heuristic idea for decreasing the size of a given circuit: go through all its subcircuits of moderate size and check whether any of them can be improved by reducing to SAT. This may be viewed as a local search approach: we search for a smaller circuit in a ball around a given circuit. We report the results of experiments with various symmetric functions.

 

_______________________________________

EVOLUTION AND RESPONSES TO STRESS

Sergei Vakulenko (researchgate.net)

Institute of Problems of Mechanical Engineering, Russian Academy of Sciences, St. Petersburg, Russia

Saint Petersburg Electrotechnical University, Ulitsa Professora Popova, Saint Petersburg, Russia

Dmitry Grigoriev (researchgate.net) (pdmi.ras.ru)

CNRS, University of Lille, Lille, France

Abstract

We consider systems of differential equations with polynomial and rational nonlinearities and with a dependence on a discrete parameter. Such systems arise in biological and ecological applications, where the discrete parameter can be interpreted as a genetic code. The genetic code defines system responses on external perturbations. These responses are defined by deep networks. We investigate the stability of attractors of our systems under sequences of perturbations (for example, stresses induced by environmental changes), and we introduce the concept f stability via gene regulation. We show that, if the gene regulation is absent, then the attractors earlier or later collapse. Regulation by genetic codes one can provide attractor stability for all times. So, in the framework of our model we prove the romov-Carbone hypothesis that evolution by replication makes biosystems robust against random fluctuations. Complexity of gene regulation and uncertainty of environment action are measured by special characteristics like to Kolmorogov entropy. To provide attractor robustness gene regulation entropy should be more than environment uncertainty. We apply these results to a model of cancer immune therapy.

 

_______________________________________

HOW COMPUTERS HAVE CHANGED MATHEMATICS

Nikolai Vavilov (researchgate.net)

St. Petersburg State University, St. Petersburg, Russia

Abstract

 

_______________________________________

EXCEPTIONAL UNIFORM POLYTOPES

Danylo Radchenko (researchgate.net)

Swiss Federal Institute of Technology Zürich (ETHZ), Zürich, Switzerland

Abstract

Universal optimality is a very strong property of discrete configurations in Euclidean space, roughly meaning that a configuration minimizes potential energy for a wide range of potentials. Conh and Kumar have conjectured that in dimensions 2, 8, and 24 there are unique universally optimal configurations given by the A2 root lattice, the E8 root lattice, and the Leech lattice respectively, and moreover that their optimality can be proved using linear programming. I will talk about recent joint work with H. Cohn, A. Kumar, S.D. Miller, and M. Viazovska in which we have proved this conjecture in dimensions 8 and 24, using a novel interpolation formula for Fourier eigenfunctions. The emphasis will be on the use of computers in the discovery of the aforementioned interpolation formula, and in the proof of a certain crucial inequality.

 

_______________________________________

SECURE DELEGATION OF COMPUTATION TO ONE OR MORE SERVERS

Vladimir Shpilrain (researchgate.net)

The City College of New York, New York, United States

Abstract

Suppose your computational abilities are limited, and you want to outsource computation of a function f(x_1,...,x_n) , but you want to keep the inputs x_1,...,x_n private. We show that for some functions, one can do this using just one server, while for other functions, including the multiplication function f(a,b)=ab, several non- colluding servers may be needed.

 

_______________________________________

IMPLEMENTATION OF ALGEBRAIC ALGORITHMS FOR APPROXIMATE PATTERN MATCHING ON COMPRESSED STRINGS

Maria Fedorkina

Higher School of Economics, St. Petersburg School of Physics, Mathematics, and Computer Science, St. Petersburg, Russia

Alexander Tiskin (researchgate.net)

St. Petersburg State University, St. Petersburg, Russia

Abstract

Approximate pattern matching is a well-studied problem on strings: given a text t and a pattern p, find all substrings of t that are similar to p. The measure of similarity that we use in this work is the length of the longest common subsequence (LCS) of two strings. We implement an algorithm that solves the approximate pattern matching problem for a pattern p of length m and a text t of length n in time O(mn) implicitly storing all of the LCS values in an algebraic structure of size O(m + n). We additionally generalize the algorithm to calculate the longest common subsequence of a plain (uncompressed) pattern string of length m and a text string of length n, compressed by a straight-line program of length k in time O(mk log k). As this algorithm’s time complexity does not depend on the length of the uncompressed text, we show that the algorithm will achieve a substantial speedup on specific types of compressed texts, even with the increase in the running time constant resulting from complex operations with algebraic structures. We compare the running time of our algorithm to the standard dynamic programming algorithm for approximate pattern matching and to existing approximate pattern matching utilities, and we demonstrate an improvement in both cases.

 

_______________________________________

Boris Melnikov (math-net.ru)

Shenzhen MSU – BIT University, Shenzhen, China

Russian State Social University, Moscow, Russia

Elena Melnikova

Russian State Social University, Moscow, Russia

Financial University under the Government of the Russian Federation, Moscow, Russia

Abstract

In the computer literature, a lot of problems are described that can be called discrete optimization problems: from encrypting information on the Internet (including creating programs for digital cryptocurrencies) before searching for "interests" groups in social networks. Often, these problems are very difficult to solve on a computer, hence they are called "intractable". More precisely, the possible approaches to quickly solving these problems are difficult to solve (to describe algorithms, to program); the brute force solution, as a rule, is programmed simply, but the corresponding program works much slower. Almost every one of these intractable problems can be called a mathematical model. At the same time, both the model itself and the algorithms designed to solve it are often created for one subject area, but they can also be used in many other areas. An example of such a model is the traveling salesman problem. The peculiarity of the problem is that, given the relative simplicity of its formulation, finding the optimal solution (the optimal route). This problem is very difficult and belongs to the so-called class of NP-complete problems. Moreover, according to the existing classification, the traveling salesman problem is an example of an optimization problem that is an example of the most complex subclass of this class. In this paper, we describe several variants of algorithms for generating source data for the traveling salesman problem. We consider both the classical heuristics associated with the branch and bound method, and some added to them. Next, we present a software implementation of our interpretation of the algorithm. At the end of the paper, we formulate some tasks for further research, so the paper can be a project for students' scientific work.

 

_______________________________________

TOUIST: TEACHER- AND STUDENT-FRIENDLY LANGUAGE FOR PROPOSITIONAL LOGIC AND DISCRETE MATHEMATICSUNIVERSAL OPTIMALITY AND INTERPOLATION FORMULAS

Olivier Gasquet (researchgate.net)

Dominique Longin (researchgate.net)

Emiliano Lorini (researchgate.net)

Frederic Maris (researchgate.net)

Pierre Regnier (researchgate.net)

Sergei Soloviev (researchgate.net)

L'Institut de recherche en informatique de Toulouse, Toulouse, France

Abstract

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.

 

_______________________________________

NEW FEATURES IN MATHPARTNER 2021

Gennadi Malaschonok (researchgate.net)

National University of Kyiv-Mohyla Academy, Kyiv, Ukraine

Alexandr Seliverstov (orcid)

Institute for Information Transmission Problems of the Russian Academy of Sciences (Kharkevich Institute), Moscow, Russia

Abstract

We introduce new features in the MathPartner service that have recently become available to users. We highlight the functions for calculating both arithmetic-geometric mean and geometric-harmonic mean. They allow calculating complete elliptic integrals of the first kind. They are useful for solving many physics problems, for example, one can calculate the period of a simple pendulum. Next, one can calculate the modified arithmetic-geometric mean proposed by Semjon Adlaj. Consequently, one can calculate the complete elliptic integrals of the second kind as well as the circumference of an ellipse. Furthermore, one can also calculate the Sylvester matrices of the first and the second kind. Thus, by means of a few strings, one can calculate the resultant of two polynomials as well as the discriminant of a binary form. Some new matrix functions are also added. So, today the list of matrix functions includes the transpose, adjugate, conjugate, inverse, generalized inverse, and pseudo inverse of a matrix, the matrix determinant, the kernel, the echelon form, the characteristic polynomial, the Bruhat decomposition, the triangular LDU decomposition, which is an exact block recursive LU decomposition, the QR block recursive decomposition, and the singular value decomposition. In addition, two block-recursive functions have been implemented for calculating the Cholesky decomposition of symmetric positive-definite matrices: one function for sparse matrices with the standard multiplication algorithm and another function for dense matrices with multiplication according to the Winograd–Strassen algorithm. The linear programming problems can be solved too. So, the MathPartner service has become better and handy. It is freely available at http://mathpar.ukma.edu.ua/ as well as at http://mathpar.com/

 

_______________________________________

INTERACTIVE PRESENTATION OF MATHEMATICAL OBJECTS

Pavel Pankov orcid

Institute of Mathematics of NAS, Bishkek, Kyrgyzstan

Abstract

Proposed kind of presentations has the following features: no preliminary knowledge on the object is necessary and the user masters the object while treating with a computer mouse; mathematical objects are treated as real ones with peculiarities; each presentation is also a task (after successful solution of the task the soft announces: ”Congratulations! You have mastered the notion ...”) . Two kinds of presentations are involved: avatar ones (the user controls an object considered as their own person) and non-avatar ones (the user is an observer moving in the space). Functions are presented as responds to avatars motions. Ordinary differential equations (ODE) are presented as directions fields and bends fields. The following items are described. For continuous objects: local suprema of a function; zeros of a function; solving of system of linear algebraic equations; contraction mapping principle; solving of initial value problem for ODE of the first order and for system of two autonomous ODE; solving of boundary value problem for ODE of the second order; kinds of symmetry;(with the notion of invariant): length and area, transformations of geometrical figures, integral; 4D-space; non-Euclidean spaces including Riemann surfaces, Moebius band, projective plane, topological torus. Discrete objects: experiments with the ring of natural numbers presented as Ulam spiral and with prime complex numbers.

 

_______________________________________

DYNAMIC MATHEMATICS WEEK BY WEEK

Vladimir Dubrovsky (istina.msu.ru)

AESC MSU – Kolmogorov boarding school, Moscow, Russia

Aleksei Sgibnev

Intellectual School, 13 Kremenchugskaia str., Moscow, Russia

Abstract

Examples of practical usage of dynamic geometry software, or of more advanced interactive mathematical systems (IMS) found in the literature most often describe some local experiments, after-class activities, or elective courses. School lockdown of 2020-21 forced instructors to conduct their regular classes remotely for an entire academic year. In these circumstances, IMS as a teaching tool have shown new sides of their potential. We share our experience of using IMC in remote teaching in two Moscow schools, give sample tasks and student feedback.  

The reported study was funded by RFBR, project number 19-29-1421

 

_______________________________________

ON THE AUXILIARY ROLE OF COMPUTER TOOLS IN THE CLARIFICATION AND PROLIFERATION OF FUNDAMENTAL GEOMETRIC CONSTRUCTIONS

Semjon Adlaj (math-net.ru)

Federal Research Center “Informatics and Control” Russian Academy of Sciences, Moscow, Russia

Abstract

Due to the spread of computer technologies, fundamental geometric constructions which were previously deemed too cumbersome for school education are nowadays quite amenable. Thus, the geometric constructions in Isaac Newton's book "Mathematical Principles of Natural Philosophy" which had remained outside the scope of any school curriculum, despite the growing importance of their study in modern civilization, with its rapidly developing technologies, might be broadly introduced and taught. Of course, the concepts of hypocycloid and hypercycloid should not remain formal for schoolers, but must be accompanied by numerous computer animations. A visual demonstration allows us to proceed with the concepts of evolute and involute (for plane curves). Thereby, concepts (which had merely been formally introduced in the school course in physics) such as the cycloid pendulum, tautochrone and brachistochrone also become accessible. And following Newton, not merely the traditional solution (in the form of a cycloid), assuming a homogeneous gravity field in the formulation of the aforementioned problems, becomes attainable for schoolers (who are not familiar with differential and integral calculus) but also a solution (in the form of a hypocycloid) of a more general setting of the problem, where the gravity field turns out being central, with its intensity increasing in direct proportion to the distance from the center. An essential factor, contributing to a successful introduction of fundamental mathematical concepts in a modern school is the possibility of establishing remote interaction with active scientists, as well as, the possibility of active participation of schoolchildren, including the youngest, in scientific conferences of both local and international significance.

 

_______________________________________

USE OF COMPUTER ALGEBRA SYSTEMS IN TEACHING MATH AT SGU

Stefan Hypolite

Aleksandr Myllari

School of Arts and Sciences, St. George’s University, Grenada, West Indies

Abstract

We present our program to incorporate Computer Algebra Systems in teaching of Mathematics (College Math, Calculus, Linear Algebra & Geometry) at St. George’s University (Grenada, West Indies). Modern Computer Algebra Systems (CAS), such as Mathematica, Maple, Maxima, etc. are very powerful, have good graphics facilities and can be used for teaching as well as research. We have selected Maxima as a base CAS to use.

 

_______________________________________

USING TECHNOLOGY WITH FUTURE TEACHERS OF PRIMARY SCHOOL MATHEMATICS: A GLIMPSE INTO AN AMERICAN EXPERIENCE

Sergei Abramovich (researchgate.net)

State University of New York School of Education and Professional Studies, Potsdam, NY, USA

Abstract

The paper describes the author’s experience in using technology within mathematics content and methods (undergraduate and graduate) courses for prospective teachers of primary grades (age 5-10). The main pedagogical idea behind the courses is to change pre-teachers’ perception of mathematics as a subject matter most people predictably dislike. It is suggested that technology can assist instructors in making mathematics an enjoyable subject matter without sacrificing content. The paper provides examples of using Excel, Wolfram Alpha, dynamic geometry software, computer graphing program, and the Online Encyclopedia of Integer Sequences. In conclusion, solicited comments by teacher candidates about their experience of learning computer assisted mathematics are shared.

 

_______________________________________

СПОСОБЫ ПРОВЕРКИ И САМОПРОВЕРКИ РАЗЛИЧНЫХ ТИПОВ ЦИФРОВЫХ ЗАДАНИЙ ПО МАТЕМАТИКЕ ДЛЯ ШКОЛЬНИКОВ

Natalia Lebedeva (researchgate.net)

1C Company, Seleznevskaya Str., 34, Moscow, Russia

Abstract

Большинство современных платформ электронного образования, предлагающих задания с автоматической проверкой ответов, обладают весьма скудным функционалом ввода и проверки ответов к математическим задачам. Обычно есть возможность вводить символы только с клавиатуры, что ограничивает формы допустимых ответов целыми числами, дробями и простыми формулами. Это вынуждает авторов электронных пособий отказываться от задач со сложными или нечисловыми ответами и формулировать задания так, чтобы ответ был «простым», что зачастую обедняет и математическое содержание. В докладе обсуждается опыт создания инструментов для проверки различных типов цифровых задач по математике со «сложными» ответами: алгебраическими выражениями, геометрическими построениями, графиками функций и др. Приводятся примеры и систематизация различных видов цифровых заданий по математике для выполнения на компьютерах (планшетах). Демонстрируются возможности автоматической проверки и самопроверки в различных классах задач. Обсуждается необходимый функционал для создания заданий со «сложными» ответами на платформах электронного образования (этапы ввода, интерпретации, отображения и проверки ответа) и необходимые инструменты (специализированные редакторы для ввода формул, инструменты построения геометрических фигур и графиков, инструменты преобразований и интерактивного взаимодействия с заданием и др.). Приводятся примеры цифровых заданий по арифметике, алгебре, планиметрии, стереометрии, теории вероятностей, в том числе и заданий для подготовки к ЕГЭ, созданных при помощи конструктора тестовых вопросов и в среде динамической математики «1С:Математический конструктор». 

Работа выполнена при поддержке гранта РФФИ №19-29-14217

 

_______________________________________

DIGITAL EXERCISERS IN STUDENTS TRAINING FOR THE UNIFIED STATE EXAMIN MATHEMATICS

Tatiana Chernetskaya

1C Company, Seleznevskaya Str., 34, Moscow, Russia

Abstract

The article considers two types of digital exercisers for preparing students for the Unified State Exam in mathematics at the advanced level: exercises for training in solving problems with a short answer (the first part of the Unified State Exam) and training simulators for preparing for solving problems with a detailed answer (the second part of the Unified State Exam). The first type of the digital exercises is characterized by the ability to repeatedly solve both problems of a certain type, and the variants formed from them, similar to the variants of the Unified State Exam, receiving hints in case of difficulties, automatic verification and analysis of answers. The second type of the digital exercises is characterized by a step-by-step analysis of the solution of each problem with hints and analysis of the correctness of each step, as well as the support of such simulators (in particular, on the topics "Stereometry" and "Problems with a parameter") with dynamic models created in the interactive mathematics environment "1C:Mathkit". The various forms of using simulators in the educational process are also discusses in the article: support for independent activity of students in the full-time educational process, support for online training with a teacher in the context of the coronavirus pandemic, and independent online training without a teacher based on specially prepared and structured training courses. In the latter case, in addition to simulators, other digital educational resources were used, the purpose of which was to increase the degree of clarity in the presentation of educational material: videos, slides, dynamic models, training exercises for problems with a detailed answer of the Unified State Exam variants. 

The reported study was funded by RFBR, project number 19-29-1421

 

_______________________________________

EXPLORING CONNECTIONS BETWEEN MATHEMATICS AND INFORMATICS FROM MID-1960S TO EARLY 1990S: FIRST EXPERIMENTS AND CONTINUING INNOVATIONS IN RUSSIAN/SOVIET SCHOOLS

Viktor Freiman (researchgate.net)

Université de Moncton, Moncton, Canada

Abstract

The modern development of computer use in school mathematics, in Russia and in other parts of the world, goes back to 1950s - early 1960s, often related to some reform-based initiatives in education, in general (closer connection of school to societal needs, to the needs of industrial development, to raise well educated citizens able to solve complex tasks able to use scientific methods while working with new technologies, among others) and specifically in mathematics (modernization of school curriculum, closer connection to real-life, increasing role of mathematics in society, learning more complex mathematics by more (all!) students, etc.). When working on our recent analysis of Russian experience in post-Soviet era (from 1990s up to recent times), Pozdniakov and Freiman (2021) have identified several trends and issues that were already identifiable in early developments when computers came to schools first as introduction to programming and related mathematics in special schools for physics and mathematics, then as part of vocational training to finally enter as independent (yet inherently related to mathematics) school subject informatics and as novel tools to enrich mathematics teaching and learning. My talk will do deeper in this process that brought to life novel connections between two disciplines while increasing learning opportunities for both, mathematics and informatics. I will focus on position papers, curriculum materials and debates in the journal Matematika v shkole (Mathematics in schools) while also crossing them with broader international experience.

 

_______________________________________

MATHEMATICS IN A TECHNICAL UNIVERSITY: THE POTENTIAL OF HORIZONTAL CONNECTIONS

Sergei Pozdniakov (researchgate.net)

Elena Tolkacheva

St. Petersburg Electrotechnical University "LETI", St. Petersburg, Russia

Abstract

In the last two years, the weight of distance learning has sharply increased in the structure of training sessions. As a result, the relationship in the triangle "teacher - student - information resources" has changed. The preservation of teaching methods with the transfer of traditional methods of working in full-time mode to a distance format led to a sharp increase in the workload of teachers, or, while maintaining the load, to a decrease in the effect of the teacher's influence on the student and a deterioration in the quality of training. The report discusses pedagogical technologies for organizing a new type of interaction between the subjects of the educational process, which the authors call "horizontal" connections and their technical support.

_______________________________________

АНАЛИЗ ПРОДУКТИВНОСТИ РЕШЕНИЯ ПЕРЦЕПТИВНО-КОГНИТИВНЫХ ЗАДАЧ В УСЛОВИЯХ ВИЗУАЛЬНОЙ НЕОПРЕДЕЛЕННОСТИ

Elena Kotova (researchgate.net)

Andrei Pisarev

St. Petersburg Electrotechnical University "LETI", St. Petersburg, Russia

Abstract

В среде обучения необходимо использовать различные инструменты оценки продуктивности учебной деятельности не только для получения итогового результата, но и в процессе обучения с целью сбора актуальных, данных, на основе которых можно проанализировать потенциальные возможности обучающихся по восприятию информации. В докладе представлен метод автоматизированного анализа результатов решения перцептивно-когнитивных задач учащимися в электронной среде обучения. Метод обеспечивает выполнение следующих функций: - интеллектуальный анализ и оценку когнитивной нагрузки; - оценку моделей когнитивного потенциала пользователей; - прогнозирование и визуализацию данных. Метод реализован в автоматизированной среде и применяется при проведении научных исследований и обучении студентов.

 

_______________________________________

PLUS COMPUTER

Sergey Ivanov

Valery Ryzhik

St. Petersburg Electrotechnical University "LETI", St. Petersburg, Russia

Lyceum "Physical-Technical High School" named after Zh.I. Alferov, St. Petersburg, Russia

Abstract

The article discusses the possibility of using the GeoGebra in school geometric education. An example is starting a systematic course. The system of problems is divided by type of activity (educational, research, critical) and by type (construction, proof, research, calculation, evaluation).

 

_______________________________________

ВНЕШНИЕ БИЛЬЯРДЫ ВНЕ РАЦИОНАЛЬНЫХ ТРАПЕЦИЙ

Yaroslav Orlov

CHOU "School" AL ", Tver, Russia

Elizaveta Manzhula

ANOO "Phystech Lyceum" named after P. L. Kapitsa, Dolgoprudny, Russia

Aleksandr Sribniak

MBOU "Gymnasia", Arzamas, Russia

Abstract

Работа посвящена исследованию ( с использованием компьютерного моделирования) внешних бильярдов вне рациональной трапеции. Она проводилась в рамках проектной смены в Сириусе проектной программе. Мотивировка предложенных результатов дана в PDF-файле с описанием проекта "Кусочно-евклидова динамика". Для удобства читателя используемые определения из проекта резюмируются в приложении. Мы ставим компьютерные эксперименты и формулируем гипотезы на их основании.

 

_______________________________________

OUTER BILLIARD OUTSIDE A REGULAR DODECAGON

Filip Rukhovich (researchgate.net)

Moscow Institute of Physics and Technology (National Research University), Moscow, Russia

Abstract

The existence of an aperiodic orbit for an outer billiard outside a regular dodecagon is proved. It is shown that almost all orbits of such an outer billiard are periodic, and all possible periods are explicitly listed. The proofs of the theorems make use of computer calculations.