Mardi 29 Janvier


Retour à la vue des calendrier
Mardi 29 Janvier
Heure: 12:30 - 13:30
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Combinaison automatique d'algorithmes et heuristiques
Description: Yanik Ngoko Sur de nombreux problèmes combinatoires comme SAT ou CSP, on peut
facilement trouver, étant donné un sous ensemble d'heuristiques, un sous
ensemble d'instances du problème sur lequel aucune heuristique ne domine
complètement les autres(*). Ceci a motivé de nombreux travaux ayant pour
but de combiner plusieurs heuristiques résolvant le même problème afin
d'exploiter leur diversité.

Dans cet exposé, nous nous intéressons à cette problématique en contexte
parallèle et homogène. Dans les solutions décrites, une combinaison est
obtenue en exécutant de façon concurrente dans le temps et dans l'espace
(coeurs, processeurs, régistres caches etc.) plusieurs heuristiques,
jusqu'à ce que l'une d'elles trouve une solution satisfaisante. Pour
apprendre à construire de telles combinaisons, nous proposons une
solution d'apprentissage basée sur une estimation du temps d'exécution
des heuristiques sur un jeu d'instances représentatives. Le coeur de
notre proposition peut être formulé comme un  problème combinatoire dont
nous prouvons la  np-completude et l'inapproximabilité. Nous proposons
pour sa résolution plusieurs heuristiques, avec garanti de performance
sous certaines hypothèses.

Finalement, nous présentons quelques résultats de notre approche de
combinaison sur les problèmes SAT et CSP.

(*) Par exemple dans le temps pris pour donner une solution satisfaisante..
Heure: 14:00 - 17:00
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Initiation à la théorie de Galois différentielle et applications aux fonctions holonomes
Description: Thierry Combot Nous présenterons la théorie de Galois différentielle appliquée auxéquations différentielles à coefficients polynomiaux puis auxéquations aux différences. On montrera ensuite comment calculer cesgroupes de Galois, et quels sont les algorithmes disponibles. Onprésentera alors les méthodes disponibles pour résoudre ceséquations en introduisant les fonctions liouviliennes. Enfin nousappliquerons ces méthodes pour l'analyse du comportementasymptotique des solutions : le groupe de Galois donne en particulier des relations algébriques a priori sur les constantes apparaissant dans ces développements asymptotiques, et permettent dans le cas liouvillien de les expliciter.