2019


Retour à la vue des calendrier
Jeudi 5 Septembre
Heure: 12:15 - 13:30
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Redescription en analyse de données : exemples variés.
Description: François Rioult Le thème général de cette présentation est la redescription des données
dans un espace où elles peuvent être prises en charge par des techniques
éprouvées d'apprentissage automatique. Par exemple, pour prédire un
événement dans une séquence, on peut la recoder comme succession de
motifs fermés. D'autres exemples seront abordés, comme la transformation
d'un ensemble de règles en un graphe, de trajectoires de joueurs d'une
équipe en trajectoire d'un polygone, ou encore d'un spectre sonore en
image pour de la classification en deep learning.
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.