2019


Retour à la vue des calendrier
Mardi 17 Septembre
Heure: 12:30 - 13:30
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Algorithmes auto-stabilisants
Description: Lélia Blin Dans le contexte des réseaux à grande échelle, la prise en compte des pannes est une nécessité. L'auto-stabilisation est une approche algorithmique de la tolérance aux pannes dans les systèmes distribués dont le but est de gérer la corruption de la mémoire des processeurs dues à des pannes transitoires. Plusieurs paramètres caractérisent l'efficacité d'un algorithme auto-stabilisant, dont en particulier (1) le temps pris par le système pour retourner dans une configuration légale suite à une corruption arbitraire de la mémoire de ses processeurs, et (2) l'espace mémoire utilisé par les processeurs pour exécuter l'algorithme. La minimisation de l'espace mémoire est motivée pas de nombreux aspects : existence de réseaux (tels que les réseaux de capteurs) offrant des espaces mémoires limités, la minimisation des échanges de données entre processeurs voisins, la limitation du stockage d'information afin de pouvoir utiliser des techniques de redondance, etc. Ce séminaire présentera l'auto-stabilisation au travers deux grands problèmes classiques : la construction d'arbres couvrants, notamment d'arbres couvrants de poids minimum, et l'election d'un leader. Il présentera en particulier les liens entre auto-stabilisation et les techniques de décision distribuée, incluant le calcul de bornes inférieures sur l'espace mémoire nécessaire à la résolution par des algorithmes auto-stabilisants des problèmes susmentionnés.
Mardi 24 Septembre
Heure: 12:30 - 13:30
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Quelques problèmes d'optimisation dans les réseaux
Description: Cedric Bentz J'évoquerai dans cet exposé quelques problèmes d'optimisation dans les réseaux auxquels je me suis intéressé, parfois en collaboration avec d'autres chercheurs, depuis quelques années. Dans certaines des variantes étudiées, les réseaux considérés peuvent être sujets aux pannes, ce qui
peut nécessiter d'en tenir compte lors de la conception de tels réseaux.

La première famille de problèmes étudiés tourne autour de généralisations du problème de multicoupe, prenant notamment en compte le fait que le bon fonctionnement d'un réseau peut être mis en cause même si seul un certain nombre des communications à assurer sont affectées, pour lesquelles des résultats de complexité paramétrée ont été récemment obtenus dans différents cas particuliers.

La seconde famille tourne autour de problèmes de d-bloqueurs dans les graphes, dans lesquels on s'intéresse au nombre minimum de noeuds (sommets) ou de liens (arêtes) qui doivent tomber en panne pour que, intuitivement, le réseau descende en-dessous d'un certain seuil de fonctionnement. Plusieurs résultats de complexité notables ont ainsi été obtenus pour cette catégorie de problèmes, dont on ne sait souvent même pas déterminer facilement s'ils sont dans NP ou non.

Enfin, la troisième et dernière famille tourne autour de problèmes d'arbres et de réseaux de Steiner, en présence de capacités, et dans certains cas de pannes. Concernant le problème d'arbre de Steiner avec capacités sur les arcs mais sans pannes, les résultats de complexité qui ont été obtenus permettent d'obtenir une caractérisation complète de la complexité de ce problème vis-à-vis de plusieurs paramètres. Concernant le problème de conception de réseaux de Steiner avec capacités et pannes, plusieurs formulations le modélisant, dont une formulation biniveau, ont été obtenues et comparées entre elles, de façon théorique comme expérimentale, et quelques inégalités permettant de les renforcer ont également été testées. Ces formulations peuvent toutes être adaptées au cas où l'on ajoute la possibilité de protéger un certain nombre de liens du réseau, mais un fait notable et pas nécessairement intuitif est que les relations entre les formulations diffèrent alors du cas précédent.
Mercredi 25 Septembre
Heure: 14:00 - 15:00
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Brzozowski and Antimirov reordering derivatives
Description: Tarmo Uustalu The Brzozowski and Antimirov derivatives are effective operations on regular expressions that calculate the (semantic) derivatives of a regular language. They yield constructions of finite deterministic and nondeterministic automata.

In this talk, I show how these operations on regular expressions admit natural generalizations for trace closures of regular languages, which are languages obtained from a regular language by allowing some pairs of letters to commute.

The automata from the Brzozowski and Antimirov reordering derivatives are generally not finite. But if the regular expression is star-connected or, more generally, if its language has uniform rank, they are.

This is joint work with Hendrik Maarand.

I will also give a short introduction to what we do in my groups in
Tallinn and Reykjavik.
Lundi 30 Septembre
Heure: 12:30 - 13:30
Lieu: Salle C316
Résumé: Détection de la radicalisation sur les réseaux sociaux
Description: Frédérique Segond Dans ce séminaire je présenterai le travail effectué dans le cadre du projet européen Saffron pour détecter la radicalisation sur les réseaux sociaux. Après avoir présenté la problématique et l’approche multidisciplinaire adoptée, je me focaliserai sur la description des modules d’analyse sémantique, en particulier sur le module d’extraction d’événements. J’illustrerai mon propos avec les difficultés rencontrées et parlerai de la difficulté d’évaluer un tel travail. Je conclurai en présentant les perspectives actuelles de ce travail par rapport à des projets en cours et à la plateforme MediaCentric développée chez Bertin IT.
Jeudi 3 Octobre
Heure: 12:15 - 13:30
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Optimal Transport for Machine Learning
Description: Bernard Kamsu-Foguem Optimal transport defines a set of geometric tools with interesting properties (comparison and morphology of probability measurements) that make it particularly suitable for solving large scale artificial learning problems.
Since probability distributions are omnipresent in Machine Learning (ML), whether theoretical or empirical, optimal transport can be useful in order to measure their separation or, even better, to be able to transform them at a lower cost.
We will investigate techniques based on optimal transport in certain practical and theoretical contexts (text classification, multi-label classification and domain adaptation), to contribute to solving the associated Machine Learning (ML) problems.