AC: Algorithmes et calcul

Les recherches en informatique théorique se caractérisent par l’utilisation de méthodes et outils mathématiques pour l’étude de problèmes de nature informatique,
en particulier l’algorithmique combinatoire, le calcul numérique, la théorie de la complexité, mais aussi la combinatoire et plus largement les mathématiques discrètes. Il s’agit de comprendre et formaliser par des raisonnement mathématiques l’efficacité et les limites des méthodes du calcul informatique ainsi que les modèles combinatoires et discrets sous-jacents aux objets manipulés par les ordinateurs.
Une large part des travaux développés au sein du pôle Algorithmes et Calcul sont orientés vers l’élaboration d’algorithmes combinatoires (méthodes exactes ou approchées, complexité) ou numériques (précision des calculs, calculs haute performance). Ces recherches algorithmes s’appuient sur des recherches amonts en combinatoire, théorie des graphes, géométrie discrète, automates cellulaires ou encore calcul formel et théorie des nombres. Nous valorisons nos recherches  fondamentales à travers le développement d’applications en imagerie, visualisation, cryptographie, sécurité numérique, bioinformatique. . .
Le pôle Algorithmes et Calcul réunit les équipes Algco, Arith, Escape, Dali, Icar, Maore regroupant environ 80 personnes dont 40 permanents. Les équipes Coconut et Mab y participent aussi de manière significative, bien qu’ayant leur centre de gravité dans d’autres pôles.

Equipes


Séminaires et Groupes de Travail (GT) des équipes

Séminaires du pôle AC

from 2013-06-27 to 2013-06-27

Orateur : Nicolas Trotignon (CNRS, Ens Lyon)
Titre : Décomposition des graphes parfaits

Résumé : La conjecture forte des graphes parfaits, énoncée dans les années 1960 par Claude Berge a été démontrée en 2002 par Chudnovsky, Robertson, Seymour et Thomas par des méthodes de décompositions de graphes. Je rappellerai très brièvement les principales notions et les idées de la preuve. J'insisterai sur le verrou qui empêche d'utiliser la preuve pour résoudre la dernière "grande question" ouverte sur les graphes parfaits, à savoir leur coloration en temps polynomial par un algorithme purement combinatoire. Ce verrou provient de décompositions "pathologiques", qui ont de bonnes propriétés pour la preuve, mais pas pour les algorithmes, par exemple les "skew partitions" inventées par Chvatal. Les skew partitions ont pour cas particulier les "star cutset", dont il sera principalement question par souci de simplification. A la fin de l'exposé, je présenterai très brièvement un résultat obtenu récemment avec Chudnovsky, Trunck et Vuskovic : un algorithme en temps polynomial qui colore les graphes parfaits sans "balanced skew partition".
__________________________________________________________________
from 2013-05-13 to 2013-05-13

Orateur : Dmitry Itsykson (Steklov Institute of Mathematics at St. Petersburg)
Titre : Proof systems and SAT algorithms.

__________________________________________________________________

Orateur : Joergen Bang-Jensen, University of Southern Denmark
Titre : flows, graphs, (arc-)disjoint paths and flows

Résumé : Flows in networks constitute probably the most important application of graph theory with litterally hundreds of practical applications. In this talk we will introduce flows and the fundamental max-flow min-cut theorem and show how this basic result has important applications as a proof techniques in graph theory.
Then we will go on to the (arc)-disjoint paths problem and discuss the complexity of this problem in both graphs and digraphs. In the last part of the talk we will introduce a common generalization of flows and disjoint paths, the (arc-)disjoint flow problem.

__________________________________________________________________

from 2012-04-19 at 14:00 to2012-04-17 at 15:00

Orateur : Erich Kaltofen (North Carolina State University)
Titre : The Art of Hybrid Computation

Résumé : Hybrid symbolic-numeric computation constitutes the Fifth of my "Seven Dwarfs" of Symbolic Computation, which I have listed in my SNSC talk in Hagenberg in 2008. Hybridization requires that the solution of a computational mathematical problem should utilize both a numeric and a symbolic algorithmic component.

In my talk, I will characterize the hybrid methodology by surveying some important results and the lessons I have learned from them. Those include the notion of approximate GCD and approximate sparse interpolant, and the task of the analysis of the random distributions of matrix condition numbers in randomized hybrid algorithms.

One can bypass the analysis by producing a certificate, and I will give sum-of-squares certificates in global optimization via our ArtinProver
software. Specifically, I will discuss certificates of impossibility of sum-of-squares representations based on the Farkas Lemma of semidefinite
programming.

This work is in collaboration with Matthew Comer, Feng Guo, Wen-shin Lee, Clement Pernet, Zhengfeng Yang, and Lihong Zhi.
__________________________________________________________________

from 2012-03-29 at 14:00 to2012-03-29 at 15:00

Orateur : Pavol Hell (Simon Fraser University)
Titre : Finite obstructions to graph partitions

Résumé : Consider graph partitions with possible restrictions on the parts, and on the connections between parts: the restrictions can be that there are no edges, or that all possible edges are present. Many partitions arising in the study of perfect graphs have this flavour. In some cases the existence of such a partition is characterized by the absence of finitely many forbidden induced subgraphs. We ask when this is the case, and give some general answers, and some answers for special graph classes, such as chordal graphs. These include joint results with T. Feder, S. Nekooei Rizi, W. Xie, O. Shklarsky, and others.
__________________________________________________________________
from 2012-02-02 at 15:00 to2012-02-02 at 16:00

Orateur : Dimitrios Thilikos (Department of Mathematics, National and Kapodistrian University of Athens)
Titre : Algorithmic Graph Minors: turning Combinatorics to Algorithms

Résumé : The main mathematical achievement of the Graph Minors Theory, developed by Robertson and Seymour, was the proof of Wagner's conjecture, now known as the Robertson & Seymour Theorem, stating that graphs are well quasi ordered under the minor containment relation. Besides its purely theoretical importance, GMT induced a series of powerful algorithmic results and techniques that had a deep influence in theoretical computer science. GMT offered the theoretical base for the understanding and the resolution of some of the most prominent graph-algorithmic problems in the design of parameterized algorithms. In this talk we give a brief presentation of the main results and techniques to this direction and we comment on their potential and their limitations.

__________________________________________________________________
Archives

Mots-clés

Algorithmique, complexité, calculs, mathématiques discrètes, combinatoire

Dernière mise à jour le 15/09/2014