Sujet 2: Comparaisons de méthodes pour calculer l'état stationnaire Nous avons identifié trois méthodes pour calculer l'état stationnaire (marche aléatoire et statistique sur la fréquence de passage dans chaque état, itérer la fonction de transition à partir d'un vecteur de proba arbitraire, calculer directement les valeurs propres de la matrice). Évaluez ces différentes méthodes sur: - une ligne, - un anneau, - et une sucette. Pour chaque cas, vous comparerez le temps de calcul et la qualité du résultat des trois méthodes. Vous interpréterez en quoi la forme du graphe influe sur la qualité de la solution.

Sujet 4 : Connexité d’un réseau de capteurs L’objectif de ce sujet est d’évaluer la couverture d’un espace sur lequel on a déposé des capteurs de manière aléatoire.Poursimplifierl’approcheonconsidèrequel’espaceestreprésentéparundisquederayon 1 etque les n capteurs sont répartis selon une loi uniforme sur ce disque. Les capteurs ont une portée de communication θ, c’est à dire que 2 capteurs situés à une distance l’un de l’autre inférieure à θ peuvent échanger des informations. . Q1.Génération du réseau • Écrire un algorithme qui génère n points dans le disque. Calculer la matrice des distances entre les différents capteurs et par suite le graphe de connexion. • Représentez graphiquement trois graphes (d’une taille n de votre choix) afin d’illustrer l’impact de θ sur la structure du graphe. . Q2.Connexité Étudier en fonction de n et de θ la probabilité pc(n,θ) que l’ensemble des capteurs soient connectés (il existe un chemin entre 2 capteurs quelconques). Pour cela tracer pc(n,θ) en fonction de θ pour n = 10,20,100. On estimera l’erreur à l’aide d’intervalles de confiance.