Les surfaces de subdivision fournissent une méthode alternative prometteuse dans la modélisation géométrique, et ont des avantages sur la représentation classique de trimmed-NURBS, en particulier dans la modélisation de surfaces lisses par morceaux. Dans ce mémoire, nous considérons le problème des opérations géométriques sur les surfaces de subdivision, avec l'exigence stricte de forme topologique correcte. Puisque ce problème peut être mal conditionné, nous proposons une approche pour la gestion de l'incertitude qui existe dans le calcul géométrique. Nous exigeons l'exactitude des informations topologiques lorsque l'on considère la nature de robustesse du problème des opérations géométriques sur les modèles de solides, et il devient clair que le problème peut être mal conditionné en présence de l'incertitude qui est omniprésente dans les données. Nous proposons donc une approche interactive de gestion de l'incertitude des opérations géométriques, dans le cadre d'un calcul basé sur la norme IEEE arithmétique et la modélisation en surfaces de subdivision. Un algorithme pour le problème planar-cut est alors présenté qui a comme but de satisfaire à l'exigence topologique mentionnée ci-dessus. / Subdivision surfaces are a promising alternative method for geometric modelling, and have some important advantages over the classical representation of trimmed-NURBS, especially in modelling piecewise smooth surfaces. In this thesis, we consider the problem of geometric operations on subdivision surfaces with the strict requirement of correct topological form, and since this problem may be ill-conditioned, we propose an approach for managing uncertainty that exists inherently in geometric computation. We take into account the requirement of the correctness of topological information when considering the nature of robustness for the problem of geometric operations on solid models, and it becomes clear that the problem may be ill-conditioned in the presence of uncertainty that is ubiquitous in the data. Starting from this point, we propose an interactive approach of managing uncertainty of geometric operations, in the context of computation using the standard IEEE arithmetic and modelling using a subdivision-surface representation. An algorithm for the planar-cut problem is then presented, which has as its goal the satisfaction of the topological requirement mentioned above.

L’arithmétique virgule flottante est une approximation de l’arithmétique réelle dans laquelle chaque opération peut introduire une erreur. La norme IEEE 754 requiert que les opérations élémentaires soient aussi précises que possible, mais au cours d’un calcul, les erreurs d’arrondi s’accumulent et peuvent conduire à des résultats totalement faussés. Cela arrive avec une expression aussi simple que ab + cd, pour laquelle l’algorithme naïf retourne parfois un résultat aberrant, avec une erreur relative largement supérieure à 1. Il est donc important d’analyser les algorithmes utilisés pour contrôler l’erreur commise. Je m’intéresse à l’analyse de briques élémentaires du calcul en cherchant des bornes fines sur l’erreur relative. Pour des algorithmes suffisamment précis, en arithmétique de base β et de précision p, on arrive en général à prouver une borne sur l'erreur de la forme α·u + o(u²) où α > 0 et u = 1/2·β1-p est l'unité d'arrondi. Comme indication de la finesse d'une telle borne, on peut fournir des exemples numériques pour les précisions standards qui approchent cette borne, ou bien un exemple paramétré par la précision qui génère une erreur de la forme α·u + o(u²), prouvant ainsi l'optimalité asymptotique de la borne. J’ai travaillé sur la formalisation d’une arithmétique à virgule flottante symbolique, sur des nombres paramétrés par la précision, et à son implantation dans le logiciel de calcul formel Maple. J’ai aussi obtenu une borne d'erreur très fine pour un algorithme d’inversion complexe en arithmétique flottante. Ce résultat suggère le calcul d'une division décrit par la formule x/y = (1/y)·x, par opposition à x/y = (x·y)/|y|². Quel que soit l'algorithme utilisé pour effectuer la multiplication, nous avons une borne d'erreur plus petite pour les algorithmes décrits par la première formule. Ces travaux sont réalisés avec mes directeurs de thèse, en collaboration avec Claude-Pierre Jeannerod (CR Inria dans AriC, au LIP). / Floating-point arithmetic is an approximation of real arithmetic in which each operation may introduce a rounding error. The IEEE 754 standard requires elementary operations to be as accurate as possible. However, through a computation, rounding errors may accumulate and lead to totally wrong results. It happens for example with an expression as simple as ab + cd for which the naive algorithm sometimes returns a result with a relative error larger than 1. Thus, it is important to analyze algorithms in floating-point arithmetic to understand as thoroughly as possible the generated error. In this thesis, we are interested in the analysis of small building blocks of numerical computing, for which we look for sharp error bounds on the relative error. For this kind of building blocks, in base and precision p, we often successfully prove error bounds of the form α·u + o(u²) where α > 0 and u = 1/2·β1-p is the unit roundoff. To characterize the sharpness of such a bound, one can provide numerical examples for the standard precisions that are close to the bound, or examples that are parametrized by the precision and generate an error of the same form α·u + o(u²), thus proving the asymptotic optimality of the bound. However, the paper and pencil checking of such parametrized examples is a tedious and error-prone task. We worked on the formalization of a symbolicfloating-point arithmetic, over numbers that are parametrized by the precision, and implemented it as a library in the Maple computer algebra system. We also worked on the error analysis of the basic operations for complex numbers in floating-point arithmetic. We proved a very sharp error bound for an algorithm for the inversion of a complex number in floating-point arithmetic. This result suggests that the computation of a complex division according to x/y = (1/y)·x may be preferred, instead of the more classical formula x/y = (x·y)/|y|². Indeed, for any complex multiplication algorithm, the error bound is smaller with the algorithms described by the “inverse and multiply” approach.This is a joint work with my PhD advisors, with the collaboration of Claude-Pierre Jeannerod (CR Inria in AriC, at LIP).

L'arithmétique par intervalles permet de calculer et simultanément vérifier des résultats. Cependant, une application naïve de cette arithmétique conduit à un encadrement grossier des résultats. De plus, de tels calculs peuvent être lents.Nous proposons des algorithmes précis et des implémentations efficaces, utilisant l'arithmétique par intervalles, dans le domaine de l'algèbre linéaire. Deux problèmes sont abordés : la multiplication de matrices à coefficients intervalles et la résolution vérifiée de systèmes linéaires. Pour le premier problème, nous proposons deux algorithmes qui offrent de bons compromis entre vitesse et précision. Pour le second problème, nos principales contributions sont d'une part une technique de relaxation, qui réduit substantiellement le temps d'exécution de l'algorithme, et d'autre part l'utilisation d'une précision étendue en quelques portions bien choisies de l'algorithme, afin d'obtenir rapidement une grande précision. / Interval arithmetic is a means to compute verified results. However, a naive use of interval arithmetic does not provide accurate enclosures of the exact results. Moreover, interval arithmetic computations can be time-consuming. We propose several accurate algorithms and efficient implementations in verified linear algebra using interval arithmetic. Two fundamental problems are addressed, namely the multiplication of interval matrices and the verification of a floating-point solution of a linear system. For the first problem, we propose two algorithms which offer new tradeoffs between speed and accuracy. For the second problem, which is the verification of the solution of a linear system, our main contributions are twofold. First, we introduce a relaxation technique, which reduces drastically the execution time of the algorithm. Second, we propose to use extended precision for few, well-chosen parts of the computations, to gain accuracy without losing much in term of execution time.

Ce mémoire propose un algorithme de compression sans perte des indices binaires d'un quantificateur algébrique encastré utilisé par le codec AMR-WB+ pour encoder certaines des trames d'un signal audio. Une étude détaillée des statistiques a été menée dans le but de développer un algorithme efficace de compression et réduire par conséquent la longueur moyenne du code binaire utilisé par le codec AMR-WB+. En se basant sur cette étude des statistiques, deux techniques ont été combinées : l'encodage par plage et l'encodage par contexte qui se sont montrés très efficaces pour estimer les probabilités des différents indices. En utilisant l'encodage arithmétique en version entière pour générer le code binaire, l'algorithme proposé permet de réduire sans perte jusqu'à 10% de la longueur du code utilisé par le AMR-WB+ tout en respectant la contrainte d'une application temps réel destinée à des terminaux GSM.

Le problème de Lehmer consiste à minorer la hauteur de Weil d'un nombre algébrique en fonction de son degré sur Q. Si la question originelle de Lehmer reste aujourd'hui sans réponse, la conjecture optimale correspondante a été démontrée à un epsilon près. Par ailleurs, ce problème admet plusieurs généralisations. D'une part, on peut formuler le même type de conjecture en remplaçant le corps des rationnels par une extension abélienne d'un corps de nombres. D'autre part, on peut généraliser ces énoncés en dimension supérieure. Il s'agit alors de minorer la hauteur normalisée d'un point ou d'une sous-variété d'un tore ; dans ce cas, on substitue au degré un invariant plus fin : l'indice d'obstruction. Il est ensuite naturel de chercher à combiner ces deux généralisations : c'est le problème de Lehmer relatif dans un tore.<br /><br />Dans cette thèse, nous considérons tout d'abord le problème de Lehmer relatif unidimensionnel. Nous donnons une minoration pour la hauteur d'un nombre algébrique en fonction de son degré sur une extension abélienne d'un corps de nombres. Il s'agit d'une amélioration d'un théorème d'Amoroso et Zannier, obtenue à l'aide d'une démonstration techniquement plus simple. De plus, nous explicitons la dépendance de la borne inférieure en le corps de base. Puis nous abordons le problème de Lehmer relatif en dimension supérieure et minorons la hauteur d'une hypersurface en fonction de son indice d'obstruction sur une extension abélienne de Q. Enfin, nous obtenons un résultat analogue pour un point, sous réserve que celui-ci satisfasse une hypothèse technique. Nous montrons ainsi les conjectures les plus fines à un epsilon près.

L'objectif général de ce travail de thèse était d'étudier le phénomène de répétition stratégique et son évolution au cours du vieillissement normal et pathologique ; mais aussi de mettre en évidence les mécanismes impliqués lors du choix d'une stratégie. Pour atteindre ces objectifs, nous avons conduit trois études, pour lesquelles nous avons adopté une approche expérimentale où nous avons utilisé des stratégies arithmétiques (i.e., méthodes utilisées par un individu pour résoudre une tâche cognitive donnée). Nous avons recueilli nos données auprès d'individus jeunes, âgés sains et patients atteints de la maladie d'Alzheimer (i.e., MA). Les principaux résultats montraient que (a) les adultes âgés répétaient significativement plus que les adultes jeunes, et ce d'autant plus lorsque la stratégie était fortement active en mémoire de travail ; cependant, (b) ils réussissaient à changer de stratégie de manière comparable aux adultes jeunes lorsque les latences entre leurs réponses et les stimuli suivant augmentaient ; et (c) les patients atteints de la MA avaient plus de difficultés à sélectionner la meilleure stratégie que les adultes âgés, et ce d'autant plus lorsque le problème était difficile. Ce travail a donc permis de préciser les processus cognitifs impliqués lors de la sélection stratégique et de comprendre les effets du vieillissement normal et pathologique sur ceux-ci. Nous discutons également de l'implication possible de ces résultats quant aux modèles théoriques de la sélection stratégique. / The main goals of this thesis were (a) to study the strategy repetition phenomenon and its evolution during normal and pathological aging and (b) to highlight mechanisms involved in the strategy selection. To achieve these purposes, we collected strategy selection data from young, healthy older adults, and patients with Alzheimer's disease (i.e., AD). Our main results showed that (a) older adults repeated strategies significantly more than young adults, and especially when this strategy was highly active in working memory, however, (b) they were able to change strategies in a comparable way to young adults when latencies between their response and the next stimulus increased, and (c) AD patients had more difficulties selecting the best strategy than healthy older adults, especially on the most difficult problems (i.e., heterogeneous problems). This work helped in clarifying cognitive processes involved in strategy selection and in understanding effects of normal and pathological aging. We also discuss the implications of these results for theoretical models of strategyselection.

Ce travail se divise en deux parties. Dans la première partie, nous généralisons le travail de Khuri-Makdisi qui décrit des algorithmes pour l'arithmétique des diviseurs sur une courbe sur un corps. Nous montrons que les analogues naturelles de ses résultats se vérifient pour les diviseurs de Cartier relatifs effectifs sur un schéma projectif, lisse et de dimension relative un sur un schéma affine noetherien quelconque, et que les analogues naturelles de ses algorithmes se vérifient pour une certaine classe d'anneaux de base. Nous présentons un formalisme pour tels anneaux qui sont caractérisés par l'existence d'un certain sous-ensemble des opérations standards de l'algèbre linéaire pour les modules projectifs sur ces anneaux.Dans la deuxième partie de ce travail, nous considérons un type de problème de Riemann-Roch pour les diviseurs sur certaines surfaces algébriques. Plus précisément, nous analysons les surfaces algébriques qui émanent d'un produit ou d'un produit symétrique d'une courbe hyperelliptique de genre supérieur à un sur un corps (presque) arbitraire. Les résultats principaux sont une décomposition des espaces de sections globales de certains diviseurs sur telles surfaces et des formules explicites qui décrivent les dimensions des espaces de sections de ces diviseurs. Dans le dernier chapitre, nous présentons un algorithme qui produit une base pour l'espace de sections globales d'un tel diviseur. / The contribution of this thesis is divided naturally into two parts. In Part I we generalise the work of Khuri-Makdisi (2004) on algorithms for divisor arithmetic on curves over fields to more general bases. We prove that the natural analogues of the results of Khuri-Makdisi continue to hold for relative effective Cartier divisors on projective schemes which are smooth of relative dimension one over an arbitrary affine Noetherian base scheme and that natural analogues of the algorithms remain valid in this context for a certain class of base rings. We introduce a formalism for such rings,which are characterised by the existence of a certain subset of the usual linear algebra operations for projective modules over these rings.Part II of this thesis is concerned with a type of Riemann-Roch problem for divisors on certain algebraic surfaces. Specifically we consider algebraic surfaces arising as the square or the symmetric square of a hyperelliptic curve of genus at least two over an (almost) arbitrary field. The main results are a decomposition of the spaces of global sections of certain divisors on such surfaces and explicit formulæ for the dimensions of the spaces of sections of these divisors. In the final chapter we present an algorithm which generates a basis for the space of global sections of such a divisor.

Actuellement, nous vivons dans une société numérique. L'avènement de l'Internet et l'arrivée du multimédia et des supports de stockage numériques, ont transformé profondément la façon dont nous communiquons. L'image en particulier occupe une place très importante dans la communication interpersonnelle moderne. Toutefois, elle présente l'inconvénient d'être représentée par une quantité d'information très importante. De ce fait, la transmission et le stockage des images soulèvent certains problèmes qui sont liés essentiellement à la sécurité et à la compression d'images. Ce sont ces considérations qui ont guidé cette thèse. En effet, la problématique que nous posons dans cette thèse est de proposer une solution conduisant à la crypto-compression d'images afin d'assurer un archivage et un transfert sécurisés tout en conservant les performances de la méthode de compression utilisée. En effet, nos travaux de recherche ont porté essentiellement sur la compression et le cryptage des images numériques. Concernant la compression, nous avons porté un intérêt particulier au codage arithmétique vu sont efficacité en terme de ta ux de compression et son utilisation par les nouvelles normes et standards de compression tel que JPEG2000, JBIG, JBIG2 et H.264/AVC. Quant au cryptage, nous avons opté pour l'utilisation du chaos combiné avec les fractions continues afin de générer des flux de clés ayant à la fois de bonnes propriétés cryptographiques et statistiques. Ainsi, nous avons proposé deux nouvelles méthodes de compression sans perte basées sur le codage arithmétique tout en introduisant de nouveaux paramètres de codage afin de réduire davantage la taille en bits des images compressées. Deux autres méthodes s'appuient sur l'utilisation du chaos et des fractions continues pour le développement d'un générateur de nombres pseudo-aléatoires et le cryptage par flot d'images. Enfin, nous proposons une nouvelle méthode qui emploie conjointement le cryptage avec la compression. Cette dernière méthode se base sur l'échange des sous-intervalles associés aux symboles d'un codeur arit hmétique binaire de façon aléatoire tout en exploitant notre générateur de nombres pseudo-aléatoire. Elle est efficace, sécurisée et conserve le taux de compression obtenu par le codage arithmétique et ceci quelque soit le modèle statistique employé : statique ou adaptatif. / Actually, we live in a digital society. The proliferation of the Internet and the rapid progress in information technology on multimedia, have profoundly transformed the way we communicate. An enormous amount of media can be easily exchanged through the Internet and other communication networks. Digital image in particular occupies an important place in modern interpersonal communication. However, image data have special features such as bulk capacity. Thus, image security and compression issues have became exceptionally acute. It is these considerations that have guided this thesis. Thus, we propose throw this thesis to incorporating security requirements in the data compression system to ensure reasonable security without downgrading the compression performance.For lossless image compression, we have paid most attention to the arithmetic coding (AC) which has been widely used as an efficient compression algorithm in the new standards including JBIG, JBIG2, JPEG2000 and H.264/AVC. For image encryption, we are based on the combination of a chaotic system and the Engel continued fraction map to generate key-stream with both good chaotic and statistical properties. First, we have proposed two new schemes for lossless image compression based on adding new pre-treatment steps and on proposing new modeling methods to estimate probabilities for AC. Experimental results demonstrate that the proposed schemes give mean compression ratios that are significantly higher than those by the conventional AC. In addition, we have proposed a new pseudo-random bit generator (PRBG). The detailed analysis done by NIST statistical test Suite demonstrates that the proposed PRGB is suitable for cryptography. The proposed PRBG is used to develop a new symmetr ic stream cipher for image encryption. Theoretic and numerical simulation analyses indicate that our image encryption algorithm is efficient and satisfies high security. Finally, we have proposed a new scheme which performs both lossless compression and encryption of image. The lossless compression is based on the binary AC (BAC) and the encryption is based on the proposed PRBG. The numerical simulation analysis indicates that the proposed compression and encryption scheme satisfies highly security with no loss of the BAC compression efficiency.

Pour réduire les coûts des systèmes embarqués, ces derniers sont livrés avec des micro-processeurs peu puissants. Ces processeurs sont dédiés à l'exécution de tâches calculatoires dont certaines, comme la transformée de Fourier rapide, peuvent s'avérer exigeantes en termes de ressources de calcul. Afin que les implémentations de ces algorithmes soient efficaces, les programmeurs utilisent l'arithmétique à virgule fixe qui est plus adaptée aux processeurs dépourvus d'unité flottante. Cependant, ils se retrouvent confrontés à deux difficultés: D'abord, coder en virgule fixe est fastidieux et exige que le programmeur gère tous les détails arithmétiques. Ensuite, et en raison de la faible dynamique des nombres à virgule fixe par rapport aux nombres flottants, les calculs en fixe sont souvent perçus comme intrinsèquement peu précis. La première partie de cette thèse propose une méthodologie pour dépasser ces deux limitations. Elle montre comment concevoir et mettre en œuvre des outils pour générer automatiquement des programmes en virgule fixe. Ensuite, afin de rassurer l'utilisateur quant à la qualité numérique des codes synthétisés, des certificats sont générés qui fournissent des bornes sur les erreurs d'arrondi. La deuxième partie de cette thèse est dédiée à l'étude des compromis lors de la génération de programmes en virgule fixe pour les briques d'algèbre linéaire. Des données expérimentales y sont fournies sur la synthèse de code pour la multiplication et l'inversion matricielles. / To be cost effective, embedded systems are shipped with low-end micro-processors. These processors are dedicated to one or few tasks that are highly demanding on computational resources. Examples of widely deployed tasks include the fast Fourier transform, convolutions, and digital filters. For these tasks to run efficiently, embedded systems programmers favor fixed-point arithmetic over the standardized and costly floating-point arithmetic. However, they are faced with two difficulties: First, writing fixed-point codes is tedious and requires that the programmer must be in charge of every arithmetical detail. Second, because of the low dynamic range of fixed-point numbers compared to floating-point numbers, there is a persistent belief that fixed-point computations are inherently inaccurate. The first part of this thesis addresses these two limitations as follows: It shows how to design and implement tools to automatically synthesize fixed-point programs. Next, to strengthen the user's confidence in the synthesized codes, analytic methods are suggested to generate certificates. These certificates can be checked using a formal verification tool, and assert that the rounding errors of the generated codes are indeed below a given threshold. The second part of the thesis is a study of the trade-offs involved when generating fixed-point code for linear algebra basic blocks. It gives experimental data on fixed-point synthesis for matrix multiplication and matrix inversion through Cholesky decomposition.

De nombreuses recherches montrent que les adultes résolvent de simples problèmes arithmétiques plus ou moins exclusivement par récupération de la réponse dans un réseau d’associations stockées en mémoire à long terme (Ashcraft, 1992 ; 1995 ; Campbell, 1995). Il est admis que les performances arithmétiques des jeunes enfants sont basées sur le comptage ou d’autres stratégies procédurales qui sont peu à peu remplacées par la récupération directe en mémoire (Barrouillet & Fayol, 1998). Ces premiers résultats ont été rapportés par Groen et Parkman (1972) en étudiant les temps de résolution. Mais moyenner des temps de latence d’essais impliquant différentes procédures peut conduire à des conclusions erronées sur la façon dont les problèmes sont résolus. D’autres auteurs ont préféré la méthode des protocoles verbaux. Cependant Kirk et Ashcraft (2001) remettent en question ce protocole. Nous proposons un nouveau paradigme pour faire la lumière sur la façon dont des problèmes additifs, soustractifs et multiplicatifs sont résolus par les adultes et les enfants. Ce paradigme tire avantage du fait que les procédures de calcul dégradent les traces en mémoire des opérandes impliquées dans les calculs (Thevenot, Barrouillet & Fayol, 2001). Le temps nécessaire à l’algorithme pour parvenir à la réponse et son coût cognitif entraînent une réduction du niveau d’activation des opérandes. Cette baisse d’activation résulte d’un phénomène de déclin mémoriel qui entraîne une détérioration des traces en mémoire (Towse & Hitch, 1995 ; Towse, Hitch & Hutton, 1998) et de l’activation concurrente de résultats transitoires provoquant un partage attentionnel entre les opérandes, leurs composantes et les résultats intermédiaires nécessaires pour arriver à la solution (Anderson, 1993). Par conséquent, lorsque l’algorithme aboutit à la réponse les traces des opérandes sont dégradées et la récupération en mémoire est difficile. Ce phénomène devrait être plus prononcé pour les grands nombres car parvenir au résultat nécessite plus d’étapes et plus de temps. En contrastant la difficulté rencontrée par des adultes pour reconnaître des opérandes après leur implication soit dans une opération arithmétique (addition, soustraction ou multiplication) soit dans une comparaison (qui ne nécessite aucune décomposition) avec un troisième nombre, nous pourrons déterminer si l’opération a été résolue par procédure algorithmique. Si la difficulté est la même dans les deux conditions, l’opération aura été résolue par récupération, une telle activité ne nécessite pas la décomposition des opérandes / Numerous studies show that adults solve simple arithmetic problems more or less exclusively by retrieval the response in a network of associations stored in long-term memory (Ashcraft, 1992, 1995 and Campbell, 1995). It is recognized that the arithmetic performance of young children are based on counting or other procedural strategies that are gradually replaced by direct memory retrieval (Barrouillet & Fayol, 1998). These first results were reported by Groen and Parkman (1972) by studying the resolution time. But average latency of trials involving different procedures can lead to erroneous conclusions about how problems are solved. Other authors have preferred the method of verbal reports. But Kirk and Ashcraft (2001) question this paradigm. We propose a new paradigm to shed light on how the addition problems, subtraction and multiplication are resolved by adults and children. This paradigm takes advantage of the fact that algorithmic computation degrades the memory traces of the operands involved in the calculation (Thevenot, Barrouillet, & Fayol, 2001). The time needed by the algorithm to reach the answer and its cognitive cost lead to a reduction in the level of activation of the operands. This decrease in activation would result both from a memory decay phenomenon, which damages memory traces (Towse & Hitch, 1995; Towse, Hitch & Hutton, 1998) and from the necessary concurrent activation of transitory results, which induces a sharing of the attentional resources between the operands, their components and the intermediate results necessary to be reached to solve the problem (Anderson, 1993). Therefore, when the algorithm leads to the response, traces of the operands are degraded and retrieval the operand in memory is more difficult. This phenomenon should be more pronounced for large numbers since arriving at the result requires more steps and more time. Thus, contrasting the relative difficulty that adults or children encounter in recognizing operands after either their involvement in an arithmetic problem or their simple comparison with a third number can allow us to determine if the arithmetic problem has been solved by an algorithmic procedure or by retrieval of the result from memory: If operands are more difficult to recognize after the operation than after their comparison, we can assume that an algorithmic procedure has been used. On the contrary, if the difficulty is the same in both conditions, then the operation has most probably been solved by retrieval, a fast activity that does not imply the decomposition of the operands