Abstract FR:

L’optimisation discrète est le noyau fédérateur de la thèse. Pour résoudre les problèmes NP-complets du domaine, les trois directions suivantes sont explorées : (i) la conception d'algorithmes efficaces par la voie d'hybridation des techniques classiques de résolution, ainsi que par l'exploitation des propriétés fondamentales du problème ; (ii) l'élaboration de méthodes heuristiques pour traiter des instances inaccessibles par les méthodes exactes ; (iii) l'utilisation performante du parallélisme pour la résolution des problèmes combinatoires. L’application d'optimisation discrète dans le parallélisme est aussi abordée dans la thèse. La parallélisation efficace d'un algorithme engendre de nombreux problèmes d'optimisation discrète, liés à l'équilibrage de charge entre processeurs, à la granularité optimale du calcul et à la réduction du surcoût de communication. Thèmes principaux : (i) problème de classification (problème d'analyse discriminante linéaire) - conception d'algorithmes efficaces séquentiels et parallèles ; (ii) problème de sac-à-dos multidimensionnel en variables 0-1 - hybridation de programmation dynamique et un système de bornes ; (iii) ordonnancement de systèmes d'équations récurrentes affines - utilisation de programmation linéaire et comparaison des méthodes différentes ; (iv) problème de pavage optimal de l'espace d'iterations pour parallelisation de nids de boucles - détermination de paramètres optimaux du pavage et application de l'approche pour comparaison de séquences génomiques.