Quelques algorithmes entre le monde des graphes et les nuages de points.

The notion of visibility is central in computer graphics and computational geometry. A visibility computation amounts to determining the shape, or merely the existence of the set of segments in space linking two specified objects without crossing any other. We examine the problem of maintaining the visibility of a moving viewpoint with the aid of a complex describing all the visibility relationships in a scene, at once: the visibility complex. <br />We take two different approaches to this problem. In one, we show how one can maintain the so-called visibility polyhedron of the moving point, in an exact fashion. We apply a variant of the algorithm to the construction of the visibility complex of a set of disjoint polytopes. <br />The second approach is motivated by the need to render complex 3D scenes at interactive rates. We propose an algorithm that decomposes a 3D scene into simple cells related together with simple visibility relationships represented as a graph. The scene is drawn as the graph is traversed, allowing pruning to speed up rendering. We also provide an efficient algorithm for real-time rendering of hard shadows.

Nous proposons une nouvelle structure de données distribuée et scalable appelée LH*RSP2P conçue pour les environnements pair à pair(P2P).Les données de l'application forment un fichier d'enregistrements identifiés par les clés primaires. Les enregistrements sont dans des cases mémoires sur des pairs, adressées par le hachage distribué (LH*). Des éclatements créent dynamiquement de nouvelles cases pour accommoder les insertions. L'accès par clé à un enregistrement comporte un seul renvoi au maximum. Le scan du fichier s'effectue au maximum en deux rounds. Ces résultats sont parmi les meilleurs à l'heure actuelle. Tout fichier LH*RSP2P est également protégé contre le Churn. Le calcul de parité protège toute indisponibilité jusqu'à k cases, où k ≥ 1 est un paramètre scalable. Un nouveau type de requêtes, qualifiées de sûres, protège également contre l'accès à toute case périmée. Nous prouvons les propriétés de notre SDDS formellement par une implémentation prototype et des expérimentations. LH*RSP2P apparaît utile aux applications Big Data, sur des RamClouds tout particulièrement

Dans ce mémoire, j'examine différents aspects d'un objet simple mais omniprésent en informatique: la séquence de symboles (appelée selon le contexte mot ou chaîne de caractères). La notion de mot est au carrefour de domaines comme la théorie de l'information et la théorie des langages. S'il est simple, il reste fondamental: nous n'avons, au plus bas niveau, que cela à disposition puisqu'il arrive toujours un moment où une donnée doit être encodée en symboles stockables en mémoire. La quantité d'information croissante de données mise à disposition et qu'on peut stocker, par exemple des génomes d'individus ou des documents numérisés, justifie que les algorithmes et les structures de données qui les manipulent soient optimisés. En conséquence, les besoins d'analyse se font sentir pour guider le choix et la conception des programmes qui manipulent ces données. L'analyse en moyenne est ici particulièrement adaptée puisque les données atteignent une variété et des volumes tellement importants que c'est le cas typique qui traduit le mieux la complexité et non pas le cas le pire. Cela évidemment pose le problème de la modélisation de données qui reste encore très épineux. En effet on souhaite deux choses contradictoires: un modèle au plus près des données, qui traduise vraiment leurs spécificités, mais aussi un modèle permettant de donner des résultats, c'est-à-dire de prédire les performances (et on comprend vite que le modèle doit donc rester relativement simple pour qu'il subsiste un espoir de le traiter!). Les méthodes sont le plus souvent celles de la combinatoire analytique et font appel à un objet mathématique, les séries génératrices, pour mener les analyses à bien.

Le perfectionnement des modes d’acquisition 3D (relevés laser, photographiques, etc.) a conduit à la multiplication des données 3D géolocalisées disponibles. De plus en plus de villes mettent leur modèle numérique 3D à disposition en libre accès. Pour garantir l’interopérabilité des différentes sources de données, des travaux ont été effectués sur la standardisation des protocoles d’échange et des formats de fichier. En outre, grâce aux nouveaux standards du Web et à l’augmentation de la puissance des machines, il est devenu possible ces dernières années d’intégrer des contenus riches, comme des applications 3D, directement dans une page web. Ces deux facteurs rendent aujourd’hui possible la diffusion et l’exploitation des données tridimensionnelles de la ville dans un navigateur web. Ma thèse, dotée d’un financement de type CIFRE avec la société Oslandia, s’intéresse à la représentation tridimensionnelle de la ville sur le Web. Plus précisément, il s’agit de récupérer et de visualiser, à partir d’un client léger, de grandes quantités de données de la ville sur un ou plusieurs serveurs distants. Ces données sont hétérogènes : il peut s’agir de la représentations 3D des bâtiments (maillages) et du terrain (carte de hauteur), mais aussi d’informations sémantiques telles que des taux de pollution (volumes), la localisation de stations de vélos (points) et le nombre de vélos disponibles, etc. Durant ma thèse, j’ai exploré différentes manières d’organiser ces données dans des structures génériques afin de permettre une transmission progressive de fortes volumétries de données 3D. La prise en compte de l’aspect multi-échelle de la ville est un élément clef de la conception de ces structures.L’adaptation de la visualisation des données à l’utilisateur est un autre grand axe de ma thèse. Du fait du grand nombre de cas d’utilisations existants pour la ville numérique, les besoins de l’utilisateur varient grandement : des zones d’intérêts se dégagent, les données doivent être représentées d’une manière spécifique... J’explore différentes manières de satisfaire ces besoins, soit par la priorisation de données par rapport à d’autres lors de leur chargement, soit par la génération de scènes personnalisés selon les préférences indiquées par l’utilisateur. / Advances in 3D data acquisition techniques (laser scanning, photography, etc.) has led to a sharp increase in the quantity of available 3D geolocated data. More and more cities provide the scanned data on open access platforms. To ensure the intercompatibility of different data sources, standards have been developed for exchange protocols and file formats. Moreover, thanks to new web standards and the increase in processing power of personal devices, it is now possible to integrate rich content, such as 3D applications, directly in a web page. These two elements make it possible to share and exploit 3D city data into a web browser.The subject of my thesis, co-financed by the Oslandia company, is the 3D representation of city data on the Web. More precisely, the goal is to retrieve and visualize a great quantity of city data from one or several distant servers in a thin client. This data is heterogenous: it can be 3D representations of buildings (meshes) or terrain (height maps), but also semantic information such as pollution levels (volume data), the position of bike stations (points) and their availability, etc. During my thesis, I explored various ways of organising this data in generic structures in order to allow the progressive transmission of high volumes of 3D data. Taking into account the multiscale nature of the city is a key element in the design of these structures. Adapting the visualisation of the data to the user is another important objective of my thesis. Because of the high number of uses of 3D city models, the user’s needs vary greatly: some specific areas are of higher interest, data has to be represented in a certain way... I explore different methods to satisfy these needs, either by priroritising some data over others during the loading stage, or by generating personalised scenesbased on a set of preferences defined by the user.

Durant cette thèse, nous avons introduit les problèmes de Bin Covering avec Contrainte de Distance (BCCD) et de Bin Packing avec Contrainte de Distance (BPCD), qui trouvent leur application dans les réseaux de grande échelle, tel Internet. L'étude de ces problèmes que nous effectuons dans des espaces métriques quelconques montre qu'il est impossible de travailler dans un tel cadre sans avoir recours à de l'augmentation de ressources, un procédé qui permet d'élaborer des algorithmes construisant des solutions moins contraintes que la solution optimale à laquelle elles sont comparées. En plus de résultats d'approximation intéressants, nous prouvons la difficulté de ces problèmes si ce procédé n'est pas utilisé. Par ailleurs, de nombreux outils ont pour objectif de plonger les grands réseaux qui nous intéressent dans des espaces métriques bien décrits. Nous avons alors étudié nos problèmes dans les espaces métriques générés par certains de ces outils, comme Vivaldi et Sequoia.

Nous considérons la résolution de très grands systèmes linéaires creux à l'aide d'une méthode de factorisation directe appelée méthode multifrontale. Bien que numériquement robustes et faciles à utiliser (elles ne nécessitent que des informations algébriques : la matrice d'entrée A et le second membre b, même si elles peuvent exploiter des stratégies de prétraitement basées sur des informations géométriques), les méthodes directes sont très coûteuses en termes de mémoire et d'opérations, ce qui limite leur applicabilité à des problèmes de taille raisonnable (quelques millions d'équations). Cette étude se concentre sur l'exploitation des approximations de rang-faible dans la méthode multifrontale, pour réduire sa consommation mémoire et son volume d'opérations, dans des environnements séquentiel et à mémoire distribuée, sur une large classe de problèmes. D'abord, nous examinons les formats rang-faible qui ont déjà été développé pour représenter efficacement les matrices denses et qui ont été utilisées pour concevoir des solveur rapides pour les équations aux dérivées partielles, les équations intégrales et les problèmes aux valeurs propres. Ces formats sont hiérarchiques (les formats H et HSS sont les plus répandus) et il a été prouvé, en théorie et en pratique, qu'ils permettent de réduire substantiellement les besoins en mémoire et opération des calculs d'algèbre linéaire. Cependant, de nombreuses contraintes structurelles sont imposées sur les problèmes visés, ce qui peut limiter leur efficacité et leur applicabilité aux solveurs multifrontaux généraux. Nous proposons un format plat appelé Block Rang-Faible (BRF) basé sur un découpage naturel de la matrice en blocs et expliquons pourquoi il fournit toute la flexibilité nécéssaire à son utilisation dans un solveur multifrontal général, en terme de pivotage numérique et de parallélisme. Nous comparons le format BRF avec les autres et montrons que le format BRF ne compromet que peu les améliorations en mémoire et opération obtenues grâce aux approximations rang-faible. Une étude de stabilité montre que les approximations sont bien contrôlées par un paramètre numérique explicite appelé le seuil rang-faible, ce qui est critique dans l'optique de résoudre des systèmes linéaires creux avec précision. Ensuite, nous expliquons comment les factorisations exploitant le format BRF peuvent être efficacement implémentées dans les solveurs multifrontaux. Nous proposons plusieurs algorithmes de factorisation BRF, ce qui permet d'atteindre différents objectifs. Les algorithmes proposés ont été implémentés dans le solveur multifrontal MUMPS. Nous présentons tout d'abord des expériences effectuées avec des équations aux dérivées partielles standardes pour analyser les principales propriétés des algorithms BRF et montrer le potentiel et la flexibilité de l'approche ; une comparaison avec un code basé sur le format HSS est également fournie. Ensuite, nous expérimentons le format BRF sur des problèmes variés et de grande taille (jusqu'à une centaine de millions d'inconnues), provenant de nombreuses applications industrielles. Pour finir, nous illustrons l'utilisation de notre approche en tant que préconditionneur pour la méthode du Gradient Conjugué.

Cette thése étudie le problème NP-difficile de optimization quadratique en variables binaires (BQO), à savoir le problème de la maximisation d'une fonction quadratique en variables binaires. BQO peut représenter de nombreux problèmes importants de différents domaines et servir de modèle unifié pour un grand nombre de problèmes d'optimisation combinatoire portant sur les graphes. Cette thèse est consacrée au développement d'algorithmes métaheuristiques efficaces pour résoudre le BQO et ses applications. Premièrement, nous proposons algorithmes de "backbone guided" recherche tabou et d'un algorithme mémétique multi-niveaux sur la base de la technique de la fixation de variables. Ces techniques sont toutes deux basées sur l'idée de la réduction du problème afin de mener à bien une exploitation exhaustive d'une petite région de recherche. Ensuite, nous nous concentrons sur des procédés avancés de génération des solutions initiales préférables et développons des algorithmes combinant GRASP avec la recherche tabou et les algorithmes de path-relinking. En outre, nous résolvons des problèmes, y compris le problème de coupe maximum, de clique maximum, de clique maximale de sommets pondérés et la somme coloration minimum, soit en appliquant directement ou avec une légère adaptation de nos algorithmes développés pour BQO, avec l'hypothèse que ces problèmes sont reformulés en BQO. Enfin, nous présentons un algorithme mémétique basé sur la recherche tabou qui s'attaque efficacement au BQO avec contrainte de cardinalité.

For many years software engineering has primarily focused on the development of new systems and neglected maintenance and reengineering of legacy applications. Maintenance typically represents 70% of the cost during the life cycle of a system. In order to allow an efficient and safe maintenance of a legacy system, we need to reverse engineer it in order to reconstruct its missing or out-of-date documentation. In data-oriented applications the reverse engineering complexity can be broken down by considering that the database can be reverse engineered independently of the procedural components. Database reverse engineering can be defined as the process of recovering the database's schema(s) of an application from database declaration text and program source code that use the data in order to understand their exact structure and meaning. A database reverse engineering methodology is broken down into three processes: project preparation, data structure extraction that recovers the database's logical schema and data structure conceptualization that interprets the logical schema in conceptual terms. In order to validate our methodology and program understanding techniques, we have developed tools to support them. Those tools have proved absolutely necessary to perform database reverse engineering of medium to larger applications in reasonable time and at reasonable cost. To cut down on the cost of large projects, we have stressed the need for automation to reduce the manual work of the analyst. Our experience with real size projects has taught us that the management aspects of a project are essential success factors. The management of a project comprises different aspects such as database reverse engineering explanation, cost evaluation and database reverse engineering result evaluation.

Tree automata, and their applications to verification from the common thread of this thesis In the first part, we definie a complete model-cheking framework.[...] The second part focus on an important aspect of the automata involved: constraints.[...] Finaly, we also study the very different variety of tree-walking automata which have tight connections with navigational languages on semi-structured documents.