Trees are said to be unordered if the order between successor nodes of a given node is not important. Unranked trees are trees which do not have a priori bound on the number of successors of each node of the tree. Unranked and unordered trees are a possible model for semistructured data. The advantage of this model is that it is less dependant on the representation of semistructured data as XML documents, and the drowback is that formalisms (tree automata, logics) for manipulating this kind of trees are generally related with worse complexity results compared with similar formalisms for unranked and ordered trees. Our aim is a theoretical study of some logics for unranked and unordered trees, espetially from the point of view of using it as query languages for semistructured data. Thus, we are interested in the model checking problem and its complexity, in the satisfiability problem and in caracterising the expressive power of these logics. The model checking problem is, given a tree and a logic formula, to decide whether the trees satisfies the formula; model checking is the mecanism used for query evaluation. The satisfiability problem is, given a logic formula, to decide whether this formula admits some models; satisfiability can be used for query optimisation. Finally, caracterisation of the expressive power of a logic is a caracterisation of the kind of properties it can express. We start from a spatial logic which has been introduced as the basis of a query language for semistructured data. This logic is quite expressive and has several kinds of operators. We consider different fragments of this logic. We identify several interesting fragments of the logic for which the satisfiability problem is decidable, when this problem is known to be undecidable for other fragments. We compare fragments of the logic with monadic second order logic on trees and extensions of it. Finally, studying the model checking problem and its complexity allowed us to propose a model checking algorithm and to establish several results on theoretic complexity of model checking for several fragments of the spatial logic.

Les systèmes embarqués temps réel nécessitent une analyse temporelle pour valider leur comportement temporel.Afin de réduire le coût de développement, l'analyse doit être effectuée à une phase précoce au moment de la modélisationpour détecter les anomalies de conception. L'analyse d'ordonnançabilité est une des analyses temporelles qui permettentde s'assurer du bon fonctionnement du système conçu. Elle est issue de la théorie de l'ordonnancement temps réel.Plusieurs méthodes et tests analytiques ont été proposés par la communauté académique mais peu sont les tests adoptéspar les industriels. En effet, l'utilisation des tests d'analyse exige une large connaissance des travaux de recherches - misà jour régulièrement - afin de choisir la méthode la plus adaptée aux systèmes conçus pour les valider ou les dimensionnerpour le cas des systèmes qui sont en cours de conception.Cette thèse s'intéresse à cette utilisation minimaliste de la théorie de l'ordonnancement dans l'industrie, et propose dessolutions d'aide à la décision basées sur l'ingénierie dirigée par les modèles. Nos solutions visent à augmenter l'applicabilitéde la théorie de l'ordonnancement, à faciliter le choix des tests appropriés et à réduire le surdimensionnement qui peutêtre généré au moment de la conception. Ces solutions sont implémentées dans un Framework appelé MoSaRT offrantdes fonctionnalités pour les concepteurs (modeleurs et analystes) afin d'améliorer le processus de conception des systèmestemps réel en vue de leur ordonnançabilité.

This thesis studies logics which express properties on programs. These logics were originally intended for the formal verification of programs with pointers. Overall, no automated verification method will be proved tractable here- rather, we give a new insight on separation logic. The complexity and decidability of some essential fragments of this logic for Hoare triples were not known before this work. Also, its combination with some other verification methods was little studied. Firstly, in this work we isolate the operator of separation logic which makes it undecidable. We describe the expressive power of this logic, comparing it to second-order logics. Secondly, we try to extend decidable subsets of separation logic with a temporal logic, and with the ability to describe data. This allows us to give boundaries to the use of separation logic. In particular, we give boundaries to the creation of decidable logics using this logic combined with a temporal logic or with the ability to describe data.

Infrastructure as a service (IaaS) Cloud platforms are increasingly used in the IT industry. IaaS platforms are providers of virtual resources from a catalogue of predefined types. Improvements in virtualization technology make it possible to create and destroy virtual machines on the fly, with a low overhead. As a result, the great benefit of IaaS platforms is the ability to scale a virtual platform on the fly, while only paying for the used resources. From a research point of view, IaaS platforms raise new questions in terms of making efficient virtual platform scaling decisions and then efficiently scheduling applications on dynamic platforms. The current thesis is a step forward towards exploring and answering these questions. The first contribution of the current work is focused on resource management. We have worked on the topic of automatically scaling cloud client applications to meet changing platform usage. There have been various studies showing self-similarities in web platform traffic which implies the existence of usage patterns that may or may not be periodical. We have developed an automatic platform scaling strategy that predicted platform usage by identifying non-periodic usage patterns and extrapolating future platform usage based on them. Next we have focused on extending an existing grid platform with on-demand resources from an IaaS platform. We have developed an extension to the DIET (Distributed Interactive Engineering Toolkit) middleware, that uses a virtual market based approach to perform resource allocation. Each user is given a sum of virtual currency that he will use for running his tasks. This mechanism help in ensuring fair platform sharing between users. The third and final contribution targets application management for IaaS platforms. We have studied and developed an allocation strategy for budget-constrained workflow applications that target IaaS Cloud platforms. The workflow abstraction is very common amongst scientific applications. It is easy to find examples in any field from bioinformatics to geology. In this work we have considered a general model of workflow applications that comprise parallel tasks and permit non-deterministic transitions. We have elaborated two budget-constrained allocation strategies for this type of workflow. The problem is a bi-criteria optimization problem as we are optimizing both budget and workflow makespan. This work has been practically validated by implementing it on top of the Nimbus open source cloud platform and the DIET MADAG workflow engine. This is being tested with a cosmological simulation workflow application called RAMSES. This is a parallel MPI application that, as part of this work, has been ported for execution on dynamic virtual platforms. Both theoretical simulations and practical experiments have shown encouraging results and improvements.

Dans cette thèse, nous définissons une nouvelle classe de graphes : les graphes hypotriangulés. Les graphes hypotriangulés vérifient que pour tout chemin de longueur deux, il existe une arête ou un autre chemin de longueur deux entre ses extrémités. Cette classe permet par exemple de modéliser des réseaux robustes. En effet, nous montrons que dans de tels graphes, la suppression d'une arête ou d'un sommet ne modifie pas la distance initiale entre toutes paires de sommets non adjacents. Ensuite, nous étudions et démontrons plusieurs propriétés pour cette classe de graphes. En particulier, après avoir introduit une famille de partitions spécifiques, nous montrons les relations entre certains éléments de cette famille et leur caractère hypotriangulé. De plus, grâce à ces partitions, nous caractérisons les graphes hypotriangulés minimum, qui, parmi les graphes hypotriangulés connexes, minimisent le nombre d'arêtes pour un nombre de sommets fixés.Dans une deuxième partie, nous étudions la complexité, pour la classe des graphes hypotriangulés, de problèmes difficiles dans le cas général. Nous montrons d'abord que les problèmes classiques de cycle hamiltonien, coloration, clique maximum et stable maximum restent NP-difficiles pour cette classe de graphes. Ensuite, nous nous intéressons à des problèmes de modification de graphes, pour lesquels il s'agit de déterminer le nombre minimal d'arêtes à ajouter ou supprimer à un graphe pour obtenir un graphe hypotriangulé : nous montrons la complexité de ces problèmes pour plusieurs classes de graphes.

With the development of the computer networks, mainly the Internet, it became easier to develop applications where the execution is shared between a local computer, the Client, and one located on the other side of the network communication channel, the Server. The hardware advancements in the recent years made it possible to display 3D graphics (games, map navigation, virtual worlds) on mobile devices. However, executing these complex applications on the client terminal is not possible without reducing the quality of the displayed graphics or lowering its processing requirements. Different solutions have already been proposed in academic publications; however none of them satisfies all requirements. The objective of this thesis is to propose an alternative solution for a new client-server architecture where the connectedness of the mobile devices is fully exploited. Several main requirements are addressed: - Minimize the network traffic, - Reduce the required computational power on the terminal, and - Preserve the user experience compared with local execution. First a formal framework is designed that can effectively define and model distributed applications for 3D graphics. Then a model of new architecture is presented, that overcomes the disadvantages of the architectures presented in the state of the art. The core of the architecture is the MPEG-4 standard, which is used to transfer the data between the server and the client in a compressed manner. The last part of explores the design of architectures optimized for running on mobile devices. The design of the new client-server architecture is validated by implementing a game and running simulations.

Lorsqu'un enseignant veut évaluer le savoir-faire des apprenants à l'aide d'un logiciel, il utilise souvent les systèmes Tutoriels Intelligents (STI). Or, les STI sont difficiles à développer et destinés à un domaine pédagogique très ciblé. Depuis plusieurs années, l'utilisation d'algorithmes de classification par apprentissage supervisé a été proposée pour évaluer le savoir des apprenants. Notre hypothèse est que ces mêmes algorithmes vont aussi nous permettre d'évaluer leur savoir-faire. Notre domaine d'application étant l'électronique numérique, nous proposons une mesure de similarité entre schémas électroniques et une bas d'apprentissage générée automatiquement. cette base d'apprentissage est composées de schémas électroniques pédagogiquement étiquetés "bons" ou "mauvais" avec des informations concernant le degré de simplification des erreurs commises. Finalement, l'utilisation d'un algorithme de classification simple (les k plus proches voisins) nous a permis de faire une évaluation des schémas électroniques dans la majorité des cas.

La programmation par contraintes est un paradigme de résolution des problèmes combinatoires sur lequel ont été bâtis des outils génériques de résolution, des solveurs. De nombreuses recherches sont menées pour élargir le champ d'application de ces outils µa des problèmes dynamiques et sur-contraints. Un axe prometteur s'appuie sur la notion d'explications. Les explications constituent une trace explicite du comportement du solveur et ont été initialement introduites pour améliorer les algorithmes de recherche arborescente. Depuis ce jour, elles ont ouvert la voie à des méthodes d'exploration plus intelligentes (mais aussi plus coûteuses) de l'espace de recherche. Cette thèse porte sur l'élaboration d'algorithmes de résolution s'appuyant sur la notion d'explications et les étudie sur des problèmes autant académiques qu'industriels. D'une part, nous examinons l'intérêt des explications dans le cadre de techniques génériques de décomposition. La mise au point d'un tel algorithme dans le contexte d'ordonnancement temps réel a montré la souplesse de la technique pour permettre la coopération de méthodes analytiques pointues avec un solveur de contraintes. D'autre part, nous montrons que le réseau d'explication constitue une information particulièrement pertinente pour révéler à un utilisateur les structures ou relations entretenues par différents éléments (variables/contraintes) du problème. Cette information, également exploitable dynamiquement par le solveur est un pas supplémentaire vers des approches de résolution génériques. Enfin, les explications ont été jusqu'ici très utilisées dans un cadre rétrospectif et pourraient l'être davantage dans un cadre prospectif (à l'image de leur exploitation par la communauté SAT). Nous revenons ainsi dans cette thèse sur des techniques de nogoods recording dans le cadre du problème de MOSP (Minimum Open Stack Problem).

Optimisation des tournées de véhicules dans le cadre de la logistique inverse : modélisation et résolution par des méthodes hybrides

Se basant sur les avancées techniques et scientifiques dans les domaines des systèmes d'information géographique et des indicateurs sociaux et environnementaux, l'objectif de cette thèse est de contribuer au développement d'un outil informatique d'aide à l'identification et à l'évaluation de variantes de tracés routiers. Le rôle du bureau d'étude en aménagement dans la conduite des projets routiers, ses besoins en matière de développement d'outil et les méthodes d'évaluation préexistantes sont d'abord présentés. On étudie ensuite les possibilités d'automatisation du traitement des données géographiques de l'aire d'étude d'un projet, permettant de faire ressortir les zones les plus propices à l'insertion de tronçons routiers (sur la base des fonctionnalités du logiciel ArcGIS). Afin d'améliorer et approfondir l'évaluation des variantes et d'aider à la sélection entre tracés, des indicateurs nouveaux relatifs aux effets globaux et locaux des tronçons routiers, sont proposés. Ils concernent les impacts environnementaux de type d'analyse de cycle de vie, la fragmentation des écosystèmes, la sécurité des transports, le patrimoine, les nuisances sonores, la co-visibilité et le rayonnement. Leur applicabilité et leur pertinence sont testées dans la comparaison de variantes d'un projet réel. Afin de répondre aux besoins du processus de concertation, une méthode interactive de combinaison des indicateurs est proposée. Enfin, les potentialités de développement de ces fonctions sous forme d'outil opérationnel pour le bureau d'étude, sont discutées.