Mardi 8 Janvier
Heure: |
12:30 - 13:30 |
Lieu: |
Salle B107, bâtiment B, Université de Villetaneuse |
Résumé: |
Aller-retour et voyageur de commerce dans les réseaux de transports urbain |
Description: |
Pierre Parent Le problème de l'aller-retour se pose lorsque l'on dispose d'un véhicule personnel, et que l'on peut faire une partie du trajet à l'aide de celui-ci, et le restant via les transports en communs. Il s'agit alors de trouver quel trajet choisir à l'aller et au retour, pour minimiser le temps total, sachant que si la voiture est garée à un endroit à l'aller on doit passer la rechercher à ce même endroit au retour.
Dans le problèmes de voyageur de commerce nous avons un certain nombre d'endroit à visiter en ville, et il s'agit de trouver le trajet optimal passant par tout ces points en utilisant les transports en commun. La difficulté réside dans le fait que les trains, arrivent et partent à des heures fixées de la journée.
Nous proposerons des méthodes de résolution pour les deux problèmes, ainsi que des résultats expérimentaux. |
Mardi 15 Janvier
Heure: |
14:00 - 17:00 |
Lieu: |
Salle B107, bâtiment B, Université de Villetaneuse |
Résumé: |
Génération aléatoire de permutations alternées |
Description: |
Philippe Marchal Désiré André (dans son article de 1879) a montré que le développement en série de tan(x) et sec(x) est lié à une jolie suite combinatoire, les nombres Eulériens, qui comptent le nombre de permutations alternées.J'introduis un nouvel algorithme, basé sur des idées de théorie des probabilités,qui permet d'engendrer une telle permutation de longueur n en temps n log n.Je montrerai que l'idée peut aussi s'étendre à d'autres classes de permutations contraintes. |
Jeudi 24 Janvier
Heure: |
12:30 - 13:30 |
Lieu: |
Salle B107, bâtiment B, Université de Villetaneuse |
Résumé: |
Analyse de données temporelles |
Description: |
Ahlame Douzal Mes travaux de recherche portent sur l'analyse de données temporelles et s'articulent en trois parties : -la représentation de séries temporelles, -la définition de métriques et leur apprentissage, -ainsi que la proposition de nouvelles approches de classification dédiées aux séries temporelles. Le déploiement de statistiques d'autocorrélation spatiale sur des structures de contiguïté particulières, telle que temporelle, met en évidence des propriétés intéressantes. Elles permettent, par exemple, d'appréhender le comportement des séries (aléatoire, chaotique), d'évaluer le niveau de saillance d'un événement, ou de mesurer la dépendance locale ou globale entre une structure évolutive et les observations associées. Ces propriétés ont guidé nos principaux travaux.Ainsi, notre première contribution concerne la représentation compacte de séries multivariées. Nous avons étudié une approche de réduction de la dimension temporelle de séries multivariées, par segmentation, préservant les corrélations inférées par la série ; l'identification de segments saillants étant guidée par la variance locale. Dans la deuxième partie de notre travail, nous nous sommes intéressé à la définition de métriques intégrant la composante forme des séries et leur positionnement dans un cadre plus général. L'alignement de séries étant un concept fondamental dans la définition de métriques, notre intérêt a porté, ensuite, sur l'apprentissage de couplages pour la discrimination de classes de séries complexes. L'approche proposée vise à lier les séries selon les caractéristiques communes au sein des classes et différentielles entre les classes. Le couplage ainsi appris permet de dériver une métrique locale pondérée restreignant la comparaison des séries aux attributs discriminants. Enfin, le troisième volet de nos travaux est dédié à l'extension des arbres de classification/régression à des variables prédictives temporelles. L'arbre temporel de classification proposé recours à un nouveau critère de coupure fondé sur une métrique adaptative et la localisation de sous-séquences discriminantes. |
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. |
Lundi 4 Février
Heure: |
00:59 - 15:00 |
Lieu: |
Salle B107, bâtiment B, Université de Villetaneuse |
Résumé: |
Séquences fréquentes maximales et applications |
Description: |
Antoine Doucet Une séquence d'items (par exemple, des mots, ou des caractères), est définie par l'ordre dans lequel ces items apparaissent dans un document, indépendamment de la distance qui les y sépare. Une séquence est dite fréquente, si elle apparaît dans plus de documents qu'un seuil de fréquence documentaire donné. Elle est dite maximale dès lors que l'insertion de tout autre item induit une fréquence inférieure au seuil. Appliquées par exemple au niveau phrastique, les séquences fréquentes maximales (SFM) forment ainsi des descripteurs compacts, qui ne sont ni limités en taille, ni par la distance les séparant dans le corpus initial. Je détaillerai tout d'abord notre méthode non supervisée permettant l'extraction et la sélection efficace de séquences fréquentes maximales depuis des corpus de texte de toute taille, quel qu'en soit le genre, et quelle qu'en soit la langue. Je présenterai ensuite plusieurs applications de ces travaux, notamment en extraction de synonymes, utilisant les SFM comme pivots d'alignement de paraphrases. J'aborderai également nos applications en recherche d'information multilingue, en veille épidémiologique multilingue et en détection de nouveauté dans des flux de dépêches d'agence de presse. |
Mardi 5 Février
Heure: |
10:30 - 13:30 |
Lieu: |
Salle B107, bâtiment B, Université de Villetaneuse |
Résumé: |
Inversion de Lagrange multivariée |
Description: |
Axel Bacher |
Heure: |
12:30 - 13:30 |
Lieu: |
Salle B107, bâtiment B, Université de Villetaneuse |
Résumé: |
Separable non-convex underestimators for binary quadratic programming |
Description: |
Emiliano Traversi We present a new approach to constrained quadratic binary programming. Dual bounds are computed by choosing appropriate global underestimators of the objective function that are separable but not necessarily convex. Using the binary constraint on the variables, the minimization of this separable underestimator can be reduced to a linear minimization problem over the same set of feasible vectors. For most combinatorial optimization problems, the linear version is considerably easier than the quadratic version. We explain how to embed this approach into a branch-and-bound algorithm and present experimental results. |
Heure: |
14:00 - 17:00 |
Lieu: |
Salle B107, bâtiment B, Université de Villetaneuse |
Résumé: |
La conjecture de Hadamard |
Description: |
Shalom Eliahou< |
Mardi 12 Février
Heure: |
10:00 - 13:00 |
Lieu: |
Salle B107, bâtiment B, Université de Villetaneuse |
Résumé: |
Journée en l'honneur du départ à la retraite de Pierre Nicodème : accueil |
Description: |
Pierre Nicodème |
Heure: |
10:30 - 13:30 |
Lieu: |
Salle B107, bâtiment B, Université de Villetaneuse |
Résumé: |
Computer algebra for the enumeration of lattice walks |
Description: |
Alin Bostan |
Heure: |
11:30 - 14:30 |
Lieu: |
Salle B107, bâtiment B, Université de Villetaneuse |
Résumé: |
Newton iteration in computer algebra and combinatorics |
Description: |
Bruno Salvy |
Heure: |
14:30 - 17:30 |
Lieu: |
Salle B107, bâtiment B, Université de Villetaneuse |
Résumé: |
Some patterns in Pierre Nicodème's works |
Description: |
Julien Clément |
Mardi 19 Février
Heure: |
12:30 - 13:30 |
Lieu: |
Salle B107, bâtiment B, Université de Villetaneuse |
Résumé: |
Discrete optimization using semidefinite methods |
Description: |
Angelika Wiegele Many real-world applications, although being non-linear, can be well described by linearized models. Therefore, Linear Programming (LP) became a widely studied and applied technique in many areas of science, industry and economy. Semidefinite Programming (SDP) is an extension of LP. A matrix-variable is optimized over the intersection of the cone of positive semidefinite matrices with an affine space. It turned out, that SDP can provide significantly stronger practical results than LP. Since then SDP turned out to be practical in a lot of different areas, like combinatorial optimization, control theory, engineering, and more recently in polynomial optimization.
In this talk I will present some ideas how to model discrete optimization problems using semidefinite programming in order to obtain semidefinite relaxations. Some of this relaxations proved to be succesful when using in a branch-and-bound framework. Furthermore, I want to present a new idea of how to strengthen semidefinite relaxations.&nbsp; |
Heure: |
14:00 - 17:00 |
Lieu: |
Salle B107, bâtiment B, Université de Villetaneuse |
Résumé: |
Énumeration exacte et asymptotique de pastèques avec barrière |
Description: |
Christian Krattenthaler Le modèle des promeneurs vicieux (sic!)a été introduit par Michael Fisher en mécanique statistique en 1984.De nombreuses variantes ont été étudiées depuis,en particulier celle que je condidère dans mon exposé :lorsque qu'il y a une interaction entre ces promeneurs et un mur.Ce modèle a été originellement proposé par Owczarek, Essam et Brak, qui ont établi quelques résultats partiels.Je montrerai comment complètement déterminer le comportement asymptotiquede la fonction de partition correspondante (et celle d'un autre paramètre pertinent).Nous rencontrerons comme de bien entendu (attendu!) mes chers amis : déterminants, une bijection de tableau et des séries hypergéometriques. |
Jeudi 21 Février
Heure: |
00:59 - 13:30 |
Lieu: |
Salle B107, bâtiment B, Université de Villetaneuse |
Résumé: |
Analyse syntaxique en dépendances et prédiction structurée |
Description: |
Joseph Leroux |
Mardi 26 Février
Heure: |
12:30 - 13:30 |
Lieu: |
Salle B107, bâtiment B, Université de Villetaneuse |
Résumé: |
 Réservation de voies dans un réseau de transport |
Description: |
Feng Chu |
Heure: |
14:00 - 17:00 |
Lieu: |
Salle B107, bâtiment B, Université de Villetaneuse |
Résumé: |
Un petit survol des grands algorithmes de la théorie des graphes, illustrés via le logiciel libre PIGALE |
Description: |
Patrice Ossona de Mendez |
|
|