This thesis discusses the design and implementation of an SQL front end for a relational database programming system JRelix. The purpose of this thesis is to lay a strong basis for the full SQL support by JRelix. The SQL language is the de facto standard in Relational Databases which motivates its integration into JRelix. Through the SQLSTMT and SQLEXP commands the user can use SQL to perform operations on a JRelix database. These operations are translated into Aldat (the native programming language of JRelix) and can interactively perform updates, deletions and selections on the distinct relations of the database. The SQLSTMT command allows us to execute full SQL commands on the system whereas the SQLEXP command returns a relational expression to the system that can interact with other elements of the commands written in Aldat in the same statement. / La présente thèse traite de la conception et de la mise en oeuvre d'une interface SQL pour le système de programmation de bases de données relationnelles JRelix. Cette thèse a pour but de poser les fondements d'une couverture exhaustive de SQL par JRelix. Le Language SQL est le standard en bases de données relationnelles ce qui est à l'origine de son intégration dans JRelix. A l'aide des commandes SQLSTMT et SQLEXP l'utilisateur peut effectuer des requêtes sur la base de données JRelix en SQL. Ces requêtes sont traduites en Aldat (le language natif de programmation de JRelix) et peut, de façon interactive, effectuer mises à jour, suppressions et sélections sur les différentes relations. La commande SQLSTMT permet d'exécuter des requêtes entièrement exprimées en SQL alors que la commande SQLEXP retourne au système une expression relationnelle qui peut interagir avec d'autres expressions relationnelles exprimées en Aldat dans la même requête.

There are many statistical measures of correlation, such as Pearson's correlation coefficient for real random variables, the chi-square statistic for discrete random variables, and mutual information. Most such measures are symmetric and do not allow detection of influence direction. We propose a novel information theory measure whose value indicates direction of functional dependency. The measure calculation algorithm is performed on real-valued data being quantized into bins. This quantization is a corner stone of the algorithm suggested, as it affects both the statistical significance between the variables being tested for dependency and the numeric strength of dependency. / Il existe de nombreuses mesures statistiques de corrélation, tels que le Pearson coefficient de corrélation des variables aléatoires, le chi-carré pour les variables aléatoires discrètes et, finalement, l'information mutuelle. La plupart de ces mesures sont symétriques et ne pas permettre la détection d'influence. Nous proposons une nouvelle mesure de l'information-théorique dont la valeur indique la direction de le dépendence fonctionnelle. La mesure algorithme de calcul est effectué sur la valeur réelle de données quantifiées en bacs. Cette quantification est une fondation de l'algorithme proposé, car elle informe à la fois la signification statistique entre les variables et la force de la dépendance.

This thesis focuses on algorithms related to ancestral genome reconstruction and phylogenetics analyses. Specially, it studies insertion and deletion (indel) in genomic sequences, their utilities for (1) evolutionary studies of species families, (2) multiple alignment and phylogenetic trees reconstruction assessment, and (3) functional DNA sequence annotation. Here, the indel scenarios reconstruction problem is presented, in a likelihood framework, and it can be stated as follows: given a multiple alignment of orthologous sequences and a phylogenetic tree for these sequences, reconstruct the most likely scenario of insertions and deletions capable of explaining the gaps observed in the alignment. This problem, that we called the Indel Maximum Likelihood Problem (IMLP), is an important step toward the reconstruction of ancestral genomic sequences, and is important for studying evolutionary processes, genome function, adaptation and convergence. In this thesis, first, we showed that we can solve the IMLP using a new type of tree hidden Markov model whose states correspond to single-base evolutionary scenarios and where transitions model dependencies between neighboring columns. The standard Viterbi and Forward-backward algorithms are optimized to produce the most likely ancestral reconstruction and to compute the level of confidence associated to specific regions of the reconstruction. A heuristic is presented to make the method practical for large data sets, while retaining an extremely high degree of accuracy. The developed methods have been made available for the community through a web interface. Second we showed the utilities of the defined indel score for assessing the accuracy of multiple sequence alignment and phylogenetic tree reconstruction. Third, the provided method is included into the framework of the ancestral protein reconstruction of phages under a reticulate evolution and the evolutionary studies of the carcinogencity of the Human Papilloma Vir / Cette thèse traite d'algorithmes pour la reconstruction de génomes ancestraux et l'analyse phylogénétique. Elle étudie particulièrement les scénarios d'insertion et délétion (indels) dans les séquences génomiques, leur utilité (1) pour l'étude des familles d'espèces, (2) pour l'évaluation des alignements multiples de séquences et la reconstruction phylogénétique, (3) et pour l'annotation de séquences génomiques fonctionnelles. Dans cette thèse, le problème de la reconstruction du scénario d'indels est étudié en utilisant le critère de maximum de vraisemblance. Ce problème peut être défini de la manière suivante: étant donné un alignement multiple de séquences orthologues et un arbre phylogénétique traduisant l'histoire évolutive de ces séquences, reconstruire le scénario d'indels le plus vraisemblable capable d'expliquer les brèches présentes dans l'alignement. Ce problème, dénommé ''Indel Maximum Likelihood Problem (IMLP)'', est une importante étape de la reconstruction de séquences ancestrales. Il est également important pour l'étude des processus évolutifs, des fonctions des gènes, de l'adaptation et de la convergence.Dans une première étape de cette thèse, nous montrons que l'IMLP peut être résolu en utilisant un nouveau type de données combinant un arbre phylogénétique et un modèle de Markov caché. Les états de ce modèle de Markov caché correspondent à un scénario évolutif d'une colonne de l'alignement. Ses transitions modélisent la dépendance entre les colonnes voisines de l'alignement.Les algorithmes standard de Viterbi et de Forward-Backward ont été optimisés pour produire le scénario ancestral le plus vraisemblable et pour calculer le niveau de confiance associé aux prédictions. Dans cette thèse, Nous présentons également une heuristique qui permet d'adapter la méthode à des données de grandes tailles. En second, nous montrons l'utilité du score d'indel dans l'évaluatio

The current trend in computer game design is toward larger and richer virtual worlds, providing interesting and abundant game content for players to explore. The creation and continuous expansion of detailed virtual environments, however, is a time and resource-consuming task for game developers. Procedural content generation potentially solves this problem; textures, landscapes, and more recently the creation of entire cities and their constituent roads and buildings can be performed in an auto mated fashion, potentially offering considerable resource savings for developers. This thesis develops a comprehensive system for content generation, centering on a hierarchical world design. The Arda tool is presented as a modular system for supporting automatic content generation in a game context. Arda is composed of a framework for internally managing environmental data and content-generation algorithms, in addition to a graphical tool providing a simplified interface for generating video game content. The tool supports extensive customization, which is demonstrated through a novel algorithm for efficient and realistic city (road-plan) generation. Experimental results show the design is practical, producing qualitatively realistic results. It is also quite fast; large city plans, extending to the size of major real-world cities can be generated in a few seconds. The Arda design demonstrates the feasibility of automatic content generation, providing a practical and flexible system for quick prototyping, development and testing of game assets. / La nouvelle tendance dans la conception de jeux vidéo vise des environnements vastes et détaillés, pour mettre en valeur l’exploration de l’univers virtuel. Cependant, la création de ce contenu impose au développeur un investissement majeur au niveau des ressources et du temps requis pour la production. L’emploi du contenu procédural pourrait résoudre le problème: la création de textures, de paysages, et finalement de villes entières—incluant des réseaux routiers et des bâtiments complexes—se fait de façon automatisée, ce qui représente une économie considérable pour les développeurs. Cette thèse présente un système de génération de contenu procédural axé sur une conception hiérarchique du monde virtuel: Arda, un outil modulaire qui facilite la création automatique de contenu pour les jeux vidéo. Arda est composé d'un cadre d'applications pour la gestion de données environnementales et d'algorithmes procéduraux, ainsi que d'une interface d'utilisation graphique qui simplifie le processus de création de contenu. L'outil est fortement paramétrable, ce qui est démontré grâce à un nouvel algorithme, conçu ci-après, pour la création efficace et réaliste de réseaux routiers. Les essais prouvent que le concept est pratique et produit des résultats très réalistes. De plus, le système est rapide: des villes virtuelles, de la même dimension que des villes actuelles, sont construites en quelques secondes. Le système Arda démontre la faisabilité de la génération de contenu procédural, fournissant une méthode pratique et modulaire pour le dévelopement et la validation rapide de contenu pour les jeux vidéo.

A game lobby is an online service provided to online game players. Players interact with each other and participate in games through the game lobby. As web technology becomes more advanced, the web is seen as a promising platform for online game lobbies. In this thesis, we develop a web-based communication middleware for game lobbies using the XML-RPC web service framework. Web-based communication middleware must use the Hypertext Transfer Protocol (HTTP) for its communication transport, which is based on the request-reply protocol, and requires all communication to be initiated by the client. This presents a major challenge for realizing the communication middleware as the lobby server needs to send information to the clients at arbitrary time points with minimum latency. We propose a novel Server Push Enabled XML-RPC (SPEX) protocol to address this problem by employing the so-called "long-polling'' technique. We also devise a light-weight authentication scheme, called Authenticated XML-RPC. We have implemented SPEX and Authenticated XML-RPC and analyzed the performance characteristics of our implementation. Experiments show that the communication middleware scales well, providing good response time for the kind of real-time interactions that occur typically in an online game lobby setting. / Un lobby de jeu est un service en ligne fourni pour les joueurs en ligne. Ces derniers peuvent interagir entre eux et prendre part aux jeux à partir du lobby de jeu. Grâce aux avancements technologiques, le Web est perçu comme une plateforme prometteuse pour développer des lobbies de jeux en ligne.Dans ce mémoire de maîtrise, nous développons un intergiciel de communication Web pour des lobbies de jeux en utilisant le cadre de service Web XML-RPC. Tout intergiciel de communication Web doit utiliser l'Hypertext Transfer Protocol (HTTP) comme transport de communication, qui est basé sur un protocole de transmission sur demande et nécessitant que toutes communications soient initiées par le client. Ceci pose un défi important à l'élaboration d'un intergiciel de communication vu que le serveur du lobby doit envoyer des informations aux clients à des temps arbitraires et avec un temps d'attente minimum. Pour aborder ce problème, nous proposons un nouveau protocole Server Push Enabled XML-RPC (SPEX) en exploitant la technique de "long-polling". Nous avons également conçu un système allégé d'authentification intitulé Authenticated XML-RPC. Nous avons mis en œuvre SPEX et Authenticated XML-RPC, ainsi qu'analysé les performances de notre implémentation sous différentes configurations. Nos expériences ont démontré que notre intergiciel de communication est extensible tout en garantissant un temps de réponse satisfaisant pour ce genre d'interactions en temps réel survenant généralement dans un environnement de lobby de jeu en ligne.

A Phishing attack is a type of identity theft attempting to steal confidential and personal data like Credit Card or banking account information. Different approaches have been proposed to defeat phishing attacks. Most of the approaches rely on a database lookup approach. In this thesis, we present a framework called CASTLE that allows a collaborative approach to build and maintain the databases containing information needed for anti-phishing services. We provide the full design and discuss how phishing sites can be captured using CASTLE. A prototype of this social frame- work for collaborative anti-phishing databases is partially implemented to evaluate the performance and effectiveness of the framework against phishing attacks. / L'hame¸connage est un type de vol d'identité qui tente de voler des donnés confidentielleset personnelles comme l'information de cartes de crédit ou de comptes bancaires.Plusieurs stratégies ont été proposées pour vaincre l'hame¸connage ; la plupart d'entreelles dépendent d'une base de données. Dans cette th'ese, nous présentons le cadreCASTLE, qui incite la collaboration pour construire et entretenir des bases de donnescontenant l'information nécessaire pour contrer l'hame¸connage. Nous fournissons laconception et discutons la mani'ere avec laquelle les sites de hameonnage peuventêtre capturés a l'aide de CASTLE. Un prototype de ce cadre est partiellement misen oeuvre pour évaluer la performance et l'efficacit du cadre contre les attaques dehame¸connage.

A facial recognition system is a computer application built to automatically identify or verify the identity of a person from a digital source. The quality of the source and environment from which digital information is retrieved pose problems to a face recognition system (FRS) that lead to erroneous results. Even though there is a necessity for systems that are capable of performing facial recognition on the fly, current systems, in order to be accurate, try to completely or partially control the environment of its digital sources. In this thesis, we approach the problems that afflict these systems by using a "game with a purpose" (GWAP). In our GWAP-based approach, we create an online game that uses human vision to perform facial recognition. We use the aid of humans because we still hold the edge over FRSs at recognizing faces and their features. It is through a GWAP that we channel our superior visual skills to deal with problems that affect current FRSs. / Un système de reconnaissance faciale est une application informatique créée pour identifier ou vérifier automatiquement l'identité d'une personne provenant d'une source numérique. La qualité de la source et l'environnement duquel l'information numérique est extrait posent des problèmes à un système de reconnaissance faciale (FRS) et peuvent causer la production de résultats erronés. Même s'il y a une nécessité pour les systèmes qui sont capables d'effectuer la reconnaissance des visages à la volée, les systèmes actuels, pour être précis, essayent de contrôler complètement ou partiellement l'environnement de ses sources numériques. Dans cette thèse, nous abordons les problèmes qui affligent ces systèmes en utilisant un "game with a purpose" (GWAP). Dans notre GWAP, nous créons un jeu en ligne qui utilise la vision humaine, pour effectuer la reconnaissance du visage. Nous utilisons l'aide des êtres humains, car nous tenons toujours l'avantage sur les systèmes de reconnaissance faciale à la reconnaissance des visages et ses caractéristiques. C'est par une GWAP que nous canalisons nos compétences visuelles supérieures pour faire face aux problèmes qui affectent actuellement les FRSs.

We present an accountability framework for the Internet which ties a user's action to her identity on an online social network. The framework is optional in that users do not need to be accountable at all times, but various web services can force accountability on the part of their users by only allowing accountable users access. Our design is general enough that higher level applications can place additional policies/restrictions on the basic accountability provided. In this thesis, we introduce the design, discuss how various applications can be mapped onto our framework, and provide performance numbers from an experimental prototype. / Nous présentons un cadre de responsabilisation pour l'Internet, qui lie l'action d'un utilisateur à son identité sur un réseau social en ligne. Le cadre est facultatif en ce que les utilisateurs n'ont pas besoin d'être responsables en tout temps, mais les services web différents peuvent envigueur responsabilité de la part de leurs utilisateurs en ne permettant l'accès que pour des utilisateurs responsables. Notre conception est suffisamment général pour que les applications de niveau supérieur peut placer d'autres politiques et les restrictions sur la responsabilité de base prévue. Dans cette thèse, nous présentons la conception, discutons comment les différentes applications peuvent être placés sur notre cadre, et fournissons des données de performance à partir d'un prototype expérimental.

Quantum information theory is a multidisciplinary field whose objective is to understand what happens when information is stored in the state of a quantum system. Quantum mechanics provides us with a new resource, called quantum entanglement, which can be exploited to achieve novel tasks such as teleportation and superdense coding. Current technologies allow the transmission of entangled photon pairs across distances up to roughly 100 kilometers. For longer distances, noise arising from various sources degrade the transmission of entanglement to the point that it becomes impossible to use the entanglement as a resource for future tasks. One strategy for dealing with this difficulty is to employ quantum repeaters, stations intermediate between the sender and receiver that can participate in the process of entanglement distillation, thereby improving on what the sender and receiver could do on their own. Motivated by the problem of designing quantum repeaters, we study entanglement distillation between two parties, Alice and Bob, starting from a mixed state and with the help of repeater stations. We extend the notion of entanglement of assistance to arbitrary tripartite states and exhibit a protocol, based on a random coding strategy, for extracting pure entanglement. We use these results to find achievable rates for the more general scenario, where many spatially separated repeaters help two recipients distill entanglement. We also study multiparty quantum communication protocols in a more general context. We give a new protocol for the task of multiparty state merging. The previous multiparty state merging protocol required the use of time-sharing, an impossible strategy when a single copy of the input state is available to the parties. Our protocol does not require time-sharing for distributed compression of two senders. In the one-shot regime, we can achieve multiparty state merging with entanglement costs not restricted to corner points of the entanglement cost region. Our analysis of the entanglement cost is performed using (smooth) min- and max-entropies. We illustrate the benefits of our approach by looking at different examples. / L'informatique quantique a pour objectif de comprendre les propriétés de l'information lorsque celle-ci est représentée par l'état d'un système quantique. La mécanique quantique nous fournit une nouvelle ressource, l'intrication quantique, qui peut être exploitée pour effectuer une téléportation quantique ou un codage superdense. Les technologies actuelles permettent la transmission de paires de photons intriqués au moyen d'une fibre optique sur des distances maximales d'environ 100 kilomètres. Au-delà de cette distance, les effets d'absorption et de dispersion dégradent la qualité de l'intrication. Une stratégie pour contrer ces difficultés consiste en l'utilisation de répéteurs quantiques: des stations intermédiaires entre l'émetteur et le récepteur, qui peuvent être utilisées durant le processus de distillation d'intrication, dépassant ainsi ce que l'émetteur et le récepteur peuvent accomplir par eux-mêmes. Motivés par le problème précédent, nous étudions la distillation d'intrication entre deux parties à partir d'un état mixte à l'aide de répéteurs quantiques. Nous étendons la notion d'intrication assistée aux états tripartites arbitraireset présentons un protocole fondé sur une stratégie de codage aléatoire. Nous utilisons ces résultats pour trouver des taux de distillation réalisable dans le scénario le plus général, où les deux parties ont recours à de nombreux répéteurs durant la distillation d'intrication. En étroite liaison avec la distillation d'intrication, nous étudions également les protocoles de communication quantique multipartite. Nous établissons un nouveau protocole pour effectuer un transfert d'état multipartite. Une caractéristique de notre protocole est sa capacité d'atteindre des taux qui ne correspondent pas à des points extrêmes de la région réalisable sans l'utilisation d'une stratégie de temps-partagé. Nous effectuons une analyse du coût d'intrication en utilisant les mesures d'entropie minimale et maximale et illustrons les avantages de notre approche à l'aide de différents exemples. Finalement, nous proposons une variante de notre protocole, où deux récepteurs et plusieurs émetteurs partagent un état mixte. Notre protocole, qui effectue un transfert partagé, est appliqué au problème de distillation assistée.

Current load-balancing and content distribution systems can efficiently handle high amounts of traffic a website encounters. However, when websites do not have the financial means of deploying multiple web-servers or acquiring services of proprietary content distribution networks such as Akamai, service interruptions are unavoidable. Recently, P2P-based approaches to content distribution have been proposed to support websites facing sporadic load. Inherent characteristics of content dissemination and scalability together with adaptation of locality-awareness allow these systems to perform on par with costly content distribution networks. Thus, implicit dissemination of key parts of a website becomes vital for load-balancing at the web-server, avoiding bottlenecks for visitors. Prevailing P2P-based caching systems, however, are either unavailable to leverage locality-awareness of participating peers or enforce structural topologies to do so. Enforcing a structural topology with such systems leads to scalability issues when participating peers exhibit dynamic behaviour, which is common with P2P systems. Hence, the system undergoes constant maintenance to achieve stability, which might not even be possible. In this thesis we outline two contributions. First, we modify Flower-CDN, a P2P content distribution network that exploits both structured and unstructured P2P features, to evaluate it with real rather than synthetic data. Second, we introduce Nebula-CDN, a locality-aware, P2P content distribution network which is completely unstructured. With Nebula-CDN, we leverage locality-awareness and efficient information dissemination by clustering geographically close peers that communicate with purely epidemic algorithms. In this thesis, the design and implementation of Nebula-CDN is assessed. Due to its design and the implemented algorithms, Nebula-CDN is better suited to handle churn without support of any underlying mechanism. Moreover, we conclude that it is able to match other content distribution networks in terms of hit-ratio and accesslatency, while keeping background bandwidth usage to a minimum. / Les systèmes actuels de balancement de la charge et de distribution de contenu peuvent gérer eficacement le haut volume de requêtes reçues par les sites web. Cependant, lorsque les sites web qui n'ont pas assez de ressources financières pour déployer plusieurs serveurs ou bien acquérir des services de réseaux propriétaires de distribution de contenu tel que Akamai, les services d'interruptions sont inévitables. Récemment des approches basées sur P2P pour la distribution de contenu ont été proposées pour supporter les sites web qui reçoivent des charges sporadiques. Les caractéristiques inhérentes de la diffusion de contenu et d'extensibilité ainsi que l'adaptation de la conscience de localité permettent à ces systèmes de fonctionner d'une façon rentable avec des réseaux de distribution de contenu. Ainsi, la diffusion implicite des éléments clés d'un site web est devenu essentielle pour le balancement de la charge d'un serveur web, évitant la congestion de visiteurs. En effet, les systèmes de cache basés sur P2P, sont soit non-disponible pour as-surer une conscience de localité des noeuds participants ou pour enforcer des topologies structurelles. Enforcer une topologie strcturelle avec ces systèmes mène à des problèmes d'extension lorsque les noeuds existants manifestent un comportement dynamique, ce qui est commun pour les systèmes P2P. D'où, le système subit une maintenance constante afin d'atteindre la stabilité, ce qui ne peut même pas être possible. Dans cette thèse, nous décrivons deux contributions. Premièrement, nous modifions Flower-CDN, un réseau de distribution de contenu P2P qui exploite à la fois les caractéristiques P2P structurées et non structurées, afin de l'évaluer avec des données réelles et non-synthétiques. Deuxièmement, nous introduisons Nebula-CDN, un système conscient de la localité et un réseau de distribution de contenu P2P qui est complètement non structuré. Avec Nebula-CDN, nous exploitons la conscience de localité et la diffusion eficace d'information en distribuant géographiquement les noeuds adjacents qui communiquent avec des algorithmes purement épidémiques. Dans cette thèse, la conception et l'implémentation de Nebula-CDN est évaluée. Grâce à sa conception et ses algorithmes implémentés, Nebula-CDN est mieux adapté pour gérer la baratte sans support d'aucun sous mécanisme. De plus, nous concluons que c'est possible de correspondre autres réseaux de distribution de contenu en termes de taux et de latence d'accès, tout en maintenant l'usage de la bande passante à son minimum.