User Tools

Site Tools


Sidebar

* [[http://www.labri.fr/perso/melancon|Me as a researcher]] --- * [[start|Home]] * [[proj_techno:start|Projets technologiques - Licence 3 Informatique]] 4TIN601U * [[proj_CMI_L2:start|Projet de programmation - CMI ISI]] 4TCM401U * [[MIAGE:processus_stoch_simulation|Processus stochastiques et simulation - MIAGE et e-MIAGE]] 4TYE814U / 4TYE808U ---- * **Fête de la Science** - [[mathc2+:analyse|"Analyse de réseau appliquée aux réseau sociaux"]] ---- * Master U de Bx * [[http://www.labri.fr/perso/melancon/Visual_Analytics_Course/|Visual Analytics]] * [[e-miage_ubx_i|e-MIAGE U de Bx]] * [[estia:estia|ESTIA DataViz / Data Science]] * [[Enseignements passés]] ---- * [[http://www.labri.fr/perso/melancon|Research]] ---- * [[admin:Site admin]]

A PCRE internal error occured. This might be caused by a faulty plugin
miage_epreuve:interro_finale_c

====== Master 4TYE814U/4TYE808U MIAGE & e-MIAGE -- Processus stochastiques et simulation ====== ;;# "It is a part of probability that many improbabilities will happen." ;;# ;;# Aristotle ;;# ---- ===== Sujet type de contrôle continu du 28/02/2017 ===== //Il va sans dire qu'une réponse non justifiée n'a que peu de valeur ...// ==== Bulldozers ==== Une société de location de matériel de chantier rencontre systématiquement le même problème chaque semaine et cherche une solution pouvant l'aider à minimiser le coût qui y est associé. En début de semaine, elle doit décider du déplacement de bulldozers quittant leurs chantiers pour être implantés sur d'autres chantiers qui débutent. Chacun des $n$ bulldozers, laissés sur des (\emph{a}nciens) chantiers $a_1, a_2, \ldots, a_n$ doivent être amenés sur les \emph{p}rochains chantiers $p_1, p_2, \ldots, p_n$. Les coûts de transport de ces machines, facturé au kilomètres parcourus, doit être tenu au minimum. On va noter par $\rho$ (la lettre grecque ``rho'' qui correspond au ``r'' latin, pour \emph{r}éaffectation) une réaffectation. C'est une fonction $i \mapsto \rho(i)$ qui code le fait que le bulldozer sur l'ancien chantier $a_i$ doit être affecté au nouveau chantier $p_{\rho(i)}$. Cette fonction est une \emph{permutation} des entiers $\{1, 2, \ldots, n\}$. Les distances entres les sites $a_1, a_2, \ldots, a_n$ et $p_1, p_2, \ldots, p_n$ entrent donc en jeu. Le but de cet exercice est d'élaborer une méthode pouvant trouver une solution acceptable au problème posé, applicable en toute généralité (quelle que soit la valeur de $n$, et les distances entre les sites). On notera $d(\rho)$ la distance associé à la réaffectation $\rho$ (la somme des distances $\sum_{i=1}^n d(a_i, p_{\rho(i)}$) de tous les déplacements des bulldozers impliqués par cette réaffectation). --- 1. Donnez un algorithme qui permet de parcourir //toutes// les réaffectations possibles des bulldozers afin de trouver une solution de coût minimum (nombre de kilomètres parcourus). --- Nous allons construire un procédé qui, pour éviter de parcourir toutes les solutions, permet au moins de choisir une solution au hasard, en faisant ce choix uniformément parmi toutes les solutions possibles (toutes les solutions ont la même probabilité d'être choisies). On considère une chaîne de Markov dont //les états sont les réaffectations// $\rho, \rho', \rho'', \ldots$ possibles des bulldozers sur les nouveaux chantiers. 2. Combien d'états possède cette chaîne (pour $n = 3, 4, \ldots$ et en toute généralité) ? 3. On considère la fonction de transition suivante. Supposons donnée une réaffectation $\rho$ des bulldozers. * On choisit au hasard deux des bulldozers (sur deux anciens sites $a_i$, $a_j$). * On considère la réaffectation $\rho'$ définit par $\rho'(i) = \rho(j)$ et $\rho'(j) = \rho(i)$, et $\rho'(k) = \rho(k)$ si $k \not = i,j$. * En d'autres mots $\rho'$ envoie les bulldozers là où les envoyait $\rho$ sauf pour les bulldozers des chantiers $a_i, a_j$. Pour ceux-là, elle inverse la réaffectation qui était préconisé par $\rho$. Avec quelle probabilité passe t-on de l'état $\rho$ à l'état $\rho'$ ? 4. Quelle est une distribution stationnaire de cette chaîne ? Est-elle unique ? (Justifiez votre réponse) --- On peut maintenant se servir de cette chaîne de Markov, et la modifier à l'aide de l'algorithme de Metropolis pour tenter de trouver une solution qui optimise la réaffectation des bulldozers. 5. Donner une distribution cible pour laquelle la probabilité va décroissante en fonction de la distance associé à une réaffectation (plusieurs choix sont possibles). 6. Donnez la fonction de transition défini par l'algorithme de Metropolis qui permet de converger vers la distribution cible. ---- ==== chifoumi ==== On se propose d'examiner le jeu de //chifoumi// depuis la théorie des chaînes de Markov. En deux mots, on se propose de mettre au point une chaîne de Markov qui piloterait la stratégie de jeu de la machine (jouant contre un utilisateur humain). **chifoumi** (Cherchez sur le net, vous trouverez toute sorte de choses ... il y a une compétition internationale de chifoumi !) Vous vous rappelez ? C'est un jeu à deux joueurs qui se joue en plusieurs manches (souvent en trois manches). A chaque manche, les deux joueurs dévoilent //simultanément// une forme parmi $\{$ //roche//, //papier//, //ciseau// $\}$. Les règles sont simples: //roche// gagne sur //ciseau// (qu'il écrase), //ciseau// gagne sur //papier// (qu'il coupe) et //papier// gagne sur //roche// (qu'il enveloppe et isole). Si les deux joueurs jouent la même forme, la manche est nulle et est rejouée. 1. Proposez une chaîne de Markov qui permet de piloter le jeu d'une machine. * Quels états ? * Quelles transitions ? * Comment utilisez-vous la chaîne de Markov pour faire jouer la machine ? Pour jouer avec la machine, un joueur décide d'abord du coup qu'il joue, puis le saisit. Puis, la machine joue à son tour -- bien entendu, sans regarder ce que l'humain a joué ! [[miage_epreuve:solution_chifoumi1|Solution]] --- Imaginons maintenant que le jeu se déroule sans fin (on joue un grand nombre de manches). 2. Discutez de l'impact des valeurs choisies pour les probabilités de transition de la chaîne sur la stratégie de jeu de la machine et sur les chances pour l'utilisateur humain de sortir vainqueur du jeu. En d'autres mots, si l'humain sait que la machine joue en utilisant une chaîne de Markov, comment peut-il en profiter pour augmenter ses chances de gagner ? Donnez une méthode systématique (un algorithme) qui permet d'apprendre la stratégie de la machine pour sortir gagnant. Faites appel aux résultats du cours pour //argumenter// votre raisonnement. ---- ==== Rat Race ==== On place un rat de laboratoire dans un "labyrinthe" (décrit par la figure). Si le rat se trouve dans une case, il peut se déplacer dans une case voisine comme l'indique les cloisons. Le rat se déplace parmi les cases en changeant de case aléatoirement à chaque top d'horloge; cependant, lorsqu'il est dans la case 1 du labyrinthe, il y reste jusqu'au prochain top d'horloge avec probabilité 0.2. {{ miage:ratmaze.jpg?direct&300 |}} On place, au départ, le rat dans une case choisit au hasard. On s'intéresse à la case où on peut trouver le rat: si on le laisse trotter pendant un moment, a t-on plus de chance de le retrouver plutôt la case du centre, dans un coin, dans la case 1 ? Bien évidemment, oh ! surprise, nous allons modéliser cette situation à l'aide d'une chaîne de Markov. 1. Précisez les états de cette chaîne de Markov. 2. Donnez sa matrice de transition. 3. Dessinez le graphe de cette chaîne. 4. La chaîne permet-elle de répondre à notre interrogation ? Quel résultat nous permet de l'affirmer ? * Donnez une réponse chiffrée à cette question. 5. Et si au départ, on plaçait systématiquement le rat dans la case du centre ? Quelle(s) hypothèse(s) modifie t-on ? et avec quel impact sur notre prédiction ? --- [[miage:processus_stoch_simulation|Retour à la page d'accueil du cours]]

miage_epreuve/interro_finale_c.txt · Last modified: 2017/03/07 09:56 by melancon