Academic literature on the topic 'Transformations algorithmiques'

This article summarizes two initiatives for artificial intelligence (AI) underway in the Canadian public service: public consultation and collaboration in compiling an algorithmic impact assessment, and a symposium on AI and human rights held by Global Affairs Canada. The findings contextualize the national consultations on digital and data transformation and future steps for more inclusive AI governance in Canada.Cet article offre une synthèse de deux initiatives sur l’intelligence artificielle (IA) en cours dans la fonction publique canadienne : la consultation et collaboration du public dans la compilation d’une évaluation d’impact algorithmique et un symposium sur l’IA et les droits de la personne organisée par Affaires mondiales Canada. Les conclusions permettent de donner un contexte aux consultations nationales sur la transformation du numérique et des données et les mesures à prendre pour une gouvernance en intelligence artificielle plus inclusive au Canada.

La thèse porte sur l'impact d'optimisations algorithmiques pour la synthèse automatique HLS pour ASIC. Ces optimisations algorithmiques sont des transformations de haut niveau, qui de part leur nature intrinsèque restent hors de porter des compilateurs modernes, même les plus optimisants. Le but est d'analyser l'impact des optimisations et transformations de haut niveau sur la surface, la consommation énergétique et la vitesse du circuit ASIC. Les trois algorithmes évalués sont les filtres non récursifs, les filtres récursifs et un algorithme de détection de mouvement. Sur chaque exemple, des gains ont été possibles en vitesse et/ou en surface et/ou en consommation. Le gain le plus spectaculaire est un facteur x12.6 de réduction de l'énergie tout en maitrisant la surface de synthèse et en respectant la contrainte d'exécution temps réel. Afin de mettre en perspective les résultats (consommation et vitesse), un benchmark supplémentaire a été réalisé sur un microprocesseur ST XP70 avec extension VECx, un processeur ARM Cortex avec extension Neon et un processeur Intel Penryn avec extensions SSE.

Cette thèse adresse la problématique de l'optimisation automatique des spécifications dans le flot de conception des circuits intégrés. Par l'utilisation d'un formalisme canonique (basé sur les Taylors Expansion Diagram) et la reconnaissance de motifs particuliers dans le graphe, les optimisations issues de ces travaux permettent d'améliorer les résultats générés par les outils de synthèse de haut niveau sans connaissance à priori de l'application à implémenter
This thesis addresses the design productivity gap problem in design automation by emp]oying a canonical representation, called Taylor Expansion Diagram. TED is a graphical representation based on Taylor series decomposition of the data-flow computation. Optimizations and high-level transformations developed in this thesis are based on transformations and pattern recognition applied to the TED representation. The results of su ch transformations are the optimized data-flow graphs, which provide input to standard, HLS too]s for final architectural synthesis. Such optimizations cannot be achieved by traditional architectural and high-level synthesis tools or compiJers available today

L'évolution constante des processeurs vers des architectures proposant des capacités superscalaires, de parallélisme au niveau des instructions, de prédiction, de spéculation et la multiplication des niveaux de hiérarchie mémoire donnent de plus en plus d'importance au travail du compilateur.
Dans cette thèse, nous nous intéressons aux transformations du programme source destinées à l'optimisation dans la chaîne de compilation, et plus particulièrement à une transformation appelée décalage d'instructions.
Cette transformation sert de base au pipeline logiciel, elle a une influence sur le parallélisme au niveau des instructions et l'utilisation des registres.
Elle intervient également comme composante des techniques de parallélisation de boucles par ordonnancement affine.
Nous avons voulu mieux comprendre les perspectives offertes par le décalage d'instructions, savoir quels objectifs il permettait d'atteindre mais aussi savoir quels problèmes de décalage restaient difficiles.
Pour cela nous avons étudié le décalage d'instructions dans plusieurs contextes plus ou moins proches, et apporté des contributions à chacun d'entre eux.

Dans le cadre du pipeline logiciel, nous proposons un algorithme polynomial pour déterminer le décalage le plus à même de produire un maximum de parallélisme au niveau des instructions, et une étude expérimentale de l'efficacité absolue de la technique à l'aide de l'outil logiciel que nous avons réalisé dans ce but : PASTAGA (pour Plate-forme d'Analyse Statistique et de Tests d'Algorithmes sur Graphes Aléatoires).
Dans le cadre de l'utilisation des registres (stage scheduling), de la parallélisation de boucle et de la localité, nous apportons des réponses aux problèmes de décalage d'instructions associés~: complexité, solutions exactes, approximations.

Le développement de la numérisation systématique des formes 3D (conservation du patrimoine national, commerce électronique, reverse engineering, intégration d’objets réels dans des environnements de réalité virtuelle) et le besoin toujours croissant de ces objets géométriques dans de nombreuses applications (conception assistée par ordinateur, calcul de simulations par éléments finis, système d’informations géographiques, loisirs numériques) a entrainé une augmentation vertigineuse du volume de données à traiter, avec l’émergence de nombreuses méthodes de compression de modèles 3D. Ce volume de données devient encore plus difficile à maitriser lorsque l’aspect temporel entre en jeu. Les maillages correspondent au modèle classiquement utilisé pour modéliser les formes numérisées et certaines approches de compression exploitent la propriété qu’une bonne estimation de la connectivité peut être déduite de l’échantillonnage, lorsque ce dernier s’avère suffisamment dense. La compression de la connectivité d’un maillage revient alors au codage de l’écart entre deux connectivités proches. Dans ce mémoire, nous nous intéressons au codage compact de cette différence pour des maillages surfaciques. Nos travaux sont fondés sur l’utilisation de la bascule d’arête (edge flip) et l’étude de ses propriétés. Nos contributions sont les suivantes. Etant donné deux triangulations connexes partageant le même nombre de sommets et un même genre topologique, nous proposons un algorithme direct et efficace pour générer une séquence de bascules d’arêtes permettant de passer d’un maillage `a un autre. Nous nous appuyons sur une correspondance entre les sommets des deux maillages, qui, si elle est non fournie, peut être choisie de manière totalement aléatoire
The development of scanning 3D shapes (national heritage conservation, ecommerce, reverse engineering, virtual reality environments) and the growing need for geometric objects in many applications (computer-aided design, simulations, geographic information systems, digital entertainment) have led to a dramatic increase in the volume of data to be processed, and the emergence of many methods of compression of 3D models. This volume of data becomes even more difficult to control when the temporal aspect comes in. Meshes correspond to the pattern typically used to model the scanned forms and some approaches exploit a property of compression that a good estimation of connectivity can be derived from sampling, when it appears sufficiently dense. Compressing the connectivity of a mesh is equivalent to coding the difference between two close connectivities. In this thesis, we focus on the compact coding of this difference for 2-dimensional meshes. Our work is based on the use and study of the properties of the edge flip. Our contributions are the following : - Given two connected triangulations that share the same number of vertices and the same topological genus, we propose a direct and efficient algorithm to generate a sequence of edge flips to change one mesh into the other. We rely on a correspondence between the vertices of the two meshes, which, if not provided, may be chosen randomly. The validity of the algorithm is based on the fact that we intend to work in a triangulation of a different class from those generally used. - We then generalize the edge flips to triangulations in which we identify each edge with a label. We show that a sequence of edge flips can be used to transpose two labels, under certain conditions. From this result, the edge flip can be generalized to meshes whose faces are not necessarily triangular, which allowed us to develop an algorithm for reducing sequences of edge flips. - Finally, we present a compact coding approach for a sequence of edge flips, and determine under what conditions it is better to use this compact transformation between two connectivities instead of coding them independently by a static algorithm

Ce mémoire de thèse présente différents modèles géométriques pour l'imagerie et leurs interconnexions. L' "espace des cercles" en constitue, en grande partie, le cadre unificateur, avec des applications aux diagrammes de voronoi͏̈ et à le recherche originale du plus petit cercle circonscrit. On y étudie des transformées alternatives à la transformée de Hough, principalement la Transformée Polaire et son cadre de dualité, généralisable à des dimensions supérieures. Les deux résultats les plus originaux de ce mémoire quantifient l'incertitude d'alignement (ou, dualement, le "flou d'intersection") via soit une mesure invariante par translation en liaison avec la géométrie intégrale et la "géométrie différentielle affine", soit des lignes iso-valeurs en faisceaux de coniques
This thesis presents various geometrical models useful for image processing and highlights their interconnections. The space of circles constitutes the unifying framework of all the models. Within this space, applications such a Voronoi diagrams computation and an original determination of the smallest circumscribed circle can be performed. Transforms alternative to the Hough transform are studied, with an instrumental role for the Polar Transform and its framework of duality, generalizable to higher dimensions is described. The two most original results of this thesis allow to quantify the uncertainty of an alignment ("intersection blur") with either a translation invariant measure in connection with integral geometry and "differential affine geometry", or contour lines which are conics pencils

L’objectif théorique de cette thèse est d’étudier le rôle de la familiarité vocale sur le traitement de la voix émotionnelle. Les chapitres 2 et 3 présentent des études comportementales et électrophysiologiques portant sur les contributions spécifiques de la voix du self et la voix de l’autre sur le traitement de la parole émotionnelle. En comparant le self et l’autre, la familiarité est évaluée ici à un niveau personnel. Les résultats du chapitre 2 montrent une dissociation chez les participants des traitements explicites et implicites de leur propre voix. Alors que la discrimination explicite de leur propre voix émotionnelle est réduite, le traitement implicite de soi entraîne un avantage pour la reconnaissance des émotions et la discrimination du locuteur. Le chapitre 3 montre que les voix inconnues sont priorisées par rapport à la voix du self dans le traitement des changements émotionnels et acoustiques de bas niveau, par des réponses électrophysiologiques (EEG) et comportementales plus rapides. Au chapitre 4, l’effet de la familiarité sur la perception des émotions vocales est évalué au niveau socioculturel en comparant la langue maternelle et étrangère. Au travers de ces études, cette thèse met en évidence les différentes manières par lesquelles «l’étrangeté» d’une voix - qu’il s’agisse d’un locuteur autre que le soi ou d’une langue étrangère - est traitée avec une priorité plus élevée, mais une précision acoustique diminuée
The human voice is a powerful tool to convey emotions. Humans hear voices on a daily basis and are able to rapidly extract relevant information to successfully interact with others. The theoretical aim of this thesis is to investigate the role of familiarity on emotional voice processing. Chapters 2 and 3 present behavioral and electrophysiological studies investigating how self- versus non self-produced voices influence the processing of emotional speech utterances. By contrasting self and other, familiarity is here assessed at a personal level. The results of Chapter 2 show a dissociation of explicit and implicit processing of the self-voice. While explicit discrimination of an emotional self-voice and other-voice was somewhat impaired, implicit self-processing prompted a self-advantage in emotion recognition and speaker discrimination. Chapter 3 reports a prioritization for the non-self voice in the processing of emotional and low-level acoustic changes, reflected in faster electrophysiological (EEG) and behavioral responses. In Chapter 4, the effect of voice familiarity on is assessed at a larger sociocultural scale by comparing speech utterances in the native and a foreign language. Taken together, this thesis highlights some ways in which the ‘otherness’ of a voice - whether a non-self speaker or a foreign language speaker - is processed with a higher priority on the one hand, but with less acoustic precision on the other hand

Cette thèse porte sur la méthode dite « méthode multipôle rapide » qui résout hiérarchiquement le problème à N-corps avec une complexité linéaire pour n'importe quelle précision. Dans le cadre de l'équation de Laplace, nous souhaitons pouvoir traiter efficacement toutes les distributions de particules rencontrées en astrophysique et en dynamique moléculaire.
Nous étudions tout d'abord deux expressions distinctes du principal opérateur (« multipôle-to-local ») ainsi que les bornes d'erreur associées. Pour ces deux expressions, nous présentons une formulation matricielle dont l'implémentation avec des routines BLAS (Basic Linear Algebra Subprograms) permet d'améliorer fortement l'efficacité de calcul. Dans la gamme de précisions qui nous intéresse, cette approche se révèle plus performante que les améliorations existantes (FFT, rotations et ondes planes), pour des distributions uniformes ou non.
Outre une nouvelle structure de données pour l'octree sous-jacent et des contributions algorithmiques à la version adaptative, nous avons aussi efficacement parallélisé notre méthode en mémoire partagée et en mémoire distribuée. Enfin, des comparaisons avec des codes dédiés justifient l'intérêt de notre code pour des simulations en astrophysique.

Ce travail est issu d'une importante recherche bibliographique et mathematique sur les modeles de definition numerique des courbes et des surfaces (les eleformes, elements de forme). Il presente une synthese des differentes methodes utilisees (rationnelles et non rationnelles, bezier, b-spline, coons) dans les logiciels de cfao (unisurf, autocad, catia, gks, euklid, cadkey, etc. . . ) des corps mecaniques dans les industries aeronautiques, automobiles, et dans la conception moderne (renault, citroen, fuji-tsushinski, boeing, dassault, ferrari, etc. . . ). En seconde partie nous presentons les algorithmes de transformation (reduction du degre, elevation du degre, insertion des nuds, etc. . . ) dans les modeles non rationnels que nous avons generalises pour les modeles rationnels. En troisieme chapitre des algorithmes d'equivalence au sens mathematique entre les modeles seront generalises pour le cas rationnel. Dans la quatrieme partie nous avons introduit une nouvelle notion d'equivalence qui depend du materiel de cfao et qui elargira les possibilites de reduction du degre. Une analyse mathematique approfondie nous permit de developper les algorithmes sub-n-1, sub-n-k et sub-red permettant de transformer un modele de degre eleve en modeles de degre faible avec des criteres geometriques (le point, la tangente, et la courbure). Du point de vue application industrielle, en derniere partie on presente le developpement des modules informatiques pour la transformation d'un maillage 3d de spline cubiques en super-carreau de bezier et son super-carreau offset, cela est une amelioration du logiciel cadkey

Dans cette thèse, nous étudions les transformations rigides dans le contexte de l'imagerie numérique. En particulier, nous développons un cadre purement discret pour traiter ces transformations. Les transformations rigides, initialement définies dans le domaine continu, sont impliquées dans de nombreuses applications de traitement d'images numériques. Dans ce contexte, les transformations rigides digitales induites présentent des propriétés géométriques et topologiques différentes par rapport à leurs analogues continues. Afin de s'affranchir des problèmes inhérents à ces différences, nous proposons de formuler ces transformations rigides dans un cadre purement discret. Dans ce cadre, les transformations rigides sont regroupées en classes correspondant chacune à une transformation digitale donnée. De plus, les relations entre ces classes de transformations peuvent être modélisées par une structure de graphe. Nous prouvons que ce graphe présente une complexité spatiale polynômiale par rapport à la taille de l'image. Il présente également des propriétés structurelles intéressantes. En particulier, il permet de générer de manière progressive toute transformation rigide digitale, et ce sans approximation numérique. Cette structure constitue un outil théorique pour l'étude des relations entre la géométrie et la topologie dans le contexte de l'imagerie numérique. Elle présente aussi un intérêt méthodologique, comme l'illustre son utilisation pour l'évaluation du comportement topologique des images sous des transformations rigides
In this thesis, we study rigid transformations in the context of computer imagery. In particular, we develop a fully discrete framework for handling such transformations. Rigid transformations, initially defined in the continuous domain, are involved in a wide range of digital image processing applications. In this context, the induced digital rigid transformations present different geometrical and topological properties with respect to their continuous analogues. In order to overcome the issues raised by these differences, we propose to formulate rigid transformations on digital images in a fully discrete framework. In this framework, Euclidean rigid transformations producing the same digital rigid transformation are put in the same equivalence class. Moreover, the relationship between these classes can be modeled as a graph structure. We prove that this graph has a polynomial space complexity with respect to the size of the considered image, and presents useful structural properties. In particular, it allows us to generate incrementally all digital rigid transformations without numerical approximation. This structure constitutes a theoretical tool to investigate the relationships between geometry and topology in the context of digital images. It is also interesting from the methodological point of view, as we illustrate by its use for assessing the topological behavior of images under rigid transformations

Les algorithmes procurent de nombreux services dans le domaine de l'agriculture et de l'alimentation. Ils facilitent l'accès à l'information et constituent d'indéniables outils d'aide à la décision. Alliés à la robotique et au machinisme, ils peuvent réduire la pénibilité du travail et l'empreinte écologique de l'agriculture. Si leur utilité n'est plus à démontrer, il n'en reste pas moins vrai que l'omniprésence et l'essor considérable des algorithmes engendrent des interrogations quant aux évolutions et risques associés relativement à l'indépendance des utilisateurs, l'uniformisation des règles de décision, l'exacerbation de certaines inégalités voire les transformations du métier d'agriculteur. Au final, il apparait que l'important n'est pas de persister dans une vision manichéenne des algorithmes (entre «~facilitateur~» et «~asservisseur~») mais de parier sur l'intelligence de l'être humain pour les utiliser de manière pertinente et non en «~aveugle~» pour les utilisateurs et en «~dominateur~» pour les concepteurs. Espérons qu'une telle utilisation intelligente des algorithmes ne soit pas une utopie.