• Refine Query
  • Source
  • Publication year
  • to
  • Language
  • 17
  • 8
  • 1
  • Tagged with
  • 28
  • 5
  • 5
  • 4
  • 4
  • 4
  • 3
  • 3
  • 3
  • 3
  • 3
  • 3
  • 3
  • 2
  • 2
  • About
  • The Global ETD Search service is a free service for researchers to find electronic theses and dissertations. This service is provided by the Networked Digital Library of Theses and Dissertations.
    Our metadata is collected from universities around the world. If you manage a university/consortium/country archive and want to be added, details can be found on the NDLTD website.
21

Approche algébrique sur l'équivalence de codes. / Algebraic Approach for Code Equivalence

Saeed, Mohamed Ahmed 18 December 2017 (has links)
Le problème d’´équivalence de code joue un rôle important dans la théorie de code et la cryptographie basée sur le code. Cela est dû à son importance dans la classification des codes ainsi que dans la construction et la cryptanalyse des cryptosystèmes à base de codes. Il est également lié à un problème ouvert d’isomorphisme de graphes, un problème bien connu dans le domaine de la théorie de la complexité. Nous prouvons pour les codes ayant un hull trivial qu’il existe une réduction polynomiale de l’équivalence par permutation de codes à l’isomorphisme de graphes. Cela montre que cette sous-classe d’équivalence de permutation n’est pas plus dure que l’isomorphisme de graphes. Nous introduisons une nouvelle méthode pour résoudre le problème d’équivalence de code. Nous développons des approches algébriques pour résoudre le problème dans ses deux versions : en permutation et en diagonale. Nous construisons un système algébrique en établissant des relations entre les matrices génératrices et les matrices de parité des codes équivalents. Nous nous retrouvons avecun système plusieurs variables d’équations linéaires et quadratiques qui peut être résolu en utilisant des outils algébriques tels que les bases de Groebner et les techniques associées. Il est possible en théorie de résoudre l’équivalence de code avec des techniques utilisant des bases de Groebner. Cependant, le calcul en pratique devient complexe à mesure que la longueur du code augmente. Nous avons introduit plusieurs améliorations telles que la linéarisation par bloc et l’action de Frobenius. En utilisant ces techniques, nous identifions de nombreux cas où le problème d’équivalence de permutation peut être résolu efficacement. Notre méthode d’équivalence diagonale résout efficacement le problème dans les corps de petites tailles, à savoir F3 et F4. L’augmentation de la taille du corps entraîne une augmentation du nombre de variables dans notre système algébrique, ce qui le rend difficile à résoudre. Nous nous intéressons enfin au problème d’isomorphisme de graphes en considérant un système algébrique quadratique pour l’isomorphisme de graphes. Pour des instances tirées aléatoirement, le système possède des propriétés intéressantes en termes de rang de la partie linéaire et du nombre de variables. Nousrésolvons efficacement le problème d’isomorphisme de graphes pour des graphes aléatoires avec un grand nombre de sommets, et également pour certains graphes réguliers tels que ceux de Petersen, Cubical et Wagner.123 / Code equivalence problem plays an important role in coding theory and code based cryptography.That is due to its significance in classification of codes and also construction and cryptanalysis of code based cryptosystems. It is also related to the long standing problem of graph isomorphism, a well-known problem in the world of complexity theory. We introduce new method for solving code equivalence problem. We develop algebraic approaches to solve the problem in its permutation and diagonal versions. We build algebraic system by establishing relations between generator matrices and parity check matrices of the equivalent codes. We end up with system of multivariables of linear and quadratic equations which can be solved using algebraic tools such as Groebner basis and related techniques. By using Groebner basis techniques we can solve the code equivalence but the computation becomes complex as the length of the code increases. We introduced several improvements such as block linearization and Frobenius action. Using these techniques we identify many cases where permutation equivalence problem can be solved efficiently. Our method for diagonal equivalence solves the problem efficiently in small fields, namely F3 and F4. The increase in the field size results in an increase in the number of variables in our algebraic system which makes it difficult to solve. We introduce a new reduction from permutation code equivalence when the hull is trivial to graph isomorphism. This shows that this subclass of permutation equivalence is not harder than graph isomorphism.Using this reduction we obtain an algebraic system for graph isomorphism with interesting properties in terms of the rank of the linear part and the number of variables. We solve the graph isomorphism problem efficiently for random graphs with large number of vertices and also for some regular graphs such as Petersen, Cubical and Wagner Graphs.
22

Réseaux de capteurs sans fil efficaces en énergie / Energy-centric wireless sensor networks

Bramas, Quentin 04 October 2016 (has links)
Les réseaux de capteurs sans fil sont constitués de noeuds capteurs, capables de récolter des données, de les analyser et de les transmettre. Ces réseaux ont plusieurs applications, en fonction de la zone où ils sont déployés. Application militaire ou de sauvetage dans des zones pouvant être inaccessibles aux humains ; application sanitaire avec des capteurs déployés sur et dans le corps humain ; application de surveillance avec des capteurs sur les voitures d'un ville, ou les arbres d'une forêt. Les noeuds sont autonomes en énergie et il est primordial d'assurer leur longévité sans retarder la récolte des données. La tache principale réalisée par les réseaux de capteurs sans fils consiste à effectuer des mesures et à envoyer ces données jusqu'à un noeud coordinateur. Cette tache d'agrégation est effectuée régulièrement, ce qui en fait la plus consommatrice d'énergie. L'étude approfondie de la consommation d'énergie des capteurs, qui au centre de ma thèse, peut se traduire de différentes manières. Premièrement, nous avons étudié la complexité du problème de l'agrégation de données en utilisant un modèle simplifié pour représenter un réseau de capteurs sans fils. Secondement, nous nous sommes concentrés sur l'estimation de cette durée de vie. Nous présentons WiSeBat, un modèle de batterie et de consommation d'énergie optimisé pour les réseaux de capteurs, implémenté dans le simulateur WSNET. Après validation, nous l'utilisons pour comparer les performances des algorithmes de broadcast efficaces en énergie. / A wireless sensor network is an ad-hoc network connecting small devices equipped with sensors. Such networks are self-organized and independent of any infrastructure. The deployment of a WSN is possible in areas inaccessible to humans, or for applications with a long lifetime requirement. Indeed, devices in a wireless sensor network are usually battery-powered, tolerate failure, and may use their own communication protocols, allowing them to optimize the energy consumption. The main application of WSNs it to sense the environment at different locations and aggregate all the data to a specific node that logs it and can send alerts if necessary. This task of data aggregation is performed regularly, making it the most energy consuming. As reducing the energy consumed by sensor is the leading challenge to ensure sustainable applications, we tackle in this thesis the problem of aggregating efficiently the data of the network. Then, we study lifetime evaluation techniques and apply it to benchmark existing energy-centric protocols.
23

On temporal coherency of probabilistic models for audio-to-score alignment / Modèles probabilistes temporellement cohérents pour l'alignement audio-sur-partition

Cuvillier, Philippe 15 December 2016 (has links)
Cette thèse porte sur l'alignement automatique d'un enregistrement audio avec la partition de musique correspondante. Nous adoptons une approche probabiliste et proposons une démarche théorique pour la modélisation algorithmique de ce problème d'alignement automatique. La question est de modéliser l'évolution temporelle des événements par des processus stochastiques. Notre démarche part d'une spécificité de l'alignement musical : une partition attribue à chaque événement une durée nominale, qui est une information a priori sur la durée probable d'occurrence de l'événement. La problématique qui nous occupe est celle de la modélisation probabiliste de cette information de durée. Nous définissons la notion de cohérence temporelle à travers plusieurs critères de cohérence que devrait respecter tout algorithme d'alignement musical. Ensuite, nous menons une démarche axiomatique autour du cas des modèles de semi-Markov cachés. Nous démontrons que ces critères sont respectés lorsque des conditions mathématiques particulières sont vérifiées par les lois a priori du modèle probabiliste de la partition. Ces conditions proviennent de deux domaines mathématiques jusqu'ici étrangers à la question de l'alignement : les processus de Lévy et la totale positivité d'ordre deux. De nouveaux résultats théoriques sont démontrés sur l'interrelation entre ces deux notions. En outre, les bienfaits pratiques de ces résultats théoriques sont démontrés expérimentalement sur des algorithmes d'alignement en temps réel. / This thesis deals with automatic alignment of audio recordings with corresponding music scores. We study algorithmic solutions for this problem in the framework of probabilistic models which represent hidden evolution on the music score as stochastic process. We begin this work by investigating theoretical foundations of the design of such models. To do so, we undertake an axiomatic approach which is based on an application peculiarity: music scores provide nominal duration for each event, which is a hint for the actual and unknown duration. Thus, modeling this specific temporal structure through stochastic processes is our main problematic. We define temporal coherency as compliance with such prior information and refine this abstract notion by stating two criteria of coherency. Focusing on hidden semi-Markov models, we demonstrate that coherency is guaranteed by specific mathematical conditions on the probabilistic design and that fulfilling these prescriptions significantly improves precision of alignment algorithms. Such conditions are derived by combining two fields of mathematics, Lévy processes and total positivity of order 2. This is why the second part of this work is a theoretical investigation which extends existing results in the related literature.
24

Méthode de conception de systèmes temps réels embarqués multi-coeurs en milieu automobile / Methodology of designing embedded real-time multi-core systems in automotive

Klikpo, Enagnon Cédric 13 March 2018 (has links)
La complexité croissante des applications embarquées dans les voitures modernes augmente le besoin de puissance de calcul. Pour répondre à ce besoin, le standard automobile AUTOSAR introduit l'utilisation de plates-formes multi-cœurs. Cependant, l'utilisation du multi-cœurs pour des applications temps-réel critique automobile soulève plusieurs problématiques. Notamment, il faut respecter la spécification fonctionnelle et garantir de manière déterministe les échanges de données entre cœurs. Dans cette thèse, nous considérons des systèmes multi-périodiques spécifiés et validés fonctionnellement avec des modèles Matlab/Simulink. Ainsi, nous avons développé un framework pour déployer des applications Matlab/Simulink sur AUTOSAR multi-cœurs afin de garantir le déterminisme fonctionnel et temporel tout en exploitant au mieux le parallélisme. Notre contribution a porté sur trois axes. Premièrement nous avons identifié les mécanismes d'échanges de données imposés dans le modèle fonctionnel Matlab/Simulink. Nous avons montré que ces mécanismes pouvaient s'exprimer en utilisant le formalisme des Synchronous Dataflow Graph (SDFG). Ce modèle est un excellent outil d'analyse pour exploiter le parallélisme car il est très populaire dans la littérature et largement étudié pour le déploiement d'applications flow de données sur plateforme multi/many-cœurs. Par la suite, nous avons développé des méthodes pour réaliser le flux de données exprimés par le SDFG dans un ordonnancement temps-réel préemptif. Ces méthodes utilisent des résultats théoriques sur les SDFGs pour garantir les contraintes de précédence de manière déterministe sans utiliser des mécanismes de synchronisation bloquants. De cette sorte, nous garantissons à la fois le déterminisme fonctionnel et temporel des applications. Finalement, nous caractérisons l'impact des contraintes de flux de données sur l'ordonnancement des tâches. Nous proposons une technique de partitionnement qui minimise cet impact. Nous montrons alors que cette technique favorise la construction d'un partitionnement et d'un ordonnancement lorsqu'elle est utilisée pour initialiser des algorithmes de recherche et d'optimisation heuristiques. / The increasing complexity of embedded applications in modern cars has increased the need of computing power. To meet this need, the European automotive standard AUTOSAR has introduced the use of \multicore platforms. However, \multicore platform for critical automotive applications raises several issues. In particular, it is necessary to respect the functional specification and to guarantee deterministically the data exchanges between cores. In this thesis, we consider multi-periodic systems specified and validated with \mat. So, we developed a framework to deploy \mat applications on AUTOSAR \multicore. This framework guarantees the functional and temporal determinism and exploits the parallelism. Our contribution is threefold. First, we identify the communication mechanisms in \mat. Then, we prove that the dataflow in a multi-periodic \mat system is modeled by a SDFG. The SDFG formalism is an excellent analysis tool to exploit the parallelism. In fact, it is very popular in the literature and it is widely studied for the deployment of dataflow applications on multi/many-core. Then, we develop methods to realize the dataflow expressed by the SDFG in a preemptive \rt scheduling. These methods use theoretical results on SDFGs to guarantee deterministic precedence constraints without using blocking synchronization mechanisms. As such, both the functional and temporal determinism are guaranteed. Finally, we characterize the impact of dataflow requirements on tasks. We propose a partitioning technique that minimizes this impact. We show that this technique promotes the construction of a partitioning and a feasible scheduling when it is used to initiate multi-objective research and optimization algorithms. %As such, we reduce the number of design iterations and shorten the design time.
25

Algorithmes et Bornes minimales pour la Synchronisation Temporelle à Haute Performance : Application à l’internet des objets corporels / Algorithms and minimum bounds for high performance time synchronization : Application to the wearable Internet of Things

Nasr, Imen 23 January 2017 (has links)
La synchronisation temporelle est la première opération effectuée par le démodulateur. Elle permet d'assurer que les échantillons transmis aux processus de démodulation puissent réaliser un taux d'erreurs binaires le plus faible.Dans cette thèse, nous proposons l'étude d'algorithmes innovants de synchronisation temporelle à haute performance.D'abord, nous avons proposé des algorithmes exploitant l'information souple du décodeur en plus du signal reçu afin d'améliorer l'estimation aveugle d'un retard temporel supposé constant sur la durée d'observation.Ensuite, nous avons proposé un algorithme original basé sur la synchronisation par lissage à faible complexité.Cette étape a consisté à proposer une technique opérant dans un contexte hors ligne, permettant l'estimation d'un retard aléatoire variable dans le temps via les boucles d'aller-retour sur plusieurs itération. Les performances d'un tel estimateur dépassent celles des algorithmes traditionnels.Afin d'évaluer la pertinence de tous les estimateurs proposés, pour des retards déterministe et aléatoire, nous avons évalué et comparé leurs performances à des bornes de Cramèr-Rao que nous avons développées pour ce cadre. Enfin, nous avons évalué les algorithmes proposés sur des signaux WBAN. / Time synchronization is the first function performed by the demodulator. It ensures that the samples transmitted to the demodulation processes allow to achieve the lowest bit error rate.In this thesis we propose the study of innovative algorithms for high performance time synchronization.First, we propose algorithms exploiting the soft information from the decoder in addition to the received signal to improve the blind estimation of the time delay. Next, we develop an original algorithm based on low complexity smoothing synchronization techniques. This step consisted in proposing a technique operating in an off-line context, making it possible to estimate a random delay that varies over time on several iterations via Forward- Backward loops. The performance of such estimators exceeds that of traditional algorithms. In order to evaluate the relevance of all the proposed estimators, for deterministic and random delays, we evaluated and compared their performance to Cramer-Rao bounds that we developed within these frameworks. We, finally, evaluated the proposed algorithms on WBAN signals.
26

Une approche par composants pour l'analyse visuelle interactive de résultats issus de simulations numériques / A component-based approach for interactive visual analysis of numerical simulation results

Ait Wakrime, Abderrahim 10 December 2015 (has links)
Les architectures par composants sont de plus en plus étudiées et utilisées pour le développement efficace des applications en génie logiciel. Elles offrent, d’un côté, une architecture claire aux développeurs, et de l’autre, une séparation des différentes parties fonctionnelles et en particulier dans les applications de visualisation scientifique interactives. La modélisation de ces applications doit permettre la description des comportements de chaque composant et les actions globales du système. De plus, les interactions entre composants s’expriment par des schémas de communication qui peuvent être très complexes avec, par exemple, la possibilité de perdre des messages pour gagner en performance. Cette thèse décrit le modèle ComSA (Component-based approach for Scientific Applications) qui est basé sur une approche par composants dédiée aux applications de visualisation scientifique interactive et dynamique formalisée par les réseaux FIFO colorés stricts (sCFN). Les principales contributions de cette thèse sont dans un premier temps, un ensemble d’outils pour modéliser les différents comportements des composants ainsi que les différentes politiques de communication au sein de l’application. Dans un second temps, la définition de propriétés garantissant un démarrage propre de l’application en analysant et détectant les blocages. Cela permet de garantir la vivacité tout au long de l’exécution de l’application. Finalement l’étude de la reconfiguration dynamique des applications d’analyse visuelle par ajout ou suppression à la volée d’un composant sans arrêter toute l’application. Cette reconfiguration permet de minimiser le nombre de services non disponibles. / Component-based approaches are increasingly studied and used for the effective development of the applications in software engineering. They offer, on the one hand, safe architecture to developers, and on the other one, a separation of the various functional parts and particularly in the interactive scientific visualization applications. Modeling such applications enables the behavior description of each component and the global system’s actions. Moreover, the interactions between components are expressed through a communication schemes sometimes very complex with, for example, the possibility to lose messages to enhance performance. This thesis describes ComSA model (Component-based approach for Scientific Applications) that relies on a component-based approach dedicated to interactive and dynamic scientific visualization applications and its formalization in strict Colored FIFO Nets (sCFN). The main contributions of this thesis are, first, the definition of a set of tools to model the component’s behaviors and the various application communication policies. Second, providing some properties on the application to guarantee it starts properly. It is done by analyzing and detecting deadlocks. This ensures the liveness throughout the application execution. Finally, we present dynamic reconfiguration of visual analytics applications by adding or removing on the fly of a component without stopping the whole application. This reconfiguration minimizes the number of unavailable services.
27

A framework for efficient execution on GPU and CPU+GPU systems / Framework pour une exécution efficace sur systèmes GPU et CPU+GPU

Dollinger, Jean-François 01 July 2015 (has links)
Les verrous technologiques rencontrés par les fabricants de semi-conducteurs au début des années deux-mille ont abrogé la flambée des performances des unités de calculs séquentielles. La tendance actuelle est à la multiplication du nombre de cœurs de processeur par socket et à l'utilisation progressive des cartes GPU pour des calculs hautement parallèles. La complexité des architectures récentes rend difficile l'estimation statique des performances d'un programme. Nous décrivons une méthode fiable et précise de prédiction du temps d'exécution de nids de boucles parallèles sur GPU basée sur trois étapes : la génération de code, le profilage offline et la prédiction online. En outre, nous présentons deux techniques pour exploiter l'ensemble des ressources disponibles d'un système pour la performance. La première consiste en l'utilisation conjointe des CPUs et GPUs pour l'exécution d'un code. Afin de préserver les performances il est nécessaire de considérer la répartition de charge, notamment en prédisant les temps d'exécution. Le runtime utilise les résultats du profilage et un ordonnanceur calcule des temps d'exécution et ajuste la charge distribuée aux processeurs. La seconde technique présentée met le CPU et le GPU en compétition : des instances du code cible sont exécutées simultanément sur CPU et GPU. Le vainqueur de la compétition notifie sa complétion à l'autre instance, impliquant son arrêt. / Technological limitations faced by the semi-conductor manufacturers in the early 2000's restricted the increase in performance of the sequential computation units. Nowadays, the trend is to increase the number of processor cores per socket and to progressively use the GPU cards for highly parallel computations. Complexity of the recent architectures makes it difficult to statically predict the performance of a program. We describe a reliable and accurate parallel loop nests execution time prediction method on GPUs based on three stages: static code generation, offline profiling, and online prediction. In addition, we present two techniques to fully exploit the computing resources at disposal on a system. The first technique consists in jointly using CPU and GPU for executing a code. In order to achieve higher performance, it is mandatory to consider load balance, in particular by predicting execution time. The runtime uses the profiling results and the scheduler computes the execution times and adjusts the load distributed to the processors. The second technique, puts CPU and GPU in a competition: instances of the considered code are simultaneously executed on CPU and GPU. The winner of the competition notifies its completion to the other instance, implying the termination of the latter.
28

Simulation and optimization models for scheduling and balancing the public bicycle-sharing systems / Modéles de simulation et d'optimisation pour l'ordonnancement et l'équilibrage des systèmes de vélos en libre-service

Kadri, Ahmed Abdelmoumene 11 December 2015 (has links)
Les enjeux du développement durable, le réchauffement climatique, la pollution dans les grandes villes, la congestion et les nuisances sonores, l'augmentation des prix de carburants, sont parmi des nombreux facteurs qui incitent les pays développés à l'innovation dans les transports publics. Dans ce contexte, l'introduction des systèmes de vélos en libre-service, au cours de ces dernières années, est une des solutions adoptées par de nombreuses grandes villes. Malgré leur succès fulgurant dans le monde entier, il existe peu d'études fondamentales sur ce type transport urbain. Pourtant, leur exploitation et leur management par des opérateurs soulèvent de nombreuses questions notamment d'ordre opérationnel. Dans ce contexte, cette thèse s'adresse aux problèmes d'ordonnancement et de rééquilibrage des stations de vélos en libre-service. Ce sont des problèmes cruciaux pour la qualité de service et la viabilité économique de tels systèmes. Le rééquilibrage consiste à redistribuer le nombre de vélos entre les différentes stations afin de satisfaire au mieux les demandes des usagers. Cette régulation se fait souvent par le biais de véhicules spécifiques qui font des tournées autour des différentes stations. Ainsi, deux problèmes d'optimisation difficiles se posent : la recherche de la meilleure tournée du véhicule de régulation (ordonnancement de la tournée) et la détermination des nombres de véhicules à utiliser (rééquilibrage des stations). Dans cette optique, les travaux de cette thèse constituent une contribution à la modélisation et à l'optimisation de performances des systèmes de vélos en libre-service en vue de leur rééquilibrage et leur ordonnancement. Plusieurs méthodes d'optimisation et ont été développées et testées. De telles méthodes incorporent différentes approches de simulation ou d'optimisation comme les réseaux de Petri, les algorithmes génétiques, les algorithmes gloutons, les algorithmes de recherche par voisinage, la méthode arborescente de branch-and-bound, l'élaboration des bornes supérieures et inférieures, etc. Différentes facettes du problème ont été étudiées : le cas statique, le cas dynamique, l'ordonnancement et le rééquilibrage avec un seul (ou multiple) véhicule(s). Afin de montrer la pertinence de nos approches, la thèse comporte également plusieurs applications réelles et expérimentations / In our days, developed countries have to face many public transport problems, including traffic congestion, air pollution, global oil prices and global warming. In this context, Public Bike sharing systems are one of the solutions that have been recently implemented in many big cities around the world. Despite their apparent success, the exploitation and management of such transportation systems imply crucial operational challenges that confronting the operators while few scientific works are available to support such complex dynamical systems. In this context, this thesis addresses the scheduling and balancing in public bicycle-sharing systems. These problems are the most crucial questions for their operational efficiency and economic viability. Bike sharing systems are balanced by distributing bicycles from one station to another. This procedure is generally ensured by using specific redistribution vehicles. Therefore, two hard optimization problems can be considered: finding a best tour for the redistribution vehicles (scheduling) and the determination of the numbers of bicycles to be assigned and of the vehicles to be used (balancing of the stations). In this context, this thesis constitutes a contribution to modelling and optimizing the bicycle sharing systems' performances in order to ensure a coherent scheduling and balancing strategies. Several optimization methods have been proposed and tested. Such methods incorporate different approaches of simulation or optimization like the Petri nets, the genetic algorithms, the greedy search algorithms, the local search algorithms, the arborescent branch-and-bound algorithms, the elaboration of upper and lower bounds, ... Different variants of the problem have been studied: the static mode, the dynamic mode, the scheduling and the balancing by using a single or multiple vehicle(s). In order to demonstrate the coherence and the suitability of our approaches, the thesis contains several real applications and experimentations

Page generated in 0.3846 seconds