Sites Inria

Version française

ALGO Research team

Algorithms

  • Leader : Bruno Salvy
  • Research center(s) : CRI de Paris
  • Field : Symbolic systems
  • Theme : Algebraic and geometric structures, algorithms

Team presentation

The aim of the project-team is the analysis and optimization of complex discrete systems with an important random behaviour. Numerous problems of large size fit into this framework, such as the quantitative study of probabilistic algorithms over discrete structures, or the optimization of resource allocation in communication networks. The achievement of this aim requires an in-depth understanding of discrete randomness and of the mathematical problems involved in its evaluation. General methods that lead to exact or asymptotic results need to be set up. Then, the results obtained provide very precise indications on the qualitative or quantitative behaviour of systems under study.

Given the very systematic nature of our approach, decision methods that can be implemented in computer algebra are also part of the aims of the project. This has proved a fruitful source of renewal which led to revising classical approaches in the areas of special functions or asymptotic expansions. The aim is to offer a reliable and complete algorithmic toolbox for large classes of well-specified problems; see our libraries gfun and Mgfun that are already used much in the combinatorial community and are included in the recent versions of Maple. These results lead to various applications besides the area of combinatorial models: thus a better integration of special functions in computer algebra is envisioned, with applications to large classes of problems in engineering.

Research themes

  • Analysis of algorithms;
  • Computer algebra;
  • Algorithms on sequences;
  • Communication algorithms and protocols for networks.

International and industrial relations

  • International relations with Barcelone, Canterbury, Florence, Hong-Kong, Montreal, Moscow, Princeton, Purdue, Rome, Vienna, Vancouver universities, ...

  • Participation in the European Union Esprit BRA Alcom-FT (Algorithms and Complexity--Future Technologies) project (10 partners). Bilateral programs Procore (Hong-Kong) and Amadeus (Austria).

  • Agreement with Waterloo Maple Inc., company selling one of the main computer algebra systems (Maple).

  • Participation in project INTAS ``Methods, algorithms, and software for functional and structural annotation of complete genoms'' (4 partners).

  • CTI France Télécom R&D for optimization of TCP traffic; RNRT Métropolis for the use of metrology in the study of IP networks.

Keywords: Analysis of algorithms Algorithmics Combinatorial and asymptotic analysis Performance evaluation Automatic analysis Symbolic computing and computer algebra Trees Sorting and searching Communication pr