Thesis (M.S.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 1980. / MICROFICHE COPY AVAILABLE IN ARCHIVES AND ENGINEERING. / Vita. / Bibliography: leaves 98-102. / by Brad Allen Myers. / M.S.

Abstract not available

Cette thèse traite le problème de la réécriture de requêtes en termes de vues en présence de contraintes de valeurs. Les contraintes de valeurs permettent de restreindre le domaine de valeur d'un attribut donné. Elles connaissent un regain d'intérêt depuis leur utilisation dans le cadre du langage d'ontologie du web OWL. Ce travail est motivé par une application réelle qui vise à permettre l'intégration flexible d'un grand nombre de sources de données agricoles. L'étude de la décidabilité de ce problème est basée sur le cadre des logiques de description. Ce travail montre également que le problème de calculer les réécritures engendrées par les contraintes de valeurs se rattache au cadre de découverte des connaissances dans les bases de données introduit par Mannila and Toivonen. Ceci nous permet d'adpter des algorithmes exustants et efficaces pour calculer ces réécritures et proposer un prototype de réécriture qui passe à l'echelle.

Les systèmes temps réel à contraintes temporelles strictes sont caractérisés par des ensembles de tâches pour lesquelles sont connus l'échéance, le modèle d'arrivée (fréquence) et la durée d'exécution pire cas (WCET). Nous nous intéressons à l'ordonnancement de ces systèmes sur plate-forme multiprocesseur. Garantir le respect des échéances pour un algorithme d'ordonnancement est l'une des problématiques majeures de cette thématique. Nous allons plus loin en nous intéressant à la sûreté temporelle, que nous caractérisons par les propriétés (i) de robustesse et (ii) de viabilité. La robustesse consiste à proposer un intervalle sur les augmentations (i-a) de WCET et (i-b) de fréquence tel que les échéances soient respectées. La viabilité consiste cette fois à garantir le respect des échéances lors du relâchement des contraintes (ii-a) de WCET (réduction), (ii-b) de fréquence (réduction) et (ii-c) d'échéance (augmentation). La robustesse revient alors à tolérer l'imprévu, tandis que la viabilité est la garantie que l'algorithme d'ordonnancement n'est pas sujet à des anomalies suite à un relâchement de contraintes. Nous considérons l'ordonnancement en priorités fixes, où chaque occurrence d'une tâche est ordonnancée avec la même priorité. Dans un premier temps, nous étudions la propriété de robustesse dans les approches d'ordonnancement hors-ligne et sans migration (partitionnement). Nous traitons le cas des tâches avec ou sans partage de ressources. Dans un second temps, nous étudions la propriété de viabilité d'une approche d'ordonnancement en ligne avec migrations restreintes et sans partage de ressources.

Depuis 20 ans, l'information quantique a profondément changé notre façon d'appréhender la physique atomique, ainsi que la nature des ressources utiles au calcul. Cette thèse aborde trois aspects relatifs à l'information quantique: - Le phénomène de décohérence -- responsable de la transition quantique-classique -- est décrit quantitativement grâce à l'analyse de l'information mutuelle entre deux systèmes quantiques ; - Une nouvelle classe de codes correcteurs d'erreurs quantiques -- les codes convolutifs -- est introduite en detail et il est montré qu'elle partage les propriétés des codes convolutifs classiques (codage et décodage en ligne, algorithme efficace d'estimation d'erreurs au maximum de vraisemblance, existence de condition nécessaire et suffisante pour l'absence d'erreur catastrophique, etc.) ; - Quelques propositions expérimentales de manipulation d'information quantique sont décrites (porte de Toffoli et clonage universel pour l'électrodynamique quantique en cavité).

Une coloration propre d'un graphe est une fonction qui attribue une couleur à chaque sommet du graphe avec la restriction que 2 sommets voisins ont des couleurs distinctes. Les colorations propres permettent de modéliser des problèmes d'ordonnancement, d'allocation de fréquences ou de registres. Le problème de trouver une coloration propre d'un graphe qui minimise le nombre de couleurs est un problème NP-difficile très connu. Dans cette thèse, nous étudions le nombre de Grundy et le nombre b-chromatique des graphes, deux paramètres qui permettent d'évaluer quelques heuristiques pour le problème de la coloration propre. Nous commençons par dresser un état de l'art des résultats sur ces deux paramètres. Puis, nous montrons que déterminer le nombre de Grundy est NP-difficile sur les graphes bipartis ou cordaux mais polynomial sur le graphes sans P5 bipartis. Ensuite, nous montrons que déterminer le nombre b-chromatique est NP-difficile pour un graphe cordal et distance-héréditaire, et nous donnons des algorithmes polynomiaux pour certaines sous-classes de graphes blocs, complémentaires des graphes bipartis et P4-sparses. Nous considérons également la complexité à paramètre fixé de déterminer le nombre de Grundy (resp. nombre b-chromatique) et en particulier, nous montrons que décider si le nombre de Grundy (ou le nombre b-chromatique) d'un graphe G est au moins |V(G)| - k admet un algorithme FPT lorsque k est le paramètre. Enfin, nous considérons la complexité de nombreux problèmes liés à la comparaison du nombre de Grundy et nombre b-chromatique avec divers autres paramètres d'un graphe.

Le langage APL a été défini en 1962 par K.E. Iverson dans un ouvrage intitulé " A Programming Language " [Iverson62]. En dépit des difficultés nouvelles que ce langage posait aux concepteurs, des interprètes APL furent rapidement disponibles chez I.B.M. [Chomat71, Iverson73]. Ce langage s'étant d'emblée révélé intéressant pour toutes les applications réclamant plus de programmation que de longs calculs, plusieurs systèmes virent le jour chez d'autres constructeurs [Martin72, Girardot76]. Réalisés pour la plupart sur de gros ordinateurs, ils réclament des ressources hors de proportion avec les moyens habituels mis à la disposition des ingénieurs ou des étudiants. Parallèlement de nombreux travaux de recherche ont été menés afin d'accélérer l'interprétation du langage. P.S. Abrams fut le premier à introduire certaines notions fondamentales d'optimisation comme le beating devenu classique de nos jours. Il a également envisagé la construction d'un matériel muni d'un code machine très voisin du langage APL [Abrams70]. D'autres approches ont consisté à réaliser un maximum de fonctions au niveau matériel, en microprogrammant un sous-interprète scalaire ou vectoriel, et en rédigeant ensuite, dans l'APL restreint ainsi obtenu, l'interprète complet. L'étude des divers systèmes existants montre que les architectures purement logicielles, utilisant presque toujours une technique d'interprétation naïve sont les plus répandues. Cependant, même si les architectures sont restées identiques, l'évolution des techniques d'implantation a permis des progrès considérables. De fait, il semble assez difficile de progresser beaucoup dans une voie purement logicielle si ce n'est par des approches radicalement différentes comme celles décrites dans [Hewlett77]. Ce système APL réalisé sur HP 3000 est en fait un compilateur incrémental générant pour chaque ligne de code qu'il exécute pour la première fois, un fragment de code machine. , Une signature associée à ce code permet de savoir ultérieurement si la réutilisation de ce code est possible.

La conception d'algorithmes pour les systèmes concurrents et répartis est subtile et difficile. Ces systèmes sont enclins à des blocages et à des conditions de course qui peuvent se produire dans des entrelacements particuliers d'actions de processus et sont par conséquent difficiles à reproduire. Il est souvent non-trivial d'énoncer précisément les propriétés attendues d'un algorithme et les hypothèses que l'environnement est supposé de satisfaire pour que l'algorithme se comporte correctement. La vérification formelle est une technique essentielle pour modéliser le système et ses propriétés et s'assurer de sa correction au moyen du model checking. Des langages formels tels TLA+ permettent de décrire des algorithmes compliqués de manière assez concise, mais les concepteurs d'algorithmes trouvent souvent difficile de modéliser un algorithme par un ensemble de formules. Dans ce mémoire nous présentons le langage PlusCal-2 qui vise à allier la simplicité de pseudo-code à la capacité d'être vérifié formellement. PlusCal-2 améliore le langage algorithmique PlusCal conçu par Lamport en levant certaines restrictions de ce langage et en y ajoutant de nouvelles constructions. Notre langage est destiné à la description d'algorithmes à un niveau élevé d'abstraction. Sa syntaxe ressemble à du pseudo-code mais il est tout à fait expressif et doté d'une sémantique formelle. Des instances finies d'algorithmes écrits en PlusCal-2 peuvent être vérifiées à l'aide du model checker tlc. La deuxième contribution de cette thèse porte sur l'étude de méthodes de réduction par ordre partiel à l'aide de relations de dépendance conditionnelle et constante. Pour calculer la dépendance conditionnelle pour les algorithmes en PlusCal-2 nous exploitons des informations sur la localité des actions et nous générons des prédicats d'indépendance. Nous proposons également une adaptation d'un algorithme de réduction par ordre partiel dynamique pour une variante du model checker tlc. Enfin, nous proposons une variante d'un algorithme de réduction par ordre partiel statique (comme alternative à l'algorithme dynamique), s'appuyant sur une relation de dépendance constante, et son implantation au sein de tlc. Nous présentons nos résultats expérimentaux et une preuve de correction.

In this PhD, we present some algorithms and complexity results for two general problems that arise in the analysis of a metabolic network: the search for elementary modes of a network and the search for minimal precursors sets. Elementary modes is a common tool in the study of the cellular characteristic of a metabolic network. An elementary mode can be seen as a minimal set of reactions that can work in steady state independently of the rest of the network. It has therefore served as a mathematical model for the possible metabolic pathways of a cell. Their computation is not trivial and poses computational challenges. We show that some problems, like checking consistency of a network, finding one elementary mode or checking that a set of reactions constitutes a cut are easy problems, giving polynomial algorithms based on LP formulations. We also prove the hardness of central problems like finding a minimum size elementary mode, finding an elementary mode containing two given reactions, counting the number of elementary modes or finding a minimum reaction cut. On the enumeration problem, we show that enumerating all reactions containing one given reaction cannot be done in polynomial total time unless P=NP. This result provides some idea about the complexity of enumerating all the elementary modes. The search for precursor sets is motivated by discovering which external metabolites are sufficient to allow the production of a given set of target metabolites. In contrast with previous proposals, we present a new approach which is the first to formally consider the use of cycles in the way to produce the target. We present a polynomial algorithm to decide whether a set is a precursor set of a given target. We also show that, given a target set, finding a minimal precursor set is easy but finding a precursor set of minimum size is NP-hard. We further show that finding a solution with minimum size internal supply is NP-hard. We give a simple characterisation of precursors sets by the existence of hyperpaths between the solutions and the target. If we consider the enumeration of all the minimal precursor sets of a given target, we find that this problem cannot be solved in polynomial total time unless P=NP. Despite this result, we present two algorithms that have good performance for medium-size networks.

Any analysis of higher-order languages must grapple with the tri-facetted nature of lambda. In one construct, the fundamental control, environment and data structures of a language meet and intertwine. With the control facet tamed nearly two decades ago, this work brings the environment facet to heel, defining the environment problem and developing its solution: environment analysis. Environment analysis allows a compiler to reason about the equivalence of environments, i.e., name-to-value mappings, that arise during a program's execution. In this dissertation, two different techniques-abstract counting and abstract frame strings-make this possible. A third technique, abstract garbage collection, makes both of these techniques more precise and, counter to intuition, often faster as well. An array of optimizations and even deeper analyses which depend upon environment analysis provide motivation for this work. In an abstract interpretation, a single abstract entity represents a set of concrete entities. When the entities under scrutiny are bindings-single name-to-value mappings, the atoms of environment-then determining when the equality of two abstract bindings infers the equality of their concrete counterparts is the crux of environment analysis. Abstract counting does this by tracking the size of represented sets, looking for singletons, in order to apply the following principle: If {x} = {y}, then x = y. Abstract frame strings enable environmental reasoning by statically tracking the possible stack change between the births of two environments; when this change is effectively empty, the environments are equivalent. Abstract garbage collection improves precision by intermittently removing unreachable environment structure during abstract interpretation.