Les lundis, à partir de 14h - UPEC CMC - Salle P2-131

14 mars 2022

Une méthode générique d’amélioration de stratégie pour les jeux stochastiques simples.

Yann Strozecki (UVSQ, laboratoire DAVID)

Les jeux stochastiques simples sont des jeux à deux joueurs, avec du hasard et à information parfaite. Deux joueurs déplacent à tour de rôle un jeton sur un graphe dans le but d’atteindre chacun un puits différent. L’objectif est de trouver le couple de stratégies optimales.

Trouver ce couple est relativement difficile : on ne connaît aucun algorithme polynomial ou quasi polynomial, contrairement aux jeux de parité, même si le problème n’est pas NP-complet (sous hypothèse de complexité).

Les algorithmes de résolution se rangent principalement dans trois catégories : programmation quadratique, propagation de valeur, et amélioration de stratégies.

On présente dans cet exposé un méta-algorithme qui généralise tous les algorithmes d’améliorations de stratégies connus. Cela nous permet de redémontrer facilement la correction de ces algorithmes, de supprimer certaines hypothèses ainsi que de donner de meilleures bornes de complexité.

24 janvier 2022

TBA

Nathan Grosshans (Universität Kassel)

15 novembre 2021

tba

Mahsa Shirmohammadi (IRIF)

18 octobre 2021

TBA

Olivier Bournez (Lix)

27 septembre 2021

Du process mining à la prédiction de parcours.

Emmanuelle Claeys (IRIT)

Après une introduction au process mining (définition, type de données, représentations communes) sera présenté le lien entre process maps et réseaux de Petri dans un contexte de fouille de processus.

Nous présenterons ensuite l’algorithme Actitrac et l’algorithme K-means pour de la clusterisation de process avant de présenter une approche hybride. Cette présentation conclura sur la capacité des ces méthodes à générer de bonnes prédictions à partir de données réelles, ainsi que sur leurs limites.