Spelling suggestions: "subject:"base dde données"" "subject:"base dee données""
1 |
De la conception d'un système d'observation à large échelle au déploiement et à l'exploitation de son système d'information : application à l'observation des habitats coralligènes et à la colonisation de récifs artificiels (ARMS) / From designing a large-scale observation system to deploying and operating its information system : application to the observation of coralligenous habitats and the colonization of artificial reefs (ARMS)David, Romain 06 July 2018 (has links)
Dans le domaine marin, des protocoles d’observation développés dans de nombreux cadres produisent un grand volume de données hétérogènes, difficiles à agréger et à utiliser. Ce travail propose i) des méthodes, protocoles et recommandations pour construire et/ou soutenir la mise en place de réseaux de suivis multi-usagers,) des utilisations novatrices des données.Deux cas d’étude ont été choisis : les habitats coralligènes à l’échelle de la Méditerranée et la colonisation de récifs artificiels dans différentes mers régionales.L’expérimentation à large échelle se base sur des méthodes de mesures les plus simples possibles, décrites très explicitement dans des termes standardisés, sur des opérateurs intercalibrés et une méthode de traitement des données. Un mécanisme de couplage de données de différentes origines reposant sur la requalification des facteurs descriptifs hétérogènes et une méthode d’analyse et de fouille de données basé sur la théorie des graphes sont proposées. / In the marine domain, observation protocols developed in many settings produce a large volume of heterogeneous data that are difficult to aggregate and use. This work proposes to develop i) methods, protocols and recommendations to build and / or support the establishment of multi-user monitoring networks, ii) innovative uses of data.Two case studies were chosen: coralligenous habitats at the Mediterranean scale and the colonisation of artificial reefs in different regional seas.Large-scale experimentation is based on the simplest possible measurement methods, described very explicitly in standardised terms, on intercalibrated operators and a method of data processing. A mechanism for coupling data from different origins based on the requalification of heterogeneous descriptive factors and a method for analysis and data mining based on graph theory is also proposed.
|
2 |
Knowledge flows through patent citation dataPillu, Hugo 18 December 2009 (has links) (PDF)
Dans cette thèse, nous analysons les différents aspects des externalités de connaissance et la façon dont les citations de brevet peuvent être utilisées comme un indicateur de ces flux. La première partie de cette thèse examine la littérature traditionnelle sur les externalités de connaissance, et cela d'un point de vue à la fois qualitatif et quantitatif (la forme quantitative est réalisée grâce à une méta-analyse). Nous insistons sur les conséquences résultant de l'utilisation de différents canaux de mesure de ces externalités, précisément nous nous attardons sur les hypothèses sous-jacentes et sur leurs implications en termes d'estimations empiriques. Ce point est important car ces canaux sont la principale source d'hétérogénéité des résultats empiriques. Dans la seconde partie, nous explorons des données de brevets et de citations de brevet encore peu étudiées (ces données sont extraites de la base de données Patstat pour les offices de brevets du G5, de l'OEB et de l'OMPI). Cette analyse est à nouveau réalisée à la fois en termes qualitatifs et quantitatifs. La troisième partie, dans un premier temps, examine de façon empirique les caractéristiques des flux de connaissance entre et au sein des inventeurs des pays du G5 et cela pour 13 secteurs industriels. Dans un deuxième temps, cette partie propose et valide la création d'un indicateur de stocks de connaissance qui prend en compte les externalités de connaissance internationales. Cet indicateur se révèle particulièrement utile puisque les indicateurs traditionnels ne sont pas toujours disponibles (comme les indicateurs basés sur les dépenses de R&D). Enfin, l'indicateur précédemment créé sera appliqué à une étude de cas consacrée à l'analyse des déterminants de l'innovation pour les technologies énergétiques efficientes.
|
3 |
Decidability and complexity of simulation preorder for data-centric Web services / Décidabilité et complexité de la relation de simulation des services Web orientés donnéesAkroun, Lakhdar 08 December 2014 (has links)
Dans cette thèse nous nous intéressons au problème d’analyse des spécifications des protocoles d’interactions des services Web orientés données. La spécification de ce type de protocoles inclut les données en plus de la signature des opérations et des contraintes d’ordonnancement des messages. L’analyse des services orientés données est complexe car l’exécution d’un service engendre une infinité d’états. Notre travail se concentre autour du problème d’existence d’une relation de simulation quand les spécifications des protocoles des services Web sont représentés en utilisant un système à transition orienté données. D’abord nous avons étudié le modèle Colombo [BCG+05]. Dans ce modèle, un service (i) échange des messages en utilisant des variables ; (ii) modifie une base de donnée partagée ; (iii) son comportement est modélisé avec un système à transition. Nous montrons que tester l’existence de la relation de simulation entre deux services Colombo non bornée est indécidable. Puis, nous considérons le cas où les services sont bornés. Nous montrons pour ce cas que le test de simulation est (i) exptime-complet pour les services Colombo qui n’accèdent pas à la base de donnée (noté ColomboDB=∅), et (ii) 2exptime-complet quand le service peut accéder à une base de donnée bornée (Colombobound). Dans la seconde partie de cette thèse, nous avons défini un modèle générique pour étudier l’impact de différents paramètres sur le test de simulation dans le contexte des services Web orientés données. Le modèle générique est un système à transition gardé qui peut lire et écrire à partir d’une base de donnée et échanger des messages avec son environnement (d’autres services ou un client). Dans le modèle générique toutes les actions sont des requêtes sur des bases de données (modification de la base de données, messages échangés et aussi les gardes). Dans ce contexte, nous avons obtenu les résultats suivant : (i) pour les services gardés sans mise à jour, le test de simulation est caractérisé par rapport à la décidabilité du test de satisfiabilité du langage utilisé pour exprimer les gardes augmenté avec une forme restrictive de négation, (ii) pour les services sans mise à jour mais qui peuvent envoyer comme message le résultat d’une requête, nous avons trouvé des conditions suffisantes d’indécidabilité et de décidabilité par rapport au langage utilisé pour exprimer l’échange de messages, et (iii) nous avons étudié le cas des services qui ne peuvent que insérer des tuples dans la base de donnée. Pour ce cas, nous avons étudié la simulation ainsi que la weak simulation et nous avons montré que : (a) la weak simulation est indécidable quand les requêtes d’insertion sont des requêtes conjonctives, (b) le test de simulation est indécidable si la satisfiabilité du langage de requête utilisé pour exprimer les insertions augmenté avec une certaine forme de négation est indécidable. Enfin, nous avons étudié l’interaction entre le langage utilisé pour exprimer les gardes et celui utilisé pour les insertions, nous exhibons une classe de service où la satisfiabilité des deux langages est décidable alors que le test de simulation entre les services qui leur sont associés ne l’est pas. / In this thesis we address the problem of analyzing specifications of data-centric Web service interaction protocols (also called data-centric business protocols). Specifications of such protocols include data in addition to operation signatures and messages ordering constraints. Analysis of data-centric services is a complex task because of the inherently infinite states of the underlying service execution instances. Our work focuses on characterizing the problem of checking a refinement relation between service interaction protocol specifications. More specifically, we consider the problem of checking the simulation preorder when service business protocols are represented using data-centric state machines. First we study the Colombo model [BCG+05]. In this framework, a service (i) exchanges messages using variables; (ii) acts on a shared database; (iii) has a transition based behavior. We show that the simulation test for unbounded Colombo is undecidable. Then, we consider the case of bounded Colombo where we show that simulation is (i) exptime-complete for Colombo services without any access to the database (noted ColomboDB=∅), and (ii) 2exptime-complete when only bounded databases are considered (the obtained model is noted Colombobound). In the second part of this thesis, we define a generic model to study the impact of various parameters on the simulation test in the context of datacentric services. The generic model is a guarded transition system acting (i.e., read and write) on databases (i.e., local and shared) and exchanging messages with its environment (i.e., other services or users). The model was designed with a database theory perspective, where all actions are viewed as queries (i.e modification of databases, messages exchanges and guards). In this context, we obtain the following results (i) for update free guarded services (i.e., generic services with guards and only able to send empty messages) the decidability of simulation is fully characterized w.r.t decidability of satisfiability of the query language used to express the guards augmented with a restrictive form of negation, (ii) for update free send services (i.e., generic services without guards and able to send as messages the result of queries over local and shared database), we exhibit sufficient conditions for both decidability and undecidability of simulation test w.r.t the language used to compute messages payloads, and (iii) we study the case of insert services (i.e., generic services without guards and with the ability of insert the result of queries into the local and the shared database). In this case, we study the simulation as well as the weak simulation relations where we show that: (i) the weak simulation is undecidable when the insertions are expressed as conjunctive queries, (ii) the simulation is undecidable if satisfiability of the query language used to express the insertion augmented with a restricted form of negation is undecidable. Finally, we study the interaction between the queries used as guards and the ones used as insert where we exhibit a class of services where satisfiability of both languages is decidable while simulation is undecidable.
|
4 |
Knowledge flows through patent citation data / Les flux de connaissances à travers les données de citations de brevetPillu, Hugo 18 December 2009 (has links)
Dans cette thèse, nous analysons les différents aspects des externalités de connaissance et la façon dont les citations de brevet peuvent être utilisées comme un indicateur de ces flux. La première partie de cette thèse examine la littérature traditionnelle sur les externalités de connaissance, et cela d'un point de vue à la fois qualitatif et quantitatif (la forme quantitative est réalisée grâce à une méta-analyse). Nous insistons sur les conséquences résultant de l'utilisation de différents canaux de mesure de ces externalités, précisément nous nous attardons sur les hypothèses sous-jacentes et sur leurs implications en termes d'estimations empiriques. Ce point est important car ces canaux sont la principale source d'hétérogénéité des résultats empiriques. Dans la seconde partie, nous explorons des données de brevets et de citations de brevet encore peu étudiées (ces données sont extraites de la base de données Patstat pour les offices de brevets du G5, de l'OEB et de l'OMPI). Cette analyse est à nouveau réalisée à la fois en termes qualitatifs et quantitatifs. La troisième partie, dans un premier temps, examine de façon empirique les caractéristiques des flux de connaissance entre et au sein des inventeurs des pays du G5 et cela pour 13 secteurs industriels. Dans un deuxième temps, cette partie propose et valide la création d'un indicateur de stocks de connaissance qui prend en compte les externalités de connaissance internationales. Cet indicateur se révèle particulièrement utile puisque les indicateurs traditionnels ne sont pas toujours disponibles (comme les indicateurs basés sur les dépenses de R&D). Enfin, l'indicateur précédemment créé sera appliqué à une étude de cas consacrée à l'analyse des déterminants de l'innovation pour les technologies énergétiques efficientes. / In this dissertation, we analyze the different aspects of knowledge spillovers with special emphasis on the use of patent citations as an indicator of knowledge flows. The first part of the thesis reviews the traditional knowledge spillovers literature both with a qualitative and a quantitative view (the quantitative form is done through a meta-analysis). A particular focus is placed on the consequences of using the different channels reflecting different weighted functions, i.e. about the underlying assumptions and the implications in terms of estimates. This point is important since these channels are the main source of heterogeneity in the analysis of knowledge spillovers. In the second part, we shed some light on patent and patent citation data that have not been much studied (taken from the Patstat database for the G5 patent offices plus the EPO and the WIPO). Once again this analysis is conducted both in qualitative and quantitative terms. The third part, in a first time, investigates empirically the diffusion pattern of knowledge between and within the G5 inventors for 13 manufacturing sectors. In a second time, it proposes and validates the creation of an input-based indicator of knowledge that takes into account international knowledge spillovers. This indicator can be very helpful since traditional indicators are not always available (such as R&D indicators). Finally, the previously created indicator will be applied in a case study dedicated to analyze the determinants of innovation for energy efficient technologies.
|
5 |
Tissue database of autofluorescence response to improve intra-operative diagnosis of primitive brain tumors / Base de données sur le signal d'autofluorescence des tissus pour améliorer le diagnostic per-opératoire des tumeurs cérébralesPoulon, Fanny 26 September 2018 (has links)
Le premier traitement standard pour les tumeurs cérébrales est la résection chirurgicale. Dans cette procédure un enjeu important demeure, l'identification des berges tumorales pour assurer une résection totale et éviter le risque de récidive pour le patient. A ce jour aucune technique d'imagerie peropératoire est capable de résoudre l'infiltration tumorale du tissu sain. La norme pour le diagnostic des berges tumorales est l'analyse histologique des biopsies. Une méthode ex vivo qui requiert un à plusieurs jours pour fournir ler apport pathologique final, un lapse de temps qui peut s'avérer fatal pour le patient. La microscopie optique a récemment été développer vers une utilisation clinique peropératoire pour répondre à cet enjeu. Dans travail, la technique de microscopie à deux-photons a été préférée pouressayer de répondre à cette problématique. Cette méthode donne accès à deux contrastes d'imagerie, la génération de seconde harmonique et l’émission de fluorescence, qui peuvent être combinés à des mesures quantitatives, tel que la spectroscopie et le temps de vie de fluorescence. Combiner ces quatre modalités de détection donnera une information complète sur la structure et le métabolisme de la région observée. Pour soutenir le développement technique vers une sonde endomicroscopique visant une utilisation peropératoire, les données en résultants doivent être fiables, et se montrer d'un intérêt pour le chirurgien. Par conséquent, une base de données sur le signal d'autofluorescence des tissus a été construite et présentée dans ce manuscrit, avec des algorithmes capables de discriminer de façon fiable les régions tumorales des régions saines. Des algorithmes qui ont montré le potentiel d'être automatisé dans une configuration clinique, afin de fournir une réponse en temps-réel au chirurgien. / The first standard approach for brain tumor treatment is the surgical resection. In this protocol an important challenge remains, the identification of tumor margins to ensure a complete resection and avoid risk of tumor recurrence. Nowadays no intra-operative means of contrast are able to resolve infiltrated regions from healthy tissue. The standard for tumor margin diagnosis is the histological analysis of biopsies. An ex vivo method that requires one to several days to issue a final pathological reports, a time lapse that could be fatal to the patient. Optical microscopy have recently been developed towards an intra-operative clinical use to answer this challenge. In this work, the technique of two-photon microscopy based on the autofluorescence of tissue have been favored. This technique gives access to two imaging contrasts, the second-harmonic generation and emission of fluorescence, and can be combined to quantitative measurements, such as spectroscopy and fluorescence lifetime. The combination of these four modalities of detection will give a complete structural and metabolic information on the observed region. To support the technical development towards an endomicroscopic probe, the resulted data have to be reliable and proved to be of interest for the surgeon. Consequently, an extensive database of the autofluorescence response of brain tumor tissue have been constructed and presented in this manuscript, with algorithms able to discriminate with reliability tumoral from healthy regions. Algorithms that have shown potential to be automatized in a clinical setting, in order to give a real-time answer to the surgeons.
|
6 |
Résolution du problème du p-médian, application à la restructuration de bases de données semi-structuréesGay, Jean-Christophe 19 October 2011 (has links) (PDF)
Les problèmes que nous considérons dans cette thèse sont de nature combinatoire. Notre principal intérêt est le problème de restructuration de données semi-structurées. Par exemple des données stockées sous la forme d'un fichier XML sont des données semi-structurées. Ce problème peut être ramené à une instance du problème du p-médian. Le principal obstacle ici est la taille des instances qui peut devenir très grande. Certaines instances peuvent avoir jusqu'à 10000 ou 20000 sommets, ce qui implique plusieurs centaines de millions de variables. Pour ces instances, résoudre ne serait-ce que la relaxation linéaire du problème est très difficile. Lors d'expériences préliminaires nous nous sommes rendu compte que CPLEX peut résoudre des instances avec 1000 sommets dans des temps raisonnables. Mais pour des instances de 5000 sommets, il peut prendre jusqu'à 14 jours pour résoudre uniquement la relaxation linéaire. Pour ces raisons nous ne pouvons utiliser de méthodes qui considère la résolution de la relaxation linéaire comme une opération de base, comme par exemple les méthodes de coupes et de branchements. Au lieu d'utiliser CPLEX nous utilisons une implémentation parallèle (utilisant 32 processeurs) de l'algorithme du Volume. L'instance pour laquelle CPLEX demande 14 heures est résolue en 24 minutes par l'implémentation séquentielle et en 10 minutes par l'implémentation parallèle de l'algorithme du Volume. La solution de la relaxation linéaire est utilisée pour construire une solution réalisable, grâce à l'application d'une heuristique de construction gloutonne puis d'une recherche locale. Nous obtenons des résultats comparables aux résultats obtenus par les meilleures heuristiques connues à ce jour, qui utilisent beaucoup plus de mémoire et réalisent beaucoup plus d'opérations. La mémoire est importante dans notre cas, puisque nous travaillons sur des données de très grandes tailles. Nous étudions le dominant du polytope associé au problème du p-médian. Nous discutons de sa relaxation linéaire ainsi que de sa caractérisation polyédrale. Enfin, nous considérons une version plus réaliste du problème de restructuration de données semi-structurées. Grosso modo, nous ajoutons au problème du p-médian original des nouveaux sommets s'ils aident à réduire le coût global des affectations.
|
7 |
Automatic prediction of emotions induced by movies / Reconnaissance automatique des émotions induites par les filmsBaveye, Yoann 12 November 2015 (has links)
Jamais les films n’ont été aussi facilement accessibles aux spectateurs qui peuvent profiter de leur potentiel presque sans limite à susciter des émotions. Savoir à l’avance les émotions qu’un film est susceptible d’induire à ses spectateurs pourrait donc aider à améliorer la précision des systèmes de distribution de contenus, d’indexation ou même de synthèse des vidéos. Cependant, le transfert de cette expertise aux ordinateurs est une tâche complexe, en partie due à la nature subjective des émotions. Cette thèse est donc dédiée à la détection automatique des émotions induites par les films, basée sur les propriétés intrinsèques du signal audiovisuel. Pour s’atteler à cette tâche, une base de données de vidéos annotées selon les émotions induites aux spectateurs est nécessaire. Cependant, les bases de données existantes ne sont pas publiques à cause de problèmes de droit d’auteur ou sont de taille restreinte. Pour répondre à ce besoin spécifique, cette thèse présente le développement de la base de données LIRIS-ACCEDE. Cette base a trois avantages principaux: (1) elle utilise des films sous licence Creative Commons et peut donc être partagée sans enfreindre le droit d’auteur, (2) elle est composée de 9800 extraits vidéos de bonne qualité qui proviennent de 160 films et courts métrages, et (3) les 9800 extraits ont été classés selon les axes de “valence” et “arousal” induits grâce un protocole de comparaisons par paires mis en place sur un site de crowdsourcing. L’accord inter-annotateurs élevé reflète la cohérence des annotations malgré la forte différence culturelle parmi les annotateurs. Trois autres expériences sont également présentées dans cette thèse. Premièrement, des scores émotionnels ont été collectés pour un sous-ensemble de vidéos de la base LIRIS-ACCEDE dans le but de faire une validation croisée des classements obtenus via crowdsourcing. Les scores émotionnels ont aussi rendu possible l’apprentissage d’un processus gaussien par régression, modélisant le bruit lié aux annotations, afin de convertir tous les rangs liés aux vidéos de la base LIRIS-ACCEDE en scores émotionnels définis dans l’espace 2D valence-arousal. Deuxièmement, des annotations continues pour 30 films ont été collectées dans le but de créer des modèles algorithmiques temporellement fiables. Enfin, une dernière expérience a été réalisée dans le but de mesurer de façon continue des données physiologiques sur des participants regardant les 30 films utilisés lors de l’expérience précédente. La corrélation entre les annotations physiologiques et les scores continus renforce la validité des résultats de ces expériences. Equipée d’une base de données, cette thèse présente un modèle algorithmique afin d’estimer les émotions induites par les films. Le système utilise à son avantage les récentes avancées dans le domaine de l’apprentissage profond et prend en compte la relation entre des scènes consécutives. Le système est composé de deux réseaux de neurones convolutionnels ajustés. L’un est dédié à la modalité visuelle et utilise en entrée des versions recadrées des principales frames des segments vidéos, alors que l’autre est dédié à la modalité audio grâce à l’utilisation de spectrogrammes audio. Les activations de la dernière couche entièrement connectée de chaque réseau sont concaténées pour nourrir un réseau de neurones récurrent utilisant des neurones spécifiques appelés “Long-Short-Term- Memory” qui permettent l’apprentissage des dépendances temporelles entre des segments vidéo successifs. La performance obtenue par le modèle est comparée à celle d’un modèle basique similaire à l’état de l’art et montre des résultats très prometteurs mais qui reflètent la complexité de telles tâches. En effet, la prédiction automatique des émotions induites par les films est donc toujours une tâche très difficile qui est loin d’être complètement résolue. / Never before have movies been as easily accessible to viewers, who can enjoy anywhere the almost unlimited potential of movies for inducing emotions. Thus, knowing in advance the emotions that a movie is likely to elicit to its viewers could help to improve the accuracy of content delivery, video indexing or even summarization. However, transferring this expertise to computers is a complex task due in part to the subjective nature of emotions. The present thesis work is dedicated to the automatic prediction of emotions induced by movies based on the intrinsic properties of the audiovisual signal. To computationally deal with this problem, a video dataset annotated along the emotions induced to viewers is needed. However, existing datasets are not public due to copyright issues or are of a very limited size and content diversity. To answer to this specific need, this thesis addresses the development of the LIRIS-ACCEDE dataset. The advantages of this dataset are threefold: (1) it is based on movies under Creative Commons licenses and thus can be shared without infringing copyright, (2) it is composed of 9,800 good quality video excerpts with a large content diversity extracted from 160 feature films and short films, and (3) the 9,800 excerpts have been ranked through a pair-wise video comparison protocol along the induced valence and arousal axes using crowdsourcing. The high inter-annotator agreement reflects that annotations are fully consistent, despite the large diversity of raters’ cultural backgrounds. Three other experiments are also introduced in this thesis. First, affective ratings were collected for a subset of the LIRIS-ACCEDE dataset in order to cross-validate the crowdsourced annotations. The affective ratings made also possible the learning of Gaussian Processes for Regression, modeling the noisiness from measurements, to map the whole ranked LIRIS-ACCEDE dataset into the 2D valence-arousal affective space. Second, continuous ratings for 30 movies were collected in order develop temporally relevant computational models. Finally, a last experiment was performed in order to collect continuous physiological measurements for the 30 movies used in the second experiment. The correlation between both modalities strengthens the validity of the results of the experiments. Armed with a dataset, this thesis presents a computational model to infer the emotions induced by movies. The framework builds on the recent advances in deep learning and takes into account the relationship between consecutive scenes. It is composed of two fine-tuned Convolutional Neural Networks. One is dedicated to the visual modality and uses as input crops of key frames extracted from video segments, while the second one is dedicated to the audio modality through the use of audio spectrograms. The activations of the last fully connected layer of both networks are conv catenated to feed a Long Short-Term Memory Recurrent Neural Network to learn the dependencies between the consecutive video segments. The performance obtained by the model is compared to the performance of a baseline similar to previous work and shows very promising results but reflects the complexity of such tasks. Indeed, the automatic prediction of emotions induced by movies is still a very challenging task which is far from being solved.
|
8 |
Confidentialité, bases de données et réseaux d'ordinateursRichy, Hélène 06 February 1978 (has links) (PDF)
.
|
9 |
Résolution du problème du p-médian, application à la restructuration de bases de données semi-structurées / Resolution of the p-median problem : application to restructuring semi-structured dataGay, Jean-Christophe 19 October 2011 (has links)
Les problèmes que nous considérons dans cette thèse sont de nature combinatoire. Notre principal intérêt est le problème de restructuration de données semi-structurées. Par exemple des données stockées sous la forme d’un fichier XML sont des données semi-structurées. Ce problème peut être ramené à une instance du problème du p-médian. Le principal obstacle ici est la taille des instances qui peut devenir très grande. Certaines instances peuvent avoir jusqu’à 10000 ou 20000 sommets, ce qui implique plusieurs centaines de millions de variables. Pour ces instances, résoudre ne serait-ce que la relaxation linéaire du problème est très difficile. Lors d’expériences préliminaires nous nous sommes rendu compte que CPLEX peut résoudre des instances avec 1000 sommets dans des temps raisonnables. Mais pour des instances de 5000 sommets, il peut prendre jusqu’à 14 jours pour résoudre uniquement la relaxation linéaire. Pour ces raisons nous ne pouvons utiliser de méthodes qui considère la résolution de la relaxation linéaire comme une opération de base, comme par exemple les méthodes de coupes et de branchements. Au lieu d’utiliser CPLEX nous utilisons une implémentation parallèle (utilisant 32 processeurs) de l’algorithme du Volume. L’instance pour laquelle CPLEX demande 14 heures est résolue en 24 minutes par l’implémentation séquentielle et en 10 minutes par l’implémentation parallèle de l’algorithme du Volume. La solution de la relaxation linéaire est utilisée pour construire une solution réalisable, grâce à l’application d’une heuristique de construction gloutonne puis d’une recherche locale. Nous obtenons des résultats comparables aux résultats obtenus par les meilleures heuristiques connues à ce jour, qui utilisent beaucoup plus de mémoire et réalisent beaucoup plus d’opérations. La mémoire est importante dans notre cas, puisque nous travaillons sur des données de très grandes tailles. Nous étudions le dominant du polytope associé au problème du p-médian. Nous discutons de sa relaxation linéaire ainsi que de sa caractérisation polyédrale. Enfin, nous considérons une version plus réaliste du problème de restructuration de données semi-structurées. Grosso modo, nous ajoutons au problème du p-médian original des nouveaux sommets s’ils aident à réduire le coût global des affectations. / The problems we consider in this thesis are of combinatorial nature. Our main interest is the problem of approximating typing of a semistructured data. For example XML is a semistructured data. This problem may be reduced to an instance of the p-median problem. The main obstacle here is the size of the instances that may be very huge, about 10000 and 20000 nodes which imply several hundreds of million variables. For these instances, even solving the linear relaxation is a hard task. In some preliminary results we noticed that Cplex may solve instances of size 1000 in an acceptable time. But for some instances having 5000 nodes, it may needs 14 days for solving only the linear relaxation. Therefore, we cannot use methods that consider the linear relaxation as an elementary operation, as for example branch-and-cut methods. Instead of using Cplex we use the Volume algorithm in a parallel implementation (32 processors).For the instance where the Cplex needs 14 hours, the Volume algorithm in sequential implementation needs 24 minutes and in parallel implementation it needs 10 minutes. The solution of the linear relaxation is used to produce a feasible solution by first applying a greedy and then a local search heuristic. We notice that the results we obtain are relatively the same as those given by the best method known up today, which produces more effort and consumes more memory. Memory is important in our case since the data we consider are huge. We study the dominant of the polytope associated with the p-median problem. We discuss linear relaxation and a polyhedral characterization. Finally, we consider a more realistic version of the p-median problem when applied to the problem of approximating typing of a semistructured data. Roughly speaking, we add new nodes to the underlying graph if this help to reduce the overall cost.
|
10 |
Structuration des données de la conception d'un bâtiment pour une utilisation informatiqueTlili, Assed 01 December 1986 (has links) (PDF)
Cette recherche propose une structure et un dictionnaire de données de la conception thermique d'un bâtiment d'habitation. L'analyse qui y est effectuée facilite la tâche des créateurs de logiciels spécifiques aux différents domaines de la conception des bâtiments en les dispensant des analyses séparées et répétées. Ces logiciels se partagent les données, saisies et manipulées une seule fois, et les échangent entre eux sans problèmes de compatibilité. La démarche se résume en quatre points : - L'analyse préliminaire de la conception d'un bâtiment fournit des listes, de phases, de fonctions et tâches, de dossiers et documents, et enfin d'ouvrages, à partir desquelles pourraient être collectées les données. - Cette collecte sera effectuée dans le domaine restreint de la conception thermique, pour permettre une analyse plus détaillée. Celle-ci aboutit, grâce aux méthodes de structuration, à la "structure brute" du premier niveau, qui contient des fichiers, et à la "structure simplifiée" du second niveau, qui contient des structures de données. - La "méta-structure" du troisième niveau contient la totalité des résultats dans le fichier "STRUCTURE" : nomenclature des données classées par types, et le fichier "DICTIONNAIRE" : tous les paramètres des données classées par ordre alphabétique. - L'application est réalisée grâce au fichier "BASE", dont le contenu (identifiants et valeurs des données) est saisi une seule fois par le premier utilisateur. La méthode qui a permis la proposition de ces résultats pour ce domaine restreint reste valable pour les domaines non traités. Le traitement de tous les domaines de la conception d'un bâtiment aboutirait à un système de CAO global.
|
Page generated in 0.0987 seconds