D'abord, on étudie trois façons d'associer une C*-algèbre à une transformation continue. Ensuite, nous donnons une nouvelle définition de l'entropie. Nous trouvons des relations entre les états KMS des algèbres préalablement définies et les états d'équilibre, donné par un principe variationnel. Dans la seconde partie, nous étudions les algèbres de Kajiwara-Watatani associees a un système des fonctions itérées. Nous comparons ces algèbres avec l'algèbre de Cuntz et le produit croisé. Enfin, nous étudions les états KMS des algèbres de Kajiwara-Watatani pour les actions provenant d'un potentiel et nous trouvouns des relations entre ces états et les mesures trouvee dans une version de le théorème de Ruelle-Perron-Frobenius pour les systèmes de fonctions itérées. / Primeiramente, estudamos três formas de associar uma C*-álgebra a uma transformação contínua. Em seguida, damos uma nova definição de entropia. Relacionamos, então, os estados KMS das álgebras anteriormente definidas com os estados de equilibro, vindos de um princípio variacional. Na segunda parte, estudamos as álgebras de Kajiwara-Watatani associadas a um sistema de funções iteradas. Comparamos tais álgebras com a álgebra de Cuntz e a álgebra do produto cruzado. Finalmente, estudamos os estados KMS das álgebras de Kajiwara-Watatani para ações vindas de um potencial e relacionamos tais estados KMS com medidas encontradas numa versão do teorema de Ruelle-Perron-Frobenius para sistemas de funções iteradas. / First, we study three ways of associating a C*-algebra to a continuous map. Then, we give a new de nition of entropy. We relate the KMS states of the previously de ned algebras with the equilibrium states, given by a variational principle. In the second part, we study the Kajiwara-Watatani algebras associated to iterated function system. We compare these algebras with the Cuntz algebra and the crossed product. Finally, we study the KMS states of the Kajiwara-Watatani algebras for actions coming from a potential and we relate such states with measures found in a version of the Ruelle-Perron- Frobenius theorem for iterated function systems.

D'abord, on étudie trois façons d'associer une C*-algèbre à une transformation continue. Ensuite, nous donnons une nouvelle définition de l'entropie. Nous trouvons des relations entre les états KMS des algèbres préalablement définies et les états d'équilibre, donné par un principe variationnel. Dans la seconde partie, nous étudions les algèbres de Kajiwara-Watatani associees a un système des fonctions itérées. Nous comparons ces algèbres avec l'algèbre de Cuntz et le produit croisé. Enfin, nous étudions les états KMS des algèbres de Kajiwara-Watatani pour les actions provenant d'un potentiel et nous trouvouns des relations entre ces états et les mesures trouvee dans une version de le théorème de Ruelle-Perron-Frobenius pour les systèmes de fonctions itérées. / Primeiramente, estudamos três formas de associar uma C*-álgebra a uma transformação contínua. Em seguida, damos uma nova definição de entropia. Relacionamos, então, os estados KMS das álgebras anteriormente definidas com os estados de equilibro, vindos de um princípio variacional. Na segunda parte, estudamos as álgebras de Kajiwara-Watatani associadas a um sistema de funções iteradas. Comparamos tais álgebras com a álgebra de Cuntz e a álgebra do produto cruzado. Finalmente, estudamos os estados KMS das álgebras de Kajiwara-Watatani para ações vindas de um potencial e relacionamos tais estados KMS com medidas encontradas numa versão do teorema de Ruelle-Perron-Frobenius para sistemas de funções iteradas. / First, we study three ways of associating a C*-algebra to a continuous map. Then, we give a new de nition of entropy. We relate the KMS states of the previously de ned algebras with the equilibrium states, given by a variational principle. In the second part, we study the Kajiwara-Watatani algebras associated to iterated function system. We compare these algebras with the Cuntz algebra and the crossed product. Finally, we study the KMS states of the Kajiwara-Watatani algebras for actions coming from a potential and we relate such states with measures found in a version of the Ruelle-Perron- Frobenius theorem for iterated function systems.

L'objet de cette thèse est l'étude du comportement asymptotique des systèmes de fonctions itérées (IFS). Dans un premier chapitre, nous présenterons les notions liées à l'étude de tels systèmes et nous rappellerons différentes applications possibles des IFS telles que les marches aléatoires sur des graphes ou des pavages apériodiques, les systèmes dynamiques aléatoires, la classification de protéines ou encore les mesures quantiques répétées. Nous nous attarderons sur deux autres applications : les chaînes de Markov d'ordre infini et d'ordre variable. Nous donnerons aussi les principaux résultats de la littérature concernant l'étude des mesures invariantes pour des IFS ainsi que ceux pour le calcul de la dimension de Hausdorff. Le deuxième chapitre sera consacré à l'étude d'une classe d'IFS composés de contractions sur des intervalles réels fermés dont les images se chevauchent au plus en un point et telles que les probabilités de transition sont constantes par morceaux. Nous donnerons un critère pour l'existence et pour l'unicité d'une mesure invariante pour l'IFS ainsi que pour la stabilité asymptotique en termes de bornes sur les probabilités de transition. De plus, quand il existe une unique mesure invariante et sous quelques hypothèses techniques supplémentaires, on peut montrer que la mesure invariante admet une dimension de Hausdorff exacte qui est égale au rapport de l'entropie sur l'exposant de Lyapunov. Ce résultat étend la formule, établie dans la littérature pour des probabilités de transition continues, au cas considéré ici des probabilités de transition constantes par morceaux. Le dernier chapitre de cette thèse est, quant à lui, consacré à un cas particulier d'IFS : les chaînes de Markov de longueur variable (VLMC). On démontrera que sous une condition de non-nullité faible et de continuité pour la distance ultramétrique des probabilités de transitions, elles admettent une unique mesure invariante qui est attractive pour la convergence faible. / The purpose of this thesis is the study of the asymptotic behaviour of iterated function systems (IFS). In a first part, we will introduce the notions related to the study of such systems and we will remind different applications of IFS such as random walks on graphs or aperiodic tilings, random dynamical systems, proteins classification or else $q$-repeated measures. We will focus on two other applications : the chains of infinite order and the variable length Markov chains. We will give the main results in the literature concerning the study of invariant measures for IFS and those for the calculus of the Hausdorff dimension. The second part will be dedicated to the study of a class of iterated function systems (IFSs) with non-overlapping or just-touching contractions on closed real intervals and adapted piecewise constant transition probabilities. We give criteria for the existence and the uniqueness of an invariant probability measure for the IFSs and for the asymptotic stability of the system in terms of bounds of transition probabilities. Additionally, in case there exists a unique invariant measure and under some technical assumptions, we obtain its exact Hausdorff dimension as the ratio of the entropy over the Lyapunov exponent. This result extends the formula, established in the literature for continuous transition probabilities, to the case considered here of piecewise constant probabilities. The last part is dedicated to a special case of IFS : Variable Length Markov Chains (VLMC). We will show that under a weak non-nullness condition and continuity for the ultrametric distance of the transition probabilities, they admit a unique invariant measure which is attractive for the weak convergence.

D'abord, on étudie trois façons d'associer une C*-algèbre à une transformation continue. Ensuite, nous donnons une nouvelle définition de l'entropie. Nous trouvons des relations entre les états KMS des algèbres préalablement définies et les états d'équilibre, donné par un principe variationnel. Dans la seconde partie, nous étudions les algèbres de Kajiwara-Watatani associees a un système des fonctions itérées. Nous comparons ces algèbres avec l'algèbre de Cuntz et le produit croisé. Enfin, nous étudions les états KMS des algèbres de Kajiwara-Watatani pour les actions provenant d'un potentiel et nous trouvouns des relations entre ces états et les mesures trouvee dans une version de le théorème de Ruelle-Perron-Frobenius pour les systèmes de fonctions itérées. / Primeiramente, estudamos três formas de associar uma C*-álgebra a uma transformação contínua. Em seguida, damos uma nova definição de entropia. Relacionamos, então, os estados KMS das álgebras anteriormente definidas com os estados de equilibro, vindos de um princípio variacional. Na segunda parte, estudamos as álgebras de Kajiwara-Watatani associadas a um sistema de funções iteradas. Comparamos tais álgebras com a álgebra de Cuntz e a álgebra do produto cruzado. Finalmente, estudamos os estados KMS das álgebras de Kajiwara-Watatani para ações vindas de um potencial e relacionamos tais estados KMS com medidas encontradas numa versão do teorema de Ruelle-Perron-Frobenius para sistemas de funções iteradas. / First, we study three ways of associating a C*-algebra to a continuous map. Then, we give a new de nition of entropy. We relate the KMS states of the previously de ned algebras with the equilibrium states, given by a variational principle. In the second part, we study the Kajiwara-Watatani algebras associated to iterated function system. We compare these algebras with the Cuntz algebra and the crossed product. Finally, we study the KMS states of the Kajiwara-Watatani algebras for actions coming from a potential and we relate such states with measures found in a version of the Ruelle-Perron- Frobenius theorem for iterated function systems.

Made available in DSpace on 2016-03-15T19:37:41Z (GMT). No. of bitstreams: 0 Previous issue date: 2011-08-22 / Fundo Mackenzie de Pesquisa / A new image compression technique is proposed, based on the affine transformations (ATs) that define an iterated function system (IFS). Previous related research in the field has shown that an image may be approximated by iteratively subjecting a set of sub-regions to a group of ATs. In this case, the original image should be partitioned in regions, and each one of the active pixels are transformed by the AT. The new transformed set should be approximated to other image regions. This iterated execution to find ATs for the best set of areas might result in smaller storage space since the similar areas might be replaced by AT coefficients. Despite this advantage, the technique is computationally intensive, because both the sub-regions and the corresponding ATs that have to be searched for. Here, a new form of similarity is proposed, based on the successive points generated by the iteration of affine transformations. By understanding an AT as a discrete dynamical system, with each image point represented by an iteration of the AT, the method captures similarities between these points, namely, those with the same color in the image; by saving the starting point and the transformations coefficients, the points can be iterated back, to reconstruct the original image. This results in lighter computational effort, since the comparison is made point by point, instead of region by region. Experiments were made on a group of 10 images, representing a broad set of distinct features and resolutions. The proposed algorithm competes in terms of storage size, when compared to JPEG, mainly when the image size is small, and the number of colors are reduced, as currently happens for most images used in the Internet. Although the proposed method is faster than the traditional method for IFS compression, it is slower than common file formats like JPEG. / Uma nova técnica para compressão de imagens é proposta, baseada em conjuntos de transformações afins (affine transformations - ATs), normalmente conhecidos como sistemas de funções iteradas (iterated function system - IFS). Pesquisas anteriores mostraram que uma imagem poderia ser aproximada pela aplicação de um grupo de ATs em conjuntos de sub-regiões da imagem, de forma iterativa. Através deste processo, a imagem original seria subdividida em regiões e sobre a coordenada de cada ponto habilitado de cada região seria aplicada uma transformação afim. O resultado representaria um novo conjunto de pontos similares a outras regiões da imagem. A execução de forma iterada deste processo de identificação das ATs para o maior conjunto de regiões similares de uma determinada imagem permitiria uma redução no armazenamento, já que as regiões similares poderiam ser armazenadas como os coeficientes das transformações afins. Apesar desta vantagem em termos de compressão, a técnica é computacionalmente intensiva, pela busca exaustiva de sub-regiões e das ATs geradoras, de forma a proporcionar o melhor preenchimento em outras regiões da imagem. Esta pesquisa propõe uma nova forma de compressão baseada em ATs, utilizando a sequência de pontos gerada pela iteração das ATs. Entendendo uma AT como um sistema dinâmico em tempo discreto, cada novo ponto identificado é consequência direta da iteração da AT sobre o ponto anterior, permitindo a captura de similaridades nesta sequência de pontos. Através do salvamento dos coeficientes das ATs e das coordenadas iniciais, é possível a reconstrução da imagem pela iteração da AT a partir do ponto inicial. Isto pode resultar em menor esforço computacional, pois apenas comparações simples de pontos são necessárias, ao invés de comparações entre os pontos de regiões da imagem. Foram feitos experimentos em um conjunto de 10 classes de imagens, representando um espectro de diferentes características gerais e resoluções. O algoritmo proposto rivaliza em termos de armazenamento quando comparado ao formato JPEG, principalmente para imagens de pequeno tamanho e com número de cores reduzidas, como as utilizadas com frequência na Internet. Apesar de ser mais rápido para a compressão do que outros métodos baseados em IFS, ele é mais lento do que métodos clássicos como o JPEG.

La thèse propose quatre contributions sur la méthode axiomatique. Les trois premiers chapitres utilisent le formalisme des jeux coopératifs à utilité transférable. Dans les deux premiers chapitres, une étude systématique de l'opération de nullification est menée. Les axiomes de retraits sont transformés en axiomes de nullification. Des caractérisations existantes de règles d’allocation sont revisitées, et des résultats totalement neufs sont présentés. Le troisième chapitre introduit et caractérise une valeur de Shapley proportionnelle, où les dividendes d’Harsanyi sont partagés en proportion des capacités des singletons concernés. Le quatrième chapitre propose une variante multi-dimensionnelle de l’indice de Hirsch. Une caractérisation axiomatique et une application aux classements sportifs sont fournies. / The dissertation provides four contributions on the axiomatic method. The first three chapters deal with cooperative games with transferable utility. In the first two chapters, a systematic study of the nullification operation is done. The removal axioms are translated into their nullified counterparts. Some existing characterizations are revisited, and completely new results are presented. The third chapter introduces and characterizes a proportional Shapley value in which the Harsanyi dividends are shared in proportion to the stand-alone worths of the concerned players. The fourth chapter proposes a multi-dimensional variant of the Hirsch index. An axiomatic characterization and an application to sports rankings are provided.

This thesis investigates decision-making in two-player imperfect information games against opponents whose actions can affect our rewards, and whose strategies may be based on memories of interaction, or may be changing, or both. The focus is on modelling these dynamic opponents, and using the models to learn high-reward strategies. The main contributions of this work are: 1. An approach to learn high-reward strategies in small simultaneous-move games against these opponents. This is done by using a model of the opponent learnt from sequence prediction, with (possibly discounted) rewards learnt from reinforcement learning, to lookahead using explicit tree search. Empirical results show that this gains higher average rewards per game than state-of-the-art reinforcement learning agents in three simultaneous-move games. They also show that several sequence prediction methods model these opponents effectively, supporting the idea of using them from areas such as data compression and string matching; 2. An online expectation-maximisation algorithm that infers an agent's hidden information based on its behaviour in imperfect information games; 3. An approach to learn high-reward strategies in medium-size sequential-move poker games against these opponents. This is done by using a model of the opponent learnt from sequence prediction, which needs its hidden information (inferred by the online expectation-maximisation algorithm), to train a state-of-the-art no-regret learning algorithm by simulating games between the algorithm and the model. Empirical results show that this improves the no-regret learning algorithm's rewards when playing against popular and state-of-the-art algorithms in two simplified poker games; 4. Demonstrating that several change detection methods can effectively model changing categorical distributions with experimental results comparing their accuracies to empirical distributions. These results also show that their models can be used to outperform state-of-the-art reinforcement learning agents in two simultaneous-move games. This supports the idea of modelling changing opponent strategies with change detection methods; 5. Experimental results for the self-play convergence to mixed strategy Nash equilibria of the empirical distributions of plays of sequence prediction and change detection methods. The results show that they converge faster, and in more cases for change detection, than fictitious play.

Ce mémoire présente une nouvelle méthode d’étudier des fonctions de Morse sur une variété compacte. Plus précisément, les croisements entre les lignes de flot de pseudo-gradients associés à des fonctions de Morse permettent de définir géométriquement des morphismes entre les complexes de Morse, morphismes qui ne peuvent généralement pas être obtenus par une homotopie. Cette nouvelle classe de morphismes mène à la définition d’une catégorie triangulée. La question centrale est de savoir si tout objet de cette catégorie est décomposable en cône itéré de fonctions de Morse parfaites. En effet, une telle décomposition simplifierait l’étude de la dynamique d’une fonction de Morse en l’interprétant plutôt comme plusieurs fonctions parfaites. Une seconde question d’importance porte sur une condition de généricité globale à laquelle est soumise cette catégorie triangulée. Nous étudions la possibilité de s’en soustraire en proposant une méthode de déformations des fonctions de Morse. / This master’s thesis introduces a new way to sudy Morse functions on a compact manifold. More specifically, crossings between flows of pseudo-gradients associated to Morse functions allow one to define geometric realisations of morphisms between the Morse complexes. This new class of morphisms leads to the definition of a triangulated category. The main question is to determine if every object of this category admits an iterated cone decomposition. Such a decomposition would greatly simplify the study of the dynamic of a Morse function by interpreting it as many perfect Morse functions. A second topic concerns the global genericity condition to which this category is subject. We study a way, through deformation of Morse functions, to avoid such a constraint.

No description available.

Tesis por compendio / [EN] Nowadays, manufacturing systems meet different new global challenges and the existence of a collaborative manufacturing environment is essential to face with. Distributed manufacturing and assembly systems are two manufacturing systems which allow industries to deal with some of these challenges. This thesis studies a production problem in which both distributed manufacturing and assembly systems are considered. Although distributed manufacturing systems and assembly systems are well-known problems and have been extensively studied in the literature, to the best of our knowledge, considering these two systems together as in this thesis is the first effort in the literature. Due to the importance of scheduling optimization on production performance, some different ways to optimize the scheduling of the considered problem are discussed in this thesis. The studied scheduling setting consists of two stages: A production and an assembly stage. Various production centers make the first stage. Each of these centers consists of several machines which are dedicated to manufacture jobs. A single assembly machine is considered for the second stage. The produced jobs are assembled on the assembly machine to form final products through a defined assembly program. In this thesis, two different problems regarding two different production configurations for the production centers of the first stage are considered. The first configuration is a flowshop that results in what we refer to as the Distributed Assembly Permutation Flowshop Scheduling Problem (DAPFSP). The second problem is referred to as the Distributed Parallel Machine and Assembly Scheduling Problem (DPMASP), where unrelated parallel machines configure the production centers. Makespan minimization of the product on the assembly machine located in the assembly stage is considered as the objective function for all considered problems. In this thesis some extensions are considered for the studied problems so as to bring them as close as possible to the reality of production shops. In the DAPFSP, sequence dependent setup times are added for machines in both production and assembly stages. Similarly, in the DPMASP, due to technological constraints, some defined jobs can be processed only in certain factories. Mathematical models are presented as an exact solution for some of the presented problems and two state-of-art solvers, CPLEX and GUROBI are used to solve them. Since these solvers are not able to solve large sized problems, we design and develop heuristic methods to solve the problems. In addition to heuristics, some metaheuristics are also designed and proposed to improve the solutions obtained by heuristics. Finally, for each proposed problem, the performance of the proposed solution methods is compared through extensive computational and comprehensive ANOVA statistical analysis. / [ES] Los sistemas de producción se enfrentan a retos globales en los que el concepto de fabricación colaborativa es crucial para poder tener éxito en el entorno cambiante y complejo en el que nos encontramos. Una característica de los sistemas productivos que puede ayudar a lograr este objetivo consiste en disponer de una red de fabricación distribuida en la que los productos se fabriquen en localizaciones diferentes y se vayan ensamblando para obtener el producto final. En estos casos, disponer de modelos y herramientas para mejorar el rendimiento de sistemas de producción distribuidos con ensamblajes es una manera de asegurar la eficiencia de los mismos. En esta tesis doctoral se estudian los sistemas de fabricación distribuidos con operaciones de ensamblaje. Los sistemas distribuidos y los sistemas con operaciones de ensamblaje han sido estudiados por separado en la literatura. De hecho, no se han encontrado estudios de sistemas con ambas características consideradas de forma conjunta. Dada la complejidad de considerar conjuntamente ambos tipos de sistemas a la hora de realizar la programación de la producción en los mismos, se ha abordado su estudio considerando un modelo bietápico en la que en la primera etapa se consideran las operaciones de producción y en la segunda se plantean las operaciones de ensamblaje. Dependiendo de la configuración de la primera etapa se han estudiado dos variantes. En la primera variante se asume que la etapa de producción está compuesta por sendos sistemas tipo flowshop en los que se fabrican los componentes que se ensamblan en la segunda etapa (Distributed Assembly Permutation Flowshop Scheduling Problem o DAPFSP). En la segunda variante se considera un sistema de máquinas en paralelo no relacionadas (Distributed Parallel Machine and Assembly Scheduling Problem o DPMASP). En ambas variantes se optimiza la fecha de finalización del último trabajo secuenciado (Cmax) y se contempla la posibilidad que existan tiempos de cambio (setup) dependientes de la secuencia de trabajos fabricada. También, en el caso DPMASP se estudia la posibilidad de prohibir o no el uso de determinadas máquinas de la etapa de producción. Se han desarrollado modelos matemáticos para resolver algunas de las variantes anteriores. Estos modelos se han resuelto mediante los programas CPLEX y GUROBI en aquellos casos que ha sido posible. Para las instancias en los que el modelo matemático no ofrecía una solución al problema se han desarrollado heurísticas y metaheurísticas para ello. Todos los procedimientos anteriores han sido estudiados para determinar el rendimiento de los diferentes algoritmos planteados. Para ello se ha realizado un exhaustivo estudio computacional en el que se han aplicado técnicas ANOVA. Los resultados obtenidos en la tesis permiten avanzar en la comprensión del comportamiento de los sistemas productivos distribuidos con ensamblajes, definiendo algoritmos que permiten obtener buenas soluciones a este tipo de problemas tan complejos que aparecen tantas veces en la realidad industrial. / [CA] Els sistemes de producció s'enfronten a reptes globals en què el concepte de fabricació col.laborativa és crucial per a poder tindre èxit en l'entorn canviant i complex en què ens trobem. Una característica dels sistemes productius que pot ajudar a aconseguir este objectiu consistix a disposar d'una xarxa de fabricació distribuïda en la que els productes es fabriquen en localitzacions diferents i es vagen acoblant per a obtindre el producte final. En estos casos, disposar de models i ferramentes per a millorar el rendiment de sistemes de producció distribuïts amb acoblaments és una manera d'assegurar l'eficiència dels mateixos. En esta tesi doctoral s'estudien els sistemes de fabricació distribuïts amb operacions d'acoblament. Els sistemes distribuïts i els sistemes amb operacions d'acoblament han sigut estudiats per separat en la literatura però, en allò que es coneix, no s'han trobat estudis de sistemes amb ambdós característiques conjuntament. Donada la complexitat de considerar conjuntament ambdós tipus de sistemes a l'hora de realitzar la programació de la producció en els mateixos, s'ha abordat el seu estudi considerant un model bietàpic en la que en la primera etapa es consideren les operacions de producció i en la segona es plantegen les operacions d'acoblament. Depenent de la configuració de la primera etapa s'han estudiat dos variants. En la primera variant s'assumix que l'etapa de producció està composta per sengles sistemes tipus flowshop en els que es fabriquen els components que s'acoblen en la segona etapa (Distributed Assembly Permutation Flowshop Scheduling Problem o DAPFSP). En la segona variant es considera un sistema de màquines en paral.lel no relacionades (Distributed Parallel Machine and Assembly Scheduling Problem o DPMASP). En ambdós variants s'optimitza la data de finalització de l'últim treball seqüenciat (Cmax) i es contempla la possibilitat que existisquen temps de canvi (setup) dependents de la seqüència de treballs fabricada. També, en el cas DPMASP s'estudia la possibilitat de prohibir o no l'ús de determinades màquines de l'etapa de producció. S'han desenvolupat models matemàtics per a resoldre algunes de les variants anteriors. Estos models s'han resolt per mitjà dels programes CPLEX i GUROBI en aquells casos que ha sigut possible. Per a les instàncies en què el model matemàtic no oferia una solució al problema s'han desenrotllat heurístiques i metaheurísticas per a això. Tots els procediments anteriors han sigut estudiats per a determinar el rendiment dels diferents algoritmes plantejats. Per a això s'ha realitzat un exhaustiu estudi computacional en què s'han aplicat tècniques ANOVA. Els resultats obtinguts en la tesi permeten avançar en la comprensió del comportament dels sistemes productius distribuïts amb acoblaments, definint algoritmes que permeten obtindre bones solucions a este tipus de problemes tan complexos que apareixen tantes vegades en la realitat industrial. / Hatami, S. (2016). The Distributed and Assembly Scheduling Problem [Tesis doctoral]. Universitat Politècnica de València. https://doi.org/10.4995/Thesis/10251/64072 / Compendio