• A
  • A
  • A
  • ABC
  • ABC
  • ABC
  • А
  • А
  • А
  • А
  • А
Regular version of the site
Advanced search
Priority areas
by year
Subject

News

19 April 2019

Can Peripheral Regions Become Popular Tourist Destinations?

What constitutes a country’s geographic core and periphery? Can a periphery turn into a core? What is the role of tourism in regional development? These questions were addressed in the presentation made by David Weaver (Dongbei University of Finance & Economics, China) at the Tourism and Hospitality session of the XX April International Conference held in Moscow last week.

19 April 2019

HSE Opens Laboratory of Financial Data Analysis

The unit will focus on applying machine learning methods to financial services. The laboratory is part of the Centre of Deep Learning and Bayesian Methods and another partner project between Sberbank and HSE’s Faculty of Computer Science.

18 April 2019

Exploring the Phenomenon of Manga Literature

On April 15, the IGITI Research Centre for Contemporary Culture hosted a round table on ‘Manga as Literature, Manga as Reading’. The event began with a guest lecture by Jaqueline Berndt (Professor of Japanese Language and Culture, Stockholm University).

Article

A new effective dynamic program for an investment optimization problem

Automation and Remote Control. 2016. Vol. 77. No. 9. P. 1633-1648.
Gafarov E., Dolgui A., Lazarev A. A., Werner F.

After a series of publications of T.E. O’Neil et al. (e.g. in 2010), dynamic programming seems to be the most promising way to solve knapsack problems. Some techniques are known to make dynamic programming algorithms (DPA) faster. One of them is the graphical method that deals with piecewise linear Bellman functions. For some problems, it was previously shown that the graphical algorithm has a smaller running time in comparison with the classical DPA and also some other advantages. In this paper, an exact graphical algorithm (GrA) and a fully polynomial-time approximation scheme based on it are presented for an investment optimization problem having the best known running time. The algorithms are based on new Bellman functional equations and a new way of implementing the GrA.

Language: English
 DOI
Keywords: algorithm
Publication based on the results of: Development and research of new mathematical models in socio-economic and political spheres(2016)
Similar publications
Mathematical Methods in Engineering
Springer, 2007.
Added: Jan 22, 2015
24th International Symposium, ISAAC 2013, Hong Kong, China, December 16-18, 2013, Proceedings
Heidelberg: Springer, 2013.
Added: Apr 11, 2019
PQ, a new program for phylogeny reconstruction
Penzar D., Krivozubov M., Спирин С. А. BMC Bioinformatics. 2018. Vol. 19. No. 374. P. 1-14.

Background. Many algorithms and programs are available for phylogenetic reconstruction of families of proteins. Methods used widely at present use either a number of distance-based principles or character-based principles of maximum parsimony or maximum likelihood.

Results. We developed a novel program, named PQ, for reconstructing protein and nucleic acid phylogenies following a new character-based principle. Being tested on natural sequences PQ improves upon the results of maximum parsimony and maximum likelihood. Working with alignments of 10 and 15 sequences, it also outperforms the FastME program, which is based on one of the distance-based principles. Among all tested programs PQ is proved to be the least susceptible to long branch attraction. FastME outperforms PQ when processing alignments of 45 sequences, however. We confirm a recent result that on natural sequences FastME outperforms maximum parsimony and maximum likelihood. At the same time, both PQ and FastME are inferior to maximum parsimony and maximum likelihood on simulated sequences. PQ is open source and available to the public via an online interface.

Conclusions. The software we developed offers an open-source alternative for phylogenetic reconstruction for relatively small sets of proteins and nucleic acids, with up to a few tens of sequences.

Added: Oct 26, 2018
О некоторых функциональных и численных характеристиках древовидных режимов работы хэш-функций
Миронкин В. О., Тимохин И. С. Обозрение прикладной и промышленной математики. 2018. Т. 25. № 2. С. 103-112.

Modes for parallelization of the process of calculating the hash code and data transfer based on l-ary trees are described. A comparative analysis of their implementations written in the Python programming language is carried out and some functional features are described. Promising directions in the field of synthesis of the tree modes of hash functions are proposed.

Added: Jan 25, 2019
Topological classification of Ω-stable flows on surfaces by means of effectively distinguishable multigraphs
Vladislav E. Kruglov, Dmitry S. Malyshev, Olga V. Pochinka. arxiv.org. math. Cornell University, 2017. No. 1706.01695v1.
Structurally stable (rough) flows on surfaces have only finitely many singularities and finitely many closed orbits, all of which are hyperbolic, and they have no trajectories joining saddle points. The violation of the last property leads to Ω-stable flows on surfaces, which are not structurally stable. However, in the present paper we prove that a topological classification of such flows is also reduced to a combinatorial problem. Our complete topological invariant is a multigraph, and we present a polynomial-time algorithm for the distinction of such graphs up to an isomorphism. We also present a graph criterion for orientability of the ambient manifold and a graph-associated formula for its Euler characteristic. Additionally, we give polynomial-time algorithms for checking the orientability and calculating the characteristic.
Added: Sep 11, 2017
On the Model Checking of Finite State Transducers over Semigroups
Gnatenko A. R., Zakharov V. Proceedings of the Institute for System Programming of the RAS. 2018. Vol. 30. No. 3. P. 303-324.

The syntax and semantics of the new temporal logic LP-CTL * designed for the formal specification of the behavior of sequential responsive programs, modeled by automata-transducers (transducers) over semigroups, are developed. An algorithm is developed for verifying the feasibility of the formulas of the proposed temporal logic on models represented by finite transducers working on free semigroups. The correctness of the developed algorithm is proved and an upper bound of its complexity is obtained.

Added: Jun 14, 2018
Языки спецификаций моделей Крипке на основе темпоральных логик и их выразительные возможности
Гнатенко А. Р., Захаров В. А. В кн.: . С. 131-133.

The expressive power of a new variant of temporal logic LP-CTL * is studied. In this logic, two classes of LP-1-LTL and LP-n-LTL formulas were distinguished and it was shown that the LP-1-LTL fragment more expressive than the known temporal logic of linear time LTL, and the LP-n-LTL fragment has the same expressive possibilities as the second-order monadic logic S1S. 

Added: Jun 14, 2018
Алгоритмизация и программирование
Паволоцкий А. В. В кн.: . Гл. 1. С. 8-87.
Added: Mar 14, 2013
Search on the enumeration tree in the multiprocessor job-shop problem
Lazarev A. A., Carballo L., Vakhania N. et al. In bk.: IFAC Proceedings Volumes 14th IFAC Symposium on Information Control Problems in Manufacturing, Bucharest, 23-25 May 2012. Bucharest: IFAC Technical Committee, 2012. P. 381-386.

We present an approach based on a two-stage ltration of the set of feasible solutions for the multiprocessor job-shop scheduling problem. On the rst stage we use extensive dominance relations, whereas on the second stage we use lower bounds. We show that several lower bounds can eciently be obtained and implemented.

Added: Feb 12, 2013