Ce mémoire présente l'implémentation d'un nouveau langage de programmation nommé Typer. Typer est un langage fonctionnel orienté vers la méta programmation. Il a été conçu pour augmenter la productivité du programmeur et lui permettre d'écrire des applications plus fiables grâce à son système de types. Pour arriver à ses fins, Typer utilise l'inférence de types et implémente un puissant système de macros. L'inférence de types permet à l'utilisateur d'omettre certains éléments, le système de macros, quant à lui, permet de compléter le programme pendant la compilation lorsque l'inférence n'est pas suffisante ou pour générer du code. Typer utilise les types dépendants pour permettre à l'utilisateur de créer des types très expressifs pouvant même être utilisés pour représenter des preuves formelles. De plus, l'expressivité des types dépendants permet au compilateur d'effectuer des vérifications plus approfondies pendant la compilation même. Ces mécaniques permettent au code source d'être moins verbeux, plus concis et plus simple à comprendre, rendant, ainsi l'écriture de programmes ou/et de preuves plus plaisante. Ces fonctionnalités sont implémentées dans l'étape que nous appelons l'élaboration, à l'intérieur de laquelle de nombreuses transformations du code source ont lieu. Ces transformations incluent l'élimination des aides syntaxiques, la résolution des identificateurs, l'expansion des macros, la propagation et l'inférence des types. / This dissertation present the implementation of a new programming language named Typer Typer is a functional programming language oriented towards meta programming. It has been created to increase the programmer productivity and enable him to write safer programs thanks to his type system. To achieve his goal, Typer use type inference and a powerful macro system. Type inference enable to user to elide some elements while the macro system enable us to complete the program during compilation. Typer use dependent type which enable the user to create very expressive types which can even be used to represent formal proofs. Furthermore, dependent type's expressivity enable the compiler to perform a in-depth checks during compilation. Those mechanics enable the source code to be less verbose, shorter and easier to understand, making the writing of new programmes more enjoyable. Those functionalities are implemented during the step we call the elaboration in which numerous transformations occur. Those transformations include the removal of syntactic sugar, identifier resolution, macro expansion and the propagation and the inference of types.

In a world of globalization, where offers continues to grow, the ability to direct people to their specific need is essential. After being key differentiating factors for Netflix and Amazon, Recommender Systems in general are no where near a downfall. Still, one downside of the basic recommender systems is that they are mainly based on indirect feedback (our behaviour, mainly form the past) as opposed to explicit demand at a specific time. Recent development in machine learning brings us closer to the possibility for a user to express it’s specific needs in natural language and get a machine generated reply. This is what Conversational Recommendation is about. Conversational recommendation encapsulates several machine learning sub-tasks. In this work, we focus our study on methods for the task of item (in our case, movie) recommendation from conversation. To explore this setting, we use, adapt and extend state of the art transformer based neural language modeling techniques to the task of recommendation from dialogue. We study the performance of different methods using the ReDial dataset [24], a conversational- recommendation dataset for movies. We also make use of a knowledge base of movies and measure their ability to improve performance for cold-start users, items, and/or both. This master thesis is divided as follows. First, we review all the basics concepts and the previous work necessary to to this lecture. When then dive deep into the specifics our data management, the different models we tested, the set-up of our experiments and the results we got. Follows the original a paper we submitted at RecSys 2020 Conference. Note that their is a minor inconsistency since throughout the thesis, we use v to represent items but in the paper, we used i. Overall, we find that pre-trained transformer models outperform baselines even if the baselines have access to the user preferences manually extracted from their utterances. / Dans un monde de mondialisation, où les offres continuent de croître, la capacité de référer les gens vers leurs besoins spécifiques est essentiel. Après avoir été un facteur de différenciation clé pour Netflix et Amazon, les systèmes de recommandation en général ne sont pas près de disparaître. Néanmoins, l’un des leurs inconvénients est qu’ils sont principalement basés sur des informations indirects (notre comportement, principalement du passé) par opposition à une demande explicite à un moment donné. Le développement récent de l’apprentissage automatique nous rapproche de la possibilité d’exprimer nos besoins spécifiques en langage naturel et d’obtenir une réponse générée par la machine. C’est ce en quoi consiste la recommandation conversationnelle. La recommandation conversationnelle englobe plusieurs sous-tâches d’apprentissage automatique. Dans ce travail, nous concentrons notre étude sur les méthodes entourant la tâche de recommandation d’item (dans notre cas, un film) à partir d’un dialogue. Pour explorer cette avenue, nous adaptons et étendons les techniques de modélisation du langage basées sur les transformeurs à la tâche de recommandation à partir du dialogue. Nous étudions les performances de différentes méthodes à l’aide de l’ensemble de données ReDial [24], un ensemble de données de recommandation conversationnelle pour les films. Nous utilisons également une base de connaissances de films et mesurons sa capacité à améliorer les performances lorsque peu d’information sur les utilisateurs/éléments est disponible. Ce mémoire par article est divisé comme suit. Tout d’abord, nous passons en revue tous les concepts de base et les travaux antérieurs nécessaires à cette lecture. Ensuite, nous élaborons les spécificités de notre gestion des données, les différents modèles que nous avons testés, la mise en place de nos expériences et les résultats que nous avons obtenus. Suit l’article original que nous avons soumis à la conférence RecSys 2020. Notez qu’il y a une incohérence mineure puisque tout au long du mémoire, nous utilisons v pour représenter les éléments mais dans l’article, nous avons utilisé i. Dans l’ensemble, nous constatons que les modèles de transformeurs pré-entraînés surpassent les modèles de bases même si les modèles de base ont accès aux préférences utilisateur extraites manuellement des dialogues.

Computers are widely present in our daily life and are used in critical applic-ations like cars, planes, pacemakers. Those real-time systems are nowadaysbased on processors which have an increasing complexity and have specifichardware services designed to reduce task preemption and migration over-heads. However using those services can add unpredictable overheads whenthe system has to switch from one task to another in some cases.This document screens existing solutions used in commonly availableprocessors to ease preemption and migration to highlight their strengths andweaknesses. A new hardware service is proposed to speed up task switchingat the L1 cache level, to reduce context switch overheads and to improvesystem predictability.The solution presented is based on stacking several identical cachememories at the L1 level. Each layer is able to save and restore its completestate independently to/from the main memory. One layer can be used forthe active task running on the processor while another layers can be restoredor saved concurrently. The active task can remain in execution until thepreempting task is ready in another layer after restoration from the mainmemory. The context switch between tasks can then be performed in avery short time by switching to the other layer which is now ready to runthe preempting task. Furthermore, the task will be resumed with the exactL1 cache memory state as saved earlier after the previous preemption. Theprevious task state can be sent back to the main memory for future use.Using this mechanism can lead to minimise the time required for migrationsand preemptions and consequently lower overheads and limit cache missesdue to preemptions and usually considered in the cache migration andpreemption delays. Isolation between tasks is also provided as they areexecuted from a dedicated layer.Both uniprocessor and multiprocessor designs are presented along withimplications on the real-time theory induced by the use of this hardware ser-vice. An implementation of the system is characterized and results show im-provements to the maximum and average execution time of a set of varioustasks: When the same size is used for the baseline cache and HwCS layers,94% of the tasks have a better execution time (up to 67%) and 80% have a bet-ter Worst Case Execution Time (WCET). 80% of the tasks are more predictableand the remaining 20% still have a better execution time. When we split thebaseline cache size among layers of the HwCS, measurements show that 75%of the tasks have a better execution time (up to 67%) leading to 50% of thetasks having a better WCET. Only 6% of the tasks suffer from worse executiontime and worse predictability while 75% of the tasks remain more predictablewhen using the HwCS compared to the baseline cache. / Les ordinateurs ont envahi notre quotidien et sont de plus en plus souventutilisés pour remplir des missions critiques. Ces systèmes temps réel sontbasés sur des processeurs dont la complexité augmente sans cesse. Des ser-vices matériels spécifiques permettent de réduire les coûts de préemption etmigration. Malheureusement, ces services ajoutent des temps morts lorsquele système doit passer d’une tâche à une autre.Ce document expose les solutions actuelles utilisées dans les processeurscourants pour mettre en lumière leurs qualités et défauts. Un nouveau ser-vice matériel (HwCS) est proposé afin d’accélérer le changement de tâches aupremier niveau de mémoire (L1) et de réduire ainsi les temps morts dus auxchangements de contextes tout en améliorant la prédictibilité du système.Bien que cette thèse se concentre sur le cache L1, le concept développépeut également s’appliquer aux autres niveaux de mémoire ainsi qu’àtout bloc dépendant du contexte. La solution présentée se base sur unempilement de caches identiques au premier niveau. Chaque couche del’empilement est capable de sauvegarder ou recharger son état vers/depuisla mémoire principale du système en toute autonomie. Une couche peutêtre utilisée par la tâche active pendant qu’une autre peut sauvegarder ourestaurer l’état d’une autre tâche. La tâche active peut ainsi poursuivre sonexécution en attendant que la tâche suivante soit rechargée. Le changementde contexte entre la tâche active et la tâche suivante peut alors avoir lieu enun temps très court. De plus, la tâche reprendra son exécution sur un cacheL1 dont l’état sera identique à celui au moment où elle a été interrompueprécédemment. L’état du cache de la tâche désormais inactive peut êtresauvegardé dans la mémoire principale en vue d’une utilisation ultérieure.Ce mécanisme permet de réduire au strict minimum le temps de calculperdu à cause des préemptions et migrations, les temps de sauvegarde et derechargement de la L1 n’ayant plus d’influence sur l’exécution des tâches. Deplus, chaque niveau étant dédié à une tâche, les interférences entre tâchessont réduites.Les propriétés ainsi que les implications sur les aspects temps réelsthéoriques sont présentées pour des systèmes mono et multiprocesseurs.Une implémentation d’un système uniprocesseur incluant ce servicematériel et sa caractérisation par rapport à l’exécution d’un set de tâchessont également présentées ainsi que les bénéfices apportés par le HwCS:Lorsque les couches du HwCS ont la même taille que le cache de base, 94%des tâches ont un meilleur temps d’exécution (jusqu’à 67%) et 80% ont unmeilleur pire temps d’exécution (WCET). 80% des tâches deviennent plusprédictibles et les 20% restants bénéficient néanmoins d’un meilleur WCET.Toutefois, si la taille du cache est partagée entre les couches du HwCS, lesmesures montrent que 75% des tâches ont un meilleur temps d’exécution,impliquant un meilleur WCET pour la moitié des tâches du système. Seule-ment 6% des tâches voient leur WCET augmenter et leur prédictibilitédiminuer tandis que 75% des tâches améliorent leur prédictibilité grâce auHwCS. / Doctorat en Sciences de l'ingénieur et technologie / info:eu-repo/semantics/nonPublished

Thèse numérisée par la Direction des bibliothèques de l'Université de Montréal. / Cette thèse porte sur l'introduction de la carte numérique dans la pratique du développement local. Nous avons travaillé sur la compréhension d'un processus cognitif d'évaluation t interpellant et interagissant avec les connaissances de perception, de raisonnement et la vie communautaire. À l'heure actuelle, la cartographie produit par l'ordinateur fait l'objet de nombreux travaux en ce qui concerne leurs techniques, leur structure et les outils pour les mettre en œuvre. Son utilisation dans un processus de planification et de consultation du développement d'une activité spatiale y est rarement étudiée et utilisée. Quand elle l'est, c'est de manière secondaire. L'introduction de la nouvelle technologie dans le développement local est ici un médium de communication pour structurer des applications interactives pouvant ainsi afficher les événements souhaités par les acteurs1et les flots de données s'y rattachant. Le modèle que nous proposons répond d'un développement convivial d'une activité. Notre stratégie consiste à afficher des cartes en plan puis des scènes en élévation et d'examiner les résultantes sur les prises de décisions et sur les réalisations. Cette thèse résulte donc d'une préoccupation : le souci de participer, pour une modeste partie, de la place de la carte numérique dans la pratique du développement local. Une recension de travaux scientifiques sur le sujet permet de noter que l'utilisation des cartes numériques dans un processus de consultation démocratique reste encore très peu mis en pratique. Dans un contexte social où les organismes locaux prennent de plus en plus leur place dans les interventions et dans les prises de décisions, la connaissance du territoire et des besoins par les décideurs et les utilisateurs devient incontournable. La recherche tente de répondre à deux défis : de l'un, en arriver à satisfaire les organismes de développement des activités et, de l'autre, à cautionner par les décisions prises à des interventions aussi bien viables que durables. Que dit la documentation? Les auteurs corroborent en disant que l'opinion des usagers est devenue, avec le temps, un outil de mesure importante dans l'élaboration d'une activité. L'informatique ajoutée à un processus démocratique où la conduite est de répondre aux besoins de tous les acteurs, peut-elle être un instrument supplémentaire de planification stratégique pour animer, pour améliorer l'accès à l'information et pour contribuer à réduire l'incertitude de son développement? Nous prétendons que la carte numérique fournit un moyen innovateur pour faire participer de façon active les acteurs aux différentes étapes d'une activité. À cause du rôle particulier que peut jouer la communauté locale, ce médium apporte une option dynamique aux efforts de l'identification des besoins, des objectifs, d'analyse spatiale, des scénarisations et des plans d'actions [les décisions]. La démocratisation de la planification, c'est-à-dire la plus grande participation des acteurs à l'activité en développement devrait aider à définir des interventions acceptables pour toutes les parties concernées. Cette convivialité est un grand pas vers le développement durable des territoires locaux. Nous allons vérifier si la carte numérique est techniquement réalisable dans un processus de développement local. Peut-elle exprimer plus facilement les besoins de l'organisation et de la communauté? Fait-elle la différence ou l'indifférence dans les réunions? Est-elle un apport au processus de réflexion, de discussion et de négociation? La nouvelle technologie informatique dans notre démarche se veut un moyen d'expression « participative » visant à aider tous les participants à établir un continuum entre les besoins exprimés et les interventions réalisées par l'organisme de développement. Elle devrait tout au long du processus faciliter le dialogue, la discussion, la réflexion, la prise d'opinions, les négociations pour contester ou affirmer... les besoins exprimés. Dans ce contexte, l'affichage numérique de l'activité offre un potentiel intéressant pour prendre des résolutions. Elle donne un regard immédiat de l'activité et son environnement, en même temps, une perspective quant aux conditions futures réduisant ainsi l'incertitude dans les prises de décisions. Le modèle de recherche que nous proposons, c'est-à-dire l'usage de la technique numérique dans le développement local, vise sa « transférabilité » à d'autres territoires locaux. Pour soumettre à l'épreuve la démarche suggérée, nous avons convié deux organismes publics œuvrant dans le développement de leur territoire respectif localisés dans la région de Montréal. Nous avons travaillé en étroite collaboration avec la Société du Parc des Îles et la Société d'initiatives de développement de l'artère commerciale Sainte-Catherine Est à l'élaboration de deux activités : l'une récréotouristique dans les lagunes de l'île Notre-Dame et l'autre commerciale sur la rue Sainte-Catherine Est. Notre recherche confirme que l'utilisation de la carte numérique est conviviale dans le développement d'une activité territoriale. Elle permet la démocratisation de la planification d'une activité spatiale en territoire local et l'implication des acteurs à toutes les étapes de son élaboration. C'est donc les participants qui décident du caractère que l'on veut lui attribuer et de l'ensemble des changements au cours du temps ; Les résultats sont conformes à ce que l'organisation et la communauté locale souhaitent selon des ententes entre les parties concernées.

Grâce à leur flexibilité et à leur facilité d’installation, les réseaux maillés sans fil (WMNs) permettent un déploiement d’une infrastructure à faible coût. Ces réseaux étendent la couverture des réseaux filaires permettant, ainsi, une connexion n’importe quand et n’importe où. Toutefois, leur performance est dégradée par les interférences et la congestion. Ces derniers causent des pertes de paquets et une augmentation du délai de transmission d’une façon drastique. Dans cette thèse, nous nous intéressons au routage adaptatif et à la stabilité dans ce type de réseaux. Dans une première partie de la thèse, nous nous intéressons à la conception d’une métrique de routage et à la sélection des passerelles permettant d’améliorer la performance des WMNs. Dans ce contexte nous proposons un protocole de routage à la source basé sur une nouvelle métrique. Cette métrique permet non seulement de capturer certaines caractéristiques des liens tels que les interférences inter-flux et intra-flux, le taux de perte des paquets mais également la surcharge des passerelles. Les résultats numériques montrent que la performance de cette métrique est meilleure que celle des solutions proposées dans la littérature. Dans une deuxième partie de la thèse, nous nous intéressons à certaines zones critiques dans les WMNs. Ces zones se trouvent autour des passerelles qui connaissent une concentration plus élevé du trafic ; elles risquent de provoquer des interférences et des congestions. À cet égard, nous proposons un protocole de routage proactif et adaptatif basé sur l’apprentissage par renforcement et qui pénalise les liens de mauvaise qualité lorsqu’on s’approche des passerelles. Un chemin dont la qualité des liens autour d’une passerelle est meilleure sera plus favorisé que les autres chemins de moindre qualité. Nous utilisons l’algorithme de Q-learning pour mettre à jour dynamiquement les coûts des chemins, sélectionner les prochains nœuds pour faire suivre les paquets vers les passerelles choisies et explorer d’autres nœuds voisins. Les résultats numériques montrent que notre protocole distribué, présente de meilleurs résultats comparativement aux protocoles présentés dans la littérature. Dans une troisième partie de cette thèse, nous nous intéressons aux problèmes d’instabilité des réseaux maillés sans fil. En effet, l’instabilité se produit à cause des changements fréquents des routes qui sont causés par les variations instantanées des qualités des liens dues à la présence des interférences et de la congestion. Ainsi, après une analyse de l’instabilité, nous proposons d’utiliser le nombre de variations des chemins dans une table de routage comme indicateur de perturbation des réseaux et nous utilisons la fonction d’entropie, connue dans les mesures de l’incertitude et du désordre des systèmes, pour sélectionner les routes stables. Les résultats numériques montrent de meilleures performances de notre protocole en comparaison avec d’autres protocoles dans la littérature en termes de débit, délai, taux de perte des paquets et l’indice de Gini. / Thanks to their flexibility and their simplicity of installation, Wireless Mesh Networks (WMNs) allow a low cost deployment of network infrastructure. They can be used to extend wired networks coverage allowing connectivity anytime and anywhere. However, WMNs may suffer from drastic performance degradation (e.g., increased packet loss ratio and delay) because of interferences and congestion. In this thesis, we are interested in adaptive routing and stability in WMNs. In the first part of the thesis, we focus on defining new routing metric and gateway selection scheme to improve WMNs performance. In this context, we propose a source routing protocol based on a new metric which takes into account packet losses, intra-flow interferences, inter-flow interferences and load at gateways together to select best paths to best gateways. Simulation results show that the proposed metric improves the network performance and outperforms existing metrics in the literature. In the second part of the thesis, we focus on critical zones, in WMNs, that consist of mesh routers which are located in neighborhoods of gateways where traffic concentration may occur. This traffic concentration may increase congestion and interferences excessively on wireless channels around the gateways. Thus, we propose a proactive and adaptive routing protocol based on reinforcement learning which increasingly penalizes links with bad quality as we get closer to gateways. We use Q-learning algorithm to dynamically update path costs and to select the next hop each time a packet is forwarded toward a given gateway; learning agents in each mesh router learn the best link to forward an incoming packet and explore new alternatives in the future. Simulation results show that our distributed routing protocol is less sensitive to interferences and outperforms existing protocols in the literature. In the third part of this thesis, we focus on the problems of instability in WMNs. Instability occurs when routes flapping are frequent. Routes flapping are caused by the variations of link quality due to interferences and congestion. Thus, after analyzing factors that may cause network instability, we propose to use the number of path variations in routing tables as an indicator of network instability. Also, we use entropy function, usually used to measure uncertainty and disorder in systems, to define node stability, and thus, select the most stable routes in the WMNs. Simulation results show that our stability-based routing protocol outperforms existing routing protocols in the literature in terms of throughput, delay, loss rate, and Gini index.

La tâche de maintenance ainsi que la compréhension des programmes orientés objet (OO) deviennent de plus en plus coûteuses. L’analyse des liens de dépendance peut être une solution pour faciliter ces tâches d’ingénierie. Cependant, analyser les liens de dépendance est une tâche à la fois importante et difficile. Nous proposons une approche pour l'étude des liens de dépendance internes pour des programmes OO, dans un cadre probabiliste, où les entrées du programme peuvent être modélisées comme un vecteur aléatoire, ou comme une chaîne de Markov. Dans ce cadre, les métriques de couplage deviennent des variables aléatoires dont les distributions de probabilité peuvent être étudiées en utilisant les techniques de simulation Monte-Carlo. Les distributions obtenues constituent un point d’entrée pour comprendre les liens de dépendance internes entre les éléments du programme, ainsi que leur comportement général. Ce travail est valable dans le cas où les valeurs prises par la métrique dépendent des entrées du programme et que ces entrées ne sont pas fixées à priori. Nous illustrons notre approche par deux études de cas. / The task of maintenance and understanding of object-oriented programs is becoming increasingly costly. Dependency analysis can be a solution to facilitate this engineering task. However, dependency analysis is a task both important and difficult. We propose a framework for studying program internal dependencies in a probabilistic setting, where the program inputs are modeled either as a random vector, or as a Markov chain. In that setting, coupling metrics become random variables whose probability distributions can be studied via Monte-Carlo simulation. The obtained distributions provide an entry point for understanding the internal dependencies of program elements, as well as their general behaviour. This framework is appropriate for the (common) situation where the value taken by the metric does depend on the program inputs and where those inputs are not fixed a priori. We provide a concrete illustration with two case studies.

Nous proposons une approche probabiliste afin de déterminer l’impact des changements dans les programmes à objets. Cette approche sert à prédire, pour un changement donné dans une classe du système, l’ensemble des autres classes potentiellement affectées par ce changement. Cette prédiction est donnée sous la forme d’une probabilité qui dépend d’une part, des interactions entre les classes exprimées en termes de nombre d’invocations et d’autre part, des relations extraites à partir du code source. Ces relations sont extraites automatiquement par rétro-ingénierie. Pour la mise en oeuvre de notre approche, nous proposons une approche basée sur les réseaux bayésiens. Après une phase d’apprentissage, ces réseaux prédisent l’ensemble des classes affectées par un changement. L’approche probabiliste proposée est évaluée avec deux scénarios distincts mettant en oeuvre plusieurs types de changements effectués sur différents systèmes. Pour les systèmes qui possèdent des données historiques, l’apprentissage a été réalisé à partir des anciennes versions. Pour les systèmes dont on ne possède pas assez de données relatives aux changements de ses versions antécédentes, l’apprentissage a été réalisé à l’aide des données extraites d’autres systèmes. / We study the possibility of predicting the impact of changes in object-oriented code using bayesian networks. For each change type, we produce a bayesian network that determines the probability that a class is impacted given that another class is changed. Each network takes as input a set of possible relationships between classes. We train our networks using historical data. The proposed impact-prediction approach is evaluated with two different scenarios, various types of changes, and five systems. In the first scenario, we use as training data, the changes performed in the previous versions of the same system. In the second scenario training data is borrowed from systems that are different from the changed one. Our evaluation showed that, in both cases, we obtain very good predictions, even though they are better in the first scenario.

L'attaque de retransmission sélective est une menace sérieuse dans les réseaux de capteurs sans fil (WSN), en particulier dans les systèmes de surveillance. Les noeuds peuvent supprimer de manière malicieuse certains paquets de données sensibles, ce qui risque de détruire la valeur des données assemblées dans le réseau et de diminuer la disponibilité des services des capteurs. Nous présentons un système de sécurité léger basé sur l'envoi de faux rapports pour identifier les attaques de retransmission sélective après avoir montré les inconvénients des systèmes existants. Le grand avantage de notre approche est que la station de base attend une séquence de faux paquets à un moment précis sans avoir communiqué avec les noeuds du réseau. Par conséquent, elle sera capable de détecter une perte de paquets. L'analyse théorique montre que le système proposé peut identifier ce type d'attaque et peut alors améliorer la robustesse du réseau dans des conditions d'un bon compromis entre la fiabilité de la sécurité et le coût de transmission. Notre système peut atteindre un taux de réussite élevé d‟identification face à un grand nombre de noeuds malicieux, tandis que le coût de transmission peut être contrôlé dans des limites raisonnables. / The selective forwarding attack is a serious threat in wireless sensor networks (WSN), especially in surveillance systems. Nodes can maliciously delete some sensitive data packets, which could destroy the value of the data assembled in the network and reduce its sensors availability. After describing the drawbacks of the existing systems in this thesis, we will present a lightweight security system based on sending fake reports used to identify selective forwarding attacks. The great advantage in our approach is that the base station expects a number of packets at a specific time. Therefore, it will be able to detect missing or delayed packets. Theoretical analysis shows that the proposed system can identify this type of attack, which will improve the robustness of the network under conditions of a good tradeoff between the security, reliability and communication overhead. Our system can achieve a high ratio of identification when facing a large number of malicious nodes, while the communication overhead can be controlled within reasonable bounds.

Nous présentons une nouvelle approche pour formuler et calculer le temps de séparation des événements utilisé dans l’analyse et la vérification de différents systèmes cycliques et acycliques sous des contraintes linéaires-min-max avec des composants ayant des délais finis et infinis. Notre approche consiste à formuler le problème sous la forme d’un programme entier mixte, puis à utiliser le solveur Cplex pour avoir les temps de séparation entre les événements. Afin de démontrer l’utilité en pratique de notre approche, nous l’avons utilisée pour la vérification et l’analyse d’une puce asynchrone d’Intel de calcul d’équations différentielles. Comparée aux travaux précédents, notre approche est basée sur une formulation exacte et elle permet non seulement de calculer le maximum de séparation, mais aussi de trouver un ordonnancement cyclique et de calculer les temps de séparation correspondant aux différentes périodes possibles de cet ordonnancement. / We present a new approach for formulating and computing time separation of events used for timing analysis of different types of cyclic and acyclic systems that obey to linear-min-max type constraints with finite and infinite bounded component delays. Our approach consists of formulating the problem as a mixed integer program then using the solver Cplex to get time separations between events. In order to demonstrate the practical use of our approach we apply it for the verification and analysis of an Intel asynchronous differential equation solver chip. Compared to previous work, our approach is based on exact formulation and it allows not only the maximum separation computing, but it can also provide cyclic schedules and compute bound on possible periods of such schedules.

L'ensemble de mon travail a été réalisé grâce a l'utilisation de logiciel libre. / La demande d'applications pour les plateformes mobiles a explosé ces dernières années. Chaque compagnie souhaite maintenant offrir pour ces nouveaux appareils les mêmes services que ceux offerts traditionnellement sur internet. Cependant, ces entreprises n'ont bien souvent que peu ou pas de connaissances concernant le développement et le déploiement de tels services. Généralement, la solution choisie consiste à externaliser ce travail en le sous-traitant à une autre compagnie. Dans ce contexte, il est souvent compliqué de s'assurer d'une part que le sous-traitant respecte le cahier des charges et d'autre part que le travail fourni est conforme aux recommandations émises par les fabricants des plateformes mobiles. Afin de pallier au second problème, nous avons créé un système de listes de vérification interactives pour plateformes mobiles. Ce système permet d'évaluer le niveau de conformité des différents composants de l'interface d'une application développée pour une plateforme mobile avec les recommandations du fabricant de cette plateforme. La solution retenue permet de se concentrer sur certains éléments particuliers de l'interface et pallie ainsi aux limites des listes de vérification classiques qui sont souvent trop longues et peu pratiques. La solution retenue offre de plus la possibilité de comparer facilement les caractéristiques des plateformes mobiles entre elles. Pour réaliser ce système, nous avons consulté de nombreux documents portant sur l'univers des plateformes mobiles afin de mieux appréhender leurs spécificités. Suite à l'étude de différentes plateformes, deux d’entre elles, soit iOS et BlackBerry, ont été retenues (il faut noter que la compagnie où s'est effectuée la recherche disposait déjà d'applications pour ces plateformes). Nous avons ensuite analysé plus finement la documentation technique fournie par chacun des fabricants afin d'en extraire les points importants. Afin que les données soient comparables, nous avons créé une nomenclature commune regroupant les composants de l'interface graphique en grandes familles (ex. : barres, saisie d'information, …) en tenant compte également du type d'interaction avec l'appareil (ex. : écran tactile). Nous avons ensuite conçu une solution permettant d'évaluer le niveau de conformité d'une application. L'idée retenue se base sur des listes de vérification permettant de systématiser le processus d'évaluation. Pour pallier aux limites de ces listes, souvent trop longues, nous permettons à l'utilisateur, via un ensemble de filtres, de se concentrer sur un sous-ensemble de composants de l’interface qu'il souhaite évaluer. L'implémentation de cette solution a été réalisée en totalité grâce à des technologies libres et de standard ouvert. De cette façon, nous nous sommes assurés de la portabilité de la solution développée et de l’absence de coûts supplémentaires liés à l'achat de licences. Le système utilise les standards web et repose sur une architecture basée sur le système d'exploitation GNU/Linux, le serveur web Apache, la base de données MySQL et le langage de scripts PHP. Ces logiciels ont déjà fait leurs preuves aussi bien pour les entreprises que pour les particuliers. De plus, la communauté très active qui s'est constituée autour de ces logiciels assure un bon support et une grande stabilité. Après avoir fait le choix de l’environnement de développement, la phase d'implémentation s'est ensuite déroulée en plusieurs étapes. Tout d'abord, l'information a été structurée selon la nomenclature mentionnée plus haut afin de créer le schéma de la base de données. Ensuite, toutes les pages ont été codées avec le langage à balises HTML et les scripts PHP pour le côté serveur et avec JavaScript pour le côté client. Enfin, l'information peut être affichée grâce aux feuilles de style en cascade (CSS), une technologie web permettant de séparer le fond de la forme en matière de mise en page. Nous avons choisi un modèle de développement itératif qui a impliqué les principaux utilisateurs dès les premières étapes de la conception du système. Cette implication s’est poursuivie jusqu’à la fin du projet afin de s'assurer que les fonctionnalités mises en place répondaient aux attentes. L’architecture modulaire qui a été retenue permet également d’adapter facilement le système aux besoins futurs. Afin de mieux comprendre comment on utilise le système, on passe en revue les différentes étapes nécessaires à la réalisation d'une évaluation. Enfin, on a réalisé une étude avec quatre utilisateurs pour évaluer l'utilisabilité du système et recueillir leur niveau de satisfaction. / The need for mobile platforms has increased in the last decade. Companies offering traditional internet services now want to move their applications on these new devices. But, most of the time, these companies do not really have the knowledge to create such applications and often ask a third party company to do the job for them. In this context, it is difficult to evaluate if the solution developed follows the recommendations of the device maker. A system based on interactive check lists has thus been created for this purpose. This system enables the evaluation of the conformity level of an application with the recommendations of the device maker, thanks to numerous filters that let the user focus on specific parts of the graphic interface. The idea behind the project was first to address some problematic issues with classical check lists and to enable the comparison of several mobile platforms with regard to specific interface components. To create this system, a lot of information about mobile platforms has first been collected. After reviewing many mobile platforms, it was decided to focus on iOS and BlackBerry, since the company where the research was performed had already applications running on them. For each platform, the major recommandations to be satisfied were identified. Also, to be sure that the extracted recommendations could be compared, a common nomenclature has been created, where the recommandations are grouped by interface components (ex: bars, data input,…) and by the type of interaction (ex: touch screen). After these preliminary steps, a solution for evaluating the level of compliance was created. We favored a check list approach because it offers a systematic evaluation process. To avoid lists of excessive length, filters were introduced in the system to allow the user to focus on particular aspects of the interface. The implementation was totally realized with open source technologies and open standards. This choice was motivated by the portability of the developed system and by the absence of licence fees. The system relies on web standards and runs on an architecture made of the CNU/Linux operating system, Apache web server, MySQL database and the script language PHP. This software has already proven its reliability for enterprises and for home users. Furthermore, the community evolving around this software offers a good support and ensures a high level of stability. After setting up the development environment, the implementation phase was engaged and took place over a number of phases. The first phase was the creation of the database structure, using the aforementioned nomenclature. The next phase was dedicated to the coding of the different web pages, thanks to the tag language HTML and the PHP scripts on the server side and JavaScript on the client side. Finally, the web page setting was developed using the cascading style sheet (CSS), a web technology that segregates the substance from the style of the web content. We chose an iterative development model where the end users were involved from the early stages of the project. This approach provides a guarantee that the user requirements are fulfilled and that any new developments will be in accordance with the expectations. Furthermore, the system is such that it can be easily modified to tackle future needs. To be able to understand how we use the systeme, we are reviewing the different steps needed to realise an evaluation. Finally, we have made a study with four users to evaluate the usability of the system and to gather their satisfaction level.