Cette thèse est composée de deux parties : l’une traite des propriétés combinatoires de mots infinis et l’autre des problèmes de colorations des graphes.La première partie du manuscrit concerne les structures régulières dans les mots apériodiques infinis, à savoir les sous-séquences arithmétiques et les premiers retours complets.Nous étudions la fonction qui donne la longueur maximale d’une sous-séquence arithmétique monochromatique (une progression arithmétique) en fonction de la différence commune d pour une famille de mots morphiques uniformes, qui inclut le mot de Thue-Morse. Nous obtenons la limite supérieure explicite du taux de croissance de la fonction et des emplacements des progressions arithmétiques de longueurs maximales et de différences d. Pour étudier des sous-séquences arithmétiques périodiques dans des mots infinis, nous définissons la notion d'indice arithmétique et obtenons des bornes supérieures et inférieures sur le taux de croissance de la fonction donnant l’indice arithmétique dans la même famille de mots.Dans la même veine, une autre question concerne l’étude de deux nouvelles fonctions de complexité de mots infinis basées sur les notions de mots ouverts et fermés. Nous dérivons des formules explicites pour les fonctions de complexité ouverte et fermée pour un mot d'Arnoux-Rauzy sur un alphabet de cardinalité finie.La seconde partie de la thèse traite des colorations parfaites (des partitions équitables) de graphes infinis de degré borné. Nous étudions les graphes de Caley de groupes additifs infinis avec un ensemble de générateurs fixé. Nous considérons le cas où l'ensemble des générateurs est composé d'entiers de l'intervalle [-n, n], et le cas où les générateurs sont des entiers impairs de [-2n-1, 2n+1], où n est un entier positif. Pour les deux familles de graphes, nous obtenons une caractérisation complète des colorations parfaites à deux couleurs / The content of the thesis is comprised of two parts: one deals with combinatorial properties of infinite words and the other with graph coloring problems.The first main part of the manuscript concerns regular structures in infinite aperiodic words, such as arithmetic subsequences and complete first returns.We study the function that outputs the maximal length of a monochromatic arithmetic subsequence (an arithmetic progression) as a function of the common difference d for a family of uniform morphic words, which includes the Thue-Morse word. We obtain the explicit upper bound on the rate of growth of the function and locations of arithmetic progressions of maximal lengths and difference d. To study periodic arithmetic subsequences in infinite words we define the notion of an arithmetic index and obtain upper and lower bounds on the rate of growth of the function of arithmetic index in the same family of words.Another topic in this direction involves the study of two new complexity functions of infinite words based on the notions of open and closed words. We derive explicit formulae for the open and closed complexity functions for an Arnoux-Rauzy word over an alphabet of finite cardinality.The second main part of the thesis deals with perfect colorings (a.k.a. equitable partitions) of infinite graphs of bounded degree. We study Caley graphs of infinite additive groups with a prescribed set of generators. We consider the case when the set of generators is composed of integers from the interval [-n,n], and the case when the generators are odd integers from [-2n-1,2n+1], where n is a positive integer. For both families of graphs, we obtain a complete characterization of perfect 2-colorings

L'étude de la formation et de l'évolution des galaxies est une thématique en pleine effeversence. Deux grands relevés (2dFGRS, SDSS), portant sur plusieurs millions de galaxies proches, ont permis récemment des avancées importantes dans la compréhension des propriétés physiques des galaxies. D'autre part l'arrivée des télescopes de 8-10m de diamètre, équipés de spectroscopes multi-objets (VLT/VIMOS, Keick/DEIMOS, Gemini/GMOS, ...), a permis la mise en place de plusieurs nouveaux grands relevés portant cette fois sur les galaxies lointaines (VVDS, DEEP2, GDDS, zCOSMOS, ...), donc situées dans un univers plus jeune.<br /><br />Ce travail de thèse porte préférentiellement sur l'étude des relations masse-métallicité ou luminosité-métallicité qui permettent d'établir un lien entre les deux processus majeurs responsables de l'évolution des galaxies: l'assemblage de la masse stellaire (formation d'étoiles ou fusion de galaxies) et l'enrichissement chimique du milieu interstellaire par les générations d'étoiles successives. Nous montrons que la forme de cette relation est un très bon test des modèles de formation et d'évolution des galaxies. Nous étudions ensuite la relation luminosité-métallicité de référence obtenue à partir du relevé 2dFGRS dans l'Univers local. Puis nous étudions l'évolution en fonction de l'âge de l'univers de la relation luminosité-métallicité à l'aide d'un petit échantillon (LCL05), puis de la relation masse-métallicité à l'aide du grand relevé VVDS. Plusieurs résultats obtenus avec ces différents échantillons sont des indices en faveur du modèle hiérarchique: les galaxies les plus massives se formeraient par fusion progressive de galaxies plus petites.<br /><br />Les propriétés physiques d'un grand nombre de galaxies sont estimées à l'aide d'outils d'analyse automatiques spécifiquement développés, ou adaptés à nos besoins, durant cette thèse. Comme résultats annexes, de nouvelles calibrations de la classification spectrale ou du taux de formation d'étoiles des galaxies sont obtenues à partir des grands relevés de l'univers local (respectivement 2dFGRS et SDSS). Ce travail offre de nombreuses perspectives de par le nombre et la diversité des données disponibles.

De nombreuses applications en vision par ordinateur nécessitent la distinction et le suivi des différents objets vidéo constituant une scène dynamique. Dans le contexte de la post-production, la qualité visuelle des résultats est une contrainte si forte qu'un opérateur doit pouvoir intervenir facilement et rapidement pour guider efficacement les traitements. Le but de cette thèse est de proposer de nouveaux algorithmes de segmentation au sens du mouvement. Ce document est décomposé en deux parties. Dans la première partie, deux nouvelles méthodes séquentielles et semi-automatiques de segmentation de séquences d'images au sens du mouvement sont proposées. Toutes deux exploitent la représentation d'une scène par un ensemble de couches de mouvement. L'extraction de ces dernières repose sur différents critères (mouvement, couleur, cohérence spatio-temporelle) combinés au sein d'une fonctionnelle d'énergie minimisée par coupe minimale/flot maximal dans un graphe. La seconde partie présente une nouvelle méthode pour le partitionnement automatique d'un ensemble de trajectoires de points d'intérêt. Chaque trajectoire est définie sur un intervalle temporel qui lui est propre et qui correspond aux instants auxquels le point considéré est visible. Comparée à un mouvement estimé entre deux images, l'information de mouvement fournie par une trajectoire offre un horizon temporel étendu qui permet de mieux distinguer des objets dont les mouvements sont différents. Les méthodes sont validées sur différentes séquences aux contenus dynamiques variés.

Nous étudions les fonctions sommatoires des suites digitales. Ces suites sont obtenues en "promenant une fenêtre" sur le développement des entiers en base q, et sont une sous- classe des suites q-régulières. Le comportement asymptotique des fonctions sommatoires est précisé, avec la mise en évidence d'une oscillation "fractale", qui fait intervenir une fonction continue nulle part dérivable. Dans la dernière partie nous nous intéressons à des suites d'entiers à la Cantor, qui s'écrivent dans une base donnée en évitant certains chiffres.

Aujourd’hui, sur le marché, on peut trouver une vaste gamme de produits différents ou des formes variées d’un même produit et ce grand assortiment fatigue les clients. Il est clair que la décision des clients d’acheter un produit dépend de l'aspect esthétique de la forme du produit et de l’affection émotionnelle. Par conséquent, il est très important de comprendre les propriétés esthétiques et de les adopter dans la conception du produit, dès le début. L'objectif de cette thèse est de proposer un cadre générique pour la cartographie des propriétés esthétiques des formes gauches en 3D en façon d'être en mesure d’extraire des règles de classification esthétiques et des propriétés géométriques associées. L'élément clé du cadre proposé est l'application des méthodologies de l’Exploration des données (Data Mining) et des Techniques d’apprentissage automatiques (Machine Learning Techniques) dans la cartographie des propriétés esthétiques des formes. L'application du cadre est d'étudier s’il y a une opinion commune pour la planéité perçu de la part des concepteurs non-professionnels. Le but de ce cadre n'est pas seulement d’établir une structure pour repérer des propriétés esthétiques des formes gauches, mais aussi pour être utilisé comme un chemin guidé pour l’identification d’une cartographie entre les sémantiques et les formes gauches différentes. L'objectif à long terme de ce travail est de définir une méthodologie pour intégrer efficacement le concept de l’Ingénierie affective (c.à.d. Affective Engineering) dans le design industriel. / Today on the market we can find a large variety of different products and differentshapes of the same product and this great choice overwhelms the customers. It is evident that the aesthetic appearance of the product shape and its emotional affection will lead the customers to the decision for buying the product. Therefore, it is very important to understand the aesthetic proper-ties and to adopt them in the early product design phases. The objective of this thesis is to propose a generic framework for mapping aesthetic properties to 3D freeform shapes, so as to be able to extract aesthetic classification rules and associated geometric properties. The key element of the proposed framework is the application of the Data Mining (DM) methodology and Machine Learning Techniques (MLTs) in the mapping of aesthetic properties to the shapes. The application of the framework is to investigate whether there is a common judgment for the flatness perceived from non-professional designers. The aim of the framework is not only to establish a structure for mapping aesthetic properties to free-form shapes, but also to be used as a guided path for identifying a mapping between different semantics and free-form shapes. The long-term objective of this work is to define a methodology to efficiently integrate the concept of Affective Engineering in the Industrial Designing.

La présente thèse a été fortement influencée par deux conjectures, l'une de Gelfond et l'autre de Sarnak.En 1968, Gelfond a prouvé que la somme des chiffres modulo m est asymtotiquement équirépartie dans des progressions arithmétiques, et il a formulé trois problèmes nouveaux.Le deuxième et le troisième problèmes traitent des sommes des chiffres pour les nombres premiers et les suites polynomiales.En ce qui concerne les nombres premiers et les carrés, Mauduit et Rivat ont résolu ces problèmes en 2010 et 2009, respectivement.Drmota, Mauduit et Rivat ont réussi généraliser le résultat concernant la suite des sommes des chiffres des carrés.Ils ont démontré que chaque bloc apparaît asymptotiquement avec la même fréquence.Selon la conjecture de Sarnak, il n'y a pas de corrélation entre la fonction de Möbius et des fonctions simples.La présente thèse traite de la répartition de suites automatiques le long de sous-suites particulières ainsi que d'autres propriétés de suites automatiques.Selon l'un des résultats principaux du présent travail, toutes les suites automatiques vérifient la conjecture de Sarnak.Moyennant une approche légèrement modifiée, nous traitons également la répartition de suites automatiques le long de la suite des nombres premiers.Dans le cadre du traitement de suites automatiques générales, nous avons mis au point une nouvelle structure destinée aux automates finisdéterministes ouvrant une vision nouvelle pour les automates et/ou les suites automatiques.Nous étendons les résultat de Drmota, Mauduit et Rivat concernant les suites digitales.Cette approche peut également être considérée comme une généralisation du troisième problème de Gelfond. / The present dissertation was inspired by two conjectures, one by Gelfond and one of Sarnak.In 1968 Gelfond proved that the sum of digits modulo m is asymptotically equally distributed along arithmetic progressions.Furthermore, he stated three problems which are nowadays called Gelfond problems.The second and third questions are concerned with the sum of digits of prime numbers and polynomial subsequences.Mauduit and Rivat were able to solve these problems for primes and squares in 2010 and 2009 respectively.Drmota, Mauduit and Rivat generalized the result concerning the sequence of the sum of digits of squares.They showed that each block appears asymptotically equally frequently.Sarnak conjectured in 2010 that the Mobius function does not correlate with deterministic functions.This dissertation deals with the distribution of automatic sequences along special subsequences and other properties of automatic sequences.A main result of this thesis is that all automatic sequences satisfy the Sarnak conjecture.Through a slightly modified approach, we also deal with the distribution of automatic sequences along the subsequence of primes.In the course of the treatment of general automatic sequences, a new structure for deterministic finite automata is developed,which allows a new view for automata or automatic sequences.We extend the result of Drmota, Mauduit and Rivat to digital sequences.This is also a generalization of the third Gelfond problem.

Cette thèse est composée d'une partie sur la conjecture des familles stables par unions et de quatre autres chapitres consacrés aux sujets liés aux suites automatiques. Dans la première partie, on donne une condition suffisante pour qu'une version affaiblie de la conjecture soit vraie. On donne aussi un majorant de la fréquence maximale minimale dans une famille de taille $n$. Dans Chapitre 3 on démontre que la formule d'extraction des coefficients des séries algébriques connue pour les corps à caractéristique $0$ est une conséquence d'un théorème de Furstenberg qui permet d'écrire certaines séries algébriques comme les diagonales des fractions rationnelles à deux variables. Comme ce théorème est valide pour tous les corps, la formule l'est aussi. Dans Chapitre 4 on donne une généralisation des résultats de J.-P. Allouche et J. Shallit concernant certains produits infinis et les fonctions qui comptent le nombre d'occurrences d'un facteur dans l'expansion en base $B$ de $n$. Dans Chapitre 5 on donne une construction explicite d'un mot infini avec complexité en facteur de $\Theta(n^t)$ avec la valuation $p$-adique. Dans Chapitre 6 on donne une nouvelle démonstration de la transcendance de la série formelle $L(1,\chi_s)/\Pi$, où $L$ est un analogue des fonctions $L$ de Dirichlet en caractéristique finie défini par D. Goss et $\Pi$ l'analogue de $\pi$ défini par L. Carlitz. / This thesis comprises one part concerning the union-closed sets conjecture and four other chapters dedicated to subjects related to automatic sequences. In the first part, we give a sufficient condition for a weaker version of the conjecture ($\varepsilon$-union closed sets conjecture) to hold. We also give an upper bound of the minimal maximal frequency for a family of size $n$. In Chapter 3 we prove that the coefficient extraction formula for algebraic series known for fields of characteristic $0$ is a consequence of a theorem of Furstenberg that says certains algebraic series can be written as the diagonals of a rational fractions in two variables. As the theorem is true for all fields, so is the formula. In Chapter 4 we give a generalization of the result of J.-P. Allouche and J. Shallit concerning certain infinite products and block-counting functions. In Chapter 5 we give an explicit construction based on $p$-adic valuation of an infinite word with subword complexity $\Theta(n^t)$. In Chapter 6 we give a new proof of the transcendence of the power series $L(1,\chi_s)/\Pi$, where $L$ is an analogue in positive characteristics of Dirichlet $L$ functions defined by D. Goss and $\Pi$ the analogue of $\pi$ defined by L. Carlitz.

Tableau d’honneur de la Faculté des études supérieures et postdoctorales, 2007-2008. / Cette thèse porte sur l'évaluation des résumés automatiques. Ce sujet présente deux problèmes majeurs. Premièrement, la terminologie utilisée dans les évaluations de résumés automatiques comporte de nombreuses lacunes, tant en anglais qu'en français. Plus précisément, un même mot est parfois utilisé pour désigner plus d'un concept et certains concepts ne sont pas dénommés adéquatement. En outre, certains termes sont vagues et certains termes sont inappropriés. Afin de remédier à ce problème, un lexique de vingt-deux termes français pour la présentation des résultats d'évaluation de résumés automatiques a été élaboré. Le deuxième problème est l'absence d'un modèle pour la présentation des résultats d'évaluation de résumés automatiques. Par conséquent, les résultats ne sont pas présentés de la même manière d'un article à l'autre. Qui plus est, de nombreux chercheurs omettent des informations importantes lors de la présentation de leurs résultats d'évaluation, par exemple le nombre de juges qui ont évalué les résumés automatiques. Toutefois, l'élaboration d'un modèle de l'évaluation des résumés automatiques requiert une étude empirique d'assez grande envergure sur le sujet. Dans cette thèse, une analyse approfondie de vingt-sept évaluations de résumés automatiques a été effectuée, ce qui constitue la plus vaste étude jamais conduite sur ce sujet. Lors de cette analyse, toutes les informations pertinentes par rapport au déroulement de l'évaluation ont été retenues dans chacune des vingt-sept expériences du corpus. Ces informations, nommées paramètres expérimentaux, ont été classées en vingt-cinq grandes catégories, plus précisément : 1. quatre paramètres sur les textes sources ; 2. six paramètres sur les résumés automatiques évalués ; 3. sept paramètres sur les résumés de comparaison ; 4. huit paramètres sur les méthodes et les critères d'évaluation. Au terme de l'analyse, quarante-cinq recommandations pour la présentation des résultats d'évaluation de résumés automatiques ont été formulées. Les outils mis en place dans cette thèse, soit la terminologie française, les résultats d'analyse et les recommandations, pourront être utilisés par les chercheurs désirant évaluer leurs résumés automatiques. De plus, ils pourront bientôt être mis à contribution pour le démarrage d'une campagne d'évaluation internationale des résumés automatiques français.

Cette thèse présente le résultat de plusieurs années de recherche dans le domaine de la génération automatique de résumés. Trois contributions majeures, présentées sous la forme d'articles publiés ou soumis pour publication, en forment le coeur. Elles retracent un cheminement qui part des méthodes par extraction en résumé jusqu'aux méthodes par abstraction. L'expérience HexTac, sujet du premier article, a d'abord été menée pour évaluer le niveau de performance des êtres humains dans la rédaction de résumés par extraction de phrases. Les résultats montrent un écart important entre la performance humaine sous la contrainte d'extraire des phrases du texte source par rapport à la rédaction de résumés sans contrainte. Cette limite à la rédaction de résumés par extraction de phrases, observée empiriquement, démontre l'intérêt de développer d'autres approches automatiques pour le résumé. Nous avons ensuite développé un premier système selon l'approche Fully Abstractive Summarization, qui se situe dans la catégorie des approches semi-extractives, comme la compression de phrases et la fusion de phrases. Le développement et l'évaluation du système, décrits dans le second article, ont permis de constater le grand défi de générer un résumé facile à lire sans faire de l'extraction de phrases. Dans cette approche, le niveau de compréhension du contenu du texte source demeure insuffisant pour guider le processus de sélection du contenu pour le résumé, comme dans les approches par extraction de phrases. Enfin, l'approche par abstraction basée sur des connaissances nommée K-BABS est proposée dans un troisième article. Un repérage des éléments d'information pertinents est effectué, menant directement à la génération de phrases pour le résumé. Cette approche a été implémentée dans le système ABSUM, qui produit des résumés très courts mais riches en contenu. Ils ont été évalués selon les standards d'aujourd'hui et cette évaluation montre que des résumés hybrides formés à la fois de la sortie d'ABSUM et de phrases extraites ont un contenu informatif significativement plus élevé qu'un système provenant de l'état de l'art en extraction de phrases. / This Ph.D. thesis is the result of several years of research on automatic text summarization. Three major contributions are presented in the form of published and submitted papers. They follow a path that moves away from extractive summarization and toward abstractive summarization. The first article describes the HexTac experiment, which was conducted to evaluate the performance of humans summarizing text by extracting sentences. Results show a wide gap of performance between human summaries written by sentence extraction and those written without restriction. This empirical performance ceiling to sentence extraction demonstrates the need for new approaches to text summarization. We then developed and implemented a system, which is the subject of the second article, using the Fully Abstractive Summarization approach. Though the name suggests otherwise, this approach is better categorized as semi-extractive, along with sentence compression and sentence fusion. Building and evaluating this system brought to light the great challenge associated with generating easily readable summaries without extracting sentences. In this approach, text understanding is not deep enough to provide help in the content selection process, as is the case in extractive summarization. As the third contribution, a knowledge-based approach to abstractive summarization called K-BABS was proposed. Relevant content is identified by pattern matching on an analysis of the source text, and rules are applied to directly generate sentences for the summary. This approach is implemented in a system called ABSUM, which generates very short and content-rich summaries. An evaluation was performed according to today's standards. The evaluation shows that hybrid summaries generated by adding extracted sentences to ABSUM's output have significantly more content than a state-of-the-art extractive summarizer.

L’objectif majeur de cette thèse a été d’appréhender les conséquences de la comparaison sociale sur l’auto-évaluation implicite et explicite en termes de prudence, les affects et les comportements à risque. Les participants ont été exposés à un standard de comparaison prudent (standard haut) ou imprudent (standard bas) en matière d’alcool. Les résultats montrent que les sujets confrontés au standard haut se perçoivent implicitement plus imprudents et ressentent plus d’anxiété que les sujets exposés au standard bas. En revanche, le standard de comparaison n’influence pas l’auto-évaluation explicite et les comportements contrôlés. Ces résultats témoignent en faveur d’une dissociation entre les processus automatiques (implicites) et contrôlés (explicites) en jeu dans la comparaison sociale. Au niveau appliqué, nos données suggèrent que dans une campagne de prévention il serait potentiellement plus efficace de mettre en scène un standard prudent plutôt que de montrer un preneur de risque. / The main goal of this PhD research was to study the consequences of social comparison on implicit and explicit self-evaluation in terms of cautiousness, on affect and on risk-taking behavior. In a series of studies, participants were exposed to a comparison standard who displayed either cautious (high standard) or reckless (low standard) drinking behavior. Results show that participants confronted with the high standard implicitly perceive themselves as more reckless and experience higher levels of anxiety than participants exposed to the low standard. On the other hand, the comparison standard does not influence explicit self-evaluation and controlled behaviors. These results indicate that there might be a dissociation between automatic (implicit) and controlled (explicit) processes involved in social comparison. On an applied level, regarding alcohol prevention campaigns, our findings suggest that it could be more effective to show a cautious standard rather than a reckless one.