O objetivo deste trabalho é apresentar o modelo dos autômatos adaptativos de segunda ordem e mostrar a forte conexão desse modelo com o aprendizado indutivo no limite. Tal modelo é definido com a utilização de um conjunto de transformações sobre autômatos finitos não - determinísticos e a conexão com o aprendizado no limite á estabelecida usando o conceito de mutação composta, onde uma hipótese inicial dá início ao processo de aprendizagem, produzindo, após uma sequência de transformações sofridas por essa primeira hipótese, um modelo final que é o resultado correto do aprendizado. Será apresentada a prova de que um autômato adaptativos de segunda ordem, usado como um aprendiz, pode realizar o processo de aprendizado no limite. O formalismo dos autômatos adaptativos de segunda ordem é desenvolvido sobre o modelo dos autômatos adaptativos de primeira ordem, uma extensão natural do modelo dos autômatos adaptativos clássicos. Embora tenha o mesmo poder computacional, o autômato adaptativo de primeira ordem apresenta uma notação mais simples e rigorosa que o seu antecessor, permitindo derivar novas propriedades. Uma dessas propriedades é justamente sua capacidade de aprendizado. Como consequência, o modelo dos autômatos adaptativos de segunda ordem aumenta a expressividade computacional dos dispositivos adaptativos através da sua notação recursiva, e também através do seu potencial para o uso em aplicações de aprendizado de máquina, ilustrados nesta tese. Uma arquitetura de aprendizado de máquina usando os autômatos adaptativos de segunda ordem é proposto e um modelo de identificação no limite, aplicado em processos de inferência para linguagens livre de contexto, é apresentado. / The purpose of this work is to present the second-order adaptive automaton under an transformation automata approach and to show the strong connection of this model with learning in the limit. The connection is established using the adaptive mutations, in which any hypothesis can be used to start a learning process, and produces a correct final model following a step-by-step transformation of that hypothesis by a second-order adaptive automaton. Second-order adaptive automaton learner will be proved to acts as a learning in the limit. The presented formalism is developed over the first-order adaptive automaton, a natural and unified extension of the classical adaptive automaton. First-order adaptive automaton is a new and better representation for the adaptive finite automaton and to also show that both formulations the original and the newly created have the same computational power. Afterwards both formulations show to be equivalent in representation and in computational power, but the new one has a highly simplified notation. The use of the new formulation actually allows simpler theorem proofs and generalizations, as can be verified in this work. As results, the second-order adaptive automaton enhances the computational expressiveness of adaptive automaton through its recursive notation, and also its skills for the use in machine learning applications were illustrated here. An architecture of machine learning to use the adaptive technology is proposed and the model of identification in limit applied in inference processes for free-context languages.

O objetivo deste trabalho é apresentar o modelo dos autômatos adaptativos de segunda ordem e mostrar a forte conexão desse modelo com o aprendizado indutivo no limite. Tal modelo é definido com a utilização de um conjunto de transformações sobre autômatos finitos não - determinísticos e a conexão com o aprendizado no limite á estabelecida usando o conceito de mutação composta, onde uma hipótese inicial dá início ao processo de aprendizagem, produzindo, após uma sequência de transformações sofridas por essa primeira hipótese, um modelo final que é o resultado correto do aprendizado. Será apresentada a prova de que um autômato adaptativos de segunda ordem, usado como um aprendiz, pode realizar o processo de aprendizado no limite. O formalismo dos autômatos adaptativos de segunda ordem é desenvolvido sobre o modelo dos autômatos adaptativos de primeira ordem, uma extensão natural do modelo dos autômatos adaptativos clássicos. Embora tenha o mesmo poder computacional, o autômato adaptativo de primeira ordem apresenta uma notação mais simples e rigorosa que o seu antecessor, permitindo derivar novas propriedades. Uma dessas propriedades é justamente sua capacidade de aprendizado. Como consequência, o modelo dos autômatos adaptativos de segunda ordem aumenta a expressividade computacional dos dispositivos adaptativos através da sua notação recursiva, e também através do seu potencial para o uso em aplicações de aprendizado de máquina, ilustrados nesta tese. Uma arquitetura de aprendizado de máquina usando os autômatos adaptativos de segunda ordem é proposto e um modelo de identificação no limite, aplicado em processos de inferência para linguagens livre de contexto, é apresentado. / The purpose of this work is to present the second-order adaptive automaton under an transformation automata approach and to show the strong connection of this model with learning in the limit. The connection is established using the adaptive mutations, in which any hypothesis can be used to start a learning process, and produces a correct final model following a step-by-step transformation of that hypothesis by a second-order adaptive automaton. Second-order adaptive automaton learner will be proved to acts as a learning in the limit. The presented formalism is developed over the first-order adaptive automaton, a natural and unified extension of the classical adaptive automaton. First-order adaptive automaton is a new and better representation for the adaptive finite automaton and to also show that both formulations the original and the newly created have the same computational power. Afterwards both formulations show to be equivalent in representation and in computational power, but the new one has a highly simplified notation. The use of the new formulation actually allows simpler theorem proofs and generalizations, as can be verified in this work. As results, the second-order adaptive automaton enhances the computational expressiveness of adaptive automaton through its recursive notation, and also its skills for the use in machine learning applications were illustrated here. An architecture of machine learning to use the adaptive technology is proposed and the model of identification in limit applied in inference processes for free-context languages.

Uma sequência de imagens de satélite climático é processada aplicando-se um conjunto de operações de filtros, no intuito de extrair padrões de comportamento das nuvens. Caracteres são criados a partir deste tratamento e suas transições são investigadas, explorando a possibilidade de justificar suas ocorrências através de linguagens formais e linguagens bidimensionais, definindo suas gramáticas. Com esta contagem de transições, uma análise de sua forma fractal é iniciada e um paralelo com outras contagens estabelecida, como uma forma de estruturar um modelo computacionalmente menos complexo de prever o tempo, ou o comportamento de qualquer entidade dinâmica que possa ser discretizada. Com estas investigações e experiências, foi possível diminuir a quantidade de símbolos utilizados para justificar as formas das nuvens, bem como criar classes de equivalências para representar conjuntos de símbolos que compartilham as mesmas propriedades, diminuindo ainda mais a complexidade da gramática que se espera encontrar. / A sequence of weather satellite images are processed by applying a set of filtering operations in order to extract the behavior patterns of clouds. Characters are created from this treatment and their transitions are investigated by exploring the possibility of justifying their occurrence across formal languages and two-dimensional languages, defining their grammar. With these count transitions an analysis of their fractals starts and counts a parallel with others established as a way to structure a model less computationally complex to predict the weather, or the behavior of any dynamic entity that could be discretized. With these investigations and experiments, it was possible to reduce the number of symbols used to explain the shapes of clouds and create equivalent classes to represent the symbol sets that share the same properties, further reducing the complexity of the grammar expected to be found.

Apesar das novas e efetivas técnicas de engenharia de software, os projetos de desenvolvimento de sistemas estão propensos a ter os mesmos problemas que acometem o software de apoio à gestão. Entrega com atraso, acima do orçamento e não suprindo as reais necessidades dos usuários finais ou da organização que está financiando o desenvolvimento do sistema, são os principais problemas. Esse último problema é o que mais afeta o desenvolvimento de sistemas e é um desafio para que o desenvolvimento personalizado seja uma solução real para várias empresas. Este trabalho apresenta uma proposta de método de gestão que auxilie a comunicação entre as atividades associadas à engenharia de requisitos e as atividades associadas à modelagem dos processos de negócio. Essa abordagem concerne à gestão e tratamento de requisitos de sistemas baseando-se em técnicas de engenharia de processos de negócios e de engenharia de requisitos, no processo unificado de desenvolvimento de software e na utilização de linguagens semi-formais e formais de modelagem, UML e SysML respectivamente. O método pretende mitigar os efeitos dos problemas de comunicação existentes entre os diversos integrantes de um projeto, com especial atenção para a comunicação entre a equipe de requisitos do projeto e os stakeholders responsáveis pela aceitação e aprovação do sistema. A pesquisa, com o apoio da apresentação de dois casos que ilustram o método de gestão proposto, permite concluir que é possível tornar mais efetiva e produtiva a comunicação entre os diversos envolvidos com o projeto, podendo resultar em um processo mais eficiente para a aceitação dos requisitos junto aos stakeholders. / Despite new and effective software engineering techniques, system development projects are likely to have the same problems that affect the management support software. Delivery delay, above budget and not fitting the real needs of end users or the organization that is funding the system development, are the most common problems. The latter problem is the one that most affects the systems development and is a challenge for the custom development to be a real solution to several companies. This work presents a proposal for a management method to help the communication between the activities associated with the engineering requirements and the activities associated with business processes modeling. This approach, concerns to the systems requirements treatment and management, is based on business processes engineering and requirements engineering, in software development unified process and in the use of semi-formal and formal modeling languages as UML and SysML, respectively. The method seeks to mitigate the effects of the communication problems among the project members, with special attention to the communication between the project requirements team and the stakeholders responsible for the system acceptance and adoption. The research, supported by the presentation of two cases which illustrates the proposed management method, has concluded that it is possible to make more effective and productive communication among members related with the project, which may result a more efficient process for the stakeholders requirement acceptance.

Cette thèse s'articule autour de la gestion de ressources explicites dans les langages fonctionnels, en mettant l'accent sur des propriétés de calculs avec substitutions explicites raffinant le lambda-calcul. Dans une première partie, on s'intéresse à la propriété de préservation de la beta-normalisation forte (PSN) pour le calcul lambda s. Dans une seconde partie, on étudie la propriété de confluence pour un large ensemble de calculs avec substitutions explicites. Après avoir donné une preuve générique de confluence basée sur une série d'axiomes qu'un calcul doit satisfaire, on se focalise sur la métaconfluence de lambda j, un calcul où le mécanisme de propagation des substitutions utilise la notion de multiplicité, au lieu de celle de structure. Dans la troisième partie de la thèse on définit un prisme des ressources qui généralise de manière paramétrique le lambda-calcul dans le sens où non seulement la substitution peut être explicite, mais également la contraction et l'affaiblissement. Cela donne un ensemble de huit calculs répartis sur les sommets du prisme pour lesquels on prouve de manière uniforme plusieurs propriétés de bon comportement comme par exemple la simulation de la beta-réduction, la PSN, la confluence, et la normalisation forte pour les termes typés. Dans la dernière partie de la thèse on montre différentes ouvertures vers des domaines plus pratiques. On s'intéresse à la complexité d'un calcul avec substitutions en premier lieu. On présente des outils de recherche et on conjecture des bornes maximales. Enfin, on finit en donnant une spécification formelle du calcul lambda j dans l'assistant à la preuve Coq.

Les langages formels sont des séquences sur un ensemble discret de symboles appelé alphabet. On les spécifie souvent par des formules dans une certaine logique, par des expressions rationnelles ou bien par des automates discrets de types variés. La théorie actuelle est principalement qualitative, dans le sens où ses objets sont des séquence sur un temps discret, non-métrique, dans le sens où l'acceptation d'une séquence sur un automate dépend du fait que l'on visite ou non un état accepteur, et enfin dans le sens où la comparaison de langages est plus souvent considérée en termes d'inclusion, plutôt qu'en termes de mesures quantitatives. Cette thèse contribue à l'étude de ces aspects souvent négligés en présentant des résultats fondamentaux dans trois nouvelles classes de problèmes quantitatifs sur les langages formels. Dans la première partie, nous étudions une classe de problèmes d'ordonnancement qui combine les aspects structurels associés aux dépendances entre tâches avec les aspects dynamiques liés au fait qu'un flux de requêtes arrive en continu pendant l'exécution. Nous montrons que, dans cette classe de problèmes, certains flux, pourtant admissibles dans le sens que les requêtes ne représentent pas plus de travail que ce que les machines peuvent traiter, ne peuvent pas être ordonnancé avec une latence bornée. Cependant nous développons une politique d'ordonnancement que peut garantir une accumulation de retard bornée pour tout flux de requêtes admissible, même sans le connaître à l'avance. Nous montrons que si les flux sont sous-critiques, alors cette même politique peut garantir une latence bornée. En vérification quantitative, les états et transitions d'un système peuvent être associés à des coûts, et ceux-ci utilisés pour associer des coûts moyens aux comportements infinis. Dans cette seconde partie, nous proposons de définir des omega-langages par des requêtes booléennes sur les coûts moyens. Des spécifications concernant des moyennes, tels que " le taux de perte moyen de messages est inférieur à un certain seuil " ne sont pas omega-régulières, mais exprimables dans notre modèle. Ainsi, nous étudions l'expressivité et la complexité de Borel de telles spécifications. Nous montrons que pour la clôture par intersection, il est nécessaire de considérer des coûts multi-dimensionnels. Nous mettons en évidence que dans le cas général, les conditions d'acceptation portent sur l'ensemble des points d'accumulation de la séquence des coûts moyens des préfixes d'une exécution, et nous donnons une caractérisation précise de tels ensembles. Nous proposons une classe de langages de coût moyen à seuils multiples, comparant les coordonnées minimales et minimales des points de cet ensemble à des constantes. Nous montrons enfin que cette classe est close par opérations booléennes et analysable. Enfin, dans le dernier volet, nous définissons deux mesures pour un langage temporisé : le volume de ses sous-langages de mots à nombre d'événements fixe et l'entropie (vitesse de croissance), mesure asymptotique pour un nombre non borné d'événements. Ces mesures peuvent être utilisées pour la comparaison quantitative de langages, et l'entropie peut être vue comme la quantité d'information par événement dans un mot typique du langage temporisé. Pour les langages acceptés par des automates temporisés déterministes, nous donnons une formule exacte pour le volume. Ensuite, nous caractérisons l'entropie, en utilisant des méthodes d'analyse fonctionnelle, en tant que logarithme du rayon spectral d'un opérateur intégral positif. Nous établissons plusieurs méthodes pour calculer l'entropie : une symbolique pour les automates que nos appelons " à une horloge et demie ", et deux numériques : une utilisant les techniques d'analyse fonctionnelle, l'autre basée sur la discrétisation. Nous donnons une interprétation de l'entropie en théorie de l'information en termes de complexité de Kolmogorov.

High Performance Computing (HPC) aims at providing reasonably fast computing solutions to both scientific and real life technical problems. Many efforts have indeed been made on the way to powerful supercomputers, both generic and customized configurations. However, whatever their current and future breathtaking capabilities, supercomputers work by brute force and deterministic steps, while human mind works by few strokes of brilliance. Thus, in order to take a significant advantage of hardware advances, we need powerful methods to solve problems together with highly skillful programming efforts and relevant frameworks. The advent of multicore architectures is noteworthy in the HPC history, because it has brought the underlying concept of multiprocessing into common consideration and has changed the landscape of standard computing. At a larger scale, there is a keen desire to build or host frontline supercomputers. The yearly Top500 ranking nicely illustrates and orchestrates this supercomputers saga. For many years, computers have been falling in price while gaining processing power often strengthened by specialized accelerator units. We clearly see that what commonly springs up in mind when it comes to HPC is computer capability. However, this availability of increasingly fast computers has changed the rule of scientific discovery and has motivated the consideration of challenging applications. Thus, we are routinely at the door of large-scale problems, and most of time, the speed of calculation by itself is no longer sufficient. Indeed, the real concern of HPC users is the time-to-output. Thus, we need to study each important aspect in the critical path between inputs and outputs, and keep striving to reach the expected level of performance. This is the main concern of the viewpoints and the achievements reported in this book. The document is organized into five chapters articulated around our main contributions. The first chapter depicts the landscape of supercomputers, comments the need for tremendous processing speed, and analyze the main trends in supercomputing. The second chapter deals with solving large-scale combinatorial problems through a mixture of continuous and discrete optimization methods, we describe the main generic approaches and present an important framework on which we have been working so far. The third chapter is devoted to the topic accelerated computing, we discuss the motivations and the issues, and we describe three case studies from our contributions. In chapter four, we address the topic of energy minimization in a formal way and present our method based on a mathematical programming approach. Chapter five debates on hybrid supercomputing, we discuss technical issues with hierarchical shared memories and illustrate hybrid coding through a large-scale linear algebra implementation on a supercomputer.

Machine learning has risen in importance across science, engineering, and business in recent years. Domain experts have begun to understand how their data analysis problems can be solved in a principled and efficient manner using methods from machine learning, with its simultaneous focus on statistical and computational concerns. Moreover, the data in many of these application domains has exploded in availability and scale, further underscoring the need for algorithms which find patterns and trends quickly and correctly. However, most people actually analyzing data today operate far from the expert level. Available statistical libraries and even textbooks contain only a finite sample of the possibilities afforded by the underlying mathematical principles. Ideally, practitioners should be able to do what machine learning experts can do--employ the fundamental principles to experiment with the practically infinite number of possible customized statistical models as well as alternative algorithms for solving them, including advanced techniques for handling massive datasets. This would lead to more accurate models, the ability in some cases to analyze data that was previously intractable, and, if the experimentation can be greatly accelerated, huge gains in human productivity. Fixing this state of affairs involves mechanizing and automating these statistical and algorithmic principles. This task has received little attention because we lack a suitable syntactic representation that is capable of specifying machine learning problems and solutions, so there is no way to encode the principles in question, which are themselves a mapping between problem and solution. This work focuses on providing the foundational layer for enabling this vision, with the thesis that such a representation is possible. We demonstrate the thesis by defining a syntactic representation of machine learning that is expressive, promotes correctness, and enables the mechanization of a wide variety of useful solution principles.

Nous nous intéressons à la représentation de graphes dans le prouveur Coq. Nous avons choisi de les représenter par des types coinductifs dont nous voulions explorer l'utilisation. Ceux-ci permettent de rendre succincte et élégante la représentation et d'obtenir la navigabilité par construction. Nous avons dû contourner la condition de garde dont le but est d'assurer la validité des opérations effectuées sur les objets coinductifs. Son implantation dans Coq est restrictive et interdit parfois des définitions sémantiquement correctes. Une formalisation canonique des graphes dépasse ainsi l'expressivité directe de Coq. Nous avons donc proposé une solution respectant ces limitations, puis nous avons défini une relation sur les graphes nous permettant d'obtenir la même notion d'équivalence qu'avec une représentation classique tout en gardant les avantages de la coinduction. Nous montrons qu'elle est équivalente à une relation basée sur des observations finies.

This paper deals with a connection between two decision problems for recognizable trace languages: the star problem and the finite power property problem. Due to a theorem by Richomme from 1994 [26, 28], we know that both problems are decidable in trace monoids which do not contain a C4 submonoid. It is not known, whether the star problem or the finite power property are decidable in the C4 or in trace monoids containing a C4. In this paper, we show a new connection between these problems. Assume a trace monoid IM (Σ, I) which is isomorphic to the Cartesian Product of two disjoint trace monoids IM (Σ1, I1) and IM (Σ2, I2). Assume further a recognizable language L in IM (Σ, I) such that every trace in L contains at least one letter in Σ1 and at least in one letter in Σ2. Then, the main theorem of this paper asserts that L* is recognizable iff L has the finite power property.