CALENDRIER

mai 2019
L M M J V S D
    01 02 03 04 05
06 07 08 09 10 11 12
13 14 15 16 17 18 19
20 21 22 23 24 25 26
27 28 29 30 31    

Partager cet événement

Enregistrer cet événement

Séminaire GIGL : Nouvel algorithme de filtrage pour le raisonnement énergétique de la contrainte Cumulative

Date
Jeudi 17 janvier 2019
11:30 à 12:20

Contact
Jinghui Cheng

Lieu
L-4812
2700, chemin de la Tour
Montréal, QC Canada
H3T 1J4

Site Web | Itinéraire et carte

Catégories

Retrouvez également cet événement sur


Consulté 272 fois

Titre : Nouvel algorithme de filtrage pour le raisonnement énergétique de la contrainte Cumulative

Conférencière : Claude-Guy Quimper

Résumé : En programmation par contraintes, la contrainte Cumulative permet de modéliser des problèmes d'ordonnancement où n tâches s'exécutent sans interruption. Des tâches peuvent s'exécuter simultanément pourvu que le taux d'utilisation total de la ressource ne dépasse pas sa capacité. Les solveurs de contraintes utilisent des algorithmes de filtrage afin de réduire la taille de l'arbre de recherche et ainsi réduire le temps de résolution d'un problème. Je présenterai un nouvel algorithme de filtrage basé sur le raisonnement énergétique. Ce raisonnement, qui permet de filtrer fortement l'espace de recherche, a longtemps souffert d'algorithmes trop lents pour être utilisé en pratique. Je présenterai le premier test du raisonnement énergétique dont le temps d'exécution est sous-quadratique: O(n log^2 n). Je présenterai aussi l'algorithme de filtrage associé à ce test qui s'exécute en O(n^2 log n).

Biographie : Claude-Guy Quimper est professeur agrégé au département d'informatique et de génie logiciel à l’Université Laval. Ses recherches portent sur la programmation par contraintes, la recherche opérationnelle, la conception d'algorithmes et l'ordonnancement. Diplômé au doctorat de l'Université de Waterloo, il a été visiteur chez NICTA et stagiaire chez Microsoft Research. Il a fait un postdoctorat à Polytechnique Montréal sous la supervision du professeur Gilles Pesant. Il a travaillé dans l'industrie chez Oméga Optimisation, avec Louis-Martin Rousseau, et chez Google.

Bienvenue à tous!

© École Polytechnique de Montréal
Bottin | Plan du site | Recherche | Conditions | Besoin d'aide?