Abstract (FR)

Les théories mathématiques en épidémiologie ont adopté l'usage de réseaux d'interactions pour modéliser la propagation d'une épidémie au sein d'une population de nœuds qui sont en contact s'ils sont reliés par une arête. Bien que des avancées majeures aient été réalisées pour concevoir des contre-mesures efficaces qui agissent directement sur les maladies, peu d'études en comparaison ont été effectuées pour tenter de modifier le réseau d'interaction lui-même. Cette thèse étudie la possibilité de trouver une modification optimale d'un réseau de manière à stopper une épidémie qui s'y propagerait. Ce problème d'optimisation étant difficile du point de vue la théorie de la complexité, nous proposons un algorithme probabiliste d'approximation qui est garanti de produire une modification stoppant l'épidémie en un temps limité. De plus, nous montrons que l'analyse du ratio d'approximation de cet algorithme est la meilleure possible pour un large ensemble d'instances. Pour mesurer l'utilité pratique d'un tel algorithme, nous procédons à une analyse critique des méthodologies actuelles en évaluation expérimentale des algorithmes. En réponse, nous proposons une nouvelle méthodologie pour étudier des implantations d'algorithmes produisant des solutions potentiellement inexactes, sous-optimales et dont le comportement dépend de paramètres.