La notion de fonction affine n’est pas disponible (Robert et Rogalski, 2002) pour bon nombre d’élèves malgré un enseignement par les problèmes. Nous avons essaye de comprendre pourquoi et de trouver des pistes pour y remédier. Pour cela, nous avons analyse le savoir enseigne en lien avec épistémologiste de cette notion, évalue les connaissances des élèves a la sortie du collège pour identifier les difficultés qu’ils rencontrent, et expérimenter différentes situations d’apprentissage. Nous avons utilise des outils inspires du cadre de la problématisation (Fabre et Orange, 1997) pour analyser les productions langagières des élèves, comprendre la manière dont ils posent les problèmes lies a l’affinité, comment ils agissent sur les objets et effectuent des changements de cadres (Douady) ou de registres (Duval). Cette étude nous a amené a penser que la disponibilité du savoir est issue d’un double processus : un apprentissage par problématisation de l’outil, un processus de secondarisation du discours. Nous avons fait l’hypothèse qu’une approche de l’affinité par un point de vue global et covariationnel devrait permettre aux élèves de mieux comprendre en quoi la fonction affine peut être un outil de modélisation pour résoudre des problèmes lies a la covariation de deux grandeurs et pense un format de séquence intégrant ces hypothèses par une succession de situations basée sur l’idée d’une problématisation par analyse des productions des élèves (PPAP). L’objectif est de travailler la relation entre l’action et l’objet de savoir. Nous avons expérimenter cette ingénierie afin d’en tirer quelques conditions favorables pouvant servir a l’enseignement des fonctions affines. / For certain pupils, the notion of linear functions is not available in spite of a teaching by problems. We tried to understand why and to find tracks to remedy it. For that purpose, we analyzed the knowledge taught in connection with the epistemology of the notion of affinity, estimated the knowledge of the pupils at the exit of the middle school to identify the obstacles or the difficulties which they meet and experimented various situations of learning. We used tools inspired by the framework of the problematization (Fabre et Orange, 1997) to analyze the linguistic productions of the pupils to understand the way they raise the problems bound to the affinity, how they act on the met objects and how they make changes of frames (Douady) or registers (Duval). This study brought to us to make the hypothesis that the availability of the knowledge arises from a double process: a learning by problematization of the tool, a process of secondarisation of the speech. Besides, an approach of the affinity by a global point of view and covariationnel should allow the pupils to understand better in what the linear functions can be a modelling tool to solve problems bound to the covariation of two quantities measurable. We thought of a format of sequence integrating these various approaches by a succession of situations based on the idea of a problematization by analysis of the productions of the pupils (PPAP) to work the relation between the action and the object of knowledge. We experimented this engineering to reach some favorable conditions which can be of use to the teaching of the linear functions.

Dans cette thèse, nous résolvons la conjecture de Fuglede sur le corps des nombres p-adiques, et étudions certaines propriétés aléatoires des suites liées à la conjecture de Sarnak, ainsi que leur propriétés oscillantes. Dans la première partie, nous prouvons d'abord la conjecture de Fuglede pour des ensembles ouverts compacts dans Q_p. Celle-ci indique qu'un ensemble ouvert compact dans Q_p est un ensemble spectral si et seulement s'il pave Q_p par translation. Il est également prouvé qu'un ensemble ouvert compact est un ensemble spectral (ou une tuile) si et seulement s'il est p-homogène. Nous caractérisons les ensembles spectraux dans Z / p^n Z ( p>1 premier, n>0 entier) par la propriété de pavage et aussi par leur homogénéité. Finalement, nous montrons la conjecture de Fuglede dans Q_p sans la restriction d'être ouvert compact en montrant que tout ensemble spectral ou toute tuile doivent être ouvert et compact à un ensemble de mesure nulle près. Dans la seconde partie, nous donnons d'abord plusieurs définitions équivalentes d'une suite oscillante en termes de disjonction de différents systèmes dynamiques sur des tores. Ensuite, nous définissons la propriété de Chowla et la propriété de Sarnak pour des suites numériques prenant des valeurs 0 ou des nombres complexes de module 1. Nous prouvons que la propriété de Chowla implique la propriété de Sarnak. Il est également prouvé que pour Lebesgue presque tout b> 1, la suite (e^{2 pi b^n})_{n in N} partage la propriété de Chowla et est par conséquent orthogonale à tout système dynamique topologique d'entropie nulle. Nous discutons également si les échantillons d'une suite aléatoire donnée ont presque sûrement la propriété de Chowla. Nous construisons certaines suites aléatoires dépendantes ayant presque sûrement la propriété de Chowla / In this thesis, we solve Fuglede's conjecture on the field of p-adic numbers, and study some randomness and the oscillating properties of sequences related to Sarnak's conjecture. In the first part, we first prove Fuglede's conjecture for compact open sets in the field Q_p which states that a compact open set in Q_p is a spectral set if and only if it tiles Q_p by translation. It is also proved that a compact open set is a spectral set (or a tile) if and only if it is p-homogeneous. We characterize spectral sets in Z/p^n Z (p>1 prime, n>0 integer) by tiling property and also by homogeneity. Finally, we prove Fuglede's conjecture in Q_p without the assumption of compact open sets and also show that the spectral sets (or tiles) are the sets which differ by null sets from compact open sets. In the second part, we first give several equivalent definitions of oscillating sequences in terms of their disjointness from different dynamical systems on tori. Then we define Chowla property and Sarnak property for numerical sequences taking values 0 or complex numbers of modulus 1. We prove that Chowla property implies Sarnak property. It is also proved that for Lebesgue almost every b>1, the sequence (e^{2 pi b^n})_{n in N} shares Chowla property and consequently is orthogonal to all topological dynamical systems of zero entropy. We also discuss whether the samples of a given random sequence have almost surely Chowla property. Some dependent random sequences having almost surely Chowla property are constructed

Les lois de commande affines par morceaux ont attiré une grande attention de la communauté d'automatique de contrôle grâce à leur pertinence pour des systèmes contraints, systèmes hybrides; également pour l'approximation de commandes nonlinéaires. Pourtant, leur mise en oeuvre est soumise à quelques difficultés. Motivé par l'intérêt à cette classe de commandes, cette thèse porte sur leur analyse, mise en oeuvre et synthèse.La première partie de cette thèse a pour but le calcul de la marge de robustesse et de la marge de fragilité pour une loi de commande affine par morceaux donnée et un système linéaire discret. Plus précisément, la marge de robustesse est définie comme l'ensemble des systèmes linéaires à paramètres variants que la loi de commande donnée garde les trajectoires dans de la région faisable. D'ailleurs, la marge de fragilité comprend toutes les variations des coefficients de la commande donnée telle que l'invariance de la région faisable soit encore garantie. Il est montré que si la région faisable donnée est un polytope, ces marges sont aussi des polytopes.La deuxième partie de ce manuscrit est consacrée au problème de l'optimalité inverse pour la classe des fonctions affines par morceaux. C'est-à-dire, l'objective est de définir un problème d'optimisation pour lequel la solution optimale est équivalente à la fonction affine par morceaux donnée. La méthodologie est fondée sur le convex lifting, i.e., un variable auxiliaire, scalaire, qui permet de définir un ensemble convex à partir de la partition d'état de la fonction affine par morceaux donnée. Il est montré que si la fonction affine par morceaux donnée est continue, la solution optimale de ce problème redéfini sera unique. Par contre, si la continuité n'est pas satisfaite, cette fonction affine par morceaux sera une solution optimale parmi les autres du problème redéfini.En ce qui concerne l’application dans la commande prédictive, il sera montré que n'importe quelle loi de commande affine par morceaux continue peut être obtenue par un autre problème de commande prédictive avec l'horizon de prédiction au plus égal à 2. A côté de cet aspect théorique, ce résultat sera utile pour faciliter la mise en oeuvre des lois de commandes affines par morceaux en évitant l'enregistrement de la partition de l'espace d'état. Dans la dernière partie de ce rapport, une famille de convex liftings servira comme des fonctions de Lyapunov. En conséquence, ce "convex lifting" sera déployé pour synthétiser des lois de commande robustes pour des systèmes linéaires incertains, également en présence de perturbations additives bornées. Des lois implicites et explicites seront obtenues en même temps. Cette méthode permet de garantir la faisabilité récursive et la stabilité robuste. Cependant, cette fonction de Lyapunov est limitée à l'ensemble λ −contractive maximal avec une constante scalaire 0 ≤ λ < 1 qui est plus petit que l'ensemble contrôlable maximal. Pour cette raison, une extension de cette méthode pour l'ensemble contrôlable de N − pas, sera présentée. Cette méthode est fondée sur des convex liftings en cascade où une variable auxiliaire sera utilisée pour servir comme une fonction de Lyapunov. Plus précisément, cette variable est non-négative, strictement décroissante pour les N premiers pas et égale toujours à 0 − après. Par conséquent, la stabilité robuste est garantie. / Piecewise affine (PWA) feedback control laws have received significant attention due to their relevance for the control of constrained systems, hybrid systems; equally for the approximation of nonlinear control. However, they are associated with serious implementation issues. Motivated from the interest in this class of particular controllers, this thesis is mostly related to their analysis and design.The first part of this thesis aims to compute the robustness and fragility margins for a given PWA control law and a linear discrete-time system. More precisely, the robustness margin is defined as the set of linear time-varying systems such that the given PWA control law keeps the trajectories inside a given feasible set. On a different perspective, the fragility margin contains all the admissible variations of the control law coefficients such that the positive invariance of the given feasible set is still guaranteed. It will be shown that if the given feasible set is a polytope, then so are these robustness/fragility margins.The second part of this thesis focuses on inverse optimality problem for the class of PWA controllers. Namely, the goal is to construct an optimization problem whose optimal solution is equivalent to the given PWA function. The methodology is based on emph convex lifting: an auxiliary 1− dimensional variable which enhances the convexity characterization into recovered optimization problem. Accordingly, if the given PWA function is continuous, the optimal solution to this reconstructed optimization problem will be shown to be unique. Otherwise, if the continuity of this given PWA function is not fulfilled, this function will be shown to be one optimal solution to the recovered problem.In view of applications in linear model predictive control (MPC), it will be shown that any continuous PWA control law can be obtained by a linear MPC problem with the prediction horizon at most equal to 2 prediction steps. Aside from the theoretical meaning, this result can also be of help to facilitate implementation of PWA control laws by avoiding storing state space partition. Another utility of convex liftings will be shown in the last part of this thesis to be a control Lyapunov function. Accordingly, this convex lifting will be deployed in the so-called robust control design based on convex liftings for linear system affected by bounded additive disturbances and polytopic uncertainties. Both implicit and explicit controllers can be obtained. This method can also guarantee the recursive feasibility and robust stability. However, this control Lyapunov function is only defined over the maximal λ −contractive set for a given 0 ≤ λ < 1 which is known to be smaller than the maximal controllable set. Therefore, an extension of the above method to the N-steps controllable set will be presented. This method is based on a cascade of convex liftings where an auxiliary variable will be used to emulate a Lyapunov function. Namely, this variable will be shown to be non-negative, to strictly decrease for N first steps and to stay at 0 afterwards. Accordingly, robust stability is sought.

Cette thèse présente une étude dans divers domaines de l'informatique théorique de modèles de calculs combinant automates finis et contraintes arithmétiques. Nous nous intéressons aux questions de décidabilité, d'expressivité et de clôture, tout en ouvrant l'étude à la complexité, la logique, l'algèbre et aux applications. Cette étude est présentée au travers de quatre articles de recherche. Le premier article, Affine Parikh Automata, poursuit l'étude de Klaedtke et Ruess des automates de Parikh et en définit des généralisations et restrictions. L'automate de Parikh est un point de départ de cette thèse; nous montrons que ce modèle de calcul est équivalent à l'automate contraint que nous définissons comme un automate qui n'accepte un mot que si le nombre de fois que chaque transition est empruntée répond à une contrainte arithmétique. Ce modèle est naturellement étendu à l'automate de Parikh affine qui effectue une opération affine sur un ensemble de registres lors du franchissement d'une transition. Nous étudions aussi l'automate de Parikh sur lettres: un automate qui n'accepte un mot que si le nombre de fois que chaque lettre y apparaît répond à une contrainte arithmétique. Le deuxième article, Bounded Parikh Automata, étudie les langages bornés des automates de Parikh. Un langage est borné s'il existe des mots w_1, w_2, ..., w_k tels que chaque mot du langage peut s'écrire w_1...w_1w_2...w_2...w_k...w_k. Ces langages sont importants dans des domaines applicatifs et présentent usuellement de bonnes propriétés théoriques. Nous montrons que dans le contexte des langages bornés, le déterminisme n'influence pas l'expressivité des automates de Parikh. Le troisième article, Unambiguous Constrained Automata, introduit les automates contraints non ambigus, c'est-à-dire pour lesquels il n'existe qu'un chemin acceptant par mot reconnu par l'automate. Nous montrons qu'il s'agit d'un modèle combinant une meilleure expressivité et de meilleures propriétés de clôture que l'automate contraint déterministe. Le problème de déterminer si le langage d'un automate contraint non ambigu est régulier est montré décidable. Le quatrième article, Algebra and Complexity Meet Contrained Automata, présente une étude des représentations algébriques qu'admettent les automates contraints et les automates de Parikh affines. Nous déduisons de ces caractérisations des résultats d'expressivité et de complexité. Nous montrons aussi que certaines hypothèses classiques en complexité computationelle sont reliées à des résultats de séparation et de non clôture dans les automates de Parikh affines. La thèse est conclue par une ouverture à un possible approfondissement, au travers d'un certain nombre de problèmes ouverts. / This thesis presents a study from the theoretical computer science perspective of computing models combining finite automata and arithmetic constraints. We focus on decidability questions, expressiveness, and closure properties, while opening the study to complexity, logic, algebra, and applications. This thesis is presented through four research articles. The first article, Affine Parikh Automata, continues the study of Klaedtke and Ruess on Parikh automata and defines generalizations and restrictions of this model. The Parikh automaton is one of the starting points of this thesis. We show that this model of computation is equivalent to the constrained automaton that we define as an automaton which accepts a word only if the number of times each transition is taken satisfies a given arithmetic constraint. This model is naturally extended to affine Parikh automata, in which an affine transformation is applied to a set of registers on taking a transition. We also study the Parikh automaton on letters, that is, an automaton which accepts a word only if the number of times each letter appears in the word verifies an arithmetic constraint. The second article, Bounded Parikh Automata, focuses on the bounded languages of Parikh automata. A language is bounded if there are words w_1, w_2, ..., w_k such that every word in the language can be written as w_1...w_1w_2...w_2 ... w_k...w_k. These languages are important in applications and usually display good theoretical properties. We show that, over the bounded languages, determinism does not influence the expressiveness of Parikh automata. The third article, Unambiguous Constrained Automata, introduces the concept of unambiguity in constrained automata. An automaton is unambiguous if there is only one accepting path per word of its language. We show that the unambiguous constrained automaton is an appealing model of computation which combines a better expressiveness and better closure properties than the deterministic constrained automaton. We show that it is decidable whether the language of an unambiguous constrained automaton is regular. The fourth article, Algebra and Complexity Meet Constrained Automata, presents a study of algebraic representations of constrained automata and affine Parikh automata. We deduce expressiveness and complexity results from these characterizations. We also study how classical computational complexity hypotheses help in showing separations and nonclosure properties in affine Parikh automata. The thesis is concluded by a presentation of possible future avenues of research, through several open problems.

Cette thèse présente une étude dans divers domaines de l'informatique théorique de modèles de calculs combinant automates finis et contraintes arithmétiques. Nous nous intéressons aux questions de décidabilité, d'expressivité et de clôture, tout en ouvrant l'étude à la complexité, la logique, l'algèbre et aux applications. Cette étude est présentée au travers de quatre articles de recherche. Le premier article, Affine Parikh Automata, poursuit l'étude de Klaedtke et Ruess des automates de Parikh et en définit des généralisations et restrictions. L'automate de Parikh est un point de départ de cette thèse; nous montrons que ce modèle de calcul est équivalent à l'automate contraint que nous définissons comme un automate qui n'accepte un mot que si le nombre de fois que chaque transition est empruntée répond à une contrainte arithmétique. Ce modèle est naturellement étendu à l'automate de Parikh affine qui effectue une opération affine sur un ensemble de registres lors du franchissement d'une transition. Nous étudions aussi l'automate de Parikh sur lettres: un automate qui n'accepte un mot que si le nombre de fois que chaque lettre y apparaît répond à une contrainte arithmétique. Le deuxième article, Bounded Parikh Automata, étudie les langages bornés des automates de Parikh. Un langage est borné s'il existe des mots w_1, w_2, ..., w_k tels que chaque mot du langage peut s'écrire w_1...w_1w_2...w_2...w_k...w_k. Ces langages sont importants dans des domaines applicatifs et présentent usuellement de bonnes propriétés théoriques. Nous montrons que dans le contexte des langages bornés, le déterminisme n'influence pas l'expressivité des automates de Parikh. Le troisième article, Unambiguous Constrained Automata, introduit les automates contraints non ambigus, c'est-à-dire pour lesquels il n'existe qu'un chemin acceptant par mot reconnu par l'automate. Nous montrons qu'il s'agit d'un modèle combinant une meilleure expressivité et de meilleures propriétés de clôture que l'automate contraint déterministe. Le problème de déterminer si le langage d'un automate contraint non ambigu est régulier est montré décidable. Le quatrième article, Algebra and Complexity Meet Contrained Automata, présente une étude des représentations algébriques qu'admettent les automates contraints et les automates de Parikh affines. Nous déduisons de ces caractérisations des résultats d'expressivité et de complexité. Nous montrons aussi que certaines hypothèses classiques en complexité computationelle sont reliées à des résultats de séparation et de non clôture dans les automates de Parikh affines. La thèse est conclue par une ouverture à un possible approfondissement, au travers d'un certain nombre de problèmes ouverts. / This thesis presents a study from the theoretical computer science perspective of computing models combining finite automata and arithmetic constraints. We focus on decidability questions, expressiveness, and closure properties, while opening the study to complexity, logic, algebra, and applications. This thesis is presented through four research articles. The first article, Affine Parikh Automata, continues the study of Klaedtke and Ruess on Parikh automata and defines generalizations and restrictions of this model. The Parikh automaton is one of the starting points of this thesis. We show that this model of computation is equivalent to the constrained automaton that we define as an automaton which accepts a word only if the number of times each transition is taken satisfies a given arithmetic constraint. This model is naturally extended to affine Parikh automata, in which an affine transformation is applied to a set of registers on taking a transition. We also study the Parikh automaton on letters, that is, an automaton which accepts a word only if the number of times each letter appears in the word verifies an arithmetic constraint. The second article, Bounded Parikh Automata, focuses on the bounded languages of Parikh automata. A language is bounded if there are words w_1, w_2, ..., w_k such that every word in the language can be written as w_1...w_1w_2...w_2 ... w_k...w_k. These languages are important in applications and usually display good theoretical properties. We show that, over the bounded languages, determinism does not influence the expressiveness of Parikh automata. The third article, Unambiguous Constrained Automata, introduces the concept of unambiguity in constrained automata. An automaton is unambiguous if there is only one accepting path per word of its language. We show that the unambiguous constrained automaton is an appealing model of computation which combines a better expressiveness and better closure properties than the deterministic constrained automaton. We show that it is decidable whether the language of an unambiguous constrained automaton is regular. The fourth article, Algebra and Complexity Meet Constrained Automata, presents a study of algebraic representations of constrained automata and affine Parikh automata. We deduce expressiveness and complexity results from these characterizations. We also study how classical computational complexity hypotheses help in showing separations and nonclosure properties in affine Parikh automata. The thesis is concluded by a presentation of possible future avenues of research, through several open problems.