The Turing Competition for Student Theory. computer science and discrete mathematics
Last year, the first student contest in theoretical computer science and discrete mathematics was held at the Academic University. Alan Turing. We recently announced the second competition (the deadline for submission of work is May 10, 2017), and in this article we will discuss the results of the first competition .
What for? The main goal of this contest is motivational: we want more students to choose science.
Jury. The jury consisted of acting scientists working in various fields of computer science and discrete mathematics. The jury was composed according to this principle: half from St. Petersburg, where an in-person tour takes place, half from other cities.
The competition consisted of two rounds: correspondence and full-time. In the correspondence round, the works were reviewed and the jury selected the participants of the final full-time tour. A total of 22 entries were submitted for the competition.
')
Selection of works. The work was reviewed according to the standards of international conferences: each work received at least three reviews. They reviewed both the jury members and external reviewers. All participants received reviews on their work. We took into account conflicts of interest and at the stage of selection of works for the final round the jury members did not have access to discuss the work of their students.
The final round. The authors of 8 works were invited to the final round (two works from St. Petersburg, two from Moscow, three from Novosibirsk and one from Ekaterinburg). The finalists made presentations, the jury members and all those present asked questions and discussed. Nonresident members of the jury watched performances on video broadcasting and also asked questions.
Summarizing. After all the speeches, the jury retired to the meeting. It turned out to be a very difficult task to choose the winners, each work had members of the jury wishing to give her a prize. Therefore, the award of prizes caused a heated discussion. As a result, the decision was made by a multi-round rating vote.
Winner. The first place was given to the work “Search for palindromes in the flow model” by Oleg Merkuryev (Ural Federal University, scientific advisor A. M. Shur). This paper solves the problem of finding the longest palindrome substring in a given string in a special streaming computation model. In this model, the string is read character by character and cannot be fully stored in memory. This model is being actively studied recently in connection with a large number of potential applications: computationally weak devices that many data passes through - for example, routers.
We have developed new algorithms that solve the problem approximately, in the sense that the solution obtained will not necessarily be optimal, but will be close to optimal. The running time of the constructed algorithms is linear, a constant number of steps is spent on processing one character, and the amount of memory used only slightly exceeds the theoretical lower estimates. The obtained algorithms significantly improve the results from previous work on this topic of Gavrihovsky and Uznansky 2015.
The solution method is based on the use of hashing, as in the Rabin-Karp algorithm for searching for substrings. The polynomial hash of substrings is easily recalculated during shift operations, which allows O (1) time to process each character. Taking into account the fact that we are satisfied with an approximate solution, it is enough for the algorithm to store not all the “partial hashes”, but only some of them, which allows us to significantly save memory. Read more in the competitive work .
General conclusions. The experience of the first competition showed that many student research papers of decent level are being written in Russia, and the competition is a good reason to bring together talented young scientists. We hope that the popularity of scientific research among students will grow, and even more interesting scientific works will be presented at the second and subsequent competitions.
What for? The main goal of this contest is motivational: we want more students to choose science.
Jury. The jury consisted of acting scientists working in various fields of computer science and discrete mathematics. The jury was composed according to this principle: half from St. Petersburg, where an in-person tour takes place, half from other cities.
The competition consisted of two rounds: correspondence and full-time. In the correspondence round, the works were reviewed and the jury selected the participants of the final full-time tour. A total of 22 entries were submitted for the competition.
')
Selection of works. The work was reviewed according to the standards of international conferences: each work received at least three reviews. They reviewed both the jury members and external reviewers. All participants received reviews on their work. We took into account conflicts of interest and at the stage of selection of works for the final round the jury members did not have access to discuss the work of their students.
The final round. The authors of 8 works were invited to the final round (two works from St. Petersburg, two from Moscow, three from Novosibirsk and one from Ekaterinburg). The finalists made presentations, the jury members and all those present asked questions and discussed. Nonresident members of the jury watched performances on video broadcasting and also asked questions.
Summarizing. After all the speeches, the jury retired to the meeting. It turned out to be a very difficult task to choose the winners, each work had members of the jury wishing to give her a prize. Therefore, the award of prizes caused a heated discussion. As a result, the decision was made by a multi-round rating vote.
Winner. The first place was given to the work “Search for palindromes in the flow model” by Oleg Merkuryev (Ural Federal University, scientific advisor A. M. Shur). This paper solves the problem of finding the longest palindrome substring in a given string in a special streaming computation model. In this model, the string is read character by character and cannot be fully stored in memory. This model is being actively studied recently in connection with a large number of potential applications: computationally weak devices that many data passes through - for example, routers.We have developed new algorithms that solve the problem approximately, in the sense that the solution obtained will not necessarily be optimal, but will be close to optimal. The running time of the constructed algorithms is linear, a constant number of steps is spent on processing one character, and the amount of memory used only slightly exceeds the theoretical lower estimates. The obtained algorithms significantly improve the results from previous work on this topic of Gavrihovsky and Uznansky 2015.
The solution method is based on the use of hashing, as in the Rabin-Karp algorithm for searching for substrings. The polynomial hash of substrings is easily recalculated during shift operations, which allows O (1) time to process each character. Taking into account the fact that we are satisfied with an approximate solution, it is enough for the algorithm to store not all the “partial hashes”, but only some of them, which allows us to significantly save memory. Read more in the competitive work .
General conclusions. The experience of the first competition showed that many student research papers of decent level are being written in Russia, and the competition is a good reason to bring together talented young scientists. We hope that the popularity of scientific research among students will grow, and even more interesting scientific works will be presented at the second and subsequent competitions.
Source: https://habr.com/ru/post/323300/
All Articles