La combinatoire de Coxeter-Catalan est très jeune. Elle s'est développée dans les deux dernières décennies en lien avec des phénomènes combinatoires reliés aux nombres de Catalan. Entre autres, elle permet d'interpréter certains résultats de la théorie des algèbres amassées, une théorie très vivante ces dernières années. En 2007, N. Reading a donné une interprétation combinatoire des générateurs des algèbres amassées - les amas - à l'aide des groupes de Coxeter et certains éléments - appelés éléments triés - ayant des propriétés combinatoires particulières. Le présent texte rassemble les notions essentielles sur les groupes de Coxeter et la combinatoire sous-jacente, afin de démontrer l'interprétation de N. Reading et d'illustrer certaines conséquences de celle-ci. Tout en introduisant les notions, une attention particulière est accordée à la perspective actuelle des résultats et au cheminement de ceux-ci. Le texte est parsemé d'images pour un apport visuel accru. Celles-ci ont été réalisées à l'aide de la librairie TikZ de LATEX. ______________________________________________________________________________

Mémoire d'orthophonie : Médecine : Université de Nantes : 2007. / Bibliogr.

Th. 3e cycle--Inform.--Lille 1, 1978. N°: 735.

Dans ce mémoire, nous présentons quelques facettes de l'étude statistique des plans par regroupement, qui nous ont paru particulièrement représentatives. Comme on rencontre les méthodologies faisant appel aux plans par regroupement surtout en génétique, nommément en génétique expérimentale, où du reste ces méthodologies s'y révèlent remarquablement adéquates, nous présentons d'abord en le chapitre l, en guise de préalable à la suite du mémoire, un certain nombre d'éléments de génétique et, en particulier, nous y présentons la notion de sonde, qui est en quelque sorte une « constante », puisque cette notion est sous-jacente à toutes les méthodologies que nous présentons ici, au sens où, plus précisément, cette notion est centrale dans ce qui motive toutes ces méthodologies. Dans le chapitre 2, nous présentons le concept de complexe simplicial. Ce concept a ceci de remarquable qu'il donne lieu à des plans par regroupement grâce auxquels on peut déterminer tous les éléments positifs à partir de la donnée des groupes positifs. Nous introduisons ensuite dans le chapitre 3 une nouvelle espèce de structures, à savoir l'espèce des plans ordonnés. Nous en déduisons ensuite une formule pour l'espérance du nombre d'éléments négatifs indéterminés dans le cas des plans par regroupement ordinaires. Nous présentons aussi une méthode, que nous qualifions d'ensembliste, pour la détermination de probabilités toujours dans le cas des plans ordonnés. Nous pensons avoir détecté une faille dans le cours du raisonnement de l'auteur de cette méthode et en proposons une solution de rechange. Dans le chapitre 4, nous présentons une méthode d'estimation de l'espérance d'un certain estimateur du nombre d'éléments positifs, estimateur que nous y définissons, pour une classe particulière de plans par regroupement, à savoir la classe des plans hypercubiques. Nous présentons ensuite différentes facettes de la mise en application de l'estimateur de Monte Carlo de l'espérance de cet estimateur-là. Cette mise en application nous permet finalement dans le chapitre 5 d'obtenir des tables d'estimations de cet estimateur pour différentes valeurs des paramètres de cette classe de plans, et pour différentes valeurs du paramètre de la loi de probabilité associée. ______________________________________________________________________________ MOTS-CLÉS DE L’AUTEUR : Génomique, Complexe simplicial, Plan par regroupement, Plan ordonné, Plan hypercubique.

Cette thèse porte sur des problèmes d'exploration de données avec le point de vue de la recherche opérationnelle. L'exploration de données consiste en l'apprentissage de nouvelles connaissances à partir d'observations contenues dans une base de données. La nature des problèmes rencontrés dans ce domaine est proche de celle des problèmes de la recherche opérationnelle: grandes instances, objectifs complexes et difficulté algorithmique. L'exploration de données peut aussi se modéliser comme un problème d'optimisation avec un objectif partiellement connu. Cette thèse se divise en deux parties. La première est une introduction à l'exploration de données. Elle présente l'Analyse Combinatoire de Données (ACD), une méthode d'exploration de données issue de l'optimisation discrète. Cette méthode est appliquée à des données médicales originales et une extension aux problèmes d'analyse de temps de survie est proposée. L'analyse de temps de survie consiste à modéliser le temps avant un événement (typiquement un décès ou une rechute). Les heuristiques proposées utilisent des techniques classiques de recherche opérationnelle telles que la programmation linéaire en nombres entiers, la décomposition de problème, des algorithmes gloutons. La seconde partie est plus théorique et s'intéresse à deux problèmes combinatoires rencontrés dans le domaine de l'exploration de données. Le premier est un problème de partitionnement de graphes en sous-graphes denses pour l'apprentissage non supervisé. Nous montrons la complexité algorithmique de ce problème et nous proposons un algorithme polynomial basé sur la programmation dynamique lorsque le graphe est un arbre. Cet algorithme repose sur des résultats de la théorie des couplages. Le second problème est une généralisation des problèmes de couverture par les tests pour la sélection d'attributs. Les lignes d'une matrice sont coloriées en deux couleurs. L'objectif est de trouver un sous-ensemble minimum de colonnes tel que toute paire de lignes avec des couleurs différentes restent distinctes lorsque la matrice est restreinte au sous-ensemble de colonnes. Nous montrons des résultats de complexité ainsi que des bornes serrées sur la taille des solutions optimales pour différentes structures de matrices. / This thesis focuses on some data mining problems with an operations research point of view. Data mining is the process of learning new knowledge from large datasets. The problems in this field are close to the ones encountered in operations research: Large instances, complex objectives and algorithmic difficulty. Moreover, learning knowledge from a dataset can be viewed as a particular optimization problem with a partially known objective function. This thesis is divided into two main parts. The first part starts with an introduction to data mining. Then it presents a specific method from the field of discrete optimization known as Logical Analysis of Data (LAD). In this part, an original medical application and an extension of LAD to survival analysis are presented. Survival analysis is the modeling of time to event (typically death or failure). The proposed heuristics are derived from classical operations research methods such as integer programming, problem decomposition and greedy algorithms. The second part is more theoretical and focuses on two combinatorial problems encountered while solving practical data mining problems. The first one is a problem of graph partition into dense subgraphs for unsupervised learning. We emphasize the algorithmic complexity of this problem, and give a polynomial algorithm based on dynamic programming when the graph is a tree. This algorithm relies on famous combinatorial optimization results in matching theory. The second problem is a generalization of test cover for feature selection. The rows of a binary matrix are bicolored. The objective is to find a minimum subset of columns such that any pair of rows with different colors are still distinct when the matrix is restricted to the subset of columns. We give complexity results and tight bounds on the size of the optimal solutions for various matrix structures.

Cette thèse porte sur des problèmes d'exploration de données avec le point de vue de la recherche opérationnelle. L'exploration de données consiste en l'apprentissage de nouvelles connaissances à partir d'observations contenues dans une base de données. La nature des problèmes rencontrés dans ce domaine est proche de celle des problèmes de la recherche opérationnelle: grandes instances, objectifs complexes et difficulté algorithmique. L'exploration de données peut aussi se modéliser comme un problème d'optimisation avec un objectif partiellement connu. Cette thèse se divise en deux parties. La première est une introduction à l'exploration de données. Elle présente l'Analyse Combinatoire de Données (ACD), une méthode d'exploration de données issue de l'optimisation discrète. Cette méthode est appliquée à des données médicales originales et une extension aux problèmes d'analyse de temps de survie est proposée. L'analyse de temps de survie consiste à modéliser le temps avant un événement (typiquement un décès ou une rechute). Les heuristiques proposées utilisent des techniques classiques de recherche opérationnelle telles que la programmation linéaire en nombres entiers, la décomposition de problème, des algorithmes gloutons. La seconde partie est plus théorique et s'intéresse à deux problèmes combinatoires rencontrés dans le domaine de l'exploration de données. Le premier est un problème de partitionnement de graphes en sous-graphes denses pour l'apprentissage non supervisé. Nous montrons la complexité algorithmique de ce problème et nous proposons un algorithme polynomial basé sur la programmation dynamique lorsque le graphe est un arbre. Cet algorithme repose sur des résultats de la théorie des couplages. Le second problème est une généralisation des problèmes de couverture par les tests pour la sélection d'attributs. Les lignes d'une matrice sont coloriées en deux couleurs. L'objectif est de trouver un sous-ensemble minimum de colonnes tel que toute paire de lignes avec des couleurs différentes restent distinctes lorsque la matrice est restreinte au sous-ensemble de colonnes. Nous montrons des résultats de complexité ainsi que des bornes serrées sur la taille des solutions optimales pour différentes structures de matrices.

Tableau d’honneur de la Faculté des études supérieures et postdoctorales, 2010-2011 / Une description des états Virasoro dans les modules irréductibles de plus haut poids des modèles minimaux M (p, p') en théorie des champs conformes est fournie par les chemins RSOS. Ces chemins sont issus des configurations des hauteurs sur une rangée du réseau des modèles statistiques exactement résolubles RSOS lors de l'évaluation de la probabilité locale d'une hauteur dans le régime III. Une seconde catégorie de chemins, définis sur un réseau demi-entier, a été proposée et élevée au rang de conjecture comme une description alternative des états Virasoro pour les modèles M (p, 2p + 1). L'avantage de cette seconde catégorie de chemins réside dans la formulation du poids qui ne dépend plus de la hauteur. L'analyse combinatoire de ces derniers est suffisamment simple pour permettre d'obtenir leurs fonctions génératrices qui sont, en vertu de la conjecture, équivalentes aux formules de caractères pour ces modèles minimaux. En nous intéressant davantage à ces chemins sur réseau demi-entier, nous avons découvert qu'il est également possible de les utiliser pour décrire les états Virasoro des modèles M (p + 1.2p+ 1). Nous présentons l'analyse combinatoire pour cette nouvelle classe ainsi que la dérivation des fonctions génératrices. Nous montrons également comment relier les chemins sur réseau demi-entier aux chemins RSOS au moyen d'une bijection qui préserve le poids. Par conséquent, nous validons la conjecture sur l'équivalence des chemins sur réseau demi-entier et des états Virasoro pour tous les modèles minimaux M(p + e, 2p-rl), e = 0,1.

L'étude du domaine récent que constituent les problèmes d'optimisation combinatoires probabilistes (POCPs) forme le sujet de cette thèse. Les POCPs sont des généralisations des problèmes d'optimisation combinatoires classiques dont les formulations contiennent explicitement des éléments probabilistes. Plusieurs motivations ont provoqué cette étude. Deux d'entre elles sont particulièrement importantes. La première correspond au désir de formuler et d'analyser des modèles qui sont plus appropriés pour des problèmes pratiques pour lesquels l'aléatoire est une source constante de préoccupations, les modèles de nature probabiliste sont plus particulièrement attractifs comme abstraction mathématique des systèmes réels. La seconde motivation est d'analyser la stabilité des solutions optimales des problèmes déterministes lorsque les exemplaires sont perturbés : les perturbations sont simulées par la présence ou l'absence de sous-ensembles des données. Notre étude s'appuie sur certains de ces problèmes et en particulier : problème du voyageur de commerce; problème d'ordonnancement des travaux probabiliste et le problème du bin-packing probabiliste. Les questions soulevées et les résultats obtenus sont dans les domaines suivants : complexités des problèmes et analyse d'heuristiques pour les POCPs ; analyse du comportement asymptotique des problèmes lorsque les exemplaires correspondent à des problèmes de grandes tailles ; dégager une méthodologie générale d'étude de la stabilité des solutions des problèmes d'optimisation combinatoires classiques.

Ce travail est la synthèse de travaux de recherches en mathématiques, dont les thèmes sont empruntés à la géométrie algébrique, la combinatoire analytique et les probabilités. La première partie concerne les variétés algébriques complexes de dimension trois. On y présente un calcul de la cohomologie singulière de variétés toriques lisses non complètes, ainsi que la construction d'un modèle toroïdal des singularités-quotient, dont le calcul nécessite l'étude combinatoire fine de l'action des groupes finis de matrices unitaires sur le plan projectif. La deuxième partie développe une adaptation "hybride" de la méthode de Darboux et de l'analyse des singularités pour le développement asymptotique des coefficients d'une série entière dans certains cas de frontière naturelle d'analyticité. De nombreux exemples issus de l'analyse combinatoire sont ainsi traités, dont celui de l'analyse d'algorithmes de factorisation de polynômes sur les corps finis qui sont utilisés en calcul formel et pour les codes correcteurs d'erreurs. La troisième partie résout une conjecture sur les arbres $m$-aires de recherche qui sont une structure fondamentale de l'algorithmiques des ensembles de données. Le modèle considéré est un modèle d'urnes qui se généralise en la notion de processus aléatoires de Pòlya dont le comportement asymptotique général est étudié. Dans la quatrième partie, on construit un arbre aléatoire associé à la \emph{Chaos Game Representation} utilisée en bio-mathématique et en bio-informatique du génôme. Les asymptotiques de la hauteur et de la profondeur d'insertion de ces arbres y sont établies.

Cette recherche visait à étudier le potentiel des transformations de représentation sémiotique d´enregistrements dans une analyse combinatoire de la proposition de l´enseignement intégré sur la résolution pour les étudiants de 2e année de l´école secondaire problème. Le cadre théorique de cette recherche a été liée à l´enseignement et l´apprentissage des cours de mathématiques en utilisant la Représentation Sémiotique registres, les niveaux de connaissance attendus des étudiants et de dépannage. Pour le développement de cette étude ont été utilisés aspects méthodologiques de génie didactique. L´analyse a été développé à partir d´un point de vue qualitatif. Participé à cette étude, les élèves de la deuxième année de l´école secondaire de la State College Victoire de Santa Maria à Aracaju / SE. Il a été prouvé dans l´application de la séquence d´enseignement que l´enseignement basé sur les leçons de l´expérience qui stimule la mobilisation des dossiers sémiotiques et les activités liées à la quotidienne de l´étudiant a contribué efficacement à l´enseignement et l´apprentissage de l´analyse combinatoire. / A presente pesquisa teve como objetivo geral investigar o potencial das transformações dos registros de representação semiótica em uma proposta de ensino de Análise Combinatória construída com base na resolução de problemas para alunos da 2º série do ensino médio. O referencial teórico desta investigação esteve relacionado com o processo de ensino e aprendizagem da disciplina matemática, utilizando os Registros de Representação Semiótica, Níveis de conhecimento esperados dos estudantes e Resolução de Problemas. Para o desenvolvimento desse estudo foram utilizados aspectos metodológicos da Engenharia Didática. A análise se desenvolveu numa perspectiva qualitativa. Participaram dessa pesquisa os alunos da segunda série do ensino médio do Colégio Estadual Vitória de Santa Maria em Aracaju/SE. Ficou comprovado na aplicação da sequência didática que o ensino baseado em experiências de aulas que estimule a mobilização dos registros semióticos e com atividades relacionadas ao cotidiano do discente contribuiu de forma efetiva para o ensino e a aprendizagem de Análise Combinatória.