|
|
 |
|
Mardi 4 Mars
| Heure: |
12:00 - 13:30 |
| Lieu: |
Salle B107, bâtiment B, Université de Villetaneuse |
| Résumé: |
Problème de placement orthogonal |
| Description: |
Petru Valicov Etant donné un conteneur rectangulaire C, on s'intéresse à
décider si un ensemble d'items rectangulaires peut être placé sans
chevauchement et sans dépassement des bords de C. Une contrainte
supplémentaire est prise en compte -- l'interdiction de rotation des
items. Ce problème est NP-complet et est un sous-problème du problème de
sac-à-dos orthogonal où à chaque item on associe un profit et on cherche
le sous-ensemble d'items réalisable de profit total maximum. Fekete et
Schepers ont introduit une caractérisation élégante des solutions du
problème de placement en utilisant les graphes d'intervalles. Nous
présentons une nouvelle caractérisation en utilisant des MPQ-arbres --
des structures de données qui encodent efficacement les graphes
d'intervalles. Un des principaux avantages de cette caractérisation est
un nombre plus restreint des solutions symétriques traitées lors de
l'exécution de l'algorithme. Nous finiront par présenter une comparaison
des résultats avec ceux de la littérature sur les jeux de données
connus. Travail effectué en collaboration avec C. Joncour et A. Pêcher. |
| Heure: |
14:00 - 17:00 |
| Lieu: |
Salle B107, bâtiment B, Université de Villetaneuse |
| Résumé: |
Rationality of growth in the Heisenberg groups |
| Description: |
Moon Duchin I'll discuss the history of work on the question of how andwhether rationality of growth depends on generators. That is, for afinitely generated group, one can study the growth function (the number ofwords spellable in up to n letters) and its growth series, the associatedgenerating function. This growth series is itself a rational function whenthere is a recursive relationship among the values of the growth function. It is known that all virtually abelian groups and all hyperbolic groupshave rational growth in any generators, by work of Benson and Cannonrespectively. Work of Shapiro and of Stoll sheds some light on thesituation in nilpotent groups, but shows it to be more complicated-- evenfor the second Heisenberg group H_5, some generators give rational growthbut others do not. I'll describe work in progress with Shapiro givinggeometric arguments to establish rationality in all generators for theclassical Heisenberg group H_3. |
Vendredi 7 Mars
| Heure: |
10:00 - 12:00 |
| Lieu: |
Salle B107, bâtiment B, Université de Villetaneuse |
| Résumé: |
Lambda-calculus and the Invariance Thesis |
| Description: |
Beniamino Accattoli
reasonable λλλλsize
explosion problemλλimpasse usefulβi.e. |
|
|
