La recherche que nous avons menée s'inscrit dans les projets de l'équipe de recherche Maths à Modeler. En particulier dans celui portant sur les situations de recherche en classe (Grenier et Payan, 2002 ; Ouvrier-Buffet, 2003 ; Godot, 2005 ; Cartier, 2008). Cette étude est centrée sur la démarche de recherche en mathématiques et plus particulièrement sur le rôle de l'expérimental. Un des postulats fondateur de notre recherche est que savoir faire des mathématiques, c'est savoir résoudre partiellement des problèmes de recherche, la résolution de tels problèmes nécessitant de passer par des phases expérimentales. Notre problématique porte donc sur la transmission aux élèves du savoir-faire « démarche expérimentale en mathématiques » et sur le rôle que celui-ci joue dans la résolution de problèmes de recherche. Considérant que ce savoir-faire ne peut s'apprendre qu'à travers sa pratique en situation de résolution de problèmes, l'objectif de notre recherche a été la détermination de conditions épistémologiques et didactiques favorisant la mise en pratique de la « démarche expérimentale ». En plus de la construction d'un modèle de situation pour la « démarche expérimentale », nous avons construit, analysé et expérimenté des situations se référant à ce modèle. Pour mener à bien notre étude, nous avons utilisé le modèle de situation de recherche pour la classe (Grenier et Payan, 2002 ; Godot, 2005), ainsi que des éléments de la théorie des situtions didactiques de Brousseau (1998), en particulier validation a-didactique, contrat didactique et milieu. Nous avons aussi défini un modèle de « démarche expérimentale en mathématiques » qui a servi de référant à notre recherche. Après avoir observé que la « démarche expérimentale en mathématiques », telle que nous l'entendons, n'est pas proposée par l'institution scolaire, les expérimentations et les analyses, que nous avons menées, ont montré que, dans une certaine mesure, il est possible de la faire pratiquer à des élèves. De plus, cette pratique a permis aux élèves de progresser dans la résolution grâce à un enrichissement des conceptions qu'ils portaient sur le problème à résoudre. Ces expérimentations nous ont aussi permis d'affiner les situations que nous avons construites. / This research fits into the projects of the Maths à Modeler research team, especially in the one about Research Situation for the Classroom (Grenier and Payan, 2002 ; Ouvrier-Buffet, 2003 ; Godot, 2005 ; Cartier, 2008). One of our founding postulate is that knowing how to do mathematics is knowing how to solve partially reserch problems, the solving of such problems requiring experimental phases. Our problematic is about the teaching of the knowledge "experimental approach in mathematics" and the role that this knowledge plays in solving research problems. As we consider that this knowledge can only be learned by its practise, the aim of our research is the identification of epistemological and didactical conditions favouring the practise of the experimental approach in mathematics. Along with the building of a model of "situations" for the experimental approach, we built, analysed and experimented situations which refer to the model. We used the model of Research Situation for the Classroom (Grenier and Payan, 2002 ; Godot, 2005) and elements of the theory of didactical situation (Brousseau, 1998), especially a-didactical validation, didactical contract and "milieu". We have also defined a model of "experimental approach in mathematics" which was used as a "guide" of our research. After observing that "the experimental approach in mathematics", as we defined it, is not proposed by schools, experimentations and analyses showed that, in a certain way, students can do experimental approach in mathematics. Moreover, this practise let students progress in finding solutions thanks to the improvement of their conceptions about the problem. These experimentations also let us refined the situations that we have built.

Ce mémoire présente quelques résultats récents sur les codes identifiants. La thèse est structurée en cinq chapitres. Le Chapitre 1 contient les définitions et présente la notion de code identifiant. Dans le Chapitre 2 nous étudions l'aspect algorithmique des codes identifiants. Le Chapitre 3 contient quelques résultats concernant des classes de graphes particulières, à savoir les hypercubes, les grilles, et les cycles. Nous étudions quelques questions extrémales au Chapitre 4. Enfin, le Chapitre 5 présente quelques résultats récents sur les codes identifiants dans les graphes aléatoires. A la fin du document nous résumons les résultats les plus importants que nous avons présentés et nous donnons quelques problèmes ouverts sur le sujet.

La recherche que nous avons menée s'inscrit dans les projets de l'équipe de recherche Maths à Modeler. En particulier dans celui portant sur les situations de recherche en classe (Grenier et Payan, 2002 ; Ouvrier-Buffet, 2003 ; Godot, 2005 ; Cartier, 2008). Cette étude est centrée sur la démarche de recherche en mathématiques et plus particulièrement sur le rôle de l'expérimental. Un des postulats fondateur de notre recherche est que savoir faire des mathématiques, c'est savoir résoudre partiellement des problèmes de recherche, la résolution de tels problèmes nécessitant de passer par des phases expérimentales. Notre problématique porte donc sur la transmission aux élèves du savoir-faire " démarche expérimentale en mathématiques " et sur le rôle que celui-ci joue dans la résolution de problèmes de recherche. Considérant que ce savoir-faire ne peut s'apprendre qu'à travers sa pratique en situation de résolution de problèmes, l'objectif de notre recherche a été la détermination de conditions épistémologiques et didactiques favorisant la mise en pratique de la " démarche expérimentale ". En plus de la construction d'un modèle de situation pour la " démarche expérimentale ", nous avons construit, analysé et expérimenté des situations se référant à ce modèle. Pour mener à bien notre étude, nous avons utilisé le modèle de situation de recherche pour la classe (Grenier et Payan, 2002 ; Godot, 2005), ainsi que des éléments de la théorie des situtions didactiques de Brousseau (1998), en particulier validation a-didactique, contrat didactique et milieu. Nous avons aussi défini un modèle de " démarche expérimentale en mathématiques " qui a servi de référant à notre recherche. Après avoir observé que la " démarche expérimentale en mathématiques ", telle que nous l'entendons, n'est pas proposée par l'institution scolaire, les expérimentations et les analyses, que nous avons menées, ont montré que, dans une certaine mesure, il est possible de la faire pratiquer à des élèves. De plus, cette pratique a permis aux élèves de progresser dans la résolution grâce à un enrichissement des conceptions qu'ils portaient sur le problème à résoudre. Ces expérimentations nous ont aussi permis d'affiner les situations que nous avons construites.

Les travaux présentés dans ce document traitent des codes identifiants dans les graphes. Cette notion, introduite à la fin des années 1990, modélise des problèmes de détection de défaillance dans les réseaux. Un code identifiant peut être vu comme une variante du problème de domination, avec une contrainte supplémentaire d'identification des sommets. La recherche de la cardinalité minimum d'un tel code est un problème NP-difficile. Les résultats obtenus sont regroupés en quatre grands thèmes. Le premier thème concerne les structures régulières (grilles, cycles, hypercubes, produits de cliques, graphes de Sierpiński), pour lesquels des résultats sur la cardinalité minimum d'un code sont présentés (bornes et valeurs exactes). Ensuite, les aspects algorithmiques sont développés, que ce soit au sujet de la recherche d'algorithmes polynomiaux pour des classes de graphes particulières (arbres, fasciagraphes) ou concernant l'approximabilité du problème. Quelques questions structurelles sont ensuite discutées, notamment la construction de graphes extrémaux pour le problème, la construction de familles de graphes admettant un code identifiant de faible cardinalité, et la structure (degrés, sous-graphes, etc.) des graphes admettant un tel code. Enfin, une nouvelle variante de ces codes est présentée, les codes identifiants adaptatifs. Cette variante permet de modéliser une situation où nous pouvons tirer parti de l'aspect dynamique du problème, et espérer interroger un nombre de sommets bien moins grand que dans le cas statique. Nous explicitons en particulier dans ce document les liens qu'entretiennent les codes identifiants avec d'autres types de structures, tels les ensembles dominants, les codes superposés, les plans projectifs, ou les jeux de Rényi.

L'image des mathématiques répandue dans notre société semble bien loin de la pratique effective de cette discipline. Mais alors, qu'est-ce que faire des mathématiques? qu'est-ce que chercher en mathématiques? Comment amener tout un chacun, élève ou grand public, à devenir un apprenti chercheur en mathématiques?<br />Nous pensons que répondre à ces questions peut être une aide pour que les mathématiques ne soient plus reconnues comme socialement problèmatiques, pour leur donner du sens aux yeux de chacun. Or, quel que soit le niveau scolaire, chercher en mathématiques n'est pas un apprentissage réellement formalisé dans l'institution scolaire, très peu d'outils étant disponibles. Alors comment faire ?<br />C'est dans ce but que l'erté Maths à modeler a été mise en place. Issue de la collaboration entre chercheurs en mathématiques discrètes et didacticiens, elle cherche à proposer à tous, élève ou grand public, de découvrir ce que peut être la recherche en mathématiques par le biais d'outils spécifiques: les situations recherche. La recherche s'y effectue de préférence en groupe, sur des problèmes facilement abordables, issus de questions de recherche et non nécessairement résolues! Il ne s'agit donc pas de trouver le bon outil mais de le construire, de se mettre dans la peau du chercheur et de fabriquer, de modeler la résolution même partielle du problème et cela sans pré requis mathématiques particulier si ce n'est savoir compter et réfléchir!<br />Dans le cadre de ma thèse, je m'intéresse plus particulièrement aux situations recherche dans lesquelles les problèmes sont présentés sous forme de jeu et par le biais d'un support matériel, afin de faciliter la rencontre entre public et mathématiques. Un des objectifs de ma recherche est d'étudier et de formaliser les savoirs en jeu (point de vue épistémologique), les apprentissages induits (point de vue didactique) dans de telles situations et les conditions de leur émergence, que ce soit à l'école (du primaire à l'université) ou sur le temps des loisirs (atelier régulier, Fête de la science...), afin de permettre une utilisation des situations Maths à modeler dans un cadre de formation et de vulgarisation.

Construire des définitions est essentiel dans l'activité de recherche mathématique et interagit dialectiquement avec la formation de concepts. La recherche présentée dans cette thèse s'est intéressée à la double question : est-il possible de faire émerger un concept, auprès d'étudiants, par des problèmes de construction de définitions, et quels sont les apprentissages en jeu ? La complexité des SCD et l'absence de l'étude de telles situations jusqu'alors nous a conduit au développement d'outils théoriques (du triple point de vue : mathématique, épistémologique et didactique) en vue de les construire, de les réaliser en classe et de les analyser. Ces outils théoriques nous ont permis d'établir une typologie des SCD, d'étudier les conceptions sur la définition chez des philosophes et des mathématiciens, d'analyser la place et le rôle des définitions dans les institutions didactiques, et d'extraire de possibles SCD de quelques travaux didactiques existants relatifs au concept de définition. Nous avons ainsi pu mener une étude des conditions pour la dévolution de telles situations, fondée sur des résultats d'expérimentations menées avec des étudiants de 1ère année d'université. Le choix des situations expérimentées relève de la typologie des SCD établie. Les concepts mathématiques en jeu ont été choisis pour leur accessibilité et leur position institutionnelle particulière : le concept d'arbre (qui vient d'entrer dans les programmes de lycée), les concepts de "générateur" et "libre" dans le plan discret (qui peuvent être considérés comme étant "en amont" des ceux des espaces vectoriels), et l'objet géométrique "droite discrète" (que l'on peut référer à la droite réelle). La variété des situations et concepts mathématiques étudiés nous permet, d'une part, de mieux cerner les conceptions sur la définition les plus répandues chez les enseignants et les étudiants et, d'autre part, d'attester la mise en oeuvre de processus de construction de définitions et de concepts. L'ensemble des résultats développés dans cette thèse devrait permettre d'élaborer des SCD, pour l'enseignement secondaire ou supérieur.

Nous nous intéressons dans cette thèse à différents types de réseaux (optiques, sans-fil, pair-à-pair) ayant chacun leurs spécificités mais partageant des problématiques communes : assurer la meilleure qualité de services possible, garantir la stabilité du système, minimiser les ressources et donc le coût de fonctionnement. Tout d'abord, nous étudions le problème de la reconfiguration du routage dans les réseaux optiques consistant à rerouter les requêtes de connexion en minimisant les perturbations pour les utilisateurs. Puis, nous nous intéressons au problème de la détermination de routages efficaces en énergie dans les réseaux coeur. Pour ce faire, nous étudions le problème de trouver des routages minimisant le nombre d'équipements utilisés. Ensuite, nous nous intéressons aux algorithmes d'ordonnancement des liens dans les réseaux sans-fil en présence d'interférence. Enfin, nous considérons le problème de stockage de données dans les réseaux pair-à-pair. Nous étudions l'impact de différentes politiques de placement sur la durée de vie des données et nous déterminons un choix de placement optimal. Pour résoudre ces problèmes, nous utilisons les outils théoriques des mathématiques discrètes (graphes, configurations, optimisation combinatoire), d'algorithmique (complexité, algorithmique distribuée) et de probabilités.

Les résultats obtenus dans cette thèse portent principalement sur l'étude des "communications dans les réseaux optiques par multiplexage en longueur d'onde". Ils s'inscrivent dans une thématique d'allocation des ressources en vue de réaliser des communications dans un réseau. La problématique générale que nous avons considérée peut se résumer de la manière suivante. Il s'agit de satisfaire dans un réseau optique une famille de requêtes de connexion, appelée instance de communication et formée de couples de noeuds (source, destination). La satisfaction d'une requête passe par l'attribution d'un chemin dans le réseau et d'une longueur d'onde sur les liens utilisés, avec la contrainte que deux requêtes ne peuvent pas utiliser le même lien avec la même longueur d'onde. L'objectif dans ce cadre est de minimiser l'utilisation des ressources optiques, c'est-à-dire le nombre total de longueurs d'onde permettant de satisfaire l'instance donnée. Dans le chapitre 1, nous présentons la technologie optique pour les télécommunications, afin de préciser le cadre technique de notre recherche et d'aider le lecteur informaticien à la compréhension des contraintes physiques sous-jacentes à la modélisation théorique. Dans le chapitre 2, nous posons la problématique étudiée au cours de la thèse et nous donnons la modélisation qui a servi de base à nos recherches. Le chapitre 3 est une synthèse des résultats obtenus dans la littérature concernant principalement le problème du routage optique. Le reste de la thèse est constituée des annexes qui rassemblent les articles publiés, dans le format des rapports de recherche.

Cette thèse s'intéresse à différents types d'interactions entre les cliques et les stables, deux objets très importants en théorie des graphes, ainsi qu'aux relations entre ces différentes interactions. En premier lieu, nous nous intéressons au problème classique de coloration de graphes, qui peut s'exprimer comme une partition des sommets du graphe en stables. Nous présentons un résultat de coloration pour les graphes sans triangles ni cycles pairs de longueur au moins 6. Dans un deuxième temps, nous prouvons la propriété d'Erdös-Hajnal, qui affirme que la taille maximale d'une clique ou d'un stable devient polynomiale (contre logarithmique dans les graphes aléatoires) dans le cas des graphes sans chemin induit à k sommets ni son complémentaire, quel que soit k.Enfin, un problème moins connu est la Clique-Stable séparation, où l'on cherche un ensemble de coupes permettant de séparer toute clique de tout stable. Cette notion a été introduite par Yannakakis lors de l’étude des formulations étendues du polytope des stables dans un graphe parfait. Il prouve qu’il existe toujours un séparateur Clique-Stable de taille quasi-polynomiale, et se demande si l'on peut se limiter à une taille polynomiale. Göös a récemment fourni une réponse négative, mais la question se pose encore pour des classes de graphes restreintes, en particulier pour les graphes parfaits. Nous prouvons une borne polynomiale pour la Clique-Stable séparation dans les graphes aléatoires et dans plusieurs classes héréditaires, en utilisant notamment des outils communs à l'étude de la conjecture d'Erdös-Hajnal. Nous décrivons également une équivalence entre la Clique-Stable séparation et deux autres problèmes  : la conjecture d'Alon-Saks-Seymour généralisée et le Problème Têtu, un problème de Satisfaction de Contraintes. / This thesis is concerned with different types of interactions between cliques and stable sets, two very important objects in graph theory, as well as with the connections between these interactions. At first, we study the classical problem of graph coloring, which can be stated in terms of partioning the vertices of the graph into stable sets. We present a coloring result for graphs with no triangle and no induced cycle of even length at least six. Secondly, we study the Erdös-Hajnal property, which asserts that the maximum size of a clique or a stable set is polynomial (instead of logarithmic in random graphs). We prove that the property holds for graphs with no induced path on k vertices and its complement.Then, we study the Clique-Stable Set Separation, which is a less known problem. The question is about the order of magnitude of the number of cuts needed to separate all the cliques from all the stable sets. This notion was introduced by Yannakakis when he studied extended formulations of the stable set polytope in perfect graphs. He proved that a quasi-polynomial number of cuts is always enough, and he asked if a polynomial number of cuts could suffice. Göös has just given a negative answer, but the question is open for restricted classes of graphs, in particular for perfect graphs. We prove that a polynomial number of cuts is enough for random graphs, and in several hereditary classes. To this end, some tools developed in the study of the Erdös-Hajnal property appear to be very helpful. We also establish the equivalence between the Clique-Stable set Separation problem and two other statements: the generalized Alon-Saks-Seymour conjecture and the Stubborn Problem, a Constraint Satisfaction Problem.