Spelling suggestions: "subject:"IT (forminformation 1echnology)"" "subject:"IT (forminformation 1technology)""
1 |
Introducing privacy in current web search engines / Introduction de la confidentialité dans les moteurs de recherche Web actuelsPetit, Albin 15 March 2017 (has links)
Au cours des dernières années les progrès technologiques permettant de collecter, stocker et traiter d'importantes quantités de données pour un faible coût, ont soulevés de sérieux problèmes concernant la vie privée. La protection de la vie privée concerne de nombreux domaines, en particulier les sites internet fréquemment utilisés comme les moteurs de recherche (ex. : Google, Bing, Yahoo!). Ces services permettent aux utilisateurs de retrouver efficacement du contenu sur Internet en exploitant leurs données personnelles. Dans ce contexte, développer des solutions pour permettre aux utilisateurs d'utiliser ces moteurs de recherche tout en protégeant leurs vies privées est devenu primordial. Dans cette thèse, nous introduirons SimAttack, une attaque contre les solutions protégeant la vie privée de l'utilisateur dans ses interactions avec les moteurs de recherche. Cette attaque vise à retrouver les requêtes initialement envoyées par l'utilisateur. Nous avons montré avec cette attaque que trois mécanismes représentatifs de l’état de l’art ne sont pas satisfaisants pour protéger la vie privée des utilisateurs. Par conséquent, nous avons développé PEAS, un nouveau mécanisme de protection qui améliore la protection de la vie privée de l'utilisateur. Cette solution repose sur deux types de protection : cacher l'identité de l'utilisateur (par une succession de deux serveurs) et masquer sa requête (en la combinant avec des fausses requêtes). Afin de générer des fausses requêtes réalistes, PEAS se base sur les précédentes requêtes envoyées par les utilisateurs du système. Pour finir, nous présenterons des mécanismes permettant d'identifier la sensibilité des requêtes. Notre objectif est d'adapter les mécanismes de protection existants pour protéger uniquement les requêtes sensibles, et ainsi économiser des ressources (ex. : CPU, mémoire vive). Nous avons développé deux modules pour identifier les requêtes sensibles. En déployant ces modules sur des mécanismes de protection existants, nous avons établi qu'ils permettent d'améliorer considérablement leurs performances. / During the last few years, the technological progress in collecting, storing and processing a large quantity of data for a reasonable cost has raised serious privacy issues. Privacy concerns many areas, but is especially important in frequently used services like search engines (e.g., Google, Bing, Yahoo!). These services allow users to retrieve relevant content on the Internet by exploiting their personal data. In this context, developing solutions to enable users to use these services in a privacy-preserving way is becoming increasingly important. In this thesis, we introduce SimAttack an attack against existing protection mechanism to query search engines in a privacy-preserving way. This attack aims at retrieving the original user query. We show with this attack that three representative state-of-the-art solutions do not protect the user privacy in a satisfactory manner. We therefore develop PEAS a new protection mechanism that better protects the user privacy. This solution leverages two types of protection: hiding the user identity (with a succession of two nodes) and masking users' queries (by combining them with several fake queries). To generate realistic fake queries, PEAS exploits previous queries sent by the users in the system. Finally, we present mechanisms to identify sensitive queries. Our goal is to adapt existing protection mechanisms to protect sensitive queries only, and thus save user resources (e.g., CPU, RAM). We design two modules to identify sensitive queries. By deploying these modules on real protection mechanisms, we establish empirically that they dramatically improve the performance of the protection mechanisms.
|
2 |
Fluxional compiler : Seamless shift from development productivity to performance efficiency, in the case of real-time web applications / Compilateur Fluxional : Passage transparent de la productivité de développement à l'efficacité des performances, dans le cas d'applications Web en temps réelBrodu, Etienne 21 June 2016 (has links)
La plupart des grands services web commencèrent comme de simples projets, et grossirent exponentiellement. Internet supporte cette croissance en étendant les communications et réduisant leur latence. Pendant son développement, une application doit croître exponentiellement, sans quoi elle risque de se faire dépasser par la compétition. Dès le début, il est important de s'assurer de répondre aux besoins du marché : Fail fast. Des langages comme Ruby ou Java sont devenus populaires en proposant la productivité nécessaire pour itérer rapidement sur les retours utilisateurs. Une application web qui répond correctement aux besoins des utilisateurs peut être adoptée de manière virale. Mais à terme, une application doit être efficace pour traiter cette augmentation de trafic. Il est difficile pour une application d'être à la fois productive et efficace. Quand l'audience devient trop importante, il est souvent nécessaire de remplacer l'approche productive pour un modèle plus efficace. Aucune plateforme de développement ne permet de concilier ces deux objectifs, il est donc nécessaire de réécrire l'application vers un modèle plus efficace, tel qu'un pipeline. Ce changement représente un risque. Il implique une quantité de travail conséquente et incertaine. Pour éviter ce risque, cette thèse propose de maintenir conjointement les représentations productives et efficaces d'une même application. Javascript est un langage productif avec une communauté importante. C'est l’environnement d’exécution le plus largement déployé puisqu'il est omniprésent dans les navigateurs, et également sur certains serveurs avec Node.js. Il est maintenant considéré comme le langage principal du web, détrônant Ruby ou Java. De plus, sa boucle évènementielle est similaire à un pipeline. Ces deux modèles d’exécution traitent un flux de requêtes en chaînant des fonctions les unes après les autres. Cependant, la boucle évènementielle permet une approche productive grâce à sa mémoire globale, tandis que le pipeline permet une exécution efficace du fait de sa parallélisation. Cette thèse étudie la possibilité pour une équivalence de transformer une implémentation d'une représentation vers l'autre. Avec cette équivalence, l'équipe de développement peut suivre les deux approches simultanément. Elle peut itérer continuellement pour prendre en compte les avantages des deux approches. Cette thèse présente un compilateur qui permet d'identifier un pipeline dans une application Javascript, et d'isoler chaque étape dans une fluxion. Une fluxion est nommée par contraction entre fonction et flux. Elle exécute une fonction pour chaque datum sur le flux. Les fluxions sont indépendantes, et peuvent être déplacées d'une machine à l'autre pour amortir l'augmentation du trafic. L'équipe de développement peut commencer à développer avec la productivité de la boucle évènementielle. Et avec la transformation, elle peut itérer pour progressivement atteindre l’efficacité du pipeline. / Most of the now popular web services started as small projects created by few individuals, and grew exponentially. Internet supports this growth because it extends the reach of our communications world wide, while reducing their latency. During its development, an application must grow exponentially, otherwise the risk is to be outpaced by the competition. In the beginning, it is important to verify quickly that the service can respond to the user needs: Fail fast. Languages like Ruby or Java became popular because they propose a productive approach to iterate quickly on user feedbacks. A web application that correctly responds to user needs can become viral. Eventually, the application needs to be efficient to cope with the traffic increase. But it is difficult for an application to be at once productive and efficient. When the user base becomes too important, it is often required to switch the development approach from productivity to efficiency. No platform conciliates these two objectives, so it implies to rewrite the application into an efficient execution model, such as a pipeline. It is a risk as it is a huge and uncertain amount of work. To avoid this risk, this thesis proposes to maintain the productive representation of an application with the efficient one. Javascript is a productive language with a significant community. It is the execution engine the most deployed, as it is present in every browser, and on some servers as well with Node.js. It is now considered as the main language of the web, ousting Ruby or Java. Moreover, the Javascript event-loop is similar to a pipeline. Both execution models process a stream of requests by chaining independent functions. Though, the event-loop supports the needs in development productivity with its global memory, while the pipeline representation allows an efficient execution by allowing parallelization. This thesis studies the possibility for an equivalence to transform an implementation from one representation to the other. With this equivalence, the development team can follow the two approaches concurrently. It can continuously iterate the development to take advantage of their conflicting objectives. This thesis presents a compiler that allows to identify the pipeline from a Javascript application, and isolate its stages into fluxions. A fluxion is named after the contraction between function and flux. It executes a function for each datum on a stream. Fluxions are independent, and can be moved from one machine to the other, so as to cope with the increasing traffic. The development team can begin with the productivity of the event-loop representation. And with the transformation, it can progressively iterate to reach the efficiency of the pipeline representation.
|
3 |
The impact of triadic strategic alignment on organisational performance in YemenAl-Surmi, Abdulrahman Mohamed January 2016 (has links)
To survive and succeed in the very competitive business environment, firms should have a clear business strategy supported by appropriate information technology (IT) and marketing strategies. Whilst many prior studies argue that strategic alignment between, for example, business strategy and IT strategy generally enhances organisational performance, strategic alignment including multiple factors has received little attention and strategic orientation of firms is rarely considered. This research, drawing on configurational theory and strategic management literature, aims to understand the performance impact of triadic strategic alignment between business, IT, and marketing strategies based on strategic orientation of firms. A number of hypotheses are proposed to examine the relationship between triadic strategic alignment and organisational performance through the use of structural equation modelling, and to identify generic types of triadic strategic alignment. The hypotheses are tested through MANOVA using data collected in a questionnaire survey of 242 managers in Yemen. The findings indicate that (1) there is an ideal triadic strategic alignment for prospectors and defenders; (2) triadic strategic alignment has a positive impact on organisational performance; and (3) triadic strategic alignment provides a better indication of the nature and performance impact of strategic alignment. Follow-up interviews were also conducted to support the arguments and to clarify how strategies should be aligned. This research also contributes to managers’ knowledge and understanding by suggesting how a firm should coherently align its strategies to improve organisational performance.
|
4 |
Performance monitoring of throughput constrained dataflow programs executed on shared-memory multi-core architectures / Evaluation de performance d'applications flot de données executées sur des architectures multi-coeurSelva, Manuel 02 July 2015 (has links)
Les progrès continus de la microélectronique couplés au problème de gestion de la puissance dissipée ont conduit les fabricants de processeurs à se tourner vers des puces dites multi-coeurs au début des années 2000. Ces processeurs sont composés de plusieurs unités de calcul indépendantes. Contrairement aux progrès précédents ces architectures multi-coeurs, le logiciel doit être en grande parti repensé pour tirer parti de toutes les unités de calcul. Il faut pouvoir paralléliser une application séquentielle en tâches le plus indépendantes possibles pour pouvoir les exécuter sur différentes unités de calcul. Pour cela, de nombreux modèles de programmations dits concurrents ont été proposés. Dans cette thèse nous nous intéressons aux programmes décrits à l’aide du modèle dataflow. Ce travail porte sur l’évaluation des performances de programmes dataflow (forme que revêtent typiquement des applications de types traitement de flux vidéos ou protocoles de communication) sur des architectures multi-coeurs. Plus particulièrement, le sujet de la thèse porte sur l’extension de modèles de programmation dataflow avec des éléments d’expression de propriétés de qualité de service ainsi que la prise en compte de ces éléments pour détecter, à l’exécution, les goulots d’étranglement de performance au sein des programmes. Les informations concernant les goulots d'étranglements collectées pendant l'exécution sont utilisées à la fois pour faire de l'analyse hors-ligne et pour faire des adaptations pendant l'exécution des programmes. Dans le premier cas, le programmeur utilise ces informations pour savoir quelles parties du programme dataflow il faut optimiser et pour savoir comment distribuer efficacement le programme sur les unités de calcul. Dans le second cas, les informations collectées sont utilisées par des mécanismes d'adaptation automatique afin de redistribuer le travail sur les différentes unités de calcul de façon plus efficace. Nous portons une attention particulière au profiling de l'utilisation faite par les applications dataflow du système mémoire. Les informations sur les échanges de données fournies par le modèle de programmation permettent d'exploiter de façon intelligente les architectures mémoires des machines multi-coeurs. Néanmoins, la complexité de ces dernières ne permet pas de façon générale d'évaluer statiquement l'impact sur les performances des accès mémoires. Nous proposons donc la mise en place d'un système de profiling mémoire pour des applications dataflow basé sur des mécanismes matériels. / Because of physical limits, hardware designers have switched to parallel systems to exploit the still growing number of transistors per square millimeter of silicon. These parallel systems are made of several independent computing units. To benefit from these computing units, software must be changed. Existing sequential applications have to be split into independent tasks to be executed in parallel on the different computing units. To that end, many concurrent programming models have been proposed and are in use today. We focus in this thesis on the dataflow concurrent programming model. This work is about performance evaluation of dataflow programs on multicore architectures. We propose to extend dataflow programming models with the notion of throughput constraints and to take this information into account in the compilation tool chain to detect at runtime the throughput bottlenecks. The profiling results gathered during the execution are used both for off-line analyzes and to adapt the application during its execution. In the former case, the developer uses this information to know which part of the dataflow program should be optimized and to efficiently distribute the program on the computing units. In the later case, the profiling information is used by runtime adaptation mechanisms to distribute differently the work on the computing units. We give a particular focus on the profiling of the usage of the memory subsystem. The data exchange information provide by the programming model allows to efficiently used the memory subsystem of multicore architectures. Nevertheless, the complexity of modern memory systems doesn't allow to statically evaluate the impact of memory accesses on the global performances of the application. We propose to set up memory profiling dedicated to dataflow applications based on hardware profiling mechanisms.
|
5 |
Compression progressive de maillages surfaciques texturés / Porgressive compression of surface textured meshesCaillaud, Florian 17 January 2017 (has links)
Depuis plusieurs années, les modèles 3D deviennent de plus en plus détaillés. Cela augmente considérablement le volume de données les décrivant. Cependant, dans un même temps, un nombre croissant d’applications sont contraintes en mémoire et/ou en vitesse (visualisation sur périphériques mobiles, jeux vidéos, etc.). Dans un contexte Web, ces difficultés sont encore plus présentes. Cette situation peut entraîner des incompatibilités, des latences de transmission ou d’affichage qui sont souvent problématiques. La compression progressive de ces modèles est une des solutions envisageables. Le but étant de compresser les informations (géométrie, connectivité et attributs associés) de façon à pouvoir reconstruire progressivement le maillage. À la différence d’une compression dite single-rate, la compression progressive propose très rapidement un aperçu fidèle du modèle 3D pour ensuite le raffiner jusqu’à retrouver le maillage complet. Ceci permet un meilleur confort pour l’utilisateur et une adaptation de la quantité d’éléments à visualiser ou à traiter en fonction des capacités du périphérique de réception. Généralement, les approches existantes pour la compression progressive se focalisent sur le traitement de maillages 2-variétés triangulaires. Très peu de méthodes sont capables de compresser progressivement des maillages surfaciques non-variétés et, à notre connaissance, aucune ne permet de compresser génériquement un maillage surfacique quel que soit son type (i.e. non-variété et polygonal). Pour supprimer ces limitations, nous présentons une méthode de compression progressive générique permettant de traiter l’ensemble des maillages surfaciques (non-variétés et polygonaux). De plus, notre approche tient compte de l’attribut de texture potentiellement associé à ces maillages, en gérant correctement les coutures éventuelles. Pour ce faire, nous décimons progressivement le maillage à l’aide d’un nouvel opérateur générique de simplification. Cette décimation est guidée par une métrique locale qui a pour but de préserver la géométrie et la paramétrisation de la texture. Durant cette simplification, nous encodons progressivement les informations nécessaires à la reconstruction. Afin d’améliorer le taux de compression, nous mettons en oeuvre certains procédés de réduction de l’entropie, ainsi que des dispositifs de prédiction basés sur la géométrie pour l’encodage de la connectivité et des coordonnées de texture. Pour finir, l’image de texture est compressée progressivement puis multiplexée avec les données relatives au maillage. Ce multiplexage est réalisé à l’aide d’une métrique perceptuelle afin d’obtenir le meilleur rapport débit-distorsion possible lors de la décompression. / Since several years, 3D models become more and more detailed. This increases substantially the amount of data needed to describe them. However, in the same time, a rising number of applications are constrained in memory and/or in speed (mobile device visualization, video games, etc.). These difficulties are even more visible within a Web context. This situation can lead to incompatibilities, latency in transmission or rendering, which is generally an issue. The progressive compression of these models is a possible solution. The goal is to compress the information (geometry, connectivity and associated attributes) in order to allow a progressive reconstruction of the mesh. Contrary to a single-rate compression, progressive compression quickly proposes a faithful draft of the 3D model and, then, refines it until the complete mesh is recovered. This allows a better comfort for the user and a real adaptation of the rendered element number in adequacy with the terminal device properties. The existing approaches for progressive compression mainly focus on triangular 2- manifold meshes. Very few methods are able to compress progressively non-manifold surface meshes and, to our knowledge, none can deal with every surface meshes (i.e. nomanifold and polygonal), in a generic way. So as to suppress these limitations, we present a new generic progressive method allowing the compression of polygonal non-manifold surface meshes. Moreover, our approach takes care of the texture attribute, possibly associated to these meshes, by handling properly potential texture seams. For that purpose, we progressively decimate the mesh using a new generic simplification operator. This decimation is driven by a local metric which aims to preserve both the geometry and the texture parametrisation. During the simplification, we progressively encode the necessary information for the reconstruction. In order to improve the compression rate, we propose several entropy reduction mechanisms, as well as geometry based prediction strategies for the connectivity and UV coordinates encoding. Finally, the texture map is progressively compressed then multiplexed with mesh data. This multiplexing is achieved using a perceptual metric to provide the best rate-distortion ratio as possible during the decompression.
|
6 |
A constraint programming approach for the time dependent traveling salesman problem / Une approche de programmation par contraintes du problème du voyageur de commerce dépendant du tempsMelgarejo, Penélope Aguiar 16 December 2016 (has links)
L'optimisation des tournées de livraison est souvent modélisée par un problème de voyageur de commerce (Traveling Salesman Problem / TSP). Pour ce problème, il est fréquent d’avoir des contraintes additionnelles telles que, par exemple, des fenêtres horaires limitant les heures de livraison chez le client ou des pauses obligatoires pour les conducteurs des camions. Le temps est une dimension importante à prendre en compte pour respecter ces contraintes. Cependant, les durées des trajets ne sont généralement pas constantes mais varient en fonction des congestions, et cette variabilité doit être intégrée au moment de l’optimisation des tournées. Ainsi, le problème du voyageur de commerce dépendant du temps (Time Dependent TSP / TD-TSP) est la version étendue du TSP où le coût d'un arc dépend de l'heure à laquelle cet arc est emprunté. Dans cet thèse nous proposons un nouveau benchmark pour le TD-TSP basé sur des données réelles de trafic (fournies par la Métropole de Lyon) et nous montrons l'intérêt de prendre en compte la variabilité des durées dans ce problème. Nous étudions comment mieux modéliser les fonctions de durée de trajet dépendantes du temps. Nous introduisons et comparons différents modèles pour résoudre le TD-TSP avec la programmation par contraintes (Constraint Programming / CP). Un premier modèle est directement dérivé du modèle CP classique pour le TSP. Nous montrons que ce modèle ne permet pas de raisonner avec des relations de précédence indirectes, ce qui pénalise sa performance sur notre benchmark. Nous introduisons une nouvelle contrainte globale qui est capable d'exploiter des relations de précédence indirectes sur des données dépendantes du temps et nous introduisons un nouveau modèle CP basé sur notre nouvelle contrainte. Nous comparons expérimentalement les deux modèles sur notre benchmark, et nous montrons que notre nouvelle contrainte permet de résoudre le TD-TSP plus efficacement. / In the context of urban deliveries, the optimization of delivery tours is usually modeled as a Traveling Salesman Problem (TSP). Side constraints like time-windows constraining the delivery times at the client or breaks for the drivers are also common in this kind of problem and time is an important dimension to take into account to respect these constraints. With travel times' variability in big cities time also tends to have a greater influence in costs and therefore it should be included in the optimization of delivery routes. The Time-Dependent Traveling Salesman Problem (TDTSP) is the extended version of the Traveling Salesman Problem (TSP) where arc costs depend on the time when the arc is traveled. In this thesis we propose a set of benchmarks for the TDTSP based on real traffic data (obtained from the city of Lyon) and show the interest of handling time dependency in the problem. A study of how to better model time-dependent travel functions in general and specifically for our approach is performed. We introduce and compare different models to solve the TDTSP with Constraint Programming (CP). A first model is derived in a straightforward way from the classical CP model for the TSP. We show that this model is not able to reason on indirect precedence relations, so that it has poor performance on our benchmark. We introduce a new global constraint which is able to exploit indirect precedence relations on time-dependent data, and we introduce a second model which is based on our new constraint. We experimentally compare the two models on our benchmark.
|
7 |
An investigation of the process and characteristics used by project managers in IT consulting in the selection of project management softwareMeyer, Eike January 2018 (has links)
As project management (PM) and information technology (IT) evolved over the last decades, an increasing number of project management software products have emerged. Project managers in IT consulting can improve the success of projects through the utilization of such software. However, the diversity of software available cannot sensibly be grasped by a single individual. Based on this context, the study aims to examine the key considerations in the selectionof project management software in IT consulting from the project managers' perspective. A literature review identifies key aspects of IT consulting projects that may be relevant to the software selection. No evidence was found that provided a view on the process of the selection of PM software in IT consulting itself. The review also unveils the lack of common terminology in regard to PM software. The study addresses these gaps by utilizing interpretative phenomenological analysis (IPA) to understand the experiences made by project managers. To gather data, 17 semistructured interviews were conducted with experienced project managers. Thematic analysis was used to develop an understanding of the process employed by project managers in the software selection and the considerations they make along the way. The findings were synthesized to create a process guide, supported by a checklist and the working definition of key terminology. This study adds a broader perspective to the field of PM software through the application of qualitative methodology in an otherwise quantitatively dominated field of research. It addresses the lack of existing knowledge on the perspective of the project manager in the selection process through the generation of a 6-staged process guide. The detailed considerations of project managers were compiled into a checklist of selection criteria. These two also contribute to practice by providing a structured approach to PM selection for practitioners. The third output is a working definition of project management software as used in practice, which simplifies an exchange of knowledge between theory and practice.
|
8 |
Lärare och digitala verktyg i matematikundervisningen : En kvantitativ studie om lärares inställning och kompetens kring användningen av digitala verktyg i årskurserna F-3 / Primary school teachers and digital tools in mathematics education : A quantitative study on teachers' attitudes and competence in the use of digital tools in grade F-3Ekman, Britteli January 2015 (has links)
The purpose of this study is to examine in what extent primary school teachers, teaching children in the age of 6 to 9, choose to use digital tools in their teaching of mathematics. I also want to examine what these teachers think, in terms of advantages and disadvantages, about using digital tools on their mathematics lessons. Finally I want to examine what skills they possess about digital tools. I am using a quantitative method to collect my data. The quantitative survey consisted of a questionnaire survey of ten questions that 38 primary school teachers have answered. The results of my study show that the teachers to some extent use digital tools when they teach mathematics and that the availability of various digital tools are generally good. But it turns out that the availability of tools is not a guarantee that they are used in teaching of mathematics. There is a great desire among the teachers in my study to use digital tools with greater frequency than in the current situation because it increases students' learning and motivation. To achieve this, the teachers need more resources such as skills, time and student computers / tablet computers.
|
9 |
Návrh implementace systému řízení vztahů se zákazníky / Proposal of Customer Relationship Management ImplementationOškrdová, Petra January 2009 (has links)
This diploma thesis is concerned with proposal and analysis new database software helping by CRM system for already exists foreign company, which has own branch office in Czech Republic. There is current database system deficient in the company. There is necessary to propose the new software, which will be operating more effectively.
|
10 |
Configuration automatique d’un solveur générique intégrant des techniques de décomposition arborescente pour la résolution de problèmes de satisfaction de contraintes / Automatic configuration of generic solver embedding tree-decomposition techniques for solving constraint satisfaction problemsBlet, Loïc 30 September 2015 (has links)
La programmation par contraintes intègre des algorithmes de résolution génériques dans des langages de modélisation déclaratifs basés sur les contraintes : ces langages permettent de décrire des problèmes combinatoires sous la forme d’un ensemble de variables devant prendre leurs valeurs dans des domaines en satisfaisant des contraintes. Nous introduisons dans cette thèse un algorithme de résolution générique paramétré par : — une stratégie d’exploration de l’espace de recherche, à choisir parmi, chronological backtracking, conflict directed backjumping, conflict directed backjumping with reordering, dynamic backtracking, decision repair, et backtracking with tree decomposition ; — une heuristique de choix de variables, à choisir parmi, min-domain/ddeg et min-domain/wdeg ; — une technique de propagation de contraintes, à choisir parmi, forward checking et maintaining arc consistency. Ainsi, cet algorithme générique s’instancie en vingt-quatre configurations différentes ; certaines correspondant à des algorithmes connus, d’autres étant nouvelles. Ces vingt- quatre configurations ont été comparées expérimentalement sur un benchmark de plus de mille instances, chaque configuration étant exécutée plusieurs fois sur chaque instance pour tenir compte du non déterminisme des exécutions. Des tests statistiques sont utilisés pour comparer les performances. Cette évaluation expérimentale a permis de mieux comprendre la complémentarité des différents mécanismes de résolution, avec une attention particulière portée sur la capacité à tirer parti de la structure des instances pour accélérer la résolution. Nous identifions notamment treize configurations complémentaires telles que chaque instance de notre benchmark est bien résolue par au moins une des treize configurations. Une deuxième contribution de la thèse est d’introduire un sélecteur capable de choisir automatiquement la meilleure configuration de notre algorithme générique pour chaque nouvelle instance à résoudre : nous décrivons chaque instance par un ensemble de descripteurs et nous utilisons des techniques d’apprentissage automatique pour construire un modèle de choix de configuration à partir de ces descripteurs. Sachant que l’apprentissage est généralement plus difficile quand il y a beaucoup de configurations, nous exprimons le problème du choix du sous-ensemble de configurations pouvant être sélectionnées comme un problème de couverture d’ensemble et nous comparons deux critères de choix : le premier vise à maximiser le nombre d’instances résolues par au moins une configuration et le second vise à maximiser le nombre d’instances pour lesquelles il y a une bonne configuration disponible. Nous montrons expérimentalement que la seconde stratégie obtient généralement de meilleurs résultats, et que le sélecteur obtient de meilleures performances que chacune de nos vingt-quatre configurations initiales. / Constraint programming integrates generic solving algorithms within declarative languages based on constraints : these languages allow us to describe combinatorial problems as a set of variables which have to take their values in domains while satisfying constraints. Numerous real-life problems can be modelled in such a way, as for instance, planification problems, scheduling problems, . . . These problems are NP-complete in the general case of finite domains. We introduce in this work a generic solving algorithm parameterized by : — a strategy for exploring the search space, to be chosen from the following six, chronological backtracking, conflict directed backjumping, conflict directed backjumping with reordering, dynamic backtracking, decision repair, and backtracking with tree decomposition ; — a variable ordering heuristic, to be chosen from the following two, min-domain/ddeg and min-domain/wdeg ; — a constraint propagation technique, to be chosen from the following two, forward checking and maintaining arc consistency. Thus, this algorithm leads to 24 different configurations ; some corresponding to already known algorithms, others being new. These 24 configurations have been com- pared experimentally on a benchmark of more than a thousand instances, each configuration being executed several times to take into account the non-determinism of the executions, and a statistical test has been used to compare performances. This experimental evaluation allowed us to better understand the complementarity of the different solving mechanisms, with a focus on the ability to exploit the structure of the instances to speed up the solving process. We identify 13 complementary configurations such that every instance of our benchmark is well solved by at least one of the 13 configurations. A second contribution of this work is to introduce a selector able to choose automatically the best configuration of our generic solver for each new instance to be solved : we describe each instance by a set of features and we use machine learning techniques to build a model to choose a configuration based on these features. Knowing that the learning process is generally harder when there are many configurations to choose from, we state the problem of choosing a subset of configurations that can be picked as a set covering problem and we compare two criterion : the first one aims to maximize the number of instances solved by at least one configuration and the second one aims to maximize the number of instances for which there is a good configuration available. We show experimentally that the second strategy obtains generally better results and that the selector obtains better performances than each of the 24 initial configurations.
|
Page generated in 0.1047 seconds