( ! ) Warning: Declaration of action_plugin_divalign2::register(&$controller) should be compatible with DokuWiki_Action_Plugin::register(Doku_Event_Handler $controller) in /net/www/gmelanco/dokuwiki/lib/plugins/divalign2/action.php on line 0
Call Stack
#TimeMemoryFunctionLocation
10.0002400752{main}( ).../doku.php:0
20.0007402112require_once( '/net/www/gmelanco/dokuwiki/inc/init.php' ).../doku.php:34
30.0226480720Doku_Event_Handler->__construct( ).../init.php:216
40.0253572104plugin_load( ).../events.php:164
50.0253572104Doku_Plugin_Controller->load( ).../pluginutils.php:45
60.0253572152class_exists ( ).../plugincontroller.class.php:95
70.0253572152spl_autoload_call ( ).../plugincontroller.class.php:95
80.0253572152load_autoload( ).../plugincontroller.class.php:95

( ! ) Warning: Declaration of syntax_plugin_divalign2_common::handle($match, $state, $pos, &$handler) should be compatible with DokuWiki_Syntax_Plugin::handle($match, $state, $pos, Doku_Handler $handler) in /net/www/gmelanco/dokuwiki/lib/plugins/divalign2/common.php on line 28
Call Stack
#TimeMemoryFunctionLocation
10.0002400752{main}( ).../doku.php:0
20.0007402112require_once( '/net/www/gmelanco/dokuwiki/inc/init.php' ).../doku.php:34
30.0226480720Doku_Event_Handler->__construct( ).../init.php:216
40.0253572104plugin_load( ).../events.php:164
50.0253572104Doku_Plugin_Controller->load( ).../pluginutils.php:45
60.0253572152class_exists ( ).../plugincontroller.class.php:95
70.0253572152spl_autoload_call ( ).../plugincontroller.class.php:95
80.0253572152load_autoload( ).../plugincontroller.class.php:95
90.0257574696require( '/net/www/gmelanco/dokuwiki/lib/plugins/divalign2/action.php' ).../load.php:140
100.0259575288require_once( '/net/www/gmelanco/dokuwiki/lib/plugins/divalign2/common.php' ).../action.php:12

( ! ) Warning: Declaration of syntax_plugin_divalign2_common::render($mode, &$renderer, $data) should be compatible with DokuWiki_Syntax_Plugin::render($format, Doku_Renderer $renderer, $data) in /net/www/gmelanco/dokuwiki/lib/plugins/divalign2/common.php on line 28
Call Stack
#TimeMemoryFunctionLocation
10.0002400752{main}( ).../doku.php:0
20.0007402112require_once( '/net/www/gmelanco/dokuwiki/inc/init.php' ).../doku.php:34
30.0226480720Doku_Event_Handler->__construct( ).../init.php:216
40.0253572104plugin_load( ).../events.php:164
50.0253572104Doku_Plugin_Controller->load( ).../pluginutils.php:45
60.0253572152class_exists ( ).../plugincontroller.class.php:95
70.0253572152spl_autoload_call ( ).../plugincontroller.class.php:95
80.0253572152load_autoload( ).../plugincontroller.class.php:95
90.0257574696require( '/net/www/gmelanco/dokuwiki/lib/plugins/divalign2/action.php' ).../load.php:140
100.0259575288require_once( '/net/www/gmelanco/dokuwiki/lib/plugins/divalign2/common.php' ).../action.php:12

( ! ) Warning: Cannot modify header information - headers already sent by (output started at /net/www/gmelanco/dokuwiki/lib/plugins/divalign2/common.php:28) in /net/www/gmelanco/dokuwiki/inc/auth.php on line 495
Call Stack
#TimeMemoryFunctionLocation
10.0002400752{main}( ).../doku.php:0
20.0007402112require_once( '/net/www/gmelanco/dokuwiki/inc/init.php' ).../doku.php:34
30.0332745064auth_setup( ).../init.php:224
40.0345756920trigger_event( ).../auth.php:109
50.0345757080Doku_Event->trigger( ).../events.php:238
60.0345757080auth_login_wrapper( ).../events.php:111
70.0345757080auth_login( ).../auth.php:177
80.0345757104auth_logoff( ).../auth.php:265
90.0346757104setcookie ( ).../auth.php:495

( ! ) Warning: preg_match(): Compilation failed: invalid range in character class at offset 5073 in /net/www/gmelanco/dokuwiki/inc/parser/lexer.php on line 118
Call Stack
#TimeMemoryFunctionLocation
10.0002400752{main}( ).../doku.php:0
20.0400847104act_dispatch( ).../doku.php:124
30.0402848040act_export( ).../actions.php:163
40.0402848184p_cached_output( ).../actions.php:671
50.0440849768p_cached_instructions( ).../parserutils.php:128
60.0846865072p_get_instructions( ).../parserutils.php:167
70.0995990360Doku_Parser->parse( ).../parserutils.php:205
80.15021384448Doku_Lexer->parse( ).../parser.php:120
90.15031384472Doku_Lexer->_reduce( ).../lexer.php:407
100.15031384496Doku_LexerParallelRegex->split( ).../lexer.php:553
110.15651398824preg_match ( ).../lexer.php:118
A PCRE internal error occured. This might be caused by a faulty plugin

( ! ) Warning: Declaration of renderer_plugin_latexit::listitem_open($level) should be compatible with Doku_Renderer::listitem_open($level, $node = false) in /net/www/gmelanco/dokuwiki/lib/plugins/latexit/renderer.php on line 38
Call Stack
#TimeMemoryFunctionLocation
10.0002400752{main}( ).../doku.php:0
20.0400847104act_dispatch( ).../doku.php:124
30.0402848040act_export( ).../actions.php:163
40.0402848184p_cached_output( ).../actions.php:671
50.16641382248p_render( ).../parserutils.php:128
60.16641382248p_get_renderer( ).../parserutils.php:634
70.16651382296Doku_Plugin_Controller->load( ).../parserutils.php:689
80.16651382344class_exists ( ).../plugincontroller.class.php:95
90.16651382344spl_autoload_call ( ).../plugincontroller.class.php:95
100.16661382344load_autoload( ).../plugincontroller.class.php:95
110.17221459648require( '/net/www/gmelanco/dokuwiki/lib/plugins/latexit/renderer.php' ).../load.php:140

( ! ) Warning: Cannot modify header information - headers already sent by (output started at /net/www/gmelanco/dokuwiki/lib/plugins/divalign2/common.php:28) in /net/www/gmelanco/dokuwiki/lib/plugins/latexit/renderer.php on line 396
Call Stack
#TimeMemoryFunctionLocation
10.0002400752{main}( ).../doku.php:0
20.0400847104act_dispatch( ).../doku.php:124
30.0402848040act_export( ).../actions.php:163
40.0402848184p_cached_output( ).../actions.php:671
50.16641382248p_render( ).../parserutils.php:128
60.19561587328renderer_plugin_latexit->document_end( ).../parserutils.php:652
70.19631587424header ( ).../renderer.php:396

( ! ) Warning: Cannot modify header information - headers already sent by (output started at /net/www/gmelanco/dokuwiki/lib/plugins/divalign2/common.php:28) in /net/www/gmelanco/dokuwiki/lib/plugins/latexit/renderer.php on line 397
Call Stack
#TimeMemoryFunctionLocation
10.0002400752{main}( ).../doku.php:0
20.0400847104act_dispatch( ).../doku.php:124
30.0402848040act_export( ).../actions.php:163
40.0402848184p_cached_output( ).../actions.php:671
50.16641382248p_render( ).../parserutils.php:128
60.19561587328renderer_plugin_latexit->document_end( ).../parserutils.php:652
70.19641587520header ( ).../renderer.php:397
\documentclass[a4paper, oneside, 10pt]{article} \usepackage[english]{babel} \usepackage[utf8x]{inputenc} \date{\today} \title{} \author{} \begin{document} ====== Master 4TYE814U/4TYE808U MIAGE \& e-MIAGE -- Processus stochastiques et simulation ====== ;;\# "It is a part of probability that many improbabilities will happen." ;;\# ;;\# Aristotle ;;\# ---- ===== Epreuve de TP noté du 07/03/2017 -- Durée : 45 minutes ===== ==== Au début de l'épreuve ==== \_\_**\textless color red/\#efefef\textgreater Dans une fenêtre terminal\textless /color\textgreater **\_\_ * **\textless color red/\#efefef\textgreater Depuis votre répertoire d'accueil\textless /color\textgreater ** * **\textless color red/\#efefef\textgreater Exécutez la commande:\textless /color\textgreater ** **''\textasciitilde{}gmelanco/MIAGe/TP\_note/debut.sh''** * Des fichiers de code seront copiés dans un répertoire de travail. * Ces fichiers de code sont à compléter selon les instructions du sujet. * D'autres fichiers vous permettent de tester votre code. * \textless color red/\#efefef\textgreater Prêtez attention à ne pas déplacer ces fichiers hors du répertoire. La bonne exécution du code exige de garder tous ces fichiers dans un même répertoire.\textless /color\textgreater ---- ==== En fin d'épreuve ==== \_\_**\textless color red/\#efefef\textgreater Dans une fenêtre terminal\textless /color\textgreater **\_\_ * **\textless color red/\#efefef\textgreater Depuis le répertoire où se trouvent les fichiers sur lesquels vous avez travaillé\textless /color\textgreater ** * **\textless color red/\#efefef\textgreater Exécutez la commande:\textless /color\textgreater ** **''\textasciitilde{}gmelanco/MIAGe/TP\_note/fin.sh''** ---- ===== Formation en équipe ===== A l'école (c'était mon cas), les équipes (à la récré) étaient formées de manière relativement démocratique ... Deux "chefs" choisissaient les joueurs à tour de rôle. On peut penser qu'à l'arrivée, les équipes comprenaient, à peu de choses près, une bande de copains -- les liens de camaraderie dominaient. A l'inverse, rivalité oblige, il y avait moins de liens de camaraderie entre les équipes. On se propose de formuler un algorithme pour partager une assemblée de personnes en deux "équipes". Le but, ultimement, sera de proposer des équipes où les liens d'amitiés dominent //dans// les équipes, alors qu'il y en a moins //entre// les deux équipes. ==== Markov simple ==== Penchons-nous d'abord sur un procédé permettant d'explorer //toutes les formations// en deux équipes. ON ne cherche pas pour l'instant à optimiser les formations. On désignera les personnes par des numéros, des entiers de 1 à \$N\$. Une formation en deux équipes est donc une paire ''equipeA, equipeB'' où ''equipeA'' et ''equipeB'' sont des listes de taille \$N/2\$ (où on suppose \$N\$ pair). On peut donc prendre, au départ, la formation: \textless code\textgreater formation = [[i for i in range(nb\_personnes/2)], [i for i in range(nb\_personnes/2, nb\_personnes)]] \textless /code\textgreater où la variable ''nb\_personnes'' a la valeur \$N\$. === Transition === Nous allons considérer une chaîne de Markov permettant d'explorer cet espace des formations. A partir d'une formation = ''equipeA, equipeB'', on "fabriquer" une autre formation en faisant: * On choisit au hasard de manière uniforme (de manière équiproblale) deux nombres \$i, j\$ entre 0 et \$N/2 - 1\$. * On échange les joueurs: le \$i\$ème joueur de l' ''équipe A'', et le \$j\$ème joueur de l' ''équipe B'' changent d'équipe. C'est ce qu'effectue la fonction: \textless code python\textgreater def transition(formation, nb\_personnes): nouv\_formation = formation[0][:], formation[1][:] \# to do \# modifier la copie de la formation reçue en paramètre \# ... return nouv\_formation '\textless /code\textgreater Cette fonction est à implémenter dans le fichier ''Markov\_simple.py''. ---- \textless color red/\#efefef\textgreater Vous utiliserez le code fourni ici comme squelette. Vous retrouverez ce code dans les fichiers qui ont été copiés dans votre répertoire d'accueil. Ne modifiez pas le nom des fichiers au risque de difficultés qui prendront du temps à être ajustées/réparées.\textless /color\textgreater \_\_\textless color red/\#efefef\textgreater Vous préservez le nom des fonctions\textless /color\textgreater \_\_ \textless color red/\#efefef\textgreater et ajoutez votre code dans le corps des fonctions. Vous pouvez bien entendu ajoutez d'autres fonctions si vous le souhaitez.\textless /color\textgreater ---- === Tester votre fonction de transition === Le code suivant doit fonctionner sans problème. La variable ''meme\_equipe'' calcule la proportion de fois où deux équipiers sont membres d'une même équipe. En principe, sa valeur doit être proche de 0.5 (pour de grandes valeurs de la variable ''nb\_pas''). Le code doit fonctionner pour différentes valeurs de la variables ''nb\_personnes''. \textless code python Markov\_simple\_test.py\textgreater \# -*- coding:utf-8 -*- import random from Markov\_simple import * nb\_personnes = 50 formation = [[i for i in range(nb\_personnes/2)], [i for i in range(nb\_personnes/2, nb\_personnes)]] nb\_pas = 100000 meme\_equipe = 0.0 for i in range(nb\_pas): equipeA = formation[0] equipeB = formation[1] if (21 in equipeA and 34 in equipeA) or (21 in equipeB and 34 in equipeB): meme\_equipe += 1 formation = transition(formation, nb\_personnes) print 'Proportion deux equipiers dans l\textbackslash{}'equipe A: ', meme\_equipe / nb\_pas print '(Lorsque nb\_pas est grand, la valeur affichee doit etre proche' print 'et osciller autour de 0.5, *quels que soient* les deux équipiers choisis.)' \textless /code\textgreater ---- ==== Algorithme de Metropolis ==== Nous allons maintenant chercher à faire un bon choix de formation. On suppose connaître le réseau social (des liens de camaraderie) entre les personnes. \{\{ :miage:reseau\_social\_camarades.png?direct\&500 |\}\} --- Un package ''Utils'' permet de charger le réseau social. Il positionne aussi des variables ''nb\_personnes'' et ''nb\_liens'' total de camaraderie dans le réseau. La variable ''reseau'' contient la description des liens dans le réseau. \textless code python\textgreater \# -*- coding:utf-8 -*- from Utils import * reseau, nb\_personnes, nb\_liens = charger\_reseau() \textless /code\textgreater La fonction de transition de l'algorithme de Metropolis cherchera à favoriser les bonnes formations: celles où le nombre de liens //internes// aux équipes est le plus grand possible. Il faut donc pouvoir calculer combien de liens sont //internes// aux équipes. Nous allons procéder \_\_ainsi\_\_: * On calculera d'abord combien de liens sont //externes//. Un lien de camaraderie est //externe// lorsqu'il lie deux personnes qui ne sont pas de la même équipe. \textless code\textgreater equipeA = formation[0] equipeB = formation[1] nb\_liens\_externes = 0.0 pour chaque personne pA dans equipeA pour chaque personne pB dans equipeB si pA est liée à pB nb\_liens\_externes += 1.0 \textless /code\textgreater en sortie de boucle, la variable ''nb\_liens\_externes'' contient le nombre de liens externes dans le réseau (par rapport à la formation donnée). Le nombre de liens //internes// est égal à: \textless code\textgreater nb\_liens\_internes = nb\_liens - nb\_liens\_externes\textless /code\textgreater Vous disposez déjà de la fonction (dans le package ''Utils''): \textless code\textgreater def sont\_liees(personne1, personne2)\textless /code\textgreater où ''personne1'' et ''personne2'' sont des entiers entre 0 et ''nb\_personnes - 1''. --- Il vous faut construire la fonction: \textless code python\textgreater def nb\_liens\_externes(formation): global nb\_liens equipeA = etat[0] equipeB = etat[1] nb\_liens\_ext = 0.0 \# to do \# ... return nb\_liens\_ext def nb\_liens\_internes(formation): global nb\_liens return nb\_liens - nb\_liens\_externes(formation) \textless /code\textgreater --- La //distribution cible// de l'algorithme de Metropolis doit donc être basée sur le ratio ''nb\_liens\_internes''/''nb\_liens''. \textless code python\textgreater def distribution\_cible(formation): global nb\_liens \# to do \# ... return ... \# valeur associée à la formation \textless /code\textgreater === Transition et Metropolis === Reste à construire la fonction qui effectue la transition comme dicté par l'algorithme de Metropolis. \textless code python\textgreater def transitionMetropolis(formation): \# to do \# ... \textless /code\textgreater L'ensemble de ces fonctions est à implémenter dans le fichier ''Markov\_Metropolis.py''. ---- === Tester votre code: algorithme de Metropolis === Ce fichier doit pouvoir s'exécuter sans problème. Il charge le code des fonctions des second et premier fichier et effectue une marche aléatoire selon la transition de Metropolis et la distribution cible que vous aurez définie. Les résultats doivent permettre de vérifier que tout se passe bien, que l'algorithme tente de trouver ue solution optimale au déplacement des bulldozers. \textless code python\textgreater \# -*- coding:utf-8 -*- import random from Utils import * from Markov\_simple import * from Markov\_Metropolis import * reseau, nb\_personnes, nb\_liens = charger\_reseau() formation = [[i for i in range(nb\_personnes/2)], [i for i in range(nb\_personnes/2, nb\_personnes)]] nb\_pas = 100 meme\_equipe = 0.0 for i in range(nb\_pas): equipeA = formation[0] equipeB = formation[1] equipier1 = 1 equipier2 = 2 if (equipier1 in equipeA and equipier2 in equipeA) or (equipier1 in equipeB and equipier2 in equipeB): meme\_equipe += 1 formation = transitionMetropolis(formation, nb\_personnes) print 'Proportion deux equipiers dans l\textbackslash{}'equipe A: ', meme\_equipe / nb\_pas print '(Lorsque nb\_pas est grand, la valeur affichee doit etre proche' print 'de 0.0 pour des personnes "eloignees" l\textbackslash{}'une de l\textbackslash{}'autre dans le reseau,' print 'et plus elevee pour des personnes "proches".)' \textless /code\textgreater --- [[miage:processus\_stoch\_simulation|Retour à la page d'accueil du cours]] --- [[miage:processus\_stoch\_simulation|Retour à la page d'accueil du cours]] \end{document}